劉永立

(北京財(cái)貿(mào)職業(yè)學(xué)院信息物流系,北京 101101)

?

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

劉永立*

(北京財(cái)貿(mào)職業(yè)學(xué)院信息物流系,北京 101101)

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

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

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

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

1　SISD算法

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

X+β(X)→X(β(X)→0,當(dāng)X→+∞)

(1)

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

(2)

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

圖1　SISD算法與TCP其他改進(jìn)算法的比較

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

分段函數(shù)β(X)的第1個(gè)階段顯示SISD算法檢測有效帶寬的速度,該階段的長度也表明該算法的激進(jìn)程度。隨后的每個(gè)階段該函數(shù)有較小的增量,這樣在平衡點(diǎn)處減小了發(fā)送數(shù)據(jù)包的抖動(dòng)現(xiàn)象[7]。

圖2　分段函數(shù)β(X)

(2)當(dāng)收到負(fù)反饋信息,發(fā)送速率將會(huì)降低?？梢圆捎肨CP的窗口機(jī)制,通過調(diào)整擁塞窗口變量(CWND)的大小來改變發(fā)送速率。為了達(dá)到此目標(biāo),可以按照如式(3)計(jì)算窗口變量(CWND)的值。該公式基于Bilinear Transformation的連續(xù)型低通過濾器(低通過濾器適用于沖突控制策略[8]),并在其基礎(chǔ)上進(jìn)行離散化。

(CWND_sampletk+CWND_sampletk-1)

(3)

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

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

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

(CWND_sampletk+CWND_sampletk-1)

(4)

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

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

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

圖3　SISD算法描述

圖3涉及如下3種情況:

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

(2)超時(shí)或丟包發(fā)生在2個(gè)不同但是連續(xù)的τ/2 s內(nèi)(圖3中第2和第3個(gè)區(qū)間是這種情況)。此時(shí)算法通過式(3)計(jì)算出窗口大小CWNDtk+2,而不是像傳統(tǒng)TCP算法那樣將其大小直接降為1。

(3)在τ/2 s內(nèi)沒有數(shù)據(jù)包丟失(此種情況并未

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

(CWND_sampletk+CWND_sampletk-1)

(5)

2　性能指標(biāo)評估

為了評估SISD算法的性能,在NS2模擬器中實(shí)現(xiàn)該算法。主要針對SISD、TCP SACK、Scalable TCP、UDP共存情況下,各個(gè)算法在平滑性、公平性、穩(wěn)定性等方面進(jìn)行比較。

仿真實(shí)驗(yàn)的網(wǎng)絡(luò)拓?fù)湟约皡?shù)如圖4所示。圖中包含2個(gè)發(fā)送節(jié)點(diǎn)、2個(gè)接收節(jié)點(diǎn),以及兩臺(tái)2個(gè)路由器。它們以瓶頸鏈路方式相連。

圖4　仿真實(shí)驗(yàn)網(wǎng)絡(luò)拓?fù)?/p>

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

通過圖5可以發(fā)現(xiàn),SISD算法可以實(shí)現(xiàn)擁塞窗口的調(diào)整,同時(shí)發(fā)現(xiàn),TCP SACK、Scalable TCP算法在調(diào)整窗口大小時(shí)出現(xiàn)了較大的抖動(dòng)。通過圖6可以發(fā)現(xiàn),當(dāng)多數(shù)據(jù)流并存時(shí),SISD算法可以實(shí)現(xiàn)數(shù)據(jù)包發(fā)送的平穩(wěn)過渡。這樣,當(dāng)它為UDP數(shù)據(jù)流提供持續(xù)不斷的服務(wù)時(shí),就可以滿足基于UDP協(xié)議應(yīng)用程序?qū)Τ掷m(xù)位傳輸?shù)膹?qiáng)烈要求。

圖5　單數(shù)據(jù)流擁塞窗口變化

圖6　多數(shù)據(jù)流擁塞窗口變化

3　結(jié)論

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

參考文獻(xiàn):

[1]劉群,張立嬌.無線傳感器網(wǎng)絡(luò)中基于拍賣博弈的數(shù)據(jù)包轉(zhuǎn)發(fā)算法[J].傳感技術(shù)學(xué)報(bào),2013(7):991-996.

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

[3]張麗娟,楊曉萍,陳虹,等.基于自適應(yīng)參數(shù)設(shè)置的AIMD算法[J].吉林大學(xué)學(xué)報(bào),2010,28(1):77-83.

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

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

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

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

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

[9]周潔.基于WIFI傳輸與接入技術(shù)的發(fā)展[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]黃衛(wèi)平.TCP/IP協(xié)議中擁塞控制算法探討[J].廣西工學(xué)院學(xué)報(bào),2003,14(2):71-73.

劉永立(1970-),男,漢族,河北涿州市人,北京財(cái)貿(mào)職業(yè)學(xué)院教師,軟件工程碩士,研究方向?yàn)槟Ｊ阶R(shí)別、人工智能,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

中圖分類號(hào):TP393.3

文獻(xiàn)標(biāo)識(shí)碼:A

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

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

項(xiàng)目來源:國家自然科學(xué)基金項(xiàng)目(61272350)