Virtual network embedding through topology-aware node ranking

Computer Communication Review - Tập 41 Số 2 - Trang 38-47 - 2011
Xiang Cheng1, Sen Su1, Zhongbao Zhang1, Hanchi Wang1, Fangchun Yang1, Yan Luo2, Jie Wang2
1Beijing University of Posts and Telecommunications, Beijing, China
2[University of Massachusetts Lowell, Lowell, USA]

Tóm tắt

Virtualizing and sharing networked resources have become a growing trend that reshapes the computing and networking architectures. Embedding multiple virtual networks (VNs) on a shared substrate is a challenging problem on cloud computing platforms and large-scale sliceable network testbeds. In this paper we apply the Markov Random Walk (RW) model to rank a network node based on its resource and topological attributes. This novel topology-aware node ranking measure reflects the relative importance of the node. Using node ranking we devise two VN embedding algorithms. The first algorithm maps virtual nodes to substrate nodes according to their ranks, then embeds the virtual links between the mapped nodes by finding shortest paths with unsplittable paths and solving the multi-commodity flow problem with splittable paths. The second algorithm is a backtracking VN embedding algorithm based on breadth-first search, which embeds the virtual nodes and links during the same stage using node ranks. Extensive simulation experiments show that the topology-aware node rank is a better resource measure and the proposed RW-based algorithms increase the long-term average revenue and acceptance ratio compared to the existing embedding algorithms.

Từ khóa


Tài liệu tham khảo

Amazonec2 http://aws.amazon.com/ec2/. Amazonec2 http://aws.amazon.com/ec2/.

VNE-RW Simulator http://int.bupt.edu.cn/~sensu/vne-rw.html. VNE-RW Simulator http://int.bupt.edu.cn/~sensu/vne-rw.html.

VNE Simulator http://www.cs.princeton.edu/~minlanyu/embed.tar.gz. VNE Simulator http://www.cs.princeton.edu/~minlanyu/embed.tar.gz.

R.K. Ahuja T.L. Magnanti J.B. Orlin and K. Weihe. Network fows: theory algorithms and applications. Prentice hall Englewood Cliffs NJ 1993. R.K. Ahuja T.L. Magnanti J.B. Orlin and K. Weihe. Network fows: theory algorithms and applications. Prentice hall Englewood Cliffs NJ 1993.

Andersen David G., 2002, Unpublished Manuscript

10.1145/1052934.1052938

10.1007/978-3-642-12963-6_3

10.1109/MCOM.2009.5183468

10.1109/INFCOM.2009.5061987

Cordella L.P., 2001, 3rd IAPR-TC15 Workshop on Graph-based Representations in Pattern Recognition, 149

10.1109/TKDE.2004.1264818

10.1109/SFCS.1994.365697

10.1109/INFOCOM.2006.139

10.1145/1198255.1198265

Global Environment for Network Innovations. National Science Foundation http://www.geni.net/ August 2005. Global Environment for Network Innovations. National Science Foundation http://www.geni.net/ August 2005.

10.1109/TPAMI.2005.138

C. Guo G. Lu H.J. Wang S. Yang C. Kong P. Sun W. Wu Y. Zhang MSR Asia and MSR Redmond. SecondNet: A Data Center Network Virtualization Architecture with Bandwidth Guarantees. C. Guo G. Lu H.J. Wang S. Yang C. Kong P. Sun W. Wu Y. Zhang MSR Asia and MSR Redmond. SecondNet: A Data Center Network Virtualization Architecture with Bandwidth Guarantees.

10.1145/380752.380830

10.1145/1544012.1544027

10.1109/ICC.2008.1056

10.1145/1592648.1592662

Page L., 1998, Stanford Digital Library Technologies Project

10.1145/956981.956988

Seneta E., 2006, Springer Verlag

10.1109/GLOCOM.2003.1258787

Turner JS, IEEE Global Telecommunications Conference, 2005. GLOBECOM'05, 2

10.1145/1355734.1355737

10.1109/INFOCOM.2006.322

Thông tin
Thông tin xuất bản

Computer Communication Review

Tập 41 Số 2

38-47

Thông tin tác giả