Topology awareness algorithm for virtual network mapping

Xiao-ling LI; Huai-min WANG; Chang-guo GUO; Bo DING; Xiao-yong LI; Wen-qi BI; Shuang TAN

doi:10.1631/jzus.C1100282

Your Location：

Home >

Browse articles >

Topology awareness algorithm for virtual network mapping

Computer & Automation | Updated：2022-12-09

- Topology awareness algorithm for virtual network mapping
- Topology awareness algorithm for virtual network mapping
- Frontiers of Information Technology & Electronic Engineering Vol. 13, Issue 3, Pages: 178-186(2012)
- Affiliations：
  
  1.National Key Laboratory of Parallel and Distributed Processing, National University of Defense Technology, Changsha 410073, China
  2.School of Computer, National University of Defense Technology, Changsha 410073, China
  3.China Electronic Systems Engineering Corporation, Beijing 100039, China
  4.The Northern Institute of Electronic Equipment of China, Beijing 100083, China
- Author bio：
  
  [ "Xiao-ling LI, nudtlxl@163.com" ]
- Funds：
- DOI：10.1631/jzus.C1100282
  CLC： TP393
- Received：26 September 2011，
  
  Revised：2012-;2-;8，
  
  Published：2012-03
- Accepted：
Scan QR Code
Xiao-ling LI, Huai-min WANG, Chang-guo GUO, et al. Topology awareness algorithm for virtual network mapping[J]. Frontiers of Information Technology & Electronic Engineering, 2012, 13(3): 178-186.
DOI：

Xiao-ling LI, Huai-min WANG, Chang-guo GUO, et al. Topology awareness algorithm for virtual network mapping[J]. Frontiers of Information Technology & Electronic Engineering, 2012, 13(3): 178-186. DOI： 10.1631/jzus.C1100282.

摘要

Abstract

Network virtualization is recognized as an effective way to overcome the ossification of the Internet. However

the virtual network mapping problem (VNMP) is a critical challenge

focusing on how to map the virtual networks to the substrate network with efficient utilization of infrastructure resources. The problem can be divided into two phases: node mapping phase and link mapping phase. In the node mapping phase

the existing algorithms usually map those virtual nodes with a complete greedy strategy

without considering the topology among these virtual nodes

resulting in too long substrate paths (with multiple hops). Addressing this problem

we propose a topology awareness mapping algorithm

which considers the topology among these virtual nodes. In the link mapping phase

the new algorithm adopts the k-shortest path algorithm. Simulation results show that the new algorithm greatly increases the long-term average revenue

the acceptance ratio

