基于多尺度分層改進(jìn)FAST TCP公平性算法研究

曾凌靜

摘? 要： FAST TCP傳輸延時(shí)的估計(jì)是一個(gè)有待解決的問題。針對該關(guān)鍵問題，提出一種多尺度分層改進(jìn)算法。在第一層，以較小的時(shí)間尺度動(dòng)態(tài)記錄當(dāng)前類FAST TCP流的啟動(dòng)時(shí)間、運(yùn)行時(shí)間和往返延時(shí)等狀態(tài)信息;在第二層，以較大的尺度計(jì)算平均排隊(duì)延時(shí)。當(dāng)新的FAST TCP流到達(dá)時(shí)，根據(jù)當(dāng)前往返延時(shí)和第二層算法提供的平均排隊(duì)延時(shí)估計(jì)本時(shí)間周期傳播延時(shí)，在沒有外部測量設(shè)備參與和網(wǎng)絡(luò)支持的情況下，實(shí)現(xiàn)高精度的傳播延時(shí)估計(jì)。NS-2仿真結(jié)果驗(yàn)證了改進(jìn)算法的有效性。

關(guān)鍵詞： FAST TCP; 傳播延時(shí); 公平; 分層; 多尺度

中圖分類號： TP393? ? ? ? ? 文獻(xiàn)標(biāo)志碼： A? ? ? ? ? 文章編號： 1671-2153（2019）03-0105-04

0? 引言

FAST TCP[1-3]是針對高速長延時(shí)網(wǎng)絡(luò)提出的一種新型傳輸控制協(xié)議，它采用排隊(duì)延時(shí)來估計(jì)網(wǎng)絡(luò)擁塞狀態(tài)，使網(wǎng)絡(luò)運(yùn)行更加穩(wěn)定、高效、公平。與丟包概率相比，排隊(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ā)送窗口更新操作依賴于傳播延時(shí)BaseRTT參數(shù)，而該BaseRTT參數(shù)可描述為目前觀察到的最小往返傳輸延時(shí)（RTT）。由于瓶頸鏈路隊(duì)列永遠(yuǎn)不會(huì)清空，因此FAST TCP 可能無法準(zhǔn)確估計(jì)實(shí)際的傳輸延時(shí)，從而導(dǎo)致不公平性。然而，目前對FAST TCP的公平性的研究還沒有深入展開，它仍然是一個(gè)急待解決的問題。

文獻(xiàn)[4-5]解釋了這種不準(zhǔn)確估測導(dǎo)致FAST的不公平性，并表明：通過在每個(gè)流優(yōu)先級中給出第一個(gè)包來改進(jìn)這種估測，可以提高公平性并減少排隊(duì)變化。文獻(xiàn)[6]指出，只有在每個(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)[7]提出的方法無法保證隊(duì)列會(huì)被清空，所以無法獲得精確的傳播延時(shí)。文獻(xiàn)[8]提出了一種新的解決方案，它不依賴于直接測量傳播延時(shí);相反，通過調(diào)整傳輸速率，源端能夠計(jì)算出估計(jì)往返傳輸延時(shí)的誤差，從而與其他FAST TCP流均勻地共享鏈路。但文獻(xiàn)[7]表明，這種方法只有在新的FAST到達(dá)時(shí)才有效，因?yàn)镕AST對往返傳播延時(shí)的估計(jì)不準(zhǔn)確，當(dāng)多個(gè)FAST到達(dá)一個(gè)瓶頸鏈路時(shí)，會(huì)出現(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é)基金會(huì)、美國國防高級研究計(jì)劃局（DARPA）和思科公司資助，在加州理工學(xué)院（Caltech）開發(fā)了名為FAST TCPTM的一種突破性的網(wǎng)絡(luò)優(yōu)化技術(shù)。FASTSoft的產(chǎn)品提高了網(wǎng)站和web應(yīng)用程序的性能，并在不需要客戶端軟件或?yàn)g覽器插件的情況下，加快了視頻和其他數(shù)字內(nèi)容在互聯(lián)網(wǎng)上的分發(fā)速度。FASTSoft的E系列軟件安裝在現(xiàn)成的Dell服務(wù)器上，在沒有客戶端軟件或?yàn)g覽器插件的情況下，提供了最高級別的Internet性能和TCP加速;從發(fā)送器到任意多個(gè)接收器的加速度是單向的;它因?yàn)椴恍枰薷姆?wù)器或重寫代碼，使網(wǎng)絡(luò)和應(yīng)用程序透明地運(yùn)行，并且安裝迅速。

