5.3 拥塞控制，Congestion Control

拥塞：到达通信子网中某个局部的分组数量过多，路由器无法及时处理，导致该部分甚至整个网络性能下降的现象。严重时会导致通信子网出现局部或全部死锁，网络的吞吐量为0。

吞吐量、网络负荷

吞吐量描述了某个设备处理数据的速度，属于性能指标。

网络吞吐量（throughput）：设备（链路或节点）单位时间内成功转发的比特数或分组数。单位是 bps(bits per second)，或 pps( packets per second)。

系统吞吐量（或叫合计吞吐量）：整个通信子网单位时间内，合计成功转发的比特数或分组数。

吞吐量本质上等同于带宽消耗，可以用排队论对其做数学分析。
单位时间内输入的数据量称为“到达率”，单位时间内成功输出的数据量称为“离开率”。

网络负荷：通信子网中正在传输的数据量（合计分组数）。

吞吐量与负荷的关系

当负荷较小时，吞吐量随负荷的增加而线性增加。

当负荷到达一个临界值时，吞吐量反而会下降，此时，说明网络出现了拥塞。

拥塞现象

拥塞：节点没有空闲的缓存空间，只能丢弃新到来的分组，发送方需要重传分组，通信子网的吞吐量下降的现象。

当分组到达节点时，因为节点的缓冲区已经用尽，分组无法暂存在节点中只能被丢弃，发送方（前节点、源节点、源主机）只能重传该分组，而且后续的多次重传仍可能没有暂存空间，此时通信子网中多个节点的CPU、缓冲区以及逻辑信道都用于这种重传，使通信子网的吞吐量大大下降。

死锁

死锁是拥塞的最后阶段。

死锁是网络中极容易发生的故障之一，即使在网络负荷不算重时也可能发生。

一组节点由于没有空闲缓冲区而无法接收和转发分组，并且它们互相等待对方节点释放缓冲区，并一直保持这一僵局，严重时导致整个网络的瘫痪。

Internet中的“拒绝攻击服务”，实际上就是制造大量没有完成三次握手的TCP连接，使网络拥塞直至瘫痪。

通常只能依靠人工重启网络，解除死锁，但重启后仍然可能再次发生死锁，不能从根本上解决问题。

5.3.1 拥塞发生的原因

1.线路结构：多条输入线路共用一条输出线路，当每条输入线路都有分组到达时，汇集处的路由器如果没有足够的内存来存放这些分组，有的分组就会丢失。

2.节点的处理能力底下：路由器的性能不足，以至于无法完成必要的处理工作（比如缓冲区排队、更新路由表等），即使内存空间足够，也来不及将分组排队放入内存中，导致分组丢失。

拥塞控制和流控制的区别

拥塞控制的任务：保证通信子网能够承载进入子网的流量。

拥塞控制是一系列系统的、全局的控制手段，涉及多个方面的行为：

所有的主机
所有的路由器
路由器内部的存储-转发处理过程
所有可能降低子网承载能力的其他因素

流控制：控制点到点的流量，确保一个发方不会持续的以超过收方消化能力的速率发送数据。

流控制的做法是：收方向发方提供反馈，让发方了解自身的状态。

5.3.2 拥塞控制的通用原则

拥塞控制原则的理论基础来自于控制论，拥塞控制的解决方法可以分为两类：开环和闭环。

开环控制

设计网络时事先考虑到发生拥塞的所有因素，系统运行后就无法再中途改正。

开环手段包括：

确定何时接收新的流量
确定何时丢弃分组
确定丢弃哪些分组
在网络的不同点上执行调度决策

这些手段与网络的实际运行状态无关。

闭环控制

闭环方法依靠对网络实际状态的反馈，包括3个部分：

1)监视系统
监控何时、何地发生了拥塞。

可以用多种指标来判断是否发生拥塞：

