网络拥塞控制指北（一）- 网络层篇

发表于 | 分类于

我们之前提到网络传输的两大基本问题，一个是「如何提供可靠的数据传输」，这个问题我们在前面的笔记中已经给出了指南，本文将解答第二个问题「如何避免网络拥塞以及在拥塞发生时如何恢复」。

什么是网络拥塞？当网络中存在太多的流量导致数据包被延迟或丢失，从而降低了网络性能，这种情况就被称之为网络拥塞。

病名：网络拥塞
早期症状：消化不良 —— 过度延迟、丢包
晚期后果：瘫痪 —— 拥塞崩溃 (congestion collapse)，因负载过重超出了网络承受能力，导致网络性能骤降
病因：被投喂过多 —— 发送方发送速率太快，导致路由器缓冲区溢出
不良影响：

  • 导致发送方重传很多不必要的数据包（还在传输途中的但因为过度延迟被判断为丢包/已经被接收但是ACK丢失的那些数据包），进一步加重拥塞，陷入恶性循环；
  • 当一个数据包传到一半时被丢弃了，则在这之前消耗的资源都被浪费了

知道了症状，也知道了病因，才好积极预防、对症下药嘛~

网络拥塞的治疗方案由网络层和传输层协作实施，网络层作为直接经历拥塞的部分，需要它最终决定如何处理过载的数据；而传输层作为“幕后黑手”，要控制拥塞还需其积极配合。

网络层的拥塞控制

那我们先来看看在网络层，有哪些方法可用于拥塞控制。
拥塞的发生表明当前的网络负载大于资源可以处理的能力，显然，解决方案有两个方向，减少负载或增加资源。
下图展示了主要的几种解决方案，从左至右，解决方案的反应时间由慢变快。左侧属于预防性措施，一般要经历长期过程；右侧则属于应急响应，效果立竿见影。
打个比方，若是应对感冒，最左好比锻炼身体增强免疫力，最右好比退烧针。

congestion-control-network-layer

网络供给 Provisioning

当出现严重拥塞时，通过动态增加网络资源疏通流量，比如使用备用路由器或者购买更多的带宽等；平时及时对经常使用的链路和路由器升级；
这些或临时或日常的操作统称为供给（provisioning），目的是建立一个与流量良好匹配的网络，网络供给通常在长期流量趋势的推动下需要几个月的时间来调整和完善。

流量感知的路由 Traffic-aware routing

为了充分利用现有的网络容量，根据每天的流量模式定制路由，就被称为流量感知的路由(traffic-aware routing)。
以全球范围为例，不同时区的用户醒着和睡觉的时间不同，不同地区的流量在不同时间段也是不同的。通过改变最短路径的权重可以更改数据包的路由，以达到使流量远离频繁使用的路径的目的。
一种简单的链路权重计算方法为将其设为一个固定链路带宽、传输延迟、可变测量负载或平均排队延迟的函数，然而这种方式由于引入了可变的负载/排队延迟，很容易造成路由振荡。

举个例子，假设有两条链路 A 和 B：

  1. 一开始，链路 A 经过计算为大部分流量所选择的最短路径，后续流量都选择路径 A；
  2. 一段时间后，链路 A 由于负载变重延迟变大，链路 B 更具有吸引力，后续流量选择路由 B；
  3. 同理，又过了一段时间，链路 B 由于负载变重延迟变大，而链路 A 的负载因为被 B 分流而得到了缓解，后续流量更倾向于选择 A；
  4. 如此摇摆，路由表可能一直处于振荡状态，从而导致不稳定的路由和其他问题

因为这些问题的存在，Internet 路由协议通常不依赖于负载来调整自己的路由，而是在路由协议外部通过慢慢改变它的输入来调整路由，即所谓的流量工程(traffic engineering)。

准入控制 Admission control

很多时候，我们不是想增加资源就能增加的，这个时候，就只能降低负载了。准入控制的思想那是相当的简单：如果新增的连接将导致网络拥塞，那就拒绝建立新连接。
一个萝卜一个坑，拒绝超载。

流量控制 Traffic Control

拥塞的发生通常是因为发送方传输速度过快导致，如果能有方法动态调节流量，使得拥塞发生之前网络能正常高效地工作，而在拥塞迫在眉睫之时通知发送方降低传输速度就好了。
要实现流量控制，主要解决两个问题：

  • 路由器如何确定即将发生拥塞？
  • 路由器如何把信息反馈给造成拥塞的发送方？

