鲤鱼笔记

路由选择协议

2022-12-17 计算机网络 网络层

# 一、路由选择分类

# 二、因特网采用分层次的路由选择协议

因特网是全球最大的互联网，它所采取的路由选择协议具有以下三个主要特点：

  1. 自适应：因特网采用动态路由选择，能较好地适应网络状态的变化。
  2. 分布式：因特网中的各路由器通过相互间的信息交互，共同完成路由信息的获取和更新。
  3. 分层次：将整个因特网划分为许多较小的自治系统（Autonomous System，AS），在自治系统内部和外部采用不同类别的路由选择协议，分别进行路由选择。

# 2.1 域间路由选择和域内路由选择

# 2.2 外部网关协议 EGP 和内部网关协议 IGP

注意

  • 外部网关协议 EGP 和内部网关协议 IGP 只是路由选择协议的分类名称，而不是具体的路由选择协议。
  • 使用 “网关” 这个名词是因为在早期的 RFC 文档中，没有使用 “路由器” 而使用的是 “网关” 这一名词。

# 三、路由信息协议 RIP

路由信息协议（Routing Information Protocol，RIP）[RFC 1058] (opens new window) 是内部网关协议中最先得到广泛使用的协议之一。

# 3.1 RIP 的相关基本概念

RIP 距离

RIP 要求自治系统 AS 内的每一个路由器，都要维护从它自己到 AS 内其他每一个网络的距离记录。这是一组距离，称为距离向量（Distance-Vector，D-V）。

RIP使用跳数（Hop Count）作为度量（Metric）来衡量到达目的网络的距离。

  • RIP 将路由器到直连网络的距离定义为 1。
  • RIP 将路由器到非直连网络的距离定义为所经过的路由器数加 1。
  • RIP 允许一条路径最多只能包含 15 个路由器，距离等于 16 时相当于不可达。因此 RIP 只适用于小型互联网。

RIP 判断好路由的标准

RIP 认为好的路由就是 “距离短” 的路由，也就是所通过路由器数量最少的路由。

当到达同一目的网络有多条 RIP 距离相等的路由时，可以进行等价负载均衡，也就是将通信量均衡地分布到多条等价的路径上。

RIP 的三个重要特点

  • 和谁交换信息：仅和相邻路由器交换信息。
  • 交换什么信息：路由器自己的路由表。
  • 何时交换信息：周期性交换 + 触发更新。

# 3.2 RIP 的基本工作过程

  1. 路由器刚开始工作时，只知道自己到直连网络的 RIP 距离为 1。
  2. 每个路由器仅和相邻路由器周期性地交换并更新路由信息。
  3. 若干次交换和更新后，每个路由器都知道到达本自治系统 AS 内各网络的最短距离和下一跳路由器，称为收敛。

# 3.3 RIP 的距离向量算法

  1. 给相邻路由器发送封装有自己所知路由信息的 RIP 更新报文。
  2. 修改来自邻居路由器的路由信息。
  3. 基于修改好的来自邻居路由器的路由信息更新自己的路由表。

下面来举例说明，假设某一时刻，路由器 C 将自己的路由表封装在 RIP 更新报文中发送给路由器 D。

除了上述 RIP 路由条目更新规则，在 RIP 的距离向量算法中还包含以下一些时间参数：

  • 路由器每隔大约 30 秒向其所有相邻路由器发送路由更新报文。
  • 若 180 秒（默认）没有收到某条路由条目的更新报文，则把该路由条目标记为无效（即把 RIP 距离设置为 16，表示不可达），若再过一段时间（如 120 秒），还没有收到该路由条目的更新报文，则将该路由条目从路由表中删除。

# 3.4 RTP 存在的问题

RIP 存在 “坏消息传播得慢” 的问题，借助下图理解。

“坏消息传播得慢” 的问题又被称为路由环路或 RIP 距离无穷计数问题。这是距离向量算法的一个固有问题，可以采取以下多种措施减少出现该问题的概率或减小该问题带来的危害。

  • 限制最大 RIP 距离 为 15（16 表示不可达）。
  • 当路由表发生变化时就立即发送路由更新报文（即 “触发更新”），而不仅是周期性发送。
  • 让路由器记录收到某个特定路由信息的接口，而不让同一路由信息再通过此接口向反方向传送（即 “水平分割”）。

注意

