Provable Approximation Algorithms for Online Traffic-Sensitive SFC Deployment

Network Function Virtualization (NFV) has the potential for cost-efficiency, manage-convenience, and flexibility services but meanwhile poses challenges for the service function chain (SFC) deployment problem, which is NP-hard. It is so complicated that existing work conspicuously neglects the flow changes along the chains and only gives heuristic algorithms without a performance guarantee. In this paper, we fill this gap by formulating a traffic-sensitive online joint SFC placement and flow routing (TO-JPR) model, with the objective of jointly optimize the resource cost and network latency, and proposing a novel two-stage scheme to solve it. We design a dynamic segmental packing (DSP) algorithm for the first stage, which not only maintains the minimal traffic burden for the network but also achieves an approximation ratio of a small constant on the resource cost. Besides, we propose the greedy mapping (GM) algorithm for the second stage, which can guarantee a global approximation ratio of O(d) on the network latency. Here d is the diameter of the network graph and is typically smaller than O(log(M)), where M is the number of servers in the network. Finally, we perform extensive simulations to demonstrate the outstanding performance of our algorithms compared with the optimal solutions and benchmarks.