茹新宇 劉 淵

1(江蘇聯(lián)合職業(yè)技術(shù)學(xué)院無錫交通分院 江蘇 無錫 214151) 2(江南大學(xué)數(shù)字媒體學(xué)院 江蘇 無錫 214122)

?

一種基于正態(tài)分布函數(shù)的新TCP擁塞控制機(jī)制

茹新宇1劉 淵2

1(江蘇聯(lián)合職業(yè)技術(shù)學(xué)院無錫交通分院 江蘇 無錫 214151)2(江南大學(xué)數(shù)字媒體學(xué)院 江蘇 無錫 214122)

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

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

0 引 言

隨著移動互聯(lián)網(wǎng)時代到來，網(wǎng)絡(luò)結(jié)構(gòu)類型深入發(fā)展，呈現(xiàn)形式日益多樣，傳統(tǒng)的TCP擁塞控制機(jī)制已略顯不足，表現(xiàn)為原AIMD算法易導(dǎo)致帶寬利用率低下及窗口波動較大等問題[1]。而且根據(jù)接收端反饋信息判斷擁塞狀況再采取相應(yīng)策略的方式具有一定延遲，常使發(fā)送端不能準(zhǔn)確及時地判斷擁塞情形，而采用不合理的處理方式，反而加劇了網(wǎng)絡(luò)的不穩(wěn)定表現(xiàn)。

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

1 現(xiàn)有的擁塞控制機(jī)制

圖1 現(xiàn)有的TCP擁塞控制機(jī)制

目前的TCP擁塞控制默認(rèn)丟包是由擁塞引起。為保證Internet穩(wěn)定性，現(xiàn)機(jī)制采用了加性增加乘性減小的AIMD算法調(diào)節(jié)擁塞窗口大小，使數(shù)據(jù)發(fā)送率被動適應(yīng)網(wǎng)絡(luò)擁塞狀況，其可分以下四個階段[4]：

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

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

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

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

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

2 基于正態(tài)分布函數(shù)的新TCP擁塞控制機(jī)制

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

2.1 基本思路

鑒于不同負(fù)載下RTT樣本可被近似修正為正態(tài)分布[3]，新機(jī)制設(shè)想以RTT值作為網(wǎng)絡(luò)擁塞狀態(tài)的反饋信號，用當(dāng)前窗口的RTT樣本均值預(yù)估即將發(fā)生的擁塞狀況，從而采取相應(yīng)措施，主動避免擁塞的產(chǎn)生、加劇甚至惡化。其基本思路為：

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

(2) 進(jìn)入擁塞避免后，由返回RTT值構(gòu)建正態(tài)函數(shù)關(guān)系式后代入新算法。并據(jù)此謹(jǐn)慎地嘗試性增大擁塞窗口值，使負(fù)載穩(wěn)定在理想?yún)^(qū)間，提高系統(tǒng)吞吐量。

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

2.2 具體實現(xiàn)

1) 采樣規(guī)則

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

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

(1)

(2)

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

注意：

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

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

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

2) 狀態(tài)算法

RTT樣本值隨擁塞程度不同而變化，正態(tài)分布函數(shù)適時調(diào)整參數(shù)μ、σ和x，從而實現(xiàn)動態(tài)擁塞控制。有三種情況需要重新“學(xué)習(xí)”并構(gòu)建分布曲線：

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

過載狀態(tài)：RTT值呈增大趨勢。條件為一個窗口最后連續(xù)7個數(shù)據(jù)包的RTT值越來越大。

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

以上三種狀態(tài)間，不同算法調(diào)控觸發(fā)值的變更類似于滑動窗口形式。輕載時調(diào)控可滯后些，區(qū)間值作適當(dāng)右移。擁塞時應(yīng)超前些，區(qū)間值可適當(dāng)左移。

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

算法A

(3)

算法B

(4)

(5)

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

表1 不同狀態(tài)下，x所處范圍對應(yīng)算法選擇(不同狀態(tài)下，不同算法調(diào)控觸發(fā)值)示意圖

3) 機(jī)制流程

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

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

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

依次重復(fù)上述過程，即可實現(xiàn)后續(xù)擁塞窗口值的自動更新。

2.3 算法分析

主要分析上述表1內(nèi)不同狀態(tài)所對應(yīng)算法的調(diào)控觸發(fā)值的選取依據(jù)，及論證算法公式中積分區(qū)間近似值選用的可行性。設(shè)正態(tài)分布概率密度函數(shù)為[8]：

(6)

1) 首先分析函數(shù)的一階導(dǎo)數(shù)

由式(6)得：

2) 其次研究函數(shù)的二階導(dǎo)數(shù)

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

3) 最后考慮函數(shù)的3σ準(zhǔn)則

當(dāng)RTT服從正態(tài)分布時，根據(jù)RTT～N(μ,σ2)性質(zhì)，總體N在以下區(qū)間取值的概率查表可知：

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σ]內(nèi)是大概率事件，其均值x情況亦如此，故選用μ±3σ作為新算法的積分區(qū)間是可行的，且具有簡化運算的積極意義。因此我們重點研究該區(qū)間內(nèi)樣本均值x的積分計算及樣本個體RTT的采樣分布情況。

根據(jù)正態(tài)分布函數(shù)特點，當(dāng)前窗口的RTT樣本值在[μ-3σ,μ+3σ]范圍內(nèi)隨機(jī)分布時，說明此時網(wǎng)絡(luò)處于一相對穩(wěn)定環(huán)境，窗口只需在不同算法間作微調(diào)；反之，當(dāng)RTT值在該范圍內(nèi)出現(xiàn)某種規(guī)律性變化時(滿足某種狀態(tài)轉(zhuǎn)移條件)，說明當(dāng)前網(wǎng)絡(luò)正在發(fā)生某種系統(tǒng)性變化，應(yīng)快速采取相應(yīng)策略對窗口進(jìn)行不同狀態(tài)間的較大調(diào)整。依據(jù)此理，為使負(fù)載穩(wěn)定在理想?yún)^(qū)間，以提高系統(tǒng)吞吐量，表1部分算法選用μ±3σ作為調(diào)控觸發(fā)值是相當(dāng)合理的。

3 仿真與驗證

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

圖2 網(wǎng)絡(luò)仿真拓?fù)浣Y(jié)構(gòu)

圖3 不同機(jī)制下，擁塞窗口值比較

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

圖4 不同機(jī)制下，各時間段的丟包數(shù)比較

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

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

圖5 不同機(jī)制下，系統(tǒng)吞吐量比較

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

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

4 結(jié) 語

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

[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的端到端網(wǎng)絡(luò)擁塞控制研究[D].天津大學(xué),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ī)制及性能分析[J].現(xiàn)代電子技術(shù),2006,29(18):86-88.

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

[6] 高大偉.基于統(tǒng)計過程控制的傳輸控制協(xié)議TCP SPC[D].天津大學(xué),2008.

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

[8] 王康.利用導(dǎo)數(shù)研究正態(tài)分布的概率密度函數(shù)性質(zhì)[J].河南教育學(xué)院學(xué)報(自然科學(xué)版),2012,21(2):31-32.

[9] 張登銀,張保峰.新型網(wǎng)絡(luò)模擬器NS-3研究[J].計算機(jī)技術(shù)與發(fā)展,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。國家自然科學(xué)基金項目(61602213)；江蘇省自然科學(xué)基金項目(BK20151131)。茹新宇，講師，主研領(lǐng)域：網(wǎng)絡(luò)擁塞控制，信息安全。劉淵，教授。

TP393

A

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