软件定义广域网中基于IPv6分段路由的双栈流量调度算法

肖漫漫，刘骥琛，李艳丽，马 迎

(中国人民大学 信息技术中心， 北京 100872)

近年来，随着大数据、人工智能、IPv6、在线视频、移动互联网等业务的快速发展，网络流量变得复杂多样，应用种类也越来越多，互联网的带宽资源越来越丰富，企业对网络的弹性、灵活性和QoS(quality of service)的需求也越来越高。因此业界提出了软件定义广域网(SD-WAN, software-defined wide area network)，通过部署SD-WAN，可将网络资源虚拟化，降低流量成本，提高带宽利用率，加速网络服务分发效率[1]，实现广域网自动网络部署和流量调度。为保障SD-WAN可靠性及利用率，SD-WAN通过部署多链路备份方案，同时接入专线、互联网、LTE/卫星线路，利用overlay技术将不同线路混合捆绑，从而实现多链路间的流量调度和复杂服务质量[2]。而目前业界部署的SD-WAN多链路间的流量调度方案均为基于IPv4协议栈技术，支持IPv4/IPv6的双栈流量调度还没有统一的解决方案。

另一方面，分段路由(SR, segment routing)技术以及与软件定义网络(SDN, software defined network)结合受到了人们的青睐。分段路由支持无状态源路由，可以减轻控制器和中间节点的开销，对路径的管理和控制也十分灵活[3]，因此也有一些工作研究了如何基于分段路由技术解决SDN中的流量调度问题[4-7]。其中文献[4]将流量路径进行分解，在考虑2段段列表的情况下，开发了离线和在线的流量调度优化算法。文献[5]提出了一种基于分段路由路径变量的数据结构，通过记录经过节点和可能的下一跳节点，达到流量调度时减小消耗计算资源的目的。文献[6]分析了基于分段路由技术的网络流量模型，考虑在流转发时使用单路径而不是会加大计算资源消耗的等价多路径模型。文献[7]提出了一种SDN网络中基于分段路由的多路径流量调度算法，该算法在进行路径权重计算后，根据路径权重选择最优路径，并基于分段路由技术构造分段流表下发到边缘交换机。但以上所述流量调度算法仅针对IPv4流量，还不能解决双栈流量的调度问题。

1 关键技术

1.1 SRv6简介

SRv6是一种基于IPv6数据平面实现的分段路由协议的网络架构，分段路由技术[8]通过将报文转发路径切割为不同的分段，并在路径的起始点往报文中插入分段信息指导报文转发。这样的路径分段通过SID(段标识符, segment identifier)来标识。路径的起始节点把这些路径分段组合起来形成段序列(segment list)，指引报文按照段列表在网络上将数据包进行转发。为在IPv6报文中实现SRv6转发，依据IPv6原有的路由扩展报文头定义了SRv6扩展报文头SRH(段路由扩展报文头, segment routing header)[9]，SRH通过携带段列表等信息显式地指定一条SRv6路径。由于对双栈流量进行了调度，与文献[4-7]针对IPv4的流量调度研究中压入SID信息引导流量转发的方式不同，通过在恢复路径中压入SRH信息引导流量转发，进而通过在处理节点指定行为指令对流量报文进行处理，最终实现流量调度。在IETF的SRv6 Network Programming[10]文稿中定义了很多SRv6段端节点(Endpoint)行为的指令，SRv6常见指令功能介绍如表1所示。

表1 SRv6 Endpoint常见指令功能Table 1 Function of SRv6 Endpoint

1.2 FRR技术

快速重路由(FRR, fast reroute)技术是指在链路故障发生时，能够快速切换到备份路由路径的机制[11]。基于FRR技术，当链路状态失效无法正常传输流量数据时， SD-WAN控制器会对备份路径进行动态计算，并将计算好的备份路径转发规则部署到相应的网络设备上，以调度中断的流量。

基于以上2种技术原理，由于网络发生故障时和故障恢复后会产生环路现象，而SRv6通过创建无环的SRv6 段列表就可以有效地消除网络环路[12]，因此分段路由技术结合FRR技术也越来越多地被用来解决链路失效时的路径恢复问题[13-15]。其中文献[13] 分别针对单链路失效和多链路失效提出基于分段路由的快速重路由技术，2种算法都是在检测到链路失效后，计算出拼接路径，并通过分段路由技术引导业务流量的恢复路径。文献[14]提出基于分段路由的主动式链路故障恢复策略，该策略利用分段路由的方法，通过将链路信息压入数据包头部进行数据包的转发，从而达到链路恢复时减少网络设备消耗流表项资源的目的。

