当前位置：首页 > APNet > 正文

【APNet'21】思路超清奇！Conjecture现代互联网拥塞控制中纳什均衡存在的猜想

APNet
2022-10-18
1583
更新：2023-01-04 21:46:01

# 摘要

互联网的拥塞控制领域目前正处于前所未有的范式转变之中。最近的一项测量研究发现，BBR（谷歌于2016年推出的一种拥塞控制算法）已被迅速采用，并在Alexa排名前20000的网站中部署了20%以上。谷歌、Dropbox和Spotify的早期部署结果令人鼓舞，这表明BBR有可能取代传统的基于丢包的拥塞控制算法，如CUBIC。在本文中，我们研究了CUBIC和BBR之间的相互作用，并证明了潜在的相互作用可以建模为一个标准形式的博弈（a normal form game）。我们的博弈论分析和试验台测量表明，虽然BBR在互联网上似乎比CUBIC取得了更好的性能，但随着BBR流量比例的增加，这种优势将减少。拥塞控制算法在互联网上的分布可能会达到纳什均衡，在纳什均衡中，没有流量有动机从CUBIC切换到BBR，反之亦然。我们还发现，在这种纳什均衡中CUBIC流和BBR流的分布将主要取决于瓶颈缓冲区的大小，而略微取决于流的RTT分布。我们的结果表明，未来的互联网可能会更加异构，缓冲区大小将继续对互联网拥塞控制产生重大影响。

# 1 导言

如今，BBR和CUBIC是互联网上两种主要的拥塞控制算法。谷歌、Spotify和Dropbox推出的BBR（及其变种BRRv2）的明显性能优势和良好部署结果可能会让网站运营商评估是否应该采用新的拥塞控制算法。最近的一项测量研究发现，Alexa排名前20000的网站中有20%以上已经采用BBR来服务HTTP流量。由于这些早期采用者中的大多数都是流视频的网站，因此BBR已经贡献了互联网上40%以上的下行流量。互联网拥塞控制领域的这一重大变化值得注意，因为BBR代表了拥塞控制的范式转变。传统的拥塞控制算法（如CUBIC）依靠丢包来推断拥塞，而BBR则使用瓶颈带宽和RTT估计。通过这样做，BBR避免了填充深度缓冲区以保持较低的延迟，并且对随机数据包丢失更具弹性。

关于CUBIC和BBR之间的相互作用已有许多研究。然而，与以往的研究主要关注流量级别的公平性不同，我们试图回答以下问题：**鉴于近年来BBR的积极采用，我们预计互联网将如何发展？期待整个互联网在不久的将来转向BBR和/或其变体是否合理？**

最近的部署将更好的吞吐量作为从CUBIC切换到BBR的关键原因。这并不奇怪，如果切换将导致更高的吞吐量，那么网站会决定从一种TCP变体切换到另一种，这似乎是完全合理的。因此，我们可以抽象地将互联网看作一个由n个流组成的系统，并将其建模为一个标准形式的博弈。在博弈论中，标准形式博弈是一个博弈的标准表示形式，其中博弈方对结果有偏好，在我们的例子中，这是更高的吞吐量。

我们对这种标准形式博弈的分析表明，鉴于BBR和CUBIC之间相互作用的特点，必然存在纳什均衡（NE）。博弈中的纳什均衡是博弈双方之间的策略分配，其中没有一方通过改变策略而获得任何收益。这本质上意味着一组n个流最终将收敛到拥塞控制算法的分布，其中没有任何流将有任何动机从CUBIC切换到BBR，反之亦然，因为这样做不会导致吞吐量的增加。我们验证了这种纳什均衡的存在，并使用一组试验台实验测量了网络参数（如瓶颈链路容量、缓冲区大小、流数和RTT）的影响。我们的结果表明，网元上拥塞控制算法的分布主要取决于瓶颈缓冲区的大小，而在一定程度上取决于流的RTT分布。

# 2 已知BBR和CUBIC之间的相互作用

CUBIC和BBR在深度缓冲区中的行为非常不同。由于CUBIC是基于丢包的，它将继续填充缓冲区，直到经历数据包丢包。另一方面，BBR限制其cwnd，从而阻止其填充深度缓冲区。虽然此行为旨在允许BBR保持较低的排队延迟，但竞争CUBIC流将更具攻击性（吞吐量方面），并占据更大的带宽份额。另一方面，在浅缓冲区中，CUBIC的吞吐量将受到限制，因为由于频繁的数据包丢包，cwnd将不断减少。因此，我们进行了以下一般性观察，这已在先前的研究中得到验证。

