一種自適應的基于時延的擁塞控制機制

摘 要:針對早期概率響應TCP(PERT)在實際網絡中與基于丟包的協議(如TCP)共存時存在帶寬共享公平性方面處于弱勢的問題，提出一種改進的PERT協議(modified PERT， MPERT)。該協議通過動態地調整擁塞窗口增加因子和縮減因子的方法，解決了這種基于時延的端系統擁塞控制機制的帶寬公平性問題，增強其對網絡環境的自適應性。另外，針對未來核心網絡將向高速化發展的趨勢，對如何有效地將新機制擴展部署于高速網絡進行了探索，以期改善MPERT協議在高速網絡下的傳輸性能。

關鍵詞:基于時延的協議; 基于丟包的協議; 帶寬共享公平性

中圖分類號:TP394文獻標志碼:A

文章編號:1001-3695(2010)06-2215-04

doi:10.3969/j.issn.1001-3695.2010.06.062

Adaptive delaybased congestion control mechanism

WU Yezhou， XING Wei， LU Dongming

(College of Computer Science Technology， Zhejiang University， Hangzhou 310027， China)

Abstract:In order to solve the problem of PERT such as unable to compete fair bandwidth share with a lossbased protocol， e.g. TCP， in the actual network， this paper proposed a kind of modified PERT， called MPERT. Adjusting its congestion window increased factor and decreased factor dynamically， it solved the bandwidth share fairness problem of this kind of delaybased endhost congestion control mechanism and made itself adaptive to varying network environment. Moreover， considering the tendency of the core network would become higher speed， researched and proposed the solution to the problem about how to develop the new mechanism in highspeed network， in order to improve the performance of MPERT in this kink of network.

Key words:delaybased protocol; lossbased protocol; bandwidth share fairness

多媒體應用具有低時延、低丟包的要求，而目前的應用主要運用UDP或TCP作為傳輸層協議。UDP不提供擁塞控制，運用UDP的應用需自己解決擁塞控制問題;而TCP的按序可靠傳輸特性對多媒體應用來說也不是必需的。因此，通過設計一種新的擁塞控制方法，促進網絡向能夠承載更高質量的多媒體應用和更高鏈路帶寬的方向發展，成為近些年的研究熱點。

傳統意義上，擁塞控制協議通過兩種不同的方法來獲取網絡中的擁塞反饋信息:a)通過檢測數據包的丟失或中間路由器對數據包打的“標記”;b)在端節點測量一些網絡特性(如傳輸時延)。然而，由于時延測算的準確性和其他不確定因素，使基于時延的擁塞檢測方法存在可靠性問題[1]。Bhandarkar等人[2]針對上述問題，提出了一種新的基于時延的擁塞控制協議——早期概率響應TCP(probabilistic early response TCP，PERT)。PERT改進了時延測算和預測擁塞的過程，即通過對測算的時延采取以相應的概率進行擁塞響應，解決了存在的時延測算不確定性。PERT在發送端節點模擬主動隊列管理(AQM)算法，當測算的時延值越大就以更高的概率響應，減速慢行，以避免發生可能的擁塞事件。

雖然PERT被證明能夠有效地達到其目的，但若要在未來的實際部署發揮功效，仍存在兩個問題:a)基于時延的協議在實際部署過程中最大的問題是如何與傳統TCP進行帶寬的競爭。如今的互聯網環境中，仍然存在著大量承載于傳統TCP之上的應用。傳統TCP作為一種基于丟包的協議，在發現有數據包丟失之前，一直維持增加擁塞窗口的大小。而另一方面，基于時延的擁塞控制協議通過提前響應擁塞，實質上為傳統TCP流“騰”出了帶寬空間。盡管大多數的基于時延的協議在同質協議的網絡環境下能夠表現出了好的特性，但若要將其部署于真實的網絡中，在與傳統TCP共存的實際場景，如何保證基于時延的協議能夠獲得公平的帶寬，這在新協議的部署過渡時期是必須要面對的問題。b)當基于時延的擁塞控制協議的單條傳輸流存在于高帶寬大時延的鏈路中，是否能夠高效地利用充裕的帶寬資源。這類話題已成為學術界最新的研究熱點，并有眾多學者針對高速網絡的特性提出了新的傳輸協議[3~5]。

本文主要針對上述問題，對原PERT進行改進，期望改進后的PERT可以自適應地運行于同質或異質協議的網絡環境，獲得公平帶寬，并能夠在高速網絡中高效利用帶寬資源。本文簡要介紹PERT協議的原理和特性，對PERT協議流的穩態吞吐率進行了分析，提出PERT的改進型方案——MPERT。

