在过去的几十年里, 互联网已经从一个最初支持发送邮件等业务的小型网络迅速演变为支持社交网络、视频流和云计算等的大型基础设施^[1-2]。与此同时, 用户对互联网服务提供商(Internet service provider, ISP)的服务质量提出了更加严格的要求, 例如给用户提供无间断服务、低延迟服务和高带宽服务等^[3-7], 其中如何向用户提供无间断服务是ISP面临的一个严峻挑战。在传统网络体系结构中, 学术界提出利用节点保护条件(node protection condition, NPC)^[8]、网络故障不敏感路由(failure insensitive routing, FIR)^[9]、Not-Via^[10]以及多协议标签交换(multi-protocol label switching, MPLS)^[11]等技术来提供无间断服务, 以应对网络中的突发故障情形。虽然NPC的实现方式简单, 但是无法很好地应对网络中的单节点故障。FIR、Not-Via和MPLS虽然可以应对网络中所有可能的单节点故障情形, 但是其实现过于复杂。NPC、FIR、Not-Via和MPLS等技术的重路由的路径拉伸度也比较高, 大大增加了网络的延迟, 降低了ISP的服务质量。因此, NPC、FIR、Not-Via和MPLS都没有很好地权衡算法实现复杂度、故障保护率和路径拉伸度之间的关系。

段路由(segment routing, SR)^[12-15]旨在支持具有严格的服务等级协议(service level agreement, SLA)保证的服务, 其核心思想是利用一系列的分段来构建特定的端到端的路径。在段路由结构中, 需要将段标签加入到数据包的头部, 然后利用这些标签完成报文的转发。段路由中有两种段标签, 分别是节点标签和邻接标签。节点标签表示一个路由器, 而邻接标签表示当前路由器的一个本地接口。目前, 主要的网络供应商已经支持SR, 并且将会进一步大部署规模。SR建立在现有的网络路由和连接管理协议的基础上, 其重要特征之一就是当网络出现故障时可以实现自动重新路由连接。因此, 可以利用SR实现基于IP的快速重路由机制。

本文首先描述了如何利用SR解决网络中单节点故障问题, 然后提出了一种基于SR的IP快速重路由(IP fast reroute based on SR, IPFRRBSR)算法, 该算法包括如何计算段标签和备份路径两部分内容, 最后在大量拓扑结构上进行了实验模拟。

1 网络模型和问题描述

网络拓扑可以表示为图G=(V, E)。在图G中，V表示网络拓扑中所有节点的集合, E表示网络拓扑中所有链路的集合, 即对于图G中$ \forall $e=(i, j)∈E。在一个网络拓扑G=(V, E)中, 源-目的节点对(o, d)(o≠d)之间的最短路径表示为p(o, d, G), 源o到目的d的最优下一跳表示为b(o, d, G), e=(o, b(o, d, G))表示o与b(o, d, G)所连接的链路。对于图G中任意节点v, 用I(v)表示所有其他节点到达该节点的边。p′(o, d, r(o, d))表示利用段标签r(o, d)计算出的节点(o, d)之间的备份路径, 简写为p′。

本文的问题可以描述为：给定网络拓扑G=(V, E), 计算图中所有(o, d)(o≠d)对的段标签, 使得利用段标签计算出的备份路径可以应对网络中所有可能的单节点故障。

输入：网络拓扑结构G=(V, E),

输出：r(o, d), o, d∈V, o≠d,

目标：Converge(o, d, l, p′)=1。

r(o, d)表示(o, d)(o≠d)之间的段标签的集合, Converge(o, d, l, p′)=1表示对于所有的(o, d)(o≠d)计算出的备份路径p′可以应对网络中所有的单节点故障。本文讨论的网络是一个健壮性网络。健壮性网络可以定义为当该网络中任意一个节点断开时, 网络依然保持连通。选择健壮性网络是因为对于一个非健壮性网络, 讨论单节点故障没有实际意义。

2 IPFRRBSR算法 2.1 算法需要解决的关键问题

下面通过2个步骤来解决第1节中提出的问题：

步骤1  计算出所有(o, d)(o≠d)之间的段标签。

步骤2  对于每一个(o, d)(o≠d), 通过计算出的段标签来计算二者之间的备份路径。

