|
|
知识路径： > 计算机网络原理 > 网络互连 > 路由算法 >
|
被考次数：4次
被考频率：中频率
总体答错率：43%
知识难度系数： 
|
由 软考在线 用户真实做题大数据统计生成
|
|
相关知识点：5个
|
|
|
|
|
距离矢量（Distance-Vector，V-D）路由算法是基于Bellman-Ford的数学研究结果，因此有时也将该算法称为Bellman-Ford算法。V-D算法要求路由器之间周期地交换路由更新报文，路由更新报文中包含到所有目的网络的距离矢量。
|
|
|
|
|
|
V-D路由算法的工作原理就是邻居路由器之间定期交换距离矢量表。每当接收到邻居路由器发来的距离矢量表时，路由器重新计算到每个目的节点的距离，并且更新路由表。
|
|
|
|
距离矢量表只包含到所有目的节点的距离，距离的度量单位可以是延迟、物理距离或其他参数。在V-D路由算法中，必须假定每个路由器都知道到邻居路由器的“距离”。如果度量标准是跳步数，则1跳表示的距离为1；如果度量标准是延迟，则路由器可以通过发送一个“回应请求（Echo Request）”报文，等待邻居路由器的“回应响应（Echo Reply）”回来后，测出它到邻居路由器的延迟。
|
|
|
|
V-D路由算法的工作原理是，每隔一段时间（通常以ms计算）邻居路由器之间交换距离矢量表，每个路由器根据各个邻居路由器报告的路由信息更新自己的路由表。
|
|
|
|
假设某路由器Y从邻居路由器X收到一张距离矢量表，路由器X告诉Y它到路由器I的延迟是XI ms，而路由器Y知道它到X的延迟为t ms，则路由器Y就知道它通过路由器X到达路由器I的延迟是（XI+t）ms。同样的道理，路由器Y收到另一个邻居路由器Z发来的距离矢量表，路由器Z告诉Y它到路由器I的延迟是ZI ms，而路由器Y知道它到Z的延迟为r ms，则路由器Y就知道通过路由器Z到达路由器I的延迟是（ZI+r）ms。通过这样的计算，路由器Y就可以找到一条到达路由器I的延迟最短的路径，然后路由器Y就将该条路径记录在路由表中，同时更新距离矢量表。
|
|
|
|
为了更好地说明V-D路由算法的工作原理，来看一个例子。下图（a）给出了某网络拓扑结构。在这个例子中，用延迟来作为“距离”的度量标准，并且假定网络中的每个路由器都知道到其邻居路由器的延迟。
|
|
|
|
|
|
|
|
上述例子的更新过程如上图（b）所示。上图（b）的前4列表示路由器J从邻居路由器A、I、H和K收到的距离矢量表。路由器A告诉J，它到B的延迟为12ms，到C的延迟为25ms，到D的延迟为40ms……同样的道理，路由器I、H和K都分别告诉路由器J它们到网络中每一个节点的延迟。
|
|
|
|
假定路由器J已经知道它到邻居路由器A、I、H和K的延迟分别为8ms、10ms、12ms和6ms。下面考察一下J怎样更新到路由器G的延迟。路由器J知道经A到G的延迟是38ms（因为A告诉J它到G的延迟是30nis，而J到A的延迟是8ms，因此J经过A到达G的延迟为30ms+8ms=38ms）。
|
|
|
|
同样的道理，J可以计算出经过I、H和K到G的延迟分别为27+10=37ms、10+12=22ms和41+6=47ms。比较这些延迟，J就知道经H到G的延迟是最小的22ms，因而在J的新路由表中填上到G的延迟为22ms，输出线路为H。同时J更新它将要发给邻居路由器的距离矢量表，把到G的距离（实际上是延迟）设为22ms，但是在距离矢量表中并没有指出是通过H到G的（这就会带来下面将要重点讨论的慢收敛问题）。
|
|
|
|
当然V-D算法刚开始工作的时候，每个路由器的距离矢量表中都是只包含到每个邻居路由器的距离，而到其他非邻居路由器的距离都是无穷大。但是，随着时间的推移，邻居路由器之间不断地交换距离矢量表，于是每个路由器都能够计算出到达其他路由器的最短距离了。
|
|
|
|
|
|
所谓收敛是指网络中所有路由器对网络的可达性达成一致。影响路由算法收敛性的因素有很多，包括网络的规模、拓扑结构、路由方法及路由策略等。
|
|
|
|
在V-D路由算法中，存在慢收敛问题。为了说明这个问题，来看如下图所示的例子（图中A、B、C、D和E为路由器，距离度量单位是跳数，而且图中的距离值都是针对以A为目的节点的）。
|
|
|
|
|
|
|
|
为了说明V-D路由算法的慢收敛问题，先来看上图（a）的情况。假定刚开始时，A到B的线路不通，因此B、C、D和E到A的距离为∞。
|
|
|
|
假设某时刻，A、B线路恢复了，则A会向B发送它的距离矢量表。经过第1次距离矢量表交换后，B收到A发来的距离矢量表，而且A告诉B它到A的距离是0，因此B就知道A可达，且B到A的距离为1。而此时，C、D和E到A的距离还是为∞，也就是说，B、C和E都还不知道A、B线路已经恢复了，如上图（a）的第二行所示。
|
|
|
|
第2次交换后，B会告诉C，它到A的距离为1，因此C知道通过B到A的距离为2；同时D会告诉C，它到A的距离为∞，而C到D的距离为1，因此C知道通过D到A的距离为∞（即不可达）；结果C在它的距离矢量表中填上到A的距离为2，输出线路是B。而此时D和E到A的距离还是∞，如上图（a）的第三行所示。再经过第3次和第4次交换后，D和E都知道到A的线路畅通了，都在自己的距离矢量表中填上最短距离和输出线路，上图（a）的第四、五行说明了这个结果。
|
|
|
|
很明显，A、B线路恢复畅通这样“好消息”的传播是每交换一次距离矢量表往前推进一步。对于最长路径为N的网络，通过N次交换后，网络上的所有路由器都能知道线路恢复或路由器恢复的“好消息”，这就是所谓的好消息传播快。
|
|
|
|
下面，再来看一下上图（b）中的情形。假定刚开始时，所有的线路和路由器都是正常的，此时B、C、D和E到A的距离分别为1、2、3和4。
|
|
|
|
突然间，A、B之间的线路断了。第1次距离矢量表交换后，B收不到A发来的距离矢量表，按理说B就可以断定A是不可达的，应该在B的距离矢量表中将到A的距离设为∞（如果B此时能照此原理进行工作，也就不存在慢收敛的问题了）。遗憾的是，C会告诉B说：“别担心，我到A且距离为2（B并不能知道C到A的路径还要经过B本身，因为C通过距离矢量表告诉B到A的距离，但是C并没有告诉B它到A的2跳距离本身就是通过B。B可能会认为C可能还有其他路径到达A且距离为2）”，结果B就认为通过C可以到达A且距离为3。此时，B到A的路径是这样构成的：B->C，C->B，B->A，B和C之间存在路径环。但经过第1次交换后，D和E并不更新其对应于A的表项。
|
|
|
|
第2次交换后，C注意到它的两个邻居B和D都声称有一条通往A的邻居，且距离为3，因此它可以任意选择一个邻居作为下一站，并将到A的距离设为4，如上图（b）第三行所示，此时B将它的无效路由又传递给C了。
|
|
|
|
同样的道理，经过第3次、第4次交换后，B、C、D和E到A的距离会慢慢增加，当超过网络最大直径（最长距离）后，最终设为∞，即不可达。也就是说，B、C、D和E到底什么时候才能知道A是不可达的，取决于网络中对无穷大的取值究竟是多少，这就是慢收敛问题（坏消息传播慢）。可以采用的办法之一是将∞设成网络的最长路径长度加1，一旦路由的距离度量达到这个值，就宣布该路由无效。对于上图的例子，由于网络的最长路径长度为4，因此，可以将∞设置为5，当B、C、D和E到A的距离计数值到5时，就可以认定A是不可达的，即宣布A不可达，因此有时也将上述问题称为计数到无穷（count to infinity）问题。
|
|
|
|
|
|
对于慢收敛这个问题有几种不完善的解决方法。其中的一种方法是使用一个较小的数作为无穷大的近似值。例如，可以认为穿过某个网络的最大跳数不会超过16，因此可以选择16来表示无穷大。这样至少可以限制计数到无穷大所花费的时间。当然，如果网络中节点间距多于16跳时，就又会出现新的问题。
|
|
|
|
（1）水平分割。改进稳定路由选择所需时间的一种方法是水平分割（split horizon）。水平分割方法的思想是任何一个节点并不把从它邻居路由器学到的路由再回送给那些邻居路由器，即当路由器从某个网络接口发送路由更新报文时，其中不能包含从该接口学到的路由信息。例如，在上图中，如果节点C在其距离矢量表中有（A，2）这一项，而且C知道该路由是从路由器B学到的。所以当C发送距离矢量表给B时，在距离矢量表中不应该包括（A，2）这一项。
|
|
|
|
为了更更具体地解释水平分割的思想，举一个现实生活中的例子。假定哈尔滨人（D地）和北京人（C地）都要去广州（A地），但他们都必须经过长沙（B地），而哈尔滨人还要先经过北京。假定哈尔滨人想要知道去广州的道路信息（道路是否畅通，距离是多少），必须先通过北京人，同样北京人要知道去广州的道路信息，必须先通过长沙人（当然，哈尔滨人知道到北京的道路信息，而北京人也知道到长沙的道路信息）。那么在这种情况下，如果出现北京人告诉长沙人去广州的路由信息是没有任何意义的。换句话说，北京人根本不需要告诉长沙人关于去广州的任何信息，因为北京人得到的关于去广州的道路信息都是长沙人告诉他们的，但北京人必须告诉哈尔滨人到广州的道路信息。对应于上图的例子，C可以告诉D它到A的实际距离，但C或不告诉B它到A的情况（水平分割），或者告诉B它到A的距离为∞（带毒性反转的水平分割）；原因是在这种情况下，C报告B它到A的距离没有任何意义，因为C到A的路由要通过B。类似的道理，D告诉E到A的实际距离，但不向C报告它到A的距离。
|
|
|
|
（2）毒性反转。比水平分割更好的一种方法是毒性反转（Poison Reverse）。使用毒性反转方法时，C仍然把来自B的到达A的路由信息回送给B，但在该距离矢量表中这一项的距离是无穷大以确保B不会使用C的路由，即C把（A，∞）这一距离矢量发送给B。而且为了加强毒性反转的效果，最好同时使用触发更新（Trigged Update）技术，即一旦某节点检测到网络故障，就立即发送距离矢量表，而不必等到下一个周期。而其他路由器一旦发现路由表有更新，就立即发送距离矢量表。
|
|
|
|
采用了毒性反转方法后，再来看看A、B线路断开后的路由交换情况。在第1次交换距离矢量表后，B发现直达A的线路断了，于是B就知道A不可达（B是通过在规定的时间之内没有收到A发来的距离矢量表来判断或者是B到A的线路出故障了，或路由器A出故障了），而C此时报告给B它到A的距离为∞，由于B的两个邻居都到不了A，B就将它到A的距离设置为∞。第2次交换后，C也发现从它的两个邻居都到不了A，C也将A标为不可达。经过第3次、第4次交换后，D和E依次发现A是不可达的。使用水平分割后，坏消息以每交换一次距离矢量表向前推进一步的速度传播。
|
|
|
|
|
|
距离矢量路由算法是非常简单的算法，基于这种算法的路由协议（如RIP）容易配置、维护和使用。因此，它对于非常小的、几乎没有冗余路径且无严格性能要求的网络非常有用。
|
|
|
|
距离矢量路由算法的最大问题是收敛慢，并且在收敛过程中，可能产生路由环问题。有许多措施来防止这种情况发生，但是不能从根本上加以解决。
|
|
|
