【网络协议-10】路由算法与协议简介

Demon.Lee 2022年05月12日 1,881次浏览

前面笔者对静态路由的配置进行了实操演示，而这一篇文章，笔者将对动态路由算法及相关协议做了一个梳理。

我们都知道，互联网上的计算机数以亿计量，对应的三层网络设备（如路由器）等也是不胜枚举，如果这些交换设备都通过管理员静态管理，那是不现实的。所以就有了支持动态路由配置的三层交换设备，这些设备只需要进行简单的配置（比如要交换路由信息的双方 IP 地址等），就能根据网络的变化动态生成路由表，无需人工干预。

那么这些设备之间交换路由信息的原理是什么呢？这就要说到路由控制算法了，主要有以下两种：距离矢量（Distance Vector）和链路状态（Link State）。

路由算法

计算机网络上的路由设备，如果将其进行抽象，就是一幅图，而路由策略就是找到两点之间（源主机与目的主机）的最短路径。

在计算机科学中，求解图上两点之间最短距离的算法通常有两种：Bellman-Ford 算法和 Dijkstra 算法。下面即将介绍的距离矢量路由算法基于 Bellman-Ford 算法，而链路状态路由算法则基于 Dijkstra 算法。

距离矢量路由算法

Distance Vector Routing 是根据距离和方向决定目标网络（或主机）位置的一种方法。即该算法对应的路由信息主要包括：方向（从哪个网口出去）和距离。

路由器之间可以互换目标网络的方向及其距离的相关信息，并以此为基础制作路由控制表。这里的信息互换，一般是全量的信息交换（即全局路由表），如果网络大了，带宽可能就支撑不住了，所以比较适用于小型网络（小于 15 跳）。

每当交换信息时（比如每 10 秒交换一次），每个路由器将自己所知的到达所有路由器的距离发送给邻居，然后邻居根据这些信息计算和其他路由器之间的距离。比如，A 和 B 是邻居，距离为 3，而 B 到 C 的距离是 x，那么 A 到 C 就是 x+2。

这类计算方式理解起来比较容易，但其也存在着问题。其中一个较大的问题就是当某个路由器挂掉之后，整个网络路由状态重新收敛到稳定的状态会比较慢，简而言之就是好消息传得快，坏消息传得慢。这是因为挂掉的消息不会被广播出去。路由器发现某个节点不通时，不认为它挂了，而是尝试走其他路径绕过去，直到发现所有路都不通时（或到达了超时时间），才发现真的挂了。


归其原因是路由信息中只有距离，没有路径，导致没有一个整体的网络拓扑视图，这也就有可能出现路由环路的情况。

正因如此，便有了这个算法的升级版：路径矢量路由（Path Vector Routing）算法。在这个算法里，有了路径，上面示例中的 Route B 就知道原来 Route A 是基于我计算出到 Route C 的距离的，既然我都找不到 Route C，那么它就更找不到了。

链路状态路由算法

Link State Routing 算法是在了解整个网络拓扑结构的基础上生成路由控制表的一种方法。也就是说，每个路由器都有相同的路由信息，这样一来，在任何一台机器上都能计算出到目的地的最佳路径。

路由信息更新的步骤可以简单总结为：

  • 当一个新路由器上线之后，先发现邻居（可以理解为旁边直连的路由设备）：向邻居发送消息，有回复的就是邻居；
  • 然后计算和邻居之间的距离，比如发送 ICMP 的 echo 请求（ping 命令），然后将 1 个 RTT 的耗时除以 2 得到它们之间的距离；
  • 有了这些信息之后，将自己和邻居之间的链路状态包广播出去，发送到整个网络的每个路由器；
  • 每个路由器收到信息后，将新路由器与其邻居的关系作为新的条件，更新现有的网络拓扑结构，重新构建一张新的网络图；
  • 最后，每个路由器根据这张图，重新计算出两点之间的最短距离。

这种与其他路由器交换信息，直到状态趋于稳定，所付出的代价是 CPU 算力以及内存存储。但是互联网上的路由信息太多了，如果一台路由器要掌握所有规则，就相当于一台超级计算机了，所以该算法适用于在局域网内使用。

与距离矢量路由算法相比，链路状态路由算法也有优点。在路由信息变化时，只需要将变化的信息同步即可，这就节省了带宽，提高了 CPU 利用率。当一个路由节点挂掉之后，其周边节点会将信息广播出去，就像八卦新闻一样，这样大家就都知道这个节点挂了，后续便能让数据包绕过这台设备。而距离矢量路由算法因为每台路由器掌握的信息不同，故无法知晓其中的路由信息是否已经失效了，只能等到数据包经过时才能验证。