在上述2个步骤中, 步骤2较为简单, 备份路径可以用公式p′(o, d, r(o, d))=p(o, r₁, G)∘ p(r₁, r₂, G)∘…∘p(r_n, d, G)表示。其中：r₁, r₂, r₃, …, r_n表示(o, d)对之间共有n个段标签, r_n用来表示r(o, d)中的第n个段标签; p(o, r_n, G)表示从o到r_n的最短路径。对于(o, d)(o≠d), 如果随意计算它们之间的段标签, 则它们之间的备份路径就可能无法应对网络中所有的单节点故障。下面将详细描述如何计算源-目的对之间的段标签, 从而实现本文提出的目标。

2.2 算法实现

图 1详细描述了IPFRRBSR的执行过程。算法输入为网络拓扑G=(V, E), 输出为拓扑中所有(o, d)对的r(o, d)的集合U。对于节点v, 构造以该节点为根的最短路径树(算法第2行)。将该树中除去节点v以外的其他节点按照深度优先的顺序存储在队列Q(v∉Q)中(第3行)。算法需要一系列的迭代过程, 在每次迭代过程中, 从队列Q(v∉Q)中取出第1个元素o(第4—6行), 这样就形成一个(o, d)对。为了解决算法中可能遇到的最后下一跳问题, 将所有链路I(b(o, d, G))从拓扑G中删除得到G′, 并且计算(o, d)对之间的最短路径p(o, d, G′)(第7—8行)。通过函数Relaynode(o, d, p(o, d, G), p(o, d, G′))计算出(o, d)对间的段标签r(o, d), 将计算好的r(o, d)并入集合U中(第9—10行)。最后, 输出集合U(第13行)。

算法IPFRRBSR中的第9行调用了函数SRLABEL, 图 2描述了SRLABEL函数的执行过程。首先, 需要给该函数输入网络拓扑G和一个(o, d)对, 以及算法IPFRRBSR第8行计算出的p(o, d, G′)。p(o, d, G′)在这里表示为{o, v₁, v₂…v_n, d}。函数输出为一个(o, d)对的段标签集合r(o, d)。如果p(o, d, G′)={o, d}, 即b(o, d, G′)=d, 则这个(o, d)对不存在段标签(第1—3行)。该函数定义了3个临时变量o′, d′, n′, 其中o′, d′∈{o, v₁, v₂…v_n, d}, 因此p(o′, d′, G′)$ \subset $p(o, d, G′)。例如，假设o′=o, d′=v₂, 则p(o′, d′, G′)={o, v₁, v₂}。初始化o′, d′, n′的数值(第4行)。为了计算段标签, 算法需要进行一系列的循环过程。在每一次循环中, 首先将变量d′和n′的值分别设置为d′=d和n′=n(第6行)。第7—16行是计算满足p(o′, d′, G′)=p(o′, d′, G)的d′的取值过程。如果满足上述条件的d′不存在, 则d′=o′(第8—10行)。如果b(o′, d, G′)≠d, 则此时节点b(o′, d, G′)为一个段标签, 将其并入集合r(o, d)中, 并且将o′的值变为b(o′, d, G′)(第18—20行), 否则d′=d。如果满足条件p(o′, d′, G′)= p(o′, d′, G)的d′存在, 继续判断d′是否等于d, 如果d′≠d, 此时d′为一个段标签, 将其并入集合r(o, d)中, 并且将o′的值变为d′(第25行)；如果d′=d, 则算法结束(第27行)。

2.3 算法复杂度分析

在IPFRRBSR中, 对于网络中的每个节点, 需要计算一棵以该节点为根的最短路径树, 这部分的时间复杂度为|V|·O(|V|lg|V|+|E|)。计算节点对之间的段标签的最坏时间复杂度为O(|V|), 即节点间的路径包含的最大节点数, 为所有节点对计算段标签的时间复杂度为V²·O(|V|)。因为计算以该节点为根的最短路径树可以并行计算, 所以该部分的算法复杂度可以为O(|V|lg|V|+|E|)。同理, 计算段标签也可以并行计算, 该部分的算法复杂度为O(|V|)。因此, IPFRRBSR的算法复杂度为O(|V|lg|V|+|E|)。

