Joint optimization of Service Chain Graph Design and Mapping in NFV-enabled networks

Network Function Virtualization (NFV) is an emerging approach to serve diverse demands of network services by decoupling network functions and dedicated network devices. Traffic needs to traverse through a sequence of software-based Virtual Network Functions (VNFs) in a preset order, which is named as Service Function Chain (SFC). Since network operators usually deploy the same type of VNFs in different locations in NFV-enabled networks. How to steer a SFC request to an appropriate path in substrate networks to meet service demands becomes an important issue, which is typically known as SFC mapping. However, the existing research works on SFC mapping often assume that service chain graphs are given in advance. They do not consider VNF interdependency and traffic volume change, which are both theoretically challenging for NFV Management and Orchestration (MANO) framework. To this end, we study the joint optimization of Service Chain Graph Design and Mapping (SCGDM) in NFV-enabled networks. Our objective is to minimize the maximum link load factor to improve the performance of network system. We first formulate the SCGDM problem as an Integer Linear Programming (ILP) model, and prove that it is an NP-hard problem by reduction from a classical Virtual Network Embedding (VNE) problem. Further, we develop an approximation algorithm using randomized rounding method and analyze the approximation performance. Extensive simulation results show that the proposed algorithm effectively reduce the maximum link load factor.