Paper Info
Title
Capacitated Shortest Path Tour Problem-Based Integer Linear Programming for Service Chaining and Function Placement in NFV Networks
Abstract
Network functions virtualization (NFV) is a new paradigm to achieve flexible and agile network services by decoupling network functions from proprietary hardware and running them on generic hardware as virtual network functions (VNFs). In the NFV network, a network service can be modeled as a sequence of VNFs, called a service chain. Given a connection request (e.g., origin, destination, and a sequence of required functions), we have to solve both the service chaining and function placement problems to find an appropriate service path that optimizes the objective (e.g., minimization of the total path delay) while satisfying the service chain requirements. In this article, focusing on the similarity between the service chaining problem and the shortest path tour problem (SPTP) and developing the novel network model called augmented network, we formulate capacitated SPTP-based integer linear programs (ILPs) for the service chaining and function placement. Through numerical results obtained by the existing solver, we show the proposed ILP for the service chaining can support 1.22-1.90 times as large-scale systems as the existing ILP. Furthermore, we also demonstrate that the proposed ILP for both the service chaining and function placement can shorten the total delay by 15.8% compared with that only for the service chaining. For further scalability, we propose a shortest-path-based heuristic algorithm to solve the ILPs and show the heuristic for service chaining and function placement can calculate the optimal solution with high accuracy in strongly polynomial time.
Year
DOI
Venue
2021
10.1109/TNSM.2020.3044329
IEEE Transactions on Network and Service Management
Keywords
DocType
Volume
Network functions virtualization (NFV),service chaining,function placement,integer linear programming (ILP),augmented network,capacitated shortest path tour problem (CSPTP)
Journal
18
Issue
ISSN
Citations 
1
1932-4537
2
PageRank 
References 
Authors
0.37
0
2
Name
Order
Citations
PageRank
Masahiro Sasabe17016.52
takanori hara293.60