Efficient VNF Migration and Recovery in Edge
Computing Environments†

†∗‡

†

†

Yu Chen , Sheng Zhang , Yanchao Zhao , Zhuzhong Qian , Yu Liang ,††Jidong Ge , Sanglu Lu†
State Key Lab. for Novel Software Technology, Nanjing University‡Nanjing University of Aeronautics and Astronautics
sheng@nju.edu.cn

Abstract
The combination of network function virtualization (NFV) and software defined networking (SDN) contributes
to making the network more efficient, and it promises to guarantee high flexibility and low cost in network operations. Meanwhile, the continuous development of mobile edge computing (MEC) makes it possible for the edgeof mobile network to run cloud computing tasks. However, edge computing environments are dynamic, and VNF
demands for computing resources usually fluctuate over time. Thus, when the demand of a VNF cannot be satisfied,
we need to migrate the VNF so as to meet its demand and retain the network performance. Our paper focuses on
efficiently migrating VNFs (MV) and recovering connections (RC) after migration, such that the migration andconnection paths can meet the bandwidth requirement for data transmission. We prove that both of MV and RC
are NP-complete. We present efficient algorithms to tackle them. Extensive simulations show that the proposed
algorithms are efficient and effective.

Motivation
Mobile edge computing (MEC) enables the cloud computing capabilities at the edge of the mobilenetwork, which greatly lowers the delay in data transmission. Virtual network functions (VNFs) canbe dynamically deployed, migrated, and removed.
Due to the dynamic nature of edges, the network changes from time to time. For instance, the topology of the network may change, the resource capacity of a specific machine may vary at some point,
and the bandwidth between two machines may increase or decrease due to different traffic situations.
In the daytime, some VNFs may require more computing resources due to heavy traffic situations,and they need to be migrated to the machines with massive resources in central network nodes; in thenight, due to the decreasing demand for computing resources, some VNFs need to be migrated backto edge network nodes with fewer resources, such that the machines with massive resources can bevacated for sudden large tasks. Therefore, we need to efficiently complete the migration of the VNF
chains, as well as the task of VNF connection recovery after migration.
In this paper, we use ‘to-be-migrated VNFs’ to represent the VNFs which we need to migrate. We
consider the problem of migrating multiple VNFs to new physical machines, as the to-be-migrated
VNFs’ demands for computing resources fluctuate due to different traffic situations. As a first step,to initiate a meaningful study, this paper narrows the scope of this problem to a manageable extent:
we assume the network node to which each VNF is migrated is known in advance; thus, we focus on
selecting the migration paths that meet the bandwidth requirements for all to-be-migrated VNFs, suchthat the task of migrating VNFs can be completed within the specified time. After migration, we needto recover the connection between the migrated VNFs which are adjacent along a VNF chain. To
prevent the traffic congestion in the network, we need to find out the connection paths that minimize
bandwidth usage.
Our contributions in the paper are three-fold: (1) We introduce MVRC using graph theory andpresent a formal formulation. We provide the NP-completeness results of both MV and RC; (2) We
propose efficient algorithms for the MVRC problem; (3) Simulations are conducted to confirm theefficiency and effectiveness of the proposed algorithms.

to see α can reflect the traffic condition of the network after migration. Our objective is to minimize
α and prevent the traffic congestion.
NP-completeness result. By reducing the Widest Pair of Paths Problem to RC and reducing theWidest Pair of Disjoint Paths Decoupled Problem to MV, we can both of MV and RC are NPcomplete.

Preliminary Solutions
Heuristics for MV. We need to select n migration paths satisfying bandwidth requirements for all tobe-migrated VNFs in MV. To ensure that as many VNFs as possible can be migrated successfully, wemigrate VNFs in the non-decreasing order of the bandwidth requirements and first select the shortestor the minimum wide-edge migration path, such that each migration path will use fewer links and thebandwidth of each link can be made the most use of on the whole.
Smallest path Heuristic (SH) algorithm. SH starts from the migration path PM,i with the smallest
bandwidth requirement. SH utilizes the Dijkstra’s Algorithm to calculate the shortest path sp between
SM,i and DM,i.
Minimum Wide-edge Heuristic (MWH) algorithm. MWH differs from SH only in that instead ofusing Dijkstra we use a similar algorithm that finds the minmum wide-edge path between two givenvertices.
Heuristics for RC. To minimize the bandwidth occupancy rate and uniformly use all links’ bandwidths, we select the migration paths that have large bandwidth capacity and traverse few links.
Widest Heuristic (WH) algorithm. WH starts from the path with the smallest bandwidth requirement,and checks whether there is any path that satisfies its demand.
Modified Shortest Heuristic (MSH) algorithm. Different from WH, MSH uses the Dijkstra’s algorithm to find a suitable for a given vertices pair.

