研究人员发现缓解网络拥塞的主要障碍

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

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

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

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

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

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

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

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

控制拥塞

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

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

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

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

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

研究饥饿

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

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

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

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

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

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

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

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

郑重声明:本文版权归原作者所有,转载文章仅为传播更多信息之目的,如作者信息标记有误,请第一时候联系我们修改或删除,多谢。