1969年秋天的一个晚上,洛杉矶的一台计算机向加州门洛帕克的另一台计算机发出了历史性信息。准确地说,只发出了“LOGIN”里的“L”和“O”——阿帕网(Arpanet,现代互联网的原型)第一条链路上的首次传输,在发出两个字符后网络就崩溃了。
![]()
近60年过去,计算机网络早已可靠得多,但我们对它的要求也高得多。在线看视频时,视频数据被切成一个个微小的“数据包”,在通往你电脑的路上于被称为路由器的站点之间跳转。路由器之间的链路有时会失效。视频没有频繁卡顿,原因之一是每台路由器都有一套周密的应急方案——一旦某条链路断开,就按既定规则重定向数据包。
如果一场大规模故障切断了两点之间的所有路径,数据包无论如何都过不去。但在理想情况下,网络应当能承受除这种最坏情形之外的任何链路故障模式。研究者把这种性质称为“完美韧性”(perfect resilience)。十多年来,计算机科学家一直想弄清:在现实条件下,什么样的网络才能做到完美韧性。
如今,在一篇于2026年6月计算理论研讨会(Symposium on Theory of Computing)上发表的论文中,两位研究者用一套完整的证明终结了这个问题。他们证明,恰好有四种最小网络结构会阻断完美韧性。在不含这些结构的网络中,你总能设计出规则,无论哪些链路失效,都能把数据包从任意源点可靠送达任意目的地。
“这是一个非常优雅的贡献,”未参与该成果的耶路撒冷希伯来大学计算机科学家迈克尔·沙皮拉(Michael Schapira)说,“能对一件事获得完整的理解,是相当罕见的。”
全局思考,局部行动
设想一个路由器网络,每台设备都能把数据包导向网络中的任意其他点。那么问题来了:路由器该遵循什么指令?
一种简单做法是:算出网络中每一对点之间的最短路径,然后给每台路由器发一份地图副本。网络一旦变化——哪怕只断一条链路——就推倒重算。理论上这能保证每个数据包都到达目的地,实践中却太慢。计算最短路径本质上是一个“全局”问题,需要掌握整个网络的信息。在真实网络中,这个计算可能要花上几秒,而每台路由器必须在不到一毫秒内做出反应。这意味着路由器只能依靠本地可获取的信息来转发数据包,比如与直接相邻路由器之间链路的状态。
这一限制让完美韧性问题复杂得多。路由器之间没有全局协调,数据包可能陷入循环。
2012年,沙皮拉与另外五位研究者正式定义了完美韧性,并建立数学模型研究它何时可实现。他们假定路由规则必须形式简单:路由器只能依据三个因素决定每个新数据包的发送方向——数据包的目的地、它从哪条链路到达、以及哪些相邻链路已失效。规则不能依赖数据包此前走过的路径,因为路由器拿不到这个信息。
在这些假设下,研究者想刻画的是“非常接近网络实际运行方式的东西”,2012年论文合著者、伊利诺伊大学厄巴纳-香槟分校计算机科学家布莱滕·戈弗雷(Brighten Godfrey)说。
戈弗雷、沙皮拉及其同事证明,在这个模型中完美韧性并非总能实现。他们找到了一个无法做到完美韧性的网络布局作为反例:无论你选哪套路由规则,总存在某种链路故障模式,让部分数据包卡在循环里。但他们找到的网络相当复杂——这是个罕见例子,还是完美韧性在许多其他网络中同样不可能?
图子式带来的突破
2012年的论文引起了现任职于柏林工业大学(Technical University of Berlin)的网络研究者斯特凡·施密德(Stefan Schmid)的注意。他断断续续琢磨完美韧性问题多年,第一次真正进展出现在2020年:他和同事把它与数学中一个叫“图子式理论”(theory of graph minors)的课题联系了起来。
计算机科学家长期把真实网络建模为图——由节点和被称为边的连线构成的网——来研究其数学性质。设想你从一个图出发,反复用三种基本操作简化它:删除一个节点、删除一条边、或合并一对相连的节点。通过这些操作得到的图,称为原图的子式。
这些操作不会让数据包更容易陷入无限循环。如果一个图具有完美韧性,那么它的所有子式也具有完美韧性。反过来,你可以用更简单子式的性质来理解大型复杂图的行为。图论中一个标志性结果——罗伯逊-西摩定理(Robertson-Seymour theorem)——说明了这种反向推理能带来什么:应用到网络韧性上,该定理指出,不具备完美韧性的子式只有有限多个,每一个缺乏完美韧性的大图都会归约到这些所谓的“禁用子式”之一。若能找出全部禁用子式,就完全掌握了完美韧性何时可实现。
可惜,罗伯逊-西摩定理并不告诉你禁用子式有多少个、如何找到它们。“我们知道这样一个有限集合存在,”施密德在新论文中的合作者、柏林工业大学理论计算机科学家马蒂亚斯·本特尔特(Matthias Bentert)说,“但我们不知道它包含一个还是两个图,还是包含10万个图。”
研究者想找出完整的禁用子式集合,并证明再无其他。2020年的论文中,施密德和同事识别出两个会阻断完美韧性的简单图子式,随后卡住了。施密德觉得需要一位更懂图论的合作者。三年后,他在一次研究静修会上遇到本特尔特,两人短暂合作了另一个问题。2025年,本特尔特在挪威结束博士后研究时,施密德邀请他加入柏林的小组。“这真是完美的匹配,”施密德说,“马蒂亚斯在我们的几个问题上做出了很多非常快的贡献。”
走出迷宫
本特尔特很快识别出第三个禁用子式。接着他决定从反方向试试能走多远:如果不存在更多禁用子式——如果找到的三个就是全部——那么他就能证明,所有不含这三个子式的图都能做到完美韧性。
策略奏效了,但结果并非他所期望。“我发现,其实我证不了,因为它不成立,”本特尔特说。他发现了第四个障碍。
现在他们有了四种禁用图结构。还有更多吗?本特尔特再次使用同一策略:证明所有不含这四个子式的图都能做到完美韧性。这次策略成功了,因为他确实找到了完整集合。
本特尔特没料到答案如此简单。“如果找到50个左右我就会停下,但真的只有四个,这让我有点意外,”他说。
当然,知道某个网络在理论上可实现完美韧性,只有在你知道如何选出正确路由规则时才有用。幸运的是,施密德和本特尔特的新结果同时给出了寻找这些规则的快速算法,而且这些规则在任何网络中形式都相似:它们都基于一个走出迷宫的技巧——在每个路口一律右转。唯一让这种迷宫导航式方法失效的网络,就是含有四种禁用子式之一的网络。对这类网络,换规则也无济于事。
现实中的韧性
凭借新结果,施密德和本特尔特完整解决了2012年最初提出的完美韧性问题。但答案并不全是好消息。尽管阻断完美韧性的图结构只有四种,它们如此简单,意味着许多网络都会把它们作为子式包含进来。连接密集的网络尤其可能缺乏完美韧性——颇具讽刺意味的是,给网络增加更多链路本是提升可靠性最直接的办法。
“你的连接越多,可能的子图就越多,”戈弗雷说,“如果许多真实网络不存在完美韧性的解,我不会感到意外。”
这未必是致命问题:在某些通信网络中,韧性不如高速和低拥塞重要,而这两个因素并不在施密德和本特尔特规则的考虑范围内。在韧性重要的场景中,他们的结果也可能不是故事的终点。他们现在计划研究:如果每个数据包能携带最近访问过的几个节点的记录,情况会如何变化。本特尔特乐观地认为,这一思路能让更广泛的网络实现完美韧性,同时仍在现实世界中可行。
“也许某些非常古怪的网络无法做到完美韧性,”即便在修改后的问题版本中,他说,“但人类或机器将来设计出的一切都可以。”
特别声明:以上内容(如有图片或视频亦包括在内)为自媒体平台“网易号”用户上传并发布,本平台仅提供信息存储服务。
Notice: The content above (including the pictures and videos if any) is uploaded and posted by a user of NetEase Hao, which is a social media platform and only provides information storage services.