路由算法

掌握RIP和OSPF的流程，可能在选择题中考察。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

每个LSA专注于描述一种类型的链路状态或网络信息。一个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 可能是如下这种形式：

LSA 类型	LSA ID	路由器 ID	链路 ID	链路类型	路径成本	连接的路由器或网络
Router	1	R1	NetA	广播链路	10	R2
Router	1	R1	NetC	广播链路	5
Router	2	R2	NetA	广播链路	10	R1
Router	2	R2	NetB	广播链路	15	R4
Router	2	R2	R3	点对点链路	20	R3
Router	3	R3	R2	点对点链路	20	R2
Router	3	R3	R4	点对点链路	10	R4
Router	4	R4	NetB	广播链路	15	R2
Router	4	R4	R3	点对点链路	10	R3

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