← 文章 / 编程开发
Quanta Magazine 1小时前 · 2026-11-21 03:25:32 · 0 阅读

网络研究员敲定“完美韧性”理论

为《Quanta Magazine》设计的 DVDP 图

引言

1969 年秋天的一个晚上,一支研究团队从洛杉矶的一台电脑向位于加州门洛帕克(Menlo Park)的另一台电脑发送了一条历史性信息。或者更准确地说,他们只发送了“LOGIN”这个词的前两个字母:“L” 和 “O”。这是 Arpanet——现代互联网的前身——在第一条链路上传输的第一条信息,但网络在传输完这两个字符后便崩溃了。

自近 60 年前那次首次测试以来,计算机网络变得更加可靠了。但我们对网络的要求也更高了。当你在线观看电影时,视频数据被分割成一系列微小的“数据包”,这些数据包在通往你电脑的过程中,会途经名为路由器的中继站。路由器之间的链路有时会失效。我们的视频之所以没有持续卡顿,其中一个原因便是每个路由器都有一套周全的应急预案——一组在链路失效时重定向数据包规则。

如果大规模故障切断了两点之间的所有路径,数据包便无法通过。但理想情况下,网络应当能够承受除这种最坏情况外的任何链路失效模式。研究人员将这种特性称为“完美韧性”(perfect resilience)。十多年来,计算机科学家一直试图弄清楚在现实条件下,哪些类型的网络可以被构建为具有完美韧性。

如今,两位研究者通过一篇在 2026 年 6 月计算理论研讨会(Symposium on Theory of Computing)上展示的论文,给出了这一问题的定论,并提供了一份完整的证明。他们 证明,恰好存在四种能阻止实现完美韧性的最小网络结构。在缺乏这些结构的网络中,无论哪些链路失效,你总能设计出一套规则,将数据包从任意源可靠地传递到任意目的地。

“这是一项非常优雅的贡献,”未参与该研究的耶路撒冷希伯来大学计算机科学家 Michael Schapira 说,“完全理解某个问题的情况相当罕见。”

全局思考,局部行动

假设你拥有一个路由器网络,其中每个设备都能将数据包定向发送给网络中的任意其他节点。那么你可以问自己:路由器应该遵循什么样的指令?

一个简单的做法是先计算出网络中任意两点之间的最短路径,给每台路由器发一份“地图”。一旦网络发生变化——哪怕只有一条链路出了故障——就推倒重来,重新计算一遍。

理论上,这种策略能保证每个数据包都抵达目的地。但实际中它太慢了。计算最短路径本质上是一个“全局”问题,需要掌握整个网络的情况。在真实网络中,这个计算可能耗时数秒,而路由器必须在不到一毫秒的时间内做出反应。这就意味着路由器只能依靠本地可得的信息来转发数据包,比如它与相邻节点之间链路的状态。

这个限制让“完美韧性”问题变得复杂得多。缺少路由器之间的全局协调,数据包很容易陷入循环转发。

在 2012 年的一篇论文中,Schapira 和另外五位研究者正式定义了完美韧性,并构建了一个数学模型来研究它在什么条件下可以实现。他们假设路由规则必须形式简单:路由器只依据三个因素来决定把新收到的数据包发往哪个方向——数据包的目的地、它从哪条链路进来,以及相邻的哪些链路已经失效。规则不能依赖于数据包此前走过的路径,因为路由器拿不到这些信息。

2012 年论文的合著者、伊利诺伊大学厄巴纳-香槟分校的计算机科学家 Brighten Godfrey 表示,通过这些假设,他们想刻画的是“非常接近真实网络运行方式”的东西。

2020 年,Stefan Schmid 及其同事证明了关于通信网络可靠性的一个部分结果。

Christian Kielmann

Godfrey、Schapira 及其同事证明,在这种模型中,完美弹性并非总能实现。他们通过找出一个网络拓扑的反例来证实这一点:无论你选择怎样的路由规则集合,总存在某种链路故障模式,会导致部分数据包陷入死循环。

但他们发现的那个网络结构相当复杂。这是一个罕见特例,还是众多其他网络同样无法实现完美弹性?

小问题

这篇 2012 年的论文引起了现任柏林工业大学网络研究学者 Stefan Schmid 的注意。多年来,他偶尔会琢磨完美弹性问题,但真正的突破出现在 2020 年:他和同事们将此问题与图小理论(graph minors)这一数学领域联系了起来。

计算机科学家长期以来一直通过将现实世界网络建模为图——即由称为“边”的线连接节点的网状结构——来研究其数学性质。想象你从一个图开始,反复运用三种基本操作进行简化:删除一个节点、删除一条边,或者合并两个相连的节点。通过这些操作组合得到的图,被称为原图的小图(minors)。

