ＣＩＲ、ＲＴＴ和ＲＴＯ感知的三色標(biāo)記算法

摘 要：往返時(shí)間(RTT)、目標(biāo)速度（CIR）以及重傳超時(shí)(RTO)等因素導(dǎo)致了帶寬分配的不均勻。通過研究帶寬與這些因素的關(guān)系，在時(shí)間滑動(dòng)窗口三色標(biāo)記器（TSW3CM）的基礎(chǔ)上，提出一種CIR、RTT、RTO感知的標(biāo)記器(CRR3CM)。該標(biāo)記器完成了在各匯聚流之間對(duì)剩余帶寬的公平分配，減少了目標(biāo)速度、往返時(shí)間，以及重傳超時(shí)因素對(duì)帶寬分配的影響。模擬實(shí)驗(yàn)表明，與TSW3CM相比，該算法有效地提高了TCP流之間帶寬分配的公平性。

關(guān)鍵詞：區(qū)分服務(wù)； 標(biāo)記器； 目標(biāo)速度； 往返時(shí)間； 重傳超時(shí)

中圖分類號(hào)：TP393 文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：10013695(2008)09280103

Three color marker algorithm of CIR， RTT and RTO aware

YANG Guanzhonga， TANG Liangb

(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電話等多媒體應(yīng)用發(fā)展，“盡力而為”服務(wù)（best effort）已經(jīng)不能滿足要求了，于是IETF提出了綜合服務(wù)(IntServ)^[1]和區(qū)分服務(wù)(DiffServ)^[2]。由于綜合服務(wù)不具備良好的可擴(kuò)展性，單純的IntServ結(jié)構(gòu)無法在Internet中得到廣泛應(yīng)用。區(qū)分服務(wù)是一種在互聯(lián)網(wǎng)中支持服務(wù)質(zhì)量(QoS)的體系框架，并且它具有良好可擴(kuò)展性。因此，區(qū)分服務(wù)框架已經(jīng)成為提供多媒體服務(wù)首要的方式。

區(qū)分服務(wù)通過分類、聚集和PHB的方式來提供有區(qū)別的QoS保證。區(qū)分服務(wù)通過在邊界路由器(edge router)將數(shù)據(jù)包分類，并在包頭標(biāo)記區(qū)分服務(wù)碼點(diǎn)(DSCP)值。在核心路由器(core router)，將具有相同DSCP的包匯集，通過對(duì)不同DSCP定義不同的調(diào)度轉(zhuǎn)發(fā)行為(PHB)，實(shí)現(xiàn)了不同業(yè)務(wù)的區(qū)分服務(wù)。目前區(qū)分服務(wù)支持三種轉(zhuǎn)發(fā)業(yè)務(wù)類，分別為盡力而為、加速型轉(zhuǎn)發(fā)(expedited forwarding)^[3]、確保型轉(zhuǎn)發(fā)(assured forwarding)^[4]。本文研究用的是確保型轉(zhuǎn)發(fā)。

目前，一種基于時(shí)間滑動(dòng)窗口的三色標(biāo)記算法(TSW3CM)^[5]已經(jīng)成為區(qū)分服務(wù)中常用的標(biāo)記算法。該算法通過估計(jì)流的到達(dá)平均速率，根據(jù)CTR和PTR以及平均速率來計(jì)算標(biāo)記概率，然后包以一定的概率被標(biāo)記為綠色、黃色和紅色。但是有人指出，該算法存在著對(duì)網(wǎng)絡(luò)剩余帶寬分配的不公平性^[6]。N.Seddigh等人^[7]指出DiffServ網(wǎng)絡(luò)中影響TCP流帶寬共享公平性的因素有：a）TCP業(yè)務(wù)流的RTT大小。RTT較小時(shí)，TCP流往往能夠獲得超過其目標(biāo)速率的帶寬。隨著RTT的逐漸增大，數(shù)據(jù)流達(dá)到其目標(biāo)速率的難度也隨之增大，因?yàn)镽TT較小時(shí)，發(fā)生丟包后其擁塞窗口能在更短時(shí)間內(nèi)恢復(fù)到原來的水平。b）目標(biāo)速率的大小。目標(biāo)速率較大的匯聚流的擁塞窗口也較大，發(fā)生丟包后其擁塞窗口需要更多的時(shí)間來恢復(fù)，難以獲得其目標(biāo)速率。c）匯聚流中單流數(shù)目的多少。匯聚流中單流數(shù)量影響平均窗口的大小，平均窗口越小，在發(fā)生擁塞后恢復(fù)到原窗口大小所需要的時(shí)間越短。因此單流數(shù)量越多，就越容易獲得帶寬保證。d）數(shù)據(jù)包大小尺寸。數(shù)據(jù)包的尺寸越大，就越容易獲得較大的帶寬分配。e）是否存在非響應(yīng)流。由于非響應(yīng)流對(duì)擁塞沒有反映，可以搶占TCP流的帶寬，并有可能導(dǎo)致網(wǎng)絡(luò)擁塞崩潰，導(dǎo)致TCP流難以獲得其目標(biāo)速率。

