距离向量路由算法

• 距离向量算法是迭代的、异步的、分布式的。
  • 分布式： 它之所以是分布式的，是因为每个节点从一个或多个直接相连的邻居接收信息，进行计算，然后将结果分发给邻居。
  • 迭代： 它之所以是迭代的，是因为它的过程一直持续到邻居之间不再有信息可以交换为止。
  • 异步： 它不需要所有节点都以相同的步调运行。
• 距离向量算法是一种动态算法。
• 它主要用于 ARPANET 和 RIP。
• 每个路由器维护一个称为向量的距离表。

理解距离向量路由算法的三个关键点

• 了解整个网络：每个路由器都会与其整个网络共享其知识。路由器将其收集到的网络信息发送给其邻居。
• 仅向邻居路由：路由器仅将其网络知识发送给那些有直接链接的路由器。路由器通过端口发送它所知道的网络信息。信息由路由器接收并用于更新其自身的路由表。
• 定期信息共享：路由器在 30 秒内将信息发送给邻近的路由器。

距离向量路由算法

令 d_x(y) 为节点 x 到节点 y 的最小费用路径的成本。最小费用由 Bellman-Ford 方程给出：

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

其中 min_v 是对所有 x 的邻居取的方程。在从 x 到达 v 后，如果我们考虑从 v 到 y 的最小费用路径，则路径成本将是 c(x,v)+d_v(y)。从 x 到 y 的最小费用是所有邻居的 c(x,v)+d_v(y) 的最小值。

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

• 对于每个邻居 v，成本 c(x,v) 是从 x 到直接相连的邻居 v 的路径成本。
• 节点 x 的距离向量，即 D_x = [ D_x(y) : y in N ]，包含其到 N 中所有目标 y 的成本。
• 其每个邻居的距离向量，即对于 x 的每个邻居 v，D_v = [ D_v(y) : y in N ]。

距离向量路由是一种异步算法，其中节点 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、成本和下一跳。

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

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

例如

更新表

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

• 调整后，A 将此表与自己的表合并以创建合并表。

• 合并表可能包含重复数据。在上图中，路由器 A 的合并表中包含重复数据，因此它只保留成本最低的数据。例如，A 可以通过两种方式将数据发送到网络 1。第一种方式不使用任何下一路由器，因此成本为一跳。第二种方式需要两跳（A 到 B，然后 B 到网络 1）。第一种选择成本最低，因此被保留，第二种被丢弃。

• 为所有路由器继续创建路由表的过程。每个路由器都接收来自邻居的信息，并更新路由表。

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