Load-Prediction: Online Provisioning for Waiting-Tolerable Multicast Virtual Network Requests in Data Centers

Abstract

As a key technology to enable multiple heterogeneous virtual networks (VNs) to coexist on top of a shared substrate infrastructure, network virtualization has attracted more and more attentions in recent years. An important issue in network virtualization is how to efficiently map a virtual network (VN) onto a shared substrate network. While many algorithms have been proposed for embedding online VN requests onto the substrate network, however, their performance is poor in terms of their blocking ratio (i.e., the ratio between the number of denied VN requests and the total amount of VN requests) is considerably high. In this paper, we investigate the problem of online multicast virtual network embedding (MVNE) by introducing the strategies of waiting-tolerant and load-prediction into our VN provisioning framework for reducing the blocking ratio. We firstly formulate the MVNE problem as an optimization problem by using mixed integer linear programming (MILP), with objectives of minizing mapping cost and balancing the workload of substrate network. Since this problem is NP-hard, we propose a heuristic algorithm called MVNE-WL (MVN Embedding with the strategies of Waiting-tolerant and Load-prediction) for solving this problem efficiently. The numerical results obtained from extensive simulations demonstrate the effectiveness of the proposed approach and show that MVNE-WL is better than traditional solutions in terms of the MVN mapping blocking ratio, the total net revenue, the unit cost efficiency, the node utilization and the link utilization in the long term.