針對(duì)TCP流帶寬共享的不公平性問題，一些文獻(xiàn)提出了不同的解決方案。文獻(xiàn)[8]提出了一個(gè)基于RTT和目標(biāo)速率感知的流量調(diào)節(jié)器。這些調(diào)節(jié)器包括了RTT感知的流量調(diào)節(jié)器(RATC)、基于目標(biāo)速率感知兩種丟棄級(jí)別的調(diào)節(jié)器(TATC2D)、基于目標(biāo)速率感知三種丟棄級(jí)別的調(diào)節(jié)器(TATC3D)。這些調(diào)節(jié)器的基本原理是根據(jù)帶寬與RTT和目標(biāo)速率的關(guān)系調(diào)節(jié)包的丟棄概率，但是模型沒有同時(shí)考慮RTT以及目標(biāo)速率的影響。文獻(xiàn)[9]認(rèn)為RATC算法過度地保護(hù)長的RTT流，占用了大部分剩余帶寬，導(dǎo)致短RTT流超時(shí)而達(dá)不到預(yù)約帶寬，于是設(shè)計(jì)了一種基于RTT和重傳超時(shí)(RTO)感知的調(diào)節(jié)器，同時(shí)考慮了RTT、RTO對(duì)TCP流的影響。文獻(xiàn)[10]提出一種基于目標(biāo)速率和RTT感知的三色標(biāo)記器(tmTRA3CM)，綜合考慮了目標(biāo)速率和RTT對(duì)TCP流的影響。總的來說它們都沒有同時(shí)考慮CIR 、RTT、RTO對(duì)TCP流的影響。

1 CIR、RTT、RTO感知的三色標(biāo)記器

1.1 CIR、RTT、RTO與帶寬共享的關(guān)系

隨著網(wǎng)絡(luò)的不斷發(fā)展，大量異質(zhì)流的存在導(dǎo)致這些影響公平性的因素始終存在。研究公平性算法的目標(biāo)就是最大程度地減少這些因素對(duì)流之間公平性的影響，在保證匯聚流競爭網(wǎng)絡(luò)資源時(shí)獲得的服務(wù)與它的目標(biāo)速率成比例的同時(shí)，還應(yīng)該考慮RTT、RTO的影響。因此研究這些因素與帶寬共享的關(guān)系顯得非常重要。

文獻(xiàn)[11]提出穩(wěn)態(tài)TCP行為模型式(1)，認(rèn)為帶寬與RTT成反比。

BW ∝ MSS/（RTTp）(1)

其中：MSS表示最大包大小；p是包丟棄概率。

文獻(xiàn)[8]對(duì)式(1)進(jìn)行了推導(dǎo)，最后得出結(jié)論。如果兩個(gè)流具有不同的RTTs，那么它們之間的丟包率與RTT關(guān)系如下：

假設(shè)包被標(biāo)記為OUT的概率的比率與在核心路由器被丟棄的概率成比例的話，根據(jù)式(2)得出

其中：Pout，1分別表示流1和2被標(biāo)記為out包的概率。式(3)可以推廣到一般的情況。

是最小RTT的流被標(biāo)記為out包的概率。

通過改變標(biāo)記不同顏色的包的概率可以改變流帶寬的分布，于是文獻(xiàn)[8]提出了流i標(biāo)記為out包的概率與目標(biāo)速率的關(guān)系如下：

其中：CIRi表示流i的目標(biāo)速率；CIRmin表示網(wǎng)絡(luò)中所有流中最小的目標(biāo)速率；q表示最小CIR的流被標(biāo)記為out包的概率。

