数学证明——网络拥塞是不可避免的

有时“解决”交通问题只会让事情变得更糟

正如高速公路网络可能会遭受交通拥堵的困扰，计算机网络也可能面临拥堵。现在一项新的研究发现，许多旨在控制计算机网络延迟的关键算法可能被证明是非常不公平的，让一些用户占用所有带宽，而另一些用户则基本上一无所获。

通过 Internet 发送数据的计算机和其他设备将其分解为更小的数据包，然后使用特殊算法来决定发送这些数据包的速度。这些拥塞控制算法旨在发现和利用所有可用的网络容量，同时与同一网络上的其他用户共享。

在过去的十年中，研究人员开发了几种拥塞控制算法，旨在实现高速数据传输，同时最大限度地减少网络中数据排队导致的延迟。其中一些，例如 Google 的BBR 算法，现在已被许多网站和应用程序广泛使用。

“即使每个人都合作，也会发生极端的不公平，这不是任何人的错。”
——文卡特·阿伦，麻省理工学院

然而，尽管在过去大约 40 年中已经提出了数百种拥塞控制算法，但“没有明显的赢家”，该研究的主要作者、麻省理工学院的计算机科学家Venkat Arun说。“我对我们对这些算法在哪里起作用和在哪里起作用知之甚少感到沮丧。这促使我创建一个可以做出更系统预测的数学模型。”

出乎意料的是，阿伦和他的同事现在发现许多拥塞控制算法可能被证明是非常不公平的。他们的新研究发现，鉴于网络路径在现实世界中的复杂性，总会出现一种情况，即无法避免被称为“饥饿”的问题——与其他用户相比，网络上至少有一个发送者几乎没有收到任何带宽。

用户的计算机不知道发送数据包的速度有多快，因为它缺乏有关网络的知识，例如网络上有多少其他发送者或连接质量。发送数据包太慢会导致对可用带宽的利用不足。但是，发送数据包过快可能会使网络不堪重负，从而导致数据包丢失。然后需要再次发送这些数据包，从而导致延迟。延迟也可能是由于数据包在队列中等待很长时间。

拥塞控制算法依靠数据包丢失和延迟作为细节来推断拥塞并决定发送数据的速度。但是，数据包可能会因为网络拥塞以外的原因而丢失和延迟。例如，数据可能会被保留，然后与其他数据包一起突发释放，或者接收器对它收到数据包的确认可能会延迟。研究人员将不是由拥塞导致的延迟称为“抖动”。

拥塞控制算法无法区分由拥塞引起的延迟和抖动引起的延迟。这可能会导致问题，因为抖动引起的延迟是不可预测的。这种模糊性使发送者感到困惑，这可能使他们每个人都以不同的方式估计延迟并以不同的速率发送数据包。研究人员发现，这最终会导致出现饥饿和一些用户完全被拒之门外的情况。

在这项新研究中，研究人员分析了他们所知道的每种拥塞控制算法以及他们设计的一些新算法是否可以避免饥饿。科学家们惊讶地发现，每种算法总有一些人获得所有带宽，而至少一个人基本上什么也得不到。

“一些用户可能会遇到非常糟糕的性能，我们并没有早点知道，”Arun 说。“即使每个人都合作，也会发生极端的不公平，这不是任何人的错。”

研究人员发现，所有现有的旨在抑制延迟的拥塞控制算法都是他们所谓的“延迟收敛算法”，它们总是会遭受饥饿的困扰。长期以来，这些广泛使用的算法的这种弱点仍然不为人知，这可能是由于仅凭经验测试“可能将性能不佳归因于网络容量不足，而不是算法决策不佳，”阿伦说。

阿伦说，尽管现有的拥塞控制方法可能无法避免饥饿，但现在的目标是开发一种新的策略。“更好的算法可以以更低的成本实现可预测的性能，”他说。

阿伦指出，这项研究可能具有超出分析网络拥塞的应用。“我们目前正在使用我们的计算机系统建模方法来推理在计算机系统中分配资源的其他算法，”他说。“我们的目标是帮助构建具有可预测性能的系统，这很重要，因为我们依赖计算机来处理越来越重要的事情。例如，生活可能取决于自动驾驶汽车做出及时的决定。”

科学家们将于8 月 24 日在 ACM 数据通信特别兴趣小组 ( SIGCOMM ) 会议上详细介绍他们的发现。

原文始发于微信公众号（网络研究院）：数学证明——网络拥塞是不可避免的