# 4.2 路由算法

## 一、路由算法概述

### 1.1 什么是路由算法

**路由算法**：
- 确定分组从源到目的的路径的算法
- 是网络层的核心算法

### 1.2 路由算法的分类

**按静态/动态分类**：
- 静态路由算法
- 动态路由算法

**按范围分类**：
- 全局路由算法（链路状态算法）
- 分布式路由算法（距离向量算法）

**按负载敏感分类**：
- 负载敏感算法
- 负载迟钝算法

---

## 二、静态路由算法

### 2.1 基本概念

**静态路由**：
- 路由表由管理员手动配置
- 不随网络状态变化
- 也称为非自适应路由

### 2.2 特点

**优点**：
- 简单
- 开销小
- 安全可靠

**缺点**：
- 不能适应网络变化
- 工作量大
- 容易出错
- 不适合大型网络

### 2.3 应用场景

- 小型网络
- 网络拓扑稳定
- 安全要求高
- 默认路由

---

## 三、动态路由算法

### 3.1 基本概念

**动态路由**：
- 路由表根据网络状态自动调整
- 也称为自适应路由

### 3.2 特点

**优点**：
- 自动适应网络变化
- 减少管理员工作量
- 适合大型网络

**缺点**：
- 复杂
- 开销大
- 可能产生路由环路

### 3.3 分类

**全局路由算法（链路状态算法）**：
- 所有路由器掌握完整的网络拓扑信息
- 使用Dijkstra算法
- 如：OSPF

**分布式路由算法（距离向量算法）**：
- 每个路由器只知道邻居信息
- 迭代计算
- 如：RIP

---

## 四、距离向量路由算法

### 4.1 基本概念

**距离向量（Distance Vector）**：
- 每个路由器维护一个距离向量表
- 记录到所有目的地的距离（代价）和下一跳

**距离**：
- 跳数（RIP）
- 延迟
- 带宽
- 费用

### 4.2 Bellman-Ford方程

$$d_x(y) = \min_v\{c(x,v) + d_v(y)\}$$

其中：
- $d_x(y)$：从x到y的最短路径代价
- $c(x,v)$：从x到邻居v的链路代价
- $d_v(y)$：从v到y的最短路径代价

### 4.3 算法过程

**初始化**：
- 到直接邻居的距离 = 链路代价
- 到其他节点的距离 = ∞

**迭代**：
1. 每个路由器向邻居发送自己的距离向量
2. 收到邻居的距离向量后，更新自己的距离向量
3. 重复直到收敛

**更新公式**：
$$D_x(y) = \min_v\{c(x,v) + D_v(y)\}$$

### 4.4 特点

**优点**：
- 简单
- 开销小

**缺点**：
- 收敛慢
- 可能产生路由环路
- 计数到无穷大问题

### 4.5 路由环路问题

**问题**：
- 链路故障时，路由器可能选择错误路径
- 形成环路

**解决方法**：
- **最大跳数限制**：RIP限制为15跳
- **水平分割**：不向原方向通告路由
- **毒性逆转**：向原方向通告无穷大代价
- **抑制计时器**：延迟更新

---

## 五、链路状态路由算法

### 5.1 基本概念

**链路状态（Link State）**：
- 每个路由器掌握完整的网络拓扑
- 使用Dijkstra算法计算最短路径

### 5.2 算法过程

**链路状态分组（LSA）**：
1. 每个路由器检测邻居和链路代价
2. 向所有路由器广播链路状态
3. 每个路由器收集所有LSA，构建拓扑图

**最短路径计算**：
1. 使用Dijkstra算法
2. 计算到所有节点的最短路径
3. 生成路由表

### 5.3 Dijkstra算法

**算法思想**：
- 贪心算法
- 逐步扩展最短路径集合

**算法步骤**：
1. 初始化：起点距离为0，其他为∞
2. 选择距离最小的未确定节点u
3. 对u的每个邻居v，更新距离：
   - 如果d(u) + c(u,v) < d(v)，更新d(v)
4. 标记u为已确定
5. 重复步骤2-4，直到所有节点确定

**时间复杂度**：O(n²) 或 O(n log n)（使用优先队列）

### 5.4 特点

**优点**：
- 收敛快
- 无路由环路
- 支持多种代价度量

**缺点**：
- 需要维护完整拓扑
- 开销大
- 计算复杂度高

---

## 六、层次路由

### 6.1 为什么需要层次路由

**问题**：
- 网络规模大时，路由表太大
- 路由计算开销大
- 路由更新流量大

**解决**：
- 将网络划分为区域（自治系统）
- 分层次进行路由

### 6.2 自治系统（AS）

**定义**：
- 一组在统一管理下的路由器
- 使用相同的路由策略

**特点**：
- 内部使用内部网关协议（IGP）
- 之间使用外部网关协议（EGP）

### 6.3 层次路由的结构

**区域内路由**：
- 使用内部网关协议
- RIP、OSPF

**区域间路由**：
- 使用外部网关协议
- BGP

---

## 七、路由算法比较

| 特性 | 距离向量 | 链路状态 |
|-----|---------|---------|
| 信息范围 | 邻居 | 全网 |
| 算法类型 | 分布式 | 集中式（全局） |
| 收敛速度 | 慢 | 快 |
| 路由环路 | 可能 | 不会 |
| 复杂度 | 低 | 高 |
| 开销 | 小 | 大 |
| 应用 | RIP | OSPF |

---

## 八、考研重点

1. **路由算法的分类**：
   - 静态/动态
   - 全局/分布式
   - 负载敏感/迟钝

2. **静态路由算法**：特点、应用场景

3. **动态路由算法**：特点

4. **距离向量路由算法**：
   - Bellman-Ford方程
   - 算法过程
   - 特点
   - 路由环路问题及解决方法

5. **链路状态路由算法**：
   - 算法过程
   - Dijkstra算法
   - 特点

6. **层次路由**：
   - 自治系统（AS）
   - 内部网关协议和外部网关协议

7. **路由算法比较**

---

*下一节：4.3 IPv4*