另外，该算法还有一个好处就是可以检测出网络环路，毕竟掌握了所有的路由信息，从节点 A 出发的数据包，转了一圈又回到了节点 A，是可以计算出来的。

路由协议

上面对基本的路由算法进行了简单的概述，基于这些理论，工程师们开发出了各类路由协议，如下所示：

路由协议名 下一层协议 方式 适用范围 循环检测
RIP UDP 距离矢量 域内 否
RIP2 UDP 距离矢量 域内 否
OSPF IP 链路状态 域内 是
BGP TCP 路径矢量 对外连接 是

在网络路由概述这篇文章中，笔者曾对下面这张图进行了说明：

  • EGP 与 IGP 是根据路由控制范围进行区分的两类协议，AS 内部用 IGP（内部网关协议），AS 之间用 EGP（外部网关协议）。二者都是不可或缺的，少了 EGP，世界上各个不同的组织机构就无法通信，少了 IGP，机构内部也无法通信。
  • 属于 EGP 的协议有：BGP（Border Gateway Protocol，边界网关协议）；属于 IGP 的协议有：RIP（Routing Information Protocol，路由信息协议），RIP2，OSPF（Open Shortest Path First，开放式最短路径优先）等。


下面笔者就对其中的几个主要路由协议逐个分析。

RIP

RIP（Routing Information Protocol）是一种距离矢量型的路由协议，广泛用于 LAN。

RIP 通过广播的方式定期（每 30 秒一次）将路由控制信息（即前面提到的距离和方向）向全网广播。如果某个路由器没有收到邻居的路由控制信息，当等待 5 次（共 6 次，即 180 秒）后仍然没有消息，会关闭连接。

RIP 中的距离用跳数（hop）来表示，即经过的路由器数量。如果经过的路由器数量越少，RIP 就认为该路径更优。如果路由器数量相同，一般会随机选择或轮换使用。

下图引用自《图解TCP/IP（第5版）》：


前面在介绍距离矢量路由算法时，提到了因某个链路断掉之后，会出现不断循环绕路的问题，直到最终超时。这个问题其实是因为对应的路由节点又收到了自己发送出去的信息（Route B 将自己到 Route C 的距离为 x 的消息发给 Route A 后，Route A 又将该消息重新发给了 Route B，即 Route A 到 Route C 的距离为 x+2 ），所以又被称为无限计数（Counting to Infinity）。

解决该问题一般有两个方法：一是前面提到的超时，最长距离不超过 16 ，一般为 120 秒，超过这个时间就无法发送；二是规定路由器不能将自己收到的路由消息再原路发给发送方，这也被称为水平分割（Split Horizon）。

但是第二种水平分割的方案也无法解决网络本身就存在环路的情况，发出去的路由消息最终会通过反向的回路再迂回到发送方，消息不断被循环往复地转发。


所以，在此基础上，人们又提出了两个解决方案：毒性逆转（Poisoned Reverse）和触发更新（Triggered Update）。简单来说，毒性逆转是指当网络链路故障时，不能静默不管，而是扩散这个坏消息，发送一个距离为 16 的广播消息，这样大家就都知道路径有问题了。触发更新则要求路由器在路由消息变化时，不等待 30 秒而立刻发送出去。

RIP规定距离值取 0~15 之间的整数，大于或等于 16 的跳数被定义为无穷大。

有了这两个方案，不管是好消息还是坏消息就都能快速传播，让整个网络内的路由信息更快地收敛。

RIP 中使用了多个定时器[1]来实现路由控制信息的交换，主要有以下 3 个：

  • 更新定时器（Update Timer）：默认每隔 30 秒交换一次路由控制信息，即路由器将自己的路由信息广播给其他邻居。
  • 无效定时器（Invalid Timer）：如果路由表中某条路由信息长期未被更新（默认 180 秒），那么这条路由信息将被置为无效路由，并将到该网段的距离设置为 16。
  • 垃圾收集定时器（Flush Timer）[2]：定义了多长时间后，未被更新的路由信息会被删除，默认为 240 秒（不同的版本可能会有差异）。需要注意的是，该定时器会与无效定时器一起运行，所以这里定义的超时时间需要大于无效定时器的超时时间。这里按默认值计算，240 - 180 = 60 ，也就是说当无效定时器处理结束后，再过 60 秒会将对应的路由信息删除。


但我们也发现，RIP 解决问题的思路是不断地打补丁，哪里不好就往哪里贴一个创可贴。所以人们在 RIP 的基础上进行了改良，发布了第二版，即 RIP2。

