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

作者简介:Domi,任职于中国移动,负责SDN/NFV相关研究设计工作。

随着互联网的爆炸式发展,运营商网络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示例拓扑

  • P-Space:S节点能够到达的节点的集合,节点集合满足:基于SPF算法S节点到达这些节点的最短路径不经过保护链路S->E,排除掉等价路径经过保护链路S->E的节点。上面的拓扑中S基于SPF算法到达A,B,C节点的路径可以不经过保护链路S->E,但是S到C的一条等价路径S->E->D->C经过了保护链路,所以C不能算作P-Space。
  • Q-Space:能够到达E节点的这些节点的集合,基于SPF算法能到达E的这些节点的最短路径不经过保护链路S->E,排除掉等价路径经过保护链路S->E的节点。上面拓扑中B,C,D节点基于SPF算法到达E节点的路径可以不经过保护链路S->E,但是B节点有一条等价路径经过了保护链路S->E,所以Q-Space是C,D
  • PQ点:P-Space和Q-Space的交集就是PQ点。当算不出PQ点的时候,就需要运行Extended P-space来进一步计算。
  • Extended P-space:再次以S节点的邻居A为根节点来计算出P-Space为B,C,那么最终的Extended P-space为A,B,C,由于Q-Space为C,D,所以交集为C,C为节点S到E链路的PQ点,作为RLFA。

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技术从提出到商用,进展如此迅速的重要原因。


  • 本站原创文章仅代表作者观点,不代表SDNLAB立场。所有原创内容版权均属SDNLAB,欢迎大家转发分享。但未经授权,严禁任何媒体(平面媒体、网络媒体、自媒体等)以及微信公众号复制、转载、摘编或以其他方式进行使用,转载须注明来自 SDNLAB并附上本文链接。 本站中所有编译类文章仅用于学习和交流目的,编译工作遵照 CC 协议,如果有侵犯到您权益的地方,请及时联系我们。
  • 本文链接https://www.sdnlab.com/22341.html
分享到:
相关文章
条评论

登录后才可以评论

domi 发表于18-09-14
3