网易首页 > 网易号 > 正文 申请入驻

四种网络结构注定无解,他们用证明终结十年悬案

0
分享至

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.

相关推荐
热点推荐
网约车司机态度强硬,乘客反感:要求那么多,你自己服务标准做到了吗?

网约车司机态度强硬,乘客反感:要求那么多,你自己服务标准做到了吗?

用车指南
2026-11-21 10:00:49
下投男!文班亚马!

下投男!文班亚马!

左右为篮
2026-11-21 12:04:10
已失业3个月!38岁本泽马找到工作:接近重返法甲7冠王 存1拦路虎

已失业3个月!38岁本泽马找到工作:接近重返法甲7冠王 存1拦路虎

风过乡
2026-11-21 07:56:34
红果短剧有多离谱?套路千篇一律,逻辑全崩,为何还让人上瘾

红果短剧有多离谱?套路千篇一律,逻辑全崩,为何还让人上瘾

浩渺青史
2026-11-20 01:27:26
今年大概是初中最后的辉煌了,明年起,初中生将越来越少。

今年大概是初中最后的辉煌了,明年起,初中生将越来越少。

小羽叨叨叨
2026-11-20 14:53:15
董路怒批浮嶋敏:3年不练5后卫一定是错的!我可是带队踢过皇马巴萨

董路怒批浮嶋敏:3年不练5后卫一定是错的!我可是带队踢过皇马巴萨

念洲
2026-11-21 10:27:40
搞大了!特朗普突然喊话:让黄仁勋回归!

搞大了!特朗普突然喊话:让黄仁勋回归!

大厂财经社
2026-11-21 11:15:21
大规模封号来了!OpenAI开打反蒸馏战

大规模封号来了!OpenAI开打反蒸馏战

新智元
2026-11-21 08:46:31
未来3月运势攀升!4生肖凭硬本事稳步向前,底气越走越足

未来3月运势攀升!4生肖凭硬本事稳步向前,底气越走越足

温暖心语
2026-11-21 14:00:07
1979年,翁美玲与男友罗柏前往威尼斯出游,1米58的她穿吊带裙与罗柏牵手漫步,镜头下甜蜜画面却藏着不为人知的结局

1979年,翁美玲与男友罗柏前往威尼斯出游,1米58的她穿吊带裙与罗柏牵手漫步,镜头下甜蜜画面却藏着不为人知的结局

磊子讲史
2026-11-04 15:53:33
1976年吴桂贤深夜受召玉泉山,进门瞥见沙发搬空那一瞬,华国锋当场宣布中央定局,改了她一生走向

1976年吴桂贤深夜受召玉泉山,进门瞥见沙发搬空那一瞬,华国锋当场宣布中央定局,改了她一生走向

唠叨说历史
2026-11-21 09:57:26
下投男!文班亚马放弃扣篮,历史首见零距离跳投!

下投男!文班亚马放弃扣篮,历史首见零距离跳投!

篮球实录
2026-11-21 00:12:07
预售飙到10亿,没上映就要破沈腾的纪录?2026年票房冠军要易主了

预售飙到10亿,没上映就要破沈腾的纪录?2026年票房冠军要易主了

靠谱电影君
2026-11-18 20:02:46
DeepSeek付费体验直线上升:免费时代结束了,充钱就能变爽!

DeepSeek付费体验直线上升:免费时代结束了,充钱就能变爽!

城事堂
2026-11-21 08:50:50
皇马8天3赛 + 迎战阿森纳!穆帅表态:皇马伤病显著减少,密集赛程要靠阵容深度扛住

皇马8天3赛 + 迎战阿森纳!穆帅表态:皇马伤病显著减少,密集赛程要靠阵容深度扛住

福酱的小时光
2026-11-21 09:49:37
单场25+9,范弗利特重伤后反而进化,火箭队5替补只拿12分,两射手只能打顺风球

单场25+9,范弗利特重伤后反而进化,火箭队5替补只拿12分,两射手只能打顺风球

替补席看球
2026-11-21 13:59:19
法布雷加斯:尼科-帕斯应专注科莫,阿根廷10号球衣应该被退役

法布雷加斯:尼科-帕斯应专注科莫,阿根廷10号球衣应该被退役

懂球帝
2026-11-21 00:22:49
东契奇挑战超级魔咒!使用率40.4%居首:史上不低于35%从未夺冠

东契奇挑战超级魔咒!使用率40.4%居首:史上不低于35%从未夺冠

罗说NBA
2026-11-21 07:15:10
黑色抹胸热裤黑丝高跟美腿小姐姐 6173 要看热裤美女 只有来年了

黑色抹胸热裤黑丝高跟美腿小姐姐 6173 要看热裤美女 只有来年了

手工制作阿歼
2026-11-21 13:02:39
美国若在G20峰会期间举行第二次三国元首会晤中方将如何回应?外交部回应

美国若在G20峰会期间举行第二次三国元首会晤中方将如何回应?外交部回应

澎湃新闻
2026-11-20 17:06:06
2026-11-21 14:36:49
闪存猎手
闪存猎手
全网蹲好价的野生捕手,算力与羊毛都不可辜负。
243文章数 84关注度
往期回顾 全部

科技要闻

老黄想回来?英伟达董事会:没门

头条要闻

历时14小时特朗普返回美国 刚下飞机就发布"重大预告"

头条要闻

历时14小时特朗普返回美国 刚下飞机就发布"重大预告"

体育要闻

脚步未停!西班牙摩托车手赤脚徒步入境中国

娱乐要闻

官媒发文 官宣赵丽颖新身份,进步很大

财经要闻

最大回撤超37%,黄金崩盘了吗?

汽车要闻

全新红旗H9最有意思的地方,是它开始有自己的豪华逻辑了

态度原创

房产
时尚
本地
数码
手机

房产要闻

黄埔商业规划曝光!科学城能级跃升,核心入场券已锁定

秋天衣服别总穿纯色,试试这几件条纹单品,简单时尚又减龄

本地新闻

乌兰察布:以前种土豆,现在种Token

数码要闻

苹果公布2026古典乐年度专辑:任奫灿《哥德堡变奏曲》获奖

手机要闻

2026年最后一款超模旗舰!小米18标准版屏幕、性能、影像全面领跑

无障碍浏览 进入关怀版