曾凌靜

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

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

中圖分類號： TP393? ? ? ? ? 文獻標志碼： A? ? ? ? ? 文章編號： 1671-2153（2019）03-0105-04

0? 引言

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

文獻[4-5]解釋了這種不準確估測導(dǎo)致FAST的不公平性，并表明：通過在每個流優(yōu)先級中給出第一個包來改進這種估測，可以提高公平性并減少排隊變化。文獻[6]指出，只有在每個流對其真正的傳播延時進行準確估計時，F(xiàn)AST才能實現(xiàn)公平性，除非有網(wǎng)絡(luò)支持，比如允許探測包繞過隊列，但獲得真正傳播延時的唯一方法是讓隊列清空。因此，Tony Cui建議對每個新啟動的流進行簡單的節(jié)流以清空隊列，從而獲得傳播延時的可靠估計。文獻[7]提出的方法無法保證隊列會被清空，所以無法獲得精確的傳播延時。文獻[8]提出了一種新的解決方案，它不依賴于直接測量傳播延時;相反，通過調(diào)整傳輸速率，源端能夠計算出估計往返傳輸延時的誤差，從而與其他FAST TCP流均勻地共享鏈路。但文獻[7]表明，這種方法只有在新的FAST到達時才有效，因為FAST對往返傳播延時的估計不準確，當(dāng)多個FAST到達一個瓶頸鏈路時，會出現(xiàn)不公平現(xiàn)象。雖然FAST不能直接通信，但該改進算法充分利用源端信息，獲得同步回退時鐘和最小回退因子，然后通過該算法使新舊流同時降低發(fā)送速率，最后，鏈路緩沖區(qū)隊列快速變?yōu)榭贞犃校瑥亩焖俟烙嬚鎸嵉膫鞑パ訒r。通過這種改進后的方法，能夠獲得較高的傳播延時估計精度和較好的新老流之間的公平性，但是這種方法需要犧牲FAST系統(tǒng)的一些穩(wěn)定性。

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

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

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

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

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

對于FAST TCP連接i，有：發(fā)送端發(fā)送擁塞窗口（包）Wi（t）;FAST TCP流傳播時延baseRTT di;瓶頸鏈路L1-L2隊列排隊延時qi（t）;FAST TCP流往返延時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ù)傳播延時baseRTT和往返延時定期更新?lián)砣翱诘膫未a是：

2? 不公平性仿真驗證

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

把每個FAST TCP流的協(xié)議參數(shù)設(shè)置為αi=50，增益參數(shù)gi=0.5，假設(shè)每個包大小設(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流能夠準確地估計瓶頸鏈路L1-L2的傳播延時，因此可以公平地分配帶寬。在150 s到400 s之間，S1-D2中創(chuàng)建的10條FAST TCP流，在隊列無法清空的情況下，無法獲得準確的傳播延時。從圖3看見，后面10條創(chuàng)建的FAST TCP 流估計的傳播延時比S1-D1鏈路的10條連接要大，估計排隊延時就小，因此比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ā)送包，隊列瞬間出現(xiàn)的清空現(xiàn)象，S1-D1和S1-D3的活躍的FAST TCP流有機會估計了準確的傳播延時，從而600 s后，活躍的FAST TCP流能夠公平的競爭帶寬，仿真驗證了上述分析的準確性。

3? 改進后FAST算法描述

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

如圖1所示，單向FAST TCP 網(wǎng)絡(luò)拓撲結(jié)構(gòu)只有一個信源主機節(jié)點S1，所有活動的FAST TCP 流都可以相互通信，活躍的FAST TCP流可以充分利用歷史流信息，快速準確地估測傳播延時。

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

算法1：

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

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

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

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

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

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

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

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

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

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

當(dāng)新的FAST到達時，第2層算法可提供本時間尺度內(nèi)平均的排隊延時。因為之前的傳播延時都準確，所以排隊延時也是準確的。現(xiàn)有的i-1個FAST已經(jīng)建立了精確的傳播延時qnow，上層算法就可以提供準確的隊列延時，因此第i個FAST可以利用算法1計算出精確的傳播延時。

4? 模擬仿真

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

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

5? 結(jié)論

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

參考文獻：

[1] 袁曉華，洪小飛. FAST TCP模型的穩(wěn)定性[J]. 西安文理學(xué)院學(xué)報（自然科學(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] 陳曉龍，張云. 基于歷史特征的FAST TCP公平性改進算法[J]. 解放軍理工大學(xué)學(xué)報，2010，27（4）：5-9.