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

计算机与自动化 | Updated：2022-12-09

- Topology awareness algorithm for virtual network mapping
- Topology awareness algorithm for virtual network mapping
- 信息与电子工程前沿（英文） 2012年13卷第3期页码：178-186
- 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：
  
  Project supported by the National Basic Research Program (973) of China (No. 2011CB302601), the National Natural Science Foundation of China (No. 90818028), and the National High-Tech R & D Program (863) of China (No. 2007AA010301)
- DOI：10.1631/jzus.C1100282
  中图分类号： TP393
- 收稿：2011-09-26，
  
  修回：2012-;2-;8，
  
  纸质出版：2012-03
- Accepted：
Scan QR Code
Topology awareness algorithm for virtual network mapping[J]. 信息与电子工程前沿（英文）, 2012,13(3):178-186.

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.
Topology awareness algorithm for virtual network mapping[J]. 信息与电子工程前沿（英文）, 2012,13(3):178-186. DOI： 10.1631/jzus.C1100282.

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

浏览量

Downloads

CSCD

文章被引用时，请邮件提醒。

Submit

工具集

关联资源

A virtual network mapping algorithm based on integer programming

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