选修3《网络通信基础》ppt课件3 高中信息技术.pptVIP

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