基于歷史流量的單向FAST TCP公平性改進(jìn)算法研究

陳常暉 曾凌靜

摘? 要：FAST TCP傳輸延時(shí)的估計(jì)是一個(gè)有待解決的問題。針對這些開放性問題，根據(jù)FAST TCP的單向加速應(yīng)用特點(diǎn)，本文提出了一種新的傳輸層兩層算法。一個(gè)活動(dòng)的FAST TCP流的歷史信息，如啟動(dòng)時(shí)間、運(yùn)行時(shí)間等，在底層被記錄下來。當(dāng)新的FAST TCP流到達(dá)時(shí)，上層算法可以根據(jù)最早的FAST TCP流提供瓶頸鏈路的當(dāng)前隊(duì)列延時(shí)。傳播延時(shí)的計(jì)算是以當(dāng)前估測的最小往返延時(shí)與傳播延時(shí)之差作為瓶頸鏈路的排隊(duì)延時(shí)。最后，NS-2仿真結(jié)果驗(yàn)證了改進(jìn)的兩層算法的有效性。

關(guān)鍵詞：FAST TCP;傳播延時(shí);公平;歷史流量信息

中圖分類號：TP339? ? ?文獻(xiàn)標(biāo)識碼：A

Abstract：It is an open problem for the FAST TCP to estimate the true propagation delay.Aiming at these open problems，according to unilateral accelerated application characteristic of FAST TCP，a new two-layer algorithm is proposed.In the lower layer，the history information of the active FAST TCP flows，such as the startup time and the running time etc.，are recorded.When new FAST TCP flows arrive，the upper layer algorithm can provide the current queue delay of the bottleneck link based on the earliest FAST TCP flow.For the first time in the calculation propagation delay，the lower layer FAST TCP algorithm estimates the accurate propagation delay based on the current round trip delay minus the queuing delay provided through the upper algorithm.Finally，the NS-2 simulation results verify the effectiveness of this improved two-layer algorithm.

Keywords：FAST TCP;propagation delay;fairness;historic flow information

1? ?引言（Introduction）

FAST TCP[1-3]是針對高速長延時(shí)網(wǎng)絡(luò)提出的一種新的傳輸控制協(xié)議，它的目標(biāo)是使網(wǎng)絡(luò)運(yùn)行更加穩(wěn)定、高效、公平，它采用排隊(duì)延時(shí)來估計(jì)網(wǎng)絡(luò)擁塞狀態(tài)。與丟包概率相比，排隊(duì)延時(shí)提供了更好的擁塞估計(jì)，并能根據(jù)網(wǎng)絡(luò)容量進(jìn)行擴(kuò)展。利用排隊(duì)時(shí)延，確定窗口調(diào)整策略，使FAST TCP在高速長時(shí)延網(wǎng)絡(luò)中實(shí)現(xiàn)高吞吐量。但眾所周知，它們的均衡傳輸速率對估測的往返傳播延時(shí)的精度和估計(jì)的排隊(duì)延時(shí)都非常敏感[4-7]。FAST TCP的源發(fā)送窗口更新操作依賴于BaseRTT的參數(shù)，該參數(shù)用來估計(jì)往返傳播延時(shí)（RTPD），是目前觀察到的最小往返傳輸延時(shí)（RTT）。由于有時(shí)路由器隊(duì)列永遠(yuǎn)不會清空，因此FAST TCP可能無法準(zhǔn)確估計(jì)實(shí)際的傳輸延時(shí)，從而導(dǎo)致不公平性。然而，目前對FAST TCP公平性的研究還沒有深入展開，這仍然是一個(gè)有待解決的問題。

2? ?現(xiàn)狀分析（Current situation analysis）

在文獻(xiàn)[4]中，Linasheng Tan解釋了這種不準(zhǔn)確估測導(dǎo)致FAST中的不公平性，并表明，通過在每個(gè)流優(yōu)先級中給出第一個(gè)包來改進(jìn)這種估測，可以提高公平性并減少排隊(duì)變化。在文獻(xiàn)[5]中，只有在每個(gè)流對其真正的傳播延時(shí)進(jìn)行準(zhǔn)確估計(jì)時(shí)，F(xiàn)AST才能實(shí)現(xiàn)公平性。除非有網(wǎng)絡(luò)支持，比如允許探測包繞過隊(duì)列，否則獲得真正傳播延時(shí)的唯一方法是讓隊(duì)列清空。因此，Tony Cui建議對每個(gè)新啟動(dòng)的流進(jìn)行簡單的節(jié)流以清空隊(duì)列，從而獲得傳播延時(shí)的可靠估計(jì)。在文獻(xiàn)[6]中，Miguel發(fā)現(xiàn)這種方法并不總是有效的。Miguel表明，只有當(dāng)競爭低值的往返傳播延時(shí)超過文獻(xiàn)[6]中的下限時(shí)，這種速率降低方法才有效，并且不能完全耗盡瓶頸隊(duì)列，因此無法獲得精確的傳播延時(shí)擁塞。

