文档介绍：摘要
随着 Internet 技术在全球范围的飞速发展，OSPF（Open Shortest Path First）
协议目前已成为 Internet 广域网和 Intranet 企业网广泛采用的路由协议之一。由于
OSPF 协议是基于链路状态的路由协议，同时可以支持大规模的网络（1000 多台
路由器）,所以它存在计算最短路径树（Shortest Path Tree，SPT）所使用的算法复
杂，耗时较长，CPU 的负担较重的问题。
为了缩短 SPT 的计算时间，使得全网能在最短的时间内稳定下来，近年来已
有学者在这方面做了大量的研究。他们将最短路径树算法做了改进提出了最短路
径树动态算法。本文首先对这些已有的动态算法做了分析，给出了这些算法的思
想以及框架，同时也比较了每个算法的不同之处。
在第三章作者给出了基于图的分解的动态最短路径树算法。然后在不同的情
况下分别将该算法与其它的几个算法进行了比较。当单条边的权重发生变化时，
通过理论分析和算法的性能比较得出了影响动态算法的因素，并通过实验对其进
行了验证。在多条边的权重同时发生变化的情况下，文章中使用了一个实际的例
子来统计当有多少条边的权重同时发生变化，使用动态算法与静态算法所需要的
时间相同。
在前两章的研究基础上，在第四章考察了动态最短路径树算法对全网性能的
影响。网络的收敛时间有一部分是由计算 SPT 所需要的时间组成的，以上的动态
算法只是针对单个节点如何快速地计算新的 SPT。但是在全网中，我们更注重的
是所有的节点如何能够快速地得到新的 SPT。所以在本章中首先研究单条边的权
重变化对多棵树的影响，给出了如何判断那些树受到影响的方法以及确定这些受
到影响的树计算新的 SPT 所需要的时间与那些因素有关。最后，通过实验来验证
了作者给出的理论分析。结合以上结论，在本章的最后，使用了一个实际的网络
拓扑图统计了单条边的权重变化时使用静态算法以及各种动态算法下的收敛时
间。并且引出了定义瞬时失效的一种可能思路。
综上，该文章所做的工作主要是 OSPF 协议中的 SPT 计算部分的研究。首先
只是针对算法做了一些研究，然后将算法应用到一个实际的网络拓扑中进行了比
较。
关键词：OSPF 协议，动态最短路径树算法，图的分解，收敛时间
I
ABSTRACT
With the rapid development of the Internet technology in the worldwide, the OSPF
(Open Shortest Path First) protocol which is a link-state based routing protocol is used
widely in the Internet WAN and Intranet enterprise network. Because OSPF is based
on the link state and can support large-scale network (about 1000 routers), it induces
the problems of computing the shortest path tree (SPT) and heavy burden on CPU;
For reducing the time of updating the SPT to make the network steady in the short
time, scholars have done a lot of researches in this area in recent years. They have done
some improvement in the existing static SPT algorithms and given several dynamic
SPT algorithms. In this paper, we not only analyze these dynamic SPT algorithms’
ideas and framewo