一種基于正態分布函數的新TCP擁塞控制機制

茹新宇 劉 淵

1(江蘇聯合職業技術學院無錫交通分院 江蘇 無錫 214151) 2(江南大學數字媒體學院 江蘇 無錫 214122)

?

一種基于正態分布函數的新TCP擁塞控制機制

茹新宇1劉 淵2

1(江蘇聯合職業技術學院無錫交通分院 江蘇 無錫 214151)2(江南大學數字媒體學院 江蘇 無錫 214122)

目前，擁塞控制已成為確保互聯網穩定性與魯棒性的極其重要因素。然而，目前的TCP擁塞控制機制使用AIMD(Additive Increase Multipli-cative Decrease)算法，其加性增加乘性減小的合理性與穩定性存在著現實問題。為此，我們改進了原有的AIMD算法，提供了一種基于正態分布函數的新TCP擁塞控制機制。并把整個擁塞避免、快速重傳與恢復階段分為輕載、過載和擁塞三種狀態，根據調控觸發值，區別選用不同算法實現。最后還從數學角度對新機制及其算法的合理性和可行性進行了分析與證明。同時，NS3的仿真結果顯示，新的TCP擁塞控制機制可明顯降低丟包率、平緩突發流量沖擊，并可增加帶寬的有效利用率、提高系統吞吐量。

加性增加乘性減小 擁塞避免 擁塞窗口 閾值 往返延遲時間 正態分布 NS3仿真

0 引 言

隨著移動互聯網時代到來，網絡結構類型深入發展，呈現形式日益多樣，傳統的TCP擁塞控制機制已略顯不足，表現為原AIMD算法易導致帶寬利用率低下及窗口波動較大等問題[1]。而且根據接收端反饋信息判斷擁塞狀況再采取相應策略的方式具有一定延遲，常使發送端不能準確及時地判斷擁塞情形，而采用不合理的處理方式，反而加劇了網絡的不穩定表現。

由文獻[2]可知，無論有線還是無線網絡，往返延遲時間RTT的變化能較客觀地反應當前網絡負載狀況，其變化適合作為擁塞反饋信號。本文基于RTT正態分布統計模型[3]，依據其采樣值變化特點判斷負載趨勢。運用正態分布概率函數，在擁塞避免、快速重傳與恢復階段動態調整擁塞窗口值，達到改進TCP擁塞控制效果。

1 現有的擁塞控制機制

圖1 現有的TCP擁塞控制機制

目前的TCP擁塞控制默認丟包是由擁塞引起。為保證Internet穩定性，現機制采用了加性增加乘性減小的AIMD算法調節擁塞窗口大小，使數據發送率被動適應網絡擁塞狀況，其可分以下四個階段[4]：

(1) 初始擁塞窗口cwnd為1個分組，且在每次收到所有返回應答報文ACK后cwnd加倍；

(2) 若cwnd增至預設的門限閾值ssthresh，則進入擁塞避免階段，收到所有ACK后cwnd加1；

(3) 當發送端收到三組重復ACK(TDACK)，則認為分組已丟失，執行快速重傳與恢復算法，ssthresh降為當前cwnd一半，且收到所有ACK后cwnd加1；

(4) 當發送端等待ACK時間超過重傳計時器RTO(Retransmission Time Out)的預設值，則判定分組已丟失，執行超時重傳。將cwnd重置為1，且把RTO加倍。若發送端等待2T后仍沒收到ACK，則繼續將RTO加倍，直到64T后RTO穩定于此。若收到ACK，則cwnd再次進入慢啟動階段。

這種基于窗口的端到端擁塞控制機制對于像Web、FTP或E-mail等無嚴格時間限制的應用具有較好適應性。但在如今高帶寬低延遲的網絡環境中，它已被證明效率低下，鏈路可能在相當長一段時間內得不到充分利用[5]。速率增長過慢減小過快是其主要問題，據此我們提出一種基于正態分布函數的新TCP擁塞控制機制，以期取得較好效果。

2 基于正態分布函數的新TCP擁塞控制機制

傳統的AIMD算法過于“激進”，易引起擁塞窗口的劇烈抖動。為減小速率震蕩，使窗口變化趨于平緩，以適應多媒體等非TCP流的傳輸要求，需要對機制作一些改進，提高其擁塞控制性能。

2.1 基本思路

鑒于不同負載下RTT樣本可被近似修正為正態分布[3]，新機制設想以RTT值作為網絡擁塞狀態的反饋信號，用當前窗口的RTT樣本均值預估即將發生的擁塞狀況，從而采取相應措施，主動避免擁塞的產生、加劇甚至惡化。其基本思路為：

