A Multi-Stage Approach for Virtual Network Function Migration and Service Function Chain Reconfiguration in NFV-enabled Networks

Network Function Virtualization (NFV), as a promising paradigm, speeds up the service deployment by separating network functions from proprietary devices and deploying them on common servers in the form of software. Any service in NFV-enabled networks is achieved as a Service Function Chain (SFC) which consists of a series of ordered Virtual Network Functions (VNFs). However, migration of VNFs for more flexible services within the dynamic NFV-enabled network is a key challenge to be addressed. Current VNF migration studies mainly focus on single VNF migration decisions without considering the sharing and concurrent migration of VNF Instance (VNFI). In this paper, we assume that each deployed VNFI is used by multiple SFCs and deal with the optimal location allocation for the contemporaneous migration of VNFIs based on the actual network situation. We first formalize the VNFI migration and SFC reconfiguration problem as a mathematical model, which aims to minimize the end-to-end delay for all affected SFCs and to guarantee network load balancing after the migration simultaneously. Then, we prove the NP-hardness of this problem and propose a multi-stage heuristic algorithm based on optimal order (MSH-OR) to solve it. Extensive evaluation shows that the proposed approach can reduce the average delay by about 16% - 25% for different scale networks while ensuring network load balancing compared with the previous algorithms.