Mark Belan/Quanta Magazine

这些操作绝不可能增加数据包陷入无限路由循环的概率。如果一个图具备完美弹性,那么它的所有小图也一定具备完美弹性。

你也可以反过来利用这一逻辑:通过简单子图(minor)的性质来理解大型复杂图的行为。图论中有一个标志性结论——Robertson-Seymour 定理,它告诉你这种反向推理能带来什么。应用到网络韧性上,该定理表明:不具备完美韧性的子图只有有限多个——每个缺乏完美韧性的更大图,都能化归到这些所谓的“禁用子图”(forbidden minors)之一。只要找出全部禁用子图,就能完整掌握完美韧性何时可以实现。 遗憾的是,Robertson-Seymour 定理既没告诉你禁用子图到底有多少个,也没说该怎么找。“我们知道这样的有限集合一定存在,”柏林工业大学的理论计算机科学家、Schmid 在新论文中的合作者 Matthias Bentert 说,“但不知道这个集合里是只有一两个图,还是有 10 万个图。”

图论数学专家 Matthias Bentert 与 Schmid 合作,完成了一项完整的证明。

Alexander Maack

研究人员想找出全部禁用子图,并证明不存在其他禁用子图。 在 2020 年的一篇论文中,Schmid 和同事找到了两个会破坏完美韧性的简单子图,但随后便陷入停滞。Schmid 意识到,要继续推进,需要一位更精通图论的合作伙伴。三年后,他在一次研究研讨会上遇到了 Bentert,两人还短暂合作过另一个问题。2025 年,当 Bentert 在挪威的博士后任期即将结束时,Schmid 邀请他加入自己在柏林的团队。 “这真是一次天作之合,”Schmid 说,“Matthias 在我们的几个问题上都很快做出了贡献。”或许他也能帮忙快速攻克完美韧性这个难题。

走出迷宫

Bentert 很快锁定了第三个禁用次结构。随后,他决定换个思路,从反方向入手。他想,如果不存在其他禁用次结构——也就是说,已发现的这三个构成了完整集合——那么他或许可以证明:所有不含有这三个结构的图,都能被构建为具备完美韧性的网络。

策略确实奏效了,但结果并非他所期望的那样。“我发现,实际上我无法证明这一点,因为它是假的,”Bentert 说。他意外地发现了第四个障碍。

至此,他们找到了四个被禁用的图结构。还会有更多吗?Bentert 再次尝试同样的策略:证明所有不含有这四个次结构的图,都能具备完美韧性。这一次策略成功了,因为他确实找到了完整的集合。

四个禁用的图次结构。

Bentert 并未预料到答案会如此简洁。“如果数量达到 50 左右,我可能就停止了。但事实只有四个,这多少让我感到惊讶,”他说。

当然,仅仅知道完美韧性在理论上对任意给定网络都可实现是不够的,你还必须知道如何选择合适的路由规则。幸运的是,Schmid 和 Bentert 的新成果同时提供了一种快速算法来寻找这些规则。这些规则在不同网络中的形式非常相似,其核心原理源自一种走出迷宫的技巧:在每个路口都向右转。唯有包含那四个禁用次结构之一的网络,这种基于迷宫导航的方法才会失效。对于这些网络,更改规则也无济于事。

Mark Belan/Quanta Magazine

现实中的韧性

凭借这一新成果,Schmid 和 Bentert 彻底解决了 2012 年最初提出的完美韧性(perfect resilience)问题。但答案并不全是好消息。虽然阻碍完美韧性的图结构只有四种,但它们恰恰过于简单,这意味着许多网络都会包含它们作为子图。连接密集的网络尤其容易缺乏完美韧性——这颇有些讽刺,因为给网络增加链路恰恰是提升可靠性的最直接手段。

“连接越多,可能的子图就越多,”Godfrey 说,“很多现实中的网络恐怕都不具备完美韧性,我不会感到意外。”

不过这未必是致命问题:在某些通信网络中,韧性并不像高速度、低拥塞那么重要,而这两点恰恰是 Schmid 和 Bentert 的规则没有考虑的。而在确实需要韧性的场景下,他们的结论也未必是故事的终点。两人目前计划研究:如果每个数据包都能记录自己最近经过的几个节点,情况会有什么变化。Bentert 乐观地认为,这种做法能让更广泛的网络实现完美韧性,同时在现实中依然可行。

“也许某些非常怪异的网络即便在改进后的问题设定下也无法做到完美韧性,”他说,“但凡是人类或机器设计出来的网络,都可以做到。”

原始来源: Quanta Magazine

评论 (0)