Sum of squares: a new metric for NFV service chain placement in edge computing environments and efficient heuristic algo
- PDF / 2,324,931 Bytes
- 14 Pages / 595.276 x 790.866 pts Page_size
- 62 Downloads / 184 Views
REGULAR PAPER
Sum of squares: a new metric for NFV service chain placement in edge computing environments and efficient heuristic algorithms Zhiqi Chen1 · Sheng Zhang1 · Zhuzhong Qian1 · Can Wang1 · Mingjun Xiao2 · Jie Wu3 · Sanglu Lu1 Received: 15 February 2019 / Accepted: 11 June 2020 © China Computer Federation (CCF) 2020
Abstract Both network function virtualization (NFV) and edge computing (EC), especially the latter, are attracting more and more attention in recent years. A growing number of network service providers are migrating their services from the cloud to the edge for better QoS services, while the recent researches on NFV also concentrate on deploying NFV services in edge computing networks. However, NFV deployment in edge networks is a troublesome challenge and is fairly alien from conventional NFV deployment problems in data centres. Edge network differs from the data center network in the following two aspects: firstly, edge nodes are constrained in computing capacity, and secondly, the network connections between edge nodes are unstable and dynamic, which may show large variance over time. This means edge computing should be designed for highefficient use of physical edge nodes’ resources. To address the challenges above, we investigate a new NFV Service Chain Placement problem in edge computing environments (NSCP-EC) in this paper. We first prove that the NSCP-EC problem is NP-complete. Then we propose a new metric which can better measure the capacity utilization rate of physical resources, and analyze its advantages with details. Based on the new metric, we propose two heuristic but efficient algorithms called MINI and MINI-tree. To confirm the performance of the two algorithms, we conduct simulations. The result demonstrates that MINI gains an advantage over genetic algorithm (GA) and MINI-tree orevails over MINI in tree topology conditions in the aspects of physical resource utilization, acceptance rate and running time. Both theoretical analysis and simulation results confirm the feasibility of the algorithms. Keywords NFV placement · Edge computing · SDN · Heuristic agorithm · Tree topology
1 Introduction Recently, network function virtualization (NFV) and edge computing (EC) appear on the stage and play an increasingly important role in the field of computer networking. However, how to combine two of them becomes a crucial issue for us
today. Inspired by this, we mainly focus on the NFV placement problem in the edge environment, under the constraints of computing resources and bandwidth. On one hand, NFV has becomed a new paradigm for orchestrating the core networks. The potential of NFV (Chiosi et al. 2012; Han et al. 2015) has drawn increasing
* Sheng Zhang [email protected]
Sanglu Lu [email protected]
Zhiqi Chen [email protected]
1
Zhuzhong Qian [email protected]
State Key Lab. for Novel Software Technology, Nanjing University, Nanjing, P.R. China
2
School of Computer Science and Technology/Suzhou Institute for Advanced Study, University of Science and Technolog
Data Loading...
