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
Corresponding author: sheng@nju.edu.cn

ABSTRACTThe combination of network function virtualization (NFV)
and software defined networking (SDN) contributes to making the network more eﬃcient, 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 edge of mobile network torun cloud computing tasks. However, edge computing environments are dynamic, and VNF demands for computing resources usually fluctuate over time. Thus, when the demandof 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 eﬃciently migrating VNFs (MV) andrecovering connections (RC) after migration, such that themigration and connection paths can meet the bandwidth requirement for data transmission. We prove that both of MV
and RC are NP-complete. We present eﬃcient algorithms totackle them. Extensive simulations show that the proposed
algorithms are eﬃcient and eﬀective.

1.

INTRODUCTION

Mobile edge computing (MEC) [2] enables the cloud computing capabilities at the edge of the mobile network, which
greatly lowers the delay in data transmission. Virtual network functions (VNFs) can be dynamically deployed [3], migrated [4], 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 diﬀerent traffic situations. In the daytime, some VNFs may require morecomputing resources due to heavy traﬃc situations, and theyneed to be migrated to the machines with massive resourcesin central network nodes; in the night, due to the decreasing demand for computing resources, some VNFs need to be
migrated back to edge network nodes with fewer resources,
such that the machines with massive resources can be va-Permission to make digital or hard copies of all or part of this work for personal orclassroom use is granted without fee provided that copies are not made or distributedfor profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others thanACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission
and/or a fee. Request permissions from permissions@acm.org.
ICPP’19, Aug 5–8, 2019, Kyoto, Japan.
Copyright 2019 ACM 978-1-4503-2193-8/13/07 ...$15.00.

cated for sudden large tasks. Therefore, we need to eﬃciently complete the migration of the VNF chains, as wellas 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 diﬀerent traﬃc situations. As a firststep, to initiate a meaningful study, this paper narrows thescope 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, such that 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 traﬃc congestion in the network, we need to find out the connection
paths that minimize bandwidth usage.
Related work. Zhang et al. [4] discussed the benefits
and challenges of VM migration and lists many open issues.
Eramo et al. [1] focuses on saving the energy consumptionof migration. Diﬀerent from previous works, in this paper,
VNF migration and connection recovery are jointly considered, and we propose eﬀective algorithms to tackle them.

2. PROBLEM FORMULATION
Migrating VNFs (MV). We assume that there are cVNF chains to be migrated, and the jth (j = 1, 2, .., c) VNF
chain has Cj to-be-migrated VNFs. Thus, the!total number
cof to-be-migrated VNFs is denoted as n =j=1 Cj . Besides, the ith (i = 1, 2, ..., n) to-be-migrated VNF is denoted
as fi , and we migrate it from the current node SM,i to thedestination node DM,i , which is specified in advance. In
the cloud-based edge network, there are rM,i paths between
rM,i12SM,i and DM,i , and they are RM,i, RM,i, ..., RM,i. We needkto select one of them, e.g., RM,i(k = 1, 2, ..., rM,i ) as thekmigration path PM,i for fi . We define BW (RM,i) as thek
bandwidth of RM,i , which equals the minimum bandwidth
kof the links along RM,i. We allocate BM,i units of bandk
width for PM,i , and BM,i is no more than BW (RM,i). If
multiple migration paths traverse the same link e, the total
bandwidth allocated for them should not exceed Be .
We start to migrate the n to-be-migrated VNFs at thesame time, and all the migration tasks need to be finishedwithin the specific time T . We assume the amount of the tobe-migrated data of fi is di . Remember that the bandwidthwe allocate for fi along PM,i is BM,i , so the time required forfi ’s migration is di /BM,i . All to-be-migrated VNFs need tobe migrated to the destinations within time T , so we should
select an appropriate migration path for each VNF. Thereis no motivation for each VNF to finish migration in thetime less than T , because it will occupy extra bandwidththat might be utilized 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, weneed 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 andDC,1 , node SC,2 and DC,2 , ..., node SC,m and DC,m . In
the cloud-based edge network, there are rC,i (i = 1, 2, ..., m)
rC,i12
paths between SC,i and DC,i , and they are RC,i, RC,i, ..., RC,i.
kSimilar to MV, we should select one of them, e.g., RC,i(k = 1, 2, ..., rC,i ) as the recovered connection path PC,i between node SC,i and DC,i . The bandwidth requirement of
the connection path between node SC,i and DC,i is BC,i .
Thus, we need to allocate BC,i units of bandwdith for PC,i ,kand BC,i is no more than BW (RC,i). If multiple recovered
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 define thebandwidth occupancy rate after recovering VNF connection|E| t
as α = maxi=1 Beei . It is easy to see α can reflect the traﬃci
condition of the network after migration. Our objective isto minimize α and prevent the traﬃc congestion.
NP-completeness result. By reducing the Widest Pairof Paths Problem to RC and reducing the Widest Pair ofDisjoint Paths Decoupled Problem to MV, we can both ofMV and RC are NP-complete.

3.

SOLUTION

Heuristics for MV. We need to select n migration paths
satisfying bandwidth requirements for all to-be-migrated VNFs
in MV. To ensure that as many VNFs as possible can be migrated successfully, we migrate VNFs in the non-decreasingorder of the bandwidth requirements and first select theshortest or the minimum wide-edge migration path, suchthat each migration path will use fewer links and the bandwidth of each link can be made the most use of on the whole.
Smallest path Heuristic (SH) algorithm. SH starts fromthe 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
diﬀers from SH only in that instead of using Dijkstra we use
a similar algorithm that finds the minmum wide-edge path
between two given vertices.
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 thepath with the smallest bandwidth requirement, and checks
whether there is any path that satisfies its demand.
Modified Shortest Heuristic (MSH) algorithm. Diﬀerent
from WH, MSH uses the Dijkstra’s algorithm to find a suitable for a given vertices pair.

Figure 1: Simulation results

4. EVALUATION
We simulate the network using the Python package NetworkX. In general, the simulation results demonstrate the efficiency and eﬀectiveness of the proposed algorithms, which
are nearly as good as the optimal solution. For example, inFig. 1(a)(b), we can see that the performance of SH and
MWH is close to the optimal solution when the number oflinks 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 and MWH 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 network and the ratio ofLBC to VBR is not very low, our algorithms for MV canachieve good results.

Acknowledgements
This work was supported in part by NSFC (61872175), NSF
of Jiangsu Province (BK20181252), and Collaborative Innovation Center of Novel Software Technology and Industrialization. Sheng Zhang is the corresponding author.

5. REFERENCES[1] V. Eramo, M. Ammar, and F. G. Lavacca. Migration energy
aware reconfigurations of virtual network function instancesin nfv architectures. IEEE Access, 5:4927–4938, 2017.
[2] M. Satyanarayanan, P. Bahl, R. Caceres, and N. Davies. The
case for vm-based cloudlets in mobile computing. IEEE
Pervasive Computing, 8(4):14–23, Oct 2009.
[3] S. Wang, M. Zafer, and K. K. Leung. Online placement ofmulti-component applications in edge computingenvironments. IEEE Access, 5:2514–2533, 2017.
[4] F. Zhang, G. Liu, X. Fu, and R. Yahyapour. A survey on
virtual machine migration: Challenges, techniques and open
issues. IEEE Communications Surveys Tutorials, pages 1–1,
2018.