針對FAST單向加速的特點(diǎn)，本文提出了一種新的多尺度分層算法。在第一層，以較小的時(shí)間尺度動(dòng)態(tài)記錄當(dāng)前類FAST TCP流的啟動(dòng)時(shí)間、運(yùn)行時(shí)間和往返延時(shí)等狀態(tài)信息。在第二層，以較大的尺度計(jì)算本尺度周期的平均排隊(duì)延時(shí)。當(dāng)新的FAST TCP流到達(dá)時(shí)，根據(jù)當(dāng)前狀態(tài)的RTT和這個(gè)大尺度的平均排隊(duì)延時(shí)估計(jì)傳播延時(shí)，在沒有外部測量設(shè)備參與和網(wǎng)絡(luò)支持的情況下，實(shí)現(xiàn)了高精度的傳播延時(shí)估計(jì)。

1? FAST TCP單向加速系統(tǒng)描述

根據(jù)實(shí)際的網(wǎng)絡(luò)模型，我們可以構(gòu)建如圖1所示的網(wǎng)絡(luò)拓?fù)洹D1中，假設(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 TCP連接i，有：發(fā)送端發(fā)送擁塞窗口（包）Wi（t）;FAST TCP流傳播時(shí)延baseRTT di;瓶頸鏈路L1-L2隊(duì)列排隊(duì)延時(shí)qi（t）;FAST TCP流往返延時(shí)RTT Di（t），其中Di=di+qi（s）;FAST TCP流速率xi（t）（數(shù)據(jù)包/秒），xi（t）=wi（t）/Di（t）;FAST TCP流協(xié)議參數(shù)（數(shù)據(jù)包）αi;比例增益協(xié)議參數(shù)gi;瓶頸鏈路L1-L2鏈路容量（數(shù)據(jù)包/秒）c;FAST TCP流窗口更新周期T（秒）。

FAST TCP流根據(jù)傳播延時(shí)baseRTT和往返延時(shí)定期更新?lián)砣翱诘膫未a是：

2? 不公平性仿真驗(yàn)證

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

把每個(gè)FAST TCP流的協(xié)議參數(shù)設(shè)置為αi=50，增益參數(shù)gi=0.5，假設(shè)每個(gè)包大小設(shè)置為1K字節(jié)。

假設(shè)路由器的緩沖區(qū)足夠大，可以避免數(shù)據(jù)包丟失，并且FAST TCP源端總是有數(shù)據(jù)要發(fā)送。仿真結(jié)果如圖3所示。

