Placement of highly available virtual network functions through local rerouting

The recent development of network function virtualization decouples network functions from dedicated hardware so that virtual network functions (VNFs) can be distributed onto groups of commodity servers called network points of presence (N-PoPs). In this way, distributed VNFs interconnected by virtual links are denoted as a service function chain (SFC). SFCs have the potential to significantly reduce the cost of network services while improving the flexibility. However, the availability of SFCs on chained up N-PoPs is always inferior to that of network services running on a single N-PoP because the failure of any N-PoP on an SFC may affect its availability. To improve the availability of SFCs, in this paper we propose a local rerouting strategy to bypass the failed N-PoPs on SFCs using locally rerouted paths (LRPs). Furthermore, we formulate an optimization model to minimize the maximum load on links while deploying SFCs and LRPs to reduce the potential risk of congested links caused by the local rerouting strategy. We then propose a randomized rounding approximation algorithm to solve the optimization problem, preserving the competitive ratio of O(log n) for the model, where n is the number of N-PoPs in the network. We also propose a fast heuristic algorithm to improve the efficiency. Our extensive simulation results show that the proposed algorithms can provide highly available SFCs with more balanced link load.