5.5 路由信息的广播 路由信息的交换是路由算法的基础。特别 是在分布式路由算法中，无论是距离矢量 算法还是链路状态算法，都需要各个节点 相互交换路由信息，然后各节点再独立的 计算各自的路由表。 在正常情况下，将路由信息从收集该信息 的节点发送到需要该信息的节点是一个比 较容易的过程。但是，当网络出现故障（ 例如：链路故障等）时，实施起来就非常 困难了。 主要困难 网络的拓扑信息必须通过链路来传输，而 链路本身可能有故障。在有中心的网络中 ，这个问题尤为严重。因为，当网络的部 分节点通过一条可能会故障的链路与网络 中心相连时，如果该链路发生了故障，则 网络中的部分节点将会与网络中心失去联 系，从而导致这些节点无法获知网络的拓 扑信息。主要困难 网络中会存在多次拓 扑变化，这就意味着 们必须对旧的路由信 息和新的路由信息加 以区分。 如果网络采用泛洪的方 式来广播拓扑变化信息 ，当网络仅有一次拓扑 变化时，泛洪方式可以 正常工作，但当网络有 多次拓扑变化时，泛洪 的方法将不能正常工作 。主要困难 当正在执行最短路由算法时，新的拓扑信 息到达，这时，要么算法能够处理这一变 化，要么中止刚才进行的计算，开始重新 计算。 当一条链路修复之后，它可能会引起分离 的网络被重新连接，这时每一个分离的部 分都可能会包括有关另一部分的过时拓扑 信息。路由算法必须能够保证这两部分最 终是一致的，并能够适应正确的网络拓扑 。 前面的讨论告诉我们，网络中的每一个节 点要在所有的时间内都得到正确的网络拓 扑是不可能的。所以我们期望的最佳值是 ：算法能够在有限的时间内处理任意有限 次的拓扑变化。 为了便于讨论，我们作如下假设，这些假设可以 保证拓扑变化能够被正确的检测到。 网络的链路能维持传输的顺序性和正确性。此外，各 节点能够维持其存储器中数据的完整性。 链路的故障是由链路的两个端点检测的，但不一定要 同时检测到。这就意味着链路的一个端点认为链路断 开后，另一个端点最终也会认为链路断开。必须注意 的是，另一个端点认为链路断开必须在第一个点认为 链路恢复之前。 有完善的数据链路层协议，能够识别链路何时再次工 作。如果链路的一个端点宣布链路恢复(UP)，则在有 限的时间内，另一个端点要么宣布链路恢复，要么首 先再次宣布链路故障(DOWN)。 节点可以有故障。这种情况下，与它关联的每一条链 路的另一个端点在有限的时间内必须宣布链路故障（ DOWN）。ARPANET的泛洪算法 泛洪算法又称为扩散式算法。其基本思想 是：每个节点通过向其所有的邻节点发送 消息的方式，将拓扑更新消息广播给所有 的节点。每个相邻节点收到该信息后，再 将其转发给它所有的邻节点，依次类推。 ARPANET泛洪算法有两个主要的特点： 能有效的防止拓扑更新信息在网络中无限 次的循环； 能有效的防止序号出错带来的影响。ARPANET的泛洪算法 如图网络，采用泛洪 的方式来广播拓扑更 新消息。 这样链路（1，2） DOWN的消息到达节 点3后，将无限次的循 环。因此，这种简单 的泛洪算法只能在没 有环的网络中正常工 作。 解决上述问题的方法是：在拓扑更新消息中，携带足够多 的附加信息，使得每个节点仅发送该信息有限次，最好是 一次。 在ARPANET中，每一消息都标定一个序号，节点j收到i 的一个消息后，首先要比较该消息的序号是否大于j从i接 收到的最后一个序号。如果大于，则转发该消息，否则丢 弃该消息。每条消息中序号域应足够大，使得在正常情况 下，序号不会从高增加到最大值然后又重新置零。 序号的使用可以保证每个节点仅发送一次同样的拓扑更新 信息。这同时也解决了如何区分新旧消息的问题。但是， 一旦在传输的过程中序号出错，将会导致很多困难。序号出错 序号出错来自两个方面： 一是由于节点故障或CRC漏检将序号改变了。这样可能会出现两种意外情况：第一种情况是某节点内部意外地将序号置0，则该节点的更新消息将被网络忽略。第二种情况是节点j意外地将节点i的序号从一个较小的值变成了较大的值，并广播到全网。这个错误的序号将被存储在各节点中，这将会导致其他节点不可能会听到i的信息。 二是网络部分节点被复位或网络被分离后又重新连通，这会导致网络中仅靠序号无法识别正确的拓扑信息。 ARPANET采用两种机制解决这一问题。 每个更新消息包括一个年龄域（Age Field），它表明 该消息已在网络中传播了多长时间。当一条消息到达 某个节点后，该节点记录它的到达时间，并根据传输 时间和传播时延，增加它的年龄域。一个节点可在任 何时间计算其内存中所有消息的年龄。当该消息的年 龄超过门限后，该消息将被丢弃，不再转发。 年龄域使用规则是：不论序号如何，过时消息将被未过时的消 息取代。而未过时的消息只有在有一个更大序号的新消息时， 才被替代。这个规则可以保证被破坏或不正确的具有较高序号 的消息，不会被相信得太久。 每个节点除了在检测到链路状态变化时发送拓扑更新 消息外，每个节点要周期性地发送更新消息（至少每 60秒钟发送一次）。周期性广播保证在网络两个分离 的部分再连通以后，使最新的拓扑更新消息能在某个 固定的时间内得到。周期性广播的缺点是网络开销较 大。