A Latency-Aware Reward Model Based Greedy Heuristic for the Virtual Network Embedding Problem

The increasing use of virtualization (e.g., in Cloud Computing, Software Defined Networks), demands to Infrastructure Providers (InPs) to optimize the placement of the virtual network requests (VNRs) into a substrate network. In addition to that, they need to cope with QoS, in particular for the rising number of time critical applications (e.g., healthcare, VoIP). Granting resource optimization along with QoS compliance, are two competing goals. In this work, we propose a two-stage virtual network embedding (VNE) algorithm, which maps first virtual nodes to substrate nodes based on a suitable latency-aware ranking algorithm and then maps links along the shortest paths, in terms of latencies. The central component of our approach is a new node ranking algorithm, MCRR-LA, based on Markov Reward Processes, which associates a metric that accounts for and well captures the amount of local resources combined with latency values available in the vicinity of a certain node. The metric is complemented with a Breadth-First search. We widely evaluated our algorithm through simulation. Our experiments point out that our algorithm is able to reduce the average path delay while granting good resource performances in terms of lower VNR blocking rate and higher revenues. We compared our algorithm with a previous two-stage approach obtaining good results useful to underline the strengths of the novel approach.