一種基于CAPPROBE帶寬估計的TCP Westwood算法

袁鵬飛，鄭 濤，楊李冬，3，戴平陽，謝 怡，2＊

（1.廈門大學信息科學與技術學院，福建 廈門361005；2.廈門大學云計算與大數據中心，福建 廈門361005；3.廈門大學深圳研究院，廣東 深圳518052）

傳 輸 控 制 協 議 （transmission control protocol，TCP）是因特網最重要的協議之一.TCP通過流量控制、差錯控制和擁塞控制保證端到端通信的可靠性.其中，擁塞控制通過調整發送端傳輸速率來適應網絡容量的實時變化，避免網絡擁塞的發生.一旦投入網絡的數據超過網絡核心設備（如路由器）的處理能力，就很容易發生網絡擁塞，并導致網絡性能的急劇下降.

本文主要討論擁塞控制機制對TCP傳輸性能的影響，尤其是它在無線網絡中的作用.擁塞控制主要包括4個經典算法［1］：慢啟動、擁塞避免、快重傳和快恢復.這些算法在有線網絡和應用中體現了很好的性能.但在無線網絡中丟包的原因既可能因為網絡擁塞也可能是由信道錯誤引起.若在這種情況下使用傳統TCP，所有的丟包事件都會觸發擁塞控制機制而減小擁塞窗口（cwnd），導致不必要的參數調整，從而降低網絡性能.因此，不少研究者致力于設計更適合無線網絡的 TCP擁塞機制，例如 TCP Peach［2］，TCP Veno［3］和 TCP Westwood（TCPW）［4］.

TCPW通過監控ACK流來估計帶寬，根據帶寬值調整cwnd.許多研究結果表明［4－5］，TCPW 相比于傳統TCP在無線網絡中具有更好吞吐量和更小的時延.實時帶寬估計是TCPW的關鍵部分，而其原始的帶寬估計方法不準確［6］.

本文基于CAPPROBE帶寬估計算法［7］，提出了一種新的網絡擁塞控制算法TCPW CAPPROBE（TCPWC）.CAPPROBE是基于雙包探測技術的帶寬估計算法.與其他基于探測包算法［8－9］相比，CAPPROBE的計算代價更小，速度更快，而且更精確.當探測包尺寸減小時，獲得精確帶寬的概率將更大.在TCPWC中，小尺寸的ACK所扮演的就是探測包的角色.由于ACK只有幾十字節，這樣的小尺寸探測包易于獲得瓶頸鏈路的準確帶寬.

因此，TCPWC算法能通過更準確的帶寬估計來合理地調整cwnd和慢啟動閾值（ssthresh），避免擁塞控制機制的過度反應，從而提高無線網絡的傳輸性能.

1 相關工作

1.1 TCPW及相關研究

基于TCP Reno機制的TCPW，同樣具有慢啟動、擁塞避免、快速重傳等機制.在慢啟動階段，發送端每收到一個新的ACK，cwnd增加1個最大數據分組（maximal segment size by bytes，MSS）.當cwnd大于ssthresh時，網絡進入擁塞避免階段.此時，發送端每接收到一個新的ACK，cwnd增加1／cwnd個MSS，即呈線性增長方式.當網絡擁塞或者鏈路錯誤而產生丟包時，TCPW不是簡單地減小參數而是根據帶寬估計值BW對cwnd和ssthresh進行更新，具體算法如下：cwnd＝1，ssthresh is given，flag＿FF＝0；∥初始化，flag＿FF用來標記是否處于快重傳階段

其中，RTTmin是整個連接過程中RTT樣本的歷史最小值，SegmentSize指傳送數據段大小.若網絡擁塞程度增加而引起丟包，BW估計值因RTT采樣值的增大而減小，而RTTmin值仍為歷史最小值，因此ssthresh減小以緩解擁塞，發送端減緩數據發送.