RIP2 与 RIP 的工作机制基本相同，但有以下几个新的改动：

  • 使用多播而不是 RIP 中的广播来交换路由信息，这样可以减少部分网络流量，提高带宽利用率。
  • 与 OSPF 类似，支持在路由信息中加入子网掩码信息，支持路由聚合和 CIDR。
  • 与 OSPF 中的区域类似，一个网络中可以使用逻辑独立的多个 RIP。
  • 支援外部路由标记（Route Tag），可以在路由策略中根据 Tag 对路由进行灵活的控制。通常用于从 BGP 等获得的路由控制信息通过 RIP 传递到一个 AS 内部。
  • 支持密码校验，用于识别身份。RIP 包中携带密码，只有在自己能够识别这个密码时才接收数据，否则丢弃该数据包。

OSPF

OSPF（Open Shortest Path First，开放式最短路径优先）是一个基于链路状态路由算法实现的，被广泛用于数据中心内部的协议，其根据 OSI 的 IS-IS（Intermediate system to intermediate system，中间系统到中间系统）协议[3]而提出。

根据前面对链路状态路由算法的描述，我们知道路由器之间通过交换链路状态生成网络拓扑信息，然后再根据这个拓扑信息生成路由控制表。所以，网络内每个路由器都有一份整个网络的拓扑结构。

与前面介绍的 RIP 选择最少路由器个数的路径不同，OSPF 选择权重最小的路径作为路由线路。那么问题来了，如何计算权重呢？答案是 OSPF 通过给每条链路赋予一个权重（或者叫代价、开销），计算出两点之间满足条件的各条线路的开销，最后再选择一条代价最小的线路进行路由。OSPF 中的代价是根据带宽来计算的，带宽越高，代价就越低。下图来自《图解TCP/IP（第5版）》，笔者对其进行了重新绘制：


有些时候，最短路径往往不止一条，这个时候就可以在多条路径中进行负载均衡，又称为等价路由。

根据上面这幅图，笔者简单梳理一下路由信息交换的基本流程。与 RIP 中只有一种网络包类型（利用路由控制信息，一边确认是否连接了网络，一边传送网络信息）相比，OSPF 有 5 种包类型，如下表所示：

消息类型 消息名称 作用
1 Hello：问候 确认相邻路由器、确定指定路由器
2 Database Description：数据库描述 链路状态数据库的摘要信息
3 Link State Request：链路状态请求 请求从数据库中获取链路状态信息
4 Link State Update：链路状态更新 更新链路状态数据库中的链路状态信息
5 Link State Acknowledgement：链路状态确认应答 链路状态信息更新的确认应答

假设图中的 Route B 第一次上线，那么 OSPF 协议的工作过程大致是下面这样的：
1）生成邻居表：Route B 每隔 10 秒就发送一个 Hello 数据包，通过发送 Hello 数据包得知哪些相邻的路由器在工作（比如这里的 Route A），并记录发送相邻路由器所需的“代价”，生成邻居表。
2）建立链路状态表：有了邻居表，相邻路由器之间就要交换链路状态，有以下几步：

  • 交换状态：各个路由器与其相邻路由器之间使用 Database Description 交换各自拥有的链路状态摘要信息，比如 Route A 和 Route B 之间；
  • 加载状态：有了其他路由器发送过来的摘要信息，与本地信息进行对比，发现缺失（或过期），Route B 便发起 Link State Request（LSR）数据包给 Route A。接着，Route A 发送 Link State Update（LSU）数据包，一般是通过泛洪的方式发送给它所有的邻接路由器。Route B 收到 Route A 发送的更新包后，会回复一个 Link State Acknowledgement（LSA）数据包。在 OSPF 协议中只有 LSU 需要显示回复确认包。
  • 完全邻接状态：邻居间的链路状态数据库同步完成。

3）生成路由表：每个路由器根据上面步骤建立全局链路状态表后，依据对应的最小路径算法，计算出两两节点之间的路由条目，并生成对应的路由表。

下图为上面流程的时序图，来自《深入浅出计算机网络》，笔者对其进行了重新绘制：


每当某个路由器的链路状态发生变化，该路由器就要使用 LSU 数据包进行泛洪广播，将变化的路由状态进行全网更新。

另外，在 OSPF 协议中还有一个区域的概念。之所以引入区域的概念，是因为当网络规模越来越大时，全局的链路状态表会越来越大，由此依据最短路径优先算法计算出路由控制表所耗费的 CPU 和内存会不断增加，时间不断变长。

