Virtual Network Embedding Through Topology-Aware Node Ranking

By: 
Xiang Cheng, Sen Su, Zhongbao Zhang, Hanchi Wang, Fangchun Yang, Yan Luo, and Jie Wang
Appears in: 
CCR April 2011

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.

Public Review By: 
S. Agarwal

In the April 2008 issue of ACM CCR, authors Yu, Yi, Rexford and Chiang showed how virtual network (VN) topologies can be embedded onto physical topologies. The applications for such technology are numerous, including supporting research experiments with diverse topological requirements on a single physical substrate. That paper introduced the techniques of path splitting and path migration to increase the number of VN requests that can be satisfied by a substrate that may be simultaneously in use by other requests.
The VN embedding problem is NP hard and we have to rely on heuristics to practically solve the problem. This paper by Cheng et al. introduces two new heuristics that increase the acceptance ratio of incoming VN requests and the overall revenue of the physical substrate. The novelty is in applying the successful PageRank algorithm from web search to this domain. In NodeRank, each physical node is ranked based on its resources (CPU and bandwidth of outgoing links), as well as the ranks of nodes that can be reached from it. In a similar fashion, virtual nodes are ranked as well. Virtual nodes and virtual links are then mapped onto the physical topology using these ranks. The heuristics are evaluated in simulations, and the paper has promised to release the VNE simulator to the research community.
The reviewers agree that this topological form of ranking nodes is different. Unsurprisingly, the gains in revenue and acceptance ratio come at a penalty in runtime, which may not be a concern depending on the duration of incoming jobs. While the graphs do not have confidence intervals plotted, and the simulation settings are slightly different from the April 2008 paper, the authors assure us that neither have significance. Interestingly, two reviewers suggested applying such techniques to handle allocations for cloud computing, and exploring whether that specialization may introduce twists to the problem or open new avenues for solutions to explore.