Virtual network embedding through node connectivity

doi:10.1016/S1005-8885(15)60620-3

中国邮电高校学报(英文) ›› 2015, Vol. 22 ›› Issue (1): 17-23.doi: 10.1016/S1005-8885(15)60620-3

Virtual network embedding through node connectivity

丁健¹,黄韬¹,王健²,胡文博¹,刘江¹,刘韵洁²

1. 北京邮电大学
2. 北京邮电大学信息与通信工程学院

收稿日期:2014-07-23 修回日期:2014-09-24 出版日期:2015-02-28 发布日期:2015-02-28
通讯作者: 丁健 E-mail:buptsky@gmail.com
基金资助:
国家973重点基础研究发展计划;国家自然科学基金;中央高校基本科研业务费专项资金

Virtual network embedding through node connectivity

Received:2014-07-23 Revised:2014-09-24 Online:2015-02-28 Published:2015-02-28
Contact: Jian Ding E-mail:buptsky@gmail.com
Supported by:
National Basic Research Program (973) of China;National Natural Science Foundation of China;the Fundamental Research Funds for the Central Universities

摘要/Abstract

摘要： Virtual network embedding (VNE) is an essential part of network virtualization, which is considered as one of the most promising way for the future network. Its main object is to efficiently assign the nodes and links of a virtual network (VN) to a shared substrate network (SN). The NP-hard and exiting studies have put forward several heuristic algorithms. However, most of the algorithms only consider the local resource of nodes, such as CPU and bandwidth (BW), to decide the embedding, and ignore the significant impact of network attributes. Based on the attributes of entire network, a model of the connectivity between each pair of nodes was formulated to measure the resource ranking of the nodes, and a new two-stage embedding algorithm was proposed. Thereafter, the node mapping and link mapping can be jointly considered. Extensive simulation shows that the proposed algorithm improves the performance of VNE by increasing the revenue/cost ratio and acceptance ratio of VN requests while reducing the runtime.

关键词: virtual network virtualization, VNE, attributes of entire network, connectivity

Abstract: Virtual network embedding (VNE) is an essential part of network virtualization, which is considered as one of the most promising way for the future network. Its main object is to efficiently assign the nodes and links of a virtual network (VN) to a shared substrate network (SN). The NP-hard and exiting studies have put forward several heuristic algorithms. However, most of the algorithms only consider the local resource of nodes, such as CPU and bandwidth (BW), to decide the embedding, and ignore the significant impact of network attributes. Based on the attributes of entire network, a model of the connectivity between each pair of nodes was formulated to measure the resource ranking of the nodes, and a new two-stage embedding algorithm was proposed. Thereafter, the node mapping and link mapping can be jointly considered. Extensive simulation shows that the proposed algorithm improves the performance of VNE by increasing the revenue/cost ratio and acceptance ratio of VN requests while reducing the runtime.

Key words: virtual network virtualization, VNE, attributes of entire network, connectivity

参考文献

1. Anderson T, Peterson L, Shenker S, et al. Overcoming the Internet impasse through virtualization. Computer, 2005, 38(4): 34-41

2. Bavier A, Feamster N, Huang M, et al. VINI veritas: Realistic and controlled network experimentation. ACM SIGCOMM Computer Communication Review, 2006,36(4): 3-14

3. Turner J S, Taylor D E. Diversifying the Internet. Proceedings of the IEEE Global Telecommunications Conference (GLOBECOM’05): Vol 6, Nov 28-Dec2, 2005, St Louis, MO, USA. Piscataway, NJ, USA: IEEE, 2005: 6p

4. Feamster N, Gao L, Rexford J. How to lease the Internet in your spare time. ACM SIGCOMM Computer Communication Review, 2007, 37(1): 61-64

5. Fischer A, Botero J F, Till Beck M, et al. Virtual network embedding: A survey. IEEE Communications Surveys & Tutorials, 2013, 15(4): 1888-1906

6. Ricci R, Alfeld C, Lepreau J. A solver for the network testbed mapping problem. ACM SIGCOMM Computer Communication Review, 2003, 33(2): 65-81

7. Lu J, Turner J. Efficient mapping of virtual networks onto a shared substrate. WUCSE-2006-35. St Louis, MO, USA: Department of Computer Science and Engineering, Washington University in St Louis, 2006

8. Zhu Y, Ammar M H. Algorithms for assigning substrate network resources to virtual network components. Proceedings of the 25th Annual Joint Conference of the IEEE Computer and Communications (INFOCOM’06): Vol 5, Apr 23-29, 2006, Barcelona, Spain. Piscataway, NJ, USA: IEEE, 2006: 12p

9. Fan J, Ammar M H. Dynamic topology configuration in service overlay networks: A study of reconfiguration policies. Proceedings of the 25th Annual Joint Conference of the IEEE Computer and Communications (INFOCOM’06): Vol 5, Apr 23-29, 2006, Barcelona, Spain. Piscataway, NJ, USA: IEEE, 2006:12p

10. Yu M, Yi Y, Rexford J, et al. Rethinking virtual network embedding: Substrate support for path splitting and migration. ACM SIGCOMM Computer Communication Review, 2008, 38(2): 17-29

11. Cheng X, Su S, Zhang Z, et al. Virtual network embedding through topology-aware node ranking. ACM SIGCOMM Computer Communication Review, 2011, 41(2): 38-47

12. Wang Z, Han Y, Lin T, et al. Virtual network embedding by exploiting topological information. Proceedings of the IEEE Global Communications Conference (GLOBECOM’12), Dec 3-7, 2012, Anaheim, CA, USA. Piscataway, NJ, USA: IEEE, 2012: 2603-2608

13. Liu J, Huang T, Chen J Y, et al. A new algorithm based on the proximity principle for the virtual network embedding problem. Journal of Zhejiang University: Science C, 2011,12(11), 910-918

14. Chowdhury N M M K, Rahman M R, Boutaba R. Virtual network embedding with coordinated node and link mapping. Proceedings of the 28th Annual Joint Conference of the IEEE Computer and Communications (INFOCOM’09), Apr 19-25, 2009, Rio de Janeiro, Brazil. Piscataway, NJ, USA: IEEE, 2009: 783-791

Virtual network embedding through node connectivity

Virtual network embedding through node connectivity

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 0

编辑推荐

Metrics

本文评价