An efficient and coordinated mapping algorithm in virtualized SDN networks

Shui-qing GONG; Jing CHEN; Qiao-yan KANG; Qing-wei MENG; Qing-chao ZHU; Si-yi ZHAO

doi:10.1631/FITEE.1500387

Your Location：

Home >

Browse articles >

An efficient and coordinated mapping algorithm in virtualized SDN networks

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

- An efficient and coordinated mapping algorithm in virtualized SDN networks
- 面向虚拟SDN网络的高效协调映射算法
- Frontiers of Information Technology & Electronic Engineering Vol. 17, Issue 7, Pages: 701-716(2016)
- Affiliations：
  
  College of Information and Navigation, Air Force Engineering University, Xi’an 710077, China
- Author bio：
  
  E-mail:gsq0121@126.com
- Funds：
- DOI：10.1631/FITEE.1500387
  CLC： TP393
- Received：10 November 2015，
  
  Accepted：16 February 2016，
  
  Published：2016-07
- Accepted：
Scan QR Code
Shui-qing GONG, Jing CHEN, Qiao-yan KANG, et al. An efficient and coordinated mapping algorithm in virtualized SDN networks[J]. Frontiers of Information Technology & Electronic Engineering, 2016, 17(7): 701-716.
DOI：

Shui-qing GONG, Jing CHEN, Qiao-yan KANG, et al. An efficient and coordinated mapping algorithm in virtualized SDN networks[J]. Frontiers of Information Technology & Electronic Engineering, 2016, 17(7): 701-716. DOI： 10.1631/FITEE.1500387.

摘要

目的

针对SDN网络虚拟化环境，考虑虚拟网络映射和控制器部署，以最小化交换机到控制器的平均时延和映射开销为目标，建立虚拟SDN网络(vSDN)映射问题的数学模型，并提出一种高效协调的虚拟SDN网络映射算法。

创新点

基于底层节点和链路的可用资源数量、底层节点间的时延和距离等因素，提出一种支持时延优化的高效协调虚拟SDN网络映射算法。

方法

将vSDN中的控制器作为一个特殊的虚拟节点，在vSDN映射过程中同时进行控制器的优化部署，并以最小化交换机到控制器的平均时延和底层SDN网络映射开销为目标，建立vSDN映射的整数线性规划模型，并提出一种支持时延优化的高效协调vSDN映射算法。该算法在节点映射阶段首先进行控制器的部署，然后进行虚拟节点的映射。在控制器部署过程中，考虑底层节点可用资源和节点之间的通信时延，引入控制器位置选择因子(CLSF)对底层节点进行排序，并将vSDN的控制器映射到CLSF值最大的底层节点上。在虚拟节点映射过程中，首先构建虚拟节点的映射树，并考虑底层节点可用资源、底层节点到控制器的时延和距离等因素，引入节点映射因子(NR)对底层节点进行排序。然后按照广度优先搜索策略将虚拟节点映射至NR值最大的底层节点上。节点映射完成后，采用

最短路径法映射虚拟链路。

结论

本文提出的虚拟SDN网络映射算法能够有效协调控制器部署、虚拟节点映射和链路映射三个阶段，保持了较高的映射收益开销比和vSDN请求接受率，并有效降低了交换机到控制器的时延(图3-6)。

Abstract

Software-defined networking (SDN) enables the network virtualization through SDN hypervisors to share the underlying physical SDN network among multiple logically isolated virtual SDN networks (vSDNs)

each with its own controller. The vSDN embedding

which refers to mapping a number of vSDNs to the same substrate SDN network

is a key problem in the SDN virtualization environment. However

due to the distinctions of the SDN

such as the logically centralized controller and different virtualization technologies

most of the existing embedding algorithms cannot be applied directly to SDN virtualization. In this paper

we consider controller placement and virtual network embedding as a joint vSDN embedding problem

and formulate it into an integer linear programming with objectives of minimizing the embedding cost and the controller-to-switch delay for each vSDN. Moreover

we propose a novel online vSDN embedding algorithm called CO-vSDNE

which consists of a node mapping stage and a link mapping stage. In the node mapping stage

CO-vSDNE maps the controller and the virtual nodes to the substrate nodes on the basis of the controller-to-switch delay and takes into account the subsequent link mapping at the same time. In the link mapping stage

CO-vSDNE adopts the

-shortest path algorithm to map the virtual links. The evaluation results with simulation and Mininet emulation show that the proposed CO-vSDNE not only significantly increases the long-term revenue to the cost ratio and acceptance ratio while guaranteeing low average and maximum controller-to-switch delay

but also achieves good vSDN performance in terms of end-to-end delay and throughput.

关键词

Keywords

references

