Partial Rerouting for High-Availability and Low-Cost Service Function Chain

The development of Virtual Network Functions (VNFs) migrates network functions from dedicated hardware to groups of commodity servers called network points of presence (N-PoPs). Thus, network services are redefined as interconnected VNFs called Service Function Chains (SFCs). SFC has the potential to reduce costs of network services and improve scalability. However, the availability of SFC brings new challenges since a failure of any N-PoP along the SFC affects its availability. Deploying backup SFCs is a practical method to improve the availability of SFCs, but inappropriate deployments of backups may trigger the unnecessary capacity expansion of N-PoPs and thus waste VNF resources. In this paper, we solve this problem by proposing an optimization model called partial service function chain mapping. The model adopts partial SFC rerouting strategy for smaller rerouting delay and minimizes the maximum load on N- PoPs to reduce unnecessary capacity expansion of N- PoPs. We then propose a randomized rounding algorithm to solve the optimization problem, preserving the competitive ratio of O(log n), where n is the number of NPoPs in the network. Our extensive simulation results show that the proposed algorithm can significantly improve the availability of SFCs and limit the capacity expansion of N-PoPs.