Capacitated Shortest Path Tour Problem Based Integer Linear Programming for Service Chaining and Function Placement in NFV Networks

Masahiro Sasabe Takanori Hara

In IEEE Transactions on Network and Service Management, 2021

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 paper, 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.

Downloads

Text Reference

Masahiro Sasabe, Takanori Hara, Capacitated Shortest Path Tour Problem Based Integer Linear Programming for Service Chaining and Function Placement in NFV Networks, IEEE Transactions on Network and Service Management, 18(1), pp.104-117, March 2021.

BibTex Reference

@article{sasabe21CapacitatedShortestPath,
    author = "Sasabe, Masahiro and Hara, Takanori",
    title = "Capacitated {{Shortest Path Tour Problem Based Integer Linear Programming}} for {{Service Chaining}} and {{Function Placement}} in {{NFV Networks}}",
    year = "2021",
    month = "March",
    journal = "IEEE Transactions on Network and Service Management",
    volume = "18",
    number = "1",
    pages = "104--117",
    doi = "10.1109/TNSM.2020.3044329"
}