|
|
知识路径： > 计算机网络原理 > 网络互连 > 路由算法 > 距离矢量路由算法 >
|
|
相关知识点：4个
|
|
|
|
|
所谓收敛是指网络中所有路由器对网络的可达性达成一致。影响路由算法收敛性的因素有很多，包括网络的规模、拓扑结构、路由方法及路由策略等。
|
|
|
|
在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）问题。
|
|
|
