Service Deployment for Parallelized Function Chains Considering Traffic-Dependent Delay

In network function virtualization, virtual network functions (VNFs) are usually chained in specific orders to generate service function chains (SFCs). Recently, SFC parallelism has been presented to enable VNFs to run in parallel to reduce the end-to-end service delay. Existing works handle the issue of unbalanced parallel branches by assuming predefined linear delay models, which have limitations in efficient resource allocation and deployment cost savings. This paper proposes a deployment model for parallelized SFC that handles the imbalance issue with considering that the delay of each VNF depends on both arriving traffic and allocated computing resources, to improve the flexibility of computing resource allocation. We consider a nonlinear relationship between delay, allocated computing resources, and arriving traffic. We apply VNF sharing to improve the efficiency of resource allocation. We formulate the proposed model as a mixed integer second-order cone programming problem (MISOCP) to minimize the total deployment cost, with satisfying the end-to-end delay requirement. We also introduce a heuristic algorithm to solve the original problem, because the MISOCP approach is intractable to handle larger-size problems in practical time. Numerical results show that the proposed model achieves lower deployment cost than the baseline models.