当用户希望通过互联网以比网络处理速度更快的速度发送数据时，就会发生拥堵——就像早上通勤到大城市时交通拥堵一样。

通过互联网传输数据的计算机和设备将数据分解成更小的数据包，并使用一种特殊的算法来决定发送这些数据包的速度。这些拥塞控制算法寻求充分发现和利用可用网络容量，同时与可能共享同一网络的其他用户公平共享。这些算法试图最小化由网络中队列中的数据等待引起的延迟。

在过去的十年中，工业界和学术界的研究人员开发了几种算法，试图在控制延迟的同时实现高速率。其中一些，例如 Google 开发的 BBR 算法，现在已被许多网站和应用程序广泛使用。

但是麻省理工学院的一组研究人员发现，这些算法可能非常不公平。在一项新的研究中，他们表明总会有一种网络场景，其中至少一个发送者与其他发送者相比几乎没有接收到带宽;也就是说，无法避免称为饥饿的问题。

“这篇论文和结果真正令人惊讶的是，当你考虑到网络路径的现实世界复杂性以及它们可以对数据包做的所有事情时，延迟控制拥塞控制算法基本上是不可能避免的使用当前方法饥饿，”电气工程和计算机科学 (EECS) 副教授 Mohammad Alizadeh 说。

虽然 Alizadeh 和他的合著者无法找到可以避免饥饿的传统拥塞控制算法，但可能有不同类别的算法可以防止这个问题。他们的分析还表明，改变这些算法的工作方式，以便它们允许更大的延迟变化，可以帮助防止某些网络情况下的饥饿。

Alizadeh 与第一作者、EECS 研究生 Venkat Arun 和资深作者、富士通计算机科学和人工智能教授 Hari Balakrishnan 共同撰写了这篇论文。该研究将在 ACM 数据通信特别兴趣小组 (SIGCOMM) 会议上发表。

控制拥塞

拥塞控制是研究人员自 1980 年代以来一直试图解决的网络中的一个基本问题。

用户的计算机不知道通过网络发送数据包的速度有多快，因为它缺少网络连接质量或有多少其他发送者正在使用网络等信息。发送数据包太慢会导致对可用带宽的利用不足。但是发送太快会使网络不堪重负，并且在这样做时，数据包将开始被丢弃。这些数据包必须重新发送，这会导致更长的延迟。延迟也可能是由于数据包在队列中等待很长时间而引起的。

拥塞控制算法使用数据包丢失和延迟作为信号来推断拥塞并决定发送数据的速度。但是互联网很复杂，数据包可能由于与网络拥塞无关的原因而延迟和丢失。例如，数据可能会沿途排队等待，然后随着其他数据包的爆发而释放，或者接收器的确认可能会延迟。作者将不是由拥塞引起的延迟称为“抖动”。

即使拥塞控制算法完美地测量了延迟，它也无法区分由拥塞引起的延迟和由抖动引起的延迟。由抖动引起的延迟是不可预测的，并且会使发送者感到困惑。由于这种模糊性，用户开始以不同的方式估计延迟，这导致他们以不同的速率发送数据包。Arun 解释说，最终，这会导致出现饥饿和有人被完全拒之门外的情况。

“我们开始这个项目是因为我们缺乏对存在抖动的拥塞控制行为的理论理解。为了将其置于更牢固的理论基础上，我们建立了一个数学模型，该模型足够简单，但能够捕捉到互联网的一些复杂性。让数学告诉我们一些我们不知道但具有实际相关性的事情是非常有益的，”他说。

研究饥饿

研究人员将他们的数学模型输入计算机，给它一系列常用的拥塞控制算法，并要求计算机使用他们的模型找到一种可以避免饥饿的算法。

“我们做不到。我们尝试了我们知道的所有算法，以及我们编写的一些新算法。没有任何效果。计算机总是会发现一些人获得所有带宽，而至少一个人基本上什么也得不到，”Arun 说。

研究人员对这一结果感到惊讶，特别是因为人们普遍认为这些算法是相当公平的。他们开始怀疑可能无法避免饥饿，这是一种极端的不公平形式。这促使他们定义了一类他们称之为“延迟收敛算法”的算法，他们证明在他们的网络模型下总是会遭受饥饿。所有控制延迟的现有拥塞控制算法(研究人员都知道)都是延迟收敛的。

Arun 补充说，这些广泛使用的算法的如此简单的故障模式在很长一段时间内仍然不为人知，这说明仅通过经验测试来理解算法是多么困难。它强调了坚实的理论基础的重要性。

但所有的希望都没有丢失。虽然他们测试的所有算法都失败了，但可能还有其他不是延迟收敛的算法可能能够避免饥饿这表明解决问题的一种方法可能是设计更广泛地改变延迟范围的拥塞控制算法，因此该范围大于由于网络抖动而可能发生的任何延迟。

“为了控制延迟，算法也试图将延迟的变化限制在所需的平衡范围内，但潜在地创造更大的延迟变化以更好地测量拥塞延迟并没有错。这只是你必须采用的一种新的设计理念，”Balakrishnan 补充道。

现在，研究人员希望继续努力，看看他们是否能找到或建立一种消除饥饿的算法。他们还希望将这种数学建模和计算证明方法应用于网络系统中其他棘手的、未解决的问题。

“对于非常关键的事情，我们越来越依赖计算机系统，我们需要将它们的可靠性建立在更牢固的概念基础上。我们已经展示了当您花时间提出这些问题实际问题的正式规范时会发现的令人惊讶的事情，”Alizadeh 说。