OSPF:使用SPF算法的路由传播
一、引言
RIP协议使用矢量距离算法在网关和主机中传播路由信息，其最大的优点就
是简单。RIP通过限制从源地址到目的地址路径上的跳数，有效防止了路由选择循环的无限延续，从而保证了网络的稳定性。然而随着Internet规模的不断扩大，RIP协议的缺点就更加严重。首先就是RIP限制了网络的规模，它能使用的最大距离为15（16为不可达）；其次路由器之间交换的完整路由信息开销太大。最后，“坏消息传播得慢”，使许多更新过程的收敛时间过长。
开放最短路径优先OSPF(Open Shortest Path First)使用链路状态算法来传播选路信息，它使用SPF算法(Dijkstra算法)。其要点如下：
1、所有的路由器都维持一个链路状态数据库，只有可达邻站的链路状态信
息才存入链路状态数据库，这个数据库实际上就是整个互连网的拓扑结构图。而使用RIP协议的路由器只各自知道到所有目的网络的下一站路由器，但却不知道全网的拓扑结构。
2、OSPF让每一个链路状态都带上一个32bit的序号（增长的速率不得超过每5秒1次），序号越大状态越新。每一个路由器用链路状态数据库中的数据，算出自己的路由表。
3、要网络拓扑发生任何变化，链路状态数据库就能很快地进行更新，使各
个路由器能够重新计算出新的路由表。
4、OSPF依靠各路由器之间的频繁交换信息来建立链路状态数据库，并维持这数据库在全网范围内的一致性（链路状态数据库的同步）。
5、OSPF不象RIP使用运输层的用户数据报UDP进行传送，而是直接用IP
数据报传送，并且数据报很短。（图1）
IP数据报首部(20字节)
OSPF报文首部(24字节)
类型1至5的OSPF报文
图1 OSPF使用IP数据报传送
由于一个路由器的链路状态只涉及到与相邻路由器的连通状态，因而与整个互连网的规模无关。
二、基本概念
1、链路状态：所谓一个路由器的“链路状态”就是该路由器都和哪些网
络或路由器相邻，以及将数据发往这些网络或路由器所需的费用。
2、自治系统：一般简称为AS。一个自治系统是一个互连网络，其最重要的特点是它有权自主地决定在本系统内应采用何种路由选择协议。
3、内部网关协议IGP：即在一个自治系统内部使用的路由选择协议。
4、区域：OSPF允许进一步地将互连网划分成一些区域。每个区域都包含一
组相邻的网络及所连接的主机，每个网关都必须被放置在其中的一个区域中。每一区域内的拓扑结构对区域外是不可见的。由于保持了区域拓扑的独立性，因此路由选择交换信息量比AS未被分隔时小。带有多个接口的路由器可加入到多个区域，这些所谓的区域边界路由器为每个区域维护一个单独的拓扑数据库。
5、链路状态数据库：是与路由器相关的网络的整体结构图，它包含从同一
区域中所有路由器接收的LSA（链路状态通告：包含有关链路接口、所用计量标准及其他变量信息）。
6、OSPF主干：负责在两个区域之间发送路由选择信息，它由区域边界路由
器、跨区域网络及与其连接的路由器组成。运行OSPF的AS边界路由器通过外部网关协议或配置信息了解外部路由。
7、指定的路由器：如果某个网络上接有N个网关，则它们可形成N(N-1)/2个可能的邻接。每当某个网关传送一个报文时，它会向所有N-1个邻接网关发送该报文，因而共传送(N-1)²个链路状态。当指定一个网关作为指定路由器后，每个网关都变得与指定路由器有邻接关系，而与其它网关不存在邻接关系，与特定网络相连的N个网关之间仅有N-1个邻接，传送的信息量大为减少。指定路由器的另一项任务是为该网络发送链路状态通告，传送链路状态更新数据。
8、后备指定路由器：当多重接入网络上的网关没有选出指定路由器的时候，后备指定路由器成为指定路由器，再在余下的网关中选出新的后备指定路由器。此时N个网关之间可能有2N-3个邻接关系。
三、OSPF分组格式
版本号（1）
类型（1）
数据分组长度（2）
路由器ID（4）
区域ID（4）
校验和（2）
鉴别类型（2）
鉴别（8）
数据（可变）
图2 OSPF分组格式
各字段含义如下（图2）：
版本号字段：给出了OSPF的版本。
类型字段：OSPF共有五种报文类型：
类型1：Hello报文，用来发现和维持邻站的可达性；
类型2：Database Description报文，向邻站给出自己的链路状态数据库中的所有链路状态项目的摘要信息；
类型3：Link State Request报文，向对方请求发送某些链路状态项目的详细信息；
类型4：Link State Update报文，用洪泛法向全网更新链路状态；
类型5：Link State Acknowledgment报文，对链路更新报文的确认。
数据分组长度字段：OSPF分组的长度，包括分组首部。
路由器ID字段：标识数据分组的源地。
区域ID字段：标识分组所属的区域。
校验和字段：检验分组内容。
鉴别类型字段：所有OSPF协议路由器间的数据交换都需要被鉴别，保证只有可信赖的路由器才能传送路由信息。
鉴别字段：包括鉴别信息。
数据：类型1至类型5的OSPF报文。
四、链路状态数据库的建立和更新
每个路由器定期发送一个链路状态通告LSA，以提供有关路由器的邻接信息，或通知其他路由器某个路由器的状态改变了。通过把已经建立的邻接路由器与连接状态相比较，可以快速检测出失效路由器，并适时修改网络的链路状态数据库，每一路由器以其为根据计算一个最短路径树，该最短路径树提供一个路由选择表。OSPF规定，每两个相邻路由器每隔10秒要交换一次Hello报文，以确知哪些邻站是可达的。只有可达邻站的链路状态信息才存入链路状态数据库，并由此算出路由表来。若有40秒没有收到某个相邻路由器发来的Hello报文，则可认为该相邻路由器不可达，应立即修改链路状态数据库，并重新计算路由表。
当一个路由器刚开始工作时，它只能通过Hello报文得知它有哪些相邻的路由器在工作，以及将数据发往相邻路由器所需的费用。OSPF让每一个路由器用Database Description报文和相邻路由器交换本数据库中已有的链路状态摘要信息（指出有哪些路由器的链路状态信息已写入数据库）。之后路由器使用Link State Request报文向对方请求发送自己所缺的某些链路状态项目的详细信息。通过一系列的这种报文交换，全网的链路状态数据库就建立起来了。
在网络运行的过程中，只要一个路由器的链路状态发生变化，该路由器就要使用Link State Update报文，用洪泛法向全网更新链路状态。当一个重复的报文到达时，网关丢弃该报文，而不发送它的副本。为了确保链路状态数据库与全网的状态保持一致，OSPF还规定每隔一段时间，如30分钟要刷新一次数据库中的链路状态。
五、OSPF的图论模型
OSPF利用网络拓扑的图论模型来计算最短路径。OSPF拓扑图中的每个节点或者对应一个网关，或者对应一个网络。如果网中两实体存在物理连接，则OSPF图在代表实体的两个节点之间有一对有向边，每个边都有一个“权”。OSPF根据沿着花费最小的路径转发数据报的原则建立选路表。
六、OSPF的有限状态机模型
有两个原因使Hello对多重接入网络特别重要。首先，网络硬件并不检查或报告网关的崩溃或重启，为了互相保留对方的状态信息，与多重接入网络相连接的两个网关必须交换分组。第二，与某个多重接入网络相连接的任意两个网关之间都能够直接通信，因此OSPF必须防止这些网关形成过多的邻接。
OSPF标准使用了一个有限状态机来规范使用Hello的网关如何与相邻网关交互作用。
一般来说，所有相邻网关最初都处于DOWN状态，表示并未准备通信。当一个网关接收到相邻网关发出的Hello分组后，它将相邻网关从DOWN状态变迁到INIT状态。在此之后，相邻网关或者进入2-WAY状态，或者进入EXSTART状态。其中2-WAY状态表示通信已经建立，但相邻网关与该网关之间没有邻接关系，EXSTART状态表示不但已经建立通信，而且两个网关之间存在经过双方协商同意的邻接关系。
当协商结束时，网关开始交换链路状态数据库中的信息，以确保它们有完全相同的底层互连网拓扑图。两个相邻网关中的一个成为“主网关”，它查询另一个网关数据库中的信息。非主网关返回数据库描述分组，以通知主网关最近接收到的该拓扑图中每条链路的信息。在建立邻接关系时，交换信息尤其重要，因为在网络断连期间，某个网关中的信息可能变为过时的信息。每个拓扑信息分组中包含一个序号，因此网关能够知道相邻网关数据库中的描述信息是否比该网关自身数据库中的信息更新。在交换完成且所有拓扑信息都已装载后，网关进入FULL状态。在FULL状态中，两个网关定期交换分组，以保持连接。
