基于动态混合超时的软件定义网络多目标优化

doi:10.11772/j.issn.1001-9081.2021010079

《计算机应用》唯一官方网站 ›› 2021, Vol. 41 ›› Issue (12): 3658-3665.DOI: 10.11772/j.issn.1001-9081.2021010079

基于动态混合超时的软件定义网络多目标优化

马晓航¹, 廖灵霞²^,³(), 李智¹^,², 秦斌⁴, 赵涵捷³

^1.桂林电子科技大学电子工程与自动化学院，广西桂林 541004
^2.桂林航天工业学院电子信息和自动化学院，广西桂林 541004
^3.台湾东华大学电机工程系，台湾花莲 974301
^4.桂林航天工业学院信息中心，广西桂林 541004

收稿日期:2021-01-14 修回日期:2021-05-18 接受日期:2021-05-21 发布日期:2021-12-28 出版日期:2021-12-10
通讯作者: 廖灵霞
作者简介:马晓航（1997—），男，江苏连云港人，硕士研究生，主要研究方向：软件定义网络、多目标优化
李智（1965—），男，广西桂林人，教授，博士，主要研究方向：自动测试总线、智能仪器系统
秦斌（1980—），男，广西桂林人，主要研究方向：网络规划设计、信息安全
赵涵捷（1963—），男，台湾台北人，教授，博士，主要研究方向：机器学习、边缘计算。
基金资助:
国家自然科学基金资助项目(61962016)

Multi-objective optimization based on dynamic mixed flow entry timeouts in software defined network

Xiaohang MA¹, Lingxia LIAO²^,³(), Zhi LI¹^,², Bin QIN⁴, Han-chieh CHAO³

^1.School of Electronic Engineering and Automation，Guilin University of Electronic Technology，Guilin Guanxi 541004，China
^2.School of Electronic Information and Automation，Guilin University of Aerospace Technology，Guilin Guanxi 541004，China
^3.Department of Electrical Engineering，Taiwan Dong Hwa University，Hualien Taiwan 974301，China
^4.Information Center，Guilin University of Aerospace Technology，Guilin Guanxi 541004，China

Received:2021-01-14 Revised:2021-05-18 Accepted:2021-05-21 Online:2021-12-28 Published:2021-12-10
Contact: Lingxia LIAO
About author:MA Xiaohang， born in 1997， M. S. candidate. His research interests include software defined network， multi-objective optimization.
LI Zhi， born in 1965， Ph. D.， professor. His research interests include automatic test bus， intelligent instrument system.
QIN Bin， born in 1980. His research interests include network planning and design， information security.
CHAO Han-chieh， born in 1963， Ph. D.， professor. His research interests include machine learning， edge computing.
Supported by:
the National Natural Science Foundation of China(61962016)

摘要/Abstract

摘要：

软件定义网络（SDN）中，流表项是由控制器创建并指导交换机处理数据包的转发规则。流表项保存在交换机的内存并有一定的超时时间，会影响SDN控制通道的带宽消耗、交换机的内存消耗以及系统资源和性能的管理。针对现有SDN性能优化方案大多为单一目标优化，未考虑流表项超时类型和时间对不同优化目标的影响，提出一种基于流表项动态混合超时的多目标优化方案，对大象流的侦测精度、流表项的交换机内存消耗和控制通道带宽占用进行三目标联合优化。动态混合超时将现有的两种流表项超时方式，即硬超时和空闲超时相结合，并对流表项的超时类型和时间进行双维度动态调节。通过NSGA-Ⅱ算法求解所提优化问题，评估不同超时方式和超时时间对三个优化目标的影响，并通过合并特定超时时间下的解集与贝叶斯多目标优化算法的解集对NSGA-Ⅱ算法的解集质量进行改进。结果表明，所提方案能提供更高的侦测精度、更低的带宽占用和更小的交换机内存消耗，明显提升了SDN的综合性能。

关键词: 软件定义网络, 流表项超时, 多目标优化, 大象流侦测, 网络性能优化

Abstract:

