一種平滑的基于AIMD的TCP擁塞控制算法——SISD*

劉永立

(北京財貿職業學院信息物流系,北京 101101)

?

一種平滑的基于AIMD的TCP擁塞控制算法——SISD*

劉永立*

(北京財貿職業學院信息物流系,北京 101101)

摘要:提出一種基于AMID(Additive Increase Multiplicative Decrease)的雙平滑TCP擁塞控制算法,即SISD(Smooth Increase Smooth Decrease)。SISD算法在數據包發送方面采用一個單調遞減函數作為提升速度的增量函數。當檢測到網絡擁塞時,依據歷史擁塞窗口的大小調整發送窗口大小,避免了不必要的網絡抖動。仿真結果顯示,當UDP、TCP協議并存時,SISD可以為UDP協議提供穩定、平滑的服務,且具備較好的穩定性、公平性,同時提高網絡帶寬的利用率。

關鍵詞:擁塞控制;雙平滑擁塞控制;NS2仿真;加法增乘法減算法

UDP協議不提供可靠數據傳輸;相反,TCP協議根據數據包反饋和確認機制,可以提供面向鏈接的可靠數據傳輸服務。由于像IP語音技術、視頻會議等應用不需要數據包的可靠傳輸服務,因此,在這些應用中,數據傳輸一般是基于UDP協議的。由于UDP沒有擁塞控制機制,網絡出現擁塞時,基于UDP協議的應用仍然會持續的按照固定速度發送數據(有時還會提升發送數據的速度),隨著應用的增多,網絡帶寬會非常容易被這些UDP數據流耗盡,還會引起整個網絡的癱瘓。由于TCP會隨著網絡環境靈活調整擁塞窗口,一旦出現擁塞或即將出現擁塞,TCP會降低數據包發送速度;可是,UDP會一直試圖爭奪帶寬,這樣便失去公平性[1]。

TCP采用了加法增乘法減AIMD(Additive Increase Multiplicative Decrease)算法的沖突處理機制[2]。其規則是:在鏈路帶寬允許的情況下,以加法速度提升發包速度;在鏈路帶寬耗盡或擁塞出現時,以乘法速度迅速遞減發包速度。雖然此方法簡單實用,但是當鏈路中包含大量音頻、視頻數據流(這些數據流需要持續不斷的位傳輸),非常容易引起速度方面的抖動[3]。為了解決這一問題,本文在AIMD算法基礎上提出一個新的擁塞控制算法,稱之為雙平滑擁塞控制SISD(Smooth Increase Smooth Decrease)。該算法在連接建立階段,將與發包速度提升相關的參數值設置得較大;隨著時間的推移,參數值遞減(發包速度仍然提升,只是提升的幅度減低);當檢測到擁塞時,參照歷史窗口的大小來調整擁塞窗口,而不是簡單地大幅度減小窗口大小。該算法在窗口大小的調整上采用一個平滑單調遞減的函數,可以有效避免抖動。

1　SISD算法

SISD算法的基本思想來自于經典AIMD算法,并對之進行了修改。在“加法增”時,發包速度平滑提升所依據的是當前速率[4];在“乘法減”時,發包速度平滑降低所依據的是歷史窗口的大小[5]。詳細說明如下。

X+β(X)→X(β(X)→0,當X→+∞)

(1)

式(1)是基于固定時間間隔,如往返時延RTT(RoundTripTime)的。同時,利用式(2)(jain公平性指數)來評估多數據流情況下的公平性[6]。

(2)

其中,n是數據流數目,xi是第i個數據流在平衡點處的發包速率。FI是一個介于1和0之間的數值。FI=1是最理想的情況。通過下面介紹的方法我們可以達到這樣的效果:FI隨著xi數值的增大(按照式(1))而增大;隨著xi的減小,FI不受影響。這就說明,FI可以作為衡量不同數據流之間公平性的重要指標。圖1顯示了SAID算法與快速TCP算法(HighSpeedTCP)、可擴展TCP算法(ScalableTCP)、TCPReno算法的對比效果。

圖1　SISD算法與TCP其他改進算法的比較

SISD算法中的β(X)函數必須滿足如下條件才可以確保算法的有效性并減少網絡抖動:當X=0時,β(X)的數值可以很大;當X增大時,β(X)必須快速遞減。分段函數β(X)的變化情形如圖2所示。圖2中的曲線是輔助線,分段函數β(X)由圖中的橫線段組成。

分段函數β(X)的第1個階段顯示SISD算法檢測有效帶寬的速度,該階段的長度也表明該算法的激進程度。隨后的每個階段該函數有較小的增量,這樣在平衡點處減小了發送數據包的抖動現象[7]。

圖2　分段函數β(X)

