A virtual service placement approach based on improved quantum genetic algorithm

Gang XIONG; Yu-xiang HU; Le TIAN; Ju-long LAN; Jun-fei LI; Qiao ZHOU

doi:10.1631/FITEE.1500494

Your Location：

Home >

Browse articles >

A virtual service placement approach based on improved quantum genetic algorithm

Special Issue on Future Network: Software-Defined Networking | Updated：2022-05-19

- A virtual service placement approach based on improved quantum genetic algorithm
- 一种基于改进量子遗传算法的虚拟服务部署方法
- Frontiers of Information Technology & Electronic Engineering Vol. 17, Issue 7, Pages: 661-671(2016)
- Affiliations：
  
  1National Digital Switching System Engineering & Technological Research Center, Zhengzhou 450002, China
  2Department of Mathematics and Computer Science, University of Antwerp, Antwerp 2020, Belgium
- Author bio：
  
  E-mail:xg1226@126.com
- Funds：
- DOI：10.1631/FITEE.1500494
  CLC： TP393
- Received：10 November 2015，
  
  Accepted：16 February 2016，
  
  Published：2016-07
- Accepted：
Scan QR Code
Gang XIONG, Yu-xiang HU, Le TIAN, et al. A virtual service placement approach based on improved quantum genetic algorithm[J]. Frontiers of Information Technology & Electronic Engineering, 2016, 17(7): 661-671.
DOI：

Gang XIONG, Yu-xiang HU, Le TIAN, et al. A virtual service placement approach based on improved quantum genetic algorithm[J]. Frontiers of Information Technology & Electronic Engineering, 2016, 17(7): 661-671. DOI： 10.1631/FITEE.1500494.

摘要

目的

在软件定义网络和网络功能虚拟化技术不断推动网络功能服务演进和创新的同时，如何降低网络业务流量在接受服务处理时的传输时延，进而提高网络整体传输效率并降低带宽资源消耗，成为业界关注的一个新方向。

创新点

文章对当前正不断兴起的网络虚拟服务部署场景进行具体分析，提出了基于整数规划的服务部署优化模型，并利用改进的量子遗传算法对模型求解，有效提高了网络在提供服务处理时的整体传输效率。

方法

首先，对网络虚拟服务的部署场景进行具体分析，将影响业务流量传输时延的因素与网络拓扑结构和服务部署位置相关联。其次，基于网络拓扑结构和服务位置变量参数，利用整数规划模型对服务位置优化部署问题进行建模。然后，针对服务优化部署模型所涉及的NP-hard问题，提出利用改进型的量子遗传算法进行启发式模型求解。最后，实验结果表明，本文方法在降低网络整体传输时延的同时，具有较小的计算时间代价（图7、8）；与随机部署策略相比，本文方法可平均降低业务流量的传输时延约30%（图9、10），从而更加有效地保障了网络传输效率。

结论

针对新型网络体系（如软件定义网络和网络功能虚拟化）中虚拟服务场景，提出了一种优化的网络服务部署方法，有效降低了业务流量接受服务处理时的传输时延。

Abstract

Despite the critical role that middleboxes play in introducing new network functionality

management and innovation of them are still severe challenges for network operators

since traditional middleboxes based on hardware lack service flexibility and scalability. Recently

though new networking technologies

such as network function virtualization (NFV) and software-defined networking (SDN)

are considered as very promising drivers to design cost-efficient middlebox service architectures

how to guarantee transmission efficiency has drawn little attention under the condition of adding virtual service process for traffic. Therefore

we focus on the service deployment problem to reduce the transport delay in the network with a combination of NFV and SDN. First

a framework is designed for service placement decision

and an integer linear programming model is proposed to resolve the service placement and minimize the network transport delay. Then a heuristic solution is designed based on the improved quantum genetic algorithm. Experimental results show that our proposed method can calculate automatically the optimal placement schemes. Our scheme can achieve lower overall transport delay for a network compared with other schemes and reduce 30% of the average traffic transport delay compared with the random placement scheme.

关键词

Keywords

references

JW Anderson , , , R Braud , , , R Kapoor , , , 等 . . xOMB: extensible open middleboxes with commodity servers . . 2012 . . Proc. 8th ACM/IEEE Symp. on Architectures for Networking and Communications Systems . . 49 - - 60 . . DOI: 10.1145/2396556.2396566 http://doi.org/10.1145/2396556.2396566 . .