Flow entries are forwarding rules generated by controllers and guide switches to process data packets in Software Defined Network （SDN）. Every flow entry is stored in the memory of switches and has timeout， which affects the bandwidth cost in SDN control channel， the memory consumption in switches， and the system’s resource management and performance. As most of the existing SDN performance optimization schemes only have single objective， and do not consider the impact of the types and time of the flow entry timeouts， a multi-objective optimization scheme was proposed based on the dynamic mixed timeouts of flow entries to simultaneously optimize the three objects： the detection of elephant flows， the memory consumption of flow entries in switches， and the control channel bandwidth occupation. In the dynamic mixed timeout， hard-timeout and idle-timeout， two timeout methods of flow entries were combined， and the timeout type and time of flow entries were adjusted in a two-dimensional dynamic way. The NSGA-Ⅱ algorithm was used to solve the proposed optimization problem and to evaluate the impact of different timeout methods and timeout time on the three optimization objectives. The solution set of specific timeouts was combined with the solution set of Bayesian multi-objective optimization algorithm to improve the quality of the solution set. The results show that the proposed scheme can provide a higher detection accuracy， a lower bandwidth occupation， and a smaller switch memory consumption. It significantly improves the overall performance of SDNs.

Key words: Software Defined Network (SDN), flow entry timeout, multi-objective optimization, elephant flow detection, network performance optimization

中图分类号:

TP393

马晓航, 廖灵霞, 李智, 秦斌, 赵涵捷. 基于动态混合超时的软件定义网络多目标优化[J]. 计算机应用, 2021, 41(12): 3658-3665.

Xiaohang MA, Lingxia LIAO, Zhi LI, Bin QIN, Han-chieh CHAO. Multi-objective optimization based on dynamic mixed flow entry timeouts in software defined network[J]. Journal of Computer Applications, 2021, 41(12): 3658-3665.

图/表 12

图1 SDN架构

Fig.1 SDN architecture

表1 优化模型参数描述

Tab. 1 Optimization model parameter description

参数名	描述
$F$	周期内数据流集合
$f i$	数集合 $F$ 的第 $i$ 条数据流
$p i j$	数据流 $f i$ 的第 $j$ 个数据包
$t i j$	包 $p i j$ 的到达时间
$t$	周期内某时刻
$f l a g f i$	$f i$ 的标签，0老鼠流，1大象流
$G$	侦测大象流使用的模型
$G (P i)$	对数据流 $f i$ 识别，0老鼠流，1大象流
$P i$	数据流 $f i$ 转发到控制器的数据总量
$F N$	标记为大象流而预测为老鼠流的流
$T P$	标记为老鼠流预测为老鼠流的流
$b w t$	周期内通过控制通道的数据量均值
$b c$	控制通道最大带宽
$P$	交换机转发到控制器的数据总量
$l i j$	数据流 $f i$ 的第 $j$ 个数据包的大小
$a i j$	数据流 $f i$ 的第 $j$ 个数据包的转发情况
$t i_u p d a t e$	数据流 $f i$ 流表项的更新时间
$E i$	$f i$ 流表项在 $t$ 时刻存活情况
$t i j_e f f e c t i v e$	$p i j$ 转发后流表项超时时间

表1 优化模型参数描述

Tab. 1 Optimization model parameter description

参数名	描述
$F$	周期内数据流集合
$f i$	数集合 $F$ 的第 $i$ 条数据流
$p i j$	数据流 $f i$ 的第 $j$ 个数据包
$t i j$	包 $p i j$ 的到达时间
$t$	周期内某时刻
$f l a g f i$	$f i$ 的标签，0老鼠流，1大象流
$G$	侦测大象流使用的模型
$G (P i)$	对数据流 $f i$ 识别，0老鼠流，1大象流
$P i$	数据流 $f i$ 转发到控制器的数据总量
$F N$	标记为大象流而预测为老鼠流的流
$T P$	标记为老鼠流预测为老鼠流的流
$b w t$	周期内通过控制通道的数据量均值
$b c$	控制通道最大带宽
$P$	交换机转发到控制器的数据总量
$l i j$	数据流 $f i$ 的第 $j$ 个数据包的大小
$a i j$	数据流 $f i$ 的第 $j$ 个数据包的转发情况
$t i_u p d a t e$	数据流 $f i$ 流表项的更新时间
$E i$	$f i$ 流表项在 $t$ 时刻存活情况
$t i j_e f f e c t i v e$	$p i j$ 转发后流表项超时时间

