Lagrangian Heuristics for Capacitated Shortest Path Tour Problem Based Online Service Chaining

Network functions virtualization (NFV) can flexibly deploy diverse network services by liberating network functions from traditional network appliances and executing them as virtual network functions (VNFs) on generic hardware. A certain network service can be represented by a service chain, which consists of VNFs in required order. The service chaining problem is finding a suitable service path from the origin to the destination such that the VNFs are executed at the intermediate nodes in the required order under the resource constraints, which belongs to the complexity class NP-hard. In our previous work, considering the similarity between the service chaining problem and the shortest path tour problem (SPTP), we formulated the service chaining as the capacitated SPTP (CSPTP) based ILP, where CSPTP is an extended version of the SPTP with the node and link capacity constraints. In this paper, to address both computational complexity and optimality of resource allocation, we propose Lagrangian heuristics to solve the CSPTP-based ILP especially for the online service chaining. Through simulation results, we show that the proposed algorithm almost achieves the optimal resource allocation with much smaller execution time compared with the existing solver, CPLEX.

网络功能虚拟化（NFV）通过将网络功能从传统网络设备中解放出来，并在通用硬件上作为虚拟网络功能（VNF）执行，能够灵活地部署各种网络服务。某个网络服务可以由一个服务链来表示，该服务链由按所需顺序排列的VNF组成。服务链问题是在资源约束条件下，从源节点到目的节点找到一条合适的服务路径，使得VNF按所需顺序在中间节点上执行，这属于NP难的复杂问题类别。在我们之前的工作中，考虑到服务链问题和最短路径环游问题（SPTP）之间的相似性，我们将服务链表述为基于带容量限制的最短路径环游问题（CSPTP）的整数线性规划（ILP），其中CSPTP是带有节点和链路容量约束的SPTP的扩展版本。在本文中，为了解决资源分配的计算复杂性和最优性问题，我们提出拉格朗日启发式算法来求解基于CSPTP的ILP，特别是针对在线服务链问题。通过仿真结果，我们表明，与现有的求解器CPLEX相比，所提出的算法几乎实现了最优的资源分配，且执行时间大幅缩短。