前言

在IP路由中,我们学到路由可以分为直连路由、静态路由与动态路由。同时简单的介绍了一下动态路由的一些协议,这一篇专注于详细介绍动态路由中的相关协议。


动态路由协议

对于路由协议,我们先来看看路由协议和我们学过的网络层协议的区别。

主动路由协议 (Routing protocols) 是路由器之间使用的通信协议,允许一台路由器与其他路由器共享路由信息。路由器使用该信息来构建和维护它们自己的路由表。

一些路由协议示例:

  • 路由信息协议RIP, Routing Information Protocol)
  • 开放最短路径优先协议OSPF, Open Shortest Path First)
  • 增强型内部网关路由协议EIGRP, Enhanced Interior Gateway Routing Protocol)

相反,被动路由协议 (Routed protocols) 在其网络层地址中提供足够的信息,以允许根据寻址方案将数据包从一台主机转发到另一台主机。例如:IP协议

此外我们还需要了解一个范围——AS(Autonomous System,自治系统),表示属于某个组织或专有的一组广播域的集合。AS将全球互联网划分为更小、更易管理的网络。由图,是一个由多个广播域组成的一个AS。

我们根据主动路由协议的范围,可以进一步划分为:

  • IGP(Interior Gateway Protocols,内部网关协议)用于在一个自治系统中路由数据。IGP的例子有RIP, EIGRP, OSPF, IS-IS等。
  • EGP(Exterior Gateway Protocols,外部网关协议)用于在自治系统之间路由数据。例如BGP。

不同的路由协议具有不同的算法,每种路由协议的设计目标都是:

  • 优化(Optimization):路由算法应该选择最佳路由。
  • 简单和低开销(Simplicity and low overhead):算法越简单,路由器中的CPU和内存处理它的效率就越高。
  • 稳定性与灵活性(Stability and Flexibility):路由算法应具有稳定性,并能快速适应各种网络变化。
  • 快速收敛(Rapid convergence):能快速使得网络上每个设备对网络(拓扑)的认识是一致的。

路由算法大多可以分为三类:

  • 距离矢量路由(Distance vector):不需要整个网络的拓扑,设备的去向由邻居决定。又称为Bellman-Ford算法,例如有RIP, IGRP
  • 链路状态路由(Link-state):需要知道整个网络的拓扑,使用最短路径优先算法或Dijkstras算法路由。例如有OSPF
  • 混合路由(Balanced-Hybrid):基于上述两种算法的其中一种,并具有另一种算法的一些特征。例如有EIGRP, IS-IS

接下来我们分别分析这三类路由算法的原理。


距离矢量路由协议

距离矢量路由协议指的是基于距离矢量的路由协议,运行距离矢量路由协议的路由器周期性的泛洪(flooding, 可以看做是一种broadcast)自己的路由表。通过路由的交互,每台路由器都从相邻的路由器学习到路由,并且加载进自己的路由表中。

我们把这样的泛洪算法称为Bellman-Ford algorithms。接下来根据一个例子来理解这个过程。

设目的主机位A,算法一般从目的主机开始泛洪。用红色表示最佳路径的距离。

第一次泛洪,由A开始,泛洪B和C。B和C到目的主机的距离分别为7和3,此时它们都是最佳路径。

From \ To B C D E F
A 7 3
Via A A

第二次泛洪,泛洪上一次中新更新的设备。路由器B泛洪到其邻居路由器C和D,同时路由器C泛洪到其邻居路由器B、D和E。

我们发现,在泛洪C的时候重新更新了B的距离,这可能导致B之前的记录也需要被更新,B需要进行重新泛洪(reflooding)。

From \ To B C D E F
A 7 3
B   9 12
C 5 7 11
B(re) 7 10
Via C A C C

第三次泛洪,泛洪新更新的路由器D和E。路由器D泛洪到其邻居B、C、E和F。同时,路由器E到其邻居路由器C、D和F。

E因为被D更新了,需要进行重新泛洪。

From \ To B C D E F
A 7 3
B   9 12
C 5 7 11
B(re) 7 10
D 12 11 10 11
E 19 14 17
E(re) 18 13 16
Via C A C D D

第四次泛洪,最后只有F为新更新的,F洪泛到其邻居路由器D和E。

From \ To B C D E F
A 7 3
B   9 12
C 5 7 11
B(re) 7 10
D 12 11 10 11
E 19 14 17
E(re) 18 13 16
F 15 17
Via C A C D D

