传输层的拥塞控制

一、拥塞的成因

1.1、2个发送方2个接收方和一台具有无穷大缓存的路由器

假设主机A和主机B都经过同一个路由器，且路由器有无限缓存，路由器的链路容量是R，如下图所示：

主机A中的应用程序以λin 字节/秒的平均发送速率将数据从应用层发送到传输层中，默认这些数据都是初始数据，每个数据单元仅通过分组发送一次，不会执行差错恢复（重传），不会执行流量控制和拥塞控制，同时忽略传输层和传输层以下（网络层，数据链路层，物理层）添加的额外头部信息，此时，主机A向路由器发送流量的速率就是λin 字节/秒，由于主机B与主机A相同并且共享一段容量为R的链路，则主机A和主机B的最大发送速率都是R/2。当主机A的发送速率接近于R/2时，主机A的发送速率与接收方的吞吐量的函数关系，主机A的发送速率与时延的函数关系，如下所示：

1.2、2个发送方2个接收方和一台具有有限缓存的路由器

假设主机A和主机B都经过同一个路由器，且路由器的缓存是有限的，路由器的链路容量是R，如下图所示：

主机A的 λin （应用层向传输层发送数据的发送速率）、主机B、链路容量R 都与1.1相同，由于路由器的缓存是有限时，那么缓存已满时多余的分组必定会被丢弃，在可靠连接中被丢弃的分组将会发生重传，这会导致传输层向网络层发送数据的发送速率λin’ ≠ λin ，假设有以下三种情形：
①、发送方能够通过某种机制获知路由器缓存（buffer）信息，并且在路由器有空闲缓存时才发送数据，此时λin’ = λin = λout，主机A的发送速率与接收方的吞吐量的函数关系与1.1相同，如下图a所示；
②、发送方不能获知路由器缓存（buffer）信息，发送方定时器的时间设置为无限长，由于发送方的定时器并不会超时，当发送方确认分组丢弃后才会重发分组，此时λin’>λin，λin’> λout，发送方必须重传丢弃的分组，当发送的0.5R的数据时，其中有0.333R是初始数据，有0.166R是重传数据，造成资源的浪费，如下图b所示；
③、发送方不能获知路由器缓存（buffer）信息，发送方定时器的时间有限，发送方在发生超时时重传在队列中已被推迟但还未丢弃的分组，此时λin’>λin，λin’> λout，发送方必须重传丢弃的分组和超时的分组，当发送的0.5R的数据时，其中有0.25R是初始数据，有0.25R是重传数据，造成资源的浪费，如下图c所示；

1.3、4个发送方4个接收方和多台具有有限缓存的路由器及多跳路径

假设主机A、主机B、主机C、主机D都通过交叠的两跳路径传输，假设每台主机都采用超时/重传机制来实现可靠数据传输，所有的主机都有相同的 λin，路由器的链路容量都是R，如下图所示：

路由器R2同时承载着主机A→主机C、主机D→主机B的数据发送，当网络拥塞形成时，会发生1.2中所出现的情况， 主机A和主机D的发送速率会接近于R/2，R/3，直到接近于R/4，造成分组成不断的丢失。与1.2不同的是，当路由器R2将主机A→主机C的分组丢弃后，会导致之前的路由器R1对于R2丢弃的分组做的存储和转发都是“劳而无功”的，因此，在多跳网络中，当分组被drop时，任何用于该分组的“上游”传输能力全都被浪费掉了，导致整个网络的吞吐率变的更差，如下图所示：

二、网络辅助的拥塞控制和端到端的拥塞控制

拥塞控制的原理可以根据网络层是否为传输层拥塞控制提供了显示的帮助来区分，如下：
①、端到端的拥塞控制：网络层没有为传输层拥塞控制提供显示支持，即使网络中存在拥塞，发送方也必须通过对网络行为的观察来推断，比如分组丢失和分组时延，TCP的拥塞控制就属于端到端的拥塞控制，详细内容，请查看本章2.2；
②、网络辅助的拥塞控制：网络层为传输层的拥塞控制提供显示支持，网络层或者核心的网络设备会向发送方显示的反馈网络拥塞信息，发送方就可以利用这个信息调整信息发送，这种方式通常需要依靠简单的拥塞指示来避免overload，简单的拥塞指示如SNA、DECbit、TCP/IP ECN、ATM...，其中ATM拥塞控制机制中的ABR（available bit rate）服务的详细内容，请查看本章2.1；

2.1、ATM拥塞控制机制中的ABR（available bit rate）服务（网络辅助的拥塞控制）

