前言

关于路由协议，可以追溯到ARPANET创立之初，那个时候BBN公司负责建立分组交换网络，网络节点被称为接口消息处理器（IMP）。IMP之间运行BBN公司独有的基于Bellman-Ford算法的距离矢量路由协议，采用时延作为度量路径优劣的权重，通过定期读取链路接口队列长度来计算时延值，队列长度越长，意味着数据被转发所需的时间越长。基于时延的最优路由可以将数据包引导经过平均队列较短的路径，从而更快地将数据传送到目的地。由于距离矢量协议受限于交换整个路由表、逐级传播路由以及基于队列长度无法准确度量转发时延等技术机制的约束，出现了收敛慢、路由振荡以及路由环路等问题，无法支撑大规模网络，难以适用于快速扩张的ARPANET。

从1979年开始，ARPANET部署一种新的基于Dijkstra算法的链路状态路由协议，主要在两个方面进行改变：一是节点之间不交换路由信息，而交互链路状态信息，协议报文长度变短、频率变低，链路状态信息通过洪泛方式在全网通告，使得每个节点拥有相同的拓扑信息，并独立地进行路由计算，在网络变化时，收敛时间快，且不会产生环路；二是重新设计了链路权重的计算方法，使之与数据包的本地处理时间、转发包的长度、链路带宽等因素密切相关，期望精确地反映数据包在节点之间的传输时延，使得端到端数据转发能够更加准确地沿着最小时延路径转发。链路状态协议较好地适应了当时ARPANET的发展。

伴随着TCP/IP技术的成熟，ARPANET整体迁移到TCP/IP技术体制。各种应用在Internet上不断涌现，促进了Internet飞速发展，吸引了越来越多的用户，Internet承载的流量越来越大。在轻载情况下，链路状态路由协议运行良好，但是在网络负载逐渐增大时，又出现了新问题。按照当时的链路权重计算方法，当链路负载较重时，会计算出非常大的链路时延值，引发路由改变，促使所有流量都从该高代价链路上迁走；之后，链路时延值又变得异常小，所有流量又迁回，这样端到端流量经过的路径不停地交替振荡。为此，将权重计算方法进一步修订为归一化跳数。当网络负载很重时，在将流量保持在原路径的条件下，尝试发现相对较长的路径。如果存在，则将部分流量迁移到相对较长的路径上；否则，将流量保持在原路径上。这种约束方法，避免将所有流量同时迁移走后，又迁移回来而引起流量振荡。

从基于Bellman-Ford算法的距离矢量路由协议，到基于Dijkstra算法的链路状态路由协议，它们都采用了基于链路负载变化而进行动态选路的路由机制，这意味着链路负载变化与路由计算相依相存。从单个链路的视图来看，链路流量负载的增加，导致链路代价增大，触发网络节点进行路由计算，进而将一部分流量从高负载链路迁移走，这使得下一个周期链路代价下降。这又促使网络节点重新进行路由计算，可能将一部分流量重新迁回该链路。这个过程将不断重复，直到新的链路代价与上次链路代价相同，重复才会停止，网络进入平衡态。从全网视图来看，当部分流量在链路之间迁移时，同样也会影响其他链路的代价变化，进而对所有链路上的所有流量都产生影响。这是一个非常复杂的反馈调整自适应模型。网络路由可能会一直处于计算调整状态。当链路代价变化不会对路由计算产生影响时，网络路由稳定，流量路径稳定，整个网络进入稳定的平衡态。以流量为权重基础的路由算法必须不断地进行路由计算和路径调整，以期望能够到达平衡态。而实际上，网络流量瞬息万变，平衡态是难以达成的。

随着Internet逐步商业化，网络运营者从运营网络的角度，需要为用户提供差异化服务以获取更多的经济效益。这个时候提升所有网络用户的服务体验并不是网络运营者追求的目标，毕竟IP提供的是尽力而为的服务。与此同时，整个Internet不再由一家公司来运营，网络设备制造商日益增多，无论是网络服务提供商还是网络设备制造商，它们之间既要竞争又要合作。综合技术、经济、政策等方面的诸多因素，伴随着路由协议的标准化，多数的路由算法不再采用动态权重，而转变为采用静态权重。路由协议聚焦于网络拓扑的变化，及时感知和响应拓扑变化，追求快速收敛，减少环路的产生，避免路由振荡，提升路由的稳定性，这些均成为大规模网络环境下路由协议关注的目标。