文獻(xiàn)[9]提出流i被標(biāo)記為out包的概率與RTO的關(guān)系為

其中：minRTO是網(wǎng)絡(luò)流中最小的RTO值；Toi是流i的RTO值。

結(jié)合式(4)~(6)可以得到被標(biāo)記為out包的概率與CIR、RTT、RTO的關(guān)系如下：

CIR越大，被標(biāo)記為out包的概率越小，占用的帶寬也就越大。同樣RTT越大，被標(biāo)記為out包的概率也越小，占用帶寬也越大。若大RTT流長期占用大量帶寬，那么會(huì)造成小CIR流丟包超時(shí)。通過RTO參數(shù)的調(diào)節(jié)又可以降低小RTT流包被標(biāo)記為out包的概率。這些參數(shù)相互調(diào)節(jié)包被標(biāo)記為out的概率，從而達(dá)到共享帶寬的公平性。

1.2 CRR標(biāo)記方案

區(qū)分服務(wù)網(wǎng)絡(luò)入口節(jié)點(diǎn)的主要功能是業(yè)務(wù)流定型。入口節(jié)點(diǎn)的結(jié)構(gòu)如圖1所示，它主要包括分類器、計(jì)量器、標(biāo)記器、整形器。分類器根據(jù)事先約定好的類別，將數(shù)據(jù)流傳送給標(biāo)記器或者計(jì)量器。計(jì)量器檢查數(shù)據(jù)流是否符合流規(guī)格(profile)，如果符合，則將數(shù)據(jù)流傳給整形器；如果不符合，則傳給標(biāo)記器。標(biāo)記器為分組設(shè)置恰當(dāng)?shù)腄SCP值。本文對(duì)入口節(jié)點(diǎn)的結(jié)構(gòu)作了如下修改，加入了一個(gè)邊界信息交換器，它是標(biāo)記器與其他入口節(jié)點(diǎn)的標(biāo)記器比較并獲取最小CIR、RTT、RTO的橋梁。其主要功能包括信息存儲(chǔ)和邊界信息交換。標(biāo)記器獲取每個(gè)流RTT、RTO、CIR的值，將這些值傳給邊界信息交換器，邊界信息交換器先算出此入口路由器所有經(jīng)過的流的最小RTT、RTO、CIR的值；然后與其他入口路由器交換這些信息，獲取這個(gè)區(qū)分服務(wù)網(wǎng)絡(luò)域的最小RTT、RTO、CIR的值；最后存儲(chǔ)在信息存儲(chǔ)器中，標(biāo)記器再從信息存儲(chǔ)器中獲取這些信息，根據(jù)標(biāo)記算法求出經(jīng)過此入口路由器的每個(gè)流中的每個(gè)包標(biāo)記為out包的概率。 

13 RTT、RTO參數(shù)的獲取

TCP是通過定時(shí)器和相應(yīng)算法在發(fā)送端計(jì)算出RTT、RTO參數(shù)的，那么怎么在入口路由器上獲取這些參數(shù)呢？文獻(xiàn)[9]提出通過在邊界路由器上模擬發(fā)送端，檢測(cè)流的序列號(hào)以及返回的ACK來計(jì)算RTT以及RTO的值。但是這種方法測(cè)得的結(jié)果不準(zhǔn)確，增加了邊界路由器的負(fù)擔(dān)，而且十分耗資源。本文提出一種新的方法來獲取發(fā)送端的RTT以及RTO的值。通過研究TCP，對(duì)TCP發(fā)包算法以及TCP包頭作如下改動(dòng)。將TCP包頭中預(yù)留字段中加入last_rtt、last_rto信息，在TCP發(fā)包時(shí)將發(fā)送端最近測(cè)得的RTT、RTO的值分別寫入TCP包頭中l(wèi)ast_rtt和last_rto；然后可以在邊界路由器獲取TCP包頭的值。此方法獲取的RTT、RTO的值更準(zhǔn)確，并且不會(huì)增加邊界路由器的負(fù)擔(dān)。

14 邊界信息交換算法

下面詳細(xì)介紹邊界信息交換器。邊界信息交換器由信息存儲(chǔ)器和邊界信息交換組成。信息存儲(chǔ)器主要是存儲(chǔ)區(qū)分服務(wù)網(wǎng)絡(luò)域最小的CIR、RTT、RTO信息。其結(jié)構(gòu)體如下：