2 DSTS算法

2.1 系统场景

在多园区网络中，各园区保留独立的园区接入广域网的出口链路，而当园区网络支持双协议栈架构时，各园区接入广域网出口多部署IPv4/IPv6双链路，多园区双栈网络拓扑可以归结为如图1所示拓扑模型。

图1 多园区双栈网络拓扑模型Fig. 1 Topology of dual stack in muti-brunches

如图1所示，园区A任意主机Ha和园区B任意主机Hb分别通过双栈链路接入广域网，在任意园区IPv4和IPv6链路有效状态下，Ha发往Hb的IPv4流量传输路径为Ha->Ra0->Ra4->WAN->Rb4->Rb0->Hb、IPv6流量传输路径为Ha->Ra0->Ra6->WAN->Rb6->Rb0->Hb。假设园区A IPv4链路出现故障，即Ra4->WAN链路失效，此时需在Ra4节点进行快速重路由，按照现有拓扑结构，恢复路径应为Ra4->Ra6->WAN。但是当IPv4数据流到达节点Ra6时，由于没有匹配的路由转发表，最终会导致数据包的丢失。同理，当园区A IPv6链路出现故障时，当IPv6数据流到达节点Ra4时，仍会面对数据包丢失的问题。

针对上述应用场景提出DSTS算法，该算法在SD-WAN的基础上，通过触发SD-WAN控制器为双栈数据流重新计算一条路径，实现路由快速恢复，并分为路径编码算法和报文处理算法2部分实现双栈流量调度，进而达到双栈业务流量快速恢复的效果。

2.2 数学模型

将计算流量路径描述为单源最短路径模型，其数学模型描述为带权有向图G(N,A)，定义节点s∈N为源节点，其他节点为非源节点，路径长度为该路径所包含链路长度之和。计算单源最短路径问题就是找出源节点s到每一个非源节点j的有向最短路径，由于流量转发设计仅支持单路径，进一步将原优化模型转换为一个整数线性规划(ILP, inter linear programming)模型，即优化目标是恢复单源路径长度。该模型用到的变量如表2所示。

表2 符号含义Table 2 Notation meaning

优化目标函数

Minimize∑(i,j)∈Acijxij，

(1)

s.t.

∑{j:(i,j)∈A}xij-∑{j:(j,i)∈A}xij=1,i,j∈A且i=s，

(2)

∑{j:(i,j)∈A}xij-∑{j:(j,i)∈A}xij=-1,i,j∈A且i=t，

(3)

∑{j:(i,j)∈A}xij-∑{j:(j,i)∈A}xij=0,i,j∈A且i≠s,t，

(4)

0≤xij≤1，i,j∈A，

(5)

∑{j:(i,j)∈A}xij≤1，i,j∈A且i≠s,t，

(6)

∑{j:(j,i)∈A}xij≤1，i,j∈A且i≠s,t，

(7)

目标函数是最小化单源恢复路径长度，公式(1)表示i,j为链路(i,j)的上下游节点，如果链路(i,j)是在业务最短路径上，则为1，否则为0。公式(2)(3)(4)表示链路流量守恒，若限制数据流转发仅支持单路径，则遵守式(2)(4)。公式(5)表示如果链路(i,j)在最短路径上，则值为0，否则为1。公式(6)(7)可防止产生环路。

优化目标函数求解算法流程如下：

1)SD-WAN控制器记录有向图G(N,A)，记录各链路权重cij，并采用Dijkstra算法计算最短路径并保存。

2)当出现链路故障时，更新失效链路权重cst=0，控制器删除故障节点和失效链路，更新网络拓扑为G(N,A′)。

3)重复步骤1) ，根据更新后的网络拓扑，采用最短路径算法重新计算最优路径并保存。

2.3 DSTS算法设计与分析

在快速重路由的应用基础上，基于SRv6提出双栈流量调度算法。设计思路是在园区网络拓扑中单协议栈出口链路失效的场景下，对于受影响的业务流量，SD-WAN控制器分别以失效链路2端的上下游节点为源节点和目的节点计算一条恢复路径，通过路径编码算法计算出并压入SRH的内容、通过报文处理算法计算出双栈流量的报文转发方式，进而将业务流量绕过失效链路引导至下游节点。基于SRv6的双栈流量调度算法如表3所示。

表3 DSTS算法Table 3 Algorithm of DSTS

