复杂网络生存遍历算法的研究

张满宇

[摘           要]  为应对大数据对网络服务质量（QoS）的要求，复杂的软件定义网络得以部署。然而该网络却因缺乏高效的风险评估频现安全问题。为此，构思一种生存遍历算法，旨在提高复杂网络体系风险的规避能力。算法通过为子网体系构建数学模型，并从全局角度建立目标遍历策略来实施风险规避，同时对风险规避后的潜在风险再次建模开展评估以确保全网生存性。测试表明，生存遍历算法各项指标表现较为显著，具有良好的全局性。

[关    键   词]  复杂网络;失效;生存;计算;评估

[中图分类号]  TN915.07         [文献标志码]  A            [文章编号]  2096-0603（2019）32-0001-03

目前关于软件定义网络体系稳健性的评估主要围绕转发层面的交换单元内部的流表项来开展。虽有部分研究也针对控制层面的稳健性来开展，但因缺乏全局性而收效甚微。以复杂网络优化算法为例，该算法首先为每个子网体系内定义一个主用控制单元同时定义一个保护控制单元。当某一个子网体系内的主用控制单元失效，则该子网体系内的所有交换单元接入本子网体系内保护控制单元。如果某一个子网体系内的两个控制单元均失效，则遍历其他子网体系并将本子网体系内失效控制单元管辖下的交换单元接入该正常的子网体系。要是子网体系中的主用控制单元均失效，则遍历出最轻载的那个备用控制单元实现交换单元接入。从应用角度分析，传统的优化思想的确改善了应用层业务QoS，但这需以网络开销为代价。故本文从全局优化角度提出一种有效降低网络开销和资源消耗的生存策略。

一、复杂网络体系下的生存思想

为避免传统复杂网络优化算法定义的冗余备用控制单元对全网开销资源造成的浪费，本文提出的复杂网络体系生存算法不再为每一个子网体系提供主备控制单元切换方案，改由将相邻子网体系内的控制单元定义为异常子网体系失效控制单元的备用接入方案。在实施接入之前生存算法遍历全局子网体系内的控制单元计算出待接入控制单元组的权值大小并排序。然后根据权值从大到小对异常子网体系内失效控制单元管辖下的交换单元组实施新的接入，并分析接入新控制单元后该新控制单元的数据流量载荷程度。若重载则遍历权值低一级的子网体系内的新控制单元实施接入并再次分析新控制单元的数据流量载荷程度，以此类推直至接入到合适载荷程度的新控制单元。当失效控制单元管辖下的交换单元所接入的新控制单元并未出现超载，则将当前新控制單元视为本轮生存遍历算法的解决方案。

根据生存算法的思路[1]，假设为一个复杂的软件定义网络定义1个异常子网体系和n个正常子网体系，其中将正常子网体系记作：SN={SN1，SN2，…，SNn}。整个复杂网络体系下的每个SN内均存在一个唯一的控制单元记作C={C1，C2，…CL…Cn，Cn+1}。失效控制单元管辖下的交换单元组记作LE={LE1，LE2，…，LEF}。当复杂网络体系在承载全业务时遭遇到数据流量载荷失效情形，此时交换单元将向其所属控制单元提交规模为Nq的策略请求，控制单元须对此次提交的请求做出计算响应，并将策略计算结果通过南向接口下发给交换单元以便其内存流表及时执行更新操作。将第L个控制单元CL受理第F个交换单元LEF的计算请求所需的处理能力定义为Nq·■。其中■为LEF向CL提交请求的路由代价。同时定义除失效控制单元之外的所有正常控制单元受理全业务的平均载荷程度为（1/F）·■CL■，CL■为CL当前载荷程度。可求得控制单元未失效时的流量载荷承载因子：θB=（1/F）·■[CL■-（1/F）·■CL■，CL■]。进而求出控制单元失效后LEF接入CL之后，该CL的流量载荷承载因子：θA=（1/F）·■[Nq·■+CL■-（1/F）■CL■]。最后得到待选控制单元组中新控制单元被接入的权重：W=（Nq·■）-1·（θA-θB）。当待选控制单元组中某一个控制单元权值最大，则该控制单元首先作为接入的首选对象。

