天天看點

擁塞控制-DAIMD

1.擁塞控制

為了更有效率地利用網絡帶寬,通過限制擁塞擴散和持續時間來減輕擁塞的一組操作。

擁塞現象是指到達通信子網中某一部分的分組數量過多,使得該部分網絡來不及處理,

以緻引起這部分乃至整個網絡性能下降的現象, 嚴重時甚至會導緻網絡通信業務陷入

停頓即出現死鎖現象。

造成擁塞的原因:

    1)多條流入線路有分組到達,并需要同一輸出線路。此時,如果路由器沒有足夠的

    記憶體來存放所有這些分組,那麼有的分組就會丢失。

    2)路由器處理器的處理能力低,以至于難以完成必要的處理工作,如緩沖區排隊、

    更新路由表等。

2.擁塞算法

UDT 的算法—DAIMD

AIMD : Additive Increase and Multiplicative Decrease

DAIMD: Decrease AIMD

我們考慮下面這個AIMD速率控制算法的原型:

在每一次速率控制的間隔,如果沒有從接收端得到負回報(丢包,漸增的延遲等),而是

得到正回報(ACK),那麼發包的速率(x)将增加α(x)。

擁塞控制-DAIMD

α(x)是一個非增的曲線,并且它随着x遞增趨近于0。

即:

擁塞控制-DAIMD

藍色 - a(x)曲線           

橙色 - TCP NewReno 版本的 AIMD 的算法曲線      

擁塞控制-DAIMD

上圖描述了 α(x)的曲線,并和 TCP NewReno 版本的 AIMD 的算法曲線做了圖示比較。

對于任意的負回報(NAK),發送速率按一個常量因子β(0 < β <1)進行降低:  

擁塞控制-DAIMD

注意,公式(1)以基于一個固定的控制間隔:RTT。它不同于 TCP 的控制  (每一個應答觸

發一次遞增)。通過修改α(x),可以确定一個在UDT中使用的速率控制算法類:   DAIMD算

法(AIMDwith decreasing increases),即加性的參數是遞減的。除了穩定性和公平性函數

α(x)在x=0值附近,值極大用以提高效率;并且能快速地降低,用以降低震蕩。

UDT 采取該高效的方法,并且指定一個分段的與鍊路容量相關的 α(x)。  UDT 固定的速率

控制間隔是 SYN(或稱為同步時間間隔),并且 SYN 值是 0.01 秒。UDT 的速率控制是一個

通過指定 α(x)的特别的 DAIMD 算法:

擁塞控制-DAIMD

在公式(3)裡:

x 的機關是:包數/秒。

L 是鍊路容量,并且機關是:bits/秒。

S 是 UDT 包大小(指 IP 的有效負荷),以位元組統計。

C(x)是一個機關轉換函數(C(x) = x * S * 8),将目前的發送速率x從包數/秒轉換成bits/秒。

τ 是一個協定參數,在目前協定規範裡指定的值是 9.因子1500 / S用來平衡不同包大小的流

産生的影響。UDT将一個标準包大小處理為1500位元組。

當第一個NAK包被接收或者流量視窗到達最大大小時,  上面描述的UDT擁塞控制就變的不

适用。UDT使用了慢啟動階段的擁塞控制。在該階段裡,包之間的時間保持為0。初始的流

量視窗大小是2,并且每觸發一次ACK事件時,視窗流量大小被設定為應答包的數量。慢啟

動隻發生在UDT建立連接配接後的初期。一旦進入上述的擁塞控制方法(DAIMD)階段,慢啟動将

不會再出現。

擁塞控制-DAIMD

上圖顯示了,單一的 UDT 流如何随時間,改變其發送速率。該情形的前提是:

網絡系統裡既沒有非擁塞控制的丢包,也沒有其它的流。否則将會出現發送速率的震蕩。

上圖裡,在每一個階段 k(k = 0,1,2…),當 x 在 0 附近或者增長和降低互相抵消時,它

可以達到平衡。發送速率在不同階段 k,近似的平衡值:

擁塞控制-DAIMD

變量 p 是丢包速率。

變量 e 是一個值,滿足:

擁塞控制-DAIMD

許多 UDT 的特性可以通過公式(4)進一步推演。一個有趣的例子是 TCP 的友好性。通過和

簡單版本的 TCP 吞吐量的模型[5]做比較(4),可以得到一個充分條件,用以保證 UDT 不如 

TCP 那般激進:

擁塞控制-DAIMD

繼續閱讀