概念
- 可以将拥塞形象的理解为堵车
在图中,绿色指的是理想情况下不发生拥塞的情况,此时吞吐量与输入负载相等。当网络资源数被全部利用时,吞吐量不再增长。
红色线指的是出现拥塞不进行处理,会导致吞吐量下降,知道吞吐量为零,产生死锁现象。
蓝色线是在出现拥塞后采用拥塞控制措施,使吞吐量保持在一定水平。
网络拥塞往往是由许多因素引起的。例如:
- 点缓存的容量太小;
- 链路的容量不足;
- 处理机处理的速率太慢;
- 拥塞本身会进一步加剧拥塞;
拥塞控制的一般原理
- 拥塞控制的前提:网络能够承受现有的网络负荷。
- 实践证明,拥塞控制是很难设计的,因为它是一个动态问题。
- 分组的丢失是网络发生拥塞的征兆而不是原因。
- 在许多情况下,甚至正是拥塞控制本身成为引起网络性能恶化、甚至发生死锁的原因。
开环控制和闭环控制
监测网络的拥塞
主要指标有:
- 由于缺少缓存空间而被丢弃的分组的百分数;
- 平均队列长度;
- 超时重传的分组数;
- 平均分组时延;
- 分组时延的标准差,等等。
拥塞控制的算法
先了解拥塞算法中的基本思路:
真正的发送窗口值 = Min (接收方窗口值,拥塞窗口值)
下图的实例横纵坐标的意思
传输轮次:
- 发送方给接收方发送数据报文段后,接收方给发送方发发回相应的确认报文段
- 一个传输轮次所经历的时间其实就是往返时间,往返时间并非是恒定的数值
- 使用传输轮次是为了强调把拥塞窗口所允许发送的报文段都连续发送出去,并受到了对已发送的最后一个报文段的确认
拥塞窗口:
- 它会随网络拥塞程度,以及所使用的拥塞控制算法动态变化
慢开始算法
- 目的:用来确定网络的负载能力或拥塞程度。
- 算法的思路:由小到大逐渐增大拥塞窗口数值。
- 两个变量:
- 拥塞窗口(cwnd):初始拥塞窗口值:2 种设置方法。窗口值逐渐增大。
- 1 至 2 个最大报文段 (旧标准)
- 2 至 4 个最大报文段 (RFC 5681)
- 慢开始门限(ssthresh):防止拥塞窗口增长过大引起网络拥塞。
- 拥塞窗口(cwnd):初始拥塞窗口值:2 种设置方法。窗口值逐渐增大。
- 慢开始指的是一开始网络注入的报文段少,并不是指拥塞窗口cwnd的增长速度慢。
为了更清楚显示出拥塞控制过程,建立以下坐标系:
其中横坐标为传输轮次,也就是完整发送一个拥塞窗口数据并且收到确认报文的时间(可以理解为往返时间)。
纵坐标为拥塞窗口,并且根据不同情况会设置一个慢开始门限。
进行第一轮数据通信:
进行第一轮数据通信时前,发送方会将初始拥塞窗口设为1,并且设置一个ssthresh(慢开始传送位),然后开始传送数据,在收到确认报文后:
将拥塞窗口设置为原来的两倍。
此时,座标系情况如下:
进行第二次发送:
第二次发送顺利进行,成功接收到确认报文后,将拥塞窗口增大到4.
此时坐标轴情况:
进行第三轮发送:
第三次发送顺利进行,成功接收到确认报文后,将拥塞窗口增大到8.
进行第四轮发送:
第四次发送顺利进行,成功接收到确认报文后,将拥塞窗口增大到16.
此时可以看出,拥塞窗口已达到慢开始门限SSTHRESH,此时,慢开始算法使用阶段结束,开始拥塞避免算法阶段。
拥塞避免算法
- 拥塞避免算法让拥塞窗口 cwnd 缓慢地增大(每伦窗口大小+1),避免出现拥塞。
- 在拥塞避免阶段,具有 “加法增大” (Additive Increase) 的特点
- 拥塞避免算法并不能完全避免拥塞,只是在拥塞避免阶段将容易拥护的窗口控制为按线性规律增长,是网络比较不容易出现拥塞
接上面的例子:
进行第六轮传输:
此时不再使用慢开始算法,采用拥塞避免算法,每个轮次只给拥塞窗口+1.
此时坐标轴情况如下:
第七轮传输:
传输成功后,给拥塞窗口+1.
循环重复此传输过程,若出现以下情况:
如果在发送过程中出现部分报文段丢失,这必然会造成发送方对这些丢失报文段的超时重传
这个时候又回到了慢开始
对于以上两个算法的完整示意图:
有一种情况:
因此提出了快重传算法和快恢复算法。
快重传算法
- 对于个别丢失的报文段,发送方不会出现超时重传,也就不会误认为出现了拥塞(这会使拥塞窗口设置为1),该算法可以使整个网络吞吐量提高约20%。
例如:
在快重传算法中,发送方会在接收到确认分组前就发送下一个分组(前提是在拥塞窗口大小内),对于丢失的分组,会在收到3个分组后发送3个重复确认丢失分组序号。
接收方收到3个重复分组序号后便开始重传,而不是等待超时计时器到时。
这样子也不会误以为出现了拥塞。
快恢复算法
四个算法再传输过程中的使用顺序图:
一开始使用慢开始算法,拥塞窗口开始指数规律增大到设定的ssthres值后执行拥塞避免算法。
拥塞避免算法将拥塞窗口以1为单位线性增大,直到出现分组丢失,重传计时器时间到后,cwnd设置为1,ssthresh值设置为发生拥塞的窗口值大小一半,并重新开始执行慢开始算法。
在发送方收到3个重复确认时及逆行快重传和快恢复算法,将ssthresh的值更新为当前拥塞窗口值得一半,更新cwnd值为ssthresh值。