针对有限TCAM的SDN网络灵活局部路由故障恢复

孙宇 梁毅娟

摘 要： 在软件定义网络中，使用大量的备份路径的转发规则会频繁地在交换机上进行数据流驱动，会增加带宽需求和处理延迟。对此，开发一组问题优化模型，可最小化备份路径所需的额外规则和带宽数量。由于该问题的计算复杂性，设计两个启发式算法计算备份路径：前向局部路由（FLR）和后向局部路由（BLR），从而提高TCAM和带宽的使用效率，并基于网络状态采用FLR和BLR设计了灵活自适应故障恢复框架。最后，通过在Internet 2网络拓扑上的仿真实验，显示所提算法在故障数据的抑制上要优于选取的对比算法，验证了算法性能优势。

关键词： 软件定义网络； 局部路由； 内容寻址存储器； 交换机； 备份路径； 故障恢复

中图分类号： TN711?34； TP391 文献标识码： A 文章编号： 1004?373X（2018）08?0013?04

Abstract： In software defined networks （SDNs）， the forwarding rule involving a large number of backup paths frequently drives data flow over a switch， which may increase the bandwidth requirement and result in processing delay. Therefore， a set of problem optimization models are developed to minimize the amount of extra rules and bandwidth required for backup paths. Two heuristic algorithms of forward local routing （FLR） and back local routing （BLR） are designed due to the computational complexity of the problem to compute backup paths so that the service efficiency of TCAM and bandwidth can be improved. A flexible adaptive fault recovery framework was designed based on network status by means of FLR and BLR. The simulation experiment on the Internet 2 network topology was carried out. The results show that the proposed algorithm outperforms the selected contrast algorithm in fault data suppression， and the performance advantage of the algorithm is verified.

Keywords： SDN； local routing； content addressable memory； switch； backup path； fault recovery

0 引 言

在传统网络中，交换机执行路由决策（控制功能）和数据转发（数据功能）。因其不支持可编程性，导致使用中存在等效网络带宽过度配置问题[1?2]。软件定义网络（SDN）已成为一种很有前途的网络范式，它将控制功能和数据功能分离开来，从而使得交换机具有可编程性，网络虚拟化成为可能。

为了进行路由决策，SDN依赖于在交换机中安装的转发规则。当数据流包到达时，如果交换机没有在其流程表中找到该数据流的任何规则，它将与控制器联系。大型网络如云数据中心网络的活跃数据流的数量可达到每服务器每秒10 000数据流，开关TCAM的大小无法与之相适应[3?4]。因此，提高TCAM的效率，即盡可能减少所需的TCAM数量，对于交通工程、故障管理、网络安全等非常重要。虽然研究界探索了SDN的许多优点，但对网络故障恢复机制的关注较少[5?6]。网络设备或链路故障导致包转发的延迟，即使网络中有替代路径，从而影响应用程序的性能，这可能导致供应商的收入损失。在最近的研究中，谷歌[7]报告指出利用OpenFlow交换机配置会出现0.1%～1%之间的高延迟或传输失败。

本文提出两种算法，即前向局部路由（FLR）和后向局部路由（BLR）算法，计算可实现主路径保护的备份路径。该算法因为需要的TCAM很少，因此其可以忽略TCAM大小的影响。

1 SDN故障恢复的局部重路由

1.1 转发规则和流程表

考虑到限位开关TCAM对于故障快速恢复的重要性，建议在动作设置列表（ACTION SET）中引入一个新的选项即Alternate_port（AP），如图1所示。而Default_output_port指示数据包转发到下一跳的沿主路上的输出端口，Alternate_port将用于指示在相应的链路失效的情况下，转发数据包的输出端口。其可以通过使用OpenFlow提供的开放接口Optimal action进行实现，也可以利用这个开放接口为存储备份输出端口添加额外的动作Alternate_port。

1.2 前向局部重路由

