Probabilistic Virtual Network Embedding under Demand Uncertainty

Abstract

This thesis investigates the problem of mapping virtual networks onto physical resources where bandwidth demand is uncertain, since, in real world, traffic demands fluctuate significantly over time. Hence, we consider the problem of mapping virtual links to physical paths subject to a constraint on each virtual link congestion probability under the assumption that bandwidth demands of virtual links are uncertain. The problem is formulated as a non-convex optimization problem. Consequently, an approximate formulation is proposed and this results in a second-order cone program that can be solved efficiently for large networks. Also, an existing virtual node embedding algorithm augmented by the proposed link embedding solution is used in simulations and experiments to show the utility and efficiency of our models in various network scenarios. Our results show that both exact and approximate models satisfy the link congestion constraint, and that the approximate model is very close to the exact model.