演示“距离矢量路由算法”和“链路状态路由算法”的工作原理。距离矢量路由算法（DistanceVectorRouting，DV）是ARPANET网络上最早使用的路由算法，也称为Bellman-Ford路由算法和Ford-Fulkerson算法，主要用在RIP（路由信息协议）协议中，Cisco的IGRP和EIGRP路由协议也使用了DV路由算法，“距离向量路由算法”的基本思想如下：每个路由器维护一个距离向量（通常以延迟为变量）表，然后通过相邻路由器之间的距离向量通知来更新距离向量表。每个距离向量表项包括两部分：到达目的节点的第一条输出线路，以及到达目的节点所需的时间或距离。目的节点。通信子网中的每个其他路由器在表中占有一个表项，并作为该表项的索引。每隔一段时间，路由器将发送它的d到每个目的节点到所有邻居节点的距离表，它还会收到来自每个邻居节点的距离表。以此类推，经过一段时间后，网络中各个路由器获得的距离向量信息就可以在各个路由器上统一起来，这样各个路由器只需要查看距离向量表就可以为不同的源组找到一条链路。路由。假设用时延作为距离的度量，举一个简单的例子，如图7-37所示。假设在某个时刻路由器Y接收到它的邻居路由器X的距离向量，其中m是Y到达路由器X的估计延迟。如果路由器Y知道它到邻居Z的延迟为n，那么它可以知道它需要m+nZ通过Y到达X的时间。如果路由器Z有其他邻居路由器，它对从每个其他邻居收到的距离矢量执行相同的计算，并且***选择时间成本最少的路由作为Z到X的最佳路由，然后更新它的路由表并通告给它的邻居路由器。距离矢量路由算法的简单示例下面用图7-38所示的例子来介绍距离矢量算法中的路由确定过程。图中标出了每条链路的时延。A、B、C、D、E代表5台路由器，假设路由表的传输方向为：A→B→C→D→E（这与路由器启动的先后顺序有关）。下面具体过程。(1)在初始状态下，每个路由器只收集直连链路的延迟信息，每个路由器节点获得自己的初始向量表，如图7-39所示。因为节点之间没有交换路由信息，所以它们在初始状态下的路由表就像它们的向量表一样。图7-38距离矢量算法路由确定示例初始状态下各节点的矢量表(2)现在路由器A将自己的路由表发送给路由器B。自己的初始路由表，并更新为新的向量表，如图7-40左图所示（最终的向量表在图中的深色部分）。从图中可以看出，从B节点到E节点有两条路径，一条是直达的，一条是经过A节点的，而且这两条线路的成本是不一样的。通过节点A到节点E的成本(7)低于直达线路的成本(8)，所以最终在形成的路由表中，将到节点E的路由改为通过节点A的路由，如如图7-40右图所示。NodeB的新向量表和路由表(3)B将最终的路由表发送给路由器C。同样，路由器C也需要将其原有的初始路由表与路由器B发来的路由表进行整合，形成一个新的向量表，如如图7-41左图所示（最终的向量表在图中部分用较深的颜色表示）。在新的向量表中，除了原来直接相连的节点B和D之间的向量之外，还新收集了到达节点A和E的向量信息。因为节点C与节点A和E没有直连，所以在初始路由表中没有到达这两个节点的路由信息??，所以现在只使用路由器B发来的路由表来通过节点B到的路径到达节点A和E。#p#这里要注意，因为在节点B(8)的路由表中已经确定了直接通过节点B到达节点E的开销大于通过节点B到达节点E的开销，并且A依次（7）大，所以在C节点路由表中，采用依次经过B、A节点到达E节点的路径。生成的路由表如图7-41右图所示。节点C的新向量表和路由表(4)RouterC将其最终的路由表发送给RouterD。同样，RouterD也需要将其原有的初始路由表与RouterC发送过来的路由表进行整合，形成一个新的向量表，如图7-42左图所示（最终的向量表在图中部分用较深的颜色表示）。在新的向量表中，除了原来直接相连的节点C和E之间的向量信息外，还新收集了到达节点A和B的向量信息。由于节点D与节点A、B没有直接联系，其初始路由表中没有到达这两个节点的向量信息，此时仍使用经C节点到A、B节点的路由。小路。这里还需要注意的是，从节点D到节点E也有两种路径：一种是直接到达，另一种是依次经过节点C、B、A到达。比较后发现，直连的开销（2）比经过节点C、B、A到达节点E的路径的开销（10）要小，所以在节点D中，到节点的路由E直接连接到这条线。生成的路由表如图7-42右图所示。(5)RouterD将自己最终的路由表发送给RouterE。同样，RouterE也需要将其原有的初始路由表与RouterD发来的路由表进行整合，形成新的向量表，如图左图所示7-43（最终的向量表在图中部分以较深的颜色显示）。在新的向量表中，除了原来直连的A、B、D节点之间的向量外，新收集到C节点的向量信息，因为E节点与C节点没有直连。此时仍然采用节点D到节点C的路径。节点D新的向量表和路由表有两点需要注意：一是节点E到节点A的路径，因为此时节点E和节点A是直连的，其开销(1)较小比原始路由表提供的路径开销（11）从D路由器通过D、C、B节点发送到节点A，所以在E节点最终的路由表中，到达节点A的路由是直连的。其次，虽然节点E也直接连接到节点B，但它的开销（8）甚至比路由器D发送的路由表中提供的开销（8）还要高，路由表中提供的从路由器D发送到节点B依次通过两个节点D和C到达节点B。开销(5)较大，所以在最终的E节点路由表中，到达B节点是采用依次经过D和C节点的路径。生成的路由表如图7-43右图所示。节点E新的向量表和路由表经过以上步骤，网络中的每台路由器完成整个路由表的确定。当然，当拓扑发生变化时，每台路由器的路由表都会发生变化并重新更新。