(1) 慢啟動沿用cwnd(x)=2x，x∈[0,log2ssthresh]。

(2) 進入擁塞避免后，由返回RTT值構建正態函數關系式后代入新算法。并據此謹慎地嘗試性增大擁塞窗口值，使負載穩定在理想區間，提高系統吞吐量。

(3) 若收到TDACK，則快速重傳丟包，后繼續2)。

2.2 具體實現

1) 采樣規則

當進入擁塞避免階段后，取樣本空間(0,+∞)，迅速對RTT采樣，利用隨機函數Rand(RTT)產生樣本值，并用一維數組RTT[N]記錄。其中N為采樣個數，RTTi表示第i個RTT采樣值。樣本容量N取13可兼顧算法“靈敏度”與合理性[6]，具體實現細節如下：

(1) 系統開辟兩組15個單元的數組。其中前13個存放前后兩次發送窗口返回RTT的隨機采樣值，后兩個存放13個RTT的樣本均值μ和標準差σ(計算公式見式(1)、式(2))。前一窗口的采樣值和計算值μ1、σ1均存放在數組1中，用以作出正態分布密度函數曲線(為表述清晰，本文令μ1=μ，σ1=σ，以下不再特意說明)。而當前窗口的采樣值、計算值μ2、σ2則置于數組2內，其中的均值μ2作為計算正態分布函數時的積分自變量(本文設μ2=x，以下皆類同)。

(1)

(2)

(2) 依據流量的自相似性[7]，另需開辟一7個單元的數組3用以保存當前窗口內最后7個連續數據包的RTT值，從而預測下一窗口滿足何種狀態？以此作為算法轉移的觸發條件。此數組內容直接影響狀態選擇，決定不同算法區間。

注意：

① 首次進入擁塞避免階段時，應從慢啟動末期提前采樣好兩個窗口的數組值，計算參數μ、σ和x。并根據數組3判斷狀態(如不滿足任何條件，則系統默認輕載)，為預估首個擁塞避免窗口值所用；

② 若進入擁塞避免時還不足13個RTT，則統計從慢啟動起始至今所有的RTT值；

③ 為保證樣本實時精確，需等前一窗口發送的所有數據包都得到確認后再開始采集新RTT樣本。由于超時重傳特殊性，規定不采集重傳數據包的RTT值。

2) 狀態算法

RTT樣本值隨擁塞程度不同而變化，正態分布函數適時調整參數μ、σ和x，從而實現動態擁塞控制。有三種情況需要重新“學習”并構建分布曲線：

輕載狀態：RTT值或其“抖動”呈減小趨勢。條件為一個窗口最后連續7個數據包的RTT值越來越小或其之間的差距越來越小。

過載狀態：RTT值呈增大趨勢。條件為一個窗口最后連續7個數據包的RTT值越來越大。

擁塞狀態：RTT值的“抖動”呈增大趨勢。條件為一個窗口最后連續7個數據包的RTT值之間的差距越來越大。

以上三種狀態間，不同算法調控觸發值的變更類似于滑動窗口形式。輕載時調控可滯后些，區間值作適當右移。擁塞時應超前些，區間值可適當左移。

根據數組3值判斷狀態，后根據數組2中RTT樣本均值x所處范圍選用對應算法，預估擁塞窗口值(詳情見表1，其中μ、σ，μ′、σ′和μ″、σ″分別為網絡輕載、過載和擁塞狀態下的參數值)。若恰巧13個樣本值均相等，此時標準差σ=0，則函數積分值F(x)置零，新算法繼續執行。

算法A

(3)

算法B

(4)

(5)

φμ,σ(x)為正態分布密度函數，圖像曲線由參數μ和σ共同確定。由于從cwnd≥ssthresh后開始的擁塞避免階段算法較謹慎，其增大的窗口值遠不及慢啟動階段的增量，所以取Φ(x)≤1是合理的。

表1 不同狀態下，x所處范圍對應算法選擇(不同狀態下，不同算法調控觸發值)示意圖

3) 機制流程

(1) 進入擁塞避免階段后，先根據數組1的值繪出正態分布密度曲線φμ,σ(x)，并依據樣本值算出μ±3σ作為上式的積分區間。而數組2中樣本均值x則作為正態分布函數的自變量，求出F(x)值。

(2) 由數組3判斷下一窗口狀態。在不同狀態下，依據當前窗口樣本均值x所處范圍選擇對應算法執行，從而預估出下一擁塞窗口值(如不滿足任何狀態條件，則沿用當前窗口狀態)。每次窗口調整都必須更新表1中對應狀態行的參數μ和σ(包括μ′、σ′和μ″、σ″)值。