**观察1**：当在缓冲区较深的瓶颈处竞争时，CUBIC往往比BBR具有更高的吞吐量；当缓冲区较浅时，情况正好相反。

我们通过一个简单的实验来研究RTT的影响，其中一个CUBIC流和一个BBR流共享一个具有不同缓冲区大小的20 Mbps瓶颈。两个流同时运行两分钟，我们在图1中绘制了BBR的稳态吞吐量，并与CUBIC流的吞吐量进行了归一化。正如预期的那样，我们看到BBR的吞吐量是缓冲区大小的平滑函数。我们还看到，在每种情况下都存在一些缓冲区大小，其中CUBIC和BBR获得瓶颈带宽的相等份额，即归一化吞吐量等于1。根据这一结果，我们可以进行下一观察：

**观察2**：当单个BBR流在瓶颈处与单个CUBIC流竞争时，必须存在一些阈值瓶颈缓冲区大小为$$T_{fair}$$，以便当瓶颈缓冲区大小$$Buff<T_{fair}$$时，BBR流获得比CUBIC流更高的吞吐量，当$$Buff>T_{fair}$$时，CUBIC流获得比BBR更高的吞吐量。

除了缓冲区大小，BBR的吞吐量还取决于瓶颈处BBR和CUBIC流的数量。我们同时运行20条CUBIC/BBR流，通过100 Mbps瓶颈。在每次迭代中，我们更改运行BBR和CUBIC的流的百分比。我们通过图2中竞争CUBIC流的平均每流吞吐量标准化了BBR的每流吞吐量。所有流的RTT均为40 ms，并运行2分钟。我们的结果表明，随着瓶颈链路中BBR流百分比的增加，BBR流的吞吐量会降低。当使用不同的缓冲区大小重复时，此行为是一致的，并且如果缓冲区较大且BBR流的数量大于阈值，则BBR流的平均吞吐量可能会降至CUBIC流的平均吞吐量以下。因此，我们提出以下观察：

**观察3**：随着瓶颈处BBR流百分比的增加，该瓶颈处BBR流的每流平均吞吐量降低。

早期的测量研究发现，当与CUBIC流竞争时，少量BBR流可以获得不成比例的大量瓶颈带宽。如图3所示，固定容量瓶颈链路上的BBR流的聚合带宽将随着流数量的增加而增加，因此结果是总吞吐量呈次线性增加（sub-linear increase），因此每流吞吐量将随着BBR流的增加而降低。

BBR和CUBIC拥塞控制算法也被认为是RTT不公平的。CUBIC是基于cwnd的，在长RTT路径中受到伤害，因为它可以比另一个具有短RTT路径的CUBIC流更频繁地增加其cwnd。另一方面，与RTT较短的流量相比，BBR倾向于支持RTT较长的流量。这是因为当BBR变为cwnd-limited时，它会将两倍于BDP（带宽延迟乘积）的数据包量放入管道中（飞行报文）。我们在观察4中总结了这些发现。

**观察4**：当两个BBR流在瓶颈处竞争时，RTT较长的流将获得比RTT较短的流更高的带宽。当两个CUBIC流在瓶颈处竞争时，RTT较短的流将比RTT较长的流获得更高的带宽。

# 3 将互联网建模为标准形式博弈

在本节中，我们将把在CUBIC和BBR之间选择流量的问题表述为一个标准形式的博弈，并使用第2节中的观察结果对其进行分析。

为了研究一组n个流的行为，我们将每个流建模为一个独立的代理/agent,其（i）可以决定流应该运行BBR还是CUBIC；（ii）知道它的当前吞吐量，以及它若是切换到替代算法（如果所有其他流不变）的吞吐量。我们假设网站可以通过CUBIC和BBR之间的A/B测试来确定（ii），并且所有流都倾向于采用允许其实现更高吞吐量的TCP变体。虽然发送方通常关心网络参数的组合，但这些参数的权重可能因站点而异。然而，改进的吞吐量被称为所有主要公司报告的关键因素，报告了从CUBIC到BBR的切换，因此为了简单起见，我们只考虑在我们的分析中的吞吐量。基于这些假设，我们有效地建立了一个标准形式博弈，其中网站/发送者可以通过两种相互排斥的策略来最大化吞吐量：（i）BBR；或（ii）CUBIC。在本节中，我们认为纳什均衡应该存在。

