网络传输问题实质上是对网络资源的共享和复用问题，因而拥塞管制是网络工程畛域的外围问题之一，并且随着互联网和数据中心流量的爆炸式增长，相干算法和机制呈现了很多翻新，本系列是收费电子书《TCP Congestion Control: A Systems Approach》的中文版，残缺介绍了拥塞管制的概念、原理、算法和实现形式。原文: TCP Congestion Control: A Systems Approach
第 6 章 被动队列治理(Active Queue Management)
当初咱们来看看路由器在拥塞管制中表演的角色，这种办法通常被称为 被动队列治理(AQM, Active Queue Management)。就其本质而言，AQM 引入了一个防止端到端解决方案的元素，即便与 TCP Reno 等基于管制的办法配合也能发挥作用。
只管对路由器行为的扭转从来不是互联网引入新性能的首选形式，但在过来 30 年里，这种办法始终令人感到缓和。问题在于，尽管人们普遍认为路由器处于检测拥塞开始的现实地位(即队列开始被填满)，但对于什么才是最佳算法并没有达成一致意见。上面介绍了两种经典机制，并简要探讨了目前的状况。
6.1 DECbit
第一种机制是为数字网络体系架构 (DNA, Digital Network Architecture) 开发的，它是 TCP/IP 互联网的晚期竞争者，也采纳了无连贯 / 尽力而为网络模型，由 K.K. Ramakrishnan 和 Raj Jain 独特创造，和 Jacobson/Karels 的论文同时发表在 1988 年的 SIGCOMM 会议。
延长浏览:\
K.K. Ramakrishnan and R. Jain. A Binary Feedback Scheme for Congestion Avoidance in Computer Networks with a Connectionless Network Layer. ACM SIGCOMM, August 1988.
其想法是在路由器和终端主机之间更平均的分担拥塞管制的责任。每个路由器监控正在解决的负载，并在拥塞行将产生时显式告诉终端节点。这个告诉是通过在流经路由器的数据包中设置一个二进制拥塞位来实现的，这个二进制拥塞位起初被称为DECbit。而后，指标主机将这个拥塞位复制到 ACK 中返回给发送端。最初，发送端通过调整发送速率防止拥塞。上面将从路由器开始具体的介绍该算法。
在包报头中减少一个拥塞位，如果数据包达到时，路由器的均匀队列长度大于或等于 1，则设置此位。均匀队列长度是在逾越上一个忙碌 / 闲暇周期，再加上以后忙碌周期的工夫距离内测量的。(路由器忙指的是正在传输数据，闲暇指的是没有传输数据。) 图 34 显示了路由器上的队列长度随工夫的变动。实际上，路由器将计算曲线下的面积，并将该值除以工夫距离来计算均匀队列长度。应用队列长度为 1 作为设置拥塞位的触发器是在有大量排队 (从而吞吐量较高) 和大量闲暇工夫 (从而提早较低) 之间的衡量。换句话说，长度为 1 的队列仿佛优化了幂函数。
当初咱们把注意力转移到该机制与主机相干的局部，发送端记录有多少包导致路由器设置了拥塞位，就像在 TCP 中一样保护了一个拥塞窗口，并察看最初一个窗口的数据包值中有多少导致拥塞位被设置。如果少于 50% 的包设置了拥塞位，则发送端的拥塞窗口就减少一个包。如果上一个窗口值的 50% 或更多的包设置了拥塞位，则发送端的拥塞窗口减小到前一个值的 0.875 倍。通过剖析，抉择 50% 作为阈值，与幂曲线的峰值绝对应。之所以抉择 ” 减少 1，缩小 0.875″ 规定，是因为线性减少 / 指数缩小使机制更稳固。
6.2 随机晚期检测(Random Early Detection)
第二种机制被称为 随机晚期检测(RED, Random Early Detection)，相似于 DECbit 计划，每个路由器都被编程来监控本人的队列长度，当检测到拥塞行将产生时，告诉发送端调整拥塞窗口。RED 是由 Sally Floyd 和 Van Jacobson 在 20 世纪 90 年代晚期创造的，与 DECbit 计划的不同之处在于以下两点。
延长浏览:\
S. Floyd and V. Jacobson Random Early Detection (RED) Gateways for Congestion Avoidance Gateways for Congestion Avoidance”). IEEE/ACM Transactions on Networking. August 1993.
首先，RED 并不向发送端显示发送拥塞告诉音讯，而是抛弃一个包，通过后续的超时或反复 ACK 来隐式告诉发送端。兴许你会猜到，RED 被设计成与 TCP 一起应用，TCP 目前就是通过超时 (或其余检测丢包的办法，比方反复 ACK) 来检测拥塞。正如 RED 首字母缩写的 ” 晚期 ” 所暗示的那样，网关必须在不得不抛弃数据包之前抛弃数据包，以便告诉发送端比失常状况下更早的缩小拥塞窗口。换句话说，路由器在缓冲区空间齐全耗尽之前通过抛弃局部数据包，从而使得发送端速度变慢，防止今后抛弃大量数据包。
RED 和 DECbit 的第二个区别在于 RED 如何决定何时抛弃一个包以及抛弃什么包。为了了解根本思维，思考一个简略的 FIFO 队列，与其期待队列齐全填满，而后被迫抛弃每个达到的包 (在第 2.1.3 节中形容的尾抛弃策略)，咱们能够决定在队列长度超过某个 抛弃级别 (drop level) 时，以肯定的概率抛弃达到的包，这一理念被称为 晚期随机丢包(early random drop)。RED 算法定义了如何监控队列长度以及何时丢包的细节。
上面咱们将介绍由 Floyd 和 Jacobson 最后提出的 RED 算法。咱们留神到，发明者和其余钻研人员曾经提出了一些修改意见，然而，要害思维依然与上面介绍的一样，而且以后大多数实现都靠近上面的算法。
首先，RED 应用与原始 TCP 超时计算中应用的加权运行平均值来计算均匀队列长度，即 AvgLen 为
$$\mathsf{AvgLen = (1 – Weight)\ x\ AvgLen + Weight\ x\ SampleLen}$$
其中 0 < Weight < 1, SampleLen为采样测量时的队列长度。在大多数软件实现中，每次有新数据包达到网关时都测量队列长度，在硬件中，能够以某个固定的采样距离进行计算。
应用均匀队列长度而不是刹时队列长度的起因是它可能更精确的体现拥塞。因为互联网流量的爆发式个性，队列可能很快被塞满，而后又疾速被清空。如果一个队列大部分工夫都是空的，那么就不应该认为产生了拥塞。因而，加权运行均匀计算试图通过过滤掉队列长度的短期变动来检测长期拥塞，如图 35 的左边局部所示。能够把运行平均值设想成低通滤波器，其中 Weight 决定滤波器的时间常数，如何抉择这个时间常数的问题将在上面探讨。
其次，RED 有两个触发特定流动的队列长度阈值: MinThreshold和 MaxThreshold。当报文达到网关时，RED 将以后AvgLen 与这两个阈值依照如下规定进行比拟:
if AvgLen <= MinThreshold
queue the packet
if MinThreshold < AvgLen < MaxThreshold
calculate probability P
drop the arriving packet with probability P
if MaxThreshold <= AvgLen
drop the arriving packet 如果均匀队列长度小于上限阈值，则不采取任何措施；如果均匀队列长度大于下限阈值，则始终抛弃报文。如果均匀队列长度在两个阈值之间，那么新达到的数据包以肯定的概率 P 被抛弃，如图 36 所示。P与 AvgLen 的近似关系如图 37 所示。留神，当 AvgLen 处于两个阈值之间时，丢包概率会迟缓减少，在下限达到 MaxP 时，就会抛弃所有包。这背地的基本原理是，如果 AvgLen 达到了上阈值，那么温和的办法 (抛弃一些包) 就不起作用，须要采取严格的措施，即抛弃所有达到的包。这里介绍的办法是从随机丢包间接跳跃到齐全丢包，不过一些钻研表明，从随机丢包平稳过渡到齐全丢包可能更适合。
只管图 37 显示的丢包概率只是 AvgLen 的一个函数，但理论状况要简单一些。实际上，P是 AvgLen 以及最初一个丢包到当初的工夫的函数。具体计算方法如下:
$$\mathsf{TempP = MaxP\ x\ (AvgLen – MinThreshold)\ /\ (MaxThreshold – MinThreshold)}$$
$$\mathsf{P = TempP\ /\ (1 – count\ x\ TempP)}$$
TempP是在图 37 中 y 轴上的变量，count计算排队 (没有被抛弃) 的新包，AvgLen位于两个阈值之间。P随着 count 的减少而迟缓减少，因而间隔上一次丢包的工夫越长，产生丢包的可能性就越来越大。这使得频繁丢包的可能性比距离较长时间丢包的可能性更低。这个计算 P 的额定步骤是由 RED 的发明者引入的，他们察看到，如果没有这一参数，丢包就不能均匀分布，而是偏向于在集中产生。因为某个连贯的数据包很可能是忽然达到的，这种集中丢包很可能造成单个连贯抛弃大量包，而这并不可取。每次往返工夫产生一次丢包就足以导致连贯缩小窗口大小，而屡次丢包可能会导致发送端切换到慢启动。
举个例子，假如咱们将 MaxP 设置为 0.02，count初始化为 0。如果均匀队列长度在两个阈值两头，那么 TempP 和P的初始值将是 MaxP 的一半，即 0.01，意味着此时达到的数据包有 99% 的机会进入队列。随着每收到一个没有被抛弃的间断数据包，P会缓缓减少，当 50 个没有抛弃的数据包达到时，P会翻倍到 0.02。尽管不太可能，但如果 99 个包都达到而没有丢包，P将变为 1，从而保障下一个包肯定会被抛弃。这部分算法的重要之处在于，能够确保随着工夫的推移，丢包的散布大抵平均。
其目标是，当 AvgLen 超过 MinThreshold 时，如果 RED 抛弃一小部分数据包，导致某些 TCP 连贯缩小窗口大小，从而缩小数据包达到路由器的速率。一切顺利的话，AvgLen将会变小，从而防止拥塞。这样能够放弃较短的队列长度，同时维持较高的吞吐量。
留神，因为 RED 操作的是随工夫变动的均匀队列长度，所以刹时队列长度可能比 AvgLen 长得多。在这种状况下，如果收到了一个包，但没有中央放它，那将不得不抛弃。当这种状况产生时，RED 的行为和尾丢包模式统一。RED 的指标之一是，在可能的条件下尽量避免尾丢包行为。
RED 的随机性赋予了算法一个乏味的个性。因为 RED 是随机丢包的，所以决定抛弃特定流的包的概率大抵与流在以后路由器上取得的带宽份额成正比。这是因为发送绝对较多的包的流为随机抛弃提供了更多的候选者。因而，只管并不准确，但 RED 具备某种偏心的资源分配策略。尽管能够说是偏心的，但因为 RED 对高带宽流的影响大于对低带宽流的影响，这减少了 TCP 重启的可能性，从而有可能对高带宽流造成额定的影响。
为了优化幂函数 (吞吐量 - 提早比)，咱们对各种 RED 参数进行了大量剖析，例如MaxThreshold、MinThreshold、MaxP 和Weight, 通过仿真验证了这些参数的性能，结果表明算法对这些参数不太敏感。然而，所有这些剖析和模仿都取决于网络工作负载的特定表征。RED 的真正奉献是提出了一种路由器能够更精确治理其队列长度的机制，而对于不同的流量组合的最优排队长度还是一个正在钻研的课题。
思考两个阈值 MinThreshold 和MaxThreshold的设置。如果流量相当大，那么 MinThreshold 应该足够大，以容许链路利用率放弃一个可承受的高水平。此外，两个阈值之间的差值应该大于一个 RTT 中计算的均匀队列长度的典型增长值。对于明天的互联网流量模型来说，将 MaxThreshold 设置为 MinThreshold 的两倍仿佛比拟正当。此外，因为咱们冀望均匀队列长度在高负载期间能够在两个阈值之间稳定，因而在 MaxThreshold 之上应该有足够的闲暇缓冲区空间来排汇突发的互联网流量，防止路由器被迫进入尾丢包模式。
下面提到 Weight 决定了运行均匀低通滤波器的时间常数，从而为如何抉择适合的 Weight 值提供了线索。回忆一下，RED 试图在拥塞期间通过丢包向 TCP 流发送信号。假如路由器抛弃了来自某个 TCP 连贯的数据包，而后立刻转发来自同一连贯的更多数据包。当这些包达到接收端时，开始向发送端发送反复的 ACK。当发送端看到足够多的反复 ACK 时，将缩小窗口大小。因而，路由器从抛弃一个数据包直到开始看到受影响连贯的窗口大小有所缩小，该连贯至多须要一个往返工夫。如果路由器对拥塞的响应工夫比连贯往返工夫短得多，可能没有多大意义。正如后面提到的，100ms 是对互联网均匀往返工夫的一个不错的估算。因而，Weight的抉择应该可能过滤掉小于 100ms 的队列长度变动。
因为 RED 通过向 TCP 流发送信号来告诉它们加速，你可能想晓得如果疏忽这些信号会产生什么，这通常被称为 无响应流(unresponsive flow) 问题。无响应流应用的网络资源超过了偏心的份额，就像没有 TCP 拥塞管制那样，如果有很多无响应流，可能会导致拥塞解体。一些排队技术，如加权偏心排队，能够通过隔离某些类别的流量来帮忙解决这个问题。还有一些探讨思考创立 RED 的变体，对于无响应流抛弃更多的包。然而，挑战性在于，很难辨别非响应行为和 ” 正确 ” 行为，特地是当流具备各种不同的 RTT 和瓶颈带宽时。
作为一个注脚，15 位驰名的网络钻研人员在 1998 年催促宽泛采纳受 RED 启发的 AQM。这一倡议在很大水平上被忽略了，起因咱们将在下文谈到。然而，基于 RED 的 AQM 办法曾经在数据中心失去了一些胜利的利用。
延长浏览:\
R. Braden, et al. Recommendations on Queue Management and Congestion Avoidance in the Internet. RFC 2309, April 1998.
6.3 可控提早(Controlled Delay)
如上一节所述，RED 从未被宽泛采纳，当然，也素来没有达到对互联网拥塞产生重大影响的必要程度。一个起因是，RED 很难以一种增量的形式进行配置。影响其操作的参数有很多(MinThreshold、MaxThreshold、Weight)，有足够的钻研表明，RED 会依据流量类型和参数设置产生不同的后果(并非所有后果都是无益的)，这就造成了对 RED 的部署有不确定性。
在过来一段时间里，Van Jacobson(因其在 TCP 拥塞方面的工作和最后的 RED 论文的合著者而闻名)与 Kathy Nichols 和其余钻研人员单干，最终提出了一种改良 RED 的 AQM 办法。这项工作被称为 CoDel(发音为 coddle) 管制提早(Controlled Delay) AQM，其根底建设对 TCP 和 AQM 几十年钻研教训的要害见解上。
延长浏览:\
K. Nichols and V. Jacobson. Controlling Queue Delay. ACM Queue, 10(5), May 2012.
首先，队列是网络的重要组成部分，网络中时不时的就会有队列沉积。例如，新关上的连贯可能会将一个窗口的数据包发送到网络中，可能会在瓶颈链路处造成队列。这自身不是问题，网络应该有足够的缓冲能力来排汇这样的突发流量。但如果没有足够的缓冲能力时，就会呈现问题，导致适量丢包。在 20 世纪 90 年代，这被了解为一种需要，即缓冲区至多可能保留一个带宽时延积的包，这一要求可能太大了，随后受到进一步钻研的质疑。但事实是，用来排汇突发流量的缓冲区是必要的。CoDel 的作者将其称为 ” 好队列 ”，如图 38 (a)所示。
当队列长期处于满状态时，就会成为问题。一个放弃满的队列除了给网络减少提早外什么用也没有，而且如果永远不会齐全清空，排汇突发流量的能力也会升高。在这些缓冲区中，大型缓冲区和长久化队列的组合是一种景象，Jim Gettys 将其命名为 Bufferbloat。很显著，设计良好的 AQM 机制会试图防止长期满队列状态。不出意外，长时间放弃满队列而无奈清空的队列被称为 ” 坏队列 ”，如图 38 (b) 所示。
延长浏览:\
J. Gettys. Bufferbloat: Dark Buffers in the Internet. IEEE Internet Computing, April 2011.
因而在某种意义上，AQM 算法的挑战是辨别 ” 好 ” 和 ” 坏 ” 队列，并且只有当确定队列是 ” 坏 ” 时才会触发丢包。实际上，这就是 RED 试图用 weight 参数 (过滤掉暂态队列长度) 做的事件。
CoDel 的翻新之一是关注 停留时间 (sojourn time): 任何给定包在队列中的等待时间。停留时间与链路带宽无关，即便在带宽随工夫变动的链路(如无线链路) 上，停留时间也能提供有用的拥塞批示。一个运行良好的队列将频繁清空，因而，数据包的停留时间接近于零，如图 38 (a)所示。相同，拥塞队列将提早每个数据包，并且最小停留时间永远不会接近于零，如图 38 (b)所示。因而，CoDel 测量停留时间(很容易对每个数据包采样)，并跟踪其是否始终处于某个阈值之上，这一阈值被定义为 ” 持续时间比典型 RTT 更长 ”。
该算法本人抉择正当的默认值，而不要求运营商确定使 CoDel 失常工作的参数。算法应用 5ms 作为指标停留时间，以及 100ms 的滑动测量窗口。与 RED 一样，直觉上，100ms 是互联网流量的典型 RTT，如果拥塞持续时间超过 100ms，可能会进入 ” 坏队列 ” 区域。所以 CoDel 监控绝对于指标 5ms 的勾留工夫，如果指标超过 100ms，就是采取行动的时候，通过丢包缩小队列(或显式标记拥塞告诉)。抉择 5ms 是因为接近于零(为了更好的提早)，但不会小到队列会会清空。值得注意的是，有对于这些数值抉择的大量试验和模仿，但更重要的是，算法仿佛对它们不太敏感。
总之，CoDel 在很大水平上疏忽了持续时间小于 RTT 的队列，但一旦队列持续时间超过 RTT，就开始采取行动。该算法对互联网 RTT 进行了正当的假如，并且无需配置参数。
另一个奥妙之处在于，只有察看到的停留时间放弃在指标上方，CoDel 就会迟缓减少丢包占流量的百分比。正如第 7.4 节中进一步探讨的那样，TCP 吞吐量已被证实与丢包率的平方根成反比。因而，只有停留时间放弃在指标上方，CoDel 就会稳步减少丢包率，与丢包次数的平方根成正比。实践上，这样做的后果是导致受影响的 TCP 连贯的吞吐量线性降落，最终将导致流量缩小，从而容许队列清空，使停留时间回到指标以下。
在 Nichols 和 Jacobson 的论文中有更多对于 CoDel 的细节，包含大量模仿，表明其在各种场景中的有效性。该算法曾经在 RFC 8289 中被 IETF 标准化为 ” 实验性 ” 算法，也实现在了 Linux 内核中，从而有助于它的部署。特地是，CoDel 在家庭路由器 (通常基于 Linux) 中提供了价值，这是端到端门路上的一个点(请参见图 39)，通常会受到缓冲区收缩的影响。
6.4 显式拥塞告诉
尽管 TCP 拥塞管制机制最后是基于丢包作为次要拥塞信号，但人们早就意识到，如果路由器发送更明确的拥塞信号，TCP 能够做得更好。也就是说，与其抛弃一个数据包并假如 TCP 最终会留神到 (例如，因为反复 ACK 的到来)，如果可能标记数据包并持续将其发送到目的地，任何 AQM 算法都能够做得更好。这个想法体现在了 IP 和 TCP 报头的变动中，被称为 显式拥塞告诉(ECN, Explicit Congestion Notification)，在 RFC 3168 中定义。
延长浏览:\
K. Ramakrishnan, S. Floyd, and D. Black. The Addition of Explicit Congestion Notification (ECN) to IP to IP”). RFC 3168, September 2001.
具体来说，通过将 IP TOS字段中的两个比特作为 ECN 比特来实现反馈机制。发送端设置一个比特示意具备 ECN 能力，即可能响应拥塞告诉，这被称为 ECT 位(ECN-Capable Transport)。当产生拥塞时，另一个比特位由端到端门路上的路由器基于所运行的 AQM 算法计算并设置，被称为 CE 位(Congestion Encountered)。
除了 IP 报头中的这两位 (与传输层无关)，ECN 还包含向 TCP 报头增加两个可选标记。一个是ECE(ECN-Echo)，接收端通过设置这个选项向发送端示意其收到了一个设置了CE 位的数据包。另一个是CWR(Congestion Window Reduced)，发送端向接收端示意曾经减小了拥塞窗口。
尽管 ECN 当初是 IP 报头 TOS 字段 8 位中的 2 位的规范定义，并且强烈建议反对 ECN，但并不是必须的。此外，还没有举荐的 AQM 算法。好的 AQM 算法应该满足一系列要求，和 TCP 拥塞控制算法一样，每种 AQM 算法都有其优缺点，所以须要大量探讨。
6.5 入口 / 进口队列
咱们曾经在网络外部 (即本章中介绍的 AQM 算法) 和网络边缘 (即前几章中介绍的基于 TCP 的算法) 的拥塞管制办法之间画了一条清晰的线，但线条并不一是那么明确。要理解这一点，只需将端到端门路设想为在发送主机的内核 / 设施接口上有一个 入口队列 (ingress queue)，在接管主机的设施 / 内核接口上有一个 进口队列(egress queue)[1]。随着虚构交换机和网卡对虚拟化的反对变得越来越广泛，这些边缘队列可能会变得越来越重要。
[1] 容易混同的是，从网络门路的角度来看，入口队列是发送主机上的出站 (进口) 队列，而进口队列是接管主机上的入站 (入口) 队列。如图 40 所示，咱们从网络的角度应用术语入口和进口。
图 40 展现了这一观点，两个队列都位于 TCP 之下，提供了向端到端门路注入第二段拥塞管制逻辑的机会。CoDel 和 ECN 就是这个想法的例子，并且曾经在 Linux 内核的设施队列级别实现。
这能起作用吗？一个问题是数据包是在入口抛弃还是在进口抛弃。当在入口 (在发送主机上) 抛弃时，TCP 会在 Write 函数的返回值中收到告诉，从而导致 ” 遗记 ” 发送了数据包，只管 TCP 的确缩小了拥塞窗口来响应失败的写操作，但接下来还会发送这个包。相同，在进口队列 (在接管主机上) 抛弃数据包，意味着 TCP 发送方将不晓得重传数据包，直到应用其规范机制之一 (例如，三个反复 ACK 或者超时) 检测到丢包。当然，在进口实现 ECN 是有益处的。
当咱们把这个探讨放在拥塞管制的大环境中思考时，能够得出两个乏味的论断。首先，Linux 提供了一种不便而平安的形式将新代码 (包含拥塞管制逻辑) 注入内核，即应用eBPF(extended Berkeley Packet Filter)。eBPF 在许多其余环境中也正在成为一项重要的技术。用于拥塞管制的规范内核 API 曾经移植到 eBPF，大多数现有的拥塞控制算法也曾经移植到这个框架上。这简化了试验新算法的工作，也能够避开在 Linux 内核里部署现有算法优化的阻碍。
延长浏览:\
The Linux Kernel. BPF Documentation.
其次，通过显式的将入口 / 进口队列裸露给决策过程，咱们为构建拥塞管制机制关上了大门，该机制蕴含一个 ” 决定何时传输数据包 ” 的组件和一个 ” 决定排队还是抛弃数据包 ” 的组件。在第 7.1 节介绍 On-Ramp 时，咱们会看到一个采纳翻新办法应用这两个组件的机制示例。
你好，我是俞凡，在 Motorola 做过研发，当初在 Mavenir 做技术工作，对通信、网络、后端架构、云原生、DevOps、CICD、区块链、AI 等技术始终保持着浓重的趣味，平时喜爱浏览、思考，置信继续学习、一生成长，欢送一起交流学习。\
微信公众号：DeepNoMind
本文由 mdnice 多平台公布