Presto: Towards efficient online virtual network embedding in virtualized cloud data centers

As an efficient solution to diversify the future Internet for resource sharing in data centers, the network virtualization enables seamless integration of network experiments, services and architectures with different features by allowing multiple heterogeneous virtual networks (VNs) to simultaneously coexist on a shared substrate infrastructure. Embedding multiple virtual networks onto a shared substrate by allocating substrate resources to virtual nodes and virtual links of VN requests under a collection of constrains is known to be an NP-hard problem even for the offline VN embedding. To deal with this issue, this paper formulates the VN embedding problem as a new multiple objective linear programming optimization program, and solves it in a preemptive strategy by decomposing the problem into node mapping and link mapping phases. Furthermore, based on an Artificial Intelligence resource abstraction model, named Blocking Island (BI), we propose an efficient online heuristic VN embedding algorithm called Presto. Presto operates with quite low computation complexity and greatly reduces the search space, which far outperforms other candidates. The goal of Presto is to maximize the economic revenue of infrastructure providers while minimizing the embedding cost. The extensive simulation results further prove the feasibility and good performance of Presto in revenue, VN request acceptance ratio, computation efficiency and resource utilization.