A Batch Approach for Survivable Virtual Network Embedding based on Monte-Carlo Tree Search

International audience© 2015 IEEE. In this paper, we address the survivable batch-embedding virtual network problem within Cloud's backbone. In fact, the batch mapping of virtual networks will enhance the cumulative Cloud provider's revenue thanks to the global view of the incoming requests during a predefined time slot. Hence, the differentiation between requests can be performed and the arrival order of requests is ignored. The embedding of one virtual network is NP-hard. Adding the batch processing of the requests will further increase the complexity of the problem. In order to skirt the exponential complexity, we formulate the problem as building and researching problems within a decision tree. To resolve it, we propose a novel reliable batch-embedding virtual network strategy denoted by BR-VNE. It is based on Monte-Carlo Tree Search optimization method in which the upper confidence bounds can be reached in polynomial time. Based on extensive simulations, the results obtained show that BR-VNE outperforms the related work in terms of i) acceptance rate of virtual network requests, ii) Cloud provider's revenue and iii) rate of requests impacted by physical failures within the Cloud's backbone