Question

2.5. 路由算法

2.5.1. 简介

路由算法是用于找到一条从源路由器到目的路由器的最佳路径的算法。存在着多种路由算法，每种算法对网络和路由器资源的影响都不同；由于路由算法使用多种度量标准 (metric)，所以不同路由算法的最佳路径选择也有所不同。

2.5.2. 路由选择算法的功能

源/宿对之间的路径选择，以及选定路由之后将报文传送到它们的目的地。

路由选择算法的要求：

• 正确性：确保分组从源节点传送到目的节点
• 简单性：实现方便，软硬件开销小
• 自适应性：也称健壮性，算法能够适应业务量和网络拓扑的变化
• 稳定性：能长时间无故障运行
• 公平性：每个节点都有机会传送信息
• 最优性：尽量选取好的路由

2.5.3. 自治系统 AS (Autonomous System)

经典定义：

• 由一个组织管理的一整套路由器和网络。
• 使用一种AS 内部的路由选择协议和共同的度量以确定分组在该 AS 内的路由。
• 使用一种 AS 之间的路由选择协议用以确定分组在AS之间的路由。

尽管一个 AS 使用了多种内部路由选择协议和度量，但对其他 AS 表现出的是一个单一的和一致的路由选择策略。

2.5.4. 两大类路由选择协议

因特网的中，路由协议可以分为内部网关协议 IGP (Interior Gateway Protocol)和外部网关协议 EGP (External Gateway Protocol)。

IGP是在一个AS内部使用的路由选择协议，如RIP和OSPF协议，是域内路由选择 (interdomain routing)。当源主机和目的主机处在不同的AS中，在数据报到达AS的边界时，使用外部网关协议 EGP 将路由选择信息传递到另一个自治系统中，如BGP-4，是域间路由选择 (intradomain routing)。

2.5.5. RIP

路由信息协议 (Routing Information Protocol, RIP) 是一种基于距离 向量的路由选择协议。RIP 协议要求网络中的每一个路由器都要维护从它自己到自治系统内其他每一个目的网络的距离和下一跳路由器地址。

2.5.6. OSPF

开放最短路径优先(Open Shortest Path First，OSPF)，这个算法名为“最短路径优先”是因为使用了 Dijkstra 提出的最短路径算法SPF，只是一个协议的名字，它并不表示其他的路由选择协议不是“最短路径优先”。