于是，Miguel提出了一種新的解決方案，它不依賴于直接測量傳播延時(shí)。相反，通過調(diào)整傳輸速率，源端能夠計(jì)算出估計(jì)往返傳輸延時(shí)的誤差，從而與其他FAST流均勻地共享鏈路。然而，在文獻(xiàn)[7]中表明，這種方法只有在新的FAST到達(dá)時(shí)才有效。因?yàn)镕AST對往返傳播延時(shí)的估計(jì)不準(zhǔn)確，當(dāng)多個(gè)FAST到達(dá)一個(gè)瓶頸鏈路時(shí)，會出現(xiàn)不公平現(xiàn)象。雖然FAST不能直接通信，但該改進(jìn)算法充分利用源端信息，獲得同步回退時(shí)鐘和最小回退因子，然后通過該算法使新舊流同時(shí)降低發(fā)送速率。最后，鏈路緩沖區(qū)隊(duì)列快速變?yōu)榭贞?duì)列，從而快速估計(jì)真實(shí)的傳播延時(shí)。通過這種改進(jìn)后的方法，能夠獲得了較高的傳播延時(shí)估計(jì)精度和較好的新老流之間的公平性，但是這種方法需要犧牲FAST系統(tǒng)的一些穩(wěn)定性。

綜上所述，對于FAST的開放性問題，目前還沒有很好的解決方案。因此，我們希望通過FAST TCP商業(yè)應(yīng)用找到解決這一開放問題的方法。

FASTSoft公司成立于2006年，是由美國國家科學(xué)基金會、美國國防高級研究計(jì)劃局（DARPA）和思科公司資助，它在加州理工學(xué)院（Caltech）開發(fā)的一種突破性的網(wǎng)絡(luò)優(yōu)化技術(shù)，名為FAST TCPTM。FASTSoft的產(chǎn)品提高了網(wǎng)站和web應(yīng)用程序的性能，并在不需要客戶端軟件或?yàn)g覽器插件的情況下，加快了視頻和其他數(shù)字內(nèi)容在互聯(lián)網(wǎng)上的分發(fā)速度。如圖1所示，F(xiàn)ASTSoft的E系列軟件安裝在現(xiàn)成的Dell服務(wù)器上，在沒有客戶端軟件或?yàn)g覽器插件的情況下，提供了最高級別的Internet性能和TCP加速。它使網(wǎng)絡(luò)和應(yīng)用程序透明地運(yùn)行，并且安裝迅速，因?yàn)椴恍枰薷姆?wù)器或重寫代碼。從發(fā)送器到任意多個(gè)接收器的加速度是單向的。

針對FAST單向加速的特點(diǎn)，本文提出了一種新的傳輸層雙層算法。在底層，以較小的時(shí)間尺度動(dòng)態(tài)記錄FAST TCP流的啟動(dòng)時(shí)間、運(yùn)行時(shí)間等歷史信息。當(dāng)新的FAST TCP流到達(dá)時(shí)，上層算法根據(jù)最早活動(dòng)FAST的傳播延時(shí)，在沒有外部測量設(shè)備參與和網(wǎng)絡(luò)支持的情況下，實(shí)現(xiàn)了高精度的傳播延時(shí)估計(jì)。由于采用了以上算法，解決了FAST不能同時(shí)收斂的問題[8]。

3? ?FAST TCP單向加速系統(tǒng)描述（Description of the FAST TCP unilateral accelerating system）

根據(jù)實(shí)際的網(wǎng)絡(luò)模型，我們可以構(gòu)建如圖2所示的網(wǎng)絡(luò)拓?fù)洹D2中，假設(shè)S1為信源主機(jī)節(jié)點(diǎn)，D1、D2、…、DM為信宿主機(jī)節(jié)點(diǎn)。中間節(jié)點(diǎn)L1、L2構(gòu)成瓶頸環(huán)節(jié)。信源主機(jī)、若干個(gè)相連接的鏈路和信宿主機(jī)組成一條路由。例如，S1- L1-L2-D1是一條路由。

對于FAST連接i，有：：發(fā)送端擁塞窗口大小（包）;：傳播時(shí)延;：隊(duì)列時(shí)延;：RTT，（s）;：速率（數(shù)據(jù)包/秒）;;：協(xié)議參數(shù)（數(shù)據(jù)包）;：協(xié)議參數(shù);：鏈路容量（數(shù)據(jù)包/秒）;：窗口更新周期（秒）。

4? ?不公平性驗(yàn)證（Demonstration of unfairness）

考慮到FIFO調(diào)度下的FAST TCP流，我們在圖2所示的網(wǎng)絡(luò)拓?fù)渖线\(yùn)行以下NS2仿真。鏈路容量和傳播時(shí)延如圖2所示。使用一個(gè)FAST TCP發(fā)送器和三個(gè)接收器（S1-D1，S1-D2，S1-D3），每對創(chuàng)建10個(gè)具有不同活動(dòng)周期的FAST TCP流，如圖3所示。