and the long-term revenue-to-cost ratio (

关键词

Keywords

references

T. Anderson , , , L. Peterson , , , S. Shenker , , , J. Turner . . Overcoming the Internet impasse through virtualization . . Computer , , 2005 . . 38 ( ( 4 ): ): 34 - - 41 . . DOI: 10.1109/MC.2005.136 http://doi.org/10.1109/MC.2005.136 . .

N. Bansal , , , K.W. Lee , , , V. Nagarajan , , , M. Zafer . . Minimum Congestion Mapping in a Cloud . . Proc.30th Annual ACM SIGACT-SIGOPS Symp. on Principles of Distributed Computing , , 2011 . . p.267 - - 276 . . DOI: 10.1145/1993806.1993854 http://doi.org/10.1145/1993806.1993854 . .

A. Bavier , , , N. Feamster , , , M. Huang , , , L. Peterson , , , J. Rexford . . In VINI veritas: realistic and controlled network experimentation . . ACM SIGCOMM Comput. Commun. Rev. , , 2006 . . 36 ( ( 4 ): ): 3 - - 14 . . DOI: 10.1145/1151659.1159916 http://doi.org/10.1145/1151659.1159916 . .

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

N.M.M.K. Chowdhury , , , M.R. Rahman , , , R. Boutaba . . Network virtualization: state of the art and research challenges . . IEEE Commun. Mag. , , 2009a . . 47 ( ( 7 ): ): 20 - - 26 . . DOI: 10.1109/MCOM.2009.5183468 http://doi.org/10.1109/MCOM.2009.5183468 . .

N.M.M.K. Chowdhury , , , M.R. Rahman , , , R. Boutaba . . Virtual Network Embedding with Coordinated Node and Link Mapping . . Proc.28th IEEE Int. Conf. on Computer Communications , , 2009b . . p.783 - - 791 . . DOI: 10.1109/INFOCOM.2009.5061987 http://doi.org/10.1109/INFOCOM.2009.5061987 . .

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

J. Fan , , , M.H. Ammar . . Dynamic Topology Configuration in Service Overlay Networks: a Study of Reconfiguration Policies . . Proc.25th IEEE Int. Conf. on Computer Communications , , 2006 . . p.1 - - 12 . . DOI: 10.1109/INFOCOM.2006.139 http://doi.org/10.1109/INFOCOM.2006.139 . .

N. Feamster , , , L. Gao , , , J. Rexford . . How to lease the Internet in your spare time . . ACM SIGCOMM Comput. Commun. Rev. , , 2007 . . 37 ( ( 1 ): ): 61 - - 64 . . DOI: 10.1145/1198255.1198265 http://doi.org/10.1145/1198255.1198265 . .

C. Guo , , , G. Lu , , , H.J. Wang , , , S. Yang , , , C. Kong , , , P. Sun , , , W. Wu , , , Y. Zhang . . SecondNet: a Data Center Network Virtualization Architecture with Bandwidth Guarantees . . Proc.6th Int. Conf. on Emerging Networking Experiments and Technologies , , 2010 . . p.15 - - 26 . . DOI: 10.1145/1921168.1921188 http://doi.org/10.1145/1921168.1921188 . .

J. Lischka , , , H. Karl . . A Virtual Network Mapping Algorithm Based on Subgraph Isomorphism Detection . . Proc.1st ACM SIGCOMM Workshop on Virtualized Infrastructure Systems and Architectures , , 2009 . . p.81 - - 88 . . . .

J. Lu , , , J. Turner . . Efficient Mapping of Virtual Networks onto a Shared Substrate . . Technical Report No. WUCSE-2006-35, Washington University, USA , , 2006 . . .

J.S. Turner , , , D.E. Taylor . . Diversifying the Internet . . IEEE Global Telecommunications Conf. , , 2005 . . p.755 - - 760 . . DOI: 10.1109/GLOCOM.2005.1577741 http://doi.org/10.1109/GLOCOM.2005.1577741 . .

Q.B. Wang , , , X. Jin , , , L. He , , , Y. Zhao . . Virtualization and Cloud Computing , , : : Beijing, China Publishing House of Electronic Industry , , 2009 . . p.26 - - 30 . . . .

M. Yu , , , Y. Yi , , , J. Rexford , , , M. Chiang . . Rethinking virtual network embedding: substrate support for path splitting and migration . . ACM SIGCOMM Commun. Rev. , , 2008 . . 38 ( ( 2 ): ): 17 - - 29 . . DOI: 10.1145/1355734.1355737 http://doi.org/10.1145/1355734.1355737 . .

E.W. Zegura , , , K.L. Calvert , , , S. Bhattacharjee . . How to Model an Internetwork . . Proc.15th IEEE Int. Conf. on Computer Communication , , 1996 . . p.594 - - 602 . . DOI: 10.1109/INFCOM.1996.493353 http://doi.org/10.1109/INFCOM.1996.493353 . .

Y. Zhu , , , M. Ammar . . Algorithms for Assigning Substrate Network Resources to Virtual Network Components . . Proc.25th IEEE Int. Conf. on Computer Communications , , 2006 . . p.1 - - 12 . . DOI: 10.1109/INFOCOM.2006.322 http://doi.org/10.1109/INFOCOM.2006.322 . .

Views

Downloads

CSCD

Alert me when the article has been cited

Submit

Tools

Publicity Resources

A virtual network mapping algorithm based on integer programming

A new algorithm based on the proximity principle for the virtual network embedding problem

Related Author

Bo LU

Jian-ya CHEN

Hong-yan CUI

Tao HUANG

Yun-jie LIU

Jiang LIU

Tao HUANG

Jian-ya CHEN

Related Institution

Beijing Key Laboratory of Network System Architecture and Convergence, Beijing University of Posts and Telecommunications

Key Laboratory of Universal Wireless Communications of Ministry of Education, Beijing University of Post and Telecommunications

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.

⁰