基于多尺度分層改進FAST TCP公平性算法研究

曾凌靜

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

關鍵詞： FAST TCP; 傳播延時; 公平; 分層; 多尺度

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

0? 引言

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

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

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

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

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

1? FAST TCP單向加速系統描述

根據實際的網絡模型，我們可以構建如圖1所示的網絡拓撲。圖1中，假設S1為信源主機節點，D1、D2、…DM為信宿主機節點。中間節點L1，L2構成瓶頸環節。信源主機、若干個相連接的鏈路和信宿主機組成一條路由。例如，S1-L1-L2-D1是一條路由。

對于FAST TCP連接i，有：發送端發送擁塞窗口（包）Wi（t）;FAST TCP流傳播時延baseRTT di;瓶頸鏈路L1-L2隊列排隊延時qi（t）;FAST TCP流往返延時RTT Di（t），其中Di=di+qi（s）;FAST TCP流速率xi（t）（數據包/秒），xi（t）=wi（t）/Di（t）;FAST TCP流協議參數（數據包）αi;比例增益協議參數gi;瓶頸鏈路L1-L2鏈路容量（數據包/秒）c;FAST TCP流窗口更新周期T（秒）。

FAST TCP流根據傳播延時baseRTT和往返延時定期更新擁塞窗口的偽代碼是：

2? 不公平性仿真驗證

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

把每個FAST TCP流的協議參數設置為αi=50，增益參數gi=0.5，假設每個包大小設置為1K字節。

假設路由器的緩沖區足夠大，可以避免數據包丟失，并且FAST TCP源端總是有數據要發送。仿真結果如圖3所示。

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

3? 改進后FAST算法描述

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

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

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

算法1：

在原有FAST基礎上做了如下改進：

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

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

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

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

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

證明：用數學歸納法證明。

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

當i=2，第一個FAST獲得準確的傳播延時， 第2層算法可以準確計算當前的瓶頸環節排隊延時。第二個FAST可以根據根據當前的往返延時減去排隊延時，從而計算準確的傳播延時。

假設這個結論對于i-1是正確的，現有的i-1個FAST TCP流已經建立了精確的傳播延時。

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

4? 模擬仿真

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

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

5? 結論

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

參考文獻：

[1] 袁曉華，洪小飛. FAST TCP模型的穩定性[J]. 西安文理學院學報（自然科學版），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]. 解放軍理工大學學報，2010，27（4）：5-9.