良好的生存机制除了考虑为失效控制单元管辖下的交换机计算出权值最大的新控制单元接入方案之外，还需对被接入的新控制单元展开数据流量处理能力展开分析，避免其重载。令CL数据流量载荷的峰值能力为HL■，则在实施[2]新控制单元接入前应先确保失效控制单元管辖下的交换单元，对被接入的新控制单元的载荷程度要求Nq·■等同或者低于该被接入的新控制单元的载荷余量HL■-CL■，方可执行接入方案。

二、复杂网络体系下的生存机制

本文构思的生存思想旨在为复杂网络体系内部的控制接入过程提供策略稳健性的优化评估。评估的过程从两个方面来分布式实施。首先打破传统优化算法在全网中的冗余定义，充分利用全局有限的控制资源为失效控制单元管辖下的交换单元提供快速修复策略，以降低数据流量载荷在局向时间成本上的代价。其次通过对被接入的新控制单元展开计算，分析其作为宿主节点在应对全业务数据流量载荷时的可用资源负载饱和度，以优化全局控制资源。基于生存思想所述，形成如下生存遍历机制：将复杂网络体系初始化为SN={SN1，SN2，…，SNn}、C={C1，C2，…CL…Cn，Cn+1}、LE={LE1，LE2，…，LEF}，并将失效控制单元相邻子网体系和自身子网体系中的控制单元写入，将失效控制单元管辖下的交换单元写入LE。其次，遍历SN={SN1，SN2，…，SNn}将控制单元写入C={C1，C2，…CL…Cn，Cn+1}。然后读出LEF并逐个求解出LEF到C={C1，C2，…CL…Cn，Cn+1}中的每一个权值W=（Nq·■）-1·（θA-θB）并按照大小排序。重新排序后再展开分析，确定其Nq·■值与HL■-CL■值之间的关系。如果前者等于或者小于后者，则说明LEF顺利通过生存性评估可实施CL的接入。反之，则对重新排序后的C展开下一个待接入控制单元的生存性评估，直至实施接入。

三、生存机制评估

（一）评估模型

整个评估过程在Mininet环境中开展。将全局网络分设为三个子网体系SN1、SN2、SN3。每个子网体系内均使用Floodlight[3]作为控制单元，记为C1、C2、C3。将OpenSwitch作为本次评估的交换单元，三个SN中的数据流量由Iperf随机生成，规模分别为0.45、0.3、0.25。位于控制单元管辖下的交换单元规模分别为3个、6个、9个。节点网元间的路由局向速度设定为15Mb/s。结合生存思想所述原理，生存机制不仅为失效控制单元管辖下的交换单元提供快速接入方案，同时也包括对接入后的数据流量载荷开展时间代价评估以及接入后的新控制单元载荷处理能力展开测评，旨在优化整个复杂网络的全业务处理能力。因此本次生存机制的效能评估应包含上述三项指标。

（二）评估结果

■

图1 接入时间成本

根据前文所述，传统的优化算法在开展复杂网络稳健性评估时因失效子网体系的不同在策略上有所调整：（1）当在某个特定的子网体系中存在一个失效的控制单元，那么该子网体系中的交换单元便转而接入该子网体系内唯一的备用控制单元;（2）当某个特定子网体系中的两个主备控制单元均失效，则遍历出一个正常的子网体系为异常子网体系中的交换单元实施接入;（3）若全局主用控制单元均失效，则锁定路由代价最小的目标控制单元。相对于后面两种情况，传统优化算法在方案（1）中的实施效率最高。由于待选接入目标位于自身子网体系内，基本不消耗太多控制单元的计算资源也省去了比较分析的算法开销，因此可在较短时间内直接实施目标接入。从接入目标所消耗的时间成本[4]上看，该方案占据绝对优势，甚至优于本文构思的生存遍历机制。这一现象在图1所示的接入时间成本曲线图中也得到了体现。由于整个接入过程位于本子网体系内部，因此实现备用目标接入后，全业务数据流量在交换单元和备用目标控制单元之间路由局向的时间代价也最小，优于本文讨论的生存遍历算法。这在图2所示的数据流量载荷局向时间代价曲线中得到说明。但是传统优化算法在实施后两者方案需遍历多个子网体系中的目标控制单元，这不仅增加筛选目标的时间成本，同时由于路由距离代价[5]的增加而直接导致接入目标与失效控制单元所在子网体系中的大量交换单元在实施全业务路由局向的时延变大。由于在方案（3）的情形下，这种遍历操作贯穿了全局所有子网体系，相应的开销代价最大。而本文所述生存算法旨在相邻子网体系内开展目标控制单元的筛选。在顺利实施目标接入后全业务的承载也局限在相邻子网体系的目标控制单元和异常子网体系中的交换单元之间。故而路由局向的时间相对方案（2）和（3）较短。算法的这些特征在图2和图3所示的曲线中也同样得到了验证。