(2)當收到負反饋信息,發送速率將會降低。可以采用TCP的窗口機制,通過調整擁塞窗口變量(CWND)的大小來改變發送速率。為了達到此目標,可以按照如式(3)計算窗口變量(CWND)的值。該公式基于Bilinear Transformation的連續型低通過濾器(低通過濾器適用于沖突控制策略[8]),并在其基礎上進行離散化。

(CWND_sampletk+CWND_sampletk-1)

(3)

其中,CWNDtk是當t=tk時的擁塞窗口數值。過濾器的截至頻率是1/τ,tk-tk-1是2個連續的包丟失事件之間的時間間隔。CWND_sampletk是在時刻tk處的取樣數值。在一般的輕度沖突時,CWND_sampletk被設置為CWND/2;在重度沖突時(超時發生時)CWND_sampletk被設置為1。CWND_sampletk-1是在時刻tk-1處的取樣數值。

式(3)中,CWNDtk的值依賴于歷史數據,包括CWNDtk-1、CWND_sampletk、CWND_sampletk-1以及連續兩次包丟失的時間間隔。

為了描述方便,假定δk=tk-tk-1,α=(2τ-δk)/(2τ+δk)。因此,式(3)可以改寫為式(4)。

(CWND_sampletk+CWND_sampletk-1)

(4)

從式(4)可見,如果δk(兩次包丟失之間的時間間隔)遞增,α遞減,意味著CWNDtk的值更多地依賴于當前取樣數據(相比于歷史數據而言)。換句話說,當丟包時間間隔增大,歷史數據(CWNDtk-1)對CWNDtk的影響將會降低;相反,若丟包時間間隔減小,α的數值隨之增大,CWNDtk的數值將會在更大程度上依賴于歷史數據CWNDtk-1,而不是當前取樣數據。從而使得擁塞窗口數值的變化呈現平滑過渡的態勢。

另外,過濾器的取樣頻率在公式中也是一個重要因素[9]。過濾器(式(3))有一個截止頻率1/τ,這意味著所有頻率超過1/τ的頻率分量會被過濾掉。基于奈奎斯特頻率采樣理論,一個信號的采樣頻率必須不低于它的最大頻率分量的兩倍[10]。因此,為了按照1/τ的頻率對信號采樣,采樣間隔要小于或等于τ/2。換句話說,CWNDtk必須在τ/2 s之內進行更新。在此情形下,式(3)中的CWND_sampletk可以用當前窗口大小代替。

圖3中顯示出SISD算法與傳統TCP算法在窗口數值計算上的不同。圖中黑色實線表示SISD算法窗口變化情況,虛線表示傳統TCP窗口變化情況,它們都是分段函數;與時間軸相交的垂直虛線代表算法的更新周期,相鄰的2個垂直虛線之間的時間長度是τ/2s(每經過一個更新周期,數值重新計算一次)。圖中黑色方框代表通過式(3)計算得到的窗口數值CWNDtk,白色方框代表式(3)中的CWND_sampletk和CWND_sampletk-1,黑色橢圓代表取樣數值,在式(3)中該數值用于計算CWND_sampletk。當非嚴重擁塞發生時,CWND_sampletk是取樣數值的一半;嚴重擁塞發生時,CWND_sampletk=1。

圖3　SISD算法描述

圖3涉及如下3種情況:

(1)在τ/2 s內出現超時或數據包丟失。過濾器利用歷史數據計算新的窗口大小(黑色方框),而不是直接將其降低為擁塞窗口的一半大小。圖3中的第1和第2個區間就是這種情況。

(2)超時或丟包發生在2個不同但是連續的τ/2 s內(圖3中第2和第3個區間是這種情況)。此時算法通過式(3)計算出窗口大小CWNDtk+2,而不是像傳統TCP算法那樣將其大小直接降為1。

(3)在τ/2 s內沒有數據包丟失(此種情況并未

在圖中顯示出來)。此種情況下窗口大小的計算采用上一次調度運行時使用的數值;另外,由于沒有丟包和超時出現,因此tk-tk-1=τ/2,因此式(3)可以簡化為式(5)。在這種情況下,CWND_sampletk數值的獲取來自于算法調度,實際上就是當前窗口大小。如果較長一段時間沒有發生丟包和超時現象,則窗口值將按照前面所述β(X)的方式持續遞增,從而使得發包速度平滑增長。

(CWND_sampletk+CWND_sampletk-1)

(5)

2　性能指標評估

為了評估SISD算法的性能,在NS2模擬器中實現該算法。主要針對SISD、TCP SACK、Scalable TCP、UDP共存情況下,各個算法在平滑性、公平性、穩定性等方面進行比較。

仿真實驗的網絡拓撲以及參數如圖4所示。圖中包含2個發送節點、2個接收節點,以及兩臺2個路由器。它們以瓶頸鏈路方式相連。

圖4　仿真實驗網絡拓撲