如果在主路径上存在从故障点到另一下游交换机的多个备份路径，则选择最少附加交换机数量的备份路径。通过附加开关，FLR显著降低TCAM数量的原因：

1） 通过将数据从故障点路由到主路径上的下游交换机，在主路径上使用相同的转发表规则，通过备份路径将一部分数据包转发到目的地。

2） 将备份通道上的附加交换机的转发条目限制为一个，允许所有备份路径通过附加交换机（对应于主路径的不同链路故障），并仅通过一个端口输出，避免转发循环并允许备份带宽共享。

1.3 后向局部重路由

考虑图2所示网络拓扑，源节点S1和目的节点S5间主路径是S1→S2→S3→S4→S5。当S2和S3间的链接失败时，在S2数据包报头中设置标志来标记失败数据流。标志在S2处由空心变为实心。然后采取预先计算的到目的节点的不相交链路节点备份路径，将此通信路由传回S1，例如在S2处的失败通信，将通过路径S2→S1→S8→S9→S10→S5传回目标节点。

虽然BLR简单，且复杂度低，但其在恢复中增加了额外延迟。当S4和S5最后一跳链接失败时，失败通信须沿主路径路由到源节点S1，则通过的备份路径是S4→S3→S2→S1→S8→S9→S10→S5。在大型网络中，链路越长情况越糟糕。此外，还需要在数据包头部识别失败数据流，将进一步增加路由延迟。

1.4 基于FLR的备份路径设定

令[G=N，E]表示网络拓扑图，其中N是网络交换机的节点集，E是交换机之间链路的边集。使用“节点”和“开关”表示网络交换机。利用W表示每个数据流计算的主路径集，[Wf∈W]表示数据流f的主路径。给定数据流f，其主路径为[Wf∈W]，算法1可计算临时备份路径集，表示为Bff，从而实现对数据流f的每个链接[lf∈Wf]进行保护。该算法的输入是网络拓扑G和数据流f的主路径[Wf]；算法的输出是保护流f的备份路径集Bff。

对于每个链接[lf∈Wf]，若其失效，首先确定遍历最小数量额外节点的最好备份路径，以保护低频链路。令[Slf]为数据流f的转发方向中的链接[lf]的来源。从[Slf]出发，该算法确定所有连接[Slf]的备份路径，每个[Slf]主路径上的下游节点为[Wf]，[Dlf]为[Slf]的下游节点集。算法1中第5行表示节点之间的最短路径。输出结果为链接[Slf]和下游节点[Dlf]的备份路径[Btemplf]。然后将这条路径添加到保护链路[lf]的备份路径集中，表示为[Blf]。

2 实验分析

实验平台为CPU i7?6400k、RAM 8 GB DDR4?2400、系统WIN7旗舰版。测试对象是Internet 2网络拓扑。所有结果用95%置信区间绘制。对比算法如下：

1） 基于备用端口的FLR算法（FLR?AP）；

2） 基于备用端口的BLR算法（BLR?AP）；

3） 文献[8]基于子树的组播故障检测与保护方法（SBFD）。

考虑一个边连通概率为0.6，具有30个节点的随机图。假设网络中所有链路都有1 000个带宽单元。每个数据流产生的带宽要求是均匀分布在0～20之间的随机数。在带宽有限情况下，FLR?AP，BLR?AP和本文算法的附加规则的数量均值指标的对比结果如圖3所示。图4显示了在链路发送故障时，数据到达目的地所需的平均额外跳数均值。

