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