在该场景下，SD-WAN控制器监控整个网络拓扑状态，当链路失效后，控制器更新网络拓扑，将失效链路删除，进而根据最短路径算法计算出恢复路径。如图2所示，当链路Ra4->WAN链路失效时，园区间IPv4流量会切换到重新计算的恢复路径Ha->Ra0->Ra4->Ra6->Rb6->Rb4->Rb0->Hb。假设园区网络内所有网络节点均支持SRv6，可以把节点Ra4作为入口节点、节点Rb4作为出口节点。SD-WAN控制器监控整个网络拓扑状态，当链路失效后，控制器更新网络拓扑，将失效链路删除，在园区出口Ra4节点通过Segment List引导流量绕过失效链路，并通过SRv6作为underlay技术穿越广域网，在出口节点(即故障链路的下游节点)弹出所有路径分段并恢复原始报文进行转发，保证双栈流量通过快速重路由生成的替代路由进行转发。采用基于编码算法的方式进行路径编码，以此确定段列表压入哪些Segment。

图2 DSTS算法拓扑Fig. 2 Topology of DSTS algorithm

2.4 DSTS算法实现

针对图2所示场景的恢复路径，设计的DSTS算法包括路径编码算法和报文处理算法2部分，算法伪代码描述分别如表4、表5所示，表6为报文处理算法使用的符号及其含义。

表4 路径编码算法Table 4 Algorithm of path coding

表5 报文处理算法Table 5 Algorithm of packet

表6 报文处理算法符号及其含义Table 6 Notation meanings of algorithm 2

表4描述了图2场景所示的恢复路径编码算法。针对不同协议流量类型，在该网络拓扑中，每条链路的权重值cij是不均等的，采用逆向遍历解法。从失效链路下游节点开始，其中恢复路径源节点S(即图2中Ra4)为失效链路上游节点、目的节点T(即图2中Rb4)为失效链路下游节点，节点X为恢复路径的中间节点。逆向遍历恢复路径直到找到节点X使其路径权重和满足公式(8)，CTX为节点T到节点X的路径权重和，而CXT为节点X到节点T的路径权重和，Y为X下一跳节点，其他变量同理。

(8)

若X节点与源节点重合，则压入目的节点Segment，若X节点与源节点不重合，则压入该节点与目的节点Segment，之后各节点依据表5所示的报文处理算法进行报文调度，最终遵循路由协议在网络中进行最短路径转发，图6为报文处理处理算法的符号及含义。

通过上述解决方案，可以基于SRv6实现受影响的广域网双栈流量的快速恢复，该方案主要解决了在单协议栈广域网链路失效的网络场景下，基于绕过失效链路的原则，以失效链路的上游节点作为源节点针对受影响数据流计算一条恢复路径，并利用路径编码算法得到Segment List压入数据包首部，进而依据报文处理算法对数据流报文及其转发方式进行处理，然后通过Segment的引导将受影响的数据流通过恢复路径调度至失效链路的下游节点，以此实现在尽可能减少网络重新配置的前提下，数据流仍沿着原有广域网链路进行传输。

3 实验验证与分析

通过实验环境下的仿真与验证，得出该方案可以解决SD-WAN单协议栈链路失效时的双栈流量调度问题，采用仿真平台mininet搭建测试拓扑，使用iproute2进行节点配置，控制器基于Python2.7开发实现，实验平台选择Ubuntu18.04(Linux内核4.15.0)，流量发生和性能测试工具采用Iperf和Wireshark软件。

3.1 系统仿真验证园区IPv4出口链路失效场景

场景仿真网络拓扑如图3所示。

图3 “园区IPv4出口链路失效场景”仿真拓扑Fig. 3 Simulation topology of IPv4 link failure scenario

如图3所示，“园区IPv4出口链路失效场景”的仿真拓扑由Ha和Hb2台主机、6台路由器和10条链接通过运行生成在mininet中，其中2台主机、6台路由器均支持IPv4/IPv6双协议栈，10条链接中除Ra4和Rb4链接构成IPv4广域网链路、Ra6和Rb6链接构成IPv6广域网链路外，其他均为双栈链路。

在该仿真场景中，断开Ra4和Rb4之间链接，Ha执行至Hb的Ping命令，数据包在Ra4处进行SRv6的T.Encaps压入Segment，通过仿真IPv6广域网后，向Ra6发送，并转发至Rb4进行END.DX4处理弹出Segment，还原为IPv4报文，向Hb进行转发，Hb收到来自Ha的ICMP-Echo-Request，向Ha发送ICMP-Echo-Reply。同理，Reply报文按相反方向进行处理转发，Ra4收到ICMP-Echo-Reply，即收到正确的Ping回复。通过在Ra4、Rb4进行Wireshark抓包分析验证了恢复路径的可行性，并验证了恢复路径流量引导和报文处理，实现了流量调度的目标。