(3) 每次擁塞窗口調整后都需用數組2值替代數組1值。并隨著新窗口依次返回的新RTT值，逐步更新數組2內容，后計算新的樣本均值μ2=x和標準差σ2。

依次重復上述過程，即可實現后續擁塞窗口值的自動更新。

2.3 算法分析

主要分析上述表1內不同狀態所對應算法的調控觸發值的選取依據，及論證算法公式中積分區間近似值選用的可行性。設正態分布概率密度函數為[8]：

(6)

1) 首先分析函數的一階導數

由式(6)得：

2) 其次研究函數的二階導數

令φ″(x)=0，得x=μ+σ或x=μ-σ，顯然當x<μ-σ或x>μ+σ時，φ″(x)>0，此時函數φ(x)為凸函數；而當μ-σ

3) 最后考慮函數的3σ準則

當RTT服從正態分布時，根據RTT～N(μ,σ2)性質，總體N在以下區間取值的概率查表可知：

F(μ+3σ)=Φ(3)=0.9987

F(μ-3σ)=Φ(-3)=1-Φ(3)=0.001 3

F(μ-3σ，μ+3σ)=F(μ+3σ)-F(μ-3σ)=

Φ(3)-Φ(-3)=0.998 7-0.001 3=0.997 4

由此可知，RTT值落在[μ-3σ,μ+3σ]內是大概率事件，其均值x情況亦如此，故選用μ±3σ作為新算法的積分區間是可行的，且具有簡化運算的積極意義。因此我們重點研究該區間內樣本均值x的積分計算及樣本個體RTT的采樣分布情況。

根據正態分布函數特點，當前窗口的RTT樣本值在[μ-3σ,μ+3σ]范圍內隨機分布時，說明此時網絡處于一相對穩定環境，窗口只需在不同算法間作微調；反之，當RTT值在該范圍內出現某種規律性變化時(滿足某種狀態轉移條件)，說明當前網絡正在發生某種系統性變化，應快速采取相應策略對窗口進行不同狀態間的較大調整。依據此理，為使負載穩定在理想區間，以提高系統吞吐量，表1部分算法選用μ±3σ作為調控觸發值是相當合理的。

3 仿真與驗證

為驗證新機制的有效性，本文在Ubuntu16.04系統+NS3.24[9]仿真軟件下搭建了一個近似于真實網絡環境的性能高度可控可重用的模擬平臺，對圖2所示的拓撲結構進行場景測試。其中S1至Sn、D1至Dn分別為發送端和接收端，它們與各自的路由帶寬均為5 Mbit/s，延時2 ms，R1、R2間瓶頸鏈路帶寬設1 Mbit/s，延時40 ms，門限閾值取原算法推薦值64 KBytes。為簡化起見，設中間節點可緩存50個分組，發送端以每個分組1 KBytes大小連續發送20 Mbytes的FTP單向數據流，路由隊列采用RED主動隊列管理算法。我們對基于正態分布函數的新TCP擁塞控制機制(命名為’New Cwnd’)與原New Reno及Tahoe兩機制進行了不同時間段的多組擁塞窗口、丟包率、吞吐量及帶寬的對比實驗，具體如圖3所示。

圖2 網絡仿真拓撲結構

圖3 不同機制下，擁塞窗口值比較

由于從擁塞避免階段開始的新機制，其算法主動根據歷史及當前窗口的經驗值，通過計算正態分布概率函數，提前預測并動態調整即將到來的擁塞窗口值，及時作出響應。較有效地緩解了原AIMD算法的窗口抖動幅度，提高了整個控制過程的擁塞窗口平均值(如圖3所示)，有效地平緩了突發流量沖擊。

圖4 不同機制下，各時間段的丟包數比較

隨著發送端接入鏈路的連接數不斷攀升，新機制有效降低了窗口發送速率抖動，使得“適當”的流量可平緩進入網絡，從而避免了不必要分組丟失及“盲目”重傳。由圖4可見，其分組丟失率確實降低明顯，而原有的兩種機制的丟包率卻基本無顯著差別。

從圖5可看出，隨著時間推移，原來的兩機制其吞吐量均有所起伏，但波動不大。而新機制吞吐量波形較平穩，在采樣時間段內平均值基本不變，整體效果略優于原機制，但相差不明顯。因此在算法流量公平性上，新舊機制基本能友好相處，共享帶寬資源。并由于擁塞窗口的平均值增大，超時重傳將會減少，也間接提高了鏈路帶寬的有效利用率，這點從表2可得到證實。可見新機制除了有助于系統吞吐量的提高與穩定外還能充分利用帶寬資源。

