西南交通大学硕士研究生学位论文第１页
摘要
ＯＳＰＦ（ｏｐｅｒｌｓｈｏｒｔｅｓｔｐａｔｈｆｉｒｓｔ）是一种专为Ｉｎｔｅｒｎｅｔ设计的链路状态内部网关协议。由于具有路由收敛快，而且只需要较少的路由控制流等特点，因而成为使用十分广泛的内部网关路由协议。ＯｓＰＦｇｒａｃｅｆｕｌｒｅｓｔａｒｔ是ＯｓＰＦ协议的补充协议，目的是使路由器的ＯＳＰＦ路由软件在重启过程中，继续实现报文转发。本论文的研究课题是在路由器上实现ＯＳＰＦｇｒａｃｅｆｕｌｒｅ８ｔａｒｔ协议，具体的工作内容有：
·介绍了ＯＳＰＦ与ＯＳＰＦｇｒａｃｅｆｕｌｒｅｓｔａｒｔ协议的实现原理，分析了协议中的重要处理流程，比较了ｇｒａｃｅｆｕｌｒｅｓｔａｒｔ
与ＯＳＰＦ标准协议的差别。对ＯＳＰＦ软件模块进行了深入的研
究，揭示了该模块与其它路由器软件模块的关系，分析了
ＯＳＰＦ模块的实现方法，总结了其中的重要处理函数与数据结
构。
●对ＯＳＰＦｇｒａｃｅｆｕｌｒｅｓｔａｒｔ协议实现进行了详细设计，介绍
了实现的全部过程与测试方法。利用伪代码描述了实现中的
重要处理函数，列出了重要的数据结构。最终在Ｘ×公司的
路由器上实现了该软件，并且通过测试。该协议的实现较大
的改善了路由器的稳定性、可维护性，提高了该系列产品的
竞争能力。
●针对ＯＳＰＦｇｒａｃｅｆｕｌｒｅｓｔａｒ协议中的不足，提出了对该协
议的改进意见，并且设计了具体的改进方法。该改进将有助
于增强该协议的性能，改善路由波动对网络的不良影响。
关键词：ＯＳＰＦ；ｇｒａｃｅｆｕｌｒｅｓｔａｒｔ；路由协议；ｈｅｌｐｅｒ
亘壹窑鎏盔兰巫主塑窒兰主丝迨塞箜！基
Ａｂｓｔｒａｃｔ
ＯＳＰＦ（ｏｐｅｎｓｈｏｒｔｅｓｔｐａｔｈｆｉｒｓｔ）ｉｓａｋｉｎｄｏｆｌｉｎｋ－ｓｔａｔｅｉｎｔｅｒｎａｌｇａｔｅｗａｙｐｒｏｔｏｃ０１ａｎｄｄｅｓｉｇｎｅｄｓｐｅｃｉａｌｌｙｆｏｒＩｎｔｅｒｌｉｅｔ．ＯＳＰＦｒｅｃａｌｃｕｌａｔｅｓｒｏｕｔｅｓｑｕｉｃｋｌＹｉｎｔｈｅｆａｃｅｏｆｔｏｐ０１０９ｉｃａｌｃｈａｎｇｅｓ，ｕｔｉｌｉｚｉｎｇｔｈｅｍｉｎｉｍｕｍｏｆｒｏｕｔｉｎｇｐｒｏｔｏｃ０１ｔｒａｆｆｉｃ．ＳｏｉｔｉｓｕｓｅｄｗｉｄｅｌｙｉｎＩｎｔｅｒｎｅｔ．ＯＳＰＦｇｒａｃｅｆｕｌｒｅｓｔａｒｔｐｒｏｔｏｃ０１，ａｎｉｍｐｌｅｍｅｎｔａｔｉｏｉ％ｔｏＯＳＰＦ，ｈａｓｔｈｅｆｕｎｃｔｉｏｎｏｆｍａｉｎｔａｉｎｉｎｇｔｈｅｄａｔａｆｏｒｗａｒｄｉｎｇｃａｐａｂｉｌｉｔｙｉｎｔｈｅｐｒｏｃｅｓｓｏｆｔｈｅＯＳＰＦｂｅｉｎｇｒｅｓｔａｒｔｅｄｉｎｔｈｅｒｏｕｔｅｒ．ＴｈｉｓｔｈｅｓｉｓｉｓａｂｏｕｔｈｏｗｔｏｒｅａｌｉｚｅｔｈｅＯＳＰＦｇｒａｃｅｆｕｌｒｅｓｔａｒｔ．Ａｎｄｔｈｅｍｓｉｎｊｏｂｓｄｏｎｅａｒｅａｓｆｏｌｌｏｗｓ：
●ＴｈｅｔｈｅｏｒｙｏｆＯＳＰＦａｎｄＯＳＰＦｇｒａｃｅｆｕｌｒｅｓｔａｒｔｉｓ
ｉｎｔｒｏｄｕｃｅｄａｎｄｉｍｐｏｒｔａｎｔｐｒｏｃｅｓｓｉｎｇｆｌＯＷＳｉｎｔｈｅｓｅ
ｐｒｏｔＯＣ０１Ｓａｒｅａｎａｌｙｚｅｄ．ＢｅｓＩＤｅｓ，ｔｈｅｄｉｆｆｅｒｅｎｃｅａｎｄ
ｃｏｍｐａｒａｔｉｏｎｏｆｔｈｏｓｅｔｗｏｐｒｏｔｏｃ０１ｓａｒｅｍａｄｅ．Ｏｎｔｈｅ
ｇｒｏｕｎｄｏｆｔｈｅｐｒｏｆｏｕｎｄｒｅｓｅａｒｃｈｏｆＯＳＰＦｒｏｕｔｉｎｇｓｏｆｔｗａｒｅ
ｍｏｄｕｌｅ．ｔｈｅｒｅｌａｔｉｏｎｓｈｉＰｂｅｔｗｅｅｎＯＳＰＦａｎｄｏｔｈｅｒｍｏｄｕｌｅｓ
ｉｎｒｏｕｔｅｒｉｓｍａｄｅｃｌｅａｒａｎｄｉｍｐｏｒｔａｎｔｐｒｏｃｅｓｓｉｎｇｆｌＯＷＳ
ａｎｄｄａｔａｓｔｒｕｏｔａｒｅｉｎｉｍｐｌｅｍｅｎｔａｔｉｏｎａｒｅｃｏｎｃｌｕｄｅｄａｓ
ｗｅｌｌ．
●ＴｈｅｄｅｔａｉｌｅｄｄｅｓｉｇｎｏｆＯＳＰＦｇｒａｅｅｆｕｌｒｅｓｔａｒｔｐｒｏｔｏｃｏｌ
ｉｓｒｅａｌｉｚｅｄａｎｄｔｈｅｄｅｔａｉｌｓｏｆｔｈｅｗｈ０１ｅｉｍｐｌｅｍｅｎｔａｔｉｏｎ
ｐｒｏｃｅｄｕｒｅｉｓｉｎｔｒｏｄｕｃｅｄ．Ｍｅａｎｗｈｉｌｅ．ｓｏｍｅｏｆｔｈｅ
ｉｍｐｏｒｔａｎｔｐｒｏｃｅｓｓｉｎｇｆｉｏｗｉｓｄｅｓｃｒｉｂｅｄｂｙｐｓｅｕｄｏｃｏｄｅ
react router的state和searchａｎｄｔｈｅｋｅｙｄａｔａｓｔｒｕｃｔｕｒｅｓａｒｅ１ｉｓｔｅｄ。ＯＳＰＦｇｒａｃｅｆｕｌ
ｒｅｓｔａｒｔｗａｓｔｅｓｔｅｄａｎｄｒｅａｌｉｚｅｄｉｎＸＸｓｅｒｉｅｓｏｆ
ｒｏｕｔｅｒｓ．ｗｈｉｃｈｇｒｅａｔｌｙｉｍｐｒｏｖｅｓｔｈｅｓｔａｂｉｌｉｔｙａｎｄ
ｍａｉｎｔａｉｎａｂｉｌｉｔｙｏｆｒｏｕｔｅｒａｎｄｉｎｃｒｅａｓｅｓｔｈｅｉｒ
ｃｏｍｐｅｔｉｔｉｖｅａｂｉｌｉｔＹ．
亘亘銮鎏查堂堡圭婴壅生堂垡笙塞整巴基●ＦｏｒｉｍｐｒｏｖｉｎｇｔｈｅｐｅｒｆｏｒｍａｎｃｅｏｆＯＳＰＦｇｒａｃｅｆｕｌｒｅｓｔａｒｔ
ｐｒｏｔｏｃ０１ａｎｄｒｅｄｕｃｉｎｇｔｈｅｎｅｇａｔｉｖｅｅｆｆｅｃｔｏｆｔｈｅｒｏｕｔｅｆｌａｐｐｉｎｇｔｏｎｅｔｗｏｒｋ，ｓｏｍｅｉｄｅａｓａｒｅｐｒｅｓｅｎｔｅｄａｎｄｔｈｅｓＰｅｃｉｆｉａｍｅｔｈｏｄｓａｒｅｐｒｏｖｉｄｅｄ．
Ｋｅｙｗｏｒｄｓ：ＯＳＰＦ：ｇｒａｃｅｆｕｌｒｅｓｔａｒｔ：ｒｏｕｔｉｎｇｐｒｏｔｏｃｏｌ：ｈｅｌｐｅｒ
第１章绪论
１。１课题研究背景与意义
ＯＳＰＦ（ｏｐｅｎｓｈｏｒｔｅｓｔｐａｔｈｆｉｒｓｔ，开放最短路径优先）是Ｉｎｔｅｒｎｅｔ路由选择协议的一种，最初是为替代ＲＩＰ协议而开发的，目前已成为构建大型网络最常用的路由选择协议。通过该协议，网络中的每一个路由器都保存一个关于整个网络拓朴结构的链路状态数据库，在该数据库上运行ＳＰＦ算法，即可计算出到网络中各节点的最短距离。ＯＳＰＦｇｒａｃｅｆｕｌｒｅｓｔａｒｔ协议是ＯＳＰＦ的一个补充协议，该协议的目的是使ＯＳＰＦ软件在重新启动的过程中，路由器依然能够起到报文转发的作用。
本论文研究课题的主要任务是对ＯＳＰＦｇｒａｃｅｆｕｌｒｅｓｔａｒｔ协议进行研究与实现。０ＳＰＦｇｒａｃｅｆｕｌｒｅｓｔａｒｔ协议提供了当ＯｓＰＦ路由控制软件重新启动时，路由器进行报文无间断转发的方法。该协议的实现原理如下所述，当一个ＯＳＰＦ进程准备重新启动时会首先保存自己的路由表到核心路由表，然后向所有邻接发送一个ｇｒａｃ—Ｌｓａ，向邻接表明要执行ｇｒａｃｅｆｕｌｒｅｓｔａｒｔ的原因、时间。然后重新启动。该路由器的所有邻接在接收到该报文后会继续利
用重启路由器的路由表进行报文转发，这样不会影响报文转发，这时的邻接被称为重启路由器的ｈｅｌｐｅｒ。为了防止由于重启路由器不参与路由信息交互而导致的路由错误，只要网络的拓扑发生了变化，ｈｅｌｐｅｒ就恢复到标准的ＯＳＰＦ运行，重新计算绕过重启路由器的路由。
当今很多高端路由器的软件设计可以在更新路由表的控制功能不存在的情况下，支持报文转发，这意味着当路由协议重启过程中，数据包可以继续转发。控制软件的切换不会影响到客户正在进行的侄务，网络可以继续运行。路由决定与转发功能的分离，以及报文的无中断转发功能为“ｇｒａｃｅｆｕｌｒｅｓｔａｒｔ”的实现提供了基础。
ＯＳＰＦｇｒａｃｅｆｕＩｒｅｓｔａｒｔ协议的提出旨在最小化ＯｓＰＦ软件重新启动对网络使用的影响。如果没有“ｇｒａｃｅｆｕｌｒｅｓｔａｒｔ”功能，当ＯＳＰＦ软件重新启动时，其相应的邻居会断掉与该路由器的连接，由此产生的路由计算和网络范围内的路由更新会消耗大量的资源，并可能产生由于网络中的路由器无法及时更新数据库而导致的路由黑洞和循环，影响网络中数据的正常转发。实现“ｇｒａｃｅｆｕｌｒｅｓｔａｒｔ”功能后将会大大减少路由协议软件启动对网络使用的影响。即当ＯＳＰＦ软件在重新启动过程中，其邻居路由器仍然保持与该路由器的连接，从而在不影响报文转发的条件下，重启动协议。“ＯＳＰＦｇｒａｃｅｆｕｌｒｅｓｔａｒｔ”与无中断转发功能为网络控制设备的稳定性提供了新的支持，实现了ＯＳＰＦ协议的平滑重启。在对网络核心设备稳定性要求越来越商的今天，该功能无疑极大的增强了路由器的性能，同时也为网络控制软件的升级、维护提供了方便的手段。
ＯＳＰＦｇｒａｃｅｆｕｌｒｅｓｔａｒｔ协议作为ＯＳＰＦ协议的加强协议，已经在很多公司生产的路由器上得到了实现，如在思科公司路由器、Ｊｕｎｉｐｅｒ网络公司的Ｈ系列路由器、Ｆｏｒｏｅｌ０公司的Ｅ系列路由器、诺基亚公司的ＳｍａｒｔＥｄａｇｅ路由器上得到了实现。这些路由器在实际应用中，显示出了优秀的性能，提高了网络的稳定性。本课题的研究将最终在××路由器上实现ＯＳＰＦｇｒａｃｅｆｕｌｒｅｓｔａｒｔ协议，这将进一步提高××路由器的稳定性，扩大其兼容性，增强产品韵竞争力。
１．２课题研究的主要内容
课题主要内容是在××系列路由器现有的ＯＳＰＦ软件的基础之上，实现ＯＳＰＦｇｒａｃｅｆｕｌｒｅｓｔａｒｔ。因此围绕该目标进行了如下的工作：
ａ）熟悉Ｖｘｗｏｒｋｓ操作系统及其开发环境Ｔｏｎａｄｅ，理解并且实践嵌入式编程，熟练掌握路由器的路由协议、接口配置。理解ＯＳＰＦ协议，分析现有ＯＳＰＦ软件的总体架构与其组成模块：邻接状态机、接口状态机、主循环、ｓＰＦ算法、ｆ１００ｄｉｎｇ过程、与其它软件模块