從圖3可見，在0到150 s，S1-D1先創(chuàng)建的10條FAST TCP流能夠準(zhǔn)確地估計(jì)瓶頸鏈路L1-L2的傳播延時(shí)，因此可以公平地分配帶寬。在150 s到400 s之間，S1-D2中創(chuàng)建的10條FAST TCP流，在隊(duì)列無法清空的情況下，無法獲得準(zhǔn)確的傳播延時(shí)。從圖3看見，后面10條創(chuàng)建的FAST TCP 流估計(jì)的傳播延時(shí)比S1-D1鏈路的10條連接要大，估計(jì)排隊(duì)延時(shí)就小，因此比S1-D1鏈路的FAST TCP流獲得了更多的帶寬，從而使得各FAST TCP 流失去了公平性。同理，400 s到600 s之間，S1-D3又產(chǎn)生10條FAST TCP流，參與競爭帶寬，同理，后面產(chǎn)生的FAST TCP 流 比前400 s的FAST TCP流獲得了更多的帶寬。到600 s后，由于S1-D2的FAST TCP流結(jié)束了發(fā)送包，隊(duì)列瞬間出現(xiàn)的清空現(xiàn)象，S1-D1和S1-D3的活躍的FAST TCP流有機(jī)會(huì)估計(jì)了準(zhǔn)確的傳播延時(shí)，從而600 s后，活躍的FAST TCP流能夠公平的競爭帶寬，仿真驗(yàn)證了上述分析的準(zhǔn)確性。

3? 改進(jìn)后FAST算法描述

為了快速準(zhǔn)確地估計(jì)傳播延時(shí)，根據(jù)NS-2仿真結(jié)果，對改進(jìn)后的算法進(jìn)行分析。

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

在第一層算法，F(xiàn)AST TCP 流增加了啟動(dòng)時(shí)間和運(yùn)行時(shí)間兩個(gè)參數(shù)。當(dāng)FAST TCP到達(dá)時(shí)，小時(shí)間尺度記錄每個(gè)FAST TCP流啟動(dòng)時(shí)間、運(yùn)行時(shí)間、往返延時(shí)RTT和傳播延時(shí)baseRTT。第二層算法，大時(shí)間尺度統(tǒng)計(jì)這個(gè)時(shí)間尺度內(nèi)平均排隊(duì)延時(shí)，即平均排隊(duì)延時(shí)等于往返延時(shí)減去傳播延時(shí)。當(dāng)有新的FAST到達(dá)時(shí)，第二層算法可以為當(dāng)前FAST TCP流提供本時(shí)間尺度平均的排隊(duì)延時(shí)。在計(jì)算傳播延時(shí)時(shí)，根據(jù)當(dāng)前的往返延時(shí)減去第二層算法提供的平均排隊(duì)延時(shí)來估計(jì)準(zhǔn)確的傳播延時(shí)。

算法1：

在原有FAST基礎(chǔ)上做了如下改進(jìn)：

第一層算法，對于每個(gè)活動(dòng)的FAST TCP 流i，每小時(shí)間尺度，記錄當(dāng)前排隊(duì)時(shí)延qi，now;FAST TCP 流i的建立開始時(shí)間ti，start和運(yùn)行時(shí)間ti，time。

根據(jù)ti，start判斷確定本小時(shí)間尺度時(shí)間內(nèi)最早建立的FAST TCP排隊(duì)延時(shí)qi，now作為本小時(shí)間尺度瓶頸鏈路排隊(duì)延時(shí)。

第二層算法，大時(shí)間尺度統(tǒng)計(jì)瓶頸鏈路平均排隊(duì)延時(shí)qi，now，平均排隊(duì)延時(shí)等于各個(gè)小時(shí)間尺度（根據(jù)ti，start和ti，time）內(nèi)統(tǒng)計(jì)的各個(gè)排隊(duì)延時(shí)的平均值。

當(dāng)新的FAST TCP流j建立時(shí)，按公式（2）計(jì)算傳播延時(shí)。

定理1：在如圖1所是的單向加速網(wǎng)絡(luò)模型，多尺度分層改進(jìn)的FAST TCP算法1能夠使得每個(gè)活躍FAST TCP流計(jì)算出精確的傳播延時(shí)。

證明：用數(shù)學(xué)歸納法證明。

當(dāng)i=1時(shí)，瓶頸鏈路路由器的隊(duì)列為空，因此第一個(gè)FAST可以獲得準(zhǔn)確的傳播延時(shí)。

