路由选择协议的核心是路由算法，即需要何种算法来获得路由表中的各项目。一个理想的路由算法应具有如下一些特点：

从路由算法能否随网络的通信量或拓扑自适应地进行调制变化来划分，有两大类：

路由信息协议 RIP (Routing Information Protocol) 是一种分布式的基于距离向量的路由选择协议，其最大的优点是简单。

RIP 协议要求网络中的每一个路由器都要维护从它自己到其他每一个目的网络的距离记录，因此这是一组距离，即距离向量。

RIP 协议中距离定义：从一路由器到直接连接的网络的距离定义为 1。从一路由器到非直接连接的网络的距离定义为所经过的路由器数加 1。

RIP 协议的距离也称为跳数 (hop count)。RIP 认为好的路由就是它通过的路由器的数目少，即距离短。RIP 允许一条路径最多只能包含 15 个路由器。因此距离等于 16 时即相当于不可达。可见 RIP 只适用于小型网络。

路由表中最主要的信息：到某个网络的距离 (即最短距离)，以及应经过的下一跳地址。 路由表更新的原则是找出到每个目的网络的最短距离。这种更新算法又称为距离向量算法。

RIP 协议的距离向量算法：

距离向量算法的基础是 Bellman-Ford 算法 (或 Ford-Fullkerson 算法)。这种算法的要点：设 X 是结点 A 到 B 的最短路径上的一个结点。若把路径 A->B 拆成两段路径 A->X 和 X->B，则每一段路径 A->X 和 X->B 也都是分别是结点 A 到 X 和结点 X 到 B 的最短路径。

RIP 首部中的命令字段指出报文的意义。例，1 表示请求路由信息，2 表示对请求路由信息的响应或未被请求而发出的路由更新报文。 RIP2 报文中路由部分由若干个路由信息组成。每个路由信息需要 20 个字节 [RFC 2453]。 地址族标识符 (又称为地址类别) 字段用来标志所使用的地址协议。如采用 IP 地址就令这个字段的值为 2。 路由标记填入自治系统号 ASN (Autonomous System Number)，这是考虑使 RIP 有可能收到本自治系统以外的路由选择信息。 一个 RIP 报文最多可包括 25 个路由，因而 RIP 报文的最大长度是 4 + 20 × 25 = 504 字节。

RIP2 还提供简单的鉴别过程支持多播。若使用鉴别功能，则将原来写入第一个路由信息 (20 字节) 的位置用作鉴别。这时应将地址族标识符置为全 1，路由标记写入鉴别类型，剩下的 16 字节为鉴别数据。在鉴别数据之后才写入路由信息。

RIP 存在的一个问题：当网络出现故障时，要经过比较长的时间才能将此信息传送到所有的路由器。 RIP 协议的这一特点叫做：好消息传播得快，坏消息传播得慢。 为了使坏消息传播得更快些，可以采取多种措施。例，让路由器记录收到某特定路由信息的接口，而不让同一路由信息再通过此接口向反方向传送。

RIP 协议最大的优点是实现简单，开销较小。

RIP 协议的缺点：

开放最短路径优先 OSPF (Open Shortest Path First) 原理简单，但实现起来较复杂 [RFC 2328]。“开放”表明 OSPF 是公开发表的。“最短路径优先”是因为使用了 Dijkstra 提出的最短路径算法 SPF。

由于各路由器之间频繁地交换链路状态信息，因此所有的路由器最终都能建立一个链路状态数据库 (link-state database)，这个数据库实际上就是全网的拓扑结构图。这个拓扑结构图在全网范围内是一致的 (这称为链路状态数据库的同步)。

OSPF 的链路状态数据库能较快地进行更新，使各个路由器能及时更新其路由表。OSPF 的更新过程收敛得快是其重要优点。

为了使 OSPF 能够用于规模很大的网络，OSPF 将一个自治系统再划分为若干个更小的范围，叫做区域 (area)。 划分区域的好处：利用洪泛法交换链路状态信息的范围局限于每一个区域而不是整个的自治系统，这减少了整个网络上的通信量。 为了使每一个区域能够和本区域以外的区域进行通信，OSPF 使用层次结构的区域划分。 在上层的区域叫做主干区域 (backbone area)。主干区域的标识符规定为 0.0.0.0。主干区域的作用是用来连通其他在下层的区域。在主干区域内的路由器叫做主干路由器 (backbone router)。从其他区域来的信息都由区域边界路由器 (area border router) 进行概括。 在主干区域内要有一个路由器专门和本自治系统外的其他自治系统交换路由信息。这样的路由器叫做自治系统边界路由器。