B Anwer , , , T Benson , , , N Feamster , , , 等 . . A slick control plane for network middleboxes . . 2013 . . Proc. 2nd ACM SIGCOMM Workshop on Hot Topics in Software Defined Networking . . 147 - - 148 . . DOI: 10.1145/2491185.2491223 http://doi.org/10.1145/2491185.2491223 . .

A Basta , , , W Kellerer , , , M Hoffmann , , , 等 . . Applying NFV and SDN to LTE mobile core gateways, the functions placement problem . . 2014 . . Proc. 4th Workshop on All Things Cellular: Operations, Applications, and Challenges . . 33 - - 38 . . DOI: 10.1145/2627585.2627592 http://doi.org/10.1145/2627585.2627592 . .

B Carpenter , , , B Brim . . Middleboxes: Taxonomy and Issues, RFC 3234. The Internet Engineering Task Force , , 2002 . . Available from: http://www.rfc-base.org/rfc-3234.html http://www.rfc-base.org/rfc-3234.html . .

GZ Cheng , , , HC Chen , , , HC Hu , , , 等 . . Enabling network function combination via service chain instantiation . . Comput. Netw. , , 2015 . . 92 ( ( Part 2 ): ): 396 - - 407 . . DOI: 10.1016/j.comnet.2015.09.015 http://doi.org/10.1016/j.comnet.2015.09.015 . .

M Chiosi , , , D Clarke , , , P Willis , , , 等 . . Network functions virtualisation-introductory white paper. SDN and OpenFlow World Congress , , 2012 . . Available from: https://portal.etsi.org/NFV/NFV_White_Paper.pdf https://portal.etsi.org/NFV/NFV_White_Paper.pdf . .

F de Turck , , , R Boutaba , , , P Chemouil , , , 等 . . Guest editors' introduction: special issue on efficient management of SDN/NFV-based systems-part I . . IEEE Trans. Netw. Serv. Manag. , , 2015 . . 12 ( ( 1 ): ): 1 - - 3 . . DOI: 10.1109/TNSM.2015.2403775 http://doi.org/10.1109/TNSM.2015.2403775 . .

SK Fayazbakhsh , , , L Chaing , , , V Sekar , , , 等 . . Enforcing network-wide policies in the presence of dynamic middlebox actions using FlowTags . . 2014 . . 11th USENIX Symp. on Networked Systems Design and Implementation . . 533 - - 546 . . . .

A Gember , , , R Grandl , , , A Anand , , , 等 . . Stratos: virtual middleboxes as first-class entities . . Technical Report, No. TR1771, University of Wisconsin-Madison, WI , , 2012a . . .

A Gember , , , P Prabhu , , , Z Ghadiyali , , , 等 . . Towards software-defined middlebox networking . . 2012b . . Proc. 11th ACM Workshop on Hot Topics in Networks . . 7 - - 12 . . DOI: 10.1145/2390231.2390233 http://doi.org/10.1145/2390231.2390233 . .

A Gember , , , R Viswanathan , , , C Prakash , , , 等 . . OpenNF: enabling innovation in network function control . . 2014 . . Proc. ACM Conf. on SIGCOMM . . 163 - - 174 . . DOI: 10.1145/2740070.2626313 http://doi.org/10.1145/2740070.2626313 . .

A Greenberg , , , G Hjalmtysson , , , DA Maltz , , , 等 . . A clean slate 4D approach to network control and management . . ACM SIGCOMM Comput. Commun. Rev. , , 2005 . . 35 ( ( 5 ): ): 41 - - 54 . . DOI: 10.1145/1096536.1096541 http://doi.org/10.1145/1096536.1096541 . .

N Gude , , , T Koponen , , , J Pettit , , , 等 . . NOX: towards an operating system for networks . . ACM SIGCOMM Comput. Commun. Rev. , , 2008 . . 38 ( ( 3 ): ): 105 - - 110 . . DOI: 10.1145/1384609.1384625 http://doi.org/10.1145/1384609.1384625 . .

A Gushchin , , , A Walid , , , A Tang . . Scalable routing in SDN-enabled networks with consolidated middleboxes . . 2015 . . Proc. ACM SIGCOMM Workshop on Hot Topics in Middleboxes and Network Function Virtualization . . 55 - - 60 . . DOI: 10.1145/2785989.2785999 http://doi.org/10.1145/2785989.2785999 . .

