A Markov Reward Model Based Greedy Heuristic for the Virtual Network Embedding Problem

An ever increasing utility and use of virtualization in various emerging scenarios, e.g.: Cloud Computing, Software Defined Networks, Data Streaming Processing, asks the Infrastructure Providers (InPs) to optimize the allocation of the virtual network requests (VNRs) into a substrate network. In this paper we present a two-stage virtual network embedding (VNE) algorithm, which map first virtual nodes to substrate nodes based on a suitable ranking algorithm and then map link along the shortest paths among the nodes. The key ingredient of our approach is a novel node ranking algorithm, MCRR (Markov Chains with Rewards Ranking), based on Markov Reward Processes, which associates a metric which accounts for and well captures the amount of local resources available in a vicinity of a given node. We have extensively evaluated our algorithm through simulation. Our experiments indicate that our algorithm outperforms previous approaches in terms of lower VNE rejection rate, higher revenues and better resources utilization.