使用上述措施仍无法彻底解决问题。因为在距离向量算法中，每个路由器都缺少到目的网络整个路径的完整信息，无法判断所选的路由是否出现了环路。

# 3.5 RIP 版本和相关报文的封装

现在较新的 RIP 版本是 1998 年 11 月公布的 RIP2 [RFC 2453] (opens new window)，已经成为因特网标准协议。与 RIP1 相比，RIP2 可以支持变长子网掩码和 CIDR；另外，RIP2 还提供简单的鉴别过程并支持多播。

RIP 相关报文使用运输层的用户数据报协议 UDP 进行封装，使用的 UDP 端口号为 520。

  • 从 RIP 报文封装的角度看，RIP 属于 TCP/IP 体系结构的应用层。
  • 但 RIP 的核心功能是路由选择，这属于 TCP/IP 体系结构的网际层。

# 3.6 RIP 的优缺点

优点

  • 实现简单，路由器开销小。
  • 如果一个路由器发现了 RIP 距离更短的路由，那么这种更新信息就传播得很快，即 “好消息传播得快”。

缺点

  • RIP 限制了最大 RIP 距离为 15，这就限制了使用 RIP 的自治系统 AS 的规模。
  • 相邻路由器之间交换的路由信息是路由器中的完整路由表，因而随着网络规模的扩大，开销也随之增大。
  • “坏消息传播得慢”，使更新过程的收敛时间过长。因此，对于规模较大的自治系统 AS，应当使用 OSPF 协议。

# 四、开放最短路径优先 OSPF

开放最短路径优先（Open Shortest Path First，OSPF）协议是为了克服路由信息协议 RIP 的缺点在 1989 年开发出来的。

  • “开放” 表明 OSPF 协议不是受某一厂商控制，而是公开发表的。
  • “最短路径优先” 是因为使用了 Dijkstra 提出的最短路径算法。

# 4.1 OSPF 的相关基本概念

链路状态 LS

链路状态（Link State，LS）是指本路由器和哪些路由器相邻，以及相应链路的 “代价（cost）”。

“代价” 用来表示费用、距离、时延和带宽等，这些都由网络管理人员来决定。

邻居关系的建立和维护

OSPF 相邻路由器之间通过交互问候（Hello）分组来建立和维护邻居关系。

  • 问候分组封装在 IP 数据报中，IP 数据报首部的协议号字段取值为 89，表明 IP 数据报的数据载荷为 OSPF 分组。
  • 问候分组的发送周期为 10 秒。
  • 若 40 秒未收到来自邻居路由器的问候分组，则认为邻居路由器不可达。
  • 每个路由器都会建立一张邻居表。

链路状态通告 LSA

使用 OSPF 的每个路由器都会产生链路状态通告（Link State Advertisement，LSA）。

LSA 包含以下两类链路状态信息：

  • 直连网络的链路状态信息。
  • 邻居路由器的链路状态信息。

链路状态更新分组 LSU

LSA 被封装在链路状态更新分组（Link State Update，LSU）中，采用洪泛法（Flooding）发送。

链路状态数据库 LSDB

使用 OSPF 的每个路由器都有一个链路状态数据库（Link State Database，LSDB），用于存储 LSA。

通过各路由器洪泛发送封装有各自 LSA 的 LSU，各路由器的 LSDB 最终将达到一致。

基于 LSDB 进行最短路径优先计算

使用 OSPF 的各路由器，基于链路状态数据库 LSDB 进行最短路径优先计算，构建出各自到达其他各路由器的最短路径，即构建各自的路由表，如下图所示。

# 4.2 OSPF 的五种分组类型

# 4.3 OSPF 的基本工作过程

  1. R1 与 R2 之间每隔 10 秒交换一次 问候分组，以便建立和维护邻居关系。
  2. 建立邻居关系后，给邻居路由器发送 数据库描述分组。也就是将自己的链路状态数据库的所有链路状态项目的摘要信息发送给邻居路由器。
  3. 假设 R1 收到 R2 的数据库描述分组后，发现自己缺少其中某些链路状态项目，会给 R2 发送 链路状态请求分组。
  4. R2 收到 R1 发来的链路状态请求分组后，将 R1 缺少的链路状态项目的详细信息，封装在 链路状态更新分组 中，发送给 R1。
  5. R1 收到 R2 发来的链路状态更新分组后，将这些缺少的链路状态项目的详细信息添加到自己的链路状态数据库中，并向 R2 发送 链路状态确认分组。