图2 NSGA-Ⅱ求解优化问题的流程

Fig. 2 NSGA-Ⅱ flowchart to solve optimization problem

图3 静态调节下两种超时方式的Pareto Frontiers

Fig.3 Pareto Frontiers of two timeout methods under static adjustment

图4 方差均值动态超时调节方式下硬超时与空闲超时Pareto Frontiers

Fig.4 Pareto Frontiers of hard-timeout and idle-timeout under ave_sig dynamic timeout adjustment method

图5 翻倍动态超时调节方式下硬超时与空闲超时的Pareto Frontiers

Fig. 5 Pareto Frontiers of hard-timeout and idle-timeout under multiple dynamic timeout adjustment method

图6 静态调节下三种超时方式的Pareto Frontiers

Fig.6 Pareto Frontiers of three timeout methods under static adjustment

图7 动态混合超时与静态混合超时的Pareto Frontiers

Fig.7 Pareto Frontiers of dynamic mixed timeout and static mixed timeout

图8 方差均值动态超时调节方式下三种超时方式的Pareto Frontiers

Fig. 8 Pareto Frontiers of three timeout methods under ave_sig dynamic timeout adjustment method

图 9 翻倍动态超时调节方式下三种超时方式的Pareto Frontiers

Fig.9 Pareto Frontiers of three timeout methods under multiple dynamic timeout adjustment method

图10 混合超时敏感性分析

Fig.10 Mixed timeout sensitivity analysis

图11 动态混合超时与静态混合超时的Pareto Frontiers （优化后）

Fig.11 Pareto Frontiers of dynamic mixed timeout and static mixed timeout （after improvement）

参考文献 29

1	董仕. 软件定义网络安全问题研究综述［J］. 计算机科学， 2021， 48（3）： 295-306. 10.11896/jsjkx.200300119
	DONG S. Survey on software defined networks security［J］. Computer Science， 2021， 48（3）：295-306. 10.11896/jsjkx.200300119
2	樊自甫，姚杰，杨先辉. 基于时延优化的软件定义网络控制层部署策略［J］. 计算机应用， 2018， 38（1）：207-211. 10.11772/j.issn.1001-9081.2017071681
	FAN Z F， YAO J， YANG X H. Controller deployment strategy based on delay optimization in software defined network［J］. Journal of Computer Applications， 2018， 38（1）：207- 211. 10.11772/j.issn.1001-9081.2017071681
3	Open Networking Foundation. OpenFlow switch specification： version1.3.1 （Wire Protocol 0x04）： ONF TS-007［EB/OL］. （2012-09-06）［2021-03-20］..
4	向雄，田检. 基于软件定义网络的对等网传输调度优化［J］. 计算机应用， 2020， 40（3）：777-782.
	XIANG X， TIAN J. P2P transmission scheduling optimization based on software defined network［J］. Journal of Computer Applications， 2020， 40（3）：777-782.
5	郑鹏，胡成臣，李昊. 基于流量特征的OpenFlow南向接口开销优化技术［J］. 计算机研究与发展， 2018， 55（2）：346-357. 10.7544/issn1000-1239.2018.20160743
	ZHENG P， HU C C， LI H. Reducing the southbound interface overhead for OpenFlow based on the flow volume characteristics［J］. Journal of Computer Research and Development， 2018， 55（2）：346-357. 10.7544/issn1000-1239.2018.20160743