從圖4可見，在150（s）和400（s）中，延遲連接的FAST TCP流高估了它的傳播延遲，因?yàn)樗乃邪冀?jīng)歷了顯著的排隊(duì)延遲，因此它的baseRTT太高。因此，對于早期加入FAST TCP流，它低估了排隊(duì)延遲，這使得延遲連接流更具攻擊性，從而獲得更高的吞吐量。在600（s）中，當(dāng)FAST TCP流離開路由2時(shí)，隊(duì)列占用率下降，因此現(xiàn)有的FAST TCP流都得到真實(shí)的傳播延遲，并獲得瓶頸鏈路帶寬的相等份額。

5? 改進(jìn)后的兩層算法（Improved two-layer algorithm）

根據(jù)以上仿真結(jié)果，為了快速準(zhǔn)確地估計(jì)傳播延時(shí)，分析如下：

如圖2所示，單向FAST TCP網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)只有一個(gè)信源主機(jī)節(jié)點(diǎn)S1，因此所有活動(dòng)的FAST TCP都可以相互通信，延時(shí)連接流可以充分利用歷史流信息，快速準(zhǔn)確地估測傳播延時(shí)。

在底層，F(xiàn)AST TCP增加了啟動(dòng)時(shí)間和運(yùn)行時(shí)間兩個(gè)參數(shù)。當(dāng)FAST到達(dá)時(shí)，每個(gè)參數(shù)都記錄它的流啟動(dòng)時(shí)間并計(jì)算它的運(yùn)行時(shí)間。上層算法總是為最早活動(dòng)的FAST保存歷史信息。當(dāng)新的FAST到達(dá)時(shí)，上層算法可以為當(dāng)前隊(duì)列延時(shí)提供最早的啟動(dòng)時(shí)間和運(yùn)行時(shí)間。在計(jì)算傳播延時(shí)時(shí)，下層FAST算法首次沒有用最小的往返估計(jì)傳播延時(shí)，而是根據(jù)當(dāng)前的往返延時(shí)減去上層算法提供的排隊(duì)延時(shí)來估計(jì)準(zhǔn)確的傳播延時(shí)。改進(jìn)后的算法實(shí)現(xiàn)如下：

6? ?虛擬仿真（Simulation）

將圖4與圖5進(jìn)行比較，在150（s）和400（s）中，延遲連接的FAST TCP流用算法1估算精確的傳播延遲，可以得到瓶頸鏈路帶寬的相等份額。在600（s）中，當(dāng)FAST TCP流離開路由2時(shí)，隊(duì)列占用率下降，因此現(xiàn)有的FAST TCP流都得到真正的傳播延遲，并獲得瓶頸鏈路帶寬的相等份額。

7? ?結(jié)論（Conclusion）

根據(jù)FAST的單向加速應(yīng)用特點(diǎn)，提出了一種新的傳輸層兩層算法。在底層，以較小的時(shí)間尺度收集活動(dòng)的FAST的歷史信息，如啟動(dòng)時(shí)間、運(yùn)行時(shí)間等。當(dāng)新的FAST到達(dá)時(shí)，上層算法可以根據(jù)最早的FAST提供瓶頸鏈路的當(dāng)前隊(duì)列延時(shí)。傳播延時(shí)是以當(dāng)前估測的最小往返延時(shí)與傳播延時(shí)之差作為瓶頸鏈路的排隊(duì)延時(shí)。仿真結(jié)果表明，在沒有外部測量設(shè)備參與和網(wǎng)絡(luò)支持的情況下，該算法可以提高TCP系統(tǒng)的公平性。

參考文獻(xiàn)（References）

[1] 梁偉，張順頤，寧向延，等.基于穩(wěn)定性的FASTTCP參數(shù)γ調(diào)整[J].通信學(xué)報(bào)，2010，31（7）：53-59.

[2] David X.Wei，Cheng Jin，S.H.Low.FAST TCP：motivation，architecture， algorithms，performance[J].IEEE/ACM Transactions on Networking，2006，14（6）：1246-1259.

[3] Chen Xiao-long，Zhang Yun.Less conservative global stability for nonlinear FAST TCP system with time-varying time-delay[J].Control Theory & Applications，2012，29（4）：477-485.

[4] Liansheng Tan，Cao Yuan，Mosh Z.FAST TCP：Fairness and Queueing Issues[J].IEEE Communications Letters，2005，9（8）：762-764.

[5] Tony Cui，Lachlan，Liansheng Tan.Improving the Fairness of FAST TCP to New Flows[J].IEEE Communications Letters，2006，10（5）：414-416.

[6] Migule R，Sergio H.Achieving Fair Network Equilibria with Delay-based Congestion Control Algorithms[J].IEEE? Communications Letters，2008，12（7）：535-537.

[7] 陳曉龍，張?jiān)?基于歷史特征的FAST TCP公平性改進(jìn)算法[J].解放軍理工大學(xué)學(xué)報(bào)，2010，27（4）：5-9.

[8] 陳靜，鄭明春.基于歷史流量及其性能分析的擁堵控制算法[J].計(jì)算機(jī)研究與發(fā)展雜志，2003，40（10）：1470-1475.