经过上述过程，所有路由器的链路状态数据库会达成一致。每隔 30 分钟或链路状态发生变化时，路由器都会洪泛发送链路状态更新分组。

# 4.4 多点接入网络中的 OSPF 路由器

在多点接入网络中，如果不采用其他机制，OSPF 会产生大量的多播分组（即问候分组和链路状态更新分组），如下图所示。

为了减少所发送分组的数量，OSPF 采用选举指定路由器（Designated Router，DR）和备用的指定路由器（Backup Designated Router，BDR）的方法。所有的普通路由器只与 DR 或 BDR 建立邻居关系，如下图所示。

# 4.5 OSPF 划分区域

为了使 OSPF 协议能够用于规模很大的网络，OSPF 把一个自治系统 AS 再划分为若干个更小的范围，称为区域（area）。

划分区域的好处就是把利用洪泛法交换链路状态信息的范围局限于每一个区域，而不是整个自治系统 AS，这样就 减少了整个网络上的通信量。

区域内路由器

如果路由器的所有接口都在同一个区域内，则该路由器称为区域内路由器（Internal Router，IR）。

见：上图中区域 1 内的 R1 和 R2，区域 2 内的 R8，区域 3 内的 R9。

区域边界路由器

为了本区域可以和自治系统内的其他区域连通，每个区域都会有一个区域边界路由器（Area Border Router，ABR）。区域边界路由器的一个接口用于连接自身所在区域，另一个接口用于连接主干区域。

见：上图中的 R3、R4 和 R7。

主干路由器

主干区域内的路由器称为主干路由器（Backbone Router，BBR），也可以把区域边界路由器看作主干路由器。

见：上图中的 R3、R4、R5、R6 和 R7。

自治系统边界路由器

在主干区域内还要有一个路由器专门和本自治系统外的其他自治系统交换路由信息，这样的路由器称为自治系统边界路由器（AS Border Router，ASBR）。

见：上图中的 R6。

# 五、边界网关协议 BGP

边界网关协议（Border Gateway Protocol，BGP）属于外部网关协议 EGP 这个类别，用于自治系统 AS 之间的路由选择协议。

# 5.1 BGP 的相关基本概念

使用 BGP 寻找最佳路由是无意义的

由于在不同 AS 内度量路由的 “代价”（距离、带宽、费用等）可能不同，因此对于 AS 之间的路由选择，使用统一的 “代价” 作为度量来寻找最佳路由是不行的。

而且 AS 之间的路由选择还必须考虑相关策略（政治、经济、安全等），它们都是由网络管理人员对每一个路由器进行设置的，但这些策略并不是自治系统之间的路由选择协议本身。

BGP 边界路由器

在配置 BGP 时，每个 AS 的管理员要选择至少一个路由器作为该 AS 的 “BGP发言人”。一般来说，两个 BGP 发言人都是通过一个共享网络连接在一起的，而 BGP 发言人往往就是 BGP 边界路由器，如下图所示。

使用 TCP 连接交换路由信息的两个 BGP 发言人，彼此称为对方的邻站（neighbor）或对等站（peer）。BGP 发言人除了运行 BGP 协议外，还必须运行自己所在 AS 所使用的内部网关协议 IGP，例如 RIP 或 OSPF。

BGP 发言人交换网络可达性的信息，也就是要到达某个网络所要经过的一系列自治系统。当 BGP 发言人相互交换了网络可达性的信息后，各 BGP 发言人就根据所采用的策略，从收到的路由信息中找出到达各自治系统的较好的路由，也就是构造出树形结构且不存在环路的自治系统连通图，如下图所示。

BGP 适用于多级结构的因特网

# 5.2 BGP-4 的四种报文

BGP-4 是目前使用最多的版本，在 [RFC 4271] (opens new window) 中规定了 BGP-4 的四种报文。

# 六、路由器的基本工作原理

路由器是一种具有多个输入端口和输出端口的专用计算机，其任务是 转发分组。

下图给出了一种典型路由器的基本结构框图，整个路由器结构可划分为两大部分：

  • 路由选择部分：核心构件是路由选择处理机，其任务是根据所使用的路由选择协议，周期性地与其他路由器进行路由信息的交换，以便构建和更新路由表。
  • 分组转发部分：由一组输入端口、交换结构以及一组输出端口构成。

# 七、参考资料

Last Updated: 2023-01-28 4:31:25

网际控制报文协议 ICMP