路由算法

静态路由和动态路由

路由表的配置包含两种方式：静态路由和动态路由。

静态路由表示路由器的路由规则由人工进行手动配置，是写死的，每次想更改路由表时必须手动去更改。

动态路由规则根据 路由算法 动态地构建路由表，这里主要包含 RIP 和 OSPF 两种方式。

两种路由方式的具体对比如下表所示：

什么是路由算法

路由算法是网络通信中的一种机制，它决定数据包在计算机网络中从源地址传输到目标地址的路径。路由算法通过选择最佳路径来优化数据传输，确保数据有效且快速地传递。

路由算法的设计是为了实现以下目标：

1. 最短路径选择：刚一个数据包经过当前机器时，路由算法通过计算路径的成本（如跳数、带宽、延迟等），能够选择从源到目标的最短或最优路径。
2. 负载均衡：在网络拥堵时，将数据流量分散到多条路径上，以避免某一条路径过载。
3. 快速收敛：当网络拓扑发生变化（如链路失败或新增路由器）时，路由算法能够快速调整并更新路由信息，确保网络稳定。

RIP 算法

RIP（Routing Information Protocol）是一种基于距离向量的路由协议，主要用于小型和中型网络中的内部网关协议。

距离向量

一个典型的距离向量（Distance Vector）可以表示为一个列表，其中每个条目包含以下信息：

• 目的地：目标网络或子网的地址。
• 距离：从当前路由器到达目标网络的代价，通常以跳数、延迟、带宽等度量标准表示。
• 下一跳：到达目标网络的下一跳路由器的地址。

距离向量算法

在距离向量算法中， 通过 周期性地 与相邻路由器 交换距离向量信息，每个路由器能够逐渐获得整个网络的拓扑信息，并更新其路由表 以选择最佳路径。

具体而言，工作流程如下：

• 初始化：每个路由器初始化其距离向量，只包含自己直接连接的网络，距离设为 0。
• 周期性更新：每个路由器周期性地将其距离向量广播给所有相邻的路由器。
• 接收和更新：每个路由器接收到相邻路由器的距离向量后，检查是否有新的或更短的路径。如果有，则更新自己的距离向量和路由表。
• 收敛：经过多次交换和更新后，所有路由器的距离向量和路由表最终会收敛到最优路径。

最短路径计算方法

当路由器 $A$ 接收到来自相邻路由器 $B$ 发送的关于某个子网 $N$ 的距离向量 $V_{B}$ 时，它需要将 $V_{B}$ 中的跳数加一 然后与当前的到达子网 $N$ 的距离向量 $V_{A}$ 进行比较（需要加一的原因时从 $A$ 出发要经过 $B$，所以多了一跳），具体比较方式如下：

• 如果 $A$ 不存在到达子网 $N$ 的路由的话，直接添加 $V_{B}$ 进入路由表
• 如果 $V_{B}$ 的跳数小于 $V_{A}$ 的跳数的话，使用 $V_{B}$ 替换 $V_{A}$

以上过程使用的算法名称叫做 Bellman-Ford 算法，是一种寻找单源最短路径的算法，单源最短路径的意思是从一个结点出发到达其他结点的最短路径。这个算法不会直接考察，了解这个算法的名称即可。

OSPF 算法

OSPF（Open Shortest Path First）是一种基于链路状态的内部网关协议（IGP），广泛应用于中大型网络中。

OSPF 几乎不考察，这里主要了解以下几个小节的概念即可。

链路状态通告

路由器通过链路状态通告（LSA，Link State Advertisement）来了解其与邻居之间的链路状态。

在 RIP 路由算法中，路由器会定期将自己的距离向量发送给相邻的路由器。在 OSPF 中，也有类似的概念，不过这里传送的不是距离向量，而是链路状态通告。

路由器将其自身的状态和与邻居的链路状态信息打包成链路状态包（LSP，Link State Packet），并在网络中洪泛（flooding）传播。

每个 LSA 专注于描述一种类型的链路状态或网络信息。一个 LSA 包含的信息通常是：

• 路由器与某一特定链路的连接状态（如 Router LSA）。
• 某个网络的状态和与其相连的路由器信息（如 Network LSA）。
• 区域间或外部路由信息（如 Summary LSA 和 AS External LSA）。

链路状态数据库

链路状态数据库（LSDB，Link State Database）是 OSPF 协议中的一个关键组件，它存储了网络中所有链路状态通告（LSA）。通过 LSDB，每个路由器可以构建整个网络的拓扑图，并使用 Dijkstra 算法计算最短路径树。

这里举个例子方便大家理解 LSDB 的概念。 假设我们有一个简单的网络拓扑，包含 4 个路由器（R1, R2, R3, R4）和几个网络网段（NetA, NetB, NetC）。

      NetA
    /       \
[R1]-----[R2]-----[NetB]
  |        |        |
  |        |        |
[NetC]    [R3]----[R4]

在链路状态算法收敛之后，某个路由器的 LSDB 可能是如下这种形式：

链路状态路由算法

OSPF 中的链路状态路由算法的思想与 RIP 中的最短路径计算算法的思想类似，不过这里是使用 Dijkstra 算法来计算最短路径。 Dijkstra 算法使用 LSDB 中的信息来生成一棵最短路径树（SPT），确定从源节点到所有其他节点的最短路径。

对比