网络转型中的快速重路由技术

随着互联网的爆炸式发展，运营商网络ALL IP的演进，越来越多行业的核心业务严重依赖网络开展。作为网络应用发源地的ICT行业自不用说，证券、金融行业现在离了网络几乎寸步难行，零售行业更是通过网络引发了电商革命。互联网大潮之下，几乎没有哪个行业不被波及，涉足网络领域成了不得不面对的选择。在这种背景下，网络的高可用性及自愈能力，日益成为构建网络的关键目标。上至运营商，下到大中型企业客户，构建基础网络时，5个9（99.999%）的网络可用性成为必然的选择，这相当于一年中，各种原因造成的网络中断总计大约为5.256分钟。同样，对于网络设备厂商而言，能否提供完善的高可用产品和解决方案，直接关系到核心竞争力，关系到在未来激烈的竞争中能否生存。

当网络链路或设备节点发生故障时，在路由再次收敛前网络流量会发生中断，以现在使用最广泛的OSPF/ISIS协议来说，会经历如下五个过程：探测到故障、产生更新信息、泛洪到整个网络、重新计算路由表以及下刷到FIB表。语音、视频等实时性网络业务的兴起，对IP网络流量的快速倒换也提出了更高的要求，新的架构需要在小于50ms的时间内完成业务的倒换。目前，主流的快速收敛技术：LFA（Loop-Free Alternate，又称 IP FRR，IP Fast Reroute），Remote LFA（Remote Loop-Free Alternate），MRT-FRR（Maximally Redundant Trees – Fast Reroute）等。下面依次介绍下三种路由备份技术原理，发掘其存在的问题。

1.IP FRR

IP FRR即Loop-Free Alternate，LFA技术。IP FRR基于Dijkstra算法计算最短路径（Shortest Path Forwarding）计算，计算出备份路径，网络节点故障时，快速切换流量到备份路径，无需等待路由收敛。存在备份路由的拓扑，典型特征是存在环状链路。引用RFC 5286简述其原理如下：

如下拓扑由4个设备节点组成，链路上的数字为路由计算选用的链路度量参数cost，数值越小，链路质量越优。

图 1 IP FRR示例拓扑

源节点S到目的节点D，根据SPF最短路径算法，优选左侧S->E->D，作为最优路径。当S和E之间链路故障，或节点E故障时，S主动切换至可备用链路的无环条件如下：

Distance_opt(N, D) < Distance_opt(N, S) + Distance_opt(S, D)

RFC5286计算出来的LFA永远是S的相连的邻居。LFA是基于SPF算法的，所有路由器都有整个区域的路由器的链路状态信息，路由器S根据SPF算法计算出到目的路由器D的主用下一条是E，然后应用上面的不等式：

Distance_opt(N, D) < Distance_opt(N, S) + Distance_opt(S, D)

发现3 < 8+9不等式成立，选择N为loop-free alternate，也就是备份下一跳。

Distance_opt(N, D)：备份下一跳到目的节点的cost值

Distance_opt(N, S)：备份节点到始发节点的cost值

Distance_opt(S, D)：始发节点到目的节点的cost值

注意：Distance_opt（X,Y）是指X到Y的最短距离，直连不一定最优。

鉴于上述过程，IP FRR存在如下问题：

1)必须得满足不等式才可以作为LFA，只能保证一部分节点有LFA，导致存在备份路径情况下，计算不出备份路由。

2)对于环形组网会出现微环路micro loop。还是以RFC5286举例：

图 2 IP FRR微环拓扑示例

部署了LFA后，到目的节点D，起始节点S和节点N是互为LFA的，但是如果节点E失效，节点S会把流量转发给LFA N节点，节点N又回把流量转发给LFA S节点，形成micro loop微环路。

2.Remote LFA

LFA计算出来的备份下一跳永远是他的直连邻居，RLFA通过tunnel技术，将远端的PQ节点作为备份下一跳， 使得LFA做了很好的扩展，能够保证更多的节点有备份下一跳。

几个概念术语，以RFC7490第四页拓扑为例，链路间为等值cost，S->E为需要保护的链路，对于S节点：

图 3 Remote LFA示例拓扑

RLFA的设计思想：选择一个PQ节点作为RLFA，源节点S与RLFA之间建立tunnel，在不经过需要保护链路的前提下，源节点S首先通过属于P-Space或 Extended P-space LSP将流量转发给它，然后，出隧道解封装，通过属于Q-Space LSP将流量转发给目的节点E，这样以来，RLFA不再局限于LFA的苛刻条件，能够保证更多的节点有RLFA，另外，当需要保护链路中断，会首先把流量转发给远端的PQ而不是直连邻居，可以避免micro loop微环的出现。