6	HU F， HAO Q， BAO K. A survey on software-defined network and OpenFlow： from concept to implementation［J］. IEEE Communications Surveys and Tutorials， 2014， 16（4）：2181-2206. 10.1109/comst.2014.2326417
7	乔思祎，胡成臣，李昊，等. OpenFlow交换机流表溢出问题的缓解机制［J］. 计算机学报， 2018， 41（9）：2003-2015. 10.11897/SP.J.1016.2018.02003
	QIAO S Y， HU C C， LI H， et al. A mechanism of taming the flow table overflow in OpenFlow switch［J］. Chinese Journal of Computers， 2018， 41（9）：2003-2015. 10.11897/SP.J.1016.2018.02003
8	KIM T， LEE K， LEE J， et al. A dynamic timeout control algorithm in software defined networks［J］. International Journal of Future Computer and Communication， 2014， 3（5）：331-336. 10.7763/ijfcc.2014.v3.321
9	史少平，庄雷，杨思锦. 一种基于预测与动态调整负载因子的SDN流表优化算法［J］. 计算机科学， 2017， 44（1）：123-127. 10.11896/j.issn.1002-137X.2017.01.024
	SHI S P， ZHUANG L， YANG S J. SDN optimization algorithm based on prediction and dynamic load factor［J］. Computer Science， 2017， 44（1）：123-127. 10.11896/j.issn.1002-137X.2017.01.024
10	刘霞，杨桂芹，邵军花，等. SDN动态停滞超时时间优化算法［J］. 传感器与微系统， 2019， 38（10）：118-121. 10.13873/J.1000-9787(2019)10-0118-04
	LIU X， YANG G Q， SHAO J H， et al. Dynamic timeout optimization algorithm in SDN［J］. Transducer and Microsystem Technologies， 2019， 38（10）：118-121. 10.13873/J.1000-9787(2019)10-0118-04
11	SOODEN B， ABBASI M R. A dynamic hybrid timeout method to secure flow tables against DDoS attacks in SDN［C］// Proceedings of the 1st International Conference on Secure Cyber Computing and Communication. Piscataway： IEEE， 2018：29-34. 10.1109/icsccc.2018.8703307
12	ISYAKU B， KAMAT M B， BAKAR K B ABU， et al. IHTA： dynamic idle-hard timeout allocation algorithm based OpenFlow switch［C］// Proceedings of the IEEE 10th Symposium on Computer Applications and Industrial Electronics. Piscataway： IEEE， 2020：170-175. 10.1109/iscaie47305.2020.9108803
13	付应辉. 基于SDN的多路径负载均衡算法及流表分配优化算法研究［D］. 合肥：安徽大学， 2017. 10.7666/d.Y3215536
	FU Y H. Research on multi path load balancing and flowtable distribution optimization based on SDN［D］. Hefei： Anhui University， 2017. 10.7666/d.Y3215536
14	唐菀，王敢甫，吴京京，等. SDN数据中心网络基于流表项转换的流表调度优化［J］. 中南民族大学学报（自然科学版）， 2017， 36（3）：111-117. 10.3969/j.issn.1672-4321.2017.03.024
	TANG W， WANG G F， WU J J， et al. Flowtable scheduling optimization based on flowentry conversion in SDN-based datacenter networks［J］. Journal of South-Central University for Nationalities （Natural Science Edition）， 2017， 36（3）：111-117. 10.3969/j.issn.1672-4321.2017.03.024
15	LIAO L X， CHAO H C， CHEN M Y. Intelligently modeling， detecting， and scheduling elephant flows in software defined energy cloud： a survey［J］. Journal of Parallel and Distributed Computing， 2020， 146： 64-78. 10.1016/j.jpdc.2020.07.008
16	董仕，李瑞轩，李晓林. 基于软件定义数据中心网络的节能路由算法［J］. 计算机研究与发展， 2015， 52（4）：806-812. 10.7544/issn1000-1239.2015.20148419
	DONG S， LI R X， LI X L. Entry efficient routing algorithm based on software defined data center network［J］. Journal of Computer Research and Development， 2015， 52（4）：806-812. 10.7544/issn1000-1239.2015.20148419
