408研刷 408
本地资料路由算法
← 上一篇23 / 34下一篇 →
SCHEDULE LOCAL中优先级20 个小节覆盖真题 2010—2024
关联考点路由协议5路由表3距离向量算法1路由算法1做相关真题 · 9 道 →
做相关真题 · 9 道选中文字可高亮或加下划线
选中文字高亮 · 下划线

路由算法

真题练习

本节细节比较多，但是考察得比较多的还是 RIP 协议，可以把 RIP 的一些知识点多看些，然后 OSPF 和 BGP 稍微了解下。

路由

这一节我们首先通过三个问题来认识什么是 路由，接下来再在此基础上介绍 路由协议。

什么是 路由？

在一个 IP 网络中，数据包要从一个设备发送到另一个设备，中间通常需要经过多个路由器的转发。每个路由器就像是一个“交通指挥员”，决定数据包该往哪个方向走。

例如，PC-1（IP 地址为 192.168.1.5）通过如下图所示的网络向 PC-2（IP 地址为 10.1.1.5）发送数据包。当路由器 R1 接收到这些数据包时，它必须知道如何到达目标子网 10.1.1.0/24，否则将丢弃这些数据包。

R1 经 R2 到达 PC-2 所在的 10.1.1.0/24 网络

路由器 R2 知道如何到达 PC-2，因为它有一个接口位于子网 10.1.1.0/24，并在 路由表 中包含了一条直接连接路由。然而，默认情况下，路由器 R1 和 R3 不知道如何到达 10.1.1.0/24。网络管理员需要配置一条 静态路由，或者 R2 必须自动告知 R1 和 R3，它们可以将目的地为 10.1.1.0/24 的数据包发送到 R2，这种方式叫做 动态路由。

路由器 怎么知道往哪里转发？

路由器内部有一个叫 路由表 的数据结构，里面记录了各目的网络前缀对应的下一跳和出接口。当收到 IP 数据报时，路由器对目的 IP 地址进行 最长前缀匹配；若没有更具体路由，才考虑默认路由，否则丢弃并可返回 ICMP 目的不可达消息。

路由表 如何建立？

路由表 主要包含两种建立方式：

  • 静态路由

    （Static）：人工手动配置，适合小型或稳定网络。

  • 动态路由

    （Dynamic）：通过 路由协议 自动学习和更新路由信息。

静态路由和动态路由在配置、适应性与资源开销上的差异

两个 路由表 建立方式各自适用于不同的场景：

特点 静态路由 动态路由
配置方式 管理员手动配置 通过路由协议自动学习和适应
适用性 小型、稳定网络，或需要特定路由策略的情况 大型、复杂且拓扑可能变化的网络
稳定性与开销 行为可预测，几乎无协议开销 更灵活，但需要协议报文、计算和存储资源
故障恢复 默认不会自动绕过故障，需人工修改或配合跟踪机制 可检测变化并重新收敛，但恢复速度取决于协议与配置
网络变化响应 不会自动适应网络变化 收敛后自动适应变化
管理复杂性 规模小时简单，规模扩大后配置负担迅速增加 初始配置更复杂，但适合维护大量路由

路由协议

路由协议 是一种 用于路由器之间交换网络路由信息的通信规则。它的主要作用是让路由器能够自动学习和维护到达各个目的网络的路径，从而实现数据包的正确转发。

路由协议 的主要作用有两个：

  • 自动学习路由：当网络结构发生变化（如新增路由器、链路断开），路由协议 能自动更新 路由表，省去了手动配置的麻烦。
  • 选择最佳路径：如果到同一个目标有多条路径，路由协议 能根据跳数、带宽、延迟等因素计算出最优路径，提高网络效率。

路由协议 分为不同种类，各自适用于不同场景，在介绍其分类前，首先要理解计算机网络中 自治系统 的概念。

自治系统

