1 拥塞避免算法

 名称解释：

 报文段---

 TCP一次传输所发送的一定长度的字节段。

 TCP的滑动窗口机制，作为接收方管理发送方发送数据量的手段，以防止接收方的接收缓冲区因为满而溢出。

拥塞窗口(cwnd)，

接收端通知窗口(rwnd)，

慢启动阀值(ssthresh)，

慢启动的特征：1 cwnd被初始化为一个数据包大小

                              2 cwnd
指数增长

拥塞避免：1在一个RTT时间内cwnd只增加一个MSS大小

                     2 cwnd线性增长

快速重传：连续收到三个重复的ack就认定数据包丢失，重传数据包（不管RTO）。

1、拥塞避免算法出现的原因

        拥塞避免算法是一种处理丢失分组的算法。

 1.1拥塞和丢失的关系

报文段丢失的认定标准就是：TCP发送超时和连续收到三次重复的ACK(Jacondson算法)。

 两个通信主机之间如果有报文段丢失，就表示二者通信存在拥塞。

2、拥塞发生后的处理

拥塞发生后，要做的就是降低分组进入网络的传输速率。而慢启动算法正好可以降低传输速率.

2.1 拥塞避免算法和慢启动算法

2.1.1算法图解

2.1.2
存在的问题

         在长延时的通信环境中效率很低。根据TCP协议，连接建立后，首先根据慢启动算法对流量进行控制。按照慢启动策略初始发送窗口大小为1个基本数据包，然后按指数增大接收窗口。这样，从开始到恢复到最大发送窗口所需的时间为：慢启动时间=RTT×1og2（max－win／MSS）其中：RTT为往返时延；max－win为TCP最大窗口；
MSS为每个数据包的长度。按照RTT＝0.5s，max－win=64K字节，MSS＝512字节，则侵启动时间为3.5s。这说明在前3.5s内，TCP传输不可能达到峰值传输速率。在实际应用中，当发送窗口大于慢启动门限窗口后，便进入了拥塞避免过程，在拥塞避免算法中，窗口的增加速率更加缓慢，不再是慢启动算法中的指数增加，而是呈线性增加的。这一方面会引起网络的激烈振荡，另一方面大大降低了网络的利用率。

2.1.2实际应用

Tahoe算法是TCP的早期版本。它的核心思想是：让cwnd以指数增长方式迅速逼进可用信道容量，然后慢慢接近均衡。Tahoe包括3个基本的拥塞控制算法：“慢启动”、“拥塞避免”和“快速重传”。

    (1)慢启动：避免了连接建立时突发数据流对网络的冲击。

    初始设置cwnd为1，并按指数型方式增长，直至cwnd超过ssthresh。

    当cwnd>=ssthresh时，Tahoe进入拥塞避免阶段。

    (2)拥塞避免：限制传输过程中无限制的速率增长，避免由此可能导致的拥塞。

    cwnd以线性方式增长。

    如果发生超时或者连续收到3个重复ACK，Tahoe认为发生了拥塞。

    对于超时，置ssthresh为当前拥塞窗口的一半，cwnd=1，转入慢启动。

    如果收到3个连续ACK，则Tahoe进入快速重传阶段。

    (3)快速重传：根据3个重复的应答报文来判断丢包，减少了超时重传的发生，加快了源端对拥塞的响应，使得拥塞能快速消除。立即重传丢失的分组，同时置ssthresh为当前拥塞窗口的一半，cwnd=1，转入慢启动。

 2.2快速重传与快速恢复算法

Jacondson算法(快速重传算法)：

 TCP传输中会统计接收到的重复ACK的次数，当次数大于三次时，说明此重复ACK中确认序号后的报文段丢失，立即重传。如图：

2.2.1重传和快速恢复具体过程为   

1. 当收到第3个重复的ACK包时，ssthreh置为阻塞窗口的一半；
  

2. 重传丢失的包后，将拥塞窗口cwnd设置为sshresh+3*SMSS；   

3. 对于每个接收到的重复的ACK包，cwnd相应增加SMSS，扩大拥塞窗口；
  

4. 如果新的拥塞窗口cwnd值大于接收方待确认数据大小，可以继续发新包

5. 当收到下一个ACK确认了新数据时，将cwnd大小调整为sshresh，减少窗口；对接收方来说，接收到重发的TCP包后就要发此ACK确认当前接收的数据。

2.2.2
快速恢复算法的特点

       （1）与慢启动不同cwnd不设置为1
而是设置为ssthresh+3

(2)如收到重复的ack(n>3),将cwnd设置为ssthresh+n

(3)如果发送窗口依然允许发送数据，则按拥塞避免算法继续发送数据

(3)如收到新的ack
将cwnd缩小为ssthresh。

2.2.3实际应用

针对Tahoe算法的不足之处，1990年Jacobson在Tahoe的基础上提出了改进算法Reno。改进主要有两个方面：一是对于收到连续3个重复ACK，算法不经过慢启动，而直接进入拥塞避免阶段；二是增加了快速重传/快速恢复机制。具体实现过程为：

    (1)收到三个重复的ACK，进入快速重传/快速恢复，此时ssthresh设置为当前拥塞窗口的一半。

    (2)重传丢失的数据包，并置cwnd＝cwnd＋ndup(ndup为收到的重复ACK数)。

    (3)发送新的数据包。

    (4)当收到非重复的ACK时，cwnd＝ssthresh。

    (5)进入拥塞避免阶段。

    从上面的过程可以看出，Reno在收到3个重复ACK后，就转入快速重传/快速恢复阶段；而遇到超时时，Reno和Tahoe一样进入慢启动阶段。

Reno目前被广泛采用，以其算法的简单、有效和鲁棒性成为TCP源算法的主流。但是如果在一个发送窗口内有多个包丢失时，该算法不能有效恢复出来，为此提出了一些改进，如NewReno、Sack等

2.3 Reno与Tahoe的区别

Reno与Tahoe相比，增加了快速恢复阶段，也就是说，完成快速重传后，进入了拥塞避免阶段而不是慢启动阶段。