如何确定拥塞即将发生

路由器可以监测的资源数据包括：

  • 输出线路的利用率 - 平均利用率没有考虑突发的流量
  • 因缓冲区溢出而丢失的数据包数量 - 因此丢包的计数来得太晚，丢包发生时，拥塞已经形成
  • 在路由器缓冲区内排队的数据包 - 通过数据包的排队延迟可以及时反映拥塞情况，排队延迟大部分时间应该很低，当突发流量产生积压时会跳跃。

通常，会使用指数加权移动平均 (EWMA, Exponentially Weighted Moving Average)来估计排队延迟 d，s 表示某个瞬时队列长度，常数 α 决定路由器多快忘记最近的历史：
$$d_{new}=\alpha \, d_{old} + (1-\alpha) s$$
当 d 升高到某个阈值之上，就表示拥塞可能要发生了。

路由器如何把拥塞信息反馈给发送方

主要有如下几种方式：

抑制包 Choke packet

当拥塞发生时，路由器选择一个被拥塞的数据包，给该数据包的源主机返回一个抑制包 (choke packet)，同时路由器会在原来的拥塞数据包上添加一个标记，这样这个数据包在后续转发的路径上不会产生更多的抑制包。当源主机收到抑制包后必须减少发送给目标主机的流量。

显式拥塞通知 Explicit Congestion Notification

当拥塞发生时，路由器在它转发的任何数据包上设置某个标志位发出信号，表明发生了拥塞。接收方收到后在应答时顺便将拥塞的消息告知发送方。这种方式被称为显式拥塞通知，Internet 用的就是这种方式。

逐跳后压

当网络速度很快或者距离很远时，由于传输延迟，拥塞信号发出后到它产生作用期间又产生了很多新流量。有一种改进方法是让抑制信号在每一跳都发挥作用。这种方式可以很快缓解拥塞点的拥塞现象，不过代价是其上游路径需要消耗更多的缓冲区空间。
这种方法可以将拥塞消灭在萌芽状态。

减载 Load shedding

当以上方法都没有办法消除拥塞时，就只能用最直接粗暴的方案了：当路由器来不及处理数据包时，就直接丢弃。
问题在于：丢弃哪些数据包呢？

一种最简单的方式就是尾丢弃 (drop-tail)，顾名思义，队尾新来的放不下的数据包会被丢弃。

然而，在某些情况下，这并不是一种好的丢弃策略。考虑到应用程序的类型，不同时刻到达的数据包其重要性并不是一样的。
举几个例子：

  • 对于文件传输 - 旧数据包比新数据包重要，如果丢弃数据包6，而保存7-9，则会迫使接收方缓存这些暂时不能使用的数据
  • 对于实时流媒体 - 新的数据包要比旧的重要

因此，在选择丢弃数据包的时候考虑应用程序的类型是一种相对更好的方式。如果要实现更智能的丢包策略，则还需要应用程序的参与，比如要求它们为每个数据包标记其重要性，路由器根据这个值来决定丢弃哪些数据包。

一般来说，在拥塞苗头刚刚出现时及时扼杀比等它发生之后再处理更有效。因此，在路由器缓冲区用尽之前提前丢包或者标记以给发送方发出拥塞的信号不失为一种有用的预防机制。

事实上，已经有很多主动性的丢包/标记策略被提出，统称为主动队列管理 (Active Queue Management, AQM) 算法。下文提到的随机早期检测 (RED) 是其中应用最广泛的算法之一。

随机早期检测 Random Early Detection

随机早期检测提供了一种确定“提前”丢包的时间点的方式：路由器维护一个队列长度的平均值，当平均队列长度超过某个阈值时，该链路就被认为拥塞，路由器会随机丢一部分数据包。随机选择使得传输速度较快的发送方发现丢包的可能性更大。当没有出现期待的应答时，发送方会发现丢包，然后传输协议将放慢速度。在这里，丢失的数据包起到了抑制包的作用，但却是隐含的，不需要路由器发送任何显式信号。

RED 最早由 Floyd 和 Jacobson 在 1993 年提出，后来又出现了不少基于 RED 的改进算法，比如 Weighted Random Early Detection (WRED)、Robust Random Early Detection (RRED) 等。

除此之外，还有很多其他的 AQM 算法，更多有关 AQM 可见其 Wiki - Active Queue Management。

到此为止，我们总结了几种主要的网络层采用的拥塞控制机制，那么传输层的拥塞控制又需要做些什么呢？
未完待续…

参考资料