因没有缓冲区而被丢弃的分组，在所有分组的占比
所有节点的平均队列长度
超时、重传分组的数量
平均分组延迟
分组延迟的标准方差

这些值越大，发生拥塞的可能性也越大。

2)将状态发送到能够采取行动的地方

有几种方法：

检测到拥塞的路由器向源端（可能有多个源）发送一个分组，报告情况。
在分组中预留一个位或一个域，当拥塞度量超过某个阈值后，路由器填充该位/域，这个分组之后传输到邻居节点时，就可以警告邻居节点。
主机或某些路由器周期性的向外发送询问分组，显式的询问拥塞的情况。
源端利用发出分组和确认分组的来回时间，隐式的推断是否可能发生拥塞。

调整系统以纠正拥塞

出现拥塞后，两种解决办法：

增加资源（带宽）：有时候增加系统的资源或容量是不可能的。
降低负载：拒绝为某些用户服务、给某些用户降低服务等级、让用户以一种更有预见性的方式来安排他们的需求。

5.3.3 拥塞预防策略

以下策略只能预防拥塞。

数据链路层

重传策略：涉及两个问题，1.超时时间设定为多久；2.超时后如何重传。对于第2个问题，可以用GBN和SR两种重传方法，显然，GBN带来的网络负载比SR多很多。
乱序分组缓存策略：如果接收方将乱序分组全部丢弃，则重传量会很大。（GBN，以及窗口很小的SR）
确认策略：有一种返回确认帧的方法是，不立即发回确认帧，而是先暂存在接收方，当发生反向流量时（收方-发方）捎带回去，但这样可能导致额外的超时和重传。
流控制方案：一个“紧凑”的流量控制方案，可以降低数据传输率，有助于缓解拥塞。紧凑是指减小窗口尺寸，比如：停止等待协议机制，滑动窗口机制。

网络层

虚电路还是数据报操作方式：许多拥塞控制算法只能与虚电路子网一起工作。
分组排队和服务策略：排队是指，是否为每条输入线路设置一个分组队列，是否为每条输出线路设置一个分组队列，或者为输入输出各设置一个队列（虚电路就是为输入输出各设置一个队列）。服务是指服务质量，虚电路在建立时就可以预留资源，这些虚电路所属的进程可以得到更好的服务。
分组丢弃策略：当节点的缓冲器耗尽时，应该丢弃哪些分组的规则。
路由算法：好的路由算法可以把流量分散到所有线路上，不好的路由算法则会将大量流量分配到已经拥塞的路线上。
分组生存管理：负责管理分组的生存时间，如果生存期太长，则会长时间的占用网络资源，但如果生存期太短，还未送达目的地就被丢弃了，会造成重传。

传输层

传输层的策略和数据链路层很相似：

重传策略
乱序缓存策略
确认策略
流控制策略
确定超时策略：传输层对确认超时的判断，比数据链路层更加困难，因为跨越整个通信子网的传输时间，比两台路由器之间的传输时间（数据链路层），更加难以预测。如果超时设定的太短，会导致更多的重传，增加拥塞的可能，如果设置得太长，重传会减少，但如果分组发生丢失，发现丢弃的响应时间会太长。

5.3.4 虚电路子网中的拥塞控制

有几种用于虚电路子网的动态拥塞控制方法：

1. 治疗措施：准入控制，一旦出现拥塞就不允许建立新的虚电路

一旦出现拥塞，则不允许创建任何新的虚电路，直到拥塞排除为止。

2. 治疗措施：允许建立新虚电路，但要避开拥塞节点重构子网拓扑，重做路由选择

即使出现拥塞，也允许建立新的虚电路，但要去掉发生拥塞的路由器，在信源和信宿间重建子网拓扑，基于新的子网拓扑进行路由选择，得到一条避开拥塞路由器的新路由。

3. 预防措施：在发生拥塞之前，建立虚电路时做好资源预留，避免发生拥塞