一个 自治系统（AS，Autonomous System）是由一个或多个网络组成的集合，这些网络 在统一的管理和策略控制下运行，并对外表现为一个单一的路由实体。

互联网由多个具有统一管理和路由策略的自治系统互联组成

互联网是由无数个独立组织维护的网络组成的。每个组织内部的网络结构和路由策略不同，AS 的概念让每个组织可以作为一个独立的“区域”，既能自主控制路由，又能通过标准协议与外部沟通，保证整个互联网正常运作。

AS 通常由一个 ISP（互联网服务提供商）、大型企业、大学等拥有和运营。AS 之间通过外部 路由协议 互联，组成整个互联网。

分类

路由协议 根据其使用范围的不同，可以分为两大类：内部网关协议（IGP，Interior Gateway Protocol）和外部网关协议（EGP，Exterior Gateway Protocol）。

IGP 在自治系统内部工作，BGP 在自治系统之间交换前缀
  • 内部网关协议：在单个组织或 自治系统（AS）内部使用的路由协议，常见的 IGP 协议包括 RIP 和 OSPF。这些协议的主要作用是在一个组织的网络内部传播和更新路由信息，以实现高效的网络通信。
  • 外部网关协议：用于在不同组织或不同 自治系统 之间交换路由信息。如今，唯一广泛使用的 EGP 协议是 BGP。BGP 的设计初衷是为了控制跨组织网络之间的路由信息传递，从而实现 自治系统 之间的互联和路径控制。
RIP、OSPF 和 BGP 分别采用距离向量、链路状态和路径向量思想

对比

重点掌握 RIP、OSPF、BGP 三个协议的区别，三者的对比如下表所示：

项目 RIP OSPF BGP
协议承载 UDP 520 端口 直接封装在 IP 中，协议号 89 TCP 179 端口
作用范围 AS 内部的 IGP AS 内部的 IGP，可划分区域 AS 之间为主，也通过 iBGP 在 AS 内传播外部路由
传播方式 向邻居周期发送路由信息，并支持触发更新 LSA 在区域内可靠泛洪 在已建立的 BGP 会话间增量传递
更新内容 距离向量，典型实现周期发送路由表 本地链路状态，变化时产生新 LSA 网络前缀及 AS_PATH、NEXT_HOP 等路径属性
拓扑视图 只知经邻居到目的网络的距离与下一跳 同一区域内拥有一致 LSDB，可构建拓扑图 不构建完整物理拓扑，保留可达前缀与路径属性
核心算法或依据 Bellman-Ford 思想 Dijkstra 最短路径算法 策略优先的路径选择，不只比较距离
收敛与扩展性 收敛较慢，最大 15 跳，扩展性差 通常较快，适合中大型内部网络 面向互联网规模，策略丰富，但全局收敛可能较慢
典型场景 小型内部网络 企业、园区或运营商内部网络 运营商与跨 AS 互联

RIP

RIP（Routing Information Protocol，路由信息协议）是一种基于 距离向量 的路由协议，主要用于小型和中型网络中的 内部网关协议。

距离向量

一个典型的 距离向量（Distance Vector）可以表示为一个列表，其中每个条目包含以下信息：

  • 目的地（To）：目标网络或子网的地址。
  • 跳数/度量值（Metric）：从当前路由器到达目标网络的 代价，通常以跳数、延迟、带宽等度量标准表示。
  • 下一跳（Next Hop）：到达目标网络的 下一跳 路由器的地址。

下表是一个 距离向量示例：

目标网络 跳数 下一跳
192.168.1.0/24 0 直连（本地接口 A）
192.168.2.0/24 1 B
192.168.3.0/24 1 C

这里用距离 0 表示“当前路由器的直连网络”，便于解释 Bellman-Ford 初始化；在 RIP 对外通告中，接收邻居会把度量加 1，因此直连网络通常以度量 1 被邻居学习。

RIP 度量上限

RIP 规定可达路由的最大跳数为 15；度量值 16 表示不可达。

