Capacitated Shortest Path Tour Problem-Based Integer Linear Programming for Service Chaining and Function Placement in NFV Networks
Capacitated Shortest Path Tour Problem-Based Integer Linear Programming for Service Chaining and Function Placement in NFV Networks
复制标题
DOI：
10.1109/tnsm.2020.3044329
复制
发表时间：
2021-03
影响因子：
5.3
通讯作者：
Masahiro Sasabe;Takanori Hara
中科院分区：
文献类型：
--
作者：
Masahiro Sasabe;Takanori Hara
网络功能虚拟化（Network Functions Virtualization，NFV）是一种通过将网络功能与专有硬件解耦并将其作为虚拟网络功能（Virtual Network Function，VNF）在通用硬件上运行来实现灵活敏捷的网络服务的新范例。在NFV网络中，网络服务可以被建模为VNF序列，称为服务链。给定连接请求（例如，源、目的地和所需功能的序列），我们必须解决服务链接和功能放置问题以找到优化目标的适当服务路径（例如，总路径延迟的最小化），同时满足服务链要求。针对服务链问题与最短路径问题（SPTP）之间的相似性，提出了一种新的网络模型--增广网络，建立了基于能力约束SPTP的整数线性规划（ILP）模型来求解服务链和功能布局问题。通过现有求解器的数值结果表明，所提出的服务链ILP可以支持1.22-1.90倍的大规模系统的现有ILP。此外，我们还表明，建议的ILP的服务链和功能放置可以缩短总延迟15.8%，相比，只有服务链。为了进一步的可扩展性，我们提出了一个基于最短路径的启发式算法来解决ILP，并显示服务链和功能布局的启发式可以计算出最优的解决方案，具有高精度在强多项式时间。
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.