
研究团队尝试用信鸽传输数据,探索网络调度问题
来源标题:Could Pigeons Deliver the Internet?
一项新研究尝试用信鸽作为数据传输网络,以此探讨现代数据中心光交换机的链路重配置问题。该思路源于1990年的愚人节RFC 1149,该文档描述了用鸟类载体发送IP数据包的方法。研究中指出,RFC 1149只说明了如何用信鸽传数据,却未解释如何高效组织飞行路线。
以下正文由 AI 翻译自 Hacker News 最新(原文版权归原站所有),可能存在偏差,重要内容请以原文为准。
训练 AI 模型需要在机器之间传输大量数据,因此高效的通信至关重要。机器学习和分布式系统领域的大量研究都投入到构建更快的网络以及寻找更智能的网络使用方式上。在最近的一篇论文中,我们尝试了一种不同类型的网络:信鸽。
这个想法比你想象的更古老。1990 年 4 月 1 日,RFC 1149 描述了如何通过“鸟类载体”发送 IP 数据包。虽然这只是愚人节玩笑,但确实有人尝试过,在几次公开比赛中,携带存储卡的鸽子击败了缓慢的宽带线路。
但这个不寻常的想法背后是一个根本性的网络问题。现代数据中心使用光交换机根据通信需求重新配置链路。这引出了如何高效地进行重新配置的问题。另一个相关领域是时间图,其中连接仅在特定时间可用,因此它们的顺序决定了哪些消息可以被送达。
这些问题在设计鸽子网络时同样会出现。虽然 RFC 1149 描述了如何使用鸽子传输数据,但它没有解释如何高效地组织它们的飞行。因此,在我们的工作《信鸽互联网协议:一种算法(且轻松愉快)的视角》中,我们研究了如何用尽可能少的鸽子来设计这样一个网络。
信鸽的特殊之处在于它会飞回家,回到它被饲养和长大的地方。假设我们想从 TU Berlin 向海法的 Technion 发送一条消息。我们需要一只在 Technion 出生的鸽子,被带到 TU Berlin,然后被释放,让它带着我们的消息飞回家。然后,一旦鸽子到达 Technion,它就不能简单地被重新用来从 TU Berlin 携带另一条消息。我们需要另一只鸽子。与电缆不同,鸽子每次携带东西都会被消耗掉。所以我们问:如果我们真的运营一个鸽子网络,我们需要多少只鸟,在哪里饲养它们?
为了研究这个问题,我们将通信需求建模为一个有向图,其中节点代表位置,边代表必须送达的消息。任务是决定在哪里饲养鸽子、将它们放置在哪里以及如何安排它们的飞行,以最小化所需鸽子的总数。偏远位置的消息可以按需保留任意长时间,并合并到之后的航班中。
我们研究了该问题的三个版本:
允许中途停留可以节省大量鸽子。另一方面,这也使问题变得更加难以求解。
在单跳情况下,每个源-目的对恰好需要一只鸽子。虽然这是最优的,但鸽子数量很快变得非常庞大。例如,如果 20 个位置想要相互通信,就需要 380 只鸽子。
一旦消息可以中途停留,寻找最优解就是 NP-hard 的。我们为两跳和多跳情况提供了从 3SAT 和 Vertex Cover 的归约。
幸运的是,我们仍然高效地找到了好的解决方案。我们的论文提出了 Coordinator 算法,它选择连接最多的位置作为协调者。然后,每个源向协调者发送消息。协调者按目的地对消息进行排序,并向每个目的地发送一只鸽子。在 20 个位置的例子中,这将鸽子数量从 380 只减少到 38 只。我们需要 19 只鸽子在协调者处收集所有消息,另外 19 只将它们分发到各自的目的地。我们证明了 Coordinator 算法使用的鸽子数量永远不会超过最优解的两倍,并且它在多项式时间内运行。对于小规模实例的精确最优解,我们还给出了两跳和多跳情况的整数线性规划。
为了保持模型简单,我们的鸽子可以携带无限量的数据。一个自然的下一步是研究当鸽子携带能力有限时会发生什么。我们也只计算了鸽子数量,而没有计算时间。更少的鸽子通常意味着更多的中途停留,而每次中途停留都会增加延迟,因此鸽子最少的网络可能是一个缓慢的网络。此外,人们可以考虑将鸽子运送到其偏远节点的能源足迹。这需要花费金钱和能源,而前往同一地点的鸟可以拼车。最后,我们假设所有消息都是预先已知的。在实践中,需求是随时间到达的,要么按照已知过程,要么以对抗性方式到达。
虽然我们的研究是轻松愉快的,但它对现实世界的问题有应用价值。我们提到了可预测的数据中心网络流量,如 AI 训练,使用光交换机重新布线以匹配预期流量。事实上,通信中的许多优化问题都依赖于需求矩阵,包括流量工程。在网络通信之外,需求感知图(就像我们用来优化鸽子流量的图)被用来确定如何路由车辆和商品流。
从谦逊的信鸽的旅行中仍然可以学到很多东西。
Tijana Milentijević 是 TU Berlin 的博士生。她的研究位于机器学习和分布式系统的交叉领域,专注于鲁棒联邦学习和分布式算法。
这项工作由 TU Berlin 和 Technion 的 Matthias Bentert、Shay Kutten、Darya Melnyk、Tijana Milentijević 和 Stefan Schmid 共同撰写。
本博客作者表达的观点仅代表他们自己,不一定反映 APNIC 的观点。请注意,本博客适用行为准则。
您的电子邮件地址将不会被发布。必填字段已标记 *
正文由 探How 从来源站点 RSS 同步,内容未经改写;遇到排版缺失或需要图片、视频时请以原文为准。