OSPF路由计算

小乔

OSPF协议路由的计算过程可简单描述如下：

• 建立邻接关系。两端设备通过以下步骤建立邻接关系：
  
  
  • 本端设备通过接口向外发送Hello报文与对端设备建立邻居关系。
  • 两端设备进行主/从关系协商和DD报文交换。
  • 两端设备通过更新LSA完成链路数据库LSDB的同步。
    
• 路由计算。OSPF采用SPF（Shortest Path First）算法计算路由，可以达到路由快速收敛的目的。
  
  

OSPF邻居状态机

在OSPF网络中，为了交换路由信息，邻居设备之间首先要建立邻接关系，邻居（Neighbors）关系和邻接（Adjacencies）关系是两个不同的概念：

• 邻居关系：OSPF设备启动后，会通过OSPF接口向外发送Hello报文，收到Hello报文的OSPF设备会检查报文中所定义的参数，如果双方一致就会形成邻居关系，两端设备互为邻居。
• 邻接关系：形成邻居关系后，如果两端设备成功交换DD报文和LSA，才建立邻接关系。
  

邻居和邻接状态是通过OSPF状态机表现的，OSPF共有8种邻居状态机，分别是Down、Attempt、Init、2-way、Exstart、Exchange、Loading、Full，如图5-13所示。Down、2-way、Full是稳定状态，Attempt、Init、Exstart、Exchange、Loading是不稳定状态。不稳定状态是在转换过程中瞬间存在的状态，一般不会超过几分钟。

图5-13 OSPF邻居状态机

                               
登录/注册后可看大图

表5-22 OSPF邻居状态机及含义[td]

状态机	含义
Down	邻居会话的初始阶段。表明没有在邻居失效时间间隔内收到来自邻居设备的Hello报文。
Attempt	处于本状态时，定期向手工配置的邻居发送Hello报文。 说明： Attempt状态只适用于NBMA类型的接口。
Init	本状态表示已经收到了邻居的Hello报文，但是对端并没有收到本端发送的Hello报文。
2-way	互为邻居。本状态表示双方互相收到了对端发送的Hello报文，建立了邻居关系。 如果不形成邻接关系则邻居状态机就停留在此状态，否则进入Exstart状态。
Exstart	协商主从关系。建立主从关系主要是为了保证在后续的DD报文交换中能够有序的发送。
Exchange	交换DD报文。本端设备将本地的LSDB用DD报文来描述，并发给邻居设备。
Loading	正在同步LSDB。两端设备发送LSR报文向邻居请求对方的LSA，同步LSDB。
Full	建立邻接。两端设备的LSDB已同步，本端设备和邻居设备建立了邻接关系。

                               
登录/注册后可看大图

本端设备和状态可能与对端设备的状态不相同。例如本端设备的邻居状态是Full，对端设备的邻居状态可能是Loading。

DR和BDR

在广播网和NBMA网络中，任意两台设备之间都要传递路由信息。如图5-14所示，网络中有n台设备，则需要建立n*(n-1)/2个邻接关系。这使得任何一台设备的路由变化都会导致多次传递，浪费了带宽资源。为解决这一问题，OSPF定义了指定路由器DR和备份指定路由器BDR。通过选举产生DR（Designated Router）后，所有设备都只将信息发送给DR，由DR将网络链路状态LSA广播出去。除DR和BDR之外的设备（称为DR Other）之间将不再建立邻接关系，也不再交换任何路由信息，这样就减少了广播网和NBMA网络上各设备之间邻接关系的数量。

图5-14 选举DR前后对比图

                               
登录/注册后可看大图