接下來，本文介紹TCPW根據ACK流估計當前帶寬b的算法，如公式（1）.其中，Cack代表ACK數量，Sseg是TCP包大小，tnow表示當前ACK的接收時間，tlast表示上一個ACK的接收時間.

僅使用公式（1）得到帶寬可能存在較大錯誤.為了得到更準確的帶寬值，Astrom等［10］提出了基于Tusin近似值的平滑模型處理，以當前平滑帶寬值＾bk作為實時帶寬估計值，如公式（2）所示.

TCPW在無線網絡通信方面表現了較傳統TCP更好的性能潛力，因此大量的研究圍繞著它展開.研究方法各有側重，有些工作關注數據TCP傳輸的吞吐量和數據延遲等指標.例如CMT機制［11］在估計帶寬值之后，使用新的策略來更新cwnd值，從而實現高效傳輸.趙文波等［12］則通過調整TCPW擁塞控制算法慢啟動階段和擁塞避免階段的發送窗口增長規則來提高網絡性能.有些工作關注TCP的友好性和公平性.例如TCPW for multiple paths（MPTCPW）［13］在通信鏈路之間進行協作式的擁塞控制，從而達到鏈路負載均衡以及瓶頸鏈路的公平性.還有些研究在TCPW與帶寬估計算法的結合方面投入較大精力［6，14］.例如 Gangadhar等［6］指出TCPW采用的帶寬估計算法因為ACK壓縮現象會導致估計帶寬偏高，因此提出使用RTT的相關值來估計帶寬.本文則巧妙地將ACK機制與基于雙包技術的CAPPROBE帶寬估計算法相結合，更準確地估計帶寬，并對cwnd和ssthresh進行更合理的自適應調整，以達到充分利用鏈路可用容量的目標.

1.2 帶寬估計及相關研究

網絡傳輸路徑由從數據發送端到接收端的一系列鏈路組成.路徑帶寬指該路徑能提供的最大IP層傳輸速率.因此，路徑帶寬取決于瓶頸鏈路帶寬.端對端路徑可用帶寬估計要反映瓶頸鏈路的可用帶寬，并以此作為網絡鏈路性能的重要測量參數.

目前大部分帶寬估計方法都是基于雙包技術［7，15］.具體做法是，發送兩個連續的數據包，而經過瓶頸鏈路的時候會使得他們產生間隔，接收方根據這個間隔來計算瓶頸鏈路帶寬.還有一類工作以觀測TCP數據段的單向延遲來測量帶寬，不足是需要發送大量的探測TCP數據段報文，如Pathload［16］.這類技術額外發送的探測報文本身就可能造成網絡的阻塞.其它無線網絡帶寬估計方法［17－18］也存在類似的問題.

相比以上帶寬估計算法，本文采用的CAPPROBE算法巧妙地改造TCP的ACK機制進行帶寬估計.它未引用額外的數據探測分組，探測包就是小尺寸的ACK分組.因此，具有代價小，速度快，而且更精確的特點.

2 TCPWC的設計

2.1 CAPPROBE帶寬估計算法

雙包技術［19］于1991年首次被提出，其關鍵是發送端發送兩個連續沒有空隙的探測包.假設，L是雙包中第2個包的大小，B是經過路徑中的瓶頸鏈路帶寬，則雙包經過瓶頸鏈路而導致的到達間隔時間為T＝L／B.由此，可以得到B的表達公式：

然而，真實網絡存在背景流量，此時測量帶寬值可能有偏差，如圖1所示.圖1（a）表示沒有背景流量影響的理想環境下，帶寬估計值是準確的.但一旦有背景流量，就很難獲得準確的可用帶寬.例如圖1（b），當雙包中第1個包由于背景流而遭遇的時延比第2個更長，就導致T減小，從而估算的帶寬會偏大；再如圖1（c），當第2個包排隊的時間延長，導致T增大，因此估算的帶寬值會偏小.

