ＣＩＲ、ＲＴＴ和ＲＴＯ感知的三色標記算法
2008-12-31 00:00:00楊貫中湯亮
計算機應用研究 2008年9期
摘 要：往返時間(RTT)、目標速度（CIR）以及重傳超時(RTO)等因素導致了帶寬分配的不均勻。通過研究帶寬與這些因素的關系，在時間滑動窗口三色標記器（TSW3CM）的基礎上，提出一種CIR、RTT、RTO感知的標記器(CRR3CM)。該標記器完成了在各匯聚流之間對剩余帶寬的公平分配，減少了目標速度、往返時間，以及重傳超時因素對帶寬分配的影響。模擬實驗表明，與TSW3CM相比，該算法有效地提高了TCP流之間帶寬分配的公平性。
關鍵詞：區(qū)分服務； 標記器； 目標速度； 往返時間； 重傳超時
中圖分類號：TP393 文獻標志碼：A
文章編號：10013695(2008)09280103
Three color marker algorithm of CIR， RTT and RTO aware
YANG Guanzhonga， TANG Liangb
(a.School of Software， b. School of Computer Communication， Hunan University， Changsha 410082， China)
Abstract:Commited information rate(CIR)，round trip time(RTT) and retransmission timeout(RTO)，can bias bandwidth assurance.Through researching the relation between bandwidth and these factors， this paper proposed a CIR，RTT，RTO aware marker(CRR3CM) based on time sliding window three color marker(TSW3CM)，which could achieve proportional fair sharing of excess bandwidth among aggregates and mitigate the impact of CIR，RTT，RTO for bandwidth assurance. Simulation results indicate that the algorithm can improve the performance of fairness bandwidth allocation between different TCP flows.
Key words：differentiated service; marker; CIR; RTT; RTO
0 引言
隨著VoIP、VOD、IP電話等多媒體應用發(fā)展，“盡力而為”服務（best effort）已經不能滿足要求了，于是IETF提出了綜合服務(IntServ)[1]和區(qū)分服務(DiffServ)[2]。由于綜合服務不具備良好的可擴展性，單純的IntServ結構無法在Internet中得到廣泛應用。區(qū)分服務是一種在互聯(lián)網中支持服務質量(QoS)的體系框架，并且它具有良好可擴展性。因此，區(qū)分服務框架已經成為提供多媒體服務首要的方式。
區(qū)分服務通過分類、聚集和PHB的方式來提供有區(qū)別的QoS保證。區(qū)分服務通過在邊界路由器(edge router)將數據包分類，并在包頭標記區(qū)分服務碼點(DSCP)值。在核心路由器(core router)，將具有相同DSCP的包匯集，通過對不同DSCP定義不同的調度轉發(fā)行為(PHB)，實現了不同業(yè)務的區(qū)分服務。目前區(qū)分服務支持三種轉發(fā)業(yè)務類，分別為盡力而為、加速型轉發(fā)(expedited forwarding)[3]、確保型轉發(fā)(assured forwarding)[4]。本文研究用的是確保型轉發(fā)。
目前，一種基于時間滑動窗口的三色標記算法(TSW3CM)[5]已經成為區(qū)分服務中常用的標記算法。該算法通過估計流的到達平均速率，根據CTR和PTR以及平均速率來計算標記概率，然后包以一定的概率被標記為綠色、黃色和紅色。但是有人指出，該算法存在著對網絡剩余帶寬分配的不公平性[6]。N.Seddigh等人[7]指出DiffServ網絡中影響TCP流帶寬共享公平性的因素有：a）TCP業(yè)務流的RTT大小。RTT較小時，TCP流往往能夠獲得超過其目標速率的帶寬。隨著RTT的逐漸增大，數據流達到其目標速率的難度也隨之增大，因為RTT較小時，發(fā)生丟包后其擁塞窗口能在更短時間內恢復到原來的水平。b）目標速率的大小。目標速率較大的匯聚流的擁塞窗口也較大，發(fā)生丟包后其擁塞窗口需要更多的時間來恢復，難以獲得其目標速率。c）匯聚流中單流數目的多少。匯聚流中單流數量影響平均窗口的大小，平均窗口越小，在發(fā)生擁塞后恢復到原窗口大小所需要的時間越短。因此單流數量越多，就越容易獲得帶寬保證。d）數據包大小尺寸。數據包的尺寸越大，就越容易獲得較大的帶寬分配。e）是否存在非響應流。由于非響應流對擁塞沒有反映，可以搶占TCP流的帶寬，并有可能導致網絡擁塞崩潰，導致TCP流難以獲得其目標速率。
針對TCP流帶寬共享的不公平性問題，一些文獻提出了不同的解決方案。文獻[8]提出了一個基于RTT和目標速率感知的流量調節(jié)器。這些調節(jié)器包括了RTT感知的流量調節(jié)器(RATC)、基于目標速率感知兩種丟棄級別的調節(jié)器(TATC2D)、基于目標速率感知三種丟棄級別的調節(jié)器(TATC3D)。這些調節(jié)器的基本原理是根據帶寬與RTT和目標速率的關系調節(jié)包的丟棄概率，但是模型沒有同時考慮RTT以及目標速率的影響。文獻[9]認為RATC算法過度地保護長的RTT流，占用了大部分剩余帶寬，導致短RTT流超時而達不到預約帶寬，于是設計了一種基于RTT和重傳超時(RTO)感知的調節(jié)器，同時考慮了RTT、RTO對TCP流的影響。文獻[10]提出一種基于目標速率和RTT感知的三色標記器(tmTRA3CM)，綜合考慮了目標速率和RTT對TCP流的影響。總的來說它們都沒有同時考慮CIR 、RTT、RTO對TCP流的影響。
1 CIR、RTT、RTO感知的三色標記器
1.1 CIR、RTT、RTO與帶寬共享的關系
隨著網絡的不斷發(fā)展，大量異質流的存在導致這些影響公平性的因素始終存在。研究公平性算法的目標就是最大程度地減少這些因素對流之間公平性的影響，在保證匯聚流競爭網絡資源時獲得的服務與它的目標速率成比例的同時，還應該考慮RTT、RTO的影響。因此研究這些因素與帶寬共享的關系顯得非常重要。
文獻[11]提出穩(wěn)態(tài)TCP行為模型式(1)，認為帶寬與RTT成反比。
BW ∝ MSS/（RTTp）(1)
其中：MSS表示最大包大小；p是包丟棄概率。
文獻[8]對式(1)進行了推導，最后得出結論。如果兩個流具有不同的RTTs，那么它們之間的丟包率與RTT關系如下：
假設包被標記為OUT的概率的比率與在核心路由器被丟棄的概率成比例的話，根據式(2)得出
其中：Pout，1分別表示流1和2被標記為out包的概率。式(3)可以推廣到一般的情況。
是最小RTT的流被標記為out包的概率。
通過改變標記不同顏色的包的概率可以改變流帶寬的分布，于是文獻[8]提出了流i標記為out包的概率與目標速率的關系如下：
其中：CIRi表示流i的目標速率；CIRmin表示網絡中所有流中最小的目標速率；q表示最小CIR的流被標記為out包的概率。
文獻[9]提出流i被標記為out包的概率與RTO的關系為
其中：minRTO是網絡流中最小的RTO值；Toi是流i的RTO值。
結合式(4)~(6)可以得到被標記為out包的概率與CIR、RTT、RTO的關系如下：
CIR越大，被標記為out包的概率越小，占用的帶寬也就越大。同樣RTT越大，被標記為out包的概率也越小，占用帶寬也越大。若大RTT流長期占用大量帶寬，那么會造成小CIR流丟包超時。通過RTO參數的調節(jié)又可以降低小RTT流包被標記為out包的概率。這些參數相互調節(jié)包被標記為out的概率，從而達到共享帶寬的公平性。
1.2 CRR標記方案
區(qū)分服務網絡入口節(jié)點的主要功能是業(yè)務流定型。入口節(jié)點的結構如圖1所示，它主要包括分類器、計量器、標記器、整形器。分類器根據事先約定好的類別，將數據流傳送給標記器或者計量器。計量器檢查數據流是否符合流規(guī)格(profile)，如果符合，則將數據流傳給整形器；如果不符合，則傳給標記器。標記器為分組設置恰當的DSCP值。本文對入口節(jié)點的結構作了如下修改，加入了一個邊界信息交換器，它是標記器與其他入口節(jié)點的標記器比較并獲取最小CIR、RTT、RTO的橋梁。其主要功能包括信息存儲和邊界信息交換。標記器獲取每個流RTT、RTO、CIR的值，將這些值傳給邊界信息交換器，邊界信息交換器先算出此入口路由器所有經過的流的最小RTT、RTO、CIR的值；然后與其他入口路由器交換這些信息，獲取這個區(qū)分服務網絡域的最小RTT、RTO、CIR的值；最后存儲在信息存儲器中，標記器再從信息存儲器中獲取這些信息，根據標記算法求出經過此入口路由器的每個流中的每個包標記為out包的概率。
13 RTT、RTO參數的獲取
TCP是通過定時器和相應算法在發(fā)送端計算出RTT、RTO參數的，那么怎么在入口路由器上獲取這些參數呢？文獻[9]提出通過在邊界路由器上模擬發(fā)送端，檢測流的序列號以及返回的ACK來計算RTT以及RTO的值。但是這種方法測得的結果不準確，增加了邊界路由器的負擔，而且十分耗資源。本文提出一種新的方法來獲取發(fā)送端的RTT以及RTO的值。通過研究TCP，對TCP發(fā)包算法以及TCP包頭作如下改動。將TCP包頭中預留字段中加入last_rtt、last_rto信息，在TCP發(fā)包時將發(fā)送端最近測得的RTT、RTO的值分別寫入TCP包頭中l(wèi)ast_rtt和last_rto；然后可以在邊界路由器獲取TCP包頭的值。此方法獲取的RTT、RTO的值更準確，并且不會增加邊界路由器的負擔。
14 邊界信息交換算法
下面詳細介紹邊界信息交換器。邊界信息交換器由信息存儲器和邊界信息交換組成。信息存儲器主要是存儲區(qū)分服務網絡域最小的CIR、RTT、RTO信息。其結構體如下：
struct Info_min {
int rtt_min;//最小往返時間
double rto_min; //最小RTO
double ctr_min; //最小目標速率
Info_min() //構造函數初始化
{
rtt_min=0;
rto_min=0;
ctr_min = 0; }
}
交換算法主要包括比較并求出經過該入口節(jié)點所有流的最小的RTT、RTO、CIR，以及控制與其他邊界路由器的信息交換頻率。
在進行算法描述之前，先定義三個變量，如表1所示。
邊界信息交換算法描述如下：
a)初始化：infomin，oldInfomin；
b)入口節(jié)點檢測到流經過時，獲取其RTT、RTO、CIR信息，存于變量newRTT、newRTO、newCIR；
c）保存調整前的存儲器信息oldInfomin = infomin；
d）如果infomin中所有值為0，表明該路由器有第一個流經過，轉到e），否則轉到f）；
e）infomin->rtt_min =newRTT
infomin->rto_min=newRTO
infomin->ctr_min=newCIR
f）求出最小的RTT、RTO、CIR的值:
infomin->rtt_min=min(infomin->rtt_min，newRTT)
Infomin->rto_min=min(infomin->rto_min，newRTO)
infomin->ctr_min=min(infomin->ctr_min，newCIR)
g）比較infomin和oldInfomin的值，如果有變化，則與其他邊界路由器交換存儲信息；
h）如果收到其他邊界路由發(fā)過來的edgeInfomin，則按式（8）求出最小的RTT、RTO、CIR的值
Infomin= min(infomin，edgeInfomin) (8)
具體標記算法如下：
For each packet arrival
avg_rate = estimated avg sending rate of traffic stream
CTR = commited target rate
PTR = peak target rate
if(avg_rate<=CTR)
將包標記為綠色；
else
計算：P1=CTR/avg_rate
P0=(1-ap)(1-P1)
P2=ap(1-P1)
以概率P1將包標記為綠色；以概率P0將包標記為黃色；以概率P2將包標記為紅色。
2 模擬實驗與分析
本節(jié)利用網絡模擬器NS2[12]比較采用CRR3CM與TSW3CM的性能。
2.1 實驗環(huán)境及參數設置
實驗用的網絡拓撲圖如圖2所示，它由兩個邊界節(jié)點(E1、E2)和一個核心節(jié)點(core)構成。節(jié)點core與E2之間采用的主動隊列管理算法是RIO，參數設置如表2所示。發(fā)送端(S1～S5)經過邊界節(jié)點E1到接收端d1；發(fā)送端（S6～S10）經過邊界節(jié)點E2到接收端d2。經過邊界節(jié)點E1和E2的聚集流由TCP業(yè)務流組成，分組大小為1 000 Byte， 實驗時間為300 s。式(7)中概率調整參數p取值為1。為了評價實驗結果，用系統(tǒng)吞吐量以及R.Jain提出的公平指數(fairness index，FI)[13]作為性能評價標準。
FI=(∑Ni=1xi)2/(N×∑Ni=1x2i)；0＜FI＜1
其中：xi=匯聚流i所得到的剩余帶寬/匯聚流i的CIR；N為匯聚流的總數量。公平指數越接近1.0，則剩余帶寬在匯聚流中的分配越公平。
2.2 不同目標速率條件下的比較
在該實驗中，筆者對不同目標速率條件下TSW3CM與CRR3CM算法性能進行了比較。匯聚流A1和A2均由五個TCP微流組成。A1的目標速率(CIR)始終為1 Mbps， 峰值速率為CIR+1 Mbps；A2的目標速率由0.5變化為5 Mbps，網絡提供級別從30%變化至120%。RTT的均為20 ms。
實驗結果如圖3所示，隨著目標速率不斷增加，采取TSW3CM算法的TCP流的目標速率越來越難滿足，在CIR=3.5 Mbps，網絡提供級別為80%時不能滿足其目標速率。采用CRR3CM算法，CIR從0.5增加大4 Mbps時，網絡提供級別由30%變化到100%， A1、A2的目標速率都得到滿足；當CIR由4增至5 Mbps時，網絡提供級別由100%變化為120%，A1和A2都遭到恰當的降級服務。
表3的實驗數據表明，在A2的CIR不斷增加的情況下，CRR3CM算法的公平指數明顯要高于TSW3CM。CRR3CM算法提高了對剩余帶寬分配的公平性。
實驗結果證明：在網絡供過于求的情況下，CRR3CM算法能夠保證各TCP流其目標速率的獲取以及剩余帶寬的合理分配；在網絡供不應求的情況下，能保證各TCP流進行恰當的降級服務，提高了TCP流之間的公平性。
23 不同RTT條件下的比較
在該實驗中，筆者對不同RTT條件下TCP流公平性進行了比較。匯聚流A1和A2均由五個單流組成，每個匯聚流目標速率均為2 Mbps，峰值速率為3 Mbps；A1的RTT始終保持20 ms，A2的RTT由10 ms變化為100 ms。
實驗結果如圖4所示。隨著流A2的RTT不斷增大，使用TSW3CM算法的匯聚流A2所占用的帶寬逐漸下降，并且最終達不到其目標速率，而RTT較小的A1隨著A2的RTT不斷增大，獲取的帶寬也逐漸增大。這是由于發(fā)生丟包后小RTT的擁塞窗口能在更短時間內恢復到原來的水平，能夠迅速獲得超過目標速率的帶寬。使用CRR3CM算法的匯聚流A1和A2，由于采用了剩余帶寬的分配與RTT、RTO參數相關的方法，其目標速率都得到了滿足，并且不會像RATC算法[8]那樣長RTT流占用過量帶寬導致短RTT流重傳超時而達不到目標速度。
在公平性方面如表4所示， A1與A2的RTT差距越大，TSW3CM算法的公平性就越低；而CRR3CM算法的公平指數一直穩(wěn)定在0.8以上。實驗數據表明CRR3CM算法提高了公平性。
實驗結果表明在各TCP流不同RTT的情況下，CRR3CM算法保證了目標速率的獲取，并且提高了對剩余帶寬分配的公平性。
3 結束語
在DiffServ確保服務中，本文針對TCP流之間分配額外帶寬時的不公平性問題，通過分析帶寬分配與目標速率、往返時間、重傳超時之間的關系，在TSW3CM的基礎上提出一種新的標記策略，它依據CIR、RTT、RTO三個參數的值來動態(tài)地調節(jié)標記概率。實驗結果表明，在不同的目標速率下和不同往返時間的條件下，該標記器保證了各TCP流目標速率的獲取，并且能夠合理地分配剩余帶寬，大大提高了TCP流之間的公平性。
參考文獻：
［1］BRADEN R， CLARK D， SHENKER S. IETF RFC 1633， Integrated services in the Internet architecture: an overview[S].1994.
[2]BLAKE S， BLACK D， WEISS W，et al. IETF RFC 2475， An architecture for differentiated services[S].1998.
[3]JACOBSON V， NICHOLS K， PODURI K. IETF RFC 2598， An expedited forwarding PHB[S].1999.
[4]HEINANEN J， BAKER F， WEISS W，et al. IETF RFC 2597， Assured forwarding PHB group[S].1999.
[5]FANG W， SEDDIGH N， NANDY B. IETF RFC 2859， A time sliding window three color marker[S]. 2000.
[6]IBANEZ J， NICHOLS K. Preliminary simulation evaluation of an assured service[K].IETF Draft，1998.
[7]SEDDIGH N， NANDY B， PIEDA P. Bandwidth assurance issues for TCP flows in a differentiated services network[C]//Proc of GLOBECOM’99.New York:IEEE，1999:17921798.
[8]NANDY B， SEDDIGH N， PIEDA P，et al. Intelligent traffic conditioners for assured forwarding based differentiated services networks[C]//Proc of High Performance Networking. Paris:IFIP，2000.
[9]HABIB A， BHARGAVA B， FAHMY S. A round trip time and timeout aware traffic conditioner for differentiated services networks[C]//Proc ofICC’ 02. New York:IEEE，2002:981985.
[10]SANGDOK M O， PKWANGSUE C. A fair bandwidth distribution mechanism in a DiffServ network[J].Computer Communications，2007，30(2):358368.
[11]MATHIS J， SEMKE J， MAHDAVI J，et al. The macroscopic behavior of the TCP congestion avoidance algorithm[J].ACM SIGCOMM Computer Communication Review，1997，27(3):6782.
[12]University of California at Berkeley. The network simulator 2[EB/OL].(1995).http：//www.isi.edu/nsnam/ns/.
[13]JAIN R. The art of computer systems performance analysis:techniques for experimental design， measurement， simulation， and modeling[M]. New York: Wiley， 1991.
