Robust Deployment Model for Parallelized Service Function Chains Against Uncertain Traffic Arrival Rates

In network function virtualization, a network service is provided by a service function chain (SFC), which consists of a chain of virtual network functions (VNFs) within a specific order. SFC parallelism allows parallel processing among VNFs to reduce the end-to-end service delay. Existing works handle the service delay without considering traffic uncertainty, which leads to degraded performance on parallel structure balancing and deployment cost saving in the parallelized SFC deployment problem. This paper proposes a robust deployment model for parallelized SFCs against traffic uncertainty that satisfies the requirement of balanced parallel structures and minimizes the deployment cost. We define a traffic uncertainty set that handles both the variation of service traffic arrival rates and the fluctuation of parallel structures. We apply VNF sharing to improve the efficiency of resource allocation. We formulate the proposed model as a mixed integer second-order cone programming (MISOCP) problem. We introduce a heuristic algorithm to handle larger-size problems, where the MISOCP approach is intractable to obtain a solution in a practical time. Numerical results show the advantages of the proposed model in terms of deployment cost over the baseline models.