此后,再无新更新的节点,算法结束,得到了整个网络中所有路由器到路由器A的最佳路径。从所有其他路由器到路由器A的最佳路径:

  • 从B到A,经过C,距离为5;
  • 从C到A,经过A,距离为3;
  • 从D到A,经过C,距离为7;
  • 从E到A,经过D,距离为10;
  • 从F到A,经过D,距离是11。

距离矢量路由协议定期或在网络拓扑发生变化时转发其整个路由表。收敛(Convergence)是路由表信息被转发到邻居路由器,邻居路由器继续将信息转发到它们的邻居的过程。

如果网络收敛缓慢(因为泛洪导致几乎n2次操作)导致路由条目不一致,则会出现路由环路,数据包可能不断在环路中循环。它的跳数(hops)会变成无限大,这种情况称为计数到无穷大(Count to infinity)。

为了解决这些问题,我们有如下解决方案:

  • 定义最大度量(Defining a maximum metric)
  • 水平分割(Split horizon)
  • 路由毒化(Route poisoning)
  • 触发更新(Triggered updates)
  • 按住计时器(Hold down timers)

其中,定义最大度量是最简单的方法。路由协议允许路由环路继续,直到度量超过其最大允许值。保证了不会一直循环下去。


EIGRP

增强型内部网关路由协议EIGRP, Enhanced Interior Gateway Routing Protocol)曾是Cisco专有的路由协议,现在是一种公认的内部网关路由协议。它是一种增强的距离矢量路由协议,基于距离矢量算法,并具有链路状态算法的特征,如部分更新和邻居发现。

EIGRP信息包含报头和数据部分,数据字段被称为Type/Length/Value (TLV),这两个部分都封装在IP数据包中。

每个EIGRP消息报头都包含操作码字段。Opcode字段指定EIGRP数据包类型:Hello、Update、Acknowledgment、Query和Reply。EIGRP使用这5种数据包类型来维护其各种表并与邻居路由器建立关系。

EIGRP利用邻居表(IP EIGRP Neighbor Table)和拓扑表(IP EIGRP Topology Table)中的信息建立路由信息,然后基于复合度量值计算出首选路由,并存储在路由表(IP Routing Table)中。

IP EIGRP Neighbor Table中记录了直接连接的相邻EIGRP邻居路由器和本地接口的列表。即该路由器的Next Hop们。

IP EIGRP Topology Table中记录了从每个EIGRP邻居获知的所有路由列表,并标识后继路由(best successor)和备选/可行后继(backup/feasible successor)路由。

IP Routing Table记录了,EIGRP拓扑表和其他路由过程中的最佳(后继)路由列表。

邻居发现与交流

EIGRP路由器通过使用hello数据包建立和维护与邻居路由器的邻接关系,并将信息存储在IP EIGRP Neighbor Table中。如图是一个邻居发现与交流的过程:

收集拓扑信息

当EIGRP路由器发现一个新邻居时,它会向新邻居发送更新请求,并从新邻居接收更新路由内容,以填充拓扑表(IP EIGRP Topology Table)。

当直接连接的路由或接口发生更改,或邻居路由器向路由报告更改时,拓扑表将更新。拓扑表中还记录了每个条目的状态:

  • 被动状态(Passive state):路由器已选择路由的状态。
  • 激活状态(Active state):路由器没有路由,正在尝试寻找路由的状态。

选择最佳路线

EIGRP使用一些算法计算后继路由和备份路由的度量值(Metrics),并将它们注入拓扑表(IP EIGRP Topology Table)。

路径上的最小开销,称为可行距离FD, feasible distance)。如果路由有FD的度量值被称为后继路由/主路由。后继可以有多个路由器,它们的FD一样。

邻居路由器通告的路由开销,称为报告距离RD, reported distance)。如果邻居路由RD小于原始的后继路由FD,则该邻居路由可以成为后备路由/可行后继路由

在默认条件下,Metrics的表达式为:

Metrics = EIGRP bandwidth + EIGRP delay
EIGRP bandwidth = (107/ bandwidth) * 256
EIGRP delay = (delay /10) * 256

bandwidth是路由上沿着任何接口的最低配置带宽,单位为kbpsdelay是从源路由到目的路由的延迟之和,单位为µs。256是缩放系数。

下面通过一个例子来理解如何计算度量值。如图是一个拓扑图,其中R2右边连接的子网是目的地址。计算从R1到目的地址的FD和RD。

我们根据之前学到的距离矢量路由协议,从目的地址开始泛洪。第一次泛洪,泛洪到邻居R2上。此时带宽最小为1Gbps,延迟为1μs。

第二次泛洪,泛洪到邻居R1和R3。分别找到两条链路上的最小的带宽和总延迟,如下图。