1 PERT的概述

PERT[2]利用平滑處理后的RTT(round trip time)測算值來表示流傳輸路徑上的擁塞程度。與其他基于時延的協議類似，PERT假設如果觀察到的時延變大，傳輸路徑上就開始出現擁塞。然而，PERT設計者意識到，由于測算時的噪聲和突發流的影響，擁塞的預測具有不確定性。為了減小這種不良效應，PERT針對測算的時延采用了一種概率響應的方式。即當感知到的隊列長度處于較低水平時，對可能發生的擁塞作出提前響應的行為概率較小;當感知到的隊列長度增加時，對可能發生的擁塞作出提前響應的行為概率也變大了。PERT以此來減少在擁塞預測時可能發生假報警(1 positive)現象[1]，該現象的產生會降低網絡的鏈路利用率。

PERT在端系統模仿AQM的RED算法[6]的機理。PERT的提前概率響應函數的設計類似于RED算法。如圖1所示，縱軸為響應概率，橫軸為擁塞檢測信號值(srttrttmin)。其中:rttmin為當網絡不存在排隊時延時的RTT值;srtt為平滑處理后的RTT值。

srtt=k×rtt-(1-k)×srtt(1)

與RED類似，它定義了最大閾值Tmax、最小閾值Tmin和最大響應概率Rmax。當(srttrttmin)的值，即排隊時延低于最小閾值時，響應概率為0;當排隊時延值超過最小閾值時，縮減窗口的響應概率線性增加，直到排隊時延的值到達最大閾值時，響應概率為Pmax。當排隊時延值處于Tmax和兩倍Tmax之間，響應概率的取值在Pmax與1之間變動。當排隊時延值超出兩倍Tmax，響應概率的取值為1。參見圖1，上述擁塞預測檢測過程可以表述如下:

if((srttrttmin)

返回1; //預測無擁塞

} else if ((srttrttmin)

以概率(srttrttmin)-TminTmax-Tmin×Pmax返回true; //預測擁塞

} else if ((srttrttmin)<2Tmax) {

以概率(srttrttmin)-TmaxTmax×(1-Pmax)+Pmax返回true;

} else {

返回true;

}

一旦(srttrttmin)高于預設的閾值時，每一個ACK包的到達都意味著一次網絡正處于擁塞狀態的警報，直到隊列長度降低于最小閾值為止。在這種情況下，需要注意的是，數據流沒有必要對每一個擁塞指示都作出響應，因為一次端系統擁塞響應的效果需要通過至少一個RTT間隔后才能反映出來。所以，端系統的提前擁塞響應行為被限制為在一個RTT間隔內至多只進行一次。

2 MPERT——對PERT的改進

2.1 吞吐率分析

為了解決PERT相對TCP的帶寬競爭力缺陷，需要對PERT流的穩態吞吐率進行分析。對于一條基于窗口的擁塞控制算法的傳輸流，在擁塞避免階段，它每收到一個ACK幀，發送端的擁塞窗口調整為W=W+a/W;當進行擁塞響應時，發送端的擁塞窗口縮減為W=(1-β)×W。其中:W為擁塞窗口大小;α和β分別為窗口調節的增加因子和縮減因子。根據上述的擁塞窗口調節機制，流處于穩定狀態時的吞吐率可以表示為1RTTαβ×p[7]。其中p為穩態丟包率。PERT對擁塞的響應可以分為兩類，即PERT以p′的概率提前響應擁塞，或在概率為p的擁塞丟包事件發生時縮減擁塞窗口。在PERT與TCP競爭時，TCP只會觀察到擁塞丟包率。在多流相互競爭帶寬時，各流觀察到的擁塞丟包率可能是不相同的，但為了簡化分析，假設PERT流和TCP流擁有相同的擁塞丟包概率。

2.2 α參數的調節

因為PERT流可能在以下兩種情況下進行擁塞響應:a)在擁塞發生前就進行了提前的擁塞響應;b)如TCP一樣在真正擁塞(丟包)發生時才進行擁塞響應。因此，上文提及的，由文獻[7]得出的穩態吞吐率公式中的穩態丟包率對PERT而言，意味著包括提前擁塞響應概率p′和丟包響應概率p，即PERT流的吞吐率受到這兩個概率的影響。PERT的聯合擁塞響應概率應該表示為

1-(1-p)×(1-p′)=p+p′-p×p′(2)

如果MPERT在與TCP競爭時要獲得公平的帶寬，那么兩種協議流的穩態吞吐率應該保持相等，可以得出如下等式:

βMPERT×(p+p′-p×p′)/αMPERT=βTCP×p/αTCP(3)