为验证恢复路径网络转发的性能，在Ha和Hb之间通过iperf对网络进行测速，如图4测量结果显示链路失效时，基于SRv6的恢复路径的网络吞吐率约为19Gbps，满足中型企业园区间的网络需求。

图4 “园区IPv4出口链路失效场景”iperf吞吐率Fig. 4 Throughput of IPv4 link failure scenario

3.2 系统仿真验证园区IPv6出口链路失效场景

场景仿真网络拓扑如图5所示。

图5 “园区IPv6出口链路失效场景”仿真拓扑Fig. 5 Simulation topology of IPv6 link failure scenario

在该仿真拓扑中，仿真网络节点设备与图3相同，在该仿真场景中，断开Ra6和Rb6之间链接，Ha执行至Hb的Ping命令，数据包在Ra6处进行SRv6的T.Encaps压入Segment，转发至Ra4节点后，通过6over4隧道封装，最外层以IPv4报文头向Rb4发送,通过仿真IPv4广域网后，在Rb4节点对6over4报文头解封装，还原为SRv6报文，转发至Rb6后进行END.DX4弹出Segment，还原为IPv4报文，向Hb进行转发，Hb收到来自Ha的ICMP-Echo-Request请求，向Ha发送ICMP-Echo-Reply，即收到正确的Ping回复。通过在Ra6、Rb6进行Wireshark抓包分析验证了恢复路径的可行性，并验证了恢复路径流量引导和报文处理的处理流程实现了流量调度的预期目标。

为验证恢复路径网络转发的性能，在Ha和Hb之间通过iperf对网络进行测速，如图6测量结果显示链路失效时，基于SRv6的恢复路径的网络吞吐率约为1.4Gbps，保障了单协议栈链路失效时企业园区间的双栈网络需求。

图6 “园区IPv6出口链路失效场景”iperf吞吐率Fig. 6 Throughput of IPv6 link failure scenario

3.3 实验分析

在Mininet系统仿真实验中，不同路径和处理方式的报文转发或封装转发吞吐率如图7所示、数据包往返时延如图8所示、流量丢包率如图9所示，仿真数据分析得出如下结论：

图7 不同方式下iperf吞吐率对比Fig. 7 Throughput comparison of different forward method

图8 不同方式下往返时延对比Fig. 8 RTT comparison of different forward method

图9 不同方式下丢包率对比Fig. 9 Packet loss rate comparison of different forward method

1)链路失效时恢复路径只使用SRv6处理报文的转发速率与链路正常时IPv6路由转发的吞吐率接近，而链路失效时恢复路径通过SRv6over4处理转发的吞吐率低于另2种方式，但也基本满足中型企业园区的网络需求。

2)链路失效时恢复路径的3种报文处理方式的往返时延差异不大，经SRv6处理报文的往返时延与链路正常时IPv6路由转发的往返时延非常接近，甚至略优，而通过SRv6over4处理转发的往返时延稍大于其他两种，但平均值在0.25 ms以下，在合理范围内。

3)链路失效恢复路径的3种报文处理方式的丢包率均为0，测试数据表明单协议栈链路失效时，恢复路径的流量引导和报文处理达到了流量调度的目的，提高了双栈SD-WAN链路的服务质量。

由于报文处理流程会导致数据流报文IP报头长度增加，可能存在报文长度超过路径最大传输单元(PMTU, path maximum transfer unit)的问题，进而导致报文在传输中被分片，大幅影响传输速率。因此，可以在网络接入层对MTU进行适当限制，或通过G-SRv6(SRv6头压缩, Generalized-SRv6)[15]技术对SID长度进行压缩，以减小处理后的报文长度。

4 结 语

针对现有园区SD-WAN网络架构下，单协议栈广域网链路失效时园区双栈流量的互联互通问题，提出了一种SD-WAN架构下基于SRv6的双栈流量调度算法，该算法基于快速重路由机制，结合SRv6技术分为路径编码算法和报文处理算法两部分实现。在链路失效时，通过快速重路由机制确定恢复路径，在恢复路径的基础上，首先通过路径编码算法得出数据流添加Segment的类型，引导数据流在恢复路径正确转发传输，然后在网络各节点根据数据流报文信息利用报文处理算法确定报文的转发方式，最终保证双栈流量通过快速重路由生成的替代路由进行转发。最终，在Mininet中运行仿真实验，并使用Iperf工具进行性能测试，实验仿真结果表明，提出的DSTS算法实现了链路失效时的双栈流量调度，增加了企业园区广域网的冗余度和可靠性，提升了企业带宽利用率和服务质量。