Virtual Network Embedding Through Topology-Aware Node Ranking
Virtual Network Embedding Through Topology-Aware Node Ranking
复制标题
DOI：
10.1145/1971162.1971168
复制
发表时间：
2011-04-01
影响因子：
2.8
通讯作者：
Wang, Jie
中科院分区：
文献类型：
--
作者：
Cheng, Xiang;Su, Sen;Wang, Jie
虚拟化和共享网络资源已经成为一种日益增长的趋势，它重塑了计算和网络架构。在云计算平台和大规模可切片网络测试平台上，在共享基板上嵌入多个虚拟网络是一个具有挑战性的问题。本文应用马尔可夫随机漫步（RW）模型，根据网络节点的资源和拓扑属性对节点进行排序。这种新颖的拓扑感知节点排序方法反映了节点的相对重要性。利用节点排序设计了两种VN嵌入算法。第一种算法根据虚拟节点的等级将虚拟节点映射到底层节点，然后通过寻找路径不可分割的最短路径，求解路径可分割的多商品流问题，在映射节点之间嵌入虚拟链路。第二种算法是基于宽度优先搜索的回溯式VN嵌入算法，该算法利用节点排名嵌入同一阶段的虚拟节点和链接。大量的仿真实验表明，拓扑感知节点秩是一种更好的资源度量，与现有嵌入算法相比，本文提出的基于rw的算法提高了长期平均收益和接受率。
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.