OSPF 的五种分组类型：

问候分组用来确定链路状态数据库的内容。只有可达邻站的链路状态信息才存入链路状态数据库。若相邻路由器不可达，应立即修改链路状态数据库，并重新计算路由表。

其他四种分组都是用来进行链路状态数据库的同步。同步是指不同路由器的链路状态数据库的内容是一样的。两个同步的路由器叫做完全邻接的 (fully adjacent) 路由器。 OSPF 使用可靠的洪泛法向全网更新链路状态。可靠的洪泛法是在收到更新分组后要发送确认 (收到重复的更新分组只需要发送一次确认)。

在不同的自治系统 AS 之间的路由选择为什么不能使用内部网关协议，如 RIP 或 OSPF？

边界网关协议 BGP 只能是力求寻找一条能够到达目的网络且比较好的路由，而并非要寻找一条最佳路由。BGP 采用了路径向量(path vector)路由选择协议 [RFC 4271]。

在 RFC 4271 中规定了 BGP-4 的四种报文：

路由器是一种具有多个输入端口和多个输出端口的专用计算机，其任务是转发分组。路由器的转发分组正是网络层的主要工作。 整个的路由器结构可划分为两大部分：

问题在于路由器必须以很高的速率转发分组。最理想的情况是输入端口的处理速率能够跟上线路把分组传送到路由器的速率。这种速率称为线速 (line speed 或 wire speed)。

交换结构是路由器的关键构件。这个交换结构把分组从一个输入端口转移到某个合适的输出端口。实现这样的交换的三种常用方法：

4-38 IGP 和 EGP 这两类协议的主要区别是什么？

互联网采用的路由选择协议主要是自适应的、分布式路由选择协议。

互联网采用分层次的路由选择协议。可以把整个互联网划分为许多较小的自治系统 AS (autonomous system)。自治系统是在单一技术管理下的一组路由器，而这些路由器使用一种自治系统内部的路由选择协议和共同的度量。一个 AS 对其他 AS 表现出的是一个单一的和一致的路由选择策略。

★ \bigstar ★ 在目前的互联网中，一个大的 ISP 就是一个自治系统。互联网把路由选择协议分为两大类：

注意：早期 RFC 文档未使用“路由器”而使用“网关”这一名词。但在新的 RFC 文档中改用“路由器”，因此有的书把 IGP 和 EGP 分别改为 IRP (内部路由器协议) 和 ERP (外部路由器协议)。此处 IGP 和 EGP 是协议类别的名称。

4-39 试简述 RIP，OSPF 和 BGP 路由选择协议的主要特点。

RIP 协议和 OSPF 协议都是分布式路由选择协议。它们的共同特点是每一个路由器都要不断地和其它路由器交换路由信息。 三个要点，即和哪些路由器交换信息？交换什么信息？在什么时候交换信息？

RIP 协议的特点：

OSPF 最主要的特征是使用分布式的链路状态协议 (link state protocol)，而不是像 RIP 那样的距离向量协议。OSPF 的三个要点和 RIP 的都不一样：

除了以上的几个基本特点外，OSPF还具有下列的一些特点：

当前互联网的多级结构的网络拓扑决定了 BGP 路由选择协议的特点：

4-40 RIP 使用 UDP，OSPF 使用 IP，而 BGP 使用 TCP。这样做有何优点？为什么 RIP 周期性地和邻站交换路由信息而 BGP 却不这样做？

RIP 只和邻站交换信息，UDP 虽不保证可靠交付，但 UDP 开销小，可以满足 RIP 的要求。OSPF 使用可靠的洪泛法，并直接使用 IP，好处是灵活性好和开销更小。BGP 需要交换整个的路由表 (在开始时) 和更新信息，TCP 提供可靠交付以减少带宽的消耗。

RIP 使用不保证可靠交付的 UDP，因此必须不断地 (周期性地) 和邻站交换信息才能使路由信息及时得到更新。但 BGP 使用保证可靠交付的 TCP，因此不需要这样做。

4-41 假定网络中的路由器 B 的路由表有如下的项目：

现在 B 收到从 C 发来的路由信息：

试求出路由器 B 更新后的路由表 (详细说明每一个步骤)。

解：RIP 的距离向量算法

4-42 假定网络中的路由器 A 的路由表有如下的项目：

现在 A 收到从 C 发来的路由信息：

试求出路由器 A 更新后的路由表 (详细说明每一个步骤)。

解：RIP 的距离向量算法

【计算机网络 (谢希仁) 习题题解】目录