J Hwang , , , KK Ramakrishnan , , , T Wood . . NetVM: high performance and flexible networking using virtualization on commodity platforms . . IEEE Trans. Netw. Serv. Manag. , , 2015 . . 12 ( ( 1 ): ): 34 - - 47 . . DOI: 10.1109/TNSM.2015.2401568 http://doi.org/10.1109/TNSM.2015.2401568 . .

D Joseph , , , I Stoica . . Modeling middleboxes . . IEEE Netw. , , 2008 . . 22 ( ( 5 ): ): 20 - - 25 . . DOI: 10.1109/MNET.2008.4626228 http://doi.org/10.1109/MNET.2008.4626228 . .

S Lange , , , S Gebert , , , T Zinner , , , 等 . . Heuristic approaches to the controller placement problem in large scale SDN networks . . IEEE Trans. Netw. Serv. Manag. , , 2015 . . 12 ( ( 1 ): ): 4 - - 17 . . DOI: 10.1109/TNSM.2015.2402432 http://doi.org/10.1109/TNSM.2015.2402432 . .

Y Li , , , M Chen . . Software-defined network function virtualization: a survey . . IEEE Access , , 2015 . . 3 2542 - - 2553 . . DOI: 10.1109/ACCESS.2015.2499271 http://doi.org/10.1109/ACCESS.2015.2499271 . .

B Lu , , , JY Chen , , , HY Cui , , , 等 . . A virtual network mapping algorithm based on integer programming . . J. Zhejiang Univ.-Sci. C (Comput. & Electron.) , , 2013 . . 14 ( ( 12 ): ): 899 - - 908 . . DOI: 10.1631/jzus.C1300120 http://doi.org/10.1631/jzus.C1300120 . .

A Malossini , , , E Blanzieri , , , T Calarco. . . Quantum genetic optimization . . IEEE Trans. Evol. Comput. , , 2008 . . 12 ( ( 2 ): ): 231 - - 241 . . DOI: 10.1109/TEVC.2007.905006 http://doi.org/10.1109/TEVC.2007.905006 . .

J Matias , , , J Garay , , , N Toledo , , , 等 . . Toward an SDN-enabled NFV architecture . . IEEE Commun. Mag. , , 2015 . . 53 ( ( 4 ): ): 187 - - 193 . . DOI: 10.1109/MCOM.2015.7081093 http://doi.org/10.1109/MCOM.2015.7081093 . .

N McKeown , , , T Anderson , , , H Balakrishnan , , , 等 . . OpenFlow: enabling innovation in campus networks . . ACM SIGCOMM Comput. Commun. Rev. , , 2008 . . 38 ( ( 2 ): ): 69 - - 74 . . DOI: 10.1145/1355734.1355746 http://doi.org/10.1145/1355734.1355746 . .

A Mohammadkhan , , , S Ghapani , , , GY Liu , , , 等 . . Virtual function placement and traffic steering in flexible and dynamic software defined networks . . 2015 . . IEEE Int. Workshop on Local and Metropolitan Area Networks . . 1 - - 6 . . DOI: 10.1109/LANMAN.2015.7114738 http://doi.org/10.1109/LANMAN.2015.7114738 . .

AM Mohammed , , , NA Elhefnawy , , , MM El-Sherbiny , , , 等 . . Quantum crossover based quantum genetic algorithm for solving non-linear programming . . 2012 . . 8th Int. Conf. on Informatics and Systems . . BIO-145 - - BIO-153 . . . .

BAA Nunes , , , M Mendonca , , , XN Nguyen , , , 等 . . A survey of software-defined networking: past, present, and future of programmable networks . . IEEE Commun. Surv. Tutor. , , 2014 . . 16 ( ( 3 ): ): 1617 - - 1634 . . DOI: 10.1109/SURV.2014.012214.00180 http://doi.org/10.1109/SURV.2014.012214.00180 . .

Open Networking Foundation (ONF) . . Software-Defined Networking: the New Norm for Networks . . 2012 . . ONF White Paper . . . .

ZA Qazi , , , CC Tu , , , L Chiang , , , 等 . . SIMPLE-fying middlebox policy enforcement using SDN . . 2013 . . Proc. ACM SIGCOMM Conf . . 27 - - 38 . . DOI: 10.1145/2486001.2486022 http://doi.org/10.1145/2486001.2486022 . .