Andersen DG Theoretical Approaches to Node Assignment , , 2002 . . Accessed on Sept. 20. 2010 Available from: http://www.cs.cmu.edu/~dga/papers/andersen-assign.ps http://www.cs.cmu.edu/~dga/papers/andersen-assign.ps . .

A Blenk , , , A Basta , , , M Reisslein , , , 等 . . Survey on network virtualization hypervisors for software defined networking . . IEEE Commun. Surv. Tutor. , , 2016 . . 18 ( ( 1 ): ): 655 - - 685 . . DOI: 10.1109/COMST.2015.2489183 http://doi.org/10.1109/COMST.2015.2489183 . .

Z Bozakov , , , P Papadimitriou . . AutoSlice: automated and scalable slicing for software-defined networks . . 2012 . . Proc. ACM CoNEXT Student Workshop . . 3 - - 4 . . DOI: 10.1145/2413247.2413251 http://doi.org/10.1145/2413247.2413251 . .

X Cheng , , , S Su , , , Z Zhang , , , 等 . . Virtual network embedding through topology-aware node ranking . . ACM SIGCOMM Comput. Commun. Rev. , , 2011 . . 41 ( ( 2 ): ): 38 - - 47 . . DOI: 10.1145/1971162.1971168 http://doi.org/10.1145/1971162.1971168 . .

RD Corin , , , M Gerola , , , R Riggio , , , 等 . . VeRTIGO: network virtualization and beyond . . 2012 . . European Workshop on Software Defined Networks . . 24 - - 29 . . DOI: 10.1109/EWSDN.2012.19 http://doi.org/10.1109/EWSDN.2012.19 . .

M Demirci , , , M Ammar . . Design and analysis of techniques for mapping virtual networks to software-defined network substrates . . Comput. Commun. , , 2014 . . 45 1 - - 10 . . DOI: 10.1016/j.comcom.2014.03.008 http://doi.org/10.1016/j.comcom.2014.03.008 . .

H Di , , , V Anand , , , HF Yu . . Design of reliable virtual infrastructure with resource sharing . . Comput. Netw. , , 2014 . . 62 137 - - 151 . . DOI: 10.1016/j.bjp.2013.09.022 http://doi.org/10.1016/j.bjp.2013.09.022 . .

J Ding , , , T Huang , , , J Liu , , , 等 . . Virtual network embedding based on real-time topological attributes . . Front. Inform. Technol. Electron.Eng. , , 2015 . . 16 ( ( 2 ): ): 109 - - 118 . . DOI: 10.1631/FITEE.1400147 http://doi.org/10.1631/FITEE.1400147 . .

D Drutskoy , , , E Keller , , , J Rexford . . Scalable network virtualization in software-defined networks . . IEEE Internet Comput. , , 2013 . . 17 ( ( 2 ): ): 20 - - 27 . . DOI: 10.1109/MIC.2012.144 http://doi.org/10.1109/MIC.2012.144 . .

D Eppstein . . Finding the k shortest paths . . SIAM J. Comput. , , 1998 . . 28 ( ( 2 ): ): 652 - - 673 . . DOI: 10.1137/S0097539795290477 http://doi.org/10.1137/S0097539795290477 . .

A Fischer , , , JF Botero , , , Beck M Till , , , 等 . . Virtual network embedding: a survey . . IEEE Commun. Surv. Tutor. , , 2013 . . 15 ( ( 4 ): ): 1888 - - 1906 . . DOI: 10.1109/SURV.2013.013013.00155 http://doi.org/10.1109/SURV.2013.013013.00155 . .

B Heller , , , R Sherwood , , , N McKeown . . The controller placement problem . . ACM SIGCOMM Comput. Commun. Rev. , , 2012 . . 42 ( ( 4 ): ): 473 - - 478 . . DOI: 10.1145/2377677.2377767 http://doi.org/10.1145/2377677.2377767 . .

Y Hu , , , W Wang , , , X Gong , , , 等 . . Reliability-aware controller placement for software-defined networks . . 2013 . . Proc. IFIP/IEEE Int. Symp. on Integrated Network Management . . 672 - - 675 . . . .

A Khan , , , A Zugenmaier , , , D Jurca , , , 等 . . Network virtualization: a hypervisor for the Internet? IEEE Commun . . Mag. , , 2012 . . 50 ( ( 1 ): ): 136 - - 143 . . DOI: 10.1109/MCOM.2012.6122544 http://doi.org/10.1109/MCOM.2012.6122544 . .

T Koponen , , , K Amidon , , , P Balland , , , 等 . . Network virtualization in multi-tenant datacenters . . 2014 . . USENIX Conf. on Networked System Design and Implementation . . 203 - - 216 . . . .