在建立虚电路前，主机和通信子网之间做好约定，约定的内容包括：流量的形状（traffic shaping)、服务质量、其他参数。
建立虚电路时，按照约定预留了资源（路由器的CPU、表空间、缓存空间、线路的带宽等），就不会发生拥塞。

5.3.5 数据报子网中的拥塞控制

数据报子网的拥塞控制方法，比虚电路子网的稍微复杂一点，但也很容易理解。

每台路由器都可以监视自己的“输出线路”和“其他资源”的使用情况。

对路由器的每一条输出线路，都可以用输出线路利用率 \(u(0.0 \lt u \lt 1.0)\) 描述“最近一个采样周期的线路利用率”。

路由器每隔采样周期 a 就会采样线路的瞬时利用率 \(f (f=0 or 1)\)，根据下面的计算公式来更新输出线路利用率 u ，使其尽可能的反映真实的情况。

\[u_{new} = a \times u_{old} + (1-a) \times f\]

采样周期 a 是一个常数，代表了：路由器需要多久来忘记历史线路利用率。

当 u 超过某个阈值时，说明该线路有发生拥塞的可能，路由器将该输出线路标记为“警告”状态。

当新的分组到达路由器时，路由器对其进行检查，如果分组流经“警告”线路，则采取以下措施：

1.警告位,Warning Bit，也称为 ECN

分组的头部中设置了一个特殊的二进制位：警告位。
当路由器发现分组应该发送到警告线路时，在分组的警告位进行标注。

被标注的分组送达目标主机后，警告位被复制到确认分组中，确认分组被送回源主机。

源主机收到带有警告位的确认分组后，减少发往该目的主机的流量。

只要输出线路的利用率高于阈值，就始终处于警告状态，被送往该线路的分组也始终被路由器设置警告位，返回源主机的确认分组也一直带有警告位。源主机根据带警告位的确认分组的比例，不断降低它的数据传输速率，
如果警告位确认分组占比低于某个临界值，源主机又会增加它的数据传输率。

疑问：数据报子网为什么有确认分组？

2.源主机响应抑制分组，Chock Packet（楔子分组）

路由器检测到某条输出线路处于警告状态时，路由器会做2个动作：

向源主机发送一个抑制分组：抑制分组中带有原数据分组的目标主机地址
在源分组头部某个二进制位进行标注：后续路由器收到这个分组时，就知道已经发回了抑制分组，不再产生更多的抑制分组

源主机收到抑制分组后，会做2个动作：

按照设定，把发送给指定目标主机的流量减少某个百分比。
在收到第一个抑制分组之前，源主机可能又向该目标主机发送了若干分组，这些分组必然会生成更多的抑制分组，此时，源主机应该在一段时间内忽略掉所有同一目标的抑制分组。

过了忽略时间段后，源主机再次可以接收该目标的抑制分组：

如果仍然收到抑制分组，说明拥塞仍然存在，源主机再次按照某百分比减少送往该目标的数据传输率，
如果没有收到该目标的抑制分组，说明拥塞排除，源主机可以增加该目标的流量。

Q.如何按百分比减少流量？
A.源主机按百分比减小发送窗口的尺寸。

3.逐跳响应抑制分组，Hop - by - hop

源主机响应抑制分组在2种情况下效果很差：

网络传输速度很高
源主机距离目的主机太远

这2种情况下，当抑制分组到达源主机时，源主机已经发送了大量的分组到子网中，拥塞控制的响应速度太慢。

逐跳响应抑制分组，是让抑制分组影响到送回源主机的沿途每一个路由器：
当抑制分组到达第一个路由器F时，F就必须减缓F-D的分组流，具体实现是：F为流向D的分组分配更多的缓冲区。
当抑制分组到达第二个路由器E时，E就会为流向F分组分配更多的缓冲区，从而减缓E-F的流量。
抑制分组到达了源节点A，A会为A-E的分组申请更多的缓冲区，将A-E的流量减缓下来。
最后，抑制分组到达与A相连的HOST，从而彻底降低HOST的分组发送速度，从源头上排除拥塞。