17	TANG Q， ZHANG H， DONG J， et al. Elephant flow detection mechanism in SDN-based data center networks［J］. Scientific Programming， 2020， 2020： No.8888375. 10.1155/2020/8888375
18	刘奕，李建华，陈玉. 基于蚁群优化的多路径流量调度算法［J］. 电光与控制， 2020， 27（12）：6-10， 14. 10.3969/j.issn.1671-637X.2020.12.002
	LIU Y， LI J H， CHEN Y. A multi-path traffic scheduling algorithm based on ant colony optimization［J］. Electronics Optics & Control， 2020， 27（12）：6-10， 14. 10.3969/j.issn.1671-637X.2020.12.002
19	AL-FARES M， RADHAKRISHNAN S， RAGHAVAN B， et al. Hedera： dynamic flow scheduling for data center networks［C］// Proceedings of the 7th USENIX Symposium on Networked Systems Design and Implementation. Berkeley： USENIX Association， 2010：281-296.
20	CURTIS A R， MOGUL J C， TOURRILHES J， et al. DevoFlow： scaling flow management for high-performance networks［C］// Proceedings of the 2011 ACM SIGCOMM Conference. New York： ACM， 2011： 254-265. 10.1145/2018436.2018466
21	杨力波. 基于机器学习的网络流量识别及其应用研究［D］. 成都：电子科技大学， 2020. 10.30919/esee8c207
	YANG L B. Research on network traffic identification and its application based on machine learning［D］. Chengdu： University of Electronic Science and Technology of China， 2020. 10.30919/esee8c207
22	BENSON T， AKELLA A， MALTZ D A. Network traffic characteristics of data centers in the wild［C］// Proceedings of the 10th ACM SIGCOMM Conference on Internet Measurement. New York： ACM， 2010： 267-280. 10.1145/1879141.1879175
23	李善俊，陈淮莉. 基于NSGA II的带时间窗生鲜品配送路径优化［J］.上海海事大学学报， 2020， 41（2）：58-64. 10.13340/j.jsmu.2020.02.011
	LI S J， CHEN H L. Optimization of fresh food distribution route with time window based on NSGA Ⅱ［J］. Journal of Shanghai Maritime University， 2020， 41（2）：58-64. 10.13340/j.jsmu.2020.02.011
24	卢小张，刘伟，陶耀东. 基于NSGA-Ⅱ的嵌入式系统软硬件划分方法［J］. 计算机应用， 2009， 29（1）：238-241. 10.3724/sp.j.1087.2009.238
	LU X Z， LIU W， TAO Y D. Method of HW/SW partitioning based on NSGA-Ⅱ［J］. Journal of Computer Applications， 2009， 29（1）：238-241. 10.3724/sp.j.1087.2009.238
25	周孔涛，崔建昆，吴鲁超. NSGA-Ⅱ算法在智能飞行器航迹规划中的应用［J］. 农业装备与车辆工程， 2020， 58（10）：63-66， 133. 10.3969/j.issn.1673-3142.2020.10.014
	ZHOU K T， CUI J K， WU L C. Application of NSGA-Ⅱ algorithm in intelligent aircraft path planning［J］. Agricultural Equipment and Vehicle Engineering， 2020， 58（10）：63-66， 133. 10.3969/j.issn.1673-3142.2020.10.014
26	王蕊，顾清华. 一种求解约束多目标问题的协作进化算法［J］. 控制与决策， 2021， 36（11）：2656-2664. 10.1007/s40747-020-00249-x
	WANG R， GU Q H. A collaborative evolutionary algorithm for solving constrained multi-objective problems［J］. Control and Decision， 2021， 36（11）：2656-2664. 10.1007/s40747-020-00249-x
27	GALUZIO P P， DE VASCONCELOS SEGUNDO E H， COELHO L D S， et al. MOBOpt — multi-objective Bayesian optimization［J］. SoftwareX， 2020， 12： No.100520. 10.1016/j.softx.2020.100520
28	江敏. 贝叶斯优化算法在多目标优化问题中的应用［J］. 上海应用技术学院学报（自然科学版）， 2012， 12（1）：41-44. 10.3969/j.issn.1671-7333.2012.01.011
	JIANG M. Application of Bayesian optimization algorithm in multiobjective problems［J］. Journal of Shanghai Institute of Technology （Natural Science）， 2012， 12（1）：41-44. 10.3969/j.issn.1671-7333.2012.01.011
