A novel dynamic programming inspired algorithm for embedding of virtual networks in future networks

Abstract Network virtualization is envisioned to support flexible, cost effective and on-demand deployment of multiple Virtual Networks (VNs) on a shared underlying infrastructure. A key challenge under the virtualization paradigm is how to effectively and efficiently map the divergent VNs onto the shared infrastructure characterized by exhaustible resources. Given that the future services will be characterized by heterogeneity in terms of topology and QoS requirements, existing algorithms can not be flexibly adapted to deal with such requests with differing constraints and mapping objectives. In this regard, this paper proposes a Dynamic Programming Inspired Algorithm (DyPI-Algo), a generic algorithm for mapping virtual networks on a shared infrastructure. Simulation results reveal that the proposed algorithm is able to maximize acceptance ratio and load balancing. Additionally, the algorithm is able to maximise revenue by admitting requests of large size compared to the benchmark algorithms. Moreover, the algorithm is found to be scalable in terms of time complexity when increasing the size of the substrate network and requests. In addition, the paper proposes an Adjacency List based heuristic and a Brute-force algorithm as additional benchmark algorithms. Simulation results show that the proposed algorithms result into up to more than a 10% improvement in terms of acceptance ratio compared to the state of the art algorithms in some scenarios.