基于多目标约束遗传算法的SDN路径增强算法
|
摘要
SDN控制器的出现有效地解决了传统网络设施僵化等问题,它可以通过自身的网络拓扑模块掌握全局拓扑,并且计算出符合全局最优的网络路径。但是,现如今的网络环境日益复杂,想要计算出可以有效满足带宽、时延、丢包率等约束的路由变得尤为困难,传统的精确算法已经很难满足各种网络业务的需求。实际上计算满足多目标多约束的路径问题本质上属于多目标优化问题(MOP),很难用精确的数学方法解决。所以借助启发式算法的思想,针对该问题,提出了一种改进的多目标约束遗传算法来找到全局最优的路径,在传统遗传算法的基础下根据网络的特性,对初始种群生成的算法进行了改进,使得初始路径满足了大部分的约束条件,实现对传统的计算路径算法的增强及优化的目标。实验结果表明,该算法可以在满足各种业务约束条件的前提下达到多个路径优化目标的效果。
The emergence of SDN controller effectively solves the problems such as the rigidity of traditional network facilities. It can master the global topology through its own network topology module and calculate the network path that conforms to the global optimal. However,nowadays,with the increasingly complex network environment,it is particularly difficult to calculate the routing that can effectively meet the constraints of bandwidth,delay,packet loss rate and so on,and the traditional precision algorithm has been difficult to meet the requirements of various network services. In fact,the computation of a path problem that satisfies multiple objectives and multiple constraints is essentially a multi-objective optimization problem(MOP),which is difficult to solve with precise mathematical methods. Therefore,with the aid of the heuristic algorithm,an improved multi-objective constrained genetic algorithm to find the global optimal path is put forward. Based on the characteristics of the network,the algorithm of initial population generation is improved based on the traditional genetic algorithm,so that the initial path satisfies most of the constraints,achieving the goal of enhancing and optimizing the traditional computation path algorithm. The experiment shows that the proposed algorithm can achieve the effect of multiple path optimization objectives under the premise of meeting various business constraints.
The emergence of SDN controller effectively solves the problems such as the rigidity of traditional network facilities. It can master the global topology through its own network topology module and calculate the network path that conforms to the global optimal. However,nowadays,with the increasingly complex network environment,it is particularly difficult to calculate the routing that can effectively meet the constraints of bandwidth,delay,packet loss rate and so on,and the traditional precision algorithm has been difficult to meet the requirements of various network services. In fact,the computation of a path problem that satisfies multiple objectives and multiple constraints is essentially a multi-objective optimization problem(MOP),which is difficult to solve with precise mathematical methods. Therefore,with the aid of the heuristic algorithm,an improved multi-objective constrained genetic algorithm to find the global optimal path is put forward. Based on the characteristics of the network,the algorithm of initial population generation is improved based on the traditional genetic algorithm,so that the initial path satisfies most of the constraints,achieving the goal of enhancing and optimizing the traditional computation path algorithm. The experiment shows that the proposed algorithm can achieve the effect of multiple path optimization objectives under the premise of meeting various business constraints.
引文
[1] MCKEOWN N,ANDERSON T,BALAKRISHNAN H,et al.OpenFlow:enabling innovation in campus networks[J].ACM SIGCOMM Computer Communication Review,2008,38(2):69-74.
[2] 赖香武,彭大芹,黄德玲,等.基于SDN的数据中心网络路由算法研究[J].无线互联科技,2016(24):38-40.
[3] 吕小兵.基于OpenFlow的SDN网络路由算法的设计与实现[J].自动化与仪器仪表,2017(9):128-130.
[4] 邓书华,卢泽斌,罗成程,等.SDN研究简述[J].计算机应用研究,2014,31(11):3208-3213.
[5] 邓谦.基于盒覆盖的SDN路由算法研究[D].长沙:湖南师范大学,2015.
[6] DAS S.A unified control architecture for packet and circuit network convergence[D].USA:Stanford Univeristy,2012.
[7] 马军锋.SDN/NFV关键技术问题分析和标准化进展[J].中兴通讯技术,2016,22(6):12-16.
[8] 李光,王延松,范成法.M-ICT时代SDN技术实践与创新[J].中兴通讯技术,2016,22(5):61-66.
[9] FEAMSTER N,REXFORD J,ZEGURA E.The road to SDN:an intellectual history of programmable networks[J].ACM SIGCOMM Computer Communication Review,2014,44(2):87-98.
[10] TOMOVIC S,RADUSINOVIC I.Fast and efficient bandwidth-delay constrained routing algorithm for SDN networks[C]//IEEE netsoft conference and workshops.Seoul,South Korea:IEEE,2016:303-311.
[11] 汪胡青,孙知信.基于Dijistra算法的多约束多播路由算法的研究[J].计算机技术与发展,2011,21(12):5-8.
[12] UPADHYAYA S,DEVI G.Characterization of QoS based routing algorithms[J].International Journal of Computer Science & Emerging Technologies,2010(20):50-52.
[13] 陈乐瑞,孔金生.基于改进遗传算法的网络路由优化研究[J].计算机应用与软件,2013,30(4):135-137.
[14] SAMPSON J R.Adaptation in natural and artificial systems (John H.Holland)[J].SIAM Review,2006,18(3):529-530.
[15] HAMIDA S B,SCHOENAUER M.ASCHEA:new results using adaptive segregational constraint handling[C]//Proceedings of the 2002 congress on evolutionary computation.Honolulu,HI,USA:IEEE,2002:884-889.
[16] HE L,MORT N.Hybrid genetic algorithms for telecommunications network back-up routeing[J].BT Technology Journal,2000,18(4):42-50.
[2] 赖香武,彭大芹,黄德玲,等.基于SDN的数据中心网络路由算法研究[J].无线互联科技,2016(24):38-40.
[3] 吕小兵.基于OpenFlow的SDN网络路由算法的设计与实现[J].自动化与仪器仪表,2017(9):128-130.
[4] 邓书华,卢泽斌,罗成程,等.SDN研究简述[J].计算机应用研究,2014,31(11):3208-3213.
[5] 邓谦.基于盒覆盖的SDN路由算法研究[D].长沙:湖南师范大学,2015.
[6] DAS S.A unified control architecture for packet and circuit network convergence[D].USA:Stanford Univeristy,2012.
[7] 马军锋.SDN/NFV关键技术问题分析和标准化进展[J].中兴通讯技术,2016,22(6):12-16.
[8] 李光,王延松,范成法.M-ICT时代SDN技术实践与创新[J].中兴通讯技术,2016,22(5):61-66.
[9] FEAMSTER N,REXFORD J,ZEGURA E.The road to SDN:an intellectual history of programmable networks[J].ACM SIGCOMM Computer Communication Review,2014,44(2):87-98.
[10] TOMOVIC S,RADUSINOVIC I.Fast and efficient bandwidth-delay constrained routing algorithm for SDN networks[C]//IEEE netsoft conference and workshops.Seoul,South Korea:IEEE,2016:303-311.
[11] 汪胡青,孙知信.基于Dijistra算法的多约束多播路由算法的研究[J].计算机技术与发展,2011,21(12):5-8.
[12] UPADHYAYA S,DEVI G.Characterization of QoS based routing algorithms[J].International Journal of Computer Science & Emerging Technologies,2010(20):50-52.
[13] 陈乐瑞,孔金生.基于改进遗传算法的网络路由优化研究[J].计算机应用与软件,2013,30(4):135-137.
[14] SAMPSON J R.Adaptation in natural and artificial systems (John H.Holland)[J].SIAM Review,2006,18(3):529-530.
[15] HAMIDA S B,SCHOENAUER M.ASCHEA:new results using adaptive segregational constraint handling[C]//Proceedings of the 2002 congress on evolutionary computation.Honolulu,HI,USA:IEEE,2002:884-889.
[16] HE L,MORT N.Hybrid genetic algorithms for telecommunications network back-up routeing[J].BT Technology Journal,2000,18(4):42-50.