我们可以计算从R1直接到目的地址的度量值。

via R2: FD = (107/ (10 * 103) + (100+1)/10) * 256

还需要注意R1和R3之间的链路,可能存在重新泛洪。此时除直连外的最小带宽和延迟变化:

我们可以计算R1经过R3时的度量值。

via R3: FD = (107/ (1 * 103) + (1000+10+1)/10) * 256

很明显,经过R2的度量值更小,它更优。所以R2就是R1的后继路由。

接下来我们还需要计算R1的邻居R3的度量值来检测经过R3的路由是否能作为备选路由。(注意:是计算R3的度量值,不包括R1到R3的链路上的带宽与延迟)

via R3: RD = (107/ (100 * 103) + (10+1)/10) * 256 < via R2 FD

我们发现它的RD会比FD要小,故R3可以选为备用路由。

维护路由信息

EIGRP中,如果后继路由发生故障,路由器将查找已识别的备用/可行后继路由。此路由将升级为后继状态。

如果从当前信息中没有识别出可行的后继路由器(没有备用路由),路由器会在路由上设置Active状态,并向所有邻居发送查询数据包,以便重新计算当前拓扑。

路由器可以根据从应答查询请求的应答分组接收的新数据来识别任何新的后继路由或可行后继路由。然后,路由器将在路由上设置Passive状态。

扩散更新算法(DUAL)

扩散更新算法(Diffusing Update Algorithm, DUAL)是Cisco的EIGRP路由协议使用的算法,用于确保在可能导致路由环路的情况下,对给定路由进行全局重新计算。

DUAL维护一个与路由表分开的拓扑表,其中包括到目标网络的最佳路径和DUAL确定为无环的备用路径。

如果一条路径变得不可用,DUAL将在其拓扑表中搜索有效的备用路径。

  • 如果存在可行后继路由器(feasible successor),则立即将该路由输入路由表中代替出现问题的后继路由器。
  • 如果不存在可行后继路由器,则DUAL执行网络发现过程,向周围的邻居发送query请求,让其告诉有效的路径。

通过下面一个例子可以理解DUAL的过程,如下拓扑图中:

在稳定状态下,DUAL维护的各拓扑表如下:

因为Router A和Router B直接相连,它们之间的仅有一条记录。因为不会产生环路,故B不会记录C和D。

Router C:

EIGRP FD RD Topology
10.1.1.0/24 3 Passive
via B 3 1 Successor
via D 4 2 Feasible Successor
via E 4 3 -

Router D:

EIGRP FD RD Topology
10.1.1.0/24 3 Passive
via B 3 1 Successor
via C 5 3 -
via E 5 4 -

Router E:

EIGRP FD RD Topology
10.1.1.0/24 3 Passive
via D 3 2 Successor
via C 4 3 -

突然,Router D与Router B之间的连接断开,此时Router B和Router D最先知晓。Router D的拓扑表变为:

Router D:

EIGRP FD RD Topology
10.1.1.0/24 3 Active
via B 3 1 Successor
via C 5 3 -
via E 5 4 -

此时刚好将Router D的后继路由器删除了,于是Router D检索拓扑表中是否存在可行后继,发现刚好也没有。于是Router D进入进入Active状态,会向它的邻居发送query,请求可行的路径。

Router C收到D的query后,会在拓扑表中删除Router D的记录,于是有:

Router C:

EIGRP FD RD Topology
10.1.1.0/24 3 Passive
via B 3 1 Successor
via D 4 2 Feasible Successor
via E 4 3 -

但Router C仍然有Successor Router,处于Passive状态,于是回复Router D可以通过Router C到达目的地。

同时,Router E收到D的query后,同样删除Router D的记录,得:

Router E:

EIGRP FD RD Topology
10.1.1.0/24 3 Active
via D 3 2 Successor
via C 4 3 -

此时将Router E的Successor删除了,故它也需要向邻居发送query。因为Router E也进入Active状态,向其他邻居Router C发送query。

Router C收到E的query后,会在拓扑表中删除Router E的记录,于是有:

Router C:

EIGRP FD RD Topology
10.1.1.0/24 3 Passive
via B 3 1 Successor
via D 4 2 Feasible Successor
via E 4 3 -

但Router C仍然有Successor Router,处于Passive状态,于是回复Router E可以通过Router C到达目的地。

Router E更新自己的状态为Passive,并设置Router C为Successor:

Router E:

EIGRP FD RD Topology
10.1.1.0/24 3 Passive
via C 4 3 Successor