此外，路由器将自己的距离向量广播给其他路由器时，距离向量中的下一跳是可以省略的，因为接收者默认认为所有距离向量中的下一跳就是发送该向量的那个路由器本身。

距离向量算法

在 距离向量算法 中，通过 周期性地 与相邻路由器交换 距离向量 信息，每个路由器能够逐渐获得整个网络的拓扑信息，并更新其路由表以 选择最佳路径。

具体而言，工作流程如下：

  • 初始化：每个路由器初始化其 距离向量，只包含自己直接连接的网络，距离设为 0。
  • 周期性更新：每个路由器典型地每 30 s 向相邻路由器发送路由信息；RIPv1 使用广播，RIPv2 通常使用组播 224.0.0.9，所以不宜一概称为广播。
  • 接收和更新：每个路由器接收到相邻路由器的 距离向量 后，检查是否有新的或更短的路径。如果有，则更新自己的 距离向量 和 路由表。
  • 收敛：经过多次交换和更新后，所有路由器的 距离向量 和 路由表 最终会收敛到最优路径。
相邻路由器周期交换距离向量并逐轮收敛

最短路径计算方法

当路由器 A 收到相邻路由器 B 关于目的网络 NN 的通告时，设 B 到 NN 的距离为 DB(N)D_B(N)，A 到 B 的链路代价为 c(A,B)c(A,B)。A 经 B 到 NN 的候选距离为

DA(B)(N)=c(A,B)+DB(N).D_A^{(B)}(N)=c(A,B)+D_B(N).

RIP 中每条相邻路由器链路按 1 跳计，因此就是把 B 通告的跳数加 1。更新时要区分当前下一跳：

  • 如果 A 不存在到达网络 NN 的路由，加入这条候选路由；
  • 如果当前路由不是经 B，而候选距离更小，就改为经 B；
  • 如果当前路由本来就经 B，即使 B 通告的距离变大，也要用新值更新，否则会保留已经失效的旧度量；
  • 候选度量达到 16 时按不可达处理。
路由器把邻居通告的距离加链路代价后与现有路由比较

以上过程体现 Bellman-Ford 的递推思想：对所有邻居取最小候选值，

DA(N)=min⁡B∈N(A){c(A,B)+DB(N)}.D_A(N)=\min_{B\in\mathcal N(A)}\{c(A,B)+D_B(N)\}.

它用于求单源最短路径，即从一个结点出发到其他结点的最短路径。408 通常重在按规则更新路由表，不要求完整证明算法。

坏消息传得慢

假设一个路由器检测到它无法到达一个网络，这个信息可能需要比较长的时间才能被网络中的所有路由器感知到，这个问题也叫做 “计数到无穷”（count to infinity）问题。

举例说明：

对于以下拓扑结构：

A --- B --- C --- X

🟢 正常情况是这样：

  • C 广播：“我可以 1 跳到达 X”
  • B 收到后更新：B 到 X 跳数 = 2（通过 C）
  • A 收到后更新：A 到 X 跳数 = 3（通过 B）

🔴 C 和 X 之间的连接断开：

  • C 发现 X 不可达，设置到 X 的跳数为 16（不可达）。
  • 但 B 和 A 互相认为“另一个可能知道路径”。
  • A 说：“我能通过 B 到 X”，B 也说：“我能通过 A 到 X”，
  • 这个过程导致 跳数慢慢增加（4、5、6……），直到达到 16（不可达） 才终止。

下面的交互按轮次展示 A、B、C 到 X 的度量变化；静态数字序列保留作复习底稿，交互用于观察“错误信息怎样在邻居之间来回抬高度量”。

交互沿用候选距离 DA(B)(N)=c(A,B)+DB(N)D_A^{(B)}(N)=c(A,B)+D_B(N) 与最小化关系 DA(N)=min⁡B∈N(A){c(A,B)+DB(N)}D_A(N)=\min_{B\in\mathcal N(A)}{c(A,B)+D_B(N)}。