2.4 算法收敛性分析

IPFRRBSR算法主要执行Dijkstra算法和字符串匹配算法。当计算两个节点之间的段标签时, 首先根据图 1算法的第2行计算出的最短路径树构造出这两个节点之间的最短路径, 然后根据图 1算法的第7—8行重新计算这两个节点之间新的最短路径。然后, 调用函数SRLABEL执行字符串匹配算法, 函数SRLABEL详细讨论了节点间所有段标签的可能情况, 因此IPFRRBSR必定会收敛。

3 实验

利用模拟实验来评价本文提出的算法IPFRRBSR的性能, 并且与算法NPC和Not-Via进行比较。模拟实验的评价指标主要包括故障保护率和路径拉伸度。为了说明IPFRRBSR不会引入过多的额外负担, 计算IPFRRBSR在不同拓扑结构中对应的段标签的个数。

为了衡量算法的性能, 本文采用了两种类型的拓扑结构, 包括2个真实拓扑结构NJLATA和TORONTO^[6], 以及4个利用Brite软件生成的拓扑结构。Brite(n, m)表示该拓扑的节点个数为n, 度数为m。

3.1 故障保护率

本节通过故障保护率来测试不同算法应对单节点故障的能力。表 1列出了不同算法在两种类型的拓扑中对应的故障保护率。从表 1可知, IPFRRBSR和Not-Via的故障保护率都为100%, 但是NPC的故障保护率在80%~98%之间。

3.2 路径拉伸度

本节将衡量当网络中出现单节点故障时, 报文的实际转发路径和发生该故障后对应的最短路径的比值, 即路径拉伸度。因为NPC算法的故障保护率不是100%, 所以在做此实验时, 仅仅比较NPC算法中能够被保护的路径对应的路径拉伸度。表 2列出了不同算法对应的平均路径拉伸度。由表 2可知, 在其中所有拓扑结构中, IPFRRBSR的路径拉伸度最小, NPC的路径拉伸度最大。特别地, 在拓扑NJLATA中, IPFRRBSR的路径拉伸度为1, 而NPC的路径拉伸度为1.072 326。

为了更加精细地描述路径拉伸度, 本文统计了不同算法对应的每个源-目的的路径拉伸度。图 3和4分别表示不同算法在拓扑NJLATA和拓扑TORONTO中路径拉伸度的累积概率分布。从图 3中可知, IPFRRBSR中所有源-目的的路径拉伸度均为1, 远远小于Not-Via和NPC的路径拉伸度。由图 4可知, IPFRRBSR中源-目的的路径拉伸度为1的比例为72%, 路径拉伸度小于1.5的比例为98%。

3.3 段标签个数

本节将描述算法IPFRRBSR在不同拓扑结构中对应的段标签的个数。由表 3可知, IPFRRBSR算法对应的平均段标签的个数均小于1.2, 因此不会增加过多的额外负担。

图 5描述了算法IPFRRBSR在两种拓扑中每个源-目的对的段标签个数累积概率分布。从图 5可知, 除去NJLATA, 在剩余拓扑中92%以上的源-目的对的段标签个数为1, 只有不到8%的源-目的对的段标签个数为2。NJLATA中仅仅有0.001%的源-目的对的段标签个数为3。

4 结论

本文提出了一种基于SR的域内路由保护算法, 即IPFRRBSR算法。IPFRRBSR算法计算节点对(o, d)之间段标签的方法如下：首先计算二者之间的最短路径；然后从原拓扑结构中删除节点o到节点d的最优下一跳, 在新的拓扑中重新计算二者之间的最短路径；最后根据这两条最短路径的匹配情况计算二者之间的段标签。因为利用IPFRRBSR计算出的节点对之间的备份路径和节点对之间的最短路径不包含公共节点(除去源和目的节点), 所以IPFRRBSR可以应对网络中的单故障情形。实验结果表明：IPFRRBSR不仅可以提供100%单故障保护率, 并且路径拉伸度较低, 很好地解决了目前路由保护方案无法平衡故障保护率和路径拉伸度的难题。IPFRRBSR可以为ISP解决域内路由可用性提供一种有效的解决方案。