论文总字数：19877字

摘 要

思科系统实施的SPF算法其实可以更加快速地计算出路由。这种变化造成了两种类型的SPF计算:完整的和局部的。

正如在链路状念通告中所表达的那样，当网络的拓扑结构发生改变时运行完整的SPF算法。而不是因为汇总的LSA，汇总的LSA导致部分的SPF运行。

在OSPF中，部分SPF只与外部的和汇总的LSA改变有关。基本上，如果网络通过外部或者局部LSA发生抖动，那么就运行局部SPF。换句话说，当区域的拓扑结构没有改变而只是一些IP的前缀发生抖动时，部分的SPF算法激活区域内的IP前缀发生改变时就激活完全SPF重新计算。

关键字：OSPF，SPF，LSA

Research and Application of Sequence Number Gain Based on SPF Algorithms

Abstract

The Cisco Systems implementation of the SPF algorithm allows for quicker ways to calculate routes. This change has resulted in two types of SPF calculations: full and partial.
The full SPF algorithm is run only when there is a topology change, as expressed in router link-state advertisements , not for summary LSAs. Summary LSAs cause a partial SPF to be run.
In OSPF, partial SPF relates to external and summary LSAs' change only. Basically, if a network flap occurs via an external or summary LSA, you run partial SPF. In other words, partial SPF is invoked when topology of the area did not change but some IP prefix flapped. An IP prefix change inside the area invokes the full SPF recalculation.

Keyword：OSPF，SPF，LSA

目录

摘 要 I

Abstract II

第一章 引言 1

1.1课题研究背景 1

1.2 SPF算法 1

1.3 研究OSPF路由协议的现状 1

第二章 SPF算法的研究与设计 2

2.1 SPF算法的数据库 2

2.1.1 树数据库 2

2.1.2 候选对象数据库 2

2.3 SPF算法的序列号的实验 4

2.4 SPF算法的衍生 11

第三章 OSPF的序列号的研究 12

3.1 OSPF的工作原理 12

3.2 OSPF的序列号的研究 12

3.2.1 线性序列号空间 13

3.2.2 循环序列号空间 14

3.2.3 棒棒糖形序列号空间 15

3.3 OSPF的序列号的实验 16

3.4 OSPF防环机制详解 18

3.4.1 Type-1 LSA及Type-2 LSA的防环 18

3.4.2 Type-3 LSA及Type-4 LSA的防环 20

3.4.3 Type-5 LSA的防环 22

3.5 LSA的老化机制 22

第四章 结论 24

参考文献 25

致 谢 26

第一章 引言

1.1课题研究背景

SPF算法是现在网络中最主流的路由协议所使用的算法，被应用与链路状态协议中，具有层次化设计的优点，同时SPF算法还将保证网络的最优路径的选择，SPF中的序列号不仅用于计算网络的拓扑，还用于网络路由信息的更新，因此序列号的增益方式和相关的应用就成为SPF算法的核心，通过对此方面的研究了解OSPF和ISIS协议的运行机理，同时理解SPF算法对LSA在传递过程中序列号的增长模式，进而对主流网络路由协议在企业网络中和运营商网络中的应用进行深入研究，以达到对现代互联网整体选路的深入理解。例如：有些人针对有线电视网络中的组播，提出了一种新的方法。将SPF算法用于计算，有线电视网络，传输链路中的最短路径开销，构建树形结构以此来建立组播协议分发树,以期为传统有线电视网的发展创新做有益的尝试。

1.2 SPF算法

开销*链路带宽（bps）=100×(10)^6，可见OSPF开销与链路带宽成反比，带宽越低，开销越大，表示开放式最短路径优先路由到想要去的路由器的距离越远。

SPF度量值是开销，而开销都是以100 M/接口为标准计算出来的。所以到某一个指定的想要去的目的地路由器的路径开销，就是这台路由器到想要去的目的地路由器之间的所有链路出接口的开销总和。

为了在LSA数据库里生成路由表，路由器以自身为根建造最短路径树。SPF算法算出到网络上每一个节点的开销最低的路径，路由器将计算出路径的路由存储到自身的路由表中。

OSPF路由协议不会广播它所有的路由信息，他使用hello报文来维持邻接关系。如果在dead-interval内没有收到来自邻居的hello报文，那就判定该邻居不存在。OSPF是递增式路由更新，只在拓扑结构变化时，才发出更新信息。当LSA的时间达到1800秒(LSA Refresh Time，LSA刷新间隔)时，则发送一个该LSA的更新。

1.3 研究OSPF路由协议的现状

IETF为了庞大的需求形成了一个开发用于大型异构网络的OSPF的工作组。新OSPF已取得些成功，所以做基础的SPF算法大受欢迎，它使路由基于链路状态选择，而不是距离向量。

第一版OSPF是IETF于1989年开发，体现在RFC 1131中，但很快改进，第2版OSPF体现在RFC 1247中。OSPFv2更新文档改进了开放标准，按版本顺序先后出现在RFC 1583、2178和2328中。

OSPF推动了路由协议的发展，其特色是在路由广播中采用授权机制提高了网络的安全性；子网掩码技术的引入提高了互联网系统中IP地址的利用率；减少路由以减轻路由器的负担。这些技术优化了网络结构，提升了网络间的通信效率。

OSPF用在同一个路由域中，路由域（routing domain）指autonomous system（AS,自治系统），是组通过统一的路由政策或路由协议交换路由信息的网络。AS中，路由器维护有相同自治系统结构的数据库，存储域内相应链路状态信息，计算路由表。

第二章 SPF算法的研究与设计

2.1 SPF算法的数据库

2.1.1 树数据库

通 过 在 数 据 库 里 面 添 加 链 路 ， 将 分 支 添 加 到 最 短 路 径 树 中 。 算 法 完 成 后 ， 树 数 据 库 可 以 描 述 最 短 路 径 树 。

2.1.2 候选对象数据库

链 路 按 指 定 的 顺 序 从 链 路 状 态 数 据 库 复 制 到 数 据 库 ， 作 为 要 添 加 到 树 数 据 库 的 候 选 对 象 。 因 此 ， 当 算 法 完 成 时 ， 数 据 库 为 空 。

2.1.3 链路状态数据库

网 络 中 的 所 有 链 路 都 存 储 在 这 个 数 据 库 中 。

2.2 SPF算法计算过程

第 1 步 ： 路 由 器 初 始 化 树 数 据 库 ， 并 将 自 己 作 树 根 。代 价 为 0 。

第 2 步 ： 查 看 链 路 状 态 数 据 库 ， 并 加 描 述 根 路 径 的 所 有 路 由 器 邻 居 链 路 三 元 组 到 候 选 对 象 数 据 库 。

剩余内容已隐藏，请支付后下载全文，论文总字数：19877字