## 3.1 两条流博弈

考虑一个具有两个发送端$$S_1$$和$$S_2$$共享一个公共瓶颈链路的简单网络。每个发送方可以选择CUBIC或BBR。我们将这两个流的RTT分别表示为$$RTT_1$$和$$RTT_2$$。在不丧失一般性的情况下，我们假设$$RTT_1>RTT_2$$。我们还将假设瓶颈队列是一个简单的FIFO队列，并且不部署任何其他队列规则或AQM。使用两个发送方和两种拥塞控制算法，总共可以有四种可能的场景或组合。我们在表1中列举了这些可能的情况。

考虑两个流$$S_1$$和$$S_2$$选择不同的算法的情况，即场景2和3。从观察结果2中，我们知道对于场景2，存在一个阈值缓冲区大小$$T_2$$，这样当瓶颈缓冲区大小$$Buff>T_2$$时，CUBIC流将获得更多带宽（CUBIC wins），当$$Buff<T_2$$时，BBR流将获得更多带宽（BBR wins）。类似地，对于场景3，存在缓冲区大小T3，使得当$$Buff>T3$$时，CUBIC流获胜，而当$$Buff<T3$$时，BBR流获胜。总之，$$T_2$$和$$T3$$分别是场景2和场景3中BBR战胜CUBIC的阈值缓冲区大小。

场景3中的BBR流的RTT高于场景2中的BBR流。从观察结果3中，我们知道RTT越高的BBR流越有效。这意味着场景3中的BBR将比场景2中的更具攻击性，因此CUBIC将需要场景3中更深的缓冲区来与BBR配合。因此，我们得出结论，$$T3>T_2$$。这种关系也可以在图1中看到。

在本文中，我们考虑了表2中所示的3种不同的机制，在每一种情况下，我们为发送者标记得到更高带宽的结果，即“W”（胜利者）和另一发送者作为“L”（失败者）的结果。选择CUBIC或BBR作为拥塞控制算法的发送方分别用字母C和B表示，并且为了便于分析，还突出显示了每种情况下获胜的拥塞控制变量。特别是，我们看到：

（1）当$$Buff<T_2$$：$$S_1$$肯定会选择BBR，而不管$$S_2$$决定选择什么。在哪种划算方面来讲，B是$$S_1$$的主导策略。$$S_2$$将选择实现更高吞吐量的算法，我们得到纳什均衡$$(B，∗)$$.

（2）当$$T_2<Buff<T3$$：B仍然是$$S_1$$的主导策略时，我们再次得到纳什均衡$$(B，∗)$$.