因為已知αTCP=1，由式(3)可得到:

αMPERT=βMPERT×(p+p′-p×p′)/(βTCP×p)(4)

若設定βMPERT=βTCP，且p′是一個接近于0的正整數，可忽略不計，則由式(4)得到:

αMPERT=1+p′/p-p′≈1+p′/p(5)

通過上述的穩態流吞吐率分析可知，在與TCP共存時，MPERT必須在增加擁塞窗口時表現得更為激進，以扳回其在提前響應擁塞時所造成的弱勢，從而與TCP公平分享鏈路帶寬。因此，當MPERT在與TCP競爭帶寬時，MPERT的窗口調整表示為

W=W+αMPERT/W，αMPERT=1+p′/p

2.3 β參數的調節

假設提前擁塞響應成功，其效果是瓶頸鏈路的隊列長度應該保持在一個較低的水位。因此，對于提前擁塞響應，不一定需要將窗口縮減因子設為0.5。可以將擁塞窗口的縮減因子設置為一個動態更新的變量:

βMPERT=qc/(qc+qmax)(6)

其中:qc為響應擁塞時測得并換算的排隊時延值;qmax為到目前為止觀察到的最大排隊時延值。可以發現，當qc=qmax時，縮減因子βMPERT即為0.5。因為此時網絡的排隊時延很大，MPERT認為此時的擁塞加劇，提前擁塞響應需要更加激進，即大幅度地縮減擁塞窗口，減輕網絡負載，以避免后續可能的丟包。因此，改進后，窗口縮減因子βMPERT是根據網絡排隊時延的大小在0~0.5動態取值的。

2.4 MPERT的運行模式

在本文中還有一個重要問題需要考慮，即如何判定MPERT何時是運行在一個同構環境(當所有的流都是類PERT流)還是異構環境(存在TCP競爭流)。雖然，激進的窗口增加使MPERT在混合的環境中可以與TCP競爭公平的帶寬，但是在同質環境中它會增加丟包率和隊列長度。可通過利用觀察的排隊時延來輔助MPERT運行模式的選擇。

當觀察的排隊時延變長時，MPERT假設它正在與一種基于丟包的協議在競爭，如TCP流會將隊列長度推高。因此，MPERT需要在增加窗口的行為上變得更激進，以補償提前擁塞響應的帶寬損失。使用0.5×qmax作為判斷是否有TCP流在與MPERT流競爭帶寬的閾值。類似地，當排隊時延持續地位于最小閾值之下，則可以認為MPERT流運行在一個帶寬充裕的網絡環境中。在這兩種狀況下，MPERT將它的窗口增加因子α從默認的1增加到一個更大的值。當排隊時延變長時，α的增加是為了與基于丟包的協議流競爭帶寬(于是增加到1+p′/p);而當排隊時延很小時，α增加的目的是為了快速地利用充裕的帶寬。

MPERT的運行可以處于三種不同的模式:a)高速模式。當觀察的排隊時延小于最小閾值C1，表示鏈路帶寬未被充分利用，可線性地增加α，直到α值等于閾值C2，這樣可以在擁塞避免階段，更快地增加窗口。b)穩定模式。當排隊時延大于最小閾值且小于觀測到的最大排隊時延的一半，表示可用帶寬被很好地利用了，且排隊時延相對較短，可認為此時的網絡環境中運行的都是與MPERT類似的流，α可以減小直到為1。c)競爭模式。當測得的排隊時延大于最大排隊時延的一半，就表示環境中有一些異質協議流存在，它們采取基于丟包的擁塞響應行為，可增加α，直到其值等于αMPERT的目標值1+p′/p。α值的調節過程將持續一段時間T，T值應該大于一個RTT，使α值可以平滑變化，有益于隊列緩沖區狀態的平滑過渡。

2.5 MPERT算法描述

本節描述PERT和MPERT算法的運行過程。在PERT算法描述中，以方框標注出了MPERT針對PERT算法需要添加或改進步驟的地方。算法描述中:rtt表示根據每個ACK包獲得的實時RTT值，srtt是當前平滑處理的RTT估計值。

1)PERT算法描述 PERT擁塞控制包括慢啟動和擁塞避免階段，其主要對擁塞避免階段的算法進行了改進。在擁塞避免階段，PERT算法可描述如下:

當每收到一個ACK包:

