Shortest Path Tour Problem Based Integer Linear Programming for Service Chaining in NFV Networks
Shortest Path Tour Problem Based Integer Linear Programming for Service Chaining in NFV Networks
复制标题
DOI：
10.1109/netsoft48620.2020.9165364
复制
发表时间：
2020-06
期刊：
影响因子：
--
通讯作者：
Masahiro Sasabe;Takanori Hara
中科院分区：
文献类型：
--
作者：
Masahiro Sasabe;Takanori Hara
网络功能虚拟化（Network Functions Virtualization，NFV）是一种通过将网络功能与专有硬件解耦并将其作为虚拟网络功能（Virtual Network Function，VNF）在通用硬件上运行来实现灵活敏捷的网络服务的新范例。在NFV网络中，某个网络服务可以被建模为一系列VNF，称为服务链。给定连接请求（源节点、目的地节点和服务链要求，这是一系列功能），服务链问题旨在找到适当的服务路径，该服务路径从源开始并以目的地结束，同时以所需的顺序在中间节点处执行VNF。一些现有的工作注意到，服务链问题类似于最短路径旅游问题（SPTP）。据我们所知，这是第一个工作，确切地制定了服务链问题作为一个基于SPTP的整数线性规划（ILP）。通过数值计算，我们表明基于SPTP的ILP可以支持比现有ILP大1.30-1.77倍的规模系统。
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 certain network service can be modeled as a sequence of VNFs, called a service chain. Given a connection request (origin node, destination node, and service chain requirement, which is a sequence of functions), the service chaining problem aims to find an appropriate service path, which starts from the origin and ends with the destination while executing the VNFs at the intermediate nodes in the required order. Some existing work noticed that the service chaining problem was similar to the shortest path tour problem (SPTP). To the best of our knowledge, this is the first work that exactly formulates the service chaining problem as an SPTP-based integer linear program (ILP). Through numerical results, we show the SPTP-based ILP can support 1.30-1.77 times larger scale systems than the existing ILP.