OSPF 基本原理

　　OSPF 是一种基于链路状态的路由协议（LS）（根据链路状态做参考），它从设计上就保证了无路由环路。OSPF 支持区域的划分，区域内部的路由器使用 SPF 最短路径算法保证了区域内部的无环路。OSPF 还利用区域间的连接规则保证了区域之间无路由环路。

　　OSPF 支持触发更新，能够快速检测并通告自治系统内的拓扑变化。

　　OSPF 可以解决网络扩容带来的问题。当网络上路由器越来越多，路由信息流量急剧增长的时候，OSPF 可以将每个自治系统划分为多个区域，并限制每个区域的范围。OSPF 这种分区域的特点，使得 OSPF 特别适用于大中型网络。OSPF 可以提供认证功能。OSPF 路由器之间的报文可以配置成必须经过认证才能进行交换。

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

(1) 建立邻接关系，过程如下：

1. 本端设备通过接口向外发送 Hello 报文与对端设备建立邻居关系。
2. 两端设备进行主/从关系协商和 DD 报文交换。
3. 两端设备通过更新 LSA 完成链路数据库 LSDB 的同步。

　　此时，邻接关系建立成功。

(2) 路由计算

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

建立邻接关系

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

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

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

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

　　广播链路邻接关系建立过程如图1所示，在广播网络中，DR、BDR 和网段内的每一台路由器都形成邻接关系，但 DR other 之间只形成邻居关系。

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

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

(1) 建立邻居关系

1. RouterA 的一个连接到广播类型网络的接口上激活了 OSPF 协议，并发送了一个 Hello 报文（使用组播地址 224.0.0.5）。此时，RouterA 认为自己是 DR 路由器（DR=1.1.1.1），但不确定邻居是哪台路由器（Neighbors Seen=0）。
2. RouterB 收到 RouterA 发送的 Hello 报文后，发送一个 Hello 报文回应给 RouterA，并且在报文中的 Neighbors Seen 字段中填入 RouterA 的 Router ID（Neighbors Seen=1.1.1.1），表示已收到 RouterA 的 Hello 报文，并且宣告 DR 路由器是 RouterB（DR=2.2.2.2），然后 RouterB 的邻居状态机置为 Init。
3. RouterA 收到 RouterB 回应的 Hello 报文后，将邻居状态机置为 2-way 状态，下一步双方开始发送各自的链路状态数据库。

(2) 主/从关系协商、DD 报文交换

1. RouterA首先发送一个 DD 报文，宣称自己是 Master（MS=1），并规定序列号 Seq=X。I=1 表示这是第一个 DD 报文，报文中并不包含 LSA 的摘要，只是为了协商主从关系。M=1 说明这不是最后一个报文。为了提高发送的效率，RouterA 和RouterB 首先了解对端数据库中哪些 LSA 是需要更新的，如果某一条 LSA 在 LSDB 中已经存在，就不再需要请求更新了。为了达到这个目的，RouterA 和 RouterB 先发送 DD 报文，DD 报文中包含了对 LSDB 中 LSA 的摘要描述（每一条摘要可以唯一标识一条 LSA）。为了保证在传输的过程中报文传输的可靠性，在 DD 报文的发送过程中需要确定双方的主从关系，作为 Master 的一方定义一个序列号 Seq，每发送一个新的 DD 报文将 Seq 加一，作为 Slave 的一方，每次发送 DD 报文时使用接收到的上一个 Master 的 DD 报文中的 Seq。
2. RouterB 在收到 RouterA 的 DD 报文后，将 RouterA 的邻居状态机改为 Exstart，并且回应了一个 DD 报文（该报文中同样不包含 LSA 的摘要信息）。由于 RouterB 的 Router ID 较大，所以在报文中 RouterB 认为自己是 Master，并且重新规定了序列号 Seq=Y。
3. RouterA 收到报文后，同意了 RouterB 为 Master，并将 RouterB 的邻居状态机改为 Exchange。RouterA 使用 RouterB 的序列号 Seq=Y 来发送新的 DD 报文，该报文开始正式地传送 LSA 的摘要。在报文中 RouterA 将 MS=0，说明自己是 Slave。
4. RouterB 收到报文后，将 RouterA 的邻居状态机改为 Exchange，并发送新的 DD 报文来描述自己的 LSA 摘要，此时 RouterB 将报文的序列号改为 Seq=Y+1。