if (該ACK包是新到達的){

獲得跟該ACK包相關的rtt;

根據式(1)更新srtt;//位置1

if (擁塞預測檢測過程認為擁塞發生){

β=0.5;//位置2

cwnd=cwnd×(1-β);//以β因子縮減擁塞窗口

} else { //擁塞預測檢測過程認為網絡不會擁塞

α=1;//位置3

cwnd=cwnd+α/cwnd;//以α因子增加擁塞窗口

}

} else { //該ACK包是重復的第三個ACK包

β= 0.5; //位置4

cwnd=cwnd×(1-β);//以β因子縮減擁塞窗口

}

2)MPERT算法描述 MPERT算法保留了PERT算法的框架結構，并對原算法中方框標注的部分進行了改進。

位置1處添加:

更新當前排隊時延值qc;

更新最大排隊時延值qmax;

位置2處改為:

β=qc/(qc+qmax)

更新提前擁塞響應概率p′;//為位置3中的α更新作準備

位置3處改為:

//根據流所處的三個不同運行模式，更新α

if (距上次α更新時隔 > T) {

if (qc

α=min(α+0.5，C2 );

} else if (qc>0.5 qmax) { //競爭模式

target=1+p′/p;

α=min(min(α+ 0.1， target)，C2);

} else { //穩定模式

α=max(0.9α， 1);

} }

位置4處改為:

β=qc/(qc+qmax)

更新丟包響應概率p;//為位置3中的α更新作準備

3 實驗分析

本文在NS2[8]網絡仿真平臺上進行模擬實驗，以檢驗MPERT的性能。本章由四個實驗組成:前三個實驗分析當有SACK協議流(一種較新的TCP版本)存在網絡中，原PERT流和MPERT流的性能比較;最后一個實驗則是分析在高速網絡中只存在單協議流時，LTCP流[3]、PERT流和MPERT流的性能比較。除非特別說明，瓶頸鏈路的緩沖大小設為帶寬延時乘積，瓶頸鏈路和端節點鏈路的帶寬都保持150 Mbps，端到端的RTT，即rttmin設定為60 ms;圖1中參數Tmin、Tmax、Pmax分別使用5 ms、10 ms和0.05;式(1)中的平滑系數k為0.01;排隊時延的最小閾值C1設為5 ms，α值的閾值C2設為32，α值的調節周期T設為5RTT。模擬時間為200 s，取位于50~150 s穩定時期內的實驗數據作為樣本。當多流共享一條鏈路時，它們的啟動時間隨機分布于(0，10)s，以防同步(synchronization)現象的發生。所有的模擬均遵循圖2的網絡拓撲。

3.1 流混合比例的變化

在本實驗中，流的總數設定為100，通過改變網絡中同時共存的不同協議流的比例，對比原PERT流和MPERT流在相同背景下相對SACK流的帶寬競爭力和丟包率。

將MPERT/PERT流在總流數中的占比調整為5%~95%，來觀察MPERT/PERT流相對SACK流的丟包率和與SACK共存時的帶寬競爭能力。從圖3顯示，PERT流對SACK流的相對丟包率總是保持在“1”以下，表明PERT在混合協議環境中始終具有更低的丟包率，而MPERT也繼承了PERT低丟包率的優點。另外，MPERT流的帶寬占用率始終隨著MPERT流比例的增加而增加，并且十分接近預期的(即公平的)帶寬占有率。圖3也驗證了PERT流由于自身設計原理的限制，提前擁塞響應，把帶寬讓給了SACK流，不能獲得公平的帶寬。

3.2 在50-50混合比例下，流總數的變化

在本實驗中，流總數的變化為20~500，設定在不同協議流的數量各占總流數一半的情況下，分析網絡中總流數變化時，原PERT流和MPERT流對網絡有什么不同的影響。圖4總結了實驗結果。如筆者預期的，不論是MPERT/SACK混合的情況還是PERT/SACK混合的情況，網絡的隊列長度和總丟包率都隨著流總數的增加而增加。筆者還觀察到，MPERT流的帶寬占用率在流總數較少時表現得比較低，而當流總數增大時，它的值會增大并趨向于50%。這是因為在可用帶寬還很充裕或隊列長度處于較低水平時，MPERT并不會總是運行在競爭模式(與SACK競爭)。Jain公平性指數[9]反映協議流間的公平性，取值為0～1，當取值為1時，協議流間達到最佳公平性。發現MPERT的Jain公平性指數的變化曲線與其流的帶寬占用率的變化曲線表現出類似的形態。由圖4中可以清楚發現，MPERT流在帶寬競爭力和Jain公平性指數方面相對PERT流都有明顯改善。

3.3 在50-50混合比例下，瓶頸鏈路緩沖大小的變化

