网络传输问题实质上是对网络资源的共享和复用问题，因而拥塞管制是网络工程畛域的外围问题之一，并且随着互联网和数据中心流量的爆炸式增长，相干算法和机制呈现了很多翻新，本系列是收费电子书《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多平台公布