（3）当$$T3<Buff$$：C现在是$$S_2$$的主导策略时，我们得到了一个纳什均衡$$(∗,C$$） 。

通过列举所有可能的情形，我们有效地证明了2条流系统必须存在唯一的纳什均衡。我们通过实验验证了我们的预测，其中两个流在20 Mbps瓶颈处竞争，$$RTT_1$$=80 ms，$$RTT_2$$=40 ms。对于小于较小流BDP两倍的缓冲区大小，网元处于（B,B），对于所有其他缓冲区大小高达10 BDP的网元处于（B,C）。

## 3.2 n个流的猜想

虽然我们可以使用第3.1节中的方法对具有n个流的系统建模，但列举所有可能的场景并不是证明纳什均衡存在的可行方法。然而，一些形式的标准形式博弈已被广泛研究，并被证明具有纯策略纳什均衡（pure strategy Nash Equilibrium）。这些博弈显示出独特的特性，如收益的连续性和有界性，以及结果的可测量性，这些特性可以很容易地扩展到我们的环境中。今后的工作仍然是检查是否有可能将n流系统建模为这些标准形式的博弈之一，以便我们可以应用已知的结果。

n条流系统的复杂性源于场景数量的指数化，以及流可能具有不同的RTT这一事实，这使得枚举所有可能性变得非常困难。然而，我们的实验中有两个关键的观察结果启发我们提出下面的猜想1：（1）随着BBR流量比例的增加，吞吐量收益将减少（参见第2节中的观察结果3）。当BBR流的比例增加超过阈值时，BBR流的平均吞吐量往往会下降到剩余CUBIC流的平均吞吐量以下（见图1）。（2） 当缓冲区较浅时，BBR是具有大RTT的流的主要策略；类似地，当缓冲区较深时，CUBIC是具有较短RTT的流的主要策略。

**猜想1**：在一个有n个流的系统中，可以选择运行CUBIC或BBR，至少会有一个纳什均衡。

# 4 评价

在本节中，我们展示了我们的试验台实验结果：（i）表明NE存在于n个流中（对于n>2），以及（ii）提供了一些关于RTT和缓冲区大小如何影响NE的见解。这些实验在有限的状态空间中验证猜想1，并且不试图复制互联网上所有可能的网络交互（因为这是不可能的）。

**试验台设置**。我们的测试台设置由两台通过1 Gbps链路连接的服务器组成。我们使用Mahimahi生成具有不同RTT的单个iperf发送端。我们使用nfqueue创建具有指定链路容量和缓冲区大小的瓶颈。

**方法**。对于每个网络设置，我们对运行CUBIC或BBR的n个发送端的所有$$2^n$$个可能组合进行3次试验。在每次试验中，发送者发送数据2分钟，我们记录他们的平均每流吞吐量。为了识别网元，我们枚举所有组合，并检查是否存在任何组合，以确保该组合中的单个流在切换到其他TCP变体（所有其他流保持固定）时不会实现更高的吞吐量。由于组合的数量随n呈指数增长，因此我们最多只能对12个流执行此测试。很明显，我们无法用实验证明猜想1。然而，在本节中，我们的目标是验证该猜想在实践中适用于某些n>2的场景，并且没有明显的反例。在我们所有的实验中，我们发现了一个NE，正如我们的猜测所表明的。

**纳什均衡被发现**。在所有情况下，我们都只找到一个NE。所有这些NE都有一个共同的特性，允许我们用一个数字简洁地指定它：CUBIC流的比例。特别是，我们观察到，在n个流的任何NE组合中，如果我们按照流的rtt对流进行排序，那么总是可以写入NE组合，其中m个流选择CUBIC，其余的（n-m） 流量选择BBR。例如，在6流实验中，其中流具有（20 ms、20 ms、50 ms、50 ms、80 ms、80 ms）的RTT分布，如果当50%的流选择CUBIC时存在NE，则NE组合将看起来像（C,C,C,B,B,B）。

也就是说，所有20毫秒流量和一个50毫秒流量选择CUBIC以及所有80毫秒流量和一个50毫秒流量选择BBR。这表明，较小的RTT流量更倾向于CUBIC而不是BBR。我们使用此属性表示具有单个数字的NE组合——NE组合中运行CUBIC的流量百分比（m/n×100）。CUBIC流始终是组合中RTT最小的流。这并不奇怪，因为在运行BBR时，较小的RTT流的性能比较大的RTT流差，反之亦然。

## 4.1 缓冲区大小的影响

在图4中，我们展示了当6、9和12个流以20、50和100 Mbps的速度在3个不同的瓶颈链路上竞争时的网元。在每个实验中，流分为3组，RTT分别为20ms、50ms和80ms。我们让这些流在具有不同缓冲区大小的公共瓶颈中竞争，并在每种情况下记录网元上的拥塞控制算法分布。一般来说，缓冲区越深，BBR上的流量越大。在非常大的缓冲区大小下，NE通常发生在CUBIC和BBR之间的五五分之一附近。

## 4.2 其他网络参数的影响。

我们在图4中的实验结果还表明，链路容量和流量数量对NE中CUBIC和BBR的分布几乎没有影响。由于我们根据最小RTT流（最小RTT乘以瓶颈链路容量）的BDP来确定瓶颈缓冲区的大小，因此链路容量增加引起的任何差异都可以通过缓冲区大小的比例增加来标准化。虽然我们的实验表明，流量的数量对网元组合中拥塞控制算法的分布没有太大影响，但这也可能是我们有限的实验数量造成的。

在图5中，我们绘制了两种不同RTT分布的结果。我们发现，当流量具有较大的RTT时，NE的流量百分比略低。换句话说，RTT分布对NE的影响不大。

# 5 讨论和今后的工作

我们的实验结果表明，对于实际大小（至少1个BDP）的缓冲区，n个流的纳什均衡将是CUBIC流和BBR流的混合，而不是所有流都是BBR的均衡。虽然最近的研究表明，BBR具有更好的链路利用率和更低且更少的可变延迟，而且BBR最近的部署显示了良好的性能，但推论是，随着更多的流量从CUBIC切换到BBR，我们预计部署BBR的好处会减少。

**互联网拥塞控制的未来**。尽管近年来BBR被迅速采用，我们的结果表明CUBIC不会很快消失或被完全取代。相反，互联网可能变得更加异构。这意味着现有的网络和中间件将需要与传统的基于丢包的TCP以及BBR及其变体一起工作。

**最好的还在后头**。我们注意到，BBRv2已经在做一些工作，它是BBR的一个不太激进的版本。HTTP/3.0将采用QUIC作为其传输堆栈。有了QUIC，开发和部署新的拥塞控制算法的门槛就更低了。在这样一个异构的环境中，网元的性质将如何变化还有待观察。即使我们在§3.2中的推测适用于n个流，其中这些流可以是CUBIC流或BBR流，但如果对拥塞控制算法的选择没有限制，则不清楚它是否适用于任何n个流。在BBRv2和任何未来基于QUIC的拥塞控制算法存在的情况下，研究网元是否以及如何存在仍然是未来的工作。

**互联网可能不会遵循经济博弈论**。我们应用博弈论的概念来模拟互联网拥塞控制的演变。它也为我们提供了一种分析CUBIC和BBR之间相互作用的原理方法。然而，很明显，互联网并不一定完全遵循经济博弈论。例如，很明显，CUBIC在与New Reno竞争时是一种占主导地位的战略，也就是说，由于CUBIC比New Reno更具侵略性，因此始终可以获得更高的吞吐量。尽管如此，今天互联网上仍有少数网站继续运行New Reno。这一现象可能是由于一些网站对网络性能漠不关心或受到其他一些无关因素的影响。这种现象与博弈论的预测相矛盾。

**纳什均衡的唯一性**。在所有的实验中，我们只发现了一个NE。我们试图在§3.2中推测，NE不仅存在，而且是唯一的。我们拒绝这样做，因为当有大量的流和许多不同的RTT时，有很大的可能性空间。纳什均衡类似于局部极小值。一个n流系统是否可以有多个纳什均衡，如果可以，是什么决定了是否有多个或唯一的纳什均衡，这仍然是一个悬而未决的问题。

**工作负载、AQM和多跳路径的影响**。诚然，本文所做的分析并不代表互联网规模的情况。标准形式的博弈将如何受到流量大小和长度的影响，以及当瓶颈移动或部署诸如RED和CoDel等AQM时CUBIC和BBR之间的交互将如何变化，还有待观察。

# 结论

在本文中，我们通过将互联网拥塞控制建模为一个标准形式博弈来研究其潜在的演变。通过分析和试验台实验，我们表明，如果所有流都是CUBIC流或BBR流，那么对于少量流，纳什均衡（NE）是存在的，并且我们推测，对于像互联网这样的大型系统，纳什均衡一般都会存在。我们的结果表明，在现实网络环境下，这种纳什均衡可能是CUBIC流和BBR流的异质混合。此外，构成NE的CUBIC流和BBR流的相对比例将主要取决于瓶颈缓冲区的大小，并略微取决于流的RTT分布，较小的RTT流通常选择CUBIC流。

这些纳什均衡的存在和性质将影响我们如何预计未来几年互联网拥塞控制格局的演变，以及它如何影响与采用新的拥塞控制算法（如BBR）相关的性能效益。特别是，我们的发现有效地驳斥了人们普遍持有的观点，即转向BBR将提高吞吐量。我们还怀疑，在不久的将来，整个互联网不太可能从CUBIC转向BBR和/或其变体。

> 参考文献：Ayush Mishra, Jingzhi Zhang, Melodies Sim, Sean Ng, Raj Joshi, and Ben Leong. “Conjecture: Existence of Nash Equilibria in Modern Internet Congestion Control”. APNet 2021.

> <span style="font-style: italic;">声明：本文素材来源于网络，仅供学习使用，如有侵权请联系网站删除(ngdcn_admin@163.com)。由于本人水平有限，如有纰漏，请以参考文献文章为准。</span>

<font color=red>**欢迎扫码关注微信公众号“网络技术风云汇”，更快速接收更多网络技术咨询。**</font>