TCP协议拥塞控制算法（Reno、HSTCP、BIC、Vegas、Westwood）

TCP协议拥塞控制算法（Reno、HSTCP、BIC、Vegas、Westwood）

一、TCP拥塞控制的研究框架

二、现有TCP拥塞控制的算法（Reno、HSTCP、Vegas、Westwood）

三、参考文献

一、TCP拥塞控制的研究框架

注：

l  基于丢包反馈：通过ACK所带回来的丢包信息来调整源端的拥塞窗口。Reno等是针对ACK返回的丢包信息改进传统TCP协议。今年来，随着网络带宽的提高、传输延时的增大，针对提高TCP带宽利用率这点，出现HSTCP、BIC-TCP、STCP协议。

l  基于路径延时反馈：RTT相对于丢包信息反应更灵敏，更能及时反映出一般网络的拥塞情况。适用于小缓存的中间节点，效率较理想。但是对于路由器经常缓存数据促使RTT延长调节拥塞窗口，实际上没有发生拥塞情况。

l  基于显示拥塞反馈：典型的ECN利用中间节点自己检测本身的拥塞状态，如路由器的反馈状态，直接反馈给TCP源端，以此调节源端的窗口值和发送速率。

二、  重点TCP拓展算法

1.      基于丢包反馈的TCP协议（Tahoe、Reno、New Reno、SACK）

1988年 V.Jacobson提出了，慢启动和拥塞避免的算法。后期对TCP传输协议算法不断优化改进。目前使用最广泛的TCP Reno拥塞控制主要分为4个阶段：

 

1）慢启动阶段：  cwnd呈现指数增长趋势

2）拥塞避免阶段：cwmd>ssthresh  呈现线性增长趋势

3）快重传阶段：发送方只要一连接收到三个重复确认就应该立即重传对方尚未的报文段，而不必等到重传计时器超时后发送。由3个重复应答判断有包丢失，重新发送丢包的信息。

4）快速恢复阶段：主要决定于收到的重复应答数据的初始门限值（一般为3）

与慢启动不同，Reno的发送方用额外到达的应答为后续包定时。

发送方窗口的上限值=min【接收方窗口，拥塞窗口】

整个reno过程见下图：

 

 

 

 

2.      基于延时反馈的TCP协议（Vegas、Westwood）

经典的Vegas算法的基本思路：RTT增加，拥塞窗口减小；RTT减少，拥塞窗口变大。

1）重传机制：Vegas采用更精确的RTT估计值在以下两种情形下决定是否重发：

- 当接受到重复ACK时，Vegas检查目前时间和记录的时间标签之差是否比超时值大，如果是，则立刻重发数据包，不必等第三个重复ACK。当接受重传数据包应答后，Vegas以3/4而不是1/2因子降低拥塞窗口。

- 当接受到非重复的ACK时，如果它是重发之后的第一或是第二个确认，Vegas将再次检测数据发送时间间隔是否查过超时值。如果是，则重发。

2）拥塞避免机制：Vegas通过比较实际吞吐量和期望吞吐量来调节拥塞窗口的大小。

期望吞吐量：Expected=cwmd/BaseRTT

实际吞吐量：Actual=cwnd/RTT

计算差值：diff=（Expected-Actual）*BaseRTT

BaseRTT是所有观测来回响应时间的最小值，一般是建立连接后所发的第一个数据包的RTT。cwnd是目前的拥塞窗口的大小。

定义阈值a、b，当diff拥塞窗口增大，+1；当diff>b，拥塞窗口缩小，-1；当a<=diff<=b,拥塞窗口不变。通常a=1，b=3，意味着该连接至少保留一个包在队列中。

3）慢启动机制

由于一开始慢启动没有相关的传输数据和带宽速度等参数，需要设定慢启动门限。Vegas每经过两个RTT使cwnd拥塞窗口增加1倍。然后计算diff，当diff>a,则结束慢启动，转入拥塞避免。

在 Vegas慢启动中，每经过两个 RTT使 W增加 1倍。其中前一个 RTT内是与 TCP Reno相同的指数增长，即每收到一个 ACK包就将加 1，同时发送出两个数据包，可称为增长期；后一个 RTT内保持不变以观测 RTT的变化，可称为观测期。Vegas的慢启动过程就是由一个增长期和一个观测期周期往复，在每个观测期结束时，计算新的 RTT和diff的值，以此决定是继续下一个周期还是结束慢启动。

这种慢启动事实严重降低了传输速率。有些学者提出了自适应慢启动算法，或是慢启动阶段采用Reno方法。

Vegas-A:主要思路是a、b可以随着网络情况自动调节，初始值分别是1和3。

 

 

