Speedy and Efficient Service Chaining and Function Placement Based on Lagrangian Heuristics for Capacitated Shortest Path Tour Problem
Speedy and Efficient Service Chaining and Function Placement Based on Lagrangian Heuristics for Capacitated Shortest Path Tour Problem
复制标题
DOI：
10.1007/s10922-022-09715-y
复制
发表时间：
2022-12
影响因子：
3.6
通讯作者：
Takanori Hara;Masahiro Sasabe
中科院分区：
文献类型：
--
作者：
Takanori Hara;Masahiro Sasabe
网络功能虚拟化（Network Functions Virtualization，NFV）通过将虚拟网络功能（Virtual Network Function，VNF）与商用服务器相结合，取代传统网络设备，实现灵活多样的网络服务。某个网络服务可以由一系列VNF组成，即，服务（功能）链。服务链（SC）问题旨在建立从源节点到目的地节点的适当服务路径，其保持以指定顺序执行所需VNF的资源约束和服务链要求。SC属于NP-难的复杂性类。在以前的工作中，受SC问题和最短路径旅游问题（SPTP）之间的相似性的启发，我们展示了基于容量限制的SPTP（CSPTP）的ILP的SC问题，其中CSPTP是一个广义版本的SPTP与节点和链路的容量限制。在本文中，我们提出了拉格朗日算法来解决基于CSPTP的ILP的SC在一个快速和有效的方式。我们进一步提出，所提出的算法也可以解决服务链和功能的放置稍微扩展的网络模型称为增强网络。通过数值计算结果，我们表明，所提出的供应链算法与最优资源分配相比具有竞争力，同时执行速度比基于CSPTP的ILP和现有求解器的组合快得多，即，CPLEX。此外，我们还表明，所提出的服务链和功能布局的算法仍然可以平衡的解决方案的最优性和计算复杂性，由于并行计算架构。
Network functions virtualization (NFV) can realize flexible and diverse network services by replacing the conventional network equipment with the combination of virtual network functions (VNFs) and commodity servers. A certain network service can be composed of a sequence of VNFs, i.e., service (function) chain. The service chaining (SC) problem aims to establish an appropriate service path from the origin node to the destination node, which holds both the resource constraints and service chain requirements of executing the required VNFs in the designated order. SC belongs to the complexity classNP-hard. In the previous work, inspired by the similarity between the SC problem and the shortest path tour problem (SPTP), we showed the capacitated SPTP (CSPTP) based ILP for the SC problem, where CSPTP is a generalized version of the SPTP with both the node and link capacity constraints. In this paper, we propose Lagrangian heuristics to solve the CSPTP-based ILP for the SC in a speedy and efficient manner. We further present that the proposed heuristics can also solve both the service chaining and function placement by slightly extending the network model called an augmented network. Through numerical results, we show that the proposed heuristics for the SC is competitive with the optimal resource allocation while executing much faster than the combination of the CSPTP-based ILP and the existing solver, i.e., CPLEX. Furthermore, we also show that the proposed heuristics for both the service chaining and function placement can still balance the solution optimality and computational complexity, thanks to the parallel computation architectures.