而将一个自治系统（Autonomous System, AS）内部划分为多个区域后，每个区域都只持有本区域内的网络拓扑数据库。以下为一个 AS 划分多个区域的示意图：


划分区域其实就是分而治之的思路，但在 AS 之内需要有一个主干区域（Backbone Area），并且所有其他区域必须与这个主干区域相连接。当然，一个区域不能划分的太大，一般来说一个区域内的路由器不超过 200 个。

根据路由器所在区域的不同，其发挥的作用也不同，总结下来有以下几类：

  • 主干路由器：只在主干区域内连接
  • AS 边界路由器：与 AS 外部连接
  • 内部路由器：只在区域内部连接
  • 区域边界路由器：连接区域与主干区域

区域内的路由器相互交换信息，但不会与区域外部的路由器交换信息，如果需要与区域之外进行交互，只能通过区域边界路由器来获取对应的路径。而区域边界路由器也不会将区域内部的链路状态信息原样发给其他区域，只会发送自己到它们的距离。前面提到，同步链路状态信息是通过泛洪的方式广播的，如今划分区域后，广播的范围大大减小，网络线路上的带宽使用率自然也就提高了。

另外，如果某个区域的出口只有一个区域边界路由器，该区域又称为末端区域。因为只有一个区域边界路由器，这就意味着发送数据包到外部只有一条路可走（相当于默认网关），故区域内路由器也就没必要了解到达其他各个网络的距离，从而减少了一定的路由信息。

需要补充的是，使用多区域划分需要与 IP 地址的划分相结合才行，因为这样才能通过路由汇总将多个区域的路由合并成一条路由信息通知到主干网络。

BGP

在前面的“路由协议”部分提到了 AS，EGP，IGP 等，也提到属于 EGP （Exterior Gateway Protocol，外部网关协议）的协议有 BGP（Border Gateway Protocol，边界网关协议）。从图中我们也能看出来，BGP 中的“边界”其实指的就是不同 AS 之间的连接。

为什么要划分 AS 呢？个人理解有两个原因：一是因为网络不是由一家运营商提供的（比如我们国家三大基础运营商：移动、联通和电信），每家运营商内部如何实现网络的接入、配置、分发以及计费等都有差异，所以从物理上这些网络本身就是隔离的；二是为了管理方便，前面 OSPF 中就有区域的概念，而我们这里 AS 可以简单理解成一个大的网络区域，在 AS 内部可以自己决定如何运营网络并制定相关管理政策以及具体执行流程。

ISP、区域网络等会将每个网络域编成一个个 AS 进行管理，每个 AS 都有一个编号，又称为 ASN，而 BGP 协议正是根据这些 AS 编号进行相应的路由控制。以下为网络上[4]查询到的我们国家相关机构申请的部分 AS 信息：


在国内，AS 可以向 CNNIC（中国互联网络中心）[5]申请并每年向其缴纳管理使用费用。


不同的 AS 有不同的管理策略，有的 AS 内部只能让外部数据包进，但不能出，有的可以帮忙转发数据包到其他 AS 。根据自治系统的不同，可以分为以下几类：

  • Stub AS：对外只有一个连接，它不会传输其他 AS 的包，比如个人或小公司的网络。
  • Multihomed AS：可能与其他多个 AS 相连，但一般不会帮其他 AS 传输数据包，比如某些大公司网络。
  • Transit AS：有多个连接与其他 AS 相连，并能帮助其他 AS 传输数据包，比如主干网，当然这中间会涉及到中转费用。

每个 AS 之间都会有边界路由器，又称为 BGP 扬声器，通过它与外部进行数据交换。而 AS 内部各个子网也需要了解外部网络的情况，才能知道走哪个边界路由器可以最快抵达目的地，这就要求边界路由器通过 BGP 学习到的路由同步到 AS 内部。因此，BGP 又可以继续划分为 eBGP（external BGP）和 iBGP（internal BGP），其中 eBGP 负责 AS 之间的 BGP 路由控制信息交换，而 iBGP 负责 AS 内部的 BGP 路由控制信息交换。


路由路径选择时，RIP 使用跳数最少（即路由器个数最少），OSPF 选择成本最小（网络带宽大），而 BGP 一般选择 AS 数最少的路径。当然，这里的 AS 数最少只是一个高层次上的统一描述，因为 AS 之间的数据传输，需要按照它们之间签订的合约进行转发，这中间可能有更细粒度的路由选择。


前面提到，BGP 是建立在 TCP 之上的路径矢量路由协议，这里的路径体现在数据包通过 BGP 协议传送到目的主机后，会生成一条中途经过所有 AS 的编号列表，又称为 AS 路径信息访问列表（AS Path List）。即 AS Path List 包含转发距离，方向以及中途经过的 AS 编号。