处于Passive状态下的Router E会回复Router D的query,于是Router D根据收到的回复,更新自己的状态为Passive,并设置Router C为Successor:

Router D:

EIGRP FD RD Topology
10.1.1.0/24 3 Passive
via C 5 3 Successor
via E 5 4 Successor

最后,整个网络收敛。

注意在整个过程中:

  • 需要等待所有的query回复后才能对比找到后继。
  • 只有Passive状态的路由器才能给出Reply。

链路状态路由协议

当网络拓扑结构发生变化后距离矢量路由算法需要太长时间才能收敛到稳定状态(由于无穷计数问题),于是一种新的路由算法链路状态路由算法(Link-state Routing)解决了这个问题,成为目前最为广泛的路由算法。

在每个应用链路状态路由协议的网络中,每个路由器都必须了解整个网络的拓扑情况才能使用该算法。每台路由器都使用最短路径优先(SPF)算法来计算通往每个网络的最短路由,并将路由信息存储在路由表中。

下面是一个最短路径算法的例子。如图是一个网络的拓扑图,A为源路由。

第一步,由A开始,泛洪邻居B和C。B和C到目的主机的距离分别为7和3,此时找到了最短路径是经过C到A。

From \ To B C D E F
A 7 3
Via A

第二步,从上一步最优的点C开始,泛洪邻居B、D、E。分别得到路径长度为5、7、11,此时B到A找到了最短路径是经过C到A。而D和E还不知道有没有更短的,先等待。

From \ To B C D E F
A 7 3
C 5 7 11
via C A

第三步,从B开始,泛洪D和C,C已经不可能存在更小的路径,而D得到了路径长度为10>7,可以确定上一步的7为最佳路径(因为D的邻居中除了E和F都已经找到最小的)。

From \ To B C D E F
A 7 3
C 5 7 11
B 10
via C A C

第四步,从D开始,泛洪E和F,分别得到路径长度为10、11,发现E的路径长度更小,于是找到了E的最佳路径。

From \ To B C D E F
A 7 3
C 5 7 11
B 10
D 10 11
via C A C D

第五步,从E开始,泛洪F,得到路径长度为16,发现经过D的路径长度更小,于是找到了F的最佳路径。

From \ To B C D E F
A 7 3
C 5 7 11
B 5 10
D 10 11
E 16
via C A C D D

最后我们得到最佳路径:

  • 从A出发,经C到B,距离为 5;
  • 从A 直接到C,距离为 3;
  • 从A经C到D,距离为 7;
  • 从A经C、D到E,距离为 10;
  • 从A经过 C、D到F,距离为 11.

我们可以得到它是一个无环树:

每个路由器从网络中的所有其他路由器收集路由信息时传递的信息为链路状态通告(Link State Advertisement, LSA)

链路状态路由协议通过以下方式维护路由信息:

  1. 每个路由器使用 LSA 跟踪其网络区域内的所有路由器,并使用 hello 数据包跟踪邻居路由器的状态。hello 数据包包含连接到路由器的网络信息。

  2. 当网络出现故障(如邻居无法访问)时,链路状态协议会在整个区域内发送带有特殊组播地址的 LSA。用于通知链路问题。
  3. 每个链路状态路由器都会获取一份 LSA 副本,并更新其链路状态或拓扑数据库。然后,链路状态路由器将 LSA 转发给所有邻居设备。LSA 会导致区域内的每个路由器重新计算路由。

与距离矢量协议对比,链路状态路由协议使用触发更新和 LSA 泛洪来立即向网络中的所有路由器报告网络拓扑的变化,加快了收敛时间如果网络发生变化,会立即发送部分更新,而不是整个路由表。部分更新只包含已发生变化的链路信息,可提高带宽利用率。


OSPF

开放式最短路径优先协议(Open Shortest Path First, OSPF) 是一种链路状态路由协议,支持IPv4和IPv6。

OSPF区域(OSPF Area)是从逻辑上将设备(路由器等)划分为不同的组,每个组用区域号(Area ID)来标识。OSPF Area可减少路由开销,加快收敛速度,将网络不稳定性限制在一个区域内,并提高性能。

其中,Area0一般是骨干网络,区域之间连接的路由器(图中R4, R6)称为区域边界路由器(Area Border Router, ABR)

OSPF的操作有如下:

  1. 建立邻居关系。
  2. 选举指定路由器(DR) 和 后备指定路由器(BDR)。
  3. 构建拓扑。
  4. 找到最佳路径。

建立邻居关系

