路由算法和路由协议

路由算法和路由协议之间的关系

如图：

路由算法和路由协议之间的关系

大纲要求掌握的路由协议： RIP 、 OSPF 、 BGP

路由算法 = 路由选择算法

路由协议 = 路由选择协议

路由算法

路由算法计算出最佳转发路径的本质是图的最短路径问题

图的节点为各网络节点，数据通路就为两者间的连接

路由协议会制定一种规则，度量一条边的“权值（代价）”

当一台路由器转发 IP 数据报时，本质就要找到从本路由器到达目的网络的“最优路径”

分类

根据是否随网络的通信量或拓扑自适应地进行调整变化来划分，路由算法可以分为两大类

• 静态路由算法

指由网络管理员手工配置每一条路由

特点：实现简单、开销小、不具备自适应能力，适用于小型网络

• 动态路由算法

路由器根据网络流量负载和拓扑结构的变化来动态调整自身的路由表

考研大纲要求的动态路由算法是：距离-向量路由算法👍和链路状态路由算法👍

特点：实现复杂、开销大、具备自适应能力，适用于大型网络

RIP 协议使用距离-向量路由算法

OSPF 协议使用链路状态路由算法

BGP 协议使用路径-向量路由算法（考纲未明确要求掌握该算法）

距离-向量路由算法

本质为 Bellman-Ford 算法在路由领域的应用

假设有以下路由拓扑：

距离-向量路由算法示例拓扑

$c(x, v_1)$ 表示 $X$ 和 $v_1$ 之间的“距离”

$d_{v_1}(net_1)$ 表示 $v_1$ 到 $net_1$ 之间的“距离”

注意

不同的路由协议对“距离”的定义可能不同。例如可以规定：

• 直接相连的两个节点之间的“距离”为 1

或

• 以往返时延作为链路的“距离”

假设 $d_x(net_1)$ 表示 $X$ 到 $net_1$ 之间的最短距离（最小代价），则有 $d_x(net_1) = \min{(c(x, v) + d_v(net_1))}$ ，其中， $v$ 是 $x$ 的所有邻居

假设一片区域有多个目的路由器

距离-向量路由算法示例拓扑

则有 $v_1$ 到 < $net_1$ , $net_2$ , $net_3$ > 的距离分别为 < $d_{v_{1}}(net_1)$ , $d_{v_{1}}(net_2)$ , $d_{v_{1}}(net_3)$ >

同理，$v_2$ 到 < $net_1$ , $net_2$ , $net_3$ > 的距离分别为 < $d_{v_{2}}(net_1)$ , $d_{v_{2}}(net_2)$ , $d_{v_{2}}(net_3)$ >

$v_3$ 到 < $net_1$ , $net_2$ , $net_3$ > 的距离分别为 < $d_{v_{3}}(net_1)$ , $d_{v_{3}}(net_2)$ , $d_{v_{3}}(net_3)$ >

$v_k$ 到 < $net_1$ , $net_2$ , $net_3$ > 的距离分别为 < $d_{v_{k}}(net_1)$ , $d_{v_{k}}(net_2)$ , $d_{v_{k}}(net_3)$ >

距离向量则为上述的后半段内容，如：< $d_{v_{1}}(net_1)$ , $d_{v_{1}}(net_2)$ , $d_{v_{1}}(net_3)$ >

对于计算 $X$ 到各目的路由器的距离，则由 $X$ 到各路由器的距离和各路由器到各目的路由器的距离向量相加得到

链路状态路由算法

链状态路由算法要求每台路由器节点都要完整了解网络的拓扑结构（知道全网的节点、相连关系、路径的权重）

获取到完整的网络拓扑结构后，就可以用数据结构中带权图的迪杰斯特拉算法找到最优转发路径

对于计算机网络而言，该算法的重点在于如何动态获取全网的网络拓扑，之后在 OSPF 算法中详细讲解

分层次的路由协议这里后续更新 TODO