首先定義雙包時延和為數據包對中兩個包的單向時延之和.在沒有背景流量的理想環境中估計的帶寬是比較準確的，所以我們在雙包時延和最小的情況下測得的帶寬是最接近準確值.因此，CAPPROBE綜合考慮時間間隔T和探測包對的時延.由于每對探測包都會因排隊產生時延，CAPPROBE將逐一記錄所有的雙包的時延和以及對應的雙包間隔T值.在估測帶寬時，根據已有的記錄找出時延和最小的探測包樣本，然后用該樣本相應的T值來估計瓶頸鏈路帶寬，然后再根據包間隔模型公式［20］計算可用帶寬值.每次帶寬估計完成后，對時延和T的記錄表進行初始化清零，重新開始記錄新的雙包信息.

2.2 TCPWC的設計

本文在TCPW的基礎上結合CAPPROBE做了帶寬估測的改進.其主要思想是：接收端對于收到任何數據包都發送兩個連續的相同的ACK包，發送端根據接收到的ACK包使用CAPPROBE算法進行帶寬估計，進而對cwnd和ssthresh值進行合理的調整，即由ACK包扮演雙包技術中的探測包角色.

如圖2，SEQ為TCP頭部序列號字段，ACK是TCP頭部確認號字段，假設每個數據段都是滿數據段.首先發送方和接收方通過3次握手建立TCP連接，然后進入發送數據階段.發送方正常發送數據包；接收方每收兩個滿數據段觸發一次確認，連續回復兩個重復的ACK.當發送方收到雙ACK包，則進行雙包處理階段.若發生超時或者收到3個重復的標準ACK，發送端找出時延T和最小的樣本L計算實時帶寬BW，詳見公式（3）.實時帶寬BW將應用1.1節所示的TCPW算法實現TCPWC的擁塞控制.

圖1 雙包探測的3種情況Fig.1 Packet pair dispersion

圖2 TCPWC時序圖Fig.2 The sequence chart of TCPWC

為了區分標準ACK包和輔助ACK包，本文對輔助ACK包進行了標記.TCP的頭部結構有個保留（reserved）字段，共6位，默認全置.保留字段是為了將來定義新的用途而設，而本文利用它來標記輔助ACK包，即使其置全1，如圖3所示.根據發送方收到ACK的3種情況，雙包處理階段如下：

1）收到ACK雙包時，將根據保留字段值來區分兩類ACK包.若值為全1，僅需要記錄其達到時間等相關信息；若值為全0，則記錄相關信息后，進入標準TCP協議的控制運作.

2）僅收到標準ACK.不進行實時帶寬測量的采樣，直接進入標準TCP協議的控制運作.

3）僅收到輔助ACK.將輔助ACK的反饋信息利用起來，亦直接進入標準TCP協議的控制運作.

圖3 輔助ACK的TCP頭部結構Fig.3 The structureof TCP header in an assistant ACK

3 TCPWC的實現及評估

本文采用仿真環境NS3來實現、驗證和評估TCP擁塞控制機制的性能.首先，本文在NS3（v.3.17）加載了 TCPW 的補丁［6］，并實現了 TCPWC.

3.1 TCPWC的NS3仿真實現

本文在NS3仿真環境中實現了TCPWC模塊，TCPWC的主要流程如圖4所示，主要功能函數如下：

圖4 TCPWC流程圖Fig.4 The flowchart of TCPWC

Ack（）：處理新接收的ACK，記錄相關信息.

CutAck（）：根據ACK包頭部的保留字段識別是否構造ACK包，如值置全1，則丟棄.

CountAck（）：保存接收端收到的連續ACK的數量.

EstimateBWC（）：TCPWC根據 CAPPROBE 算法估計帶寬.

NewAck（）：根據TCP Reno的規則來設置cwnd和ssthresh的值.

DupAck（）：接收的ACK數量超過某個常數之后，根據估計的帶寬對cwnd和ssthresh值進行調整.

Data（）：接收者收到新的數據.

