对网络拓扑完成以后，接下来的工作就是进行路由计算了。在学习OSPF路由计算之前，我们先回忆一下使用DV算法计算路由的RIP协议。使用RIP协议的路由器在收到邻居发送过来的路由信息后，将收到的路由信息添加到自己的路由表中。这个路由信息是谁发给我的，我便将自己的下一条指向这个路由器。OSPF协议算法相对来说比较复杂，它采用了SPF算法，SPF算法是OSPF路由协议的基础。SPF算法有时也被称为Dijkstra算法，这是因为最短路径优先算法SPF是Dijkstra发明的。SPF算法将每一个路由器作为根（ROOT）来计算其到每一个目的地路由器的距离，每一个路由器根据一个统一的数据库会计算出路由域的拓扑结构图，该结构图类似于一棵树，在SPF算法中，被称为最短路径树。在OSPF路由协议中，最短路径树的树干长度，即OSPF路由器至每一个目的地路由器的距离，称为OSPF的Cost，其算法为：Cost = 100×106/链路带宽
在这里，链路带宽以bps来表示。也就是说，OSPF的Cost 与链路的带宽成反比，带宽越高，Cost越小，表示OSPF到目的地的距离越近。举例来说，FDDI或快速以太网的Cost为1，2M串行链路的Cost为48，10M以太网的Cost为10等。作为一种典型的链路状态的路由协议，OSPF还得遵循链路状态路由协议的统一算法。链路状态的算法非常简单，在这里将链路状态算法概括为以下四个步骤：
1、当路由器初始化或当网络结构发生变化（例如增减路由器，链路状态发生变化等）时，路由器会产生链路状态广播数据包LSA（Link-State Advertisement），该数据包里包含路由器上所有相连链路，也即为所有端口的状态信息。
2、所有路由器会通过一种被称为刷新（Flooding）的方法来交换链路状态数据。Flooding是指路由器将其LSA数据包传送给所有与其相邻的OSPF路由器，相邻路由器根据其接收到的链路状态信息更新自己的数据库，并将该链路状态信息转送给与其相邻的路由器，直至稳定的一个过程。
3、 当网络重新稳定下来，也可以说OSPF路由协议收敛下来时，所有的路由器会根据其各自的链路状态信息数据库计算出各自的路由表。该路由表中包含路由器到每一个可到达目的地的Cost以及到达该目的地所要转发的下一个路由器（next-hop）。
4、 第4个步骤实际上是指OSPF路由协议的一个特性。当网络状态比较稳定时，网络中传递的链路状态信息是比较少的，或者可以说，当网络稳定时，网络中是比较安静的。这也正是链路状态路由协议区别与距离矢量路由协议的一大特点。
下面我们举例来看OSPF是如何计算路由的。首先，每个路由器都向自己的邻居发送自己的网络拓扑结构，生成一个LSA的数据结构，并且将这个数据结构发送给网络中每一台运行OSPF的路由器，从而每一台运行OSPF协议的路由器将LSA组合起来形成一个LSDB。在每个路由器都得到相同的LSDB后路由器会依据LSA进行路由计算，在进行路由计算的时候路由器会把LSDB打开，进行每一段的搜寻。详细过程可以参考下图：
每一台路由器都已自己为根节点来使用SPF算来计算路由。拿上图来举例说明：RTA收到每台路由器传来的LSA后形成LSDB，然后打开LSDB进行每一段的搜寻。当检索到Type字段为StubNet的时候，RTA知道描述的是一条路由，于是将这条路由添加到自己的路由表中（实际上，这些路由是RTA的本地接口路由）。当检索的LSA中Type字段为Router的时候，RTA知道它是与一台路由器相连（从这条LSA中可以获知相连路由器的接口地址和Router ID以及到达相连路由器的花费）。这个时候，路由计算会停止，RTA会根据Link ID寻找与其相连路由器生成的LSA。因为在LSA的Head中有Router ID，所以，RTA会以Router ID为关键字进行检索从而计算出到RTB的路由，并添加到路由表中。假设RTB还与RTC相连，那么RTA在查找由RTB生成的LSA时，会发现RTB生成的LSA中Type字段也为Router，这个时候RTA停止计算，重新以RTC的Router ID为关键字在LSDB中检索，然后将RTC的路由添加到自己的路由表中，同时RTA得知通过RTB可以到达RTC，在添加路由Metric值时就将RTC到RTB，RTB到RTA的Metric值相加，得到RTA到达RTC的Metric。
OSPF协议路由计算过程
第一步，网络中所有运行OSPF协议的路由器都清楚地描述自己邻居的拓扑结构，并生成LSA。
第二步，将LSA传给给自己相邻的路由器，保证网络中所有路由器都收到其他路由器的LSA，最终形成LSDB。
第三步，通过LSDB计算出一张带权的有向图，最终形成统一的路由表。
本文为IT168网络通信频道（http://net.it168.com）原创。转载请注明出处、作者和文章原始地址。
