Robust Virtual Network Function Deployment against Uncertain Traffic Arrival Rates

Network function virtualization enables service providers to flexibly provision services with virtual network functions. Traffic uncertainty typically exists in a network, which can degrade the performance of a virtual network function. This paper proposes a robust virtual network function deployment model against the traffic uncertainty to minimize the total deployment cost with satisfying the service delay constraint. A virtual network function instance is allowed to be shared by different services to reduce the initial and proportional costs. We describe the traffic uncertainty from different aspects with considering the characteristics in the context of network function virtualization. We formulate the robust deployment problem as a mixed integer second-order cone programming problem. A heuristic algorithm is introduced to solve the problem polynomially by decomposing the original problem to several convex problems. The numerical results reveal that the proposed model saves the deployment cost in average 27% compared to a baseline that uses the deterministic traffic arrival rate, in our examined scenarios.