疑问：数据报子网中，源节点可以为每条输出线路单独划分缓冲区？

5.3.6 负载丢弃，Load Shedding

注意：负载丢弃适用于虚电路子网和数据报子网！

当前述的任何一种方法都不起作用时，就只能采取负载丢弃。

负载丢弃：当路由器来不及处理分组时，只要将这些分组丢弃即可。

应该丢弃哪些分组？

根据应用类型

根据发送分组的应用程序的分类，有2种丢弃分组的策略：

葡萄酒策略：老的比新的好，丢弃新的分组。比如：文件传输，假设一个文件总共有12个分组，接收方要求顺序接收分组（虚电路），丢掉分组6保留7_{12的话，可能会导致重传分组6}12，而丢弃分组10，只会导致10~12的重传。（这个例子举得不太好，将就看）
牛奶策略：新的比老的好，丢弃老的分组。多媒体传输，比如实时语音/视频，丢弃老的分组可能更好。 ###### 根据分组优先级发送方的应用程序给自己的分组标注优先级。
路由器丢弃分组时，从优先级低的开始丢弃。

随机的早期预测算法，RED(Random Early Detection)

RED，有多种展开法：Random Early Detection, Random Early Discard, Random Early Drop。

预先发现拥塞，比真的发生拥塞再来解决要好得多，RED就是基于这个思路的算法。

随机早期预测算法：在路由器发现分组队列缓冲区即将耗尽之前，就随机的丢弃分组。

平均队列长度： Average Queue Length，指数加权移动平均。

\(Q_{avg} = (1-w) \times Q_{avg} + w \times Q_{sample} ,(0 \le w \le 1)\)

\(Q_{sample}\)是采样获得的实际长度。\(w\) 是采样周期。

路由器为每一条输入线路设置了独立的分组缓冲队列，并且监控了每个队列的平均队列长度。一旦某条输入线路的平均队列长度超过了阈值，则认定它发生了拥塞（实际上此时分组缓冲尚未耗尽）。虽然定位了拥塞队列，但无法判断哪一个源主机是引起拥塞的元凶（实际上也可能是多个源共同作用的结果），因此，路由器随机的丢弃拥塞队列中的分组。

即使丢弃了分组，仍然需要通知造成拥塞的源主机才能从根本上消除拥塞。通知源主机的方法有：

显式通知，回送抑制分组：源主机响应的、逐跳响应的。缺点：在已经拥塞的网络中引入更多的负载。
隐式通知，不发送抑制分组：源主机发现没有确认分组返回时，不再重发分组，而是降低发送速率。需要：给源主机设定“不重发、仅降速”的策略。

5.3.7 抖动控制，jitter control

抖动：“分组到达路由器或信宿的传输时间”的标准差。

标准差（标准偏差，均方差）：所有数减去平均值，每个差值的平方和除以数的个数（或个数减一)，再把所得值开根号。
标准查表示了一组数值的离散程度。

传输音频流/视频流时，高抖动会导致声音/电影不稳定。

如何降低抖动？

事先通过计算，可以确定分组在每一跳的期望到达时间。

当一个分组到达路由器时，路由器会检查实际到达时间和期望到达时间，并将检查结果标注在分组中。
如果早到了就多存储一会儿，如果晚到了就优先转发出去。并在转发时更新时间差。后续路由器重复此动作。

如果多个分组竞争同一输出线路，应该先转发哪一个？

路由器采取的算法是：与期望到达时间偏差最大最晚的那个分组，最先发出。

接收方缓存分组

除了路由器，目的主机也可以缓存分组，通过稍微延后的播放视频消除抖动，而非实时接收分组。

但对于实时交互的应用，比如网络电话、视频会议，接收方缓存就无法消除抖动了。