过程流

RIP 坏消息如何逐轮计数到无穷

在 A—B—C—X 拓扑中逐轮查看 C—X 断开后，未启用水平分割时 A、B 的旧路由怎样互相误导，直至度量达到 16。

收敛状态→链路断开链路断开→错误旧路由回流错误旧路由回流→逐轮抬高逐轮抬高→达到无穷链路断开→应用缓解机制

当前查看：收敛状态。X 与 C 直连：C、B、A 到 X 的度量分别为 1、2、3，下一跳依次为直连、C、B。

这也是 RIP 的 核心缺陷，主要由以下几个 RIP 的特性导致：

成因与缓解

  1. RIP 是距离向量协议，而不是链路状态协议
  • RIP 依靠邻居通告的目的网络与跳数，而不是让每台路由器都看到完整拓扑。
  • RIP 有周期更新和触发更新；链路断开时可把到 X 的度量通告为 16，但其他路由器仍可能在更新到达前把旧路径反向传播回来。
  1. RIP 更新基于邻居通告，不能看到完整路径是否成环

B 不知道“我从 A 学到的这条路径，实际上也是绕了一圈又回到我这里”，因为：

  • B 从 A 收到：“X 的跳数是 4”
  • B 就以为“哦，那我到 A 是 1 跳，所以我到 X 是 5 跳”
  • B 没有办法判断这条路径是否环绕回了自己！

它只根据“谁告诉我能到哪里”来加一跳数做判断，而不会检查路径是否形成了环路。

常见缓解机制包括：

  • 水平分割（split horizon）：从某接口学到的路由不再从该接口通告回去；
  • 毒性逆转（poison reverse）：向原邻居把该路由通告为度量 16；
  • 触发更新：检测到变化后立即通告，不必等下一个周期；
  • 抑制定时器：短时间内谨慎接受可疑的“更优”旧信息。

这些机制能缩小环路和计数到无穷的影响，但 RIP 仍受 15 跳上限和收敛速度限制。

OSPF

OSPF（Open Shortest Path First）是一种基于 链路状态 的 内部网关协议（IGP），广泛应用于中大型网络中。

链路状态

路由器通过 链路状态通告（LSA，Link State Advertisement）来了解其与邻居之间的链路状态。

在 RIP 路由算法中，路由器会定期将自己的 距离向量 发送给相邻的路由器。在 OSPF 中，也有类似的概念，不过这里传送的不是距离向量，而是 链路状态通告。

路由器把自身接口、邻居和链路代价等信息组织成 链路状态通告（LSA），再由 OSPF 的 Link State Update 报文承载并在区域内可靠 泛洪（flooding）。“LSP”是链路状态协议的通用说法，但 OSPF 规范中的核心对象是 LSA。

每个 LSA 专注于描述一种类型的链路状态或网络信息。一个 LSA 包含的信息通常是：

  • 路由器与某一特定链路的连接状态（如 Router LSA）。
  • 某个网络的状态和与其相连的路由器信息（如 Network LSA）。
  • 区域间或外部路由信息（如 Summary LSA 和 AS External LSA）。

链路状态数据库

链路状态数据库（LSDB，Link State Database）是 OSPF 协议中的关键组件，它存储了网络中所有 链路状态通告（LSA）。通过 LSDB，每个路由器可以构建整个网络的拓扑图，并使用 Dijkstra 算法计算最短路径树。

这里举个例子方便大家理解 LSDB 的概念。假设我们有一个简单的网络拓扑，包含 4 个路由器（R1, R2, R3, R4）和几个网络网段（NetA, NetB, NetC）。

四台 OSPF 路由器及其广播网络和点到点链路拓扑

在 链路状态算法 收敛之后，某个路由器的 LSDB 可能是如下这种形式：

