学习回顾OSPF路由计算原理

OSPF网络是在一个AS中以区域为单位的分层结构，而且在区域中又分为两种不同的角色:骨干区域和普通区域。这就决定了OSPF的路由也必定是分层的，分为区域内路由和区域间路由，而不像RIP路由那样是扁平的。

整个OSPF路由计算过程是OSPF设备间建立了完全的邻接关系后进行的，依据的就是路由器为所连接的各个区域所保存的LSDB(每个连接区域都有一个专门的LSDB)，但在具体的OSPF路由计算中，又分为区域内路由和区域间路由两个方面，下面一次介绍。

1) OSPF区域内路由计算原理

当网络重新稳定下来后，OSPF录取会根据其各自的LSDB采用SPF(最短路径优先)算法(具体算法为Dijkstra，IS-IS路由也采用这种算法)独立地计算到达每一个目的网络的路径，并将路径存入路由表中。路由表中包含该路由器到每一个可到达目的地址、开销和下一跳。OSPF区域内路由是有OSPF内部路由器使用最小开销的路径到达目的网络，且区域内的路由不被聚合。

OSPF的Dijkstra算法是利用开销来计算路由路径性能的，开销最小者即为最短路径。在配置OSPF路由器时可根据实际情况，如链路带宽、时延等设置链路的开销大小。开销越小，则该链路被选为路由的可能性越大。这里的开销时根据链路类型来计算的，不同的链路类型对应的开销值不一样。

【Dijkstra算法原理】

在Dijkstra算法中，为了在一对给定的路由器节点之间选择一条最短(其实是指链路开销最小)路由路径，只需在通信子网中找到在起始和结束之间的中间节点串联起来后链路开销最短的路径即可。它把最短路由的节点表示为工作节点，并且是永久性的节点，其到达源节点的距离值是不能改变的，其他的标识为临时性的节点，其到达源节点的距离可能会随工作节点的不同而改变。所有工作节点串联起来就是对应源节点和目的节点之间的最短路由路径。

如图所示的子网图是一个典型的最短路径路由算法子网图，图中的每一个节点(以字母标注)代表一台OSPF路由器，每条线段代表一条通信链路，线段上的数字代表对应你链路的开销值。先假设要使用Dijkstra算法计算节点A到节点D之间的最短路径。在网络中路由器启动时，首先需要初始化，测量每条链路的开销，参见图中各条线段上的数字。下面是从A节点达到D节点的路由确定流程。

① 首先将源节点A标记为永久性工作节点(用箭头来特别标识)，然后依次检查每一个与A节点直接连接的相邻节点，并且把它们与A节点之间的距离重新以(n，N)的方式进行标识，其中的n为与A节点相距的链路开销，N为最近的工作节点。

因为本示例中与节点A直接相邻的节点只有B和G，所以仅需要标识这两个节点与A节点之间的距离。此时的工作节点为A，如图所示，B节点的标识为(2,A)，G节点的标识为(6,A)，因为B节点到A节点的链路开销为2，G节点到A节点的链路开销为6。其他与A节点不相邻的节点的距离标识为无穷远。

② 比较B和G这两个节点与A节点之间距离，可以看出B节点的距离更短，于是把B节点改为工作节点(箭头移到B)，同时变为永久节点，其他节点(包括G节点)标注为临时节点。然后以B节点为工作节点，标记直接相邻的节点到源节点A的距离，当然对于前面已经计算过的节点将忽略，如源节点A和G节点。

在本示例与B节点直接相邻的节点中，除了A节点以外还有C、E这两个节点。C节点到达A节点的距离就是C节点到B节点的链路开销7，再加上B节点到A节点的链路开销2，所以C节点到A节点的距离为2+7=9，标识为(9,B)。同理，E节点到A节点的距离为2+2=4，标识为(4,B)，如图所示。其他既不与A节点，又不与B节点相邻的仍为无穷远。

③ 同样经过比较得出，E节点到A节点之间的距离(为4)，比C节点到A节点的距离(为9)近，所以此时把E改为工作节点(箭头移到E)，同时标注E节点为永久节点，其他节点(包括C节点)标注为临时节点。

