A Fast Near-Optimal Approach for Energy-Aware SFC Deployment

Service function chaining along with network function virtualization enable flexible and rapid provisioning of network services to meet increasing demand for short-lived services with diverse requirements. In this paradigm, the main question to be answered is how to deploy the requested services by means of creating virtual network function (VNF) instances and routing the traffic between them, according to the services specifications. In this paper, we define the energy aware service deployment problem, and present the ILP formulation of it by considering limited traffic processing capacity of VNF instances and management concerns. We apply the Benders decomposition technique to decompose the problem into two smaller problems: master and sub-problem. As it is NP-Hard to find a non-trivial solution to the ILP master problem, we resort to the relaxed LP version of the problem. Then, we design methods based on the feasibility pump and duality theorem to rapidly calculate a near-optimal integer solution. The extensive simulation results show even in a network with 24 switches and 40 servers, our algorithm can deploy 35 requests in less than 3 seconds while the total power consumption is only about 1.3 times of the optimal solution obtained by the exhaustive exact approach. Moreover, it significantly outperforms the prominent SFC deployment algorithms in the fat-tree topology.