路由算法

路由算法

1. 路由算法概述

路由算法是网络层的核心，负责为数据包选择最佳传输路径。

路由算法的目标

• 最短路径：选择距离最短的路径
• 最小延迟：选择延迟最小的路径
• 最大带宽：选择带宽最大的路径
• 最小成本：选择成本最低的路径

路由算法的分类

• 静态路由：人工配置，不自动更新
• 动态路由：自动学习，根据网络变化更新

2. 静态路由

特点

• 人工配置：网络管理员手动配置
• 固定不变：除非人工修改，否则不变
• 简单可靠：配置简单，运行稳定
• 适合小型网络：网络规模较小时使用

配置方式

• 直连路由：路由器直接连接的网络
• 静态路由：手动配置的路由条目
• 默认路由：当没有匹配的路由时使用

优缺点

优点：

• 配置简单
• 运行稳定
• 不占用网络带宽
• 安全性好

缺点：

• 不能适应网络变化
• 配置工作量大
• 容易出错
• 不适合大型网络

3. 动态路由

特点

• 自动学习：路由器自动学习网络拓扑
• 自动更新：根据网络变化自动更新路由表
• 适应性强：能够适应网络拓扑变化
• 适合大型网络：网络规模较大时使用

分类

• 距离向量算法：基于距离信息
• 链路状态算法：基于链路状态信息
• 路径向量算法：基于路径信息

4. 距离向量路由算法

基本原理

• 距离信息：每个路由器只知道到邻居的距离
• 周期性交换：定期与邻居交换路由信息
• 分布式计算：每个路由器独立计算最短路径
• Bellman-Ford 算法：基于动态规划的最短路径算法

工作过程

1. 初始化：路由器只知道直连网络的距离
2. 信息交换：与邻居交换路由表信息
3. 距离计算：使用 Bellman-Ford 算法计算最短路径
4. 路由更新：更新本地路由表
5. 重复过程：重复步骤 2-4 直到收敛

典型协议

• RIP：路由信息协议，跳数限制为 15
• IGRP：内部网关路由协议，Cisco 专有
• EIGRP：增强型内部网关路由协议

优缺点

优点：

• 实现简单
• 计算量小
• 适合小型网络

缺点：

• 收敛速度慢
• 容易产生路由环路
• 跳数限制限制了网络规模

5. 链路状态路由算法

基本原理

• 链路状态信息：每个路由器收集全网链路状态
• 拓扑数据库：构建完整的网络拓扑图
• 集中式计算：使用 Dijkstra 算法计算最短路径
• 全局视图：每个路由器都有全网拓扑信息

工作过程

1. 发现邻居：通过 Hello 包发现邻居路由器
2. 测量成本：测量到邻居的链路成本
3. 构建 LSA：构建链路状态通告
4. 泛洪传播：将 LSA 泛洪到全网
5. 构建拓扑：构建完整的网络拓扑数据库
6. 计算路径：使用 Dijkstra 算法计算最短路径

典型协议

• OSPF：开放最短路径优先协议
• IS-IS：中间系统到中间系统协议

优缺点

优点：

• 收敛速度快
• 支持大型网络
• 支持多种度量
• 不容易产生路由环路

缺点：

• 实现复杂
• 计算量大
• 占用更多资源

6. 层次路由

基本原理

• 分层结构：将网络分为多个层次
• 域内路由：在同一个域内使用域内路由协议
• 域间路由：在不同域间使用域间路由协议
• 自治系统：每个自治系统独立管理

层次结构

• 自治系统（AS）：独立管理的网络
• 域内路由协议：RIP、OSPF、IS-IS
• 域间路由协议：BGP

优点

• 可扩展性：支持大规模网络
• 管理简单：分层管理，职责明确
• 安全性：域间路由可以实施安全策略
• 灵活性：不同域可以使用不同的路由协议

练习题

练习 1

距离向量与链路状态路由算法有何区别？

练习 2

静态路由和动态路由各有什么优缺点？