无线传输中的Westwood算法

基本思路：发送端利用检测到的ACK的到达率来估测可使用的带宽。

1）快速恢复机制：westwood算法重点放在出现报文丢失时候如何使用带宽估计值设定拥塞窗口的cwnd和ssthresh。在收到了三个重复的ACK或是超时，具体算法：

其中，PacketSize 指分组大小，BWE 为带宽估计值（单位时间分组数目*分组大小），RTTmin 是测得的最小 RTT 值，理想情况下等于中间队列长度为零时测得的值。TCPW 在Reno的基础上，通过测量估算出网络的可用带宽，对拥塞窗口cwnd进行适当调整，实现更快速的恢复。这种机制尤其在无线网中非常有效，与Reno相比吞吐量成倍提高。

2）慢启动阶段

慢启动和加性递增阶段仍然采用Reno的增加机制。慢启动处于带宽探测阶段，慢启动时处于带宽探测阶段，cwnd呈指数增长，ssthresh如果定的过高，容易导致较多的分组重传，而如果ssthresh 定的过低，则会导致过早进入线性递增，降低带宽利用率。

由于westwood无法区分网络拥塞丢包和无线随机错误丢包，尤其是无线网络时延抖动和随机错误丢包会被westwood误认为是网络拥塞，大大降低网络带宽利用。

Westwood-v算法：在慢启动阶段, 改进算法对慢启动阶段的网络状态根据队列中的报文长度N 进行区分, 并把窗口调整与估计带宽紧密结合起来, 根据网络状况, 采用不同的窗口增加策略, 避免了原有 TCPW 中拥塞窗口的盲目增加导致的分组拥塞丢失。此外, 对于分段, 不是采用固定值ssthresh/2, 而是根据当前的拥塞窗口与预测到的下一时刻的可用带宽的关系来分段, 具有动态自适应性。简而言之，慢启动时，采用vegas的方法计算diff与b比较，如果说明带宽还未充分利用，保持reno的指数和线性增加。当>b意味着带宽充分利用，但接近拥塞状态，如果还处于慢启动阶段，说明ssthresh偏大，需要更改，使TCP进入拥塞避免阶段。如果处于拥塞避免阶段，则降低窗口增加速率。

3、基于丢包反馈的高速带宽算法（HSTCP、STCP、BIC-TCP、CUBIC）

HSTCP与STCP的基本思想：当拥塞窗口>阈值时，窗口增加因子a（w）与减少因子b（w）成为窗口调节大小w的函数。

1.      HSTCP-high speed TCP高速传输协议 

适用于高速度、大时延网络  窗口快速增长，乘性缩小

该算法的根本思想是修改标准TCP协议的反应函数，受到窗口增长和丢包下降函数综合影响。重点介绍HSTCP的拥塞避免阶段窗口的调节算法。在拥塞避免阶段，接受一个ACK后，增长方式为：

线性增加  cwmd=cwmd+a（w）/cwmd

发生一次拥塞，拥塞窗口减少方式为：

乘性减少  cwnd=（1-b(w)）*cwnd

a（w）和b（w）的公式依次为：

当w>W_L

当w<=W_L时，a（w）=1  b（w）=0.5

 

2.      STCP- scable TCP

拥塞避免阶段受到ACK：cwmd=cwmd+a（w）

拥塞发生时：cwnd=（1-b(w)）*cwnd

a=0.01  b=0.125参数固定不变。

 

3.    BIC-TCP

BIC将拥塞控制视为一个搜索问题，具有良好的拓展性、友好性和公平性。但是丢失率<1e^-8其发送速率的增长不如HSTCP、STCP快。

BIC包括两部分：二分搜索增加（Binary Search increase）+加性增加（additive increase）

      二分搜索： TCP主动而非被动搜索一个处于丢包触发阈值的分组发送速率。

Wmin 快速恢复借宿后的拥塞窗口大小值

Wmax 快速恢复结束前的拥塞窗口大小值

首先设置目标窗口的大小为Wmin和Wmax的中间值。如果没有丢包，则当前窗口的值设为Wmin，拥塞窗口增加现在与Wmin差值的一半；如果丢包，当前窗口值为Wmax。

加性增长：如果目前值与目标值差值太大，将拥塞窗口直接设置为目标值带来很大压力。此时设置一个Smax，按照Smax步长增长。

4.   CUBIC

对BIC算法的简化，用三次项支配窗口扩充算法，新窗口的尺寸w为：

 

三、参考文献

http://blog.csdn.net/zhangskd/article/details/6715751

http://baike.baidu.com/view/1954873.htm

还有许多硕士、博士论文，就不一一列举了，一并感谢。