网络传输问题实质上是对网络资源的共享和复用问题，因而拥塞管制是网络工程畛域的外围问题之一，并且随着互联网和数据中心流量的爆炸式增长，相干算法和机制呈现了很多翻新，本系列是收费电子书《TCP Congestion Control: A Systems Approach》的中文版，残缺介绍了拥塞管制的概念、原理、算法和实现形式。原文: TCP Congestion Control: A Systems Approach

第5章 回避算法(Avoidance-Based Algorithms)

对TCP拥塞管制学术文献的回顾能够发现，最后在1988年和1990年别离引入的TCP Tahoe和Reno机制与1994年开始的钻研流动之间存在着显著不同，次要标记是引入了一种被称为TCP Vegas的代替计划，从而引发了大量比拟钻研和代替设计，并继续了25年以上的工夫。

延长浏览:\
L. Brakmo, S. O’Malley and L. Peterson TCP Vegas: New Technique for Congestion Detection and Avoidance. ACM SIGCOMM ‘94 Symposium. August 1994. (Reprinted in IEEE/ACM Transactions on Networking, October 1995).

只管截止目前所介绍的办法都将丢包视为拥塞信号，并试图在拥塞产生后对管制拥塞做出反馈，但TCP Vegas采取了一种基于回避(avoidance-based) 的办法应答拥塞: 它试图检测吞吐率的变动来发现拥塞，并在拥塞重大到足以导致丢包之前调整发送速率。本章将介绍个别的"Vegas策略"，以及随着工夫的推移引入的三个不同的例子。这类钻研的低潮是谷歌现在所提倡的BBR算法。

5.1 TCP Vegas

TCP Vegas背地的根本思维是依据测量的吞吐率和预期吞吐率的比拟来调整发送速率。能够从图29中给出的TCP Reno图示中直观看到，最下面的图显示了连贯的拥塞窗口，给出的信息与前一章雷同。两头和底部的图形容了新的信息: 两头的图显示了在发送端处测量的均匀发送速率，而底部的图显示了在瓶颈路由器处测量的均匀队列长度，三个图在工夫上是同步的。在4.5秒到6.0秒之间(暗影区域)，拥塞窗口减少(上图)，咱们预计察看到的吞吐量也会减少，但实际上却放弃不变(中图)，这是因为吞吐量的减少不能超过可用带宽，超过可用带宽之后，任何窗口大小的减少只会导致占用更多的瓶颈路由器缓冲区空间(下图)。

一个乏味的比喻能够用来形容图29中所示景象，即冰上驾驶。速度计(拥挤窗口)可能会显示速度是每小时30英里，但通过看车窗里面，看到步行通过你的人们(测量的吞吐率)，你晓得本人的速度不超过每小时5英里。在这种类比中，发动机无意义的空转就像发送的额定数据包一样，只是无用的停留在路由器缓冲区中。

TCP Vegas用这种思维来测量和管制连贯传输中的额定数据量，这里的"额定数据"指的是如果发送端可能齐全匹配网络可用带宽，就不会传输的数据。TCP Vegas的指标是在网络中保护"正确的"额定数据量。显然，如果一个发送端发送了太多额定数据，将导致长时间的提早，并可能导致拥塞。不太显著的是，如果一个连贯发送的额定数据太少，就无奈对可用网络带宽的短暂减少做出足够快的响应。TCP Vegas基于估算网络中额定数据量的变动做出回避拥塞动作，而不仅仅基于丢包，接下来咱们具体介绍这个算法。

首先，将给定流的BaseRTT定义为当流没有拥塞时数据包的RTT。在实践中，TCP Vegas将BaseRTT设置为测量到的所有往返工夫的最小值，通常是在路由器因为该流造成队列减少之前，连贯发送的第一个包的RTT。如果假如没有溢出连贯，那么预期吞吐量为

$$\mathsf{ExpectedRate = CongestionWindow\ /\ BaseRTT}$$

其中CongestionWindow是TCP拥塞窗口，假如(为了这个探讨的目标)等于传输中的字节数。

其次，TCP Vegas计算以后发送速率ActualRate。计算方法是记录一个辨别数据包(distinguished packet)的发送工夫，记录从数据包发送到接管到它的ACK之间传输了多少字节，并当ACK信息达到时计算辨别数据包的样本RTT，最初传输字节数除以样本RTT，此计算在每次往返工夫中执行一次。