ABR服务是一种“弹性服务”，工作逻辑大致如下：
①、如果发送方发现网络路径的负载比较低（underloaded），那么发送方会使用可用带宽来发送数据；
②、如果发送方发现网络路径出现拥塞，那么发送方的发送速率会降低到最低保障速率。
在ATM网络中，除了有data cell（在ATM网络中，data cell表示分组），还有RM cell（也是一种分组），这种RM cell是穿插在data cell中间的，发送方一般在发送若干个data cell后，会发送一个RM cell，RM cell在整个网络传输过程中，网络设备会修改RM cell中的数据，主要修改的RM cell中的数据有以下2种：
①、NI bit：是否允许传输速率继续增长；
②、CI bit：当前网络中是否拥塞。
当RM cell通过整个网络传输给接收方时，接收方会将RM cell返回给发送方，此时发送方就可以利用RM cell了解整个网络的拥塞情况，整个过程如下图所示：

2.2、TCP的拥塞控制的基本原理（端到端的拥塞控制）

Tahoe算法和Reno算法的详细细节，请查看：
7.3、传输层的拥塞控制算法—Tahoe算法和Reno算法
TCP拥塞控制的主要措施是限制发送方的发送速率，与TCP协议的流量控制不同（流量控制是在接收方设置一个RevBuffer大小的内存空间），TCP协议的拥塞控制是在发送方设置一个拥塞窗口——窗口大小为CongWin，CongWin满足以下公式：

；；������������−�������������<=�������；

LastByteSent 表示最后一个发送的分组的序列号；
LastByteAcked 表示最后一个确认接收的分组的序列号；
rate（发送速率）≈ CongWin/Rtt；

此时，我们通过改变CongWin的大小，就可以间接的改变发送速率。当网络拥塞程度比较严重时，将CongWin的值调整的较小一些即可，当网络中不存在拥塞或者网络拥塞的程度比较小时，将CongWin的值调整的较大一些即可。对于网络拥塞的感知，TCP协议主要通过loss事件来进行判断，loss事件可以分为以下2种：
①、发送方的发送窗口出现timeout；
②、发送方的收到3个重复的ACK。
当发送方出现loss事件时，发送方判定为网络拥塞，此时发送方需要降低发送速率，当发送速率成功降低后，发送方又要合理的调整CongWin的大小，使发送速率恢复到一个较大的值来进行网络传输，整个CongWin的调整逻辑，如下图所示：

TCP协议控制CongWin的策略，主要有以下3种：
①、加性增，乘性减的AIMD机制，AIMD的原则是逐渐增加发送速率，谨慎探测可用带宽，直到发生loss事件。其中加性增（Additive Increase）策略指的是在每个RTT后将CongWin增大一个MSS（最大段的长度），乘性减（Multiplicative Decrease）指的是发生loss事件后将CongWin减半。整个过程中拥塞窗口大小CongWin的变化，如下图所示：

②、慢启动（ss），慢启动的原则是当TCP连接开始时，CongWin可以指数性增长。慢启动的原则解决了AIMD机制中加性增（Additive Increase）的线性增长问题，因为在网络初始阶段，可用带宽可能远远高于初始发送速率，此时我们希望的是发送速率可以快速增长。如下图所示：

③、Threshold变量。通过AIMD中的加性增（Additive Increase）和慢启动（ss），可以实现CongWin的线性增长和指数增长，但是在切换CongWin的线性增长和指数增长时，需要依靠Threshold变量。一般系统会有一个初始的Threshold变量，当拥塞窗口的大小CongWin<Threshold时，CongWin为指数增长，当拥塞窗口的大小CongWin=Threshold时，CongWin由指数增长变为线性增长。无论CongWin使用哪种增长方式，当前网络都有可能发生loss事件，当loss事件发生时，CongWin和Threshold有以下2种变化方式：
a、loss事件为发送方的收到3个重复的ACK时，此时CongWin=CongWin/2，Threshold=CongWin/2，修改后，CongWin等于Threshold，CongWin继续线性增长；
b、loss事件为发送方的发送窗口出现timeout时，此时CongWin=1个MSS（MSS表示最大分组的长度）的大小，Threshold=CongWin/2，修改后，CongWin<Threshold，CongWin变为指数增长，当CongWin等于Threshold时，CongWin由指数增长变为线性增长；
以上a，b这两种变化方式，如下图所示：

因此，通过Threshold变量来控制AIMD机制和慢启动（ss）机制，总结如下：

2.2.1、TCP拥塞控制算法

伪代码如下：

Threshold = 根据主机和当前网络设置一个合理的值 CongWin = 1 MSS /*指数增长：slow start or exponential increase */ While (No Packet Loss and CongWin < Th) { send CongWin TCP segments for each ACK increase CongWin by 1//每个RTT都会增长 } /*线性增长：congestion avoidance or linear increase */ While (No Packet Loss) { send CongWin TCP segments for CongWin ACKs, increase CongWin by 1//整个拥塞窗口RRT才会增长 } Threshold = CongWin/2 //无论哪种loss，Threshold都减半 //CongWin 需要根据loss事件来确定CongWin=CongWin/2 或 CongWin=1 If (3 Dup ACKs) CongWin = Threshold;