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.
Takanori Hara, Masahiro Sasabe, Lagrangian Heuristics for Capacitated Shortest Path Tour Problem Based Online Service Chaining, Proc. of IEEE/IFIP Network Operations and Management Symposium (NOMS), pp.1-9, April 2022.
@inproceedings{hara22LagrangianHeuristicsCapacitated,
author = "Hara, Takanori and Sasabe, Masahiro",
title = "Lagrangian {{Heuristics}} for {{Capacitated Shortest Path Tour Problem Based Online Service Chaining}}",
booktitle = "Proc. of {{IEEE}}/{{IFIP Network Operations}} and {{Management Symposium}} ({{NOMS}})",
year = "2022",
month = "April",
pages = "1--9",
doi = "10.1109/NOMS54207.2022.9789758"
}