Exploring online virtual networks mapping with stochastic bandwidth demand in multi-datacenter
Exploring online virtual networks mapping with stochastic bandwidth demand in multi-datacenter
复制标题
DOI：
10.1007/s11107-011-0341-z
复制
发表时间：
2011-11
影响因子：
1.7
通讯作者：
Gang Sun;Hong-Fang Yu;Le Min Li;V. Anand;Yanyang Cai;Hao Di
中科院分区：
文献类型：
--
作者：
Gang Sun;Hong-Fang Yu;Le Min Li;V. Anand;Yanyang Cai;Hao Di
网络虚拟化是一种很有前途的技术，可以提供灵活和高度适应性的共享底层网络，以满足需求的多样性并克服Internet基础设施的僵化。虚拟网络映射问题是构建虚拟网络的关键问题，许多研究工作提出了各种先进的算法来解决虚拟网络映射问题。然而，这些传统的方法对于网络资源需求具有确定性的虚拟网络映射是有效的，它们甚至通过过度配置来处理动态的资源需求。这些方法显然是不可取的，因为网络资源变得越来越稀缺。本文研究了在线随机VN映射（StoVNM）问题，其中VN是一个泊松过程，每个带宽需求服从一个正态分布，即xi~N（μi, σi2）。首先，以最小映射代价和负载平衡为目标，利用混合整数线性规划方法建立StoVNM问题的模型；然后，我们设计了一种基于滑动窗口方法的启发式算法w-StoVNM来有效地解决这个NP-hard StoVNM问题。大量的仿真实验结果证明了该方法的有效性，并且在VN映射成本、阻塞比和长期总净收入方面优于传统的VN映射解决方案。
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 demandxifollows a normal distribution, i.e.,xi~N(μi, σi2). 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.