4.4 距离向量路由算法（P160 4.6.2）

（P159 4.6.2）路由信息协议 RIP（Routing Information Protocol） 是内部网关协议 IGP（Internal Gateway Protocol） 中最先得到广泛使用的协议。RIP 是一种分布式的基于距离向量的路由选择协议。

注：教材中所叙述的 RIP 协议是由 RFC-1058 定义的 RIP v1。而 RFC-2453 定义了 RIP v2。

RIP 协议要求网络中每个路由器都要维护一个从它自己到其他每一个目的网络的距离记录，即这是一组距离，因此命名为距离向量。

（P160 4.6.2）RIP 协议规定：

• 从路由器到直连网络的距离定义为 1。
• 从主机到非直连网络的距离定义为所经过的路由器数量加 1。
• 当距离等于 16 时即代表网络不可达。

RIP 协议所定义的距离又称跳数（Hop Count）。由于距离等于 16 即代表不可达，即一条路径最多包含 15 个路由器，因此 RIP 仅能适用于小型网络。

RIP 协议有以下三个要点：

• 仅和相邻的路由器交换信息。若两个路由器之间的通信不需要经过另一个路由器，则这两个路由器是相邻的。
• 路由器交换的信息是当前本路由器所知道的全部信息，即自己当前的路由表。
• 按固定时间间隔交换路由信息，当网络拓扑结构发生变化时，路由器立即开始一次信息交换。

若某次交换时传输发生错误等原因导致数据包被数据链路层丢弃，由于是按固定时间交换信息，则数据包丢失无伤大雅，于是无需对数据包做出确认。

当网络刚启动时，所有路由器的路由表都是空的。若路由器连接了一个子网，则向相邻的路由器通报，这些距离定义为 1。然后相邻的路由器继续通报给其相邻的路由器。最终网络中所有路由器都能得到自身所能达到的所有网络的距离，并形成路由表。这一过程称为收敛。

一般情况下，RIP 可以收敛，且收敛速度较快。

（P160 4.6.2）当路由器收到其相邻路由器发来的 RIP 报文：

• 修改报文中的所有条目，将“下一跳路由器”全部修改为发来报文的相邻路由器，将“距离”全部加 1。

• 对修改后的报文的每一个条目：

  • 若原来的路由表不包含条目中的网络，则将该项目直接加入路由表。

  • 若原来的路由表包含条目中的网络，则对比下一跳路由器：

    • 若已有条目的下一跳路由就是发来报文的相邻路由器，则将已有条目替换为新的条目（即更新距离）。
    • 若已有条目的下一跳路由不是发来报文的相邻路由器，则对比距离：
      • 若已有条目的距离大于通报的新距离，则更新路由表。
      • 否则放弃更新。

  若路由表有更新，则立即向相邻路由表通报。

• 若 3 分钟内没有收到路由表中存在的下一跳路由的通报信息，则将下一跳为该路由器的所有条目标记为不可达。

具体的：

• 网络启动，所有路由器的路由表都为空。

• 路由器 $R_1$ 连接子网 $Net_1$，于是 $R_1$ 记录路由表自身到 $Net_1$ 的距离为 1，并向相邻的路由器通报。

  此时 $R_1$ 的路由表如下：

  目的网络	距离	下一跳路由器
  $Net_1$	1	直接交付

• 路由器 $R_2$ 连接路由器 $R_1$，$R_2$ 收到 $R_1$ 发来的 RIP 报文。于是将距离加 1，下一跳路由器记录为 $R_1$，即：

  目的网络	距离	下一跳路由器
  $Net_1$	2	$R_1$

  检查发现路由表中没有目的网络为 $Net_1$ 的条目，于是存入路由表，并向 $R_2$ 相邻的路由器通报。

  此时 $R_2$ 的路由表如下：

  目的网络	距离	下一跳路由器
  $Net_1$	2	$R_1$

• 路由器 $R_1$ 收到 $R_2$ 发来的 RIP 报文，包含到 $Net_1$ 的条目。于是将距离加 1，下一跳路由器记录为 $R_2$，即：

  目的网络	距离	下一跳路由器
  $Net_1$	3	$R_2$

  检查发现路由表中存在目的网络为 $Net_1$ 的条目，且下一跳路由器与已有条目不同，于是对比距离，发现距离不小于已有条目中的距离（即 1），于是放弃该条目更新。由于路由表没有更新，则不对相邻路由进行通报。

  此时 $R_1$ 的路由表如下：

  目的网络	距离	下一跳路由器
  $Net_1$	1	直接交付

• 以此类推。

由此可见，RIP 协议拥有好消息传播得快的特点，即若一个路由发现了更短的路径，则更新信息传播速度很快。

但 RIP 协议还存在坏消息传播得慢的缺点。现假定 $R_1$ 到 $Net_1$ 的链路发生了故障：

• $R_1$ 发现到 $Net_1$ 的链路发生故障，于是将 $Net_1$ 的跳数标记为 16，并向相邻路由器通报。

  目的网络	距离	下一跳路由器
  $Net_1$	16	直接交付

  注：网络不可达有很多中标记方法，常见方法有：

  • 保留下一跳路由器为原值，仅修改距离为 16，这也是最常见的实现，也是上表中使用的标记方法。
  • 标记下一跳路由器为 $0.0.0.0$，并修改距离为 16。
  • 直接清除不可达的条目。

• 假设此刻碰巧是路由器之间定期交换路由表的时间，在 $R_2$ 收到 $R_1$ 发来的消息前，已将自己的路由表发送给了 $R_1$，即（$R_2$ 发来的路由表）：

  目的网络	距离	下一跳路由器
  $Net_1$	2	$R_1$

  此时 $R_1$ 收到 $R_2$ 发来的路由表，对比距离发现小于 16，即 $Net_1$ 可以通过 $R_2$ 到达，于是更新路由表（$R_1$ 的路由表）：

  目的网络	距离	下一跳路由器
  $Net_1$	3	$R_2$

  而 $R_2$ 收到 $R_1$ 先前发送的路由表，将 $Net_1$ 标记为不可达。

• 固定时间间隔后，路由器再次开始定期交换信息，$R_2$ 收到 $R_1$ 的路由表，将距离更新为 4。此时 $R_2$ 的路由表如下：

  目的网络	距离	下一跳路由器
  $Net_1$	4	$R_2$

• 每一次交换，路由表中到 $Net_1$ 的距离都 $+1$，直到 16，即不可达。

综上，当一个网络不可达时，可能出现需要经过很多轮交换才能让所有路由器都知晓网络 $Net_1$ 不可达的情况。

解决上述问题的方法称为水平分割，又称分裂视野。即如果路由器 A 从路由器 B 学习到了一条达到某个网络的距离，那么 A 就不会再将这个信息告诉给 B。

如果是用来水平分割的方法，在上述过程中的第二步里，$R_1$ 就不会收到 $R_2$ 发来的关于可以通过 $R_1$ 前往 $Net_1$ 且距离为 2 的信息，因此 $R_1$ 的路由表会保持到达 $Net_1$ 的距离为 16。