圖5 不同機制下，系統吞吐量比較

表2 不同機制下，鏈路帶寬大小比較

綜上所述，新機制在擁塞窗口平均值、丟包率以及帶寬資源利用率等方面均優于原有機制，而系統吞吐量也有一定程度的改善，并且基本不影響流量的公平性。

4 結 語

本文首先分析了目前基于窗口的TCP擁塞控制機制及其AIMD算法對網絡性能的影響。然后利用不同負載時RTT近似服從正態分布的特性，從主動預判層面提出了一種基于正態分布函數的新TCP擁塞控制機制。系統根據RTT樣本參數預估網絡可能的負載狀態，調用正態分布函數，動態調整下一擁塞窗口值。理論分析證明該機制及其算法具有合理性、可行性。最后，NS3仿真實驗也表明該機制能有效穩定地增加擁塞窗口值、減少丟包率、提高帶寬的實際利用率。并在基本不影響流量公平性的前提下改善系統吞吐量，實現高效穩定的擁塞避免過程。但目前該機制的算法設置過于傾向TCP流，而視頻流媒體等UDP流卻并不遵守擁塞控制機制，對網絡資源具有權限更高的“掠奪”性。針對此不足之處，下一步我們將結合IP層的主動隊列管理算法，努力實現TCP/IP層同步協作化擁塞控制，使TCP與UDP流能公平合理地共享帶寬資源，以期進一步提高網絡性能。

[1] Chiu D M,Jain R.Analysis of the Increase and Decrease Algorithms for Congestion Avoidance in Computer Networks[J].Computer Networks & Isdn Systems,1989,17(1):1-14.

[2] 趙偉豐.基于RTT的端到端網絡擁塞控制研究[D].天津大學,2014.

[3] Elteto T,Molnar S.On the Distribution of Round-trip Delays in TCP/IP Networks[C]//Proceedings of the 24th Annual IEEE Conference on Local Computer Networks,1999.

[4] 廖敬萍.TCP擁塞控制機制及性能分析[J].現代電子技術,2006,29(18):86-88.

[5] Floyd S.HighSpeed TCP for Large Congestion Windows[G].Rfc,2003.

[6] 高大偉.基于統計過程控制的傳輸控制協議TCP SPC[D].天津大學,2008.

[7] 張賓,楊家海,吳建平.Internet流量模型分析與評述[J].軟件學報,2011,22(1):115-131.

[8] 王康.利用導數研究正態分布的概率密度函數性質[J].河南教育學院學報(自然科學版),2012,21(2):31-32.

[9] 張登銀,張保峰.新型網絡模擬器NS-3研究[J].計算機技術與發展,2009,19(11):80-84.

[10] Morris R.Scalable TCP Congestion Control[J].Proceedings-IEEE INFOCOM,2000,3(5):1176-1183.

[11] Padhye J,Firoiu V,Towsley D,et al.Modeling TCP throughput: a simple model and its empirical validation[C]//ACM SIGCOMM’98 Conference on Applications,Technologies,Architectures,and Protocols for Computer Communication.ACM,1998:303-314.

ANEWTCPCONGESTIONCONTROLMECHANISMBASEDONNORMALDISTRIBUTEDFUNCTION

Ru Xinyu1Liu Yuan2
1(WuxiTransportationCollege,JiangsuUnionTechnicalInstitute,Wuxi214151,Jiangsu,China)2(SchoolofDigitalMedia,JiangnanUniversity,Wuxi214122,Jiangsu,China)

So far the congestion control has become the most important factor to ensure the stability and robustness of the Internet. However, the AIMD algorithm used in TCP congestion control mechanism currently is unstable and insufficient. There exist practical problems in the rationality and stability of the additive increase and the multiplicative reduction. To solve these problems, we provide a new TCP congestion control mechanism, based on normal distributed function, instead of the AIMD algorithm. And the whole congestion avoidance, fast retransmit and recovery phase are divided into three states: light load, overload and congestion, according to the regulation of the difference between the trigger value use different algorithms. Finally, the rationality and feasibility of the new algorithm have been verified by using mathematical analysis. Furthermore, the simulation results from NS3 demonstrate that the new TCP congestion control mechanism can obviously reduce packet losses and the impact of network burst transmission, improve the bandwidth utilization ratio and the network throughput.

AIMD Congestion avoidance Congestion window Threshold RTT Normal distribution NS3 simulation

2016-11-16。國家自然科學基金項目(61602213)；江蘇省自然科學基金項目(BK20151131)。茹新宇，講師，主研領域：網絡擁塞控制，信息安全。劉淵，教授。

TP393

A

10.3969/j.issn.1000-386x.2017.08.044