B Lantz , , , B Heller , , , N McKeown . . A network in a laptop: rapid prototyping for software-defined networks . . 2010 . . Proc. 9th ACM SIGCOMM Workshop on Hot Topics in Networks . . 19:1 - - 19:6 . . DOI: 10.1145/1868447.1868466 http://doi.org/10.1145/1868447.1868466 . .

XL Li , , , HM Wang , , , CG Guo , , , 等 . . Topology awareness algorithm for virtual network mapping . . J. Zhejiang Univ.-Sci. C (Comput. & Electron.) , , 2012 . . 13 ( ( 3 ): ): 178 - - 186 . . DOI: 10.1631/jzus.C1100282 http://doi.org/10.1631/jzus.C1100282 . .

XL Li , , , HM Wang , , , B Ding , , , 等 . . Resource allocation with multi-factor node ranking in data center networks . . Fut. Gener. Comput. Syst. , , 2014 . . 32 1 - - 12 . . DOI: 10.1016/j.future.2013.09.028 http://doi.org/10.1016/j.future.2013.09.028 . .

SH Liu , , , ZP Cai , , , H Xu , , , 等 . . Towards security-aware virtual network embedding . . Comput. Netw. , , 2015 . . 91 151 - - 163 . . DOI: 10.1016/j.comnet.2015.08.014 http://doi.org/10.1016/j.comnet.2015.08.014 . .

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 . .

R Mijumbi , , , J Serrat , , , J Rubio-Loyola , , , 等 . . Dynamic resource management in SDN-based virtualized networks . . 2014 . . Int. Conf. on Network and Service Management . . 412 - - 417 . . DOI: 10.1109/CNSM.2014.7014204 http://doi.org/10.1109/CNSM.2014.7014204 . .

E Salvadori , , , RD Corin , , , A Broglio , , , 等 . . Generalizing virtual network topologies in OpenFlow-based networks . . 2011 . . IEEE Global Telecommunications Conf. . . 1 - - 6 . . DOI: 10.1109/GLOCOM.2011.6134525 http://doi.org/10.1109/GLOCOM.2011.6134525 . .

A Schrijver . . Theory of Linear and Integer Programming , , 1998 . . : Wiley, New York, USA : . .

R Sherwood , , , G Gibb , , , KK Yap , , , 等 . . Can the production network be the testbed? . . 2010 . . 9th USENIX Symp. on Operating System Design and Implementation . . 1 - - 6 . . . .

S Su , , , ZB Zhang , , , AX Liu , , , 等 . . Energy-aware virtual network embedding . . IEEE/ACM Trans. Netw. , , 2014 . . 22 ( ( 5 ): ): 1607 - - 1620 . . DOI: 10.1109/TNET.2013.2286156 http://doi.org/10.1109/TNET.2013.2286156 . .

AJ Wang , , , M Iyer , , , R Dutta , , , 等 . . Network virtualization: technologies, perspectives, and frontiers . . J. Lightw. Technol. , , 2013 . . 31 ( ( 4 ): ): 523 - - 537 . . DOI: 10.1109/JLT.2012.2213796 http://doi.org/10.1109/JLT.2012.2213796 . .

ZM Wang , , , JX Wu , , , Y Wang , , , 等 . . Survivable virtual network mapping using optimal backup topology in virtualized SDN . . China Commun. , , 2014 . . 11 ( ( 2 ): ): 26 - - 37 . . DOI: 10.1109/CC.2014.6821735 http://doi.org/10.1109/CC.2014.6821735 . .

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 . .

B Zhou , , , W Gao , , , S Zhao , , , 等 . . Virtual network mapping for multi-domain data plane in software-defined networks . . 2014 . . Int. Conf. on Wireless Communications, Vehicular Technology, Information Theory and Aerospace & Electronic Systems . . 1 - - 5 . . DOI: 10.1109/VITAE.2014.6934439 http://doi.org/10.1109/VITAE.2014.6934439 . .

Views

Downloads

CSCD

Alert me when the article has been cited

Submit

Tools

Publicity Resources

AKself-adaptive SDN controller placement for wide area networks#

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

A virtual service placement approach based on improved quantum genetic algorithm

A video conferencing system based on SDN-enabled SVC multicast

Organizational dynamics in adaptive distributed search processes: effects on performance and the role of complexity#

Related Author

Peng XIAO

Zhi-yang LI

Song GUO

Heng QI

Wen-yu QU

Hai-sheng YU

Peng ZHANG

Lei XIONG

Related Institution

School of Information Science and Technology, Dalian Maritime University

School of Information Science and Engineering, Dalian Polytechnic University

School of Computer Science and Engineering, The University of Aizu, Aizuwakamatsu

School of Computer Science and Technology, Dalian University of Technology

School of Computer Software, Tianjin 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.

⁰