距离向量路由、Bellman-Ford与收敛问题

距离向量算法（Distance-Vector Routing Protocol）

距离向量算法是分布式的，因为每个结点都要从一个或多个直连邻居接收信息，执行计算，然后将结果分发给邻居。

距离向量算法根据Bellman-Ford方程$d_x(y) = \min_v\{c(x, v) + d_v(y)\}$得来，其中$d_x(y)$表示从x到y的最小开销，$c(x, v)$表示x到邻居v的开销，$d_v(y)$表示从邻居v到终点y的开销。

这个方程的含义很直观：如果从x出发先走到邻居v，再沿v的最低开销路径到达y，开销是$c(x, v) + d_v(y)$；x只需要在所有邻居中选出使这个和最小的那一个，它同时也是x到y的下一跳。

该算法的结点具有的唯一信息是它到直接邻居的链路开销和它从这些邻居接收到的信息，每个结点等待来自任何邻居的更新。

每个结点x维护三样东西：到每个邻居v的链路开销$c(x, v)$；自己的距离向量$\mathbf{D}_x = [D_x(y): y \in N]$，即x对它到每个目的的最低开销的估计；以及从每个邻居收到的最新距离向量$\mathbf{D}_v$。算法的执行过程如下：

初始化：
    对每个目的y：D_x(y) = c(x, y)（不是邻居则为∞），D_x(x) = 0
    把D_x发给所有邻居
循环：
    等待（直连链路开销变化，或收到邻居发来的距离向量）
    对每个目的y：D_x(y) = min_v{c(x, v) + D_v(y)}
    如果D_x中有任何值发生变化，把新的D_x发给所有邻居

距离向量算法是迭代的（不断交换直到没有新信息）、异步的（各结点不必同时计算）和自我终止的（没有变化时就不再发送消息）。

链路开销变化与无穷计数问题

当某条链路的开销减小时，“好消息”会很快在网络中传开：每个结点算出更小的开销后立即通知邻居，几轮之后就收敛了。

开销增大时情况就不同了。考虑三个结点x、y、z：$c(x, y) = 4$，$c(y, z) = 1$，$c(z, x) = 50$。原先$D_y(x) = 4$（直达），$D_z(x) = 5$（经过y）。现在$c(x, y)$增大到60：

1. y发现变化，用z此前通告的$D_z(x) = 5$计算：$D_y(x) = \min\{60 + 0, 1 + 5\} = 6$，于是改为经过z到达x。可z到x的路径恰恰要经过y，这就形成了路由环路。
2. z收到y的新向量，算出$D_z(x) = \min\{50 + 0, 1 + 6\} = 7$，通告给y。
3. y又算出8，z又算出9……两者轮流把开销加1。

这样的交换要重复四十多次，直到z算出经过y的开销超过50、改为直达x为止。如果$c(z, x)$本身也很大甚至不存在，开销会一直增加下去，这称为无穷计数（count-to-infinity）问题。

毒性逆转（poisoned reverse）可以避免这种两个结点之间的环路：如果z经过y到达x，那么z向y通告$D_z(x) = \infty$。y就不会再选择经过z回到x，在上例中y直接算出$D_y(x) = 60$，很快收敛。不过毒性逆转无法解决涉及三个或更多结点的环路。

链路状态与距离向量的比较

因特网中两种算法都在使用：OSPF基于链路状态，RIP基于距离向量。RIP以跳数作为开销，最大跳数为15，16表示不可达（“无穷”），从而给无穷计数设了一个上限。