struct Info_min {

int rtt_min;//最小往返時(shí)間

double rto_min; //最小RTO

double ctr_min; //最小目標(biāo)速率

Info_min() //構(gòu)造函數(shù)初始化

{

rtt_min=0;

rto_min=0;

ctr_min = 0; }

}

交換算法主要包括比較并求出經(jīng)過該入口節(jié)點(diǎn)所有流的最小的RTT、RTO、CIR，以及控制與其他邊界路由器的信息交換頻率。

在進(jìn)行算法描述之前，先定義三個(gè)變量，如表1所示。

邊界信息交換算法描述如下：

a)初始化：infomin，oldInfomin；

b)入口節(jié)點(diǎn)檢測(cè)到流經(jīng)過時(shí)，獲取其RTT、RTO、CIR信息，存于變量newRTT、newRTO、newCIR；

c）保存調(diào)整前的存儲(chǔ)器信息oldInfomin = infomin；

d）如果infomin中所有值為0，表明該路由器有第一個(gè)流經(jīng)過，轉(zhuǎn)到e），否則轉(zhuǎn)到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的值，如果有變化，則與其他邊界路由器交換存儲(chǔ)信息；

h）如果收到其他邊界路由發(fā)過來的edgeInfomin，則按式（8）求出最小的RTT、RTO、CIR的值

Infomin= min(infomin，edgeInfomin) (8) 

具體標(biāo)記算法如下：

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)

將包標(biāo)記為綠色；

else

計(jì)算：P1=CTR/avg_rate

P0=(1-ap)(1-P1)

P2=ap(1-P1)

以概率P1將包標(biāo)記為綠色；以概率P0將包標(biāo)記為黃色；以概率P2將包標(biāo)記為紅色。

2 模擬實(shí)驗(yàn)與分析

本節(jié)利用網(wǎng)絡(luò)模擬器NS2^[12]比較采用CRR3CM與TSW3CM的性能。

2.1 實(shí)驗(yàn)環(huán)境及參數(shù)設(shè)置

實(shí)驗(yàn)用的網(wǎng)絡(luò)拓?fù)鋱D如圖2所示，它由兩個(gè)邊界節(jié)點(diǎn)(E1、E2)和一個(gè)核心節(jié)點(diǎn)(core)構(gòu)成。節(jié)點(diǎn)core與E2之間采用的主動(dòng)隊(duì)列管理算法是RIO，參數(shù)設(shè)置如表2所示。發(fā)送端(S1～S5)經(jīng)過邊界節(jié)點(diǎn)E1到接收端d1；發(fā)送端（S6～S10）經(jīng)過邊界節(jié)點(diǎn)E2到接收端d2。經(jīng)過邊界節(jié)點(diǎn)E1和E2的聚集流由TCP業(yè)務(wù)流組成，分組大小為1 000 Byte， 實(shí)驗(yàn)時(shí)間為300 s。式(7)中概率調(diào)整參數(shù)p取值為1。為了評(píng)價(jià)實(shí)驗(yàn)結(jié)果，用系統(tǒng)吞吐量以及R.Jain提出的公平指數(shù)(fairness index，F(xiàn)I)^[13]作為性能評(píng)價(jià)標(biāo)準(zhǔn)。

FI=(∑Ni=1xi)2/(N×∑Ni=1x2i)；0＜FI＜1

其中：xi=匯聚流i所得到的剩余帶寬/匯聚流i的CIR；N為匯聚流的總數(shù)量。公平指數(shù)越接近1.0，則剩余帶寬在匯聚流中的分配越公平。

2.2 不同目標(biāo)速率條件下的比較

在該實(shí)驗(yàn)中，筆者對(duì)不同目標(biāo)速率條件下TSW3CM與CRR3CM算法性能進(jìn)行了比較。匯聚流A1和A2均由五個(gè)TCP微流組成。A1的目標(biāo)速率(CIR)始終為1 Mbps， 峰值速率為CIR+1 Mbps；A2的目標(biāo)速率由0.5變化為5 Mbps，網(wǎng)絡(luò)提供級(jí)別從30%變化至120%。RTT的均為20 ms。 

