邻居发现与交流#

EIGRP 路由器通过使用 hello 数据包建立和维护与邻居路由器的邻接关系，并将信息存储在 IP EIGRP Neighbor Table 中。如图是一个邻居发现与交流的过程：

收集拓扑信息#

当 EIGRP 路由器发现一个新邻居时，它会向新邻居发送更新请求，并从新邻居接收更新路由内容，以填充拓扑表 (IP EIGRP Topology Table)。

当直接连接的路由或接口发生更改，或邻居路由器向路由报告更改时，拓扑表将更新。拓扑表中还记录了每个条目的状态：

• ** 被动状态 (Passive state):** 路由器已选择路由的状态。
• ** 激活状态 (Active state):** 路由器没有路由，正在尝试寻找路由的状态。

选择最佳路线#

EIGRP 使用一些算法计算后继路由和备份路由的 度量值 (Metrics)，并将它们注入拓扑表 (IP EIGRP Topology Table)。

路径上的最小开销，称为 可行距离（FD, feasible distance）。如果路由有 FD 的度量值被称为 后继路由/主路由。后继可以有多个路由器，它们的 FD 一样。

邻居路由器通告的路由开销，称为 报告距离（RD, reported distance）。如果邻居路由 RD 小于原始的后继路由 FD，则该邻居路由可以成为 后备路由/可行后继路由。

在默认条件下，Metrics 的表达式为：

bandwidth 是路由上沿着任何接口的 最低 配置带宽，单位为 kbps。delay 是从源路由到目的路由的延迟之和，单位为 µs。256 是缩放系数。

下面通过一个例子来理解如何计算度量值。如图是一个拓扑图，其中 R2 右边连接的子网是目的地址。计算从 R1 到目的地址的 FD 和 RD。

我们根据之前学到的距离矢量路由协议，从目的地址开始泛洪。第一次泛洪，泛洪到邻居 R2 上。此时带宽最小为 1 Gbps，延迟为 1 μs。

第二次泛洪，泛洪到邻居 R1 和 R3。分别找到两条链路上的最小的带宽和总延迟，如下图。

我们可以计算从 R1 直接到目的地址的度量值。

$\,\text{via R2: } FD = \left(\frac{10^7}{10 \times 10^3} + \frac{100 + 1}{10}\right) \times 256\,$

还需要注意 R1 和 R3 之间的链路，可能存在重新泛洪。此时除直连外的最小带宽和延迟变化：

我们可以计算 R1 经过 R3 时的度量值。

$\,\text{via R3: } FD = \left(\frac{10^7}{1 \times 10^3} + \frac{1000 + 10 + 1}{10}\right) \times 256\,$

很明显，经过 R2 的度量值更小，它更优。所以 R2 就是 R1 的后继路由。

接下来我们还需要计算 R1 的 邻居 R3 的度量值 来检测经过 R3 的路由是否能作为备选路由。（注意：是计算 R3 的度量值，不包括 R1 到 R3 的链路上的带宽与延迟）

$\,\text{via R3: } RD = \left(\frac{10^7}{100 \times 10^3} + \frac{10 + 1}{10}\right) \times 256 \;<\; \text{via R2 FD}\,$

我们发现它的 RD 会比 FD 要小，故 R3 可以选为备用路由。

维护路由信息#

EIGRP 中，如果后继路由发生故障，路由器将查找已识别的备用/可行后继路由。此路由将升级为后继状态。

如果从当前信息中没有识别出可行的后继路由器（没有备用路由），路由器会在路由上设置 Active 状态，并向所有邻居发送查询数据包，以便重新计算当前拓扑。

路由器可以根据从应答查询请求的应答分组接收的新数据来识别任何新的后继路由或可行后继路由。然后，路由器将在路由上设置 Passive 状态。

扩散更新算法 (DUAL)#

扩散更新算法（Diffusing Update Algorithm, DUAL）是 Cisco 的 EIGRP 路由协议使用的算法，用于确保在可能导致路由环路的情况下，对给定路由进行全局重新计算。

DUAL 维护一个与路由表分开的拓扑表，其中包括到目标网络的最佳路径和 DUAL 确定为无环的备用路径。

如果一条路径变得不可用，DUAL 将在其拓扑表中搜索有效的备用路径。

• 如果存在可行后继路由器 (feasible successor)，则立即将该路由输入路由表中代替出现问题的后继路由器。
• 如果不存在可行后继路由器，则 DUAL 执行网络发现过程，向周围的邻居发送 query 请求，让其告诉有效的路径。

通过下面一个例子可以理解 DUAL 的过程，如下拓扑图中：

在稳定状态下，DUAL 维护的各拓扑表如下：

因为 Router A 和 Router B 直接相连，它们之间的仅有一条记录。因为不会产生环路，故 B 不会记录 C 和 D。

Router C:

Router D:

Router E:

突然，Router D 与 Router B 之间的连接断开，此时 Router B 和 Router D 最先知晓。Router D 的拓扑表变为：

Router D:

此时刚好将 Router D 的后继路由器删除了，于是 Router D 检索拓扑表中是否存在可行后继，发现刚好也没有。于是 Router D 进入 Active 状态，会向它的邻居发送 query，请求可行的路径。

Router C 收到 D 的 query 后，会在拓扑表中删除 Router D 的记录，于是有：

Router C:

但 Router C 仍然有 Successor Router，处于 Passive 状态，于是回复 Router D 可以通过 Router C 到达目的地。

同时，Router E 收到 D 的 query 后，同样删除 Router D 的记录，得：