■

图2 数据流量载荷局向时间代价

■

图3 被接入目标载荷承重度

有别于传统优化算法，本文描述的生存机制不仅考虑了目标的优化选择，也兼顾了实施接入以后目标的载荷承重度。此举主要从全网优化角度来考虑，进一步加强了复杂网络的生存性。而传统优化算法目标仅仅只是为失效子网体系实施风险转移，并未长远地考虑到风险转移之后目标承载度是否处于重载状态。本质上看，该行为实际上是将潜在的风险嫁接到了目标控制单元，这势必降低整个复杂网络的QoS，也不利于软件定义网络架构优势的发挥。算法的这些性能通过图3所示的接入目标承重度来接受测评。图3示可见，当SN1中的C1出现失效后其承载能力急剧下降至零，SN2和SN3中的C2、C3作为目标接受接入。由于目标控制单元需要对新增的交换单元做出载荷响应，因此无论传统算法还是本文阐述的生存机制，其载荷程度均有所增加。图中曲线的递增走势说明了此问题。从图中曲线不难观测到，在实施接入之前C2的承载度轻于C3的承载度，本着全局均衡优化原则，实施目标接入后C2的承载度保持增重趋势的前提下应该保持相对重载。C3的承载度在保持增重趋势的前提下应该保持相对轻载。从图中可见，这样的均衡优化特征在本文的生存算法得到了发挥。相比之下传统优化算法因缺乏全局性使接入在实施之后出现潜在的重载风险。

四、结论

本文围绕软件定义网络架构的优势展开讨论了复杂网络在应用中存在的风险，并提出相应的解决方案。方案的实施有效地突破了传统优化算法在稳健性评估方面存在的局限性。评估结果表明，该方案不仅有效地提高了复杂网络风险转移的效能性，同时也有效地避免了二次风险潜伏的可能性，具有良好的全局性。

参考文献：

[1]王帅，金华敏.基于SDN的安全分析及关键技术研究[J].电信科学，2018，34（2）：45-49.

[2]杨耀通.基于蝙蝠算法的SDN多控制器部署[J].重庆大学学报，2018，41（9）：57-65.

[3]周环，劉慧.基于Floodlight的SDN控制器研究[J].计算机工程与应用，2016，52（24）：137-146.

[4]陈鸣，代飞，许博，等.主动测量SDN性能的机制[J].通信学报，2018，38（6）：35-44.

[5]许训，李鉴.基于SDN和离线计算的QoS路由方法[J].信息技术，2018，41（11）：91-96.

◎编辑 赵瑞峰

Research on Survival Traversal Algorithm of Complex Networks

ZHANG Man-yu

Abstract：Although in response to big dataundefineds（QoS） requirements for network quality of service，complex software-defined networks can be deployed. However，security problems frequently arise because of the lack of efficient risk assessment.In this paper，a survival ergodic algorithm is proposed to improve the risk aversion ability of complex network systems.The algorithm builds a mathematical model for the subnet system and sets up a target traversal strategy from the global point of view to implement risk avoidance.At the same time，it evaluates the potential risk modeling after risk avoidance to ensure the survivability of the whole network. The test results show that the survival ergodic algorithm performs significantly and has a good global performance.

Key words：complex network;failure;survival;computation;evaluation