网络研究者明确了“完美韧性”理论
1969年秋天的一个傍晚,一个研究团队从洛杉矶的一台计算机向加利福尼亚州门洛帕克的一台计算机发送了一条历史性信息。更确切地说,他们只发送了信息的一部分:“LOGIN”中的“L”和“O”。这条经由 Arpanet 第一条链路进行的首次传输——Arpanet 是现代互联网的原型——只持续了两个字符,网络就崩溃了。
自近60年前的那次首次测试以来,计算机网络已经可靠得多。但我们对它们的要求也高得多。当你在网上看一部电影时,视频数据会被分成一系列微小的“数据包”,它们在通往你计算机的途中,会在称为路由器的中转站之间跳转。路由器之间的链路有时会故障。我们的视频没有不断出现故障,一个原因是每台路由器都有周密的应急方案——一套在链路断开时重定向数据包的规则。
如果一次大规模中断切断了两点之间的所有路径,数据包就无法通过。但理想情况下,网络应能承受除这种最坏情形之外的任何链路故障模式。研究者将这种性质称为“完美韧性”。十多年来,计算机科学家一直试图理解,在现实条件下,哪些类型的网络能够实现完美韧性。
如今,在2026年6月于 Symposium on Theory of Computing 上宣读的一篇论文中,两位研究者用一份完整的证明解决了这个问题。他们证明,恰好有四种最小网络结构会阻碍完美韧性。在缺少这些结构的网络中,无论哪些链路发生故障,你总能设计出规则,将数据包从任意源可靠地送达任意目的地。
“这是一个非常优雅的贡献,”Michael Schapira 说。他是 Hebrew University of Jerusalem 的计算机科学家,没有参与这项成果。“对某个问题获得完整理解相当罕见。”
全球思考,本地行动
设想你有一个由路由器组成的网络,其中每台设备都能将发往网络中任意其他点的数据包导向目的地。然后你可以问自己:路由器应遵循什么指令?
一种简单方法是标出网络中每一对点之间的最短路径,然后给每台路由器一份该地图的副本。如果网络发生变化——哪怕只有一条链路故障——就重新开始,再做一遍。
原则上,这种策略将确保每个数据包都到达其目的地。在实践中,它太慢了。计算最短路径本质上是一个“全局”问题——它需要关于整个网络的知识。在现实世界的网络中,这种计算可能需要长达几秒钟。但每台路由器都必须快速行动,在一毫秒的几分之一或更短时间内完成。这意味着路由器必须仅使用本地可获取的信息来导向数据包,例如与其直接邻居之间链路的状态。
这一限制使完美韧性问题复杂得多。路由器之间没有任何全局协调时,数据包可能陷入循环。
在2012年的一篇论文中,Schapira 和其他五位研究者正式定义了完美韧性,并设计了一个数学模型来研究它在何时可以实现。他们假设路由规则必须具有简单形式。路由器仅使用三个因素就能决定将每个新数据包发送到哪个方向:数据包的目的地、它到达时所经过的链路,以及哪些相邻链路已经故障。规则不能依赖数据包迄今为止走过的路径,因为路由器无法获取这一信息。
“在这些假设下,研究者旨在刻画‘非常接近网络实际运行方式的东西’,”Brighten Godfrey 说。他是 University of Illinois, Urbana-Champaign 的计算机科学家,也是2012年论文的合著者。

网络研究者厘清了“完美韧性”理论
2020 年,Stefan Schmid 和他的同事证明了关于通信网络可靠性的一个部分结果。
Christian Kielmann
Godfrey、Schapira 和他们的同事表明,在这个模型中,完美韧性并非总能实现。他们通过找到一个无法实现完美韧性的网络布局示例来做到这一点。无论你选择哪一组路由规则,总存在某种链路故障模式,会使一些数据包陷入循环而卡住。
但他们识别出的网络相当复杂。它是一个罕见的例子吗?还是说完美韧性在许多其他网络中也不可能实现?
子式问题
2012 年的论文引起了 Stefan Schmid 的注意,他现在是柏林工业大学的一名网络研究者。多年来,他断断续续地琢磨完美韧性问题,但他第一次真正取得进展是在 2020 年,当时他和同事把它与数学中一个称为图子式理论的主题联系了起来。
计算机科学家长期以来通过将现实世界网络建模为图来研究其数学性质——图是由称为边的线连接起来的节点之网。想象你从一个图开始,然后用三种基本操作反复简化它:可以删除一个节点、删除一条边,或合并一对相连的节点。通过组合这些操作所能得到的图,称为较大图的子式。