距离矢量路由算法

本文概述

距离矢量路由算法
算法
分享信息
路由表

距离矢量算法是迭代的, 异步的和分布式的。分布式的：分布式的是, 每个节点都从一个或多个直接连接的邻居接收信息, 执行计算, 然后将结果分发回其邻居。迭代：迭代的过程一直持续到邻居之间没有更多的信息可交换为止。异步：不需要其所有节点都在锁定步骤中彼此操作。
距离矢量算法是一种动态算法。
它主要用于ARPANET和RIP。
每个路由器都维护一个称为Vector的距离表。

理解距离矢量路由算法工作的三个关键：

有关整个网络的知识：每个路由器都通过整个网络共享其知识。路由器将收集到的有关网络的知识发送给其邻居。
仅路由到邻居：路由器仅将其有关网络的知识发送到具有直接链接的那些路由器。路由器通过端口发送关于网络的所有信息。该信息由路由器接收, 并使用该信息更新其自己的路由表。
定期共享信息：路由器在30秒内将信息发送到相邻路由器。

令dx（y）为从节点x到节点y的最小成本路径的成本。最少的费用与Bellman-Ford方程相关,

dx(y) = minv{c(x, v) + dv(y)}

其中minv是对所有x个邻居采取的方程式。从x到v行进之后, 如果我们考虑从v到y的最小成本路径, 则路径成本将为c（x, v）+ dv（y）。从x到y的最小开销是对所有邻居取的c（x, v）+ dv（y）的最小值。

使用距离矢量路由算法, 节点x包含以下路由信息：

对于每个邻居v, 成本c（x, v）是从x到直接连接的邻居v的路径成本。
距离向量x, 即Dx = [Dx（y）：N中的y], 其中包含距离N的所有目的地y的成本。
每个邻居的距离向量, 即x的每个邻居v的Dv = [Dv（y）：N中的y]。

距离矢量路由是一种异步算法, 其中节点x将其距离矢量的副本发送到其所有邻居。当节点x从其相邻向量v中接收到新的距离向量时, 它将保存v的距离向量, 并使用Bellman-Ford公式更新其自身的距离向量。公式如下：

dx(y) = minv{ c(x, v) + dv(y)}     for each node y in N

节点x通过使用上面的等式更新了自己的距离矢量表, 并将其更新的表发送给其所有邻居, 以便它们可以更新自己的距离矢量。

算法

At each node x, Initialization 
for all destinations y in N:
Dx(y) = c(x, y)     // If y is not a neighbor then c(x, y) = ∞
for each neighbor w
Dw(y) = ?     for all destination y in N.
for each neighbor w
send distance vector Dx = [ Dx(y)  : y in N ] to w
loop
  wait(until I receive any distance vector from some neighbor w)
  for each y in N:
  Dx(y) = minv{c(x, v)+Dv(y)}
If Dx(y) is changed for any destination y
Send distance vector Dx = [ Dx(y) : y in N ] to all neighbors
forever

注意：在距离向量算法中, 当节点x在一个直接链接的节点中看到任何成本更改或从某个邻居接收到任何向量更新时, 它都会更新其表。

让我们通过一个例子来理解：

分享信息

在上图中, 每个云代表网络, 云内部的数字代表网络ID。
所有LAN通过路由器连接, 并在标有A, B, C, D, E, F的框中表示。
距离矢量路由算法通过假设每条链路的成本为一个单位来简化路由过程。因此, 可以通过到达目的地的链路数量来衡量传输效率。
在距离矢量路由中, 成本基于跳数。

在上图中, 我们观察到路由器将知识发送到直接邻居。邻居将此知识添加到自己的知识中, 并将更新后的表发送给自己的邻居。这样, 路由器将获得自己的信息以及有关邻居的新信息。

路由表

发生两个过程：

创建表
更新表

创建表

最初, 为每个路由器创建路由表, 其中包含至少三种类型的信息, 例如网络ID, 成本和下一跳。

NET ID：网络ID定义了数据包的最终目的地。
成本：成本是数据包到达那里必须经过的跳数。
下一跳：这是必须将数据包传递到的路由器。

在上图中, 显示了所有路由器的原始路由表。在路由表中, 第一列表示网络ID, 第二列表示链接的成本, 第三列为空。
这些路由表被发送到所有邻居。

例如：

A sends its routing table to B, F & E.
B sends its routing table to A & C.
C sends its routing table to B & D.
D sends its routing table to E & C.
E sends its routing table to A & D.
F sends its routing table to A.

更新表

当A从B接收到路由表时, 它将使用其信息来更新该表。
B的路由表显示了数据包如何移动到网络1和4。
B是A路由器的邻居, 从A到B的数据包可以在一跳内到达。因此, 将B的表中给出的所有成本加1, 而总和就是到达特定网络的成本。

调整后, A然后将此表与其自己的表合并以创建合并表。

组合表可能包含一些重复数据。在上图中, 路由器A的组合表包含重复数据, 因此它仅保留成本最低的那些数据。例如, A可以通过两种方式将数据发送到网络1。第一个不使用下一个路由器, 因此花费一跳。第二个需要两跳（A到B, 然后B到网络1）。第一种选择的成本最低, 因此保留它, 而第二种选择则放弃。

对于所有路由器, 将继续创建路由表。每个路由器都从邻居那里接收信息, 并更新路由表。

下面给出了所有路由器的最终路由表：

距离矢量路由算法

本文概述

理解距离矢量路由算法工作的三个关键：