“离矢量路由算法”的算法及实图讲解

　　距离矢量路由算法)是ARPANET网络上最早使用的路由算法，也称Bellman-Ford路由算法和Ford-Fulkerson算法，主要在RIP协议中使用。Cisco的IGRP和EIGRP路由协议也是采用DV这种路由算法的。距离矢量路由算法具体的工作原理是每个路由器维护一张路由表(即一个矢量)，它以网络中的每个路由器为索引，表中列出了当前已知的路由器到每个目标路由器的最佳距离，以及所使用的线路。通过在邻居之间相互交换信息，路由器不断地更新他们的内部路由表。但算法会有环回路由，慢收敛，无穷计算，扩展性差等问题。

     现代计算机网络通常使用动态路由算法，因为这类算法能够适应网络的拓扑和流量变化，其中最流行的两种动态路由算法是“距离矢量路由算法”和“链路状态路由算法”。

　　距离矢量路由算法（DistanceVectorRouting，DV）是ARPANET网络上最早使用的路由算法，也称Bellman-Ford路由算法和Ford-Fulkerson算法，主要在RIP（RouteInformationProtocol）协议中使用。Cisco的IGRP和EIGRP路由协议也是采用DV这种路由算法的。

　　“距离矢量路由算法”的基本思想如下：每个路由器维护一个距离矢量（通常是以延时是作变量的）表，然后通过相邻路由器之间的距离矢量通告进行距离矢量表的更新。每个距离矢量表项包括两部分：到达目的结点的最佳输出线路，和到达目的结点所需时间或距离，通信子网中的其它每个路由器在表中占据一个表项，并作为该表项的索引。每隔一段时间，路由器会向所有邻居结点发送它到每个目的结点的距离表，同时它也接收每个邻居结点发来的距离表。这样以此类推，经过一段时间后便可将网络中各路由器所获得的距离矢量信息在各路由器上统一起来，这样各路由器只需要查看这个距离矢量表就可以为不同来源分组找到一条最佳的路由。

　　现假定用延时作为距离的度量，举一个简单的例子，如图7-37所示。假设某个时候路由器Y收到其邻居路由器X的距离矢量，其中m是Y估计到达路由器X的延时。若Y路由器知道它到邻居Z的延时为n，那么它可以得知Z通过Y到达X需要花费时间m+n。如果Z路由器还有其他相邻路由器，则对于从其他每个邻居那儿收到的距离矢量，该路由器执行同样的计算，最后从中选择费时最小的路由作为Z去往X的最佳路由，然后更新其路由表，并通告给其邻居路由器。

　　图7-37距离矢量路由算法简单实例

　　现以一个如图7-38所示的示例介绍距离矢量算法中的路由的确定流程，各段链路的延时均已在图中标注。A、B、C、D、E代表五个路由器，假设路由表的传递方向为：A→B→C→D→E（这与路由器启动的先后次序有关）。下面具体的流程。

　　（1）初始状态下，各路由器都只收集直接相连的链路的延时信息，各路由器结点得出各自的初始矢量表如图7-39所示。因为各结点间还没有交换路由信息，所以它们的初始状态的路由表也如它们的矢量表。

　　图7-38距离矢量算法路由确定示例

　　图7-39初始状态下各结点的矢量表

　　（2）现在路由器A把它的路由表发给路由器B。此时它会综合从A路由器发来的路由表和它自己的初始路由表，更新为一个新的矢量表，如图7-40左图所示（最终的矢量表如图中深颜色部分）。从图中可以看出，从B结点到达E结点此时存在两条路径，一条是直达的，一条是通过A结点到达的。而且这两条线的开销不同，经过A结点到达E结点的开销（7）比直达线路的开销（8）更低，所以最终在形成的路由表中，把到达E结点的线路改为经由A结点这条线路，如图7-40右图所示。

　　图7-40B结点新的矢量表和路由表

　　（3）B再把最终形成的路由表发给路由器C。同样，路由器C也要把它原来的初始路由表与从B路由器发来的路由表进行综合，形成新的矢量表，如图7-41左图所示（最终的矢量表如图中深颜色部分）。在新的矢量表中，除了最初的直接连接的B和D结点间的矢量外，还新收集了到达A和E结点的矢量信息。因为C结点没有与A和E结点的直接连接，在初始路由表中并没有到达这两个结点的路由信息，所以现在只有采用从B路由器发来的路由表中，经过B结点到达A、E结点的路径。

　　这里要注意一点，因为在B结点路由表中就已识别了直接通过B结点到达E结点的开销（8）还比依次通过B、A结点到达E结点的开销（7）大，所以在C结点路由表中是采用依次通过B、A结点到达E结点这条路径。最终形成的路由表如图7-41右图所示。

　　图7-41C结点新的矢量表和路由表

　　（4）路由器C再把它的最终路由表发给路由器D。同样，路由器D也要把它原来的初始路由表与从C路由器发来的路由表进行综合，形成新的矢量表，如图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）路由器D再把它的最终路由表发给路由器E。同样，路由器E也要把它原来的初始路由表与从D路由器发来的路由表进行综合，形成新的矢量表，如图7-43左图所示（最终的矢量表如图中深颜色部分）。在新的矢量表中，除了最初的直接连接的A、B和D结点间的矢量外，还新收集了到达C结点的矢量信息，因为E结点没有与C结点的直接连接。此时仍采用经过D结点到达C结点的路径。

　　图7-42D结点新的矢量表和路由表

　　在这里有两个要注意的地方：一是从E结点到达A结点的路径问题，因为此时E结点与A结点是直接连接的，而且其开销（1）要比原来从D路由口器发来的路由表中提供的通过D、C、B结点到达A结点路径开销（11）要小，所以在最终的E结点路由表中，到达A结点是采用直接连接这条线路。二是E结点虽然也是与B结点直接连接，但它的开销（8）还要比原来从D路由器发来的路由表中提供的依次经过D、C这两个结点到达B结点的开销（5）大，所以在最终的E结点路由表中，到达B结点是采用依次经过D、C两个结点这条路径。最终形成的路由表如图7-43右图所示。

　　图7-43E结点新的矢量表和路由表

　　距离矢量路由算法是这样工作的：每个路由器维护一张路由表（即一个矢量），它以网络中的每个路由器为索引，表中列出了当前已知的路由器到每个目标路由器的最佳距离，以及所使用的线路。通过在邻居之间相互交换信息，路由器不断地更新他们的内部路由表。

　　举例来说，假定使用延迟作为“距离”的度量标准，并且该路由器发送一个列表，其中包含了他到每一个目标路由器的延时估计值；同时，他也从每个邻居路由器接收到一个类似的列表。假设一个路由器接收到来自邻居x的一个列表，其中x（i）表示x估计的到达路由器i所需要的时间。如果该路由器知道他到x的延时为m毫秒，那么他也知道在x（i）+m毫秒之间内经过x可以到达路由器i。一个路由器针对每个邻居都执行这样的计算，就可以发现最佳的估计值，然后在新的路由器表中使用这个最佳的估计值以及对应的输出路线。

　　通过以上的步骤，我们会发现网络中各路由器就完整了整个路由表的确定，当然在拓扑结构发生变化时，各路由器的路由表又会发生变化，重新进行更新。当收到路由中毒消息的路由器，不遵守水平分割原则将中毒消息转发给所有的相邻路由器，也包括发送中毒信息的源路由器，也就是通告相邻路由器这条路由信息己失效了,主要目的是达到快速收敛的目的。 

      关于离矢量路由算法的更多详细资料尽在课课家教育，我们24小时客服在线，等待您的咨询！