實(shí)驗(yàn)結(jié)果如圖3所示，隨著目標(biāo)速率不斷增加，采取TSW3CM算法的TCP流的目標(biāo)速率越來越難滿足，在CIR=3.5 Mbps，網(wǎng)絡(luò)提供級(jí)別為80%時(shí)不能滿足其目標(biāo)速率。采用CRR3CM算法，CIR從0.5增加大4 Mbps時(shí)，網(wǎng)絡(luò)提供級(jí)別由30%變化到100%， A1、A2的目標(biāo)速率都得到滿足；當(dāng)CIR由4增至5 Mbps時(shí)，網(wǎng)絡(luò)提供級(jí)別由100%變化為120%，A1和A2都遭到恰當(dāng)?shù)慕导?jí)服務(wù)。

表3的實(shí)驗(yàn)數(shù)據(jù)表明，在A2的CIR不斷增加的情況下，CRR3CM算法的公平指數(shù)明顯要高于TSW3CM。CRR3CM算法提高了對(duì)剩余帶寬分配的公平性。

實(shí)驗(yàn)結(jié)果證明：在網(wǎng)絡(luò)供過于求的情況下，CRR3CM算法能夠保證各TCP流其目標(biāo)速率的獲取以及剩余帶寬的合理分配；在網(wǎng)絡(luò)供不應(yīng)求的情況下，能保證各TCP流進(jìn)行恰當(dāng)?shù)慕导?jí)服務(wù)，提高了TCP流之間的公平性。

23 不同RTT條件下的比較

在該實(shí)驗(yàn)中，筆者對(duì)不同RTT條件下TCP流公平性進(jìn)行了比較。匯聚流A1和A2均由五個(gè)單流組成，每個(gè)匯聚流目標(biāo)速率均為2 Mbps，峰值速率為3 Mbps；A1的RTT始終保持20 ms，A2的RTT由10 ms變化為100 ms。 

實(shí)驗(yàn)結(jié)果如圖4所示。隨著流A2的RTT不斷增大，使用TSW3CM算法的匯聚流A2所占用的帶寬逐漸下降，并且最終達(dá)不到其目標(biāo)速率，而RTT較小的A1隨著A2的RTT不斷增大，獲取的帶寬也逐漸增大。這是由于發(fā)生丟包后小RTT的擁塞窗口能在更短時(shí)間內(nèi)恢復(fù)到原來的水平，能夠迅速獲得超過目標(biāo)速率的帶寬。使用CRR3CM算法的匯聚流A1和A2，由于采用了剩余帶寬的分配與RTT、RTO參數(shù)相關(guān)的方法，其目標(biāo)速率都得到了滿足，并且不會(huì)像RATC算法^[8]那樣長RTT流占用過量帶寬導(dǎo)致短RTT流重傳超時(shí)而達(dá)不到目標(biāo)速度。

在公平性方面如表4所示， A1與A2的RTT差距越大，TSW3CM算法的公平性就越低；而CRR3CM算法的公平指數(shù)一直穩(wěn)定在0.8以上。實(shí)驗(yàn)數(shù)據(jù)表明CRR3CM算法提高了公平性。

實(shí)驗(yàn)結(jié)果表明在各TCP流不同RTT的情況下，CRR3CM算法保證了目標(biāo)速率的獲取，并且提高了對(duì)剩余帶寬分配的公平性。

3 結(jié)束語

在DiffServ確保服務(wù)中，本文針對(duì)TCP流之間分配額外帶寬時(shí)的不公平性問題，通過分析帶寬分配與目標(biāo)速率、往返時(shí)間、重傳超時(shí)之間的關(guān)系，在TSW3CM的基礎(chǔ)上提出一種新的標(biāo)記策略，它依據(jù)CIR、RTT、RTO三個(gè)參數(shù)的值來動(dòng)態(tài)地調(diào)節(jié)標(biāo)記概率。實(shí)驗(yàn)結(jié)果表明，在不同的目標(biāo)速率下和不同往返時(shí)間的條件下，該標(biāo)記器保證了各TCP流目標(biāo)速率的獲取，并且能夠合理地分配剩余帶寬，大大提高了TCP流之間的公平性。

參考文獻(xiàn)：

［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 sliding 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:17921798.

[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 timeout aware traffic conditioner for differentiated services networks[C]//Proc ofICC’ 02. New York:IEEE，2002:981985.

[10]SANGDOK M O， PKWANGSUE C. A fair bandwidth distribution mechanism in a DiffServ network[J].Computer Communications，2007，30(2):358368.

[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):6782.

[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.