SendPacketC（ACK）：這里除了發送正常的ACK包之外，還緊接著發送一個本文構造的ACK包.

3.2 實驗環境

為了評估不同指標下各TCP版本的吞吐量對比，本文建立了圖5的拓撲環境.其中吞吐量是指網絡在單位時間內成功傳送的數據總量.在利用圖5拓撲比較吞吐量的實驗中，拓撲中只有一條TCP連接，每次實驗采用不同擁塞控制機制的TCP版本.此時，吞吐量的值只需考慮一條連接在單位時間內成功傳送的數據.路由器左邊的鏈路帶寬為10Mbits／s，傳播時延為25ms，路由器右邊鏈路帶寬為2Mbits／s，傳播時延為0.01ms.為了模擬無線環境，鏈路都配置了錯誤模塊來模擬無線鏈路丟包.為了和文獻結果［4］進行對比，本文都保持了許多典型參數，例如誤包率（packet error rates，PER）設置為0.05且符合均勻分布，最大傳輸單元（maximum transmission unit，MTU）大小為400B，延遲 ACK計數為2，延遲ACK超時時間為200ms，代表性的數據流來自FTP應用.為了實驗結果的可靠性，每次仿真模擬時間長達300s，每次仿真試驗都重復多次，再計算指標的平均值.詳細參數見表1.

圖5 仿真拓撲圖Fig.5 Simulation topology of throughput

表1 仿真參數Tab.1 Simulation parameters

本文還針對算法的友好性和公平性的評估設計了圖6的拓撲環境.與圖5拓撲不同，圖6仿真拓撲包含多條TCP連接，吞吐量的計算需要考慮多條連接.路由器A和B之間是一條帶寬為2Mbits／s，傳播時延為2ms的瓶頸鏈路.源主機通過一條帶寬為10 Mbits／s，時延為0.01ms的Access鏈路與路由器A連接，目的主機通過一條同樣的Access鏈路與路由器B連接.

3.3 評 估

本文考慮了瓶頸鏈路傳播時延，瓶頸鏈路誤包率和瓶頸鏈路傳播帶寬這3個參數對流量控制算法的影響.主要分析在不同取值下，不同TCP版本獲得的鏈路吞吐量的對比.

圖6 友好性與公平性仿真拓撲圖Fig.6 Simulation topology of friendliness and fairness

首先，當以上3個重要參數采用表1的默認值時（即誤碼率為0.01，瓶頸鏈路帶寬為2Mbits／s，瓶頸鏈路傳播時延0.01ms），對不同TCP版本在2種經典數據流模型進行了簡單吞吐量對比，如表2.一個是經典的固定比特率（CBR）數據流模型；另一個是基于FTP應用產生的數據流.

表2 2種數據流模型吞吐量對比Tab.2 Throughput of two flow model Mbits／s

由表2可以看出，在2種數據流模型下，TCPWC相比于傳統TCP版本有明顯的性能提升.同時對于TPCW也體現了一定的優越性.接下來，本文將FTP數據流模型為代表，對各TCP版本的性能進行詳細對比分析.

接著，觀察在無線鏈接的不同誤包率情況下，TCPW、TCPWC以及其他的TCP算法的性能.誤包率的范圍設置為0.000 1～0.1.如圖7所示，同其他TCP版本相比較，TCPW和TCPWC的吞吐量有了顯著的提高.這是因為通過估計帶寬來設置cwnd，提高了網絡利用率.由于CAPPROBE算法提高了帶寬估計的準確性，當誤包率大于0.001，TCPWC的吞吐量也比TCPW明顯提高.

同時，本文觀察瓶頸鏈路造成的傳播時延.假設誤包率固定為0.005，瓶頸鏈路傳播時延范圍設為0.1 ms到25ms.如圖8所示為不同傳播時延下網絡的吞吐量情況.結果表明，同舊版本的TCP比較，TCPW的性能有了很顯著的提高，同時TCPWC的性能比TCPW也有接近15%的性能提升.TCPWC更充分地利用了鏈路容量.