基于Dijkstra算法的链路状态路由协议在现网运行达10年之久，基于积累的工程实践经验，1989年IETF发布了OSPF协议的第一个版本，但并未得到广泛应用。1998年稳定版本的OSPFv2正式发布并被使用至今。在这20多年里，OSPF协议的基本原理和机制一直保持不变，足以见证该协议强大的生命力。在协议提出伊始，围绕协议框架，IETF注重于协议机制优化，一方面加强最短路径计算的效率，提升协议收敛速度；另一方面注重于协议可扩展性。这个时期主要以协议基本框架为基础，提出各种优化技术，使得OSPF能够支撑多种类型的大规模网络建设。但伴随着网络应用需求发展和技术创新驱动，OSPF协议已经逐渐沉淀为互联网架构的基础支撑模块，基于OSPF的链路状态特性和全域拓扑发现机制，可以拓展支撑新兴网络应用需求，例如通过OSPF承载链路和带宽资源信息以实现流量工程等。这个时候OSPF变成了一种支撑其他网络技术的工具。OSPF的基础协议架构中并未考虑这些功能拓展，于是，IETF通过引入不透明LSA技术来构建一个以OSPF为基础的协议拓展框架。这对OSPF协议而言是一个巨大的改变，未来依托网络拓扑且需要分布式扩散相关信息的技术都可以通过对OSPF进行拓展实现，因此，OSPF可以持续迸发蓬勃生命力。基于OSPF拓展能力支持Segment Routing技术就是一个典型案例，通过定义几种新的LSA类型承载Segment ID信息，就可以完成段标签的分发，有力支撑新一代网络技术的构建和增量部署。

随着SDN/NFV技术的发展，网络设备的集中化运维管理已成为发展趋势。OSPF已经成为构建下一代运营商骨干网络、云数据中心网络的核心支撑协议之一。本书以OSPF原理为出发点，系统梳理了自OSPFv2协议诞生至今，IETF发布的以OSPF协议为基础的各类功能拓展，把各类零散的知识点进行了整理归纳和总结，希望能够给读者呈现OSPF协议的知识全貌。读者可以将本书作为原理性书籍来学习，通过阅读第2～4章可以深入掌握协议的设计原理和工作机制；可以将本书作为工程应用书籍来参考，参阅第5、6、8、9章了解相关拓展机制和优化方法，支持网络规划设计与优化部署；还可以将本书作为学习Segment Routing技术的一个入口，通过阅读第7～9章了解扩展OSPF协议支持Segment Routing标签分发的原理，以及使用Segment Routing技术改造现有网络，提升网络弹性的方法。

本书的写作经历了近3年时间，由于我平时科研及教学工作较忙，全书内容都是在节假日撰写，其间大女儿升入初中，二女儿出生，还经历了新冠肺炎疫情。本书原计划在二女儿出生时成稿，总因为科研工作一拖再拖。感谢父母含辛茹苦的养育，他们一直教导着我诚信做人、踏实做事，要积极上进、不断进取。感谢我的岳父母，他们一直不辞辛苦地帮助我照顾家庭，对我工作给予了巨大的支持，他们是我的坚实后盾和无形的精神力量支撑，一直关注我书稿的写作进度，并分担了很多本应该由我来做的事情。感谢我的妻子，为了保证我的写作时间，她承担了全部的家务，担负起培养和养育孩子的重任。还要感谢我的两个可爱的女儿，她们给我带来的无穷快乐和挑战，也给了我与她们一起成长的机会，让我的人生更加美好。

本书的出版得到国家重点研发计划课题（No.2017YFB0800304）的资助，在此一并感谢。

作者
2021年5月于郑州