今天的服务端编程，经常被提及的一个词是分布式系统，面对海量的互联网用户，大厂们基本上都会使用分布式系统来解决高可用、高性能以及可扩展的问题。如果与其进行类比，那么分布在互联网上的海量路由器设备则天然构成了一个分布式系统，而在其中发挥举足轻重作用的则是一个个路由协议，是它们保证了路由信息的准确，从而让一个个数据包快速找到目的地。

MPLS

最后，我们简单提及一下 MPLS 协议。

MPLS 全称为 Multiprotocol Label Switching，即多协议标记交换技术。路由技术基于 IP 地址中的最长匹配原则进行数据包转发，MPLS 不使用 IP 地址，而使用标记交换技术，即对每个数据包都打一个 tag，然后根据这个 tag 进行转发。

以下是维基百科上的定义：

Multiprotocol Label Switching (MPLS) is a routing technique in telecommunications networks that directs data from one node to the next based on labels rather than network addresses.Whereas network addresses identify endpoints the labels identify established paths between endpoints. MPLS can encapsulate packets of various network protocols, hence the multiprotocol component of the name. MPLS supports a range of access technologies, including T1/E1, ATM, Frame Relay, and DSL.

从定义上，我们可以了解到：多协议的含义是指 MPLS 不但可以支持多种网络层层面上的协议，还可以兼容第二层的多种数据链路层技术，包括T1/E1，ATM，帧中继和DSL。


上图为两种路由方式的对比，在 MPLS 标记路由示意图中，我们可以看到这里的路由器与普通的路由器有些不同（个人理解是其中安装的软件不同，即支持 MPLS）。在 MPLS 网络中实现 MPLS 功能的路由器称为标记交换路由器（LSR），而与外部网络连接的那部分 LSR 又称为标记边缘路由器（LER）。

在 LSR 上有三种操作，分别是：

  • 添加标记：push
  • 替换标记：swap
  • 删除标记：pop

这里对标记的操作，其实就是额外插入一个 header，以以太网数据链路为例，它会插在 IP 头和以太网首部之间（有些书中总结 MPLS 工作在 2.5 层），如下图所示：


从图上可知，该头部占用 32 bit（即 4 bytes），其中标记值占用 20 bit[6]。需要补充说明的是，MPLS 头部中可以添加多个标记。

类比 IP 路由表，MPLS 也有一个标记表，只不过这个表中的 key 为标记值，而 value 为对应的网卡出口。一个 LSR 收到数据包之后，会从数据包提取对应的标记值，并根据它查找标记表。在数据包被转发之前，旧的标记被从包头中删除，并用新的标记取代。

那么问题来了，这些 LSR 中的标记表是如何构建起来的？简单来说有两种方式，一种是各个 LSR 向邻接 LSR 分配 MPLS 标记，又称为 LDP（Label Distribution Protocol，标记分配协议），另一种则是通过路由协议载着标记信息进行交换。

从上面的描述中，可以了解到 MPLS 技术一个最大的优势是速度快。因为 IP 路由需要根据最长匹配原则进行计算，而 MPLS 用一个标记值直接查找路由，处理简单，速度更快。另外一个优势是可以利用标记生成一条虚拟路径，在此之上就能实现 IP 等数据包的通信。由于 MPLS 首部包含了 QoS 等内容，因而在 IP 网络之上也可以实现通信质量控制、带宽保证和 VPN 等功能。

总结

从路由算法到各类路由协议，从 AS 到 BGP，可以看到整个网络大厦是如此的宏伟和复杂。笔者还是一个初学者，对很多细节内容也不清楚，这里对相关内容进行梳理，主要还是想对路由协议有一个宏观层面的整体认识。针对具体某一种网络协议，待某个场景需要使用时，笔者将再进行深入的分析，比如查阅这类协议的源码等。

参考资料

  1. 参考 https://en.wikipedia.org/wiki/Routing_Information_Protocol 和 https://zh.wikipedia.org/zh-cn/路由信息协议 ↩︎

  2. http://www.routeralley.com/guides/rip.pdf ↩︎

  3. 参考 https://zh.m.wikipedia.org/zh-cn/中间系统到中间系统 和 https://en.wikipedia.org/wiki/IS-IS ↩︎

  4. http://as.chacuo.net/CN ↩︎

  5. http://www.cnnic.cn/ ↩︎

  6. https://en.wikipedia.org/wiki/Multiprotocol_Label_Switching#Operation ↩︎

上一篇： 漫画计算机原理