|
|
知识路径： > 计算机网络原理 > 网络互连 > 路由算法 > 距离矢量路由算法 >
|
|
相关知识点：4个
|
|
|
|
|
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算法刚开始工作的时候，每个路由器的距离矢量表中都是只包含到每个邻居路由器的距离，而到其他非邻居路由器的距离都是无穷大。但是，随着时间的推移，邻居路由器之间不断地交换距离矢量表，于是每个路由器都能够计算出到达其他路由器的最短距离了。
|
|
|