29	DEB K， PRATAP A， AGARWAL S， et al. A fast and elitist multiobjective genetic algorithm： NSGA-II［J］. IEEE Transactions on Evolutionary Computation， 2002， 6（2）：182-197. 10.1109/4235.996017

[1]	刘晓芳, 张军. 概率驱动的动态多目标多智能体协同调度进化优化[J]. 《计算机应用》唯一官方网站, 2024, 44(5): 1372-1377.
[2]	高麟, 周宇, 邝得互. 进化双层自适应局部特征选择[J]. 《计算机应用》唯一官方网站, 2024, 44(5): 1408-1414.
[3]	田野, 陈津津, 张兴义. 面向约束多目标优化的进化计算与梯度下降联合优化算法[J]. 《计算机应用》唯一官方网站, 2024, 44(5): 1386-1392.
[4]	赵楷文, 王鹏, 童向荣. 基于双阶段搜索的约束进化多任务优化算法[J]. 《计算机应用》唯一官方网站, 2024, 44(5): 1415-1422.
[5]	姜涛, 梁振宇, 程然, 金耀初. GPU加速的演化算法求解多目标流水车间调度问题[J]. 《计算机应用》唯一官方网站, 2024, 44(5): 1364-1371.
[6]	李建强, 何舟. 面向多行程取送货车辆路径问题的混合NSGA-Ⅱ[J]. 《计算机应用》唯一官方网站, 2024, 44(4): 1187-1194.
[7]	马勇健, 史旭华, 王佩瑶. 基于两阶段搜索与动态资源分配的约束多目标进化算法[J]. 《计算机应用》唯一官方网站, 2024, 44(1): 269-277.
[8]	徐赛娟, 裴镇宇, 林佳炜, 刘耿耿. 基于多阶段搜索的约束多目标进化算法[J]. 《计算机应用》唯一官方网站, 2023, 43(8): 2345-2351.
[9]	葛晨洋, 刘勤让, 裴雪, 魏帅, 朱正彬. 软件定义网络中高效协同防御分布式拒绝服务攻击的方案[J]. 《计算机应用》唯一官方网站, 2023, 43(8): 2477-2485.
[10]	金苍宏, 邵育华, 何琴芳. 基于自适应群组重排的长尾推荐模型[J]. 《计算机应用》唯一官方网站, 2023, 43(4): 1122-1128.
[11]	柳隽琰, 江沸菠, 彭于波, 董莉. 基于分解法与轨迹搜索的无人机群轨迹多目标优化模型[J]. 《计算机应用》唯一官方网站, 2023, 43(12): 3806-3815.
[12]	柳春锋, 李峥, 王居凤. 分布式工厂中微型制造单元多目标优化[J]. 《计算机应用》唯一官方网站, 2023, 43(12): 3824-3832.
[13]	李二超, 张生辉. 基于新评价指标自适应预测的动态多目标优化算法[J]. 《计算机应用》唯一官方网站, 2023, 43(10): 3178-3187.
[14]	李兴佳, 杨秋辉, 洪玫, 潘春霞, 刘瑞航. 基于历史数据和多目标优化的测试用例排序方法[J]. 《计算机应用》唯一官方网站, 2023, 43(1): 221-226.
[15]	马艳芳, 张文, 李宗敏, 闫芳, 郭凌云. 考虑负效应的垃圾回收两级选址‒路径模型与算法[J]. 《计算机应用》唯一官方网站, 2023, 43(1): 289-298.

基于动态混合超时的软件定义网络多目标优化

Multi-objective optimization based on dynamic mixed flow entry timeouts in software defined network

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

图/表 12

参考文献 29

相关文章 15

编辑推荐

Metrics