当 OSPF 路由器连接到一个网络时,它会向本地直连网络上的路由器发送 hello 数据包,尝试与邻居建立邻接关系。

每个路由器都会保存一份与之建立了双向通信的相邻邻居的列表,称为邻接数据库(adjacency database)。该数据库对每个路由器都是唯一的。

OSPF的路由器会使用路由ID(Router ID),用于在一个OSPF域中唯一地标识一台路由器。

选举 DR 和 BDR

指定路由器(Designated Router, DR)和后备指定路由器(Backup Designated Router, BDR)是在多接入网络中交换 OSPF 路由信息的中心点。每个非 DR 或非 BDR 路由器将只与 DR 和 BDR 交换路由信息,而不是与网段上的每个路由器交换更新。 这样所有的拓扑信息均由DR来发布,大大减少 OSPF 流量。

对于单接入网络不存在DR和BDR。

具有最高 OSPF 优先级的路由器将被选为 DR。优先级第二高的路由器将成为 BDR。当 OSPF 优先级相同时,OSPF 将根据路由器 ID 决定 DR 的选举。选择最高的路由器 ID

选举过程结束后,即使网络中添加了 OSPF 优先级值更高的路由器,DR 和 BDR 仍会保留其角色。

例如:

它们的优先级都一样,选取ID最大的R3为DR,第二大的R2为BDR。

构建拓扑结构

每个 OSPF 路由器都会向同一区域内的所有邻居发送 LSA。然后,OSPF 会收集包含邻居路由器每个直接连接链路的状态和Cost的 LSA 列表,并构建一个完整的拓扑图,称为拓扑数据库(topological database)或链路状态数据库(link-state database)。该数据库在同一区域的所有路由器中都是相同的。

找到最佳路径

每个 OSPF 路由器都应用 SPF 算法计算通往每个目标网络的最佳路径。SPF 算法将Cost相加,Cost值通常基于带宽。Cost最低的路径会被添加到 OSPF 路由表,也称为转发数据库(forwarding database)中。该数据库对每个路由器都是唯一的。

路径开销(Path Cost)的计算公式为:OSPF cost = 100,000,000 / Bandwidth (bps) = 108 / Bandwidth (bps)

其值在 1 到 65535 之间。

下面是一个OSPF图:

图中存在6个Router,构成了4个子网,R1、R2、R3是一个局域网,网段为192.168.1.0/24,R1、R4是点对点的单接入网络,网段为192.168.2.0/30,R4、R5、R6之间通过广域网连接,网段为192.168.3.0/24,R6还接着一个子网。

RID设置为这个Router的一个IP如图所示。在发送hello数据包建立邻居关系后,在每个子网中选举DR和BDR。

根据RID的大小可以找到DR和BDR。此时经过STP的树可以是:

假设一个LSA从R1到R6,LSA会经过如下的路径:R1 -> R4 -> R6,它的开销Cost为:Metric = 108/(64*103 bps) + 108/(128*103 bps) + 108/(10*106 bps)


维护OSPF网络

当网络无任何变化的时候,OSPF会定期使用 hello 数据包来确定邻居的可达性。默认情况下,在点对点和广播式多接入网络上,每 10 秒发送一次 hello,在 NBMA(非广播式多接入,使用虚电路和交换结构连接)网络上,每 30 秒发送一次 hello

当网络发生变化时,OSPF 路由器通过向同一个Area内的所有其他路由器泛洪发送 LSU(link-state update) 来通知邻居,邻居将通过 LSAck 确认收到 LSU。

在点对点链路中,LSU使用224.0.0.5互相发送给对方

在多接入链路上,LSU 使用组播地址 224.0.0.6 发送给 DR。然后,DR 使用组播地址 224.0.0.5 将 LSU 泛洪到该网络中的所有 OSPF 路由器。

如果路由器是区域边界路由器(ABR),则它会继续向其他网络泛洪 LSU。OSPF 路由器收到包含新信息的 LSU 后,会运行 SPF 算法重新计算路由表。

在之前例子中,若R6接入的subnet连接断开,下面是整个网络泛洪LSU的过程:


后记

本文详细介绍了动态路由协议的基本概念和工作原理,包括主动路由协议和被动路由协议的区别,以及自治系统的概念。我们深入探讨了不同的路由协议,如OSPF、EIGRP等,以及它们的优化目标和算法。我们还详细分析了距离矢量路由协议和链路状态路由协议的工作原理,包括邻居发现、DR和BDR的选举、拓扑信息的收集、最佳路径的选择以及路由信息的维护等过程。最后,我们通过实例详细解释了DUAL算法和OSPF的工作流程。