H Qi , , , M Shiraz , , , JY Liu , , , 等 . . Data center network architecture in cloud computing: review, taxonomy, and open research issues . . J. Zhejiang Univ.-Sci. C (Comput. & Electron.) , , 2014 . . 15 ( ( 9 ): ): 776 - - 793 . . DOI: 10.1631/jzus.C1400013 http://doi.org/10.1631/jzus.C1400013 . .

S Rajagopalan , , , D Williams , , , H Jamjoom , , , 等 . . Split/Merge: system support for elastic execution in virtual middleboxes . . 2013 . . 10th USENIX Symp. on Networked Systems Design and Implementation . . 227 - - 240 . . . .

V Sekar , , , S Ratnasamy , , , MK Reiter , , , 等 . . The middlebox manifesto: enabling innovation in middlebox deployment . . 2011 . . Proc. 10th ACM Workshop on Hot Topics in Networks . . 1 - - 6 . . DOI: 10.1145/2070562.2070583 http://doi.org/10.1145/2070562.2070583 . .

V Sekar , , , N Egi , , , S Ratnasamy , , , 等 . . Design and implementation of a consolidated middlebox architecture . . 2012 . . Proc. 9th USENIX Conf. on Networked Systems Design and Implementation . . 323 - - 336 . . . .

J Shen , , , WB He , , , X Liu , , , 等 . . End-to-end delay analysis for networked systems . . Front. Inform. Technol. Electron. Eng. , , 2015 . . 16 ( ( 9 ): ): 732 - - 743 . . DOI: 10.1631/FITEE.1400414 http://doi.org/10.1631/FITEE.1400414 . .

J Sherry , , , S Hasan , , , C Scott , , , 等 . . Making middleboxes someone else's problem: network processing as a cloud service . . ACM SIGCOMM Comput. Commun. Rev. , , 2012 . . 42 ( ( 4 ): ): 13 - - 24 . . DOI: 10.1145/2377677.2377680 http://doi.org/10.1145/2377677.2377680 . .

M Walfish , , , J Stribling , , , M Krohn , , , 等 . . Middleboxes no longer considered harmful . . 2004 . . Proc. 6th Symp. on Operating Systems Design & Implementation . . 215 - - 230 . . . .

EW Zegura , , , KL Calvert , , , S Bhattacharjee . . How to model an internetwork . . 1996 . . 15th Annual Joint Conf. of the IEEE Computer and Communications Societies . . 594 - - 602 . . DOI: 10.1109/INFCOM.1996.493353 http://doi.org/10.1109/INFCOM.1996.493353 . .

Y Zhang , , , N Beheshti , , , L Beliveau , , , 等 . . StEERING: a software-defined networking for inline service chaining . . 2013 . . Proc. 21st IEEE Int. Conf. on Network Protocols . . 1 - - 10 . . DOI: 10.1109/ICNP.2013.6733615 http://doi.org/10.1109/ICNP.2013.6733615 . .

Views

Downloads

CSCD

Alert me when the article has been cited

Submit

Tools

Publicity Resources

A forwarding graph embedding algorithm exploiting regional topology information

A secure and high-performance multi-controller architecture for software-defined networking

An efficient and coordinated mapping algorithm in virtualized SDN networks

AKself-adaptive SDN controller placement for wide area networks#

A video conferencing system based on SDN-enabled SVC multicast

Related Author

Fan ZHANG

Yu-xing MAO

Zhen-peng WANG

Hong-chao HU

Huan-zhao WANG

Peng ZHANG

Lei XIONG

Xin LIU

Related Institution

National Digital Switching System Engineering & Technological R&D Center

Department of Computer Science and Technology, Xi'an Jiaotong University

Science and Technology on Information Transmission and Dissemination in Communication Networks Laboratory

MOE Key Laboratory for Intelligent Networks and Network Security, Xi'an Jiaotong University

College of Information and Navigation, Air Force Engineering University

Chat

Address：Zhejiang University Press, 148 Tianmushan Road, Hangzhou, China Postal code：310028
Tel：+86-571-88273162 Email：fitee@zju.edu.cn
It is recommended to read the content of this site in Chrome&IE9+. Please switch to extreme mode in browser 360.
Cookies We use cookies to help provide and enhance our service and tailor content. By continuing, you agree to the use of cookies.

⁰