Stochastic virtual network embedding via accelerated Benders decomposition

Abstract The interest in network virtualization as a solution to the current ossification of the Internet has been recently revived. Virtual Network Embedding (VNE) is the central problem in network virtualization that determines mapping of Virtual Networks (VN) on the physical substrate network while satisfying VN requirements and the substrate network resource constraints. Much research has been conducted on the VNE problem with the assumption that the VN requirements are known beforehand. Nevertheless, the precise amounts of the requirements are uncertain in practice. The limited research that has considered the uncertainty focused on obtaining conservative solutions that increase embedding cost in terms of substrate network resource consumption. In this paper, we examine the VNE problem with the objective of minimizing embedding cost via obtaining a non-conservative solution in the case of the bandwidth requirements of virtual links are expressed as random variables with known distributions. For the first time, we formulate the problem using the stochastic programming framework and utilize the sample average approximation technique to solve it. To tackle its complexity, we decompose the problem based on Benders method which is accelerated by four proposed techniques. Extensive simulation results show that the proposed approach outperforms the conservative solution by about 40%–45%, and it is up to 7.5 times faster than the branch and bound method.