仿真過程中,路由器的緩沖大小設置為帶寬延遲積BDP(Bandwidth-Delay Product)的二倍,管理策略采用RED處理機制,RED的最大和最小閥值分別是1.4*BDP和0.4*BDP[11]。另一個重要參數是變量τ,它與低通過濾器的截止頻率(1/τ)和調度算法的時鐘間隔(τ/2)有緊密的聯系。一般而言,τ不能設置得太小。因為在一個很小的時間段內不一定會發生丟包,若將τ設置得太小,會造成調度算法頻繁運行。因此,建議將τ/2設置為等于一個往返時延。

通過圖5可以發現,SISD算法可以實現擁塞窗口的調整,同時發現,TCP SACK、Scalable TCP算法在調整窗口大小時出現了較大的抖動。通過圖6可以發現,當多數據流并存時,SISD算法可以實現數據包發送的平穩過渡。這樣,當它為UDP數據流提供持續不斷的服務時,就可以滿足基于UDP協議應用程序對持續位傳輸的強烈要求。

圖5　單數據流擁塞窗口變化

圖6　多數據流擁塞窗口變化

3　結論

本文在研究傳統TCP數據流的擁塞控制算法基礎上,通過借鑒AIMD算法,提出一個新的擁塞控制算法,命名為SISD。該算法在TCP連接建立階段,通過控制擁塞窗口的變化,使其初始增速平滑增大;當數據包發送速度接近可用帶寬極限且檢測到網絡擁塞時,算法利用擁塞窗口的歷史數據修正窗口大小,使其在擁塞窗口數值增速遞減的過程中也同樣能夠保持平穩。仿真結果顯示SISD算法減少了擁塞窗口的抖動,該算法不但能夠保持數據包發送速度的相對平穩,而且在TCP、UDP數據流同時存在時,該算法可以確保網絡帶寬占用的公平性。

參考文獻:

[1]劉群,張立嬌.無線傳感器網絡中基于拍賣博弈的數據包轉發算法[J].傳感技術學報,2013(7):991-996.

[2]吳元保,劉振盛,張文良.基于學習的擴展AIMD擁塞控制機制[J].計算機工程,2008,34(9):232-234.

[3]張麗娟,楊曉萍,陳虹,等.基于自適應參數設置的AIMD算法[J].吉林大學學報,2010,28(1):77-83.

[4]劉俊,謝華.一種改進的TCP擁塞控制算法[J].計算機工程,2011,37(13):95-106.

[5]陳旭,宋愛國.螞蟻算法與免疫算法結合求解TSP問題[J].傳感技術學報.2006(2):504-507.

[6]Marco Dorigo,Thomas Stuitizle.Ant Colony Optimization.[M].北京:清華大學出版社,2007:30-51.

[7]孫文勝,趙玉江.IPv6網絡接入控制方法研究與實現.[J].電子器件,2009(5):981-984+988

[8]金純,陳林星,楊吉云,等.IEEE802.11無線局域網[M].北京:電子工業出版社,2004:1-54.

[9]周潔.基于WIFI傳輸與接入技術的發展[J].信息通信,2012(2):115-116.

[10]Abdel-Moniem A M,Mohamed M H,Hedar A R,et al.An Ant Colony Optimization Algorithm for the Mobile Ad Hoc Network Routing Problem Based on AODV Protocol[C]//Proceedings of ISDA’10.2010:1332-1337.

[11]黃衛平.TCP/IP協議中擁塞控制算法探討[J].廣西工學院學報,2003,14(2):71-73.

劉永立(1970-),男,漢族,河北涿州市人,北京財貿職業學院教師,軟件工程碩士,研究方向為模式識別、人工智能,cgyliu@126.com。

ASmoothTCPCongestionControlAlgorithmBasedonAIMD—SISD*

LIUYongli*

(Beijing Vocational College of Finance and Commerce,Beijing 101101,China)

Abstract:SISD(Smooth Increase Smooth Decrease),a dual smooth TCP congestion control algorithm based on AIMD(Additive Increase Multiplicative Decrease)is presented.SISD uses a decreasing function as the increment in the speed of sending and when the congestion is detected,the current sending rate is changed smoothly referred the historical value of CWND,thus the oscillatory of sending speed is improved.The simulation results show that when the UDP and TCP co-exist,SISD provides a smooth services for UDP,and it has good fairness and stability,meanwhile it can improve the utilization of bandwidth.

Key words:congestion control;SISD;NS2 simulation;AIMD algorithm

doi:EEACC:7210G10.3969/j.issn.1005-9490.2014.04.019

中圖分類號:TP393.3

文獻標識碼:A

文章編號:1005-9490(2014)04-0665-04

收稿日期:2013-09-23修改日期:2013-10-15

項目來源:國家自然科學基金項目(61272350)