OSPF协议算法
通过前两课的学习我们知道OSPF是一种链路状态算法，在介绍链路状态算法之前，我们再来回忆一下DV算法，比如说RIP，RIP协议在计算路由的时候首先把自己已知的路由发送给自己的邻居，当这个邻居收到路由之后会与自己的路由进行比较，然后取一个最优的路由添加到路由表中，同时将下一条指向发给自己路由的路由器。而OSPF链路状态协议采用了一种全新的设计思想，在网络中运行OSPF的路由器在向外发送的信息中不仅包含了路由信息，还包括了链路的状态信息及网络的拓扑结构（拓扑结构可以理解为，在网络中使用的接口，每个接口的网络状况是什么样的，以及在网络中的互连情况）。
OSPF协议通过LSA描述网络拓扑
在了解了OSPF协议的算法后，下面我们来看下OSPF协议是如何来描述这种信息的。首先，现存的网络中的任何形式的组网精选后都不外乎以下四种：
第一种：为整个网段中只有路由器本身运行OSPF，与这台路由器相连的接口的其它设备都不运行OSPF。
第二种：两台运行OSPF协议的路由器通过点对点链路相连（比如PPP/HDLC）。
第三种：一台路由器在同一个网段中通过点对多点链路与多个路由器相连，而这多个路由器之间不存在互连关系。
第四种：一台路由器在一个网段中通过点对多点链路与多个路由器相连，但这多个路由器之间存在互连关系（也就是说在网络中的路由器都是两两互通，不需要转发而可以直接相互访问）。
四种网络拓扑如下图所示：
在对网络拓扑进行抽象描述后，我们具体讲述下上图中RTA是如何描述它身边的这四种网络情况。
首先我们来看第一种（整个网段中只有路由器本身运行OSPF，与这台路由器相连的接口的其它设备都不运行OSPF）无论什么路由协议，归根结底都是为了计算出路由。在第一种网络结构中，首先要描述出自己已知的路由，那么在运行OSPF的路由器中该如何描述呢？
Link Id:192.168.1.0 /本地接口网段/
Data: 255.255.255.0 /掩码/
Type: StubNet (3) /类型/
Metric: 5 /花费值/
由于有了网段和掩码我们就可以描述出这条路由，上述例子描述了192.168.1.0/24网段的路由，同时，到达这个网段的花费值为5。并且把第一种类型的网络定义成3这个字符，当其他设备收到字符3时就会明白在整个网段中只有发送3字符的路由器运行OSPF协议。
接下来我们来看第二种网络拓扑（两台运行OSPF协议的路由器通过点对点链路相连）该如何描述。第二种网络拓扑描述的时候分两步。首先，同第一种情况类似的是，路由器需要把本地运行OSPF接口的路由信息描述出来，即：
Link Id:192.168.2.0 /网段/
Data: 255.255.255.0 /掩码/
Type: StubNet (3) /类型/
Metric: 5 /花费值/
第二步，描述与其相连的RTB路由器。
Link Id:192.168.2.1 /RTB 的Router ID/
Data: 2.2.2.2 /RTB的接口地址/
Type: Router (1) /类型/
Metric: 20 /花费值/
在这里需要说明的是，在对RTB路由器进行描述的时候，Link ID字段必须用一个唯一的数字来表示，既不能是路由器的名称也不能是路由器的型号，因为在整个网络中Router ID是唯一的，所以这里用RTB的Router ID来描述RTA与RTB相连。同时，在Type字段中添加的数字为1，就表示是与一台路由器相连。那么是否通过这些描述就能非常清楚地没有歧义的描述出网络拓扑呢？答案是否定的。因为RTA与RTB相连有可能是多个接口互连，比如RTA与RTB互连是通过多条串行线路。所以，当RTA知道了自己与RTB相连后，还需要知道是与RTB的哪个接口相连，因此在Data字段中我们用RTB的接口地址来描述RTA是与RTB的那个接口相连。最后，在计算到RTB的花费。通过这些描述，RTA就能够清楚地描述出自己的连接状况。
OSPF对第三种网络拓扑的描述
第三种为一台路由器在同一个网段中通过点对多点链路与多个路由器相连，而这多个路由器之间不存在互连关系。首先，RTA仍然是先描述自己的接口。
Link ID： 1.1.1.1 /本地接口地址/
Data： 255.255.255.255 /掩码/
Type： StubNet（3） /类型/
Metric： 5 /花费/
在这里需要注意的是，在第三种网络拓扑中RTA描述自己的接口是采用的是主机地址而不是网段。
第二步描述与RTE相连
Link ID：2.2.2.2 /RTE的Router ID/
Data： 1.1.1.1 /与RTE相连的接口地址/
Type： Router（1） /类型/
Metric： 10 /花费/
第三步描述与RTF相连
Link ID：3.3.3.3 /RTF的Router ID/
Data： 1.1.1.1 /与RTF相连的接口地址/
Type： Router（1） /类型/
Metric： 20 /花费/
第四种为一台路由器在一个网段中通过点对多点链路与多个路由器相连，但这多个路由器之间存在互连关系（full mesh）。
Link ID：4.4.4.4 /网段中DR的接口地址/
Data： 4.4.4.1 /本地接口地址/
Type： TransNet（2） /类型/
Metric： 20 /花费/
在第四种情况中（实际上，第四种情况可以看作是第三种拓扑的特例），RTA并不描述自己接口的路由而是描述与DR相连的接口地址，以及DR的接口地址。在full mesh结构中，每个路由器都会生成这种LSA，其他的拓扑信息都在DR上描述。
DR生成的LSA
Net Mask：255.255.255.0
Attached： 4.4.4.1
Attached： 4.4.4.2
Attached： 4.4.4.3
通过DR（DR的产生我们会在下面讲到）上的LSA和其他路由器上的LSA就可以描述出这种拓扑。那么这样做有什么好处呢？如果我们按照第三种拓扑来描述第四种全连通的网络，我们会发现在网络中的每台路由器都会生成一个很庞大的LSA。每台路由器都要清楚而准确无误的描述出与自己相连的路由器，如果一个网络中有50台路由器那么每台路由器就需要描述1225条LSA。这会造成无谓的带宽浪费和设备性能的下降。而通过DR来生成LSA就大大缓解了这种情况的发生。
在现存的网络拓扑中，OSPF通过LSA都能准确无误的描述出来。在路由器向其他设备通告LSA的时候还需要加上一个头（head）。以下是Head的结构。
Type： Router /LSA的类型，可以看出此例是异地中情况的LSA/
Ls ID：1.1.1.1 /LSA的标示/
Adv rtr: 1.1.1.1 /生成LSA的路由器/
Ls Age: 40 /本条LSA的老化时间/
Length: 108 /LSA的长度/
Seq# 70000001 /LSA的序号/
Cksum: 0x3543 /校验和/
Link Count：7 /本条LSA中包含的连接个数/
至此，LSA加上Head后就完成了对自己周边拓扑的描述。
对网络拓扑完成以后，接下来的工作就是进行路由计算了。在学习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计算出一张带权的有向图，最终形成统一的路由表。
