Path Splitted and Energy Efficient Virtual Network Function Chains Embedding

Recently network function virtualization has been proposed to execute virtual network functions (VNF) on software middle-boxes hosted on commodity servers (substrate nodes). Normally, a request needs to invoke several VNFs in a particular order. As we know, activating and running a substrate node comes at a certain energy cost, and deploying a service chain requires several open substrate nodes which lead to high energy consumption. Furthermore, the deployment of service chains also needs to consume bandwidth resource on a substrate network. After embedment of some service chains, the substrate network may consist of many links with fragmented remaining resources that are too little to be utilized by any other requests. The nodes resources than cannot be fully utilized and are expended quickly, which causes low resources utilization. Since the resources of the physical network are limited, due to their faster consumption, the acceptance ratio remains very low. In this paper, we aim to investigate the problem of high energy consumption, low resources utilization and low acceptance ratio in embedment concurrently. To tackle this problem, we consider deploying service chains on splitted paths to utilize the fragmented resources and minimize the number of open nodes to save the energy consumption. To minimize the number of open nodes, we first formulate the embedment of a service chain as a mixed integer linear program with binary constraints on nodes and continuous constraints on flows. For the purpose of supporting an operation of max-cut that support splitted paths, we consider constructing a network flow model by setting the cost weight based on the state of the nodes. Then, we devise service chains constrained Min-Cost Flow (SC-MCF) Algorithm to find an optimal splitted path with minimal cost weight. Finally, we conduct extensive experiments based on two real topologies EasyNet and GrNet. The experiments show that our proposed SC-MCF Algorithm decreases the number of open nodes and increases the acceptance ratio while saving the resources in the long run.