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

doi:10.11772/j.issn.1001-9081.2021010079

Journal of Computer Applications ›› 2021, Vol. 41 ›› Issue (12): 3658-3665.DOI: 10.11772/j.issn.1001-9081.2021010079

• Advanced computing • Previous Articles Next Articles

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)

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

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

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

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

Abstract

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

摘要：

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

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

CLC Number:

TP393

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.

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

Figures/Tables 12

Fig.1 SDN architecture

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$ 转发后流表项超时时间

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$ 转发后流表项超时时间

Fig. 2 NSGA-Ⅱ flowchart to solve optimization problem

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

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

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

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

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

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

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

Fig.10 Mixed timeout sensitivity analysis

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

References 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]	Lin GAO, Yu ZHOU, Tak Wu KWONG. Evolutionary bi-level adaptive local feature selection [J]. Journal of Computer Applications, 2024, 44(5): 1408-1414.
[2]	Ye TIAN, Jinjin CHEN, Xingyi ZHANG. Hybrid optimizer combining evolutionary computation and gradient descent for constrained multi-objective optimization [J]. Journal of Computer Applications, 2024, 44(5): 1386-1392.
[3]	Tao JIANG, Zhenyu LIANG, Ran CHENG, Yaochu JIN. GPU-accelerated evolutionary optimization of multi-objective flow shop scheduling problems [J]. Journal of Computer Applications, 2024, 44(5): 1364-1371.
[4]	Kaiwen ZHAO, Peng WANG, Xiangrong TONG. Two-stage search-based constrained evolutionary multitasking optimization algorithm [J]. Journal of Computer Applications, 2024, 44(5): 1415-1422.
[5]	Jianqiang LI, Zhou HE. Hybrid NSGA-Ⅱ for vehicle routing problem with multi-trip pickup and delivery [J]. Journal of Computer Applications, 2024, 44(4): 1187-1194.
[6]	Yongjian MA, Xuhua SHI, Peiyao WANG. Constrained multi-objective evolutionary algorithm based on two-stage search and dynamic resource allocation [J]. Journal of Computer Applications, 2024, 44(1): 269-277.
[7]	Saijuan XU, Zhenyu PEI, Jiawei LIN, Genggeng LIU. Constrained multi-objective evolutionary algorithm based on multi-stage search [J]. Journal of Computer Applications, 2023, 43(8): 2345-2351.
[8]	Chenyang GE, Qinrang LIU, Xue PEI, Shuai WEI, Zhengbin ZHU. Efficient collaborative defense scheme against distributed denial of service attacks in software defined network [J]. Journal of Computer Applications, 2023, 43(8): 2477-2485.
[9]	Canghong JIN, Yuhua SHAO, Qinfang HE. Long-tail recommendation model based on adaptive group reranking [J]. Journal of Computer Applications, 2023, 43(4): 1122-1128.
[10]	Junyan LIU, Feibo JIANG, Yubo PENG, Li DONG. Multi-objective optimization model for unmanned aerial vehicles trajectory based on decomposition and trajectory search [J]. Journal of Computer Applications, 2023, 43(12): 3806-3815.
[11]	Chunfeng LIU, Zheng LI, Jufeng WANG. Multi-objective optimization of minicells in distributed factories [J]. Journal of Computer Applications, 2023, 43(12): 3824-3832.
[12]	Erchao LI, Shenghui ZHANG. Dynamic multi-objective optimization algorithm based on adaptive prediction of new evaluation index [J]. Journal of Computer Applications, 2023, 43(10): 3178-3187.
[13]	LI Xingjia, YANG Qiuhui, HONG Mei, PAN Chunxia, LIU Ruihang. Test case prioritization approach based on historical data and multi-objective optimization [J]. Journal of Computer Applications, 2023, 43(1): 221-226.
[14]	MA Yanfang, ZHANG Wen, LI Zongmin, YAN Fang, GUO Lingyun. Two-echelon location-routing model and algorithm for waste recycling considering obnoxious effect [J]. Journal of Computer Applications, 2023, 43(1): 289-298.
[15]	Xiangyu ZHANG, Yang YANG, Guohui FENG, Chuan QIN. Reversible data hiding in encrypted image based on multi-objective optimization [J]. Journal of Computer Applications, 2022, 42(6): 1716-1723.

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

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

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 12

References 29

Related Articles 15

Recommended Articles

Metrics