Exploring online virtual networks mapping with stochastic bandwidth demand in multi-datacenter

• Published in: Photonic network communications 2012-04, Vol.23 (2), p.109-122
• Main Authors: Sun, Gang, Yu, Hongfang, Li, Lemin, Anand, Vishal, Cai, Yanyang, Di, Hao
• Format: Article
• Language: English
• Subjects: Characterization and Evaluation of Materials; Computer Communication Networks; Computer Science; Electrical Engineering
• ISSN: 1387-974X; 1572-8188
• DOI: 10.1007/s11107-011-0341-z

Network virtualization serves as a promising technique for providing a flexible and highly adaptable shared substrate network to satisfy the diversity of demands and overcoming the ossification of Internet infrastructure. As a key issue of constructing a virtual network (VN), various state-of-the-art algorithms have been proposed in many research works for addressing the VN mapping problem. However, these traditional works are efficient for mapping VN which with deterministic amount of network resources required, they even deal with the dynamic resource demand by using over-provisioning. These approaches are obviously not advisable, since the network resources are becoming more and more scarce. In this paper, we investigate the online stochastic VN mapping (StoVNM) problem, in which the VNs are generated as a Poisson process and each bandwidth demand x i follows a normal distribution, i.e., x i ~ N ( μ i , σ i 2 ). Firstly, we formulate the model for StoVNM problem by mixed integer linear programming, which with objective including minimum-mapping-cost and load balance. Then, we devise a sliding window approach-based heuristic algorithm w-StoVNM for tackling this NP-hard StoVNM problem efficiently. The experimental results achieved from extensive simulation experiments demonstrate the effectiveness of the proposed approach and superiority than traditional solutions for VN mapping in terms of VN mapping cost, blocking ratio, and total net revenue in the long term.