當(dāng)i=2，第一個(gè)FAST獲得準(zhǔn)確的傳播延時(shí)， 第2層算法可以準(zhǔn)確計(jì)算當(dāng)前的瓶頸環(huán)節(jié)排隊(duì)延時(shí)。第二個(gè)FAST可以根據(jù)根據(jù)當(dāng)前的往返延時(shí)減去排隊(duì)延時(shí)，從而計(jì)算準(zhǔn)確的傳播延時(shí)。

假設(shè)這個(gè)結(jié)論對于i-1是正確的，現(xiàn)有的i-1個(gè)FAST TCP流已經(jīng)建立了精確的傳播延時(shí)。

當(dāng)新的FAST到達(dá)時(shí)，第2層算法可提供本時(shí)間尺度內(nèi)平均的排隊(duì)延時(shí)。因?yàn)橹暗膫鞑パ訒r(shí)都準(zhǔn)確，所以排隊(duì)延時(shí)也是準(zhǔn)確的?，F(xiàn)有的i-1個(gè)FAST已經(jīng)建立了精確的傳播延時(shí)qnow，上層算法就可以提供準(zhǔn)確的隊(duì)列延時(shí)，因此第i個(gè)FAST可以利用算法1計(jì)算出精確的傳播延時(shí)。

4? 模擬仿真

以下給出了一組NS-2仿真結(jié)果，驗(yàn)證了改進(jìn)的公平性算法1的有效性。對“不公平性仿真驗(yàn)證”中考慮的相同環(huán)境進(jìn)行了仿真，結(jié)果如圖4所示。

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

5? 結(jié)論

根據(jù)FAST的單向應(yīng)用中各FAST TCP具有共享一些信息特點(diǎn)，提出了一種新的多尺度分層算法。在第一層，以較小的時(shí)間尺度收集活動(dòng)的FAST TCP流的歷史信息，如啟動(dòng)時(shí)間、運(yùn)行時(shí)間、排隊(duì)延時(shí)等。在第二層算法大尺度計(jì)算平均排隊(duì)延時(shí)。這樣，當(dāng)有新的FAST到達(dá)時(shí)，可以根據(jù)第二層算法提供的準(zhǔn)確排隊(duì)延時(shí)計(jì)算傳播延時(shí)，從而是以當(dāng)前估測的往返延時(shí)與計(jì)算的傳播延時(shí)之差作為瓶頸鏈路的排隊(duì)延時(shí)。仿真結(jié)果表明，在沒有外部測量設(shè)備參與和網(wǎng)絡(luò)支持的情況下，該算法可以提高TCP系統(tǒng)的公平性。

參考文獻(xiàn)：

[1] 袁曉華，洪小飛. FAST TCP模型的穩(wěn)定性[J]. 西安文理學(xué)院學(xué)報(bào)（自然科學(xué)版），2017，31（5）：53-59.

[2] ZHANG H，CHEN L，BAIREN Y，et al. CODA：Toward Automatically Identifying and Scheduling Coflows in the Dark[C]//Proceedings of the 2016 ACM SIGCOMM Conference. New York：ACM，2016：160-173.

[3] CHEN L，CHEN K，BAI W，et al. Scheduling Mix-flows in Commodity Datacenters with Karuna[C]//Proceedings of the 2016 ACM SIGCOMM Conference. New York：ACM，2016：174-187.

[4] CHEN Xiaolong，ZHANG Yun，LIU Z. Less conservative global stability for nonlinear FAST TCP system with time-varying time-delay[J]. Control Theory & Applications，2012，29（4）：477-485.

[5] TAN L S，YUAN C， ZUKERMAN M. FAST TCP：Fairness and Queueing Issues[J]. IEEE? Communications Letters，2005，9（8）：762-764.

[6] CUI T，ANDREW L L H，ZUKERMAN M，et al. Improving the Fairness of FAST TCP to New Flows[J]. IEEE? Communications Letters，2006，10（5）：414-416.

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

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