Virtual network embedding through topology-aware node ranking
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
Cordella L.P., 2001, 3rd IAPR-TC15 Workshop on Graph-based Representations in Pattern Recognition, 149
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.
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.
Page L., 1998, Stanford Digital Library Technologies Project
Seneta E., 2006, Springer Verlag
Turner JS, IEEE Global Telecommunications Conference, 2005. GLOBECOM'05, 2