圖7 吞吐量vs.瓶頸鏈路誤包率Fig.7 Ave throughput vs.bottleneck link error rates

圖8 吞吐量vs.時延Fig.8 Ave throughput vs.bottleneck link delay

圖9則描述瓶頸鏈路在不同帶寬下獲得的吞吐量比較結果，其中帶寬范圍從1Mbits／s到4Mbits／s，且時延設置為固定值0.01ms，誤包率設置為固定值0.005.從圖9中可以看出與之前結果類似，TCPWC的性能表現最好，其次是TCPW，最后為傳統TCP算法.

同時，友好性和公平性也是評估TCP算法的重要指標.友好性指一種新的TCP擁塞控制算法，必須能夠和其他現存TCP擁塞控制算法共存，即對其他TCP擁塞算法的友好（因篇幅有限，本文以TCP Reno作為現存擁塞控制算法的代表）.公平性指對于采用相同TCP擁塞控制算法的多條連接，它們在穩定時應公平地使用帶寬.接下來，本文基于圖6的拓撲結構進行了友好性和公平性的仿真評估.

首先，設置路由器之間的瓶頸鏈路延時為25ms，誤包率為0.008，TCP連接共2個.

圖9 吞吐量vs.瓶頸鏈路帶寬Fig.9 Ave throughput vs.bottleneck bandwidth

圖10 吞吐量vs.Reno連接數量Fig.10 Ave throughput vs.the number of TCP Reno connections over lossy link

1）建立2條基于TCPWC的數據連接，模擬發送數據100s.可觀察到各連接平均吞吐量為0.97 Mbits／s，最大吞吐量比平均值高出約16%，而最小值比平均值低約18%.與上一個實驗相比，公平性略有下降.

2）保持TCPWC和TCP Reno的連接總數為2，模擬發送數據100s.結果如圖10所示，橫坐標表示TCP Reno的連接條數，縱坐標表示基于相同算法的各連接的平均吞吐量.TCPWC可以與TCP Reno共存，但性能更優越，可獲得高出其約20%的平均吞吐量.

綜上分析，TCPWC具有較好的傳輸速度，良好的友好性和公平性.雖然隨著網絡擁塞程度增加，公平性有所下降，但不會過度搶占其他連接資源.

4 結 論

本文將CAPPROBE帶寬估計算法應用于TCPW，提出了一種基于CAPPROBE帶寬估計算法的網絡擁塞控制算法TCPWC.通過設計ACK雙包機制，本文使用CAPPROBE算法獲得更精確的瓶頸鏈路帶寬估計值，從而優化擁塞控制參數的設置，避免無線鏈路高誤包率的影響.本文在NS3中實現了TCPWC，并與TCPW、傳統的TCP機制NewReno、Reno和Tahoe做了性能比較.從實驗結果可以看出，TCPWC的吞吐量有了明顯的改進，并同時表現出友好性和公平性.考慮到真實網絡環境的復雜性和不可預測性，仿真的結果帶有一定局限性.例如，還未深入分析TCPWC對RTT過大的TCP連接的性能影響（經過同步衛星鏈路的TCP連接，其RTT通常大于0.5s）.因此，將來的工作是搭建網絡測試平臺，通過更細致全面的通信實驗，進一步驗證TCPWC的性能.

［1］Allman M，Paxson V，Stevens W.TCP congestion control，IETF RFC 2581［EB／OL］.［1999－04］.http：∥www.tools.ietf.org／rfc／rfc2581.txt.

［2］Akyildiz I F，Morabito G，Palazzo S.TCP－Peach：a new congestion control scheme for satellite IP networks［J］.IEEE／ACM Transactions on Networking，2001，9（3）：307－321.

［3］Fu C P，Liew S C.TCP veno：TCP enhancement for transmission over wireless access networks［J］.IEEE Journal on Selected Areas in Communications，2003，21（2）：216－228.

