天天看点

拥塞控制-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

继续阅读