Client-Constrained Virtual Network Embedding under Uncertainty

This paper addresses uncertainty in resource demands and heterogeneous requests with affinity and anti-affinity constraints on virtual nodes and links in traditional Virtual Network Embedding. This is realized using stochastic modeling and methods based on an initial Integer-Linear Programming (ILP) model formulation of the VNE problem. The ILP is extended to build a nonlinear Chance-Constrained Programming (CCP) model to address uncertainty. The derived CCP model is then linearized for exploitation by standard solvers. Numerical experiments and comparisons with state-of-the-art methods illustrate the efficiency of our approaches. The results provide insight to cloud service providers on their resource investment to serve clients with affinity and antiaffinity requirements under uncertainty.