基于拥塞及内存感知的SD-WAN故障恢复.pdf

基于拥塞及内存感知的 SD-WAN 故障恢复庄捷1,2,张奇支1,2,郑伟平1,2,赵淦森1,21(华南师范大学计算机学院,广州510631)2(广州市云计算安全与测评技术重点实验室,广州510631)通信作者:张奇支,E-mail:摘要:在软件定义广域网(SD-WAN)中,链路故障会导致大量丢包,严重时会引起部分网络瘫痪.现有的流量工程方法通过在数据平面提前安装备份路径能够加快故障恢复过程,但在资源受限的情况下难以适应各种网络故障情况,从而使恢复后的网络性能下降.为了保证网络在故障恢复之后的性能并减少备份资源的消耗,本文提出一种基于拥塞及内存感知的主动式故障恢复方案(CAMA),不仅能够将受影响数据流进行快速重定向,还能实现负载均衡避免恢复后潜在的链路拥塞.实验结果表明,与已有方案相比,CAMA 能有效利用备份资源,在负载均衡上有较好的性能,且仅需少量备份规则即可覆盖所有单链路故障情况.关键词:软件定义网络;软件定义广域网;故障恢复;负载均衡;备份资源引用格式:庄捷,张奇支,郑伟平,赵淦森.基于拥塞及内存感知的 SD-WAN 故障恢复.计算机系统应用,2023,32(9):106114.http:/www.c-s- Failure Recovery Based on Congestion and Memory AwarenessZHUANGJie1,2,ZHANGQi-Zhi1,2,ZHENGWei-Ping1,2,ZHAOGan-Sen1,21(SchoolofComputerScience,SouthChinaNormalUniversity,Guangzhou510631,China)2(KeyLaboratoryonCloudSecurityandAssessmentTechnologyofGuangzhou,Guangzhou510631,China)Abstract:Insoftware-definedwideareanetworks(SD-WANs),linkfailurescanresultinsubstantialpacketloss,leadingtopartialnetworkparalysisinseverecases.Theexistingtrafficengineeringapproachescanexpeditefailurerecoverybyinstallingbackuppathsinadvanceonthedataplane.However,itisdifficulttoadapttovariousnetworkfailureswithlimitedresources,whichdegradesthenetworkperformanceafterrecovery.Tomaintainthenetworkperformanceafterfailurerecoveryandreducetheconsumptionofbackupresources,thisstudyproposesaproactivefailurerecoveryschemebasedoncongestionandmemoryawareness(CAMA),whichcannotonlyredirecttheaffecteddataflowsquicklybutalsorealizetheloadbalancingtoavoidthepotentiallinkcongestionafterrecovery.Experimentalresultsdemonstratethatcomparedwithexistingschemes,CAMAcaneffectivelyutilizebackupresources,performswellinloadbalancing,andrequiresonlyasmallnumberofbackuprulestocoverallsingle-linkfailurescenarios.Key words:software-definednetworking(SDN);software-definedwideareanetwork(SD-WAN);failurerecovery;loadbalancing;backupresource1引言 1.1 研究背景及介绍软件定义网络(software-definednetworking,SDN)解耦了控制平面和数据平面,使得逻辑集中的控制器拥有网络拓扑的全局视图,能够决定底层设备的转发行为并监控各交换机的状态1.利用强大的管控能力,计算机系统应用ISSN1003-3254,CODENCSAOBNE-mail:ComputerSystems&Applications,2023,32(9):106114doi:10.15888/ki.csa.009222http:/www.c-s-中国科学院软件研究所版权所有.Tel:[phone]基金项目:国家重点研发计划(2019YFB1804003);广东省重点领域研发计划(2019B010137003);广东省科技基金(2016B030305006,2018A07071702);广州市科技基金(201804010314)收稿时间:2023-02-22;修改时间:2023-03-22;采用时间:2023-03-30;csa 在线出版时间:2023-07-17CNKI 网络首发时间:2023-07-18106系统建设SystemConstruction控制器能够收集交换机和链路的状态信息,为网络建立合理的转发方案,提升网络的服务质量.由于硬件设备的内部冗余,节点故障的概率远低于链路故障的概率,而多链路故障的概率又远低于单链路故障概率2.但即使是单链路故障,其影响也不容忽视.软件定义广域网(software-definedWAN,SD-WAN)中通常使用流量工程(trafficengineering,TE),也就是通过动态路由选择和带宽分配实现网络可用性和有效资源间的平衡.SDN 中两种最主要的故障恢复方法分别是主动式(proactive)和反应式(reactive)恢复3.反应式恢复方法在故障发生之后生效,控制器根据数据平面发送的故障消息和状态做出决策,为受影响流量计算备份路径.因此在故障恢复过程中,控制器与交换机之间的通信、新路由的计算以及设备上转发规则的配置等过程,会为故障恢复带来较大的开销和时延.相反,主动式方法在故障发生前为各种可能的故障制定备份策略,提前在相关交换机上安装备份规则,从而避免了恢复过程中控制器的介入.通常来说主动式恢复方法需要提前占用交换机更多的存储空间.1.2 相关工作在 SDN 数据平面的故障恢复研究领域已有大量的研究成果,主要采用了各种主动式恢复方案进行流量的重定向,以减少故障发生时产生拥塞的概率.Liu等人4提出一种具有 k 个并发故障容错能力的链路故障恢复机制 FFC.一旦发生故障,受影响流量将通过备份路径进行传输.然而方案需要链路预留一定容量,容易导致资源的浪费.Shojaee 等人5提出的 Safeguard方案为受影响的数据流遍历所有备份路径,检查链路剩余容量,通过贪心算法将数据流重定向至剩余资源更充足的备份路径.这种方法的目的是在多路径传输中尽量避免碎片化造成的资源浪费,但是也可能导致链路上的带宽资源耗尽,因为其没有考虑网络的动态性.Zheng 等人6的 Sentinel 方案则不需要保留空闲容量,方案通过提前安装备份路径并解决 ILP 模型来重路由流量,同时最小化最大链路利用率.这些基于数据流的解决方案均存在缺陷,即在选择路径和分配流量时并没有考虑交换机内存的限制.交换机内存耗尽会增加表查找和更新时间,导致大量丢包7.针对交换机容量的限制,Wang 等人8提出一种基于共享环的备份路径方案.方案通过节点重要性的排序选举出一组核心交换机,并在这组交换机中定义共享环.由于共享环被所有备份路径共享,因此环中备份流表项复用率高.该方案在保证故障恢复时延的同时,在备份资源消耗方面具有很好的性能.但是共享环不能规避恢复后的链路拥塞风险.而 Wang 等人9、Barakabitze 等人10、Tian 等人11在流量工程中采用 SegmentRouting 的思想,通过在入口节点为数据包头添加有序的路径信息,有效地减少了交换机内存的消耗.由于其技术特点,所采用的方法引入了报文头开销与更多的延迟.考虑到网络的动态性,Wang 等人12提出了一种基于反应式和主动式策略协同的链路故障恢复机制,首先保证故障发生后网络连通性的即时恢复,再根据当前网络状态信息对备份路径进行调整.该方案通过反应式和主动式策略的协同工作,实现了恢复时间和资源利用上的有效平衡.1.3 基于拥塞及内存感知的链路故障恢复考虑到数据平面故障恢复的需求,以及当前研究存在的一些不足,本文提出一种基于拥塞及内存感知的主动式故障恢复方案,命名为 CAMA(congestionandmemoryawareness).CAMA 方案使用较少的备份规则即可实现所有链路的备份路径配置,完成故障恢复的同时避免潜在的链路拥塞,从而实现负载均衡.本文工作的贡献在于:(1)提出基于链路的保护方法,使用 VLAN 标签聚合故障链路流量,减少交换机流表项条数.(2)提出将部分受故障影响的数据流提前导回到原主路径的流表设计方案,减少链路带宽的消耗.(3)提出一种基于拥塞及内存感知的建模方法,并通过启发式算法在合理时间内求解.通过实验评估,CAMA 方案在节省备份资源上表现出了较优的性能,能有效减少交换机内存的消耗,避免故障恢复后的链路拥塞.2问题描述本文的故障恢复方案在每个 TE 间隔内包括两个步骤:(1)为每个链路故障计算备份路径,下发相应流表项和组表项至交换机;(2)当发生链路故障时交换机自动切换到备份路径.本文的重点是故障链路备份路径的计算,以实现负载均衡和资源优化.本节首先通过一个简单示例展示 CAMA 的整体设计思路和优势(如图 1 所示).2023年第32卷第9期http:/www.c-s-计 算 机 系 统 应 用SystemConstruction系统建设107S1S3S6S7S8S2S1S5S6S3S3S6S7S8S5S4S6S1S2S7S8S1S7S2S5S4S8S4S3T2T3T3T1T2T2T3T1S2S5S4T1221(a)数据流的主路径传输情况(b)链路故障情况方案的传输路径(d)链路故障后 CAMA方案的传输路径12222221111(c)链路故障后 Safeguard、Sentinel图 1简单示例为简单起见,将两个通信节点之间产生的流量合称为一条数据流.考虑到负载均衡因素,该数据流会在这两个通信节点之间的多条路径上传输(称之为主路径),每条路径由多段链路组成.CAMA 会为网络中的每一段链路计算备份路径.备份路径通过快速恢复组表(OpenFlowfastfailovergrouptables,FF)进行配置,并在发生故障时完成检测和即时恢复.在 SND 交换机中,一个 FF 组表项包含一系列的动作桶,每个动作桶关联一个交换机端口,负责监测端口的状态并执行相应的动作.如果监测到端口无法使用,数据包将被快速切换到列表中正常工作的下一个动作桶.在图 1(a)的示例拓扑中有 8 个交换机,每条链路容量均为 10Gb/s.考虑从 S1到 S8带宽需求为 10Gb/s的数据流 f,路径 T1,T2是控制器为 f 计算得到的两条主路径.当 S3和 S6之间的链路发生故障时,路径 T2上传输的流量将中断,设相应的备份路径为 T3,如图 1(b)所示.表 1 展示了示例中的路径信息.S1中通过选择组表(OpenFlowSELECTgrouptables,SELECT)实现流量的权重划分.SELECT 组表包含一系列动作桶,通过为不同端口设定权重来实现多路径传输,具体实现办法可以参考 Safeguard5.在示例中每条路径负载为5Gb/s,即权重设定为(1/2,1/2).表 1图 1 中路径的描述路径Id路径类型标号路径信息1primaryT12primaryT23backupT3根据 SafeGuard 及 Sentinel5,6中的算法,故障发生后的传输路径如图 1(c).此时交换机 S3上相关的流表和组表如表 2 所示.当它监测到首选端口状态变为down 后,会根据下一个动作桶的配置将数据包转发到备份路径 T3上.然而,这种基于数据流的备份方法产生的流表项会随数据流的数量增加而剧增.本文从另一个角度出发,考虑基于链路的保护方法,即在故障节点处为受影响的数据包添加故障标签(VLANID),同时在备份路径的每个节点上增加一条对应的流表项.通过匹配流表项中指定的 VLAN 字段,可以将中断的流聚合到同一流表项中.这样,所有受影响的数据包在备份路径上传输时,只需匹配一条流表项即可完成重定向.因此,本文提出的基于链路的保护方法能够有效地节省交换机存储空间13.本例中针对交换机 S3,它修改后的组表项如表 3.在备份路径的设计上,文献 5,6都主张将数据流从故障链路的入口节点尽快重定向到出口节点,而不是重新规划一条从故障链路的入口节点到终点的新路径.这是因为将数据流重定向至原工作路径能减少对其他链路上正常流量的影响,避免产生拥塞14.本文我们仍然沿用这种思路,并对其进行优化.表 2图 1 示例中交换机 S3的流表和组表匹配域指令SrcAddrDstAddrTagPri流表S1S81Group4.1组表组Id组类型动作桶Gr4.1FastFailoverBucket1:watch_port=1,output=1Bucket2:watch_port=2,output=2表 3交换机 S3修改后的组表组Id组类型动作桶Gr4.1FastFailoverBucket1:watch_port=1,output=1Bucket2:watch_port=2,TagidoflinkS3S6,Gr4.2在本例中,主路径 T2与备份路径 T3存在重叠,会使数据流在 S6和 S7之间的链路上往返传输,从而浪费了带宽.针对这个问题,本文提出改进算法,让合适的数据流在备份路径上提前找到出口,以减少在往返链路上的传输.我们的做法是让相关数据包在相交节点处匹配到高优先级的流表项,提前去除故障标签.去除标签的数据包通过多级流表回环,继续匹配属于主路计 算 机 系 统 应 用http:/www.c-s-2023年第32卷第9期108系统建设SystemConstruction径的工作流表项,从而在备份路径中提前找到出口并完成后续的传输,传输路径如图 1(d).本例中,S7是我们要找的出口节点,它的转发规则如表 4 所示.表 3 与表 4 中动作指向的组表项 Group4.2、Group7.2 类型为 SELECT,由后续的备份路径选择算法提供.表 4图 1 示例中交换机 S7的流表和组表匹配域指令SrcAddr DstAddrTagPri流表IdoflinkS3S61Output:1S1S81Gr7.1S1S8IdoflinkS3S62Poptag,Gr7.1组表组Id组类型动作桶Gr7.1FastFailoverBucket1:watch_port=2,output=2Bucket2:watch_port=1,TagIdoflinkS7S8,Gr7.2综上所述,CAMA 方案在为故障链路计算备份方案时需要考虑两点:(1)如何在可用路径中选取合适的备份路径并计算权重;(2)如何为受影响流量在备份路径上找到出口,以降低链路利用率.3系统建模本节将 SD-WAN 中的单链路故障恢复问题表述为一个混合整数线性规划(mixed-integerlinearpro-gramming,MILP)问题,所提出的解决方法将在第 4 节详细阐述.3.1 网络描述G=(V,E)V=1,2,nE(i,j)Eci,jfbffPffPfeQep QePff本文将 SDN 网络表示为一个有向图,记作图.其中为网络中 SDN 交换机节点的集合,为网络中边的集合,每条链路的链路容量为.两个通信节点之间的数据流记为,带宽需求为.数据流 在入口交换机处经过权重划分后在不同的路径上传输.这些不同路径的集合记为,称之为 的主路径集合.我们约定中的路径彼此不存在链路重合的情况.本文主要考虑单链路故障,此时故障将影响经过该链路的所有数据流.当链路 发生故障时,假设存在一个候选路径集,其中每条路径都不包含故障链路且彼此不相交,使得流量能从故障链路的入口节点重定向至出口节点.由于中的路径彼此链路不重合,因此故障发生时最多影响 的一条主路径.由于经过故障链路的流可能不止一条,本文将经过FeQeee该故障链路的所有数据流视为一条聚合流.根据后续的备份路径选择算法,集合中的一条或多条路径将被选中为链路 发生故障时的备份路径,并根据权重对链路 上的数据流进行重定向.本文用到的主要符号如表 5 所示.表 5主要符号及意义符号描述G=(V,E)VE包含节点集 和链路集 的网络图Pff数据流 的主路径集合Qee链路 的备份路径集合Fee链路 故障时受影响的数据流集合Fe链路 故障时不受影响的数据流集合bff数据流 的带宽需求ci,j(i,j)E链路的带宽容量ti,j(i,j)E链路的已用带宽Tcii V节点的TCAM容量rij,p(i,j)p示性函数,链路时等于1si,pi p示性函数,节点时等于1oi,fif示性函数,节点 是 的出口时等于1li,pi pp节点在路径 中的位置(跳数)链路带宽利用率最大值xf,pfp数据流 在路径 上分配的权重 3.2 变量与参数xf,p 0,1oi,fxf,ppfoi,fifeFexFe,p,p Qeoi,f,f Fe在发生故障时需要将受影响的数据流分配到可用备份路径上,并在备份路径上寻找出口节点.因此本文定义一个决策变量和一个示性函数.大于 0 时既表示路径 被选中为数据流 的传输路径,同时也表示数据流在该路径上分配的权重.等于 1 时表示节点 是数据流 在备份路径上的出口节点.CAMA 方案的关键就是针对故障链路,为受影响的聚合流计算所有的,以及对应的节点集合.(i,j)Eti,jrij,psi,p(i,j)ip本文将链路的已使用带宽记为,同时使用示性函数与分别表示链路与节点 是否属于路径.rij,p=1,if(i,j)p0,otherwise(1)si,p=1,if i p0,otherwise(2)3.3 约束条件ci,j(1)链路和节点容量限制:约束式(3)表示链路已使用带宽不能超过设定的阈值,即参数 与链路容量的乘积.表示网络中链路带宽利用率的最大值.故2023年第32卷第9期http:/www.c-s-计 算 机 系 统 应 用SystemConstruction系统建设109(i,j)teei障恢复后链路已使用带宽包含两部分:受故障影响的数据流在包含该链路的备份路径上分配的带宽大小,与不受故障影响的数据流在包含该链路的主路径上分配的带宽大小.表示链路 发生故障前的已用带宽.约束式(4)用于防止交换机使用的存储空间超过容量上限.与链路带宽约束类似,交换机 已使用的存储空间同样包含两部分:每种故障情况下交换机新增的备份流表项,以及交换机上已有的流表项.pQetexFe,prij,p+fFpPfbfxf,prij,p ci,j,(i,j)E(3)eEpQesi,p1+fFeoi,f+fFpPfsi,p Tci,i V(4)pxFe,p=0 xFe,p(2)数据流限制:约束式(5)用于满足数据流的带宽需求,同时也说明当路径 未被使用时,否则必须是一个正数.pQexFe,p=1 xFe,p 0,e E(5)3.4 目标函数在满足约束条件的情况下,目标函数(6)追求在完成故障恢复的同时最小化最大链路带宽利用率.需要注意的是,在备份路径上提前出口的数据流数量越多,新增带宽需求越少,但备份流表项数量会增多.min(6)本文的故障恢复方案作为一个 MILP 问题,已被证明为 NP 难15,且在实践运行中需要花费较长时间.而流量工程要求的时间间隔一般不超过 5min,因此本文提出一种启发式恢复算法,来保证故障恢复问题能够在合理时间内解决.4CAMA 方案本节主要展示所提出的启发式算法.算法包含 3 个部分:计算可用路径影响程度并排序;在已排序路径中选择备份路径;在备份路径中为数据流寻找出口节点.4.1 路径的影响程度本文采用影响程度描述一条路径的性能,该指标使用一个三元组来表示,包括链路负载、跳数、交换机负载.所使用的 3 个参数都与路径传输性能以及网络资源调度相关.CAMA 方案使用路径中的最大链路利用率表示链路负载,用路径中的最大流表项数量来表示交换机负载.KK=|Qe|根据上述的评价参数,CAMA 方案构建一个关于条候选备份路径的影响程度评价矩阵,其中.A=a11a12a13a21a22a23.apq.aK1aK2aK3,p=1,2,K;q=1,2,3(7)AapqpqK=1Z评价矩阵 中,代表第 条候选路径的第 个评价参数的数值.当时,唯一路径将被直接选中作为备份路径.由于每个评价参数的单位不同,本文采用最大最小归一化对参数进行无量纲化处理,得到标准化评价矩阵.Z=z11z12z13z21z22z23.zpq.zK1zK2zK3,p=1,2,K;q=1,2,3(8)zpqa.qz.q其中,的获取方式如式(9).当某列参数在所有路径上的值都相等时,赋予相同的数值,此时路径在此参数上没有区别.zpq=apqmin(a.q)max(a.q)min(a.q),max(a.q),min(a.q)0,max(a.q)=min(a.q)p=1,2,K;q=1,2,3(9)impp方案定义路径评价指标表示候选路径 的性能,如式(10)所示:imp=133q=1qzpq,p=1,2,K(10)=1,0.8,0.5其中,代表每个参数的权重.根据上述讨论,参数分别为链路负载、跳数、交换机负载.为保证路径的传输性能,根据各评估参数的重要性以及实际运行中各参数产生的效果,本文设置.4.2 备份路径选择算法 1 展示了单链路故障情况下备份路径的选择过程.算法将移除故障链路后的网络拓扑、受影响数据流以及可用候选路径作为输入.算法 1.备份路径选择算法G=(V,Ee)FeQe输入:网络拓扑;聚合流;可用路径xFe,p,pQe输出:路径分配权重计 算 机 系 统 应 用http:/www.c-s-2023年第32卷第9期110系统建设SystemConstructionimp,pQe1.计算路径的影响程度impQe2.根据将升序排序Cap res1 sum0 temp03.,pQe4.fordoCap=Capcapp5.sum=sum+capp6.cappCap7.fordoptecappsump8.将带宽分配至路径得到的最大链路利用率temp=max(temp,p)9.restemp10.ifthenres=temp11.xFe,p=Capsum12.impCappcappCapsum算法 1 首先根据影响程度对候选路径进行升序排序,排序后的候选路径同时代表着路径传输性能的次序.算法定义一个集合,用于存储已遍历路径的瓶颈剩余带宽.依次遍历每条候选路径,将该路径的瓶颈链路剩余带宽(计算方法见式(11)加入集合中,并在变量中累加(见算法 1 中的第 36 行).capp=min(i,j)p(ci,jti,j)(11)p=max(i,j)p(ti,jci,j)(12)Capcapp/sumteppptemptempresresxFe,pCapsum在算法 1 的内层循环中(见算法 1 中的第 79 行),根据集合中已遍历路径的剩余带宽的比例分配带宽,计算分配流量后路径的最大链路利用率(计算方法见式(12),循环结束后得到已遍历路径中的最大值并保存在变量中,用于后续的比较.在内层循环之后,当经过流量分配得到的最大链路利用率小于中间结果,说明已计算出使得最大链路利用率更小的权重分配方案,此时算法 1 更新并修改路径权重集合,其中更新的值为集合中的每一项与的比值(见算法 1 中的第 1012 行).4.3 数据流出口位置计算f Fe算法 2 展示了备份路径中数据流的出口位置计算过程,其将算法 1 中的权重集合作为输入,在权重值非 0 的备份路径中为数据流寻找出口位置.算法 2.数据流出口位置计算策略G=(V,Ee)eFeQe输入:网络拓扑;故障链路,聚合流;可用路径oi,f,fFe输出:数据流出口节点集合fFe1.fordopf2.数据流 受影响的主路径i1,i2e3.链路 的入口节点及出口节点pQe4.fordoxFe,p=05.ifthen6.breakp=pi1,i27.ip8.fordosi,p=1li,pli2,p9.ifandthenoi,f=110.oi,f=oi,foi,f11.12.breakf Feppfoi,fli,pipf Feoi,f对于数据流,由于主路径之间链路不相交,故只有一条主路径受影响.算法 2 在获取路径后遍历备份路径,寻找主路径与备份路径的相交节点(见算法 2 中的第 412 行).当节点相交并且该节点在主路径中所处的位置在故障链路之后,算法 2 将该节点设置为数据流 的出口节点,即将置 1(见算法 2 中的第 912 行).由于本文采用有向网络,为防止出现环路,算法 2 选取的出口节点在主路径中处于故障链路之后.算法中表示节点 在路径 中所处的位置(跳数).算法 2 最终得到链路发生故障的情况下,数据流的出口位置集合.5实验评估本文通过仿真实验来评估 CAMA 方案的性能,包括故障恢复后的链路利用率、备份路径长度、数据流在备份路径上提前找到出口的概率、备份流表项数量等指标.5.1 实验设置本文将 CAMA 方案编写成 Python 应用部署在SDN 控制器 Ryu(版本 4.34)上,数据平面采用 Mininet(版本 2.3.0)实现,所有的实验都在一台 3.20GHzCPU 和 8GBRAM 的机器上运行.本文考虑两个网络拓扑:GoogleB416(12 个节点,38 条链路)与 ATT17(25 个节点,112 条链路).每个节点是一个CPqD18交换机实例,链路容量被设置为 1Gb/s 并且包含 1ms 时延,实验中每个交换机连接一个主机.本文通过与现有的 SD-WAN 故障恢复方案 SafeGuard和 Sentinel 进行对比,验证 CAMA 方案的有效性.当发生链路故障时,Sentinel 致力于最小化最大链路利用率,然而没有考虑备份路径长度与交换机有限的存储空间;而 SafeGuard利用贪心算法选择剩余带宽更多的备份路径,容易导致潜在的链路拥塞.实验通过 iperf 工具在数据平面产生 UDP 流量,并通过调整数据流的数量进行多次比较.2023年第32卷第9期http:/www.c-s-计 算 机 系 统 应 用SystemConstruction系统建设111除非特别说明,每条流的速率都是设定的 50Mb/s.实验结果基于多组实验数据的平均值.5.2 链路利用率实验评估不同方案在完成单链路故障之后,恢复结果对整体网络利用率的影响.实验分别为 B4 以及ATT 网络拓扑设置了 60 和 200 条数据流,并在传输过程中使用 link-down 命令模拟链路故障,计算恢复后活跃链路的利用率.图 2 展示了故障后不同方案的活跃链路利用率的累积概率分布(CDF),可以看到 CAMA对流量负载的分配比 Sentinel 和 SafeGuard 更加均匀.在图 2(a)中,所有方案都没有产生链路满载,在 B4 拓扑中 CAMA 的所有链路利用率都小于 60%.而 Safe-Guard 中接近 20%的链路利用率大于 80%,在 Sentinel中这个数值为 28%.图 2(b)中数值差距进一步扩大.由于数据流数量的增加,3 种方案在 ATT 拓扑中的链路利用率都有不同程度的提高.在 SafeGuard 中,链路利用率大于 80%的链路约有 40%,在 Sentinel 中数值提升至 57%,而 CAMA 将这个数值降低至 2%.000.20.20.40.40.60.60.80.81.01.0(a)B400.20.40.60.81.0(b)ATTCDF00.20.40.60.81.0CDFCAMASafeGuardSentinelCAMASafeGuardSentinelLink utilizationLink utilization图 2B4 及 ATT 拓扑的链路利用率累积概率分布经过分析,CAMA 与 SafeGuard、Sentinel 之间实验数据差异较大的原因有:(1)在 SafeGuard 中,主路径没有考虑到环路的存在,并且在计算过中采用了与备份路径类似的贪心算法,按照数据流带宽需求从高到低进行分配,未考虑整体最优的情况;(2)Sentinel 允许主路径之间链路相交,由于主路径与备份路径均采用基于数据流的计算方法,且未考虑路径的长度,部分节点的存储空间已经满载,导致大量数据包的查表时间增加;(3)在 CAMA 中,所选主路径不存在环路,并且在计算过程中考虑当前路径负载以及路径长度;(4)CAMA 根据路径性能选取备份路径,并且部分数据流在备份路径上提前找到出口,有效节省带宽.这说明CAMA 具有负载均衡的效果以及较优的实用性.5.3 路径延伸备份路径越长,故障恢复的时延就会越大,对活跃链路的影响也会越大.备份路径长度直接影响了恢复后网络的整体性能.实验通过调整数据流的数量,评估随机产生链路故障后不同方案备份路径的延伸长度19,其中延伸长度为数据流使用的最长备份路径长度与可能的最短路径长度之间的比值.实验结果中误差棒上下限为不同组实验中结果的最大和最小值,每组实验在运行 20 次后取平均值.图 3 展示了两种拓扑中不同数据流数量的平均路径延伸,可以看出 CAMA 与其他方案的结果具有相反的变化趋势.在 B4 拓扑中,如图 3(a)所示,当数据流数量为 20 时 CAMA 中备份路径延伸的数值大于另两种方案,而当数量增加到 40 时CAMA 在备份路径延伸上已经优于对比方案.特别是数量增加到 60,CAMA 与 SafeGuard 相比数值减少了20%(1.15 比 1.38),而与 Sentinel 相比减少了 42%(1.15 比 1.64).在 ATT 拓扑中也有类似的趋势,图 3(b)显示当数据流数量超过 120 时,CAMA 备份路径延伸的数值优于另两种方案.当数量为 200 时,CAMA 与SafeGuard、Sentinel 相比数值分别减少了约 25%和38%.CAMA 在数据流数量较少时,数据流在备份路径上提前出口的概率较小,使得备份路径较长.而随着数据流数量增加,数据流提前出口的概率增大,备份路径长度减少.在 SafeGuard 与 Sentinel 中,随着数据流数量增加,网络中的链路利用率也会增加,为了降低恢复计 算 机 系 统 应 用http:/www.c-s-2023年第32卷第9期112系统建设SystemConstruction后的链路利用率,只能选择更多的备份路径,从而造成了 CAMA 与对比方案的不同变化趋势.实验说明,在路径延伸方面,CAMA 在数据流数量较多的网络中表现更优.Path stretch1.81.61.41.21.0CAMASafeGuardSentinelPath stretch1.81.61.41.21.0CAMASafeGuardSentinel2030405060(a)B4(b)ATT4080120160200Number of flowsNumber of flows图 3不同方案的平均路径延伸 5.4 提前出口数据流及备份规则的数量本节研究 CAMA 方案中对网络整体性能影响较大的因素,如数据流提前出口的概率,以及交换机上新增的备份规则数量.在评估数据流提前出口概率的实验中,拓扑规模及数据流数量设置同第 5.3 节,即在 B4 拓扑中实验组别对应的数据流数量分别为(20,30,40,50,60),在ATT 拓扑中对应的数据流数量分别为(40,80,120,160,200).实验结果取 10 次运行的平均值,如表 6 所示.表 6不同实验组别的数据流提前出口概率(%)拓扑B416.1717.2217.9818.6219.38ATT11.2814.416.2518.5919.16可以看出在相同拓扑规模下,随着数据流数量的增加,数据流提前出口的概率随之增加;在不同规模拓扑下,拓扑规模越大数据流提前出口的概率越小.这是因为当拓扑扩大时,备份路径与主路径相交的概率降低,而当数据流数量增加时,备份路径与主路径相交的概率也会上升.在评估故障恢复所需备份规则数量的实验中,规模设置同第 5.2 节,结果如图 4 所示.在有效保护每一条链路故障的情况下,每个交换机只需增加数十条备份规则,有效节省了交换机有限的存储空间.6结束语本文主要围绕 SDN 数据平面的故障恢复问题展开讨论,总结已有方法存在的局限性,并提出了一种基于拥塞及内存感知的主动式故障恢复方案 CAMA.该方案首先将候选路径进行排序,然后计算最优的备份方案并为数据流设置出口位置,以实现恢复后的负载均衡并减少交换机的资源消耗.CAMA 方案在不同拓扑中的负载均衡效果优于对比方案,能有效节省带宽;在路径延伸上,CAMA 方案更适用于数据流数量较多的网络,在少量数据流的网络中没有优势;CAMA 在节省备份资源上表现出了较优的性能,仅需增加数十条备份转发规则即可覆盖所有单链路故障情况.综上所述,本文提出的 CAMA 方案具有一定的实用性及适用性.CDF1.00.80.60.40.200B4ATT10203040506070Number of backup rules required图 4交换机备份规则数量累积概率分布参考文献AliJ,LeeGM,RohBH,et al.Software-definednetworking12023年第32卷第9期http:/www.c-s-计 算 机 系 统 应 用SystemConstruction系统建设113approachesforlinkfailurerecovery:Asurvey.Sustainability,2020,12(10):4255.doi:10.3390/su12104255FarhadyH,LeeH,NakaoA.Software-definednetworking:Asurvey.ComputerNetworks,2015,81:7995.doi:10.1016/net.2015.02.0142Fonseca PC,Mota ES.A survey on fault management insoftware-defined networks.IEEE Communications Surveys&Tutorials,2017,19(4):22842321.doi:10.1109/COMST.2017.27198623LiuHH,KandulaS,MahajanR,et al.Trafficengineeringwithforwardfaultcorrection.Proceedingsofthe2014ACMConferenceonSIGCOMM.Chicago:ACM,2014.527538.doi:10.1145/2619239.26263144ShojaeeM,NevesM,HaqueI.SafeGuard:Congestionandmemory-awarefailurerecoveryinSD-WAN.Proceedingsofthe16thInternationalConferenceonNetworkandServiceManagement.Izmir:IEEE,2020.17.doi:1