［4］Mascolo S，Casetti C，Gerla M，et al.TCP westwood：bandwidth estimation for enhanced transport over wireless links［C］∥Proceedings of the 7th Annual International Conference on Mobile Computing and Networking.Rome，Italy：ACM，2001：287－297.

［5］Sheth A M，Patel K D，Chaudhari J P，et al.Analysis of TCP westwood NR protocol in congested and lossynetwork［J］.International Journal of Engineering and Technology，2013，4：477－482.

［6］Gangadhar S，Nguyen T A N，Umapathi G，et al.TCP Westwood（＋）Protocol Implementation in ns－3［C］∥Proceedings of the 6th International ICST Conference on Simulation Tools and Techniques.Cannes，France：ICST，2013：167－175.

［7］Kapoor R，Chen L J，Li L，et al.CapProbe：a simple andaccurate capacity estimation technique［C］∥Proceedings of the 2004Conference on Applications，Technologies，Architectures，and Protocols for Computer Communications.Portland，Oregon，USA：ACM，2004：67－78.

［8］Lai K，Baker M.Measuring link bandwidth using a deterministic model of packet delay［C］∥Proceedings of the 2000Conference on Applications，Technologies，Architectures，and Protocols for Computer Communications.Stockholm，Sweden：ACM，2000：283－294.

［9］Downey A B.Using pathchar to estimate internet link characteristics［C］∥Proceedings of the 1999Conference on Applications，Technologies，Architectures，and Protocols for Computer Communications.Cambridge，Massachusetts，USA：ACM，1999：241－250.

［10］Astrom K J，Wittenmark B."Computer controlled systems"theory and design［M］.New Jersey，USA：Prentice Hall，1997.

［11］Lan K，Sha N.A CMT congestion window updates mechanism based on TCP westwood［C］∥Proceedings of the Mechatronic Science，Electric Engineering and Computer（MEC）2011International Conference on.Jilin，China：IEEE，2011：2119－2122.

［12］趙文波，孫小科，馬草川.基于非線性窗口增長的TCP Westwood改進算法［J］.計算機應用，2011，31（9）：2344－2348.

［13］Le T A，Hong C S，Huh E N.Coordinated TCP westwood congestion control for multiple paths over wireless networks［C］∥Proceedings of the International Conference on Information Network 2012.Bali，Indonesia：IEEE，2012：92－96.

［14］Hagag S，El－Sayed A.Enhanced TCP westwood congestion avoidance mechanism（TCP westwood new）［J］.International Journal of Computer Application，2012，45（5）：21－29.

［15］Goldoni E，Rossi G，Torelli A A.A new method for available bandwidth estimation［C］∥Proceedings of the 4th International Conference on Internet Monitoring and Protection.Mestre，Italy：IEEE，2009：130－136.

［16］Jain M，Dovrolis C.Pathload：a measurement tool for endtoend available bandwidth［C］∥Proceedings of the Passive and Active Measurements （PAM）Workshop.Colorado，USA：Citeseer，2002：14－25.

［17］Li M，Mark C，Rober K.WBest：a bandwidth estimation tool for IEEE 802.11wirelessnetworks［C］∥Proceedings of the 33rd IEEE Conference on Local Computer Networks（LCN）.Montreal，Canada：IEEE，2008：374－381.

［18］Sarr C，Chaudet C，Chelius G.Bandwidth estimation for IEEE 802.11－based ad hoc networks［J］.Mobile Computing，IEEE Transactions on，2008，7（10）：1228－1241.

［19］Keshav S.The packet pair flow control protocol［M］.Berkeley：International Computer Science Institute，1991.

［20］Strauss J，Katabi D，Kashoek F.A measurement study of available bandwidth estimation tools［C］∥Proceedings of the 3rd ACM SIGCOMM Conference on Internet Mesurement.Miami，USA：ACM，2003：39－44.