Remote LFA大幅提升了备份路由覆盖率，大多数理论上存在备份路由的情况，能够产生备份路由。RLFA仍存在如下较大问题：

1.某些情况下，PQ节点不存在，无法计算出备份路由，典型情况举例如下，假定S—A间链路cost为10，此时P-Space及Extended P-space均不存在，导致无法计算出PQ隧道出节点，无法形成备份路由。

图 4 Remote LFA失效拓扑示例

2.P-Space，Extended P-space及Q-Space计算以大量的SPF计算为基础，需要变换根节点进行多次SPF计算，当拓扑较复杂时，该计算量极为庞大，远超路由计算本身。为了达到备份路由的目的，带来的是路由收敛性能的大幅降低，某些场景下得不偿失。

3.MRT-FRR

针对LFA及RLFA存在的上述问题，IETF相关工作组，提出了基于MRT（Maximally Redundant Trees）的备份路由计算机制，旨在寻找能够达到100%覆盖率的快速重路由技术。理论上存在备份路由的场景下，MRT均能产生备份路由，彻底解决了某些场景下无备份路由的问题。RFC 7811，RFC 7812定义了其框架原理。核心思想为，路由设备除了能够按照SPF最短路径进行转发外，还要求其可以按照MRT-RED/MRT-BLUE两棵最大冗余树（Maximally Redundant Trees）进行转发。MRT-RED/MRT-BLUE分别按照协议标准规范以当前设备为根，按照两个方向进行DFS（Depth First Search）搜索，基于MRT Lowpoint算法计算而生成。

图 5 MRT Lowpoint计算示例

MRT-FRR存在如下缺点：

1)对现网设备要求很高，除了具备传统SPF最短路径转发能力外，还需要额外的软件及硬件支持，现网设备目前基本都不支持，导致MRT-FRR只具备理论可能，没有实际可行性。

2)MRT-RED/MRT-BLUE的计算需要进行多次DFS运算，其对性能消耗要高于路由算法SPF运算复杂度，为了达到较高备份路由覆盖了，极大牺牲了路由收敛性能，舍本逐末。

3)MRT-RED/MRT-BLUE进行DFS运算，并不是依赖算法自身保证路径的唯一性，比如，拓扑固定情况下，SPF算法可以保证全网所有设备运算的最短路径树是一致的。而MRT通过DFS算法进行运算，并不能保证分发树唯一，而是通过协议规范约定一致的规则而保证。网络设备厂商形形色色，对网络设备有极高要求，影响较大。目前，MRT-FRR鲜有应用。

Segment Routing

SDN网络下，可充分发挥集中控制优势，进行拓扑计算，跳出了传统路由交换设备限制，可彻底解决快速重路由的计算问题，而转发面如何实施成为关键。Segment Routing技术提供了一种软件定义路由的方法，其机制简单优雅，可高效快速解决快速重路由覆盖率低的问题。而这一切得益于SR的软件定义路由优势。

先介绍下Segment Routing工作原理。

Segment Routing，即段路由技术。它提供了一种软件定义路由转发路径的方法。

Segment Routing的前缀段，邻接段，及混合段工作原理下面分别进行阐述。段可以理解为标签，SR通过定义一系列段，即标签序列，实现对转发路径的定义。

通俗地讲，前缀段可以理解为传统路由前缀直接映射为一个数字标签，该映射通过IGP路由直接完成，不需要LDP再次交互。比如图 6 前缀段示例中1.1.1.5/32路由映射为16005，通过IGP路由发布后，其各设备到达该目的地址的路径如下，MPLS转发时，标签即为16005，中间各设备节点自动选择下一跳进行标签转发，直至到达节点5，弹出标签，完成转发。

图 6 前缀段示例

图 7 存在等价路由的前缀段示例 是存在等价路径ECMP情况下的，拿1.1.1.4/32路由举例的标签转发路径。前缀段的转发路径和IGP路由转发实际路径没有什么不同，只不过采用标签MPLS转发，而不采用IP路由转发。

图 7 存在等价路由的前缀段示例

邻接段，可以理解为针对某个链路的一个局部段，用于实现特定场景下，用户想让流量经过某段特定链路的需求。之所以称作邻接段，来源于其实际含义，用于两个节点间链路指定。比如图 8 邻接段示例，节点2和4之间，节点2和5之间分别定义邻接段标签24024及24025。

图 8 邻接段示例

单独的前缀段或邻接段，应用比较有限，功能比较单一。当我们将二者结合起来，形成段序列，或者说标签序列时，将具备一项超乎寻常的特异功能，而MPLS标签转发天然支持标签栈。比如，定义到达节点5的流量必须经过节点4，并且经过节点4和5之间的链路，并可形成标签序列{16004,24045,16005}（注：节点5发布的前缀段可能不止16005，图例里因此没有标识为16005，这里拿16005举例）。节点1，根据栈顶标签16004进行转发，16004为节点段标签存在ECMP，进行负载分担转发至节点4，由于16004为节点4发布的标签，弹出16004，露出24045标签并弹出，将其从和节点5连接的接口转发出去，到达节点5后，处理16005标签，由于16005标签为节点5发布的标签，弹出该标签，全部标签处理完毕，转发完成。