Formulation
Migrating VNFs (MV). We assume that there are c VNF chains to be migrated, and the jth(j = 1, 2, .., c) VNF chain
Pchas Cj to-be-migrated VNFs. Thus, the total number of to-be-migrated
VNFs is denoted as n = j=1 Cj . Besides, the ith (i = 1, 2, ..., n) to-be-migrated VNF is denoted asfi, and we migrate it from the current node SM,i to the destination node DM,i, which is specified inadvance. In the cloud-based edge network, there are rM,i paths between SM,i and DM,i, and they are
rM,i12k (k = 1, 2, ..., r
RM,i, RM,i, ..., RM,i. We need to select one of them, e.g., RM,iM,i ) as the migrationk ) as the bandwidth of Rk , which equals the minimum bandpath PM,i for fi. We define BW (RM,iM,ik . We allocate B
width of the links along RM,iM,i units of bandwidth for PM,i, and BM,i is no morek ). If multiple migration paths traverse the same link e, the total bandwidth allocatedthan BW (RM,ifor them should not exceed Be.
We start to migrate the n to-be-migrated VNFs at the same time, and all the migration tasks need
to be finished within the specific time T . We assume the amount of the to-be-migrated data of fi isdi. Remember that the bandwidth we allocate for fi along PM,i is BM,i, so the time required for fi’s
migration is di/BM,i. All to-be-migrated VNFs need to be migrated to the destinations within timeT , so we should select an appropriate migration path for each VNF. There is no motivation for each
VNF to finish migration in the time less than T , because it will occupy extra bandwidth that might beutilized by other VNFs. Thus, the bandwidth requirement of PM,i is equal to di/T , i.e., BM,i = di/T .
Recovering Connections (RC). After migration, we need to recover the connection path between
each migrated VNF and its neighbor VNFs along the VNF chain. We assume that there are m connection paths to be recovered in total, and they are each selected between node SC,1 and DC,1, node SC,2and DC,2, ..., node SC,m and DC,m. In the cloud-based edge network, there are rC,i (i = 1, 2, ..., m)rC,i21paths between SC,i and DC,i, and they are RC,i, RC,i, ..., RC,i . Similar to MV, we should select onek (k = 1, 2, ..., r ) as the recovered connection path Pof them, e.g., RC,iC,iC,i between node SC,i andDC,i. The bandwidth requirement of the connection path between node SC,i and DC,i is BC,i. Thus,k ). If multiple
we need to allocate BC,i units of bandwdith for PC,i, and BC,i is no more than BW (RC,irecovered connection paths traverse the same link e, the total bandwidth allocated for them should
not exceed Be.
The total bandwidth allocated for the connection paths traversing the link ei is denoted as tei , and we|E| t
define the bandwidth occupancy rate after recovering VNF connection as α = maxi=1 Bei . It is easyeiFigure1 Simulation results

Preliminary Results
We simulate the network using the Python package NetworkX. In general, the simulation results
demonstrate the efficiency and effectiveness of the proposed algorithms, which are nearly as goodas the optimal solution. For example, in Fig. 1(a)(b), we can see that the performance of SH and
MWH is close to the optimal solution when the number of links is more than twice that of network
nodes, i.e., 128. Besides, when the ratio of LBC to VBR in the network is larger than 8, SH andMWH also perform nearly as well as OPT. From Fig. 1(c)(d), we learn that the running time cost ofSH and MWH is much less than that of OPT. Thus, when there are a number of links in the networkand the ratio of LBC to VBR is not very low, our algorithms for MV can achieve good results.