Virtual network embedding through topology-aware node ranking
Top Cited Papers
- 15 April 2011
- journal article
- Published by Association for Computing Machinery (ACM) in ACM SIGCOMM Computer Communication Review
- Vol. 41 (2), 38-47
- https://doi.org/10.1145/1971162.1971168
Abstract
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.Keywords
This publication has 17 references indexed in Scilit:
- Topology-Awareness and Reoptimization Mechanism for Virtual Network EmbeddingLecture Notes in Computer Science, 2010
- Network virtualization: state of the art and research challengesIEEE Communications Magazine, 2009
- Virtual Network Embedding with Coordinated Node and Link MappingPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2009
- How to lease the internet in your spare timeACM SIGCOMM Computer Communication Review, 2007
- Dynamic Topology Configuration in Service Overlay Networks: A Study of Reconfiguration PoliciesPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2006
- Exact and approximate graph matching using random walksIEEE Transactions on Pattern Analysis and Machine Intelligence, 2005
- Inside PageRankACM Transactions on Internet Technology, 2005
- A unified probabilistic framework for web page scoring systemsIEEE Transactions on Knowledge and Data Engineering, 2004
- Finding the k shortest pathsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Provisioning a virtual private networkPublished by Association for Computing Machinery (ACM) ,2001