图 9 组合段示例

综上所述，所有的前缀段标签转发按照IGP最优路径转发，同时邻接段按照用户定义转发，路径序列通过在源节点压入标签序列来实现。SDN场景下，SDN控制器收集到各种标签，用户通过图形界面定义流量转发路径，形成段序列，通过南向接口可通知转发面，形成基于源头的路由，可实现极其灵活的转发路径自定义，只需要控制器进行统一计算调度，转发面只负责接收流表，下刷流表即可。

本文简单探讨一种基于SR技术实现100%路由备份，达到快速重路由的方案。

1.传统基于链路状态的路由协议（OSPF/ISIS等），进行SPF计算，生成最短路径树SPF-T1，形成最优路由，该步骤为目前路由设备的标准实现。示例如下：标号为1~5的5个路由设备节点组成如下拓扑。

图 10 示例拓扑

设备1为根，基于Dijkstra算法进行SPF计算，生成的SPF-T1如下：

图 11 SPF最短路径树示例

设备1到设备5的最短路径为：1->2->5，链路cost为：5。

2.针对要保护的链路，在链路状态数据库中删除该链路，然后进行SPF最短路径计算，生成最短路径树SPF-T2。计算完毕，为了不影响后续基础路由功能，保持链路状态一致，再将删除的链路进行恢复添加。示例如下：

针对受保护的链路为1—2之间的链路，删除该链路后，拓扑如下：

图 12 剔除受保护链路拓扑示例

针对上述拓扑进行SPF计算，生成SPF-T2如下：

图 13 剔除受保护链路后最短路径树

设备1到设备5的路径为：1->3->4->2->5，链路cost为：8。

3.针对经过受保护链路的所有目的节点路径，对比SPF-T1和SPF-T2。从目的节点向左依次对比，将SPF-T2中和SPF-T1相同的节点全部剔除，直至遇到不同节点。如：针对步骤1，2中设备1到设备5的两条路径，1->2->5（SPF-T1）和1->3->4->2->5（SPF-T2），SPF-T2从目的节点5开始，依次向左，对比SPF-T1，剔除相同节点后，产生路径1->3->4。

该步骤用于剔除备份路径中不必要的邻接标签序列，防止SR标准栈溢出，同时复用最短路径转发。该步骤可用反证法证明其正确性。

4.将步骤三中形成的路径，做Segment Routing邻接段序列化，形成特定路径，即利用SR中邻接段路由，重新定义备份转发路径。示例如下：假定设备5的前缀段标签为16005，其他节点间邻接段标签分别如下图。步骤三示例中，产生的备份路径为：1->3->4，则形成针对设备1到设备5的备份路由SR标签栈序列为{24013，24034，24024，16005}，栈底为16005。

图 14 拓扑标签段示例

5.进行路由计算时，同时进行上述步骤运算，将生成的备份路由序列保存至转发表，当检测到链路故障时，采用预算保存的SR标签栈进行路由转发，完成备份路由切换。

6.理论上存在备份路径的拓扑，其链路至少存在两条以上，剔除受保护的链路，100%可产生备份路径，因此，该方案可提供100%备份路由保护。

该方案仅为毛糙想法，结合SDN集中控制，必将出现更为优雅的快速重路由技术。在细分领域的深耕变革，远不如SR这种从转发面进行的深层次颠覆。

Segment Routing技术助力快速重路由，在该细分领域至少带来如下便利：

1)简化了传统快速重路由技术的实施难度。比如，Remote LFA技术，需要自动化建立及拆除到PQ节点的隧道，且该隧道依赖传统SPF最短路径，SR技术天生完美支持。单单是LDP及MPLS TE的配置复杂度就让人却步，在传统网络上施加RLFA，可见其难度。

2)SR具备灵活的软件定义路径能力，理论上，只要存在备份路径，利用SR前缀段及邻接段，可以指导转发设备强制按规则转发，跳出单纯SPF最短路径的怪圈。该优势可轻松取代MRT-FRR复杂的拓扑运算带来的效果，同时，对传统设备没有过多要求。

而这一切，是如此自然，Segment Routing大道至简，至简而美，我想这也是SR技术从提出到商用，进展如此迅速的重要原因。

原文发布时间为：2018-09-14

本文作者：Domi

本文来自云栖社区合作伙伴“SDNLAB”，了解相关信息可以关注“SDNLAB”。