如果DR由于某种故障而失效，则网络中的设备必须重新选举DR，并与新的DR同步。这需要较长的时间，在这段时间内，路由的计算有可能是不正确的。为了能够缩短这个过程，OSPF提出了BDR（Backup Designated Router）的概念。BDR是对DR的一个备份，在选举DR的同时也选举出BDR，BDR也和本网段内的所有设备建立邻接关系并交换路由信息。当DR失效后，BDR会立即成为DR。由于不需要重新选举，并且邻接关系已建立，所以这个过程非常短暂，这时还需要再重新选举出一个新的BDR，虽然一样需要较长的时间，但并不会影响路由的计算。

DR和BDR不是人为指定的，而是由本网段中所有的设备共同选举出来的。设备接口的DR优先级决定了该接口在选举DR、BDR时所具有的资格。本网段内DR优先级大于0的设备都可作为“候选人”。选举中使用的“选票”就是Hello报文。每台设备将自己选出的DR写入Hello报文中，发给网段上的其他设备。当处于同一网段的两台设备同时宣布自己是DR时，DR优先级高者胜出。如果优先级相等，则Router ID大者胜出。如果一台设备的优先级为0，则它不会被选举为DR或BDR。

建立邻接关系

在上述邻居状态机的变化中，有两处决定是否建立邻接关系：

• 当与邻居的双向通讯初次建立时。
• 当网段中的DR和BDR发生变化时。
  
  

OSPF在不同网络类型中，OSPF邻接关系建立的过程不同，分为广播网络，NBMA网络，点到点/点到多点网络。

在广播网络中建立OSPF邻接关系

广播链路邻接关系建立过程如图5-15所示。

在广播网络中，DR、BDR和网段内的每一台设备都形成邻接关系，但DR other之间只形成邻居关系。

图5-15 在广播网络中建立OSPF邻接关系

                               
登录/注册后可看大图

如图5-15所示，在广播网络中建立OSPF邻接关系的过程如下：

• 建立邻居关系
  
  
  • DeviceA的一个连接到广播类型网络的接口上激活了OSPF协议，并发送了一个Hello报文（使用组播地址224.0.0.5）。此时，DeviceA不确定DR是哪台路由器（DR=0.0.0.0），也不确定邻居是哪台设备（Neighbors Seen=0）。
  • DeviceB收到DeviceA发送的Hello报文后，发送一个Hello报文回应给DeviceA，并且在报文中的Neighbors Seen字段中填入DeviceA的Router ID（Neighbors Seen=1.1.1.1），表示已收到DeviceA的Hello报文，并且宣告DR路由器是DeviceB（DR=2.2.2.2），然后DeviceB的邻居状态机置为Init。
  • DeviceA收到DeviceB回应的Hello报文后，将邻居状态机置为2-way状态，下一步双方开始发送各自的链路状态数据库。
    
    
  
                                 
  登录/注册后可看大图
  在广播网络中，两个接口状态是DR Other的设备之间将停留在此步骤。
  
  
• 主/从关系协商、DD报文交换
  
  
  • DeviceA首先发送一个DD报文，宣称自己是Master（MS=1），并规定序列号Seq=x。I=1表示这是第一个DD报文，报文中并不包含LSA的摘要，只是为了协商主从关系。M=1说明这不是最后一个报文。
    为了提高发送的效率，DeviceA和DeviceB首先了解对端数据库中哪些LSA是需要更新的，如果某一条LSA在LSDB中已经存在，就不再需要请求更新了。为了达到这个目的，DeviceA和DeviceB先发送DD报文，DD报文中包含了对LSDB中LSA的摘要描述（每一条摘要可以唯一标识一条LSA）。为了保证在传输的过程中报文传输的可靠性，在DD报文的发送过程中需要确定双方的主从关系，作为Master的一方定义一个序列号Seq，每发送一个新的DD报文将Seq加一，作为Slave的一方，每次发送DD报文时使用接收到的上一个Master的DD报文中的Seq。
  • DeviceB在收到DeviceA的DD报文后，将DeviceB的邻居状态机改为Exstart，并且回应了一个DD报文（该报文中同样不包含LSA的摘要信息）。由于DeviceB的Router ID较大，所以在报文中DeviceB认为自己是Master，并且重新规定了序列号Seq=y。
  • DeviceA收到报文后，同意了DeviceB为Master，并将DeviceA的邻居状态机改为Exchange。DeviceA使用DeviceB的序列号Seq=y来发送新的DD报文，该报文开始正式地传送LSA的摘要。在报文中DeviceA将MS=0，说明自己是Slave。
  • DeviceB收到报文后，将DeviceB的邻居状态机改为Exchange，并发送新的DD报文来描述自己的LSA摘要，此时DeviceB将报文的序列号改为Seq=y+1。
    
    
  上述过程持续进行，DeviceA通过重复DeviceB的序列号来确认已收到DeviceB的报文。DeviceB通过将序列号Seq加1来确认已收到DeviceA的报文。当DeviceB发送最后一个DD报文时，在报文中写上M=0。
