4.5 扩散更新算法

DUAL是EIGRP协议使用的计算到目的地最佳路由的一种算法，该算法根据复合度量值来选择路由，并确保所选路由是无环的。

4.5.1 EIGRP术语

为了说明DUAL的运行过程，先解释几个相关术语。

1.后继路由器

后继路由器（Successor）是一台用于转发数据的相邻路由器，经由它到达目的地的路径开销最小，并保证不是路由环路中的一部分。如果存在多条开销最小的等值路径，就有多台后继路由器。如图4-2所示，路由器R1到达网络10.10.0.0存在两条路径，经由R2的度量是10，经由R3的度量是20，所以R2是路由器R1的后继路由器。

2.可行距离和通告距离

路由器使用的具有最低开销的路径度量值称为可行距离（Feasible Distance，FD），如图4-3所示。通告距离（Advised Distance，AD）指通往目的地的路径上下一跳路由器到目的地的路径开销，即邻居的可行距离（如图4-3所示）。通告距离也写做RD（Reported Distance）。

3.可行后继路由器

备份路径中的下一跳路由器（邻居）被称为可行后继路由器（Feasible Successor，FS）。成为可行后继路由器的条件是：经由该邻居路由器到达目标网络的通告距离小于当前正在使用的路径的可行距离，并且不构成环路。如图4-4所示，由于R1经由R3到达目标网络的通告距离（AD=2）小于当前经由R2到达目标网络的可行距离（FD=3），所以R3成为R1的可行后继路由器。可行后继路由器可能存在多台，也可能不存在，存在可行后继路由器就意味着存在到达目标网络的备份路由。当路由器失去正在使用的最佳路由后，它将查看拓扑结构数据库，试图寻找FS，如果存在，最佳的可行后继路由器被提升为后继路由器，并把经由新的后继路由器的路由安放到路由表中。当没有可行后继路由器时，将进行新的路由计算。

4.5.2 DUAL的运行过程

下面以图4-5的拓扑为例说明DUAL的运行过程。当网络发生变化时考察路由器R3、R4和R5的拓扑数据库的变化（以到达目标网络为例）。图4-5所示的状态是收敛状态。路由器R3到达目标网络的路径是经由R2，因为该条路径的开销最小（FD=3），并且R4是它的可行后继路由器。路由器R4到达目标网络的路径是经由R2，没有可行后继路由器。路由器R5到达目标网络的路径是经由R4，没有可行后继路由器。

当路由器R2和R4之间的链路失效后，DUAL执行下面的操作。

第一步，路由器R4把通过路由器R2到达目标网络的路径标记为不可用，如图4-6所示。

第二步，如图4-7所示。

①在路由器R4上由于没有到达目标网络的可行后继路由器，它将执行下面的操作：

●将到达目标网络的度量值设为不可到达（-1为不可到达）。

●将到达目标网络的路由置为活跃（Active）状态。当一条路由正被计算时，该路由被视为是活跃的；计算完成时则是消极（Passive）的。

●向路由器R3和R5发送查询路径的消息。

●将通过路由器R3和R5到达目标网络的路由信息条目标记为查询挂起（用q表示），表示正在向对方查询，还没有得到回答。

②在路由器R5上，收到R4的查询后将通过路由器R4到达目标网络的路由标记为不可用。

第三步，如图4-8所示。

①路由器R4接收到来自路由器R3的答复，R3声明其到达目标网络的路由没有变化，R4执行下面的操作：

●取消对路由器R3的查询挂起标志。

●继续保持到达目标网络的路由为活跃状态，等待路由器R5的答复。

②在路由器R5上，因为没有到达目标网络的可行后继路由器，所以：

●向路由器R3进行查询。

●将通过路由器R3到达目标网络的路由信息条目标记为查询挂起。

第四步，如图4-9所示。

①在路由器R4上，仍然保持到达目标网络的路由为活跃状态，等待路由器R5的回答。

②在路由器R5上，收到路由器R3的应答，R3声明自己到达目标网络的路由没有变化，路由器R5执行如下操作：

●取消对路由器R3的查询挂起标志。

●计算新的FD并把新的后继路由器放置在路由表中。

第五步，如图4-10所示。

在路由器R4上，收到路由器R5的回答执行如下操作：

●取消对路由器R5的查询挂起标志。

●计算新的FD并把新的后继路由器放置在路由表中。此时，有两条等值的路由出现，两个邻居都为Successor。

第六步，如图4-11所示。

此时的网络是收敛的。路由器R4上有两条等值的路由到达目标网络，它使用这两条路径均衡负载。

提示

从以上过程可以看出，路由器通过跟踪邻居通告的所有路由的方式计算路由，因此，DUAL也称为有限状态机。