第三，TCP Vegas比拟ActualRate和ExpectedRate并相应调整窗口。Diff = ExpectedRate - ActualRate，留神，依据定义，Diff为正或0。只有当测量样本RTT小于BaseRTT时，才会呈现ActualRate > ExpectedRate的状况，如果产生这种状况，将BaseRTT改为最新采样的RTT。咱们还定义了两个阈值， < ，别离对应于网络中额定数据太少和太多的状况。当Diff < 时，TCP Vegas在下一个RTT期间线性减少拥塞窗口；当Diff > 时，TCP Vegas在下一个RTT期间线性缩小拥塞窗口。当 < Diff < 时，TCP Vegas放弃拥塞窗口不变。

直观来看，理论吞吐量与预期吞吐量之间的差距越远，网络中的拥塞就越大，意味着发送速率应该升高，阈值就会触发发送率降落。另一方面，当理论吞吐率太靠近预期吞吐率时，连贯就会面临无奈利用可用带宽的地步，阈值就会触发发送率的减少。总的指标是在网络中保留的额定字节数介于和之间。

图30显示了TCP Vegas拥塞防止算法。上图显示了拥塞窗口，与本章给出的其余图示雷同。下图显示了预期和理论的吞吐量，这决定了如何设置拥塞窗口。下图最能阐明算法是如何工作的。黑白线显示了ExpectedRate，而黑线显示了ActualRate。暗影局部给出了和阈值区间，暗影带的顶部间隔ExpectedRate有 KBps的间隔，底部间隔ExpectedRate有 KBps的间隔，指标是将ActualRate放弃在暗影区域内的这两个阈值之间。每当ActualRate低于暗影区域(即离ExpectedRate太远)，TCP Vegas就会放心网络中有太多的包被缓冲，从而缩小拥塞窗口。同样，每当ActualRate超过暗影区域(即太靠近ExpectedRate)，TCP Vegas就会放心网络没有被充分利用，因而会减少拥塞窗口。

因为方才介绍的算法比拟理论和冀望吞吐量率与和阈值之间的差别，所以这两个阈值是依照KBps定义的。然而，思考连贯在网络中占用了多少额定的包缓冲区可能更精确。例如，在BaseRTT为100ms，数据包大小为1 KB的连贯上，如果 = 30 KBps以及 = 60 KBps，那么能够认为指定该连贯须要在网络中占用至多3个额定的缓冲区，并且指定该连贯在网络中占用不超过6个额定的缓冲区。和的设置在Vegas第一次部署的理论环境中工作得很好，但正如下一节将会介绍的，这些参数将继续依据一直变动的环境进行调整。

最初，留神TCP Vegas以线性形式缩小拥塞窗口，仿佛与须要指数缩小来确保稳定性的规定相冲突。这是因为TCP Vegas在超时产生时的确应用指数缩小，方才介绍的线性降落是拥塞窗口的晚期降落，产生在拥塞产生以及数据包开始被抛弃之前。

5.2 不同的假如

为了响应不同网络的假如，TCP Vegas以及相似Vegas的拥塞回避办法曾经随着工夫的推移进行了调整。Vegas从未像Reno那样被宽泛应用，所以这些批改通常更多的是由实验室钻研而不是宽泛的事实教训驱动的，但对算法的欠缺有助于咱们对基于回避的算法的了解。咱们在这里总结了其中一些见解，但在第7章中咱们将持续介绍为特定用例定制拥塞控制算法的一般性主题。

5.2.1 FAST TCP

第一种受到Vegas启发的机制是FAST TCP，它对Vegas进行了改良，使其在具备大带宽时延积的高速网络上更加高效。其次要想法是在算法试图找到可用的"传输中"带宽(数据包在网络中被缓冲之前)的阶段更踊跃的减少拥塞窗口，而后在算法开始与其余流在瓶颈路由器上抢夺缓冲区时体现的激进。FAST还倡议将值调整为大概30个包。

除了在具备大带宽时延积的网络中治理拥塞之外，放弃流水线满也是一个实质性的挑战，对于FAST还有两个值得注意的事项。首先，TCP Reno和TCP Vegas都是基于直觉和大量试错的后果，而FAST是基于优化实践(起初这被用来解释为什么Vegas行得通)。其次，与咱们所知的所有其余拥塞控制算法不同，FAST的实现只能作为专有的解决方案。

