An Opportunistic Resource Sharing and Topology-Aware mapping framework for virtual networks

Network virtualization provides a promising way to overcome Internet ossification. A major challenge is virtual network mapping, i.e., how to embed multiple virtual network requests with resource constraints into a substrate network, such that physical resources are utilized in an efficient and effective manner. Since this problem is known to be NP-complete, a variety of heuristic algorithms have been proposed. In this paper, we re-examine this problem and propose a virtual network mapping framework, ORS TA, which is based on Opportunistic Resource Sharing and Topology-Aware node ranking. Opportunistic resource sharing is taken into consideration at the entire network level for the first time and we develop an online approximation algorithm, FFA, for solving the corresponding time slot assignment problem. To measure the topology importance of a substrate node, a node ranking method, MCRank, based on Markov chain is presented. We also devise a simple and practical method to estimate the residual resource of a substrate node/link. Extensive simulation experiments demonstrate that the proposed framework enables the substrate network to achieve efficient physical resource utilization and to accept many more virtual network requests over time.