4.2 路由算法

路由算法：静态与动态路由、距离-向量、链路状态、层次路由。

4.2 路由算法

路由表是路由器进行分组转发的核心依据，由路由选择算法生成。根据能否根据网络通信量及拓扑结构动态调整，路由算法分为两大类。

4.2.1 静态路由与动态路由

4.2.2 距离-向量路由算法

基本概念

• 距离向量：每个节点维护一个包含所有目标节点距离的向量，距离通常以跳数衡量。
• 路由表：记录到达各目标节点的下一跳节点和路径距离。

路由信息交换

• 节点周期性地向相邻节点广播其距离向量。
• 接收到距离向量后，节点根据Bellman-Ford算法更新自己的路由表。

Bellman-Ford算法

节点i对其每个相邻节点j的距离向量进行处理，更新到目标节点k的最短路径距离$D_i(k)$：

$$D_i(k) = \min(D_i(k),; D_j(k) + c_{i,j})$$

其中，$c_{i,j}$表示节点i到节点j之间的路径代价（通常为1表示一跳）。

特点

• 收敛：通过多次迭代和信息交换，最终所有节点的路由表达到稳定状态。
• 慢收敛：收敛速度较慢。
• 路由环路：可能产生环路问题，导致数据包在网络中不断循环。
• 典型协议：RIP（Routing Information Protocol）

例题（2021年37题）

某网络所有路由器均采用距离向量路由算法。路由器E与邻居A、B、C、D的直接链路距离分别为8、10、12、6，收到邻居的距离向量如下表：

求：E更新后的到达Net1~Net4的距离。

解：E到各目的网络的距离 = min(直接链路距离 + 邻居到目的的距离)

• Net1：min(8+1=9, 10+23=33, 12+20=32, 6+22=28) = 9
• Net2：min(8+12=20, 10+35=45, 12+30=42, 6+28=34) = 20
• Net3：min(8+24=32, 10+18=28, 12+16=28, 6+36=42) = 28
• Net4：min(8+36=44, 10+30=40, 12+8=20, 6+24=30) = 20

答案：C. 9, 20, 28, 20

4.2.3 链路状态路由算法

基本概念

• 链路状态：每个路由器了解其直接相连链路的状态（带宽、延迟、成本等）及相邻节点。
• **链路状态包(LSP)**：包含节点链路状态的信息，广播给整个网络。

算法步骤

1. 初始化：每个节点仅了解与其直接相连的链路状态。
2. 链路状态包生成：节点创建LSP，包含节点ID、相邻节点ID、链路成本等信息。
3. 链路状态包广播：节点将LSP通过泛洪法发送给所有相邻节点，确保全网收到。
4. 拓扑数据库更新：每个节点根据收到的LSP构建全网拓扑图（链路状态数据库）。
5. 最短路径计算：每个节点使用Dijkstra算法计算到所有其他节点的最短路径，生成路由表。

特点

• 发送方式：向本自治系统中所有路由器发送信息（泛洪法）。
• 发送内容：与路由器相邻的所有路由器的链路状态。
• 发送时机：仅当链路状态发生变化时才发送。
• 典型协议：OSPF（Open Shortest Path First）

优点

• 每个节点独立计算路径，不依赖中间节点。
• 链路状态报文不加改变地传播，易于查找故障。
• 一步汇聚：节点收到所有报文后可立即计算正确通路。
• 报文大小只与邻接节点数有关，规模可伸展性优于距离-向量算法。

4.2.4 层次路由

• 因特网将路由协议划分为**内部网关协议(IGP)和外部网关协议(EGP)**。
• 层次路由：使用OSPF将一个自治系统(AS)划分为多个区域。
  • 每个路由器仅知道本区域内的转发细节。
  • 虽增加了信息交换种类，但大大减少了区域内部路由信息交换的通信量。
  • 使OSPF协议能用于规模很大的自治系统。

笔记结束