在本實驗中，流總數仍設定為100，其中50條MPERT/PERT流，50條SACK流，瓶頸鏈路的緩沖大小變化范圍為1/4到4倍的帶寬時延乘積(簡稱BDP)，分析當瓶頸鏈路緩沖區大小變化時，原PERT流和MPERT流的不同表現。圖5總結了MPERT/PERT相對SACK的丟包率和帶寬占用率。

可以觀察到，MPERT的帶寬占用率在瓶頸鏈路的緩沖區大小很小時，優于SACK;而只有當緩沖大小變得很大時，PERT的帶寬占用率才輸給SACK，性能退化為PERT。這是因為當瓶頸鏈路的緩沖大小較小時，隊列長度在較早階段就處于較高“水位”，促使PERT運行在競爭模式中。這表示PERT在瓶頸鏈路的緩沖大小較小時，可以運行得很好。MPERT的帶寬占用率在較大的緩沖大小(3.5倍BDP或以上)的情況下會輸給SACK的原因主要是:MPERT運行在穩定模式下，試圖減少隊列長度，而SACK卻反之。因此，MPERT可以在較寬的緩沖區大小變化范圍中(從0.5倍BDP到3倍BDP)，與SACK競爭到公平的帶寬。從圖5中看到，PERT流始終不能獲得公平的帶寬。

另外還發現，MPERT/PERT相對SACK的丟包率始終處于“1”的下方。

這些結果為MPERT協議未來的部署提供了更充分的理由，它不僅可以廣泛應用于小緩沖區的路由設備，具有低時延要求的實時多媒體應用也可以得益于此。

3.4 在高速網絡中的性能

實驗說明改進后的MPERT在混合協議流環境下運行得很好，現在觀察MPERT是否能夠改善PERT在高帶寬網絡中的性能。在本實驗中，瓶頸鏈路的帶寬保持在2.4 Gbps不變，端節點的鏈路帶寬在100 Mbps~2.4 Gbps變化，端到端的RTT設定為120 ms，比較原PERT流和MPERT流在高帶寬網絡下的性能。圖6總結了實驗結果。筆者觀察到單條MPERT流比PERT流能夠更充分地利用高帶寬鏈路資源并且繼承了PERT流具有低丟包率的優點。對比高速網傳輸協議LTCP[3]的仿真結果，MPERT不但具有接近LTCP的高帶寬利用性能，而且具有明顯更低的丟包率。

4 結束語

本文對PERT原來的擁塞控制機制進行了改進，改進后的新機制根據傳輸時延感知網絡狀態，動態調整窗口增加系數α和窗口縮減系數β，使這種基于時延的協議在異質的網絡環境中，同樣可以運行得很好，獲得公平的帶寬、保持較少的丟包率。筆者相信，這一特性將為MPERT協議未來的部署過渡階段，在與主流協議TCP的帶寬競爭中，獲得公平地位提供有力的保障。另外，本文實驗結果還表明MPERT可以改善PERT在利用高速網絡的充裕帶寬方面的能力，并比同類高速網絡傳輸協議[3]具有更少的丟包率。

參考文獻:

[1]REWASKAR S， KAUR J， SMITH D. Why don’t delaybased congestion estimators work in the realworld， Technical report TR06001[R].[S.l.]: Department of Computer Science， UNC Chapel Hill， 2005.

[2]BHANDARKAR S， REDDY A L N， ZHANG Y， et al. Emulating AQM from end hosts[C]//Proc of ACM SIGCOMM. New York: ACM Press，2007: 349-360.

[3]BHANDARKAR S， JAIN S， NARASIMHA REDDY A L. LTCP: improving the performance of TCP in highspeed networks[J]. Computer Communication Review，2006，36(1): 41-50.

[4]WEI D X， JIN Cheng， LOW S H， et al. FAST TCP: motivation， architecture， algorithms， performance[C]//Proc of IEEE INFOCOM. Piscataway， NJ: IEEE Press，2006:1246-1259.

[5]LEITH D J， SHORTEN R N. HTCP protocol for highspeed long distance networks[C]//Proc of the 2nd PFLDNet. 2004.

[6]FENG W， KANDLUR D， SAHA D， et al. A selfconfiguring RED gateway[C]//Proc of IEEE INFOCOM’99. New York: IEEE Communications Society，1999:1320-1328.

[7]BANSAL D， BALAKRISHNAN H. Binomial congestion control algorithms[C]//Proc of INFOCOM. 2001:631-640.

[8]The network simulator NS-2[ EB/OL ].(2007-01). http: //www.isi.edu/nsnam/ns.

[9]CHIU D M， JAIN R. Analysis of the increase and decrease algorithms for congestion avoidance in computer networks[J]. Computer Networks and ISDN Systems，1989，17(1):1-14.