Router E:

此时将 Router E 的 Successor 删除了，故它也需要向邻居发送 query。因为 Router E 也进入 Active 状态，向其他邻居 Router C 发送 query。

Router C 收到 E 的 query 后，会在拓扑表中删除 Router E 的记录，于是有：

Router C:

但 Router C 仍然有 Successor Router，处于 Passive 状态，于是回复 Router E 可以通过 Router C 到达目的地。

Router E 更新自己的状态为 Passive，并设置 Router C 为 Successor：

Router E:

处于 Passive 状态下的 Router E 会回复 Router D 的 query，于是 Router D 根据收到的回复，更新自己的状态为 Passive，并设置 Router C 为 Successor：

Router D:

最后，整个网络收敛。

注意在整个过程中：

• 需要等待所有的 query 回复后才能对比找到后继。
• 只有 Passive 状态的路由器才能给出 Reply。

建立邻居关系#

当 OSPF 路由器连接到一个网络时，它会向本地直连网络上的路由器发送 hello 数据包，尝试与邻居建立邻接关系。

每个路由器都会保存一份与之建立了双向通信的相邻邻居的列表，称为 邻接数据库（adjacency database）。该数据库对每个路由器都是唯一的。

OSPF 的路由器会使用 路由 ID (Router ID)，用于在一个 OSPF 域中唯一地标识一台路由器。

选举 DR 和 BDR#

指定路由器 (Designated Router, DR) 和 后备指定路由器 (Backup Designated Router, BDR) 是在多接入网络中交换 OSPF 路由信息的 中心点。每个非 DR 或非 BDR 路由器将 只与 DR 和 BDR 交换路由信息，而不是与网段上的每个路由器交换更新。这样所有的拓扑信息均由 DR 来发布，大大减少 OSPF 流量。

对于单接入网络不存在 DR 和 BDR。

具有 最高 OSPF 优先级 的路由器将被选为 DR。优先级第二高的路由器将成为 BDR。当 OSPF 优先级相同时，OSPF 将根据路由器 ID 决定 DR 的选举。选择 最高的路由器 ID。

选举过程结束后，即使网络中添加了 OSPF 优先级值更高的路由器，DR 和 BDR 仍会保留 其角色。

例如：

它们的优先级都一样，选取 ID 最大的 R3 为 DR，第二大的 R2 为 BDR。

构建拓扑结构#

每个 OSPF 路由器都会向同一区域内的所有邻居发送 LSA。然后，OSPF 会收集包含邻居路由器每个直接连接链路的状态和 Cost 的 LSA 列表，并构建一个完整的拓扑图，称为 拓扑数据库 (topological database) 或 链路状态数据库 (link-state database)。该数据库在同一区域的所有路由器中都是相同的。

找到最佳路径#

每个 OSPF 路由器都应用 SPF 算法计算通往每个目标网络的最佳路径。SPF 算法将 Cost 相加，Cost 值通常基于带宽。Cost 最低的路径会被添加到 OSPF 路由表，也称为 转发数据库 (forwarding database) 中。该数据库对每个路由器都是唯一的。

路径开销 (Path Cost) 的计算公式为：$\,\text{OSPF cost} = \dfrac{100{,}000{,}000}{\text{Bandwidth (bps)}} = \dfrac{10^8}{\text{Bandwidth (bps)}}\,$

其值在 1 到 65535 之间。

下面是一个 OSPF 图：

图中存在 6 个 Router，构成了 4 个子网，R1、R2、R3 是一个局域网，网段为 192.168.1.0/24，R1、R4 是点对点的单接入网络，网段为 192.168.2.0/30，R4、R5、R6 之间通过广域网连接，网段为 192.168.3.0/24，R6 还接着一个子网。

RID 设置为这个 Router 的一个 IP 如图所示。在发送 hello 数据包建立邻居关系后，在每个子网中选举 DR 和 BDR。

根据 RID 的大小可以找到 DR 和 BDR。此时经过 STP 的树可以是：

假设一个 LSA 从 R1 到 R6，LSA 会经过如下的路径：R1 -> R4 -> R6，它的开销 Cost 为：$\,\text{Metric} = \dfrac{10^8}{64\times 10^3\ \text{bps}} + \dfrac{10^8}{128\times 10^3\ \text{bps}} + \dfrac{10^8}{10\times 10^6\ \text{bps}}\,$

维护 OSPF 网络#

当网络无任何变化的时候，OSPF 会定期使用 hello 数据包来确定邻居的可达性。默认情况下，在点对点和广播式多接入网络上，每 10 秒发送一次 hello，在 NBMA（非广播式多接入，使用虚电路和交换结构连接）网络上，每 30 秒发送一次 hello。

当网络发生变化时，OSPF 路由器通过向同一个 Area 内的所有其他路由器泛洪发送 LSU (link-state update) 来通知邻居，邻居将通过 LSAck 确认收到 LSU。

在点对点链路中，LSU 使用 ** 224.0.0.5 ** 互相发送给对方。

在多接入链路上，LSU 使用组播地址 ** 224.0.0.6 ** 发送给 DR。然后，DR 使用组播地址 ** 224.0.0.5 ** 将 LSU 泛洪到该网络中的所有 OSPF 路由器。

如果路由器是 区域边界路由器 (ABR)，则它会继续向其他网络泛洪 LSU。OSPF 路由器收到包含新信息的 LSU 后，会运行 SPF 算法重新计算路由表。

在之前例子中，若 R6 接入的 subnet 连接断开，下面是整个网络泛洪 LSU 的过程：