LSA 类型 LSA ID 路由器 ID 链路 ID 链路类型 路径成本 相邻路由器或网络
Router 1 R1 NetA 广播链路 10 R2
Router 1 R1 NetC 广播链路 5 直连网络
Router 2 R2 NetA 广播链路 10 R1
Router 2 R2 NetB 广播链路 15 R4
Router 2 R2 R3 点到点链路 20 R3
Router 3 R3 R2 点到点链路 20 R2
Router 3 R3 R4 点到点链路 10 R4
Router 4 R4 NetB 广播链路 15 R2
Router 4 R4 R3 点到点链路 10 R3

这张表是帮助理解 LSDB 的简化表示，不是逐字段复刻真实 Router-LSA 报文。真实 OSPF 中 LSA 类型、链路状态 ID、Advertising Router 等字段有严格语义；同一区域内路由器通过 LSA 序列号和老化机制维持一致数据库。

链路状态路由算法

距离向量 算法（如 RIP）中，每个路由器只维护到各个目的网络的距离（如跳数）和 下一跳 信息，周期性地 将整个路由表发送给直接相邻的 路由器，依赖邻居的更新来调整自己的 路由表，缺乏全局视角，容易形成路由环路，收敛速度较慢，并且存在坏消息传得慢的问题。

而 链路状态 算法（如 OSPF）则由每个路由器通过 链路状态广播（LSA）将本地链路信息 泛洪 给全网，所有路由器据此构建一致的网络拓扑图，然后独立运行 Dijkstra 最短路径算法计算路由，具备 全局视角，收敛速度 快，稳定性好，适合大型复杂网络。

下图通过一个实例对比了 距离向量 和 链路状态 算法的区别：

距离向量只交换目的距离，链路状态则泛洪局部链路并各自计算全图

OSPF 还可把一个自治系统划分为多个区域。区域内维护一致的 LSDB，区域之间通过骨干区域 0 交换汇总信息，从而控制泛洪范围与计算规模。

BGP

BGP（Border Gateway Protocol，边界网关协议）是互联网的核心路由协议，用于在不同 自治系统 之间交换路由信息，属于路径向量（Path Vector）协议，目前广泛使用的版本是 BGP-4。

在 BGP 中，自治系统（AS）是互联网的基本单位，每个 AS 是一个由单个组织控制的网络集合（如一个运营商或大型企业）。AS 与 AS 之间的路由交换就是通过 BGP 完成的，AS 之内的路由交换通过 内部网关协议 完成。

BGP 原理

1. 建立 BGP 对等会话

  • 每个 AS 内部可以有多个 BGP 路由器，其中一个或多个边界路由器与其他 AS 的对等体建立 eBGP 会话；AS 内还可通过 iBGP 传播外部路由。“BGP 发言人”描述参与 BGP 会话的路由器，并不限定每个 AS 只有一个。
AS 内可有多个 BGP 发言人与外部对等体建立会话

2. 交换路径向量与属性

  • BGP 发言人之间通过 TCP 连接建立 BGP 会话，并交换路由前缀及其路径属性。
  • 每个 AS 在接收到路径信息后，可以根据自身策略决定：
    • 是否接受该路由
    • 是否将其传播给其他邻居
    • 是否作为本地的最佳路径使用
BGP 更新携带网络前缀、AS PATH 与下一跳等属性

3. 路由更新与维护

  • BGP 是 事件驱动协议，不像 RIP 周期性更新，而是在以下事件发生时才发送 UPDATE 消息：
    • 新的可达前缀出现
    • 现有前缀的属性发生变化
    • 某个前缀不再可达（发送 Withdraw 消息）

BGP 的最佳路径不等同于“跳数最少”。实现会依次考虑本地策略与多种属性，例如 LOCAL_PREF、AS_PATH、ORIGIN、MED、eBGP/iBGP 来源以及到 NEXT_HOP 的内部代价。408 复习时应先把握两点：BGP 能利用 AS_PATH 检测 AS 级环路；跨 AS 路由选择以策略为核心，而不只是求最短路。

上一篇ARP下一篇SDN