延长浏览:\
S. Low, L. Peterson, and L. Wang. Understanding TCP Vegas: A Duality Model. Journal of the ACM, Volume 49, Issue 2, March 2002.
5.2.2 TCP Westwood

尽管Vegas的动机是在产生丢包之前检测并防止拥塞，但TCP Westwood (TCPW)的动机次要是意识到数据包失落并不总是拥塞的牢靠指标。这在无线连接方面尤其显著，在Vegas被提出时这还是陈腐事物，但在TCPW呈现时曾经变得很广泛了。无线链路常常会因为无线信道上未纠正的谬误而丢包，而这与拥塞无关，因而，须要用另一种办法检测拥塞。乏味的是，其最终后果与Vegas有些类似，TCPW还试图通过查看ACK返回胜利交付的数据包的速率来确定瓶颈带宽。

当产生丢包时，因为还不晓得丢包是因为拥塞还是因为链路相干，TCPW不会立刻将拥塞窗口缩短一半，取而代之的是会预计在丢包产生之前流量的流动速度，这是一种比TCP Reno更温和的让步模式。如果丢包与拥塞相干，则TCPW应该以丢包前可承受的速率发送。如果丢包是由无线谬误造成的，则TCPW不会升高发送率，并且还会开始再次进步发送率，以充分利用网络。其后果是一个在固定链接上相似于Reno，但在有损链接上性能取得了实质性晋升的协定。

无线链路上拥塞控制算法的优化依然是一个具备挑战性的问题，更简单的是，WiFi和挪动蜂窝网络具备不同的个性。咱们将在第7章从新探讨这个问题。

5.2.3 New Vegas

最初一个例子是New Vegas (NV)，它是对Vegas基于提早的办法的一种适应，实用于链路带宽为10Gbps或更高的数据中心网络，其RTT通常在几十微秒内。这是咱们在第7章将介绍的一个重要用例，以后的指标是建设一些直观感触。

为了了解NV的根本思维，假如咱们为每个收到ACK的包绘制Rate与CongestionWindow的关系图。出于简化目标，Rate仅仅是CongestionWindow(以字节为单位)与被ACK(以秒为单位)的数据包RTT的比率。留神，为了简略起见，探讨中应用了CongestionWindow，而实际上NV应用的是传输中(未收到ACK)的字节。如图31所示，咱们用竖条(而不是点)示意因为测量中的刹时拥塞或噪声而导致的CongestionWindow值。

条形图顶部的最大斜率示意过来所能达到的最佳程度。在一个通过良好调整的零碎中，条形图的顶端由一条穿过原点的直线作为边界。这个想法是，只有网络没有拥塞，每RTT发送的数据量增加一倍，速率就会增加一倍。

Rate和CongestionWindow的新测量值能够落在边界线左近(图中的彩色菱形)或上面(图中的蓝色菱形)。在该直线上方的测量会导致NV通过减少其斜率来自动更新该直线，因而测量后果将落在新直线上。如果新的度量值靠近这条线，那么NV会减少CongestionWindow。如果测量值低于这条线，那就意味着和之前较低的拥塞窗口相似的性能。图31所示示例中，咱们看到了与CongestionWindow=12相似的性能，所以缩小了CongestionWindow。在新的测量有噪声的状况下，这种升高是指数级的，而不是霎时的。为了过滤掉不好的度量值，NV收集了许多度量值，而后在做出拥塞判断之前应用最好的度量值。

5.3 TCP BBR

BBR(Bottleneck Bandwidth and RTT)是谷歌钻研人员开发的一种新的TCP拥塞控制算法。像Vegas一样，BBR是基于提早的，意味着它试图检测缓冲区的增长，以防止拥塞和丢包。BBR和Vegas都应用最小RTT和察看到的瓶颈带宽(依据一段时间距离计算)作为次要管制信号。