根据图3指标对比情况可知，本文算法所需要的附加规则的数量均值要比FLR?AP算法低30%左右。原因是，本文算法对流量的优先保护顺序是首先利用FLR备份路径，然后采用BLR备份路径，最后无保护，这种故障恢复方法更加灵活。同时，因为BLR?AP算法需要的额外规则数量最少，因此降低了本文算法所需的额外的规则数，要优于SBFD算法。但是BLR?AP算法的缺点是会增加一定的传输延迟，并且需要增加故障标记位。根据图4结果可知，在数据流较低时，本文算法与FLR算法和BLR算法在平均额外跳数均值指标上相差不大。但是随着数据流的增加，BLR算法的平均额外跳数均值指标增加非常迅速，而FLR算法的平均额外跳数均值指标增加最为缓慢，本文算法居中。原因在于当流量增加时，FLR的备份路径不可用，因此选择BLR备份路径实现对数据流的保护。实际上，本文算法所需的额外跳数均值要比BLR算法少25%左右，优于SBFD算法。

此外，还对随机图上的算法的带宽效率进行评估。图5给出4种算法使用的总带宽对比情况。图6给出4种算法的不可用数据抑制比指标对比情况，

可观察到，FLR，BLR和本文算法的备份路径的带宽共享效率分别为80%，55%和70%。其中FLR算法的带宽使用情况最佳。结果显示，本文算法在此指标上优于SBFD算法。由图6结果可知，利用本文算法的不可用数据抑制比可实现大幅降低。因此，对于带宽受限网络，当可对延迟和TCAM进行权衡时，本文算法可以接收更多的数据流，从而提高网络的传输效率。

3 结 语

本文通过从单一链路故障的备份路径限制开关TCAM进行数据流保护流的软件定义网络的容错性问题。首先定义一个优化问题，在备份路径中进行最优解求取，最大限度地减少备份链路的带宽要求和TCAM组合成本。同时开发一个高效的局部重路由方法，考虑开关记忆约束TCAM的SDNS快速故障恢复。使用这种方法，本文开发了两种算法即FLR和BLR，有效解决了备份路径数据流保护过程中的SDN交换机TCAM的大小约束问题。

注：本文通讯作者为梁毅娟。

参考文献

[1] LEI Ding， WEI Xingzheng. Network?based practical consensus of heterogeneous nonlinear multi?agent systems [J]. IEEE transactions on cybernetics， 2017， 47（8）： 1841?1851.

[2] KOBAYASHI K， HIRAISHI K. Design of probabilistic Boolean networks based on network structure and steady?state probabilities [J]. IEEE transactions on neural networks &； learning systems， 2017， 28（8）： 1966?1971.

[3] YANG E Z， ZHANG L K， YAO Z， et al. A video conferencing system based on SDN?enabled SVC multicast [J]. Frontiers of information technology &； electronic engineering， 2016， 17（7）： 672?681.

[4] HUANG T， YU F R， ZHANG C， et al. A survey on large?scale software defined networking （SDN） testbeds： approaches and challenges [J]. IEEE communications surveys &； tutorials， 2017， 19（2）： 891?917.

[5] LOPES F A， SANTOS M， FIDALGO R， et al. A software engineering perspective on SDN programmability [J]. IEEE communications surveys &； tutorials， 2016， 18（2）： 1255?1272.

[6] NGUYEN V G， DO T X， KIM Y H. SDN and virtualization?based LTE mobile network architectures： a comprehensive survey [J]. Wireless personal communications， 2016， 86（3）： 1401?1438.

[7] KANG S， YOON W. SDN?based resource allocation for heterogeneous LTE and WLAN multi?radio networks [J]. Journal of supercomputing， 2016， 72（4）： 1342?1362.

[8] RAJA V R， LUNG C H， PANDEY A， et al. A subtree?based approach to failure detection and protection for multicast in SDN [J]. Frontiers of information technology &； electronic engineering， 2016， 17（7）： 682?700.

[9] BHOLEBAWA I Z， JHA R K， DALAL U D. Performance analysis of proposed openflow?based network architecture using mininet [J]. Wireless personal communications， 2016， 86（2）： 943?958.

[10] SIQUEIRA M A， HOOFT F N， OLIVEIRA J R， et al. Providing optical network as a service with policy?based transport SDN [J]. Journal of network and systems management， 2015， 23（2）： 360?373.