主讲人:Timothy G. Griffin(剑桥大学教授、剑桥国王学院院士)
报告时间:2026 年 11 月 20 日(星期五)10:30–11:30
报告地点:厦门大学翔安校区西部片区信息学院3号楼109会议室
报告摘要:
Most Internet routing protocols have one of two algorithms lurking at their core — either Dijkstra’s algorithm in the case of link-state protocols or a distributed Bellman-Ford algorithm in the case of distance-vector or path-vector protocols. When computing simple shortest paths these protocols can be modified to utilize all best paths with a combination of next-hop sets and Equal Cost Multi-Path (ECMP) forwarding. We show that this picture breaks down even for simple modifications to the shortest path metric. This is illustrated with widest-shortest paths where among all shortest paths only those with greatest bandwidth are considered best. In this case Bellman-Ford and Dijkstra may compute different sets of paths and neither can compute all best paths. In addition, some paths computed by Dijkstra’s algorithm cannot be implemented with next-hop forwarding. We provide a general algebraic model that helps to clarify such anomalies. This is accomplished by computing paths within the route metric rather than with specialized algorithmic extensions. Our results depend on the distinction between global and local optima that has hitherto been applied almost exclusively to more exotic routing protocols such as BGP.

报告人简介:
Tim Griffin is an Emeritus Professor of Computer Science at Cambridge University and a fellow of King's College. He has a PhD from Cornell University and has published research in the areas of interactive theorem proving, programming language semantics, database theory, and internet routing. While at Bell Laboratories, AT&T Research, Intel Research, and finally Cambridge University, he contributed to the development of mathematical models that help us understand routing protocols like BGP.
邀请人:计算机科学与技术系 向乔教授