图32显示了BBR的根本思维。假如某个网络的瓶颈链路还有一些可用带宽和队列容量，随着拥塞窗口关上，更多的数据被发送，最后因为瓶颈未满，提早没有减少，吞吐量会减少(下图)。而后，一旦速率达到瓶颈带宽，就开始填充队列。此时，RTT回升，但没有察看到吞吐量回升，这是拥塞阶段的开始。这个图表实际上是咱们在图29中4.5到6.0秒工夫框架中看到的简化版本。

像Vegas一样，BBR的指标是精确确定队列刚刚开始填充的那个点，而不是像Reno那样始终继续到填满缓冲区并导致丢包。BBR的很多工作都是围绕着进步定位最佳点的机制的灵敏度，其中有许多挑战: 测量带宽和提早是有噪声的；网络条件是动静的；以及在与BBR和非BBR流竞争带宽时对偏心的长期谋求。

与其余办法相比，BBR的一个显著特点是不齐全依赖于CongestionWindow来决定有多少数据被传输。值得注意的是，BBR还试图平滑发送者将数据送入网络的速率，以防止会导致适度排队的突发峰值流量。现实条件下，咱们心愿以完全符合瓶颈的速度发送数据，从而在不造成队列沉积的状况下实现尽可能高的吞吐量。尽管大多数TCP变体应用ACK达到来触发数据的发送，从而确保传输中未确认数据的数量放弃不变，但BBR创立了瓶颈带宽的估算，并应用本地调度算法以该速率发送数据。ACK在更新无关网络的状态方面依然施展着重要作用，但并不间接用于调整传输速度，这意味着提早的ACK不会导致传输量的忽然暴发。当然，CongestionWindow依然用于确保能够发送足够的数据以放弃流水线满，并确保传输中的数据量不会比带宽提早积大太多，从而防止队列溢出。

为了保护以后RTT和瓶颈带宽的最新视图，有必要在以后预计的瓶颈带宽高低继续探测。因为竞争流流量的缩小、链路属性(如无线链路)的变动或路由的变动，兴许能够取得更多带宽。如果门路变动了，RTT也有可能会变。为了检测RTT的变动，须要发送更少的流量，从而清空队列。为了检测可用带宽的变动，须要发送更多的流量。因而，BBR在其以后预计的瓶颈带宽的高低同时探测，如果有必要，会更新估算，并相应更新发送速率和CongestionWindow。

图33的状态图显示了程序探测可用带宽和最小RTT的过程。在尝试建设门路上的可用带宽的激进启动阶段之后，升高发送速率以清空队列，而后算法进入图的内环，在内环中，定期检查在较低发送速率下是否有更低的提早，或者在较高发送速率下是否有更高的吞吐量。在一个绝对较长的工夫范畴内(几秒)，算法进入ProbeRTT状态，将其发送速率升高两倍，以齐全清空队列并测试是否有更低的RTT。

该办法乏味的中央在于，当一个大流在ProbeRTT状态下显著升高发送速率时，该流对队列提早的奉献将降落，这将导致其余流同时看到一个新的、更低的RTT，并更新它们的估算。因而，当队列实际上是空的或靠近空的时候，流体现出同步RTT估算的趋势，从而进步了估算的准确性。

BBR正在踊跃开发并在疾速倒退中，撰写本文时最新版本是2。其次要焦点是偏心，例如，一些晚期试验表明，CUBIC流在与BBR流竞争时取得的带宽缩小了100倍，而其余试验表明，BBR流之间可能存在不公平性。BBR版本1对丢包不敏感，特地是当门路上的缓冲量绝对较低时，可能会导致较高的丢包率。因为BBR的几种实现当初正在不同环境中进行试验，包含在谷歌的外部主干网以及更宽泛的互联网中，人们正在收集教训来进一步欠缺设计。IETF的拥塞管制工作组正在主持对于正在进行的设计和试验的探讨。

延长浏览:\
N. Cardwell, Y. Cheng, C. S. Gunn, S. Yeganeh, V. Jacobson. BBR: Congestion-based Congestion Control. Communications of the ACM, Volume 60, Issue 2, February 2017.

你好，我是俞凡，在Motorola做过研发，当初在Mavenir做技术工作，对通信、网络、后端架构、云原生、DevOps、CICD、区块链、AI等技术始终保持着浓重的趣味，平时喜爱浏览、思考，置信继续学习、一生成长，欢送一起交流学习。 \
微信公众号：DeepNoMind

本文由mdnice多平台公布