　　上述过程持续进行，RouterA 通过重复 RouterB 的序列号来确认已收到 RouterB 的报文。RouterB 通过将序列号 Seq 加 1 来确认已收到 RouterA 的报文。当 RouterB 发送最后一个 DD 报文时，在报文中写上 M=0。

(3) LSDB 同步（LSA 请求、LSA 传输、LSA 应答）

1. RouterA 收到最后一个 DD 报文后，发现 RouterB 的数据库中有许多 LSA 是自己没有的，将邻居状态机改为 Loading 状态。此时 RouterB 也收到了 RouterA 的最后一个 DD 报文，但 RouterA 的 LSA，RouterB 都已经有了，不需要再请求，所以直接将 RouterA 的邻居状态机改为 Full 状态。
2. RouterA 发送 LSR 报文向 RouterB 请求更新 LSA。RouterB 用 LSU 报文来回应 RouterA 的请求。RouterA 收到后，发送 LSAck 报文确认。

　　上述过程持续到 RouterA 中的 LSA 与 RouterB 的 LSA 完全同步为止，此时 RouterA 将 RouterB 的邻居状态机改为 Full 状态。当路由器交换完 DD 报文并更新所有的 LSA 后，此时邻接关系建立完成。

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

　　NBMA 网络和广播网络的邻接关系建立过程只在交换 DD 报文前不一致，如图2中的蓝色标记。在 NBMA 网络中，所有路由器只与 DR 和 BDR 之间形成邻接关系。

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

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

(1) 建立邻居关系

1. RouterB 向 RouterA 的一个状态为 Down 的接口发送 Hello 报文后，RouterB 的邻居状态机置为 Attempt。此时，RouterB 认为自己是 DR 路由器（DR=2.2.2.2），但不确定邻居是哪台路由器（Neighbors Seen=0）。
2. RouterA 收到 Hello 报文后将邻居状态机置为 Init，然后再回复一个Hello 报文。此时，RouterA 同意 RouterB 是 DR 路由器（DR=2.2.2.2），并且在 Neighbors Seen 字段中填入邻居路由器的 Router ID（Neighbors Seen=2.2.2.2）。

(2) 主/从关系协商、DD 报文交换过程同广播网络的邻接关系建立过程。

(3) LSDB 同步（LSA 请求、LSA 传输、LSA 应答）过程同广播网络的邻接关系建立过程。

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

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

路由计算

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

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

　　每台路由器根据有向图，使用 SPF 算法计算出一棵以自己为根的最短路径树，这棵树给出了到自治系统中各节点的路由。如图4所示。
图4：最小生成树

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

1.计算区域内路由

　　Router LSA 和 Network LSA 可以精确的描述出整个区域内部的网络拓扑，根据 SPF 算法，可以计算出到各个路由器的最短路径。根据 Router LSA 描述的与路由器的网段情况，得到了到达各个网段的具体路径。

2.计算区域外路由

　　从一个区域内部看，相邻区域的路由对应的网段好像是直接连接在 ABR 上，而到 ABR 的最短路径已经在上一过程中计算完毕，所以直接检查 Network Summary LSA，就可以很容易得到这些网段的最短路径。另外，ASBR 也可以看成是连接在 ABR 上，所以 ASBR 的最短路径也可以在这个阶段计算出来。

3.计算自治系统外路由

　　由于自治系统外部的路由可以看成是直接连接在 ASBR 上，而到 ASBR 的最短路径在上一过程中已经计算完毕，所以逐条检查 AS External LSA 就可以得到到达各个外部网络的最短路径。

本文转自华为官网中NetEngine AR 产品文档中OSPF原理描述（NetEngine AR路由器）