考研笔记

路由算法：静态与动态，距离-向量与链路状态

路由选择协议的核心是路由算法，即需要何种算法来获得路由表中的各个项目。路由算法的目的很简单：给定一组路由器及连接路由器的链路，路由算法要找到一条从源路由器到目的路由器的”最佳”路径。通常，“最佳”路径是指具有最低费用的路径。

本节是 4.4 的理论底座：两种动态路由算法分别落地为 RIP（4.4.3）和 OSPF（4.4.4）。区分两者只需记住三个问题的答案：和谁交换、交换什么、怎样计算。

机制

静态路由与动态路由

路由器转发分组是通过路由表转发的，而路由表是通过各种算法得到的。从能否随网络的通信量或拓扑自适应地进行调整变化来划分，路由算法可以分为如下两大类：

静态路由算法动态路由算法
做法网络管理员手工配置每一条路由根据网络流量负载和拓扑结构的变化来动态调整自身的路由表
优点简单、开销较小能较好地适应网络状态的变化
缺点不能及时适应网络状态的变化实现复杂，开销也大
适用简单的小型网络较复杂的大型网络

常用的动态路由算法可分为两类：距离-向量路由算法和链路状态路由算法。

距离-向量路由算法

距离-向量算法的基础是 Bellman-Ford 算法，它用于计算单源最短路径。每个节点以自身为源点执行 Bellman-Ford 算法，所以全局上可以解决任意节点对之间的最短路径问题。

设 表示从节点 到节点 的带权最短路径的费用，则是的所有邻居式中， 是从 到其邻居 的费用。已知 的所有邻居到 的最短路径费用后，从 到 的最短路径费用是对所有邻居 的 的最小值。所有最短路径算法都依赖于一个性质：“两点之间的最短路径也包含了路径上其他顶点间的最短路径。”

对于距离-向量算法，每个节点 维护下列路由信息：

  1. 从 到每个直接相连邻居 的链路费用 。
  2. 节点 的距离向量，即 到网络中其他节点的费用。这是一组距离，因此称为距离向量。
  3. 它收到的每个邻居的距离向量，即 的每个邻居到网络中其他节点的费用。

在距离-向量算法中，每个节点定期地向它的每个邻居发送它的距离向量副本。当节点 从它的任何一个邻居 接收到一个新距离向量时，它首先保存 的距离向量，然后使用 Bellman-Ford 公式更新自己的距离向量。若节点 的距离向量因这个更新步骤而改变，则节点 接下来继续向它的每个邻居发送其更新后的距离向量。

例（距离向量路由算法的具体实现 2021 年考过）：三个节点 、、，链路费用 ，，。

目的初始 初始 初始 第一次交换后 第一次交换后
02703
20121
71030

初始时各节点之间尚未交换过任何路由信息，每个节点的距离向量就等于它到每个直接相连邻居的费用。每个节点第一次向所有邻居发送距离向量后，节点 重新计算：节点 到节点 的最低费用从 7 变成了 3，节点 到节点 的最低费用也从 7 变成了 3。距离向量变化了的节点再次向邻居发送更新，没有变化的节点 不用发送。接收到更新报文后重新计算，此次没有节点更新，因此也无更新报文发送，算法进入静止状态。

显然，更新报文的大小与网络中的节点数量成正比，大型网络将导致很大的更新报文。最常见的距离-向量路由算法是 RIP 算法，它采用跳数作为距离的度量。

链路状态路由算法

链路状态是指本路由器都和哪些路由器相邻，以及相应链路的代价。链路状态算法要求每个节点都具有全网拓扑结构图（这个拓扑结构图在全网范围内是一致的），它们执行下列两项任务：第一，主动测试所有相邻节点的状态；第二，定期地将链路状态传播给所有其他节点。因此每个节点都知道全网共有多少个节点、哪些节点是相连的、其代价是多少等，于是每个节点都可使用 Dijkstra 最短路径算法计算出到达其他节点的最短路径。

在链路状态算法中，节点每收到一个链路状态报文，便用其更新自己的网络状态”视野图”；一旦链路状态发生变化，就使用 Dijkstra 算法重新计算到达所有其他节点的最短路径。

因为一个节点的链路状态只涉及相邻节点的连通状态，而与整个互联网的规模并无直接关系，所以链路状态算法适用于大型的或路由信息变化聚敛的互联网环境。

链路状态算法的主要优点是：

  • 每个节点都使用同样的链路状态数据独立地计算路径，而不依赖中间节点的计算；
  • 链路状态报文不加改变地传播，因此采用该算法易于查找故障；
  • 当一个节点从所有其他节点接收到报文时，它就在本地立即计算出正确的路径，保证一步汇聚；
  • 因为链路状态报文仅运载来自单个节点关于直接链路的信息，其大小与网络中的节点数量无关，所以链路状态算法比距离-向量算法有更好的规模可伸展性。

典型的链路状态路由算法是 OSPF 算法。

两种算法的比较

比较项距离-向量链路状态
和谁交换仅与直接邻居通过洪泛与所有其他节点
交换什么自己的路由表（到所有目的地的距离）只有与自己直接相连的链路的费用
报文大小与网络中的节点数量成正比，代价较大与节点数量无关
每个节点知道什么只知道经哪个邻居、距离多少，不知道全网拓扑全网拓扑
计算方法Bellman-Ford，依赖邻居的计算结果Dijkstra，各自独立计算
典型协议RIPOSPF

一句话概括：距离-向量是”把我知道的一切告诉邻居”，链路状态是”把我的邻居告诉所有人”。

边界

距离-向量算法中，节点不知道全网拓扑。 它只知道到每个目的地”经过哪个邻居、总距离多少”，因此一旦邻居给出了错误的距离，它无从核实，这就是 RIP”坏消息传得慢”的根源（4.4.3）。

链路状态算法”与所有节点交换”，交换的却是很少的信息；距离-向量算法”只与邻居交换”，交换的却是全部信息。 两个维度正好相反，判断题常把它们交叉搭配。

只有距离向量变化了的节点才发送更新。 例子中节点 第一次交换后没有变化，就不再发送。

两种算法都是动态路由算法。 静态路由由管理员配置，不运行任何路由算法。

对照速查

说法对错
静态路由能及时适应网络状态的变化❌
距离-向量算法的基础是 Bellman-Ford 算法✅
距离-向量算法中，每个节点向所有节点发送自己的路由表❌（只向邻居）
链路状态算法中，每个节点只向邻居发送链路状态❌（向所有节点）
链路状态算法中，每个节点都有全网拓扑图✅
链路状态报文的大小与网络中的节点数量成正比❌（距离-向量才是）
链路状态算法比距离-向量算法有更好的可伸展性✅
典型的距离-向量协议是 OSPF❌（RIP）

考点

  • 静态路由 vs 动态路由
  • 距离-向量：Bellman-Ford，，只和邻居交换全部路由表（2021）
  • 链路状态：Dijkstra，洪泛给所有节点，只含相邻链路费用，全网拓扑一致
  • 比较表；RIP 属于距离-向量，OSPF 属于链路状态

链接

反向链接