Virtual network embedding based on restrictive selection and optimization theory
Haotong Cao, Jinbo Chen, Longxiang Yang · 2017
One main challenge in network virtualization is virtual network embedding (VNE). VNE is NP-hard. Previous VNE algorithms in the literature are mostly heuristic, while the remaining algorithms are exact. To make a trade-off between the heuristic and the exact, this paper proposes the algorithm VNE-RSOT, based on restrictive selection and optimization theory, to solve the VNE problem. The restrictive selection contributes to largely cutting down on the number of integer variables, adopted in the following optimization theory approach. The VNE-RSOT aims to minimize the substrate resource cost. A simulation against several state-of-art heuristic algorithms is made. Numerical results reveal that virtual network request (VNR) acceptance ratio of VNE-RSOT is, at least, 10% higher than the best-behaved heuristic. The execution time is also plotted to emphasize the efficiency of VNE-RSOT.