按照同样方法标记与E节点直接相邻的节点(包括节点B、节点G和节点F)到E节点的距离，但对于前面已经计算过的永久节点B节点不再重新计算，而对虽然原来已计算过，但为临时节点的G以及F节点均需要重新计算。最终G节点的标识改为(5,E)(在此步之前为(6,A)),F节点标识为(6,E),表示G节点和F节点到达A节点的距离分别是5和6，如图所示。

④ 再用同样的方法比较G节点和F节点到达A节点之间的距离，可以得出G节点更近，所以此时把G节点改为工作节点(箭头移至G)，同时标注G节点为永久性节点，其他节点(包括F节点)标注为临时节点，如图所示

再看一下与G节点直接相邻的节点，包括A、E、H这3个节点，但是A、E这两个节点在前面已经标注过永久性节点了，标识是不能更改的，所以在这里只需对H节点计算到达E节点的距离(2+2=4),所以经过后面的计算发现，在前面把G节点标识为永久节点是多雾的，这时要把F节点标识为工作节点(箭头移到F)，撤销G节点为永久工作节点的资格，入如图所示。

此时，因为H节点是直接与目的节点D相连，所以无需在进行选举了，直接标识D节点的距离为(10,H)。即从A节点到目的节点D的最短距离就为10，即2+2+2+2+2，如图所示的连线:A->B->E->F->H->D，这样，就找出了源节点到目的节点的最短路径。

从以上可以看出Dijkstra算法虽然能得出最短路径，但由于遍历计算的节点很多，所以效率低。另外，有些节点还不能一次标识正确，因为还要考虑后续节点到达源节点的距离，如以上示例中G节点和F节点的工作点标识，最初的标识就是错误的，因为它没有考虑后续及节点到源节点的距离。

2) OSPF区域间路由的计算原理

OSPF路由器的ABR连接多个OSPF区域，所以他保存了多个区域的LSDB。但是在ABR与所连区域的内部路由器，以及其他区域路由器的通信都不像区域内部那样是以具体的明细路由进行的，而是采用聚合路由进行的，因为都是通过Summary类型的LSA计算。

在ABR上会以Type-3 LSA向所连区域内，以及其他区域通告所连区域的网络聚合路由，其他区域的路由也是以Type-3 LSA向所连区域内通告的。所以，区域内路由器与ABR，以及ABR与其他区域的通信都是以网络聚合路由进行的。但是要注意的是，两个非骨干区域之间是不能直接进行LSA通告的，而是必须借助骨干区域进行转发，同样，两个非骨干区域自检是不能直接进行路由通信的，必须借助骨干区域的路由转发。所以在区域间的路由路径中一定会包括到达骨干区域对应路由器所连网段的路由。

总体来说，OSPF曲艺那的路由将按照以下过程进行。

① 在源区域内部的路由器，按照到达最近ABR的开销最小的网络聚合路由进行通信。

② 骨干区域按照到达连接到包含目的主机IP地址所在区域最近ABR的开销最小的网络聚合路由进行通信。

③ 包含目的主机IP地址所在区域的ABR，按照到达目的主机的开销最小网络聚合路由进行通信。

如图所示，假设Area1中的IP地址为192.168.1.10/26的HostA要向位于Area2中的IP地址为182.16.2.10/24的HostB发送数据报文。

① 首先，从Area1中的内部路由器以一个对应的聚合地址(这个可以由管理员在R1上配置，假设为192.168.1.0/24，可进行自动路由聚合)到达R1(ABR/骨干路由器)。

② 然后，数据报文再通过骨干区域Area0中的路由转发到R2.

③ 最后，数据报文通过对应的聚合路由(这个也可以有管理员在R2上配置，假设为172.16.0.0/16，也可以是自动路由聚合)转发，通过Area2中的内部路由器到达目的主机。

3) OSPF路由更新

当链路状态发生变化时，OSPF通过泛洪过程在区域内广播给其他路由器。OSPF路由器接收到包含有新信息的链路状态更新报文，将更新自己的LSDB，然后用SPF算法重新在区域内各路由器上计算OSPF路由器。在重新计算过程中，各路由器继续使用原来的路由表，直到SPF完成新的路由表计算。要注意的是，即使链路状态没有发生改变，OSPF路由信息也会自动更新，缺省时间为30min。