• LSDB同步（LSA请求、LSA传输、LSA应答）
  
  
  • DeviceA收到最后一个DD报文后，发现DeviceB的数据库中有许多LSA是自己没有的，将邻居状态机改为Loading状态。此时DeviceB也收到了DeviceA的最后一个DD报文，但DeviceA的LSA，DeviceB都已经有了，不需要再请求，所以直接将DeviceA的邻居状态机改为Full状态。
  • DeviceA发送LSR报文向DeviceB请求更新LSA。DeviceB用LSU报文来回应DeviceA的请求。DeviceA收到后，发送LSAck报文确认。
    
    
  上述过程持续到DeviceA中的LSA与DeviceB的LSA完全同步为止，此时DeviceA将DeviceB的邻居状态机改为Full状态。当设备交换完DD报文并更新所有的LSA后，此时邻接关系建立完成。
  
  

在NBMA网络中建立OSPF邻接关系

NBMA网络和广播网络的邻接关系建立过程只在交换DD报文前不一致，如图5-16中的深蓝色标记。

在NBMA网络中，所有设备只与DR和BDR之间形成邻接关系。

图5-16 在NBMA网络中建立OSPF邻接关系

                               
登录/注册后可看大图

如图5-16所示，在NBMA网络中建立OSPF邻接关系的过程如下：

• 建立邻居关系
  
  
  • DeviceB向DeviceA的一个状态为Down的接口发送Hello报文后，DeviceB的邻居状态机置为Attempt。此时，DeviceB认为自己是DR路由器（DR=2.2.2.2），但不确定邻居是哪台设备（Neighbors Seen=0）。
  • DeviceA收到Hello报文后将邻居状态机置为Init，然后再回复一个Hello报文。此时，DeviceA同意DeviceB是DR路由器（DR=2.2.2.2），并且在Neighbors Seen字段中填入邻居设备的Router ID（Neighbors Seen=2.2.2.2）。
    
    
  
                                 
  登录/注册后可看大图
  在NBMA网络中，两个接口状态是DR Other的设备之间将停留在此步骤。
  
  
• 主/从关系协商、DD报文交换过程同广播网络的邻接关系建立过程。
• LSDB同步（LSA请求、LSA传输、LSA应答）过程同广播网络的邻接关系建立过程。
  
  

在点到点/点到多点网络中建立OSPF邻接关系

在点到点/点到多点网络中，邻接关系的建立过程和广播网络一样，唯一不同的是不需要选举DR和BDR，DD报文是组播发送的。

路由计算

OSPF采用SPF（Shortest Path First）算法计算路由，可以达到路由快速收敛的目的。

OSPF协议使用链路状态通告LSA描述网路拓扑，即有向图。Router LSA描述设备之间的链接和链路的属性。设备将LSDB转换成一张带权的有向图，这张图便是对整个网络拓扑结构的真实反映。各个设备得到的有向图是完全相同的。如图5-17所示。

图5-17 由LSDB生成带权有向图

                               
登录/注册后可看大图

每台设备根据有向图，使用SPF算法计算出一棵以自己为根的最短路径树，这棵树给出了到自治系统中各节点的路由。如图5-18所示。

图5-18 最短路径树

                               
登录/注册后可看大图

当OSPF的链路状态数据库LSDB发生改变时，需要重新计算最短路径，如果每次改变都立即计算最短路径，将占用大量资源，并会影响设备的效率，通过调节SPF的计算间隔时间，可以抑制由于网络频繁变化带来的占用过多资源。缺省情况下，SPF时间间隔为5秒钟。

具体的计算过程如下：

• 计算区域内路由。
  Router LSA和Network LSA可以精确的描述出整个区域内部的网络拓扑，根据SPF算法，可以计算出到各个设备的最短路径。根据Router LSA描述的与设备的网段情况，得到了到达各个网段的具体路径。
  
                                 
  登录/注册后可看大图
  在计算过程中，如果有多条等价路由，SPF算法会将所有等价路径都保留在LSDB中。
  
  
• 计算区域外路由。
  从一个区域内部看，相邻区域的路由对应的网段好像是直接连接在ABR上，而到ABR的最短路径已经在上一过程中计算完毕，所以直接检查Network Summary LSA，就可以很容易得到这些网段的最短路径。另外，ASBR也可以看成是连接在ABR上，所以ASBR的最短路径也可以在这个阶段计算出来。
  
                                 
  登录/注册后可看大图
  
  
  • 如果进行SPF计算的设备是ABR，那么只需要检查骨干区域的Network Summary LSA。
  • 如果存在多个到ASBR的路径，需要注意各设备类型上intra和inter类型ASBR的优选规则是否一致，如果存在不一致可能发生环路。
    RFC1583兼容模式和不兼容模式会影响选路规则，另外在相同模式下，不同厂商设备对该场景的选路规则的也可能存细微差异，在已知选路规则存在差异的情况下，本产品提供了命令行对ASBR在RFC1583兼容模式和不兼容模式的选路规则进行调整，可以在一定程度上避免环路。
    
    
  
  
• 计算自治系统外路由。
  由于自治系统外部的路由可以看成是直接连接在ASBR上，而到ASBR的最短路径在上一过程中已经计算完毕，所以逐条检查AS External LSA就可以得到到达各个外部网络的最短路径。
  
  

PRC

PRC（Partial Route Calculation）是指当网络上路由发生变化的时候，只对发生变化的路由进行重新计算。

当网络拓扑中有一个节点发生变化时，SPF算法需要重新计算网络中的所有节点，计算时间长，占用过多的CPU资源，影响整个网络的收敛速度。I-SPF（Incremental SPF）改进了这个算法，除了第一次计算时需要计算全部节点外，每次只计算受到影响的节点，而最后生成的最短路径树SPT与原来的算法所计算的结果相同，大大降低了CPU的占用率，提高了网络收敛速度。

PRC的原理与I-SPF相同，都是只对发生变化的路由进行重新计算。不同的是，PRC不需要计算节点路径，而是根据I-SPF算出来的SPT来更新路由。在路由计算中，叶子代表路由，节点则代表路由器。SPT变化和叶子变化都会引起路由信息的变化，但两者不存在依赖关系，PRC根据SPT或叶子的不同情况进行相应的处理：

• SPT变化，PRC处理变化节点上的所有叶子的路由信息。
• SPT没有变化，PRC不会处理节点的路由信息。
• 叶子变化，PRC处理变化的叶子的路由信息。
• 叶子没有变化，PRC不会处理叶子的路由信息。
  
  

比如一个节点新增使能一个OSPF接口，则整个网络拓扑的SPT是不变的，这时PRC只更新这个节点的接口路由，从而节省CPU占用率。

PRC和I-SPF配合使用可以将网络的收敛性能进一步提高，它是原始SPF算法的改进，所以已经代替了原有的算法。

mawr1985

薯条

薯条