Deep Reinforcement Learning with Graph Neural Networks for Capacitated Shortest Path Tour based Service Chaining
Deep Reinforcement Learning with Graph Neural Networks for Capacitated Shortest Path Tour based Service Chaining
复制标题
DOI：
10.23919/cnsm55787.2022.9965166
复制
发表时间：
2022-10
期刊：
影响因子：
--
通讯作者：
Takanori Hara;Masahiro Sasabe
中科院分区：
文献类型：
--
作者：
Takanori Hara;Masahiro Sasabe
网络功能虚拟化（NFV）通过在通用硬件上执行网络功能作为虚拟网络功能（VNF）来实现多样化和灵活的网络服务。某个网络服务被视为一个VNF序列，称为服务链。服务链（SC）问题旨在找到从源节点到目的地节点的适当服务路径，同时在节点和链路上的资源约束下以所需顺序在中间节点处执行VNF。SC问题属于复杂性类NP-hard。在我们以前的工作中，我们建模的SC问题作为一个整数线性规划（ILP）的基础上的容量限制的最短路径旅游问题（CSPTP），其中CSPTP是一个扩展版本的SPTP与节点和链路的容量限制。我们还开发了拉格朗日算法，以实现最优性和计算复杂性之间的平衡。在本文中，我们进一步提出了一个深度强化学习（DRL）框架与图神经网络（GNN），以实现基于CSPTP的SC自适应服务需求和/或网络拓扑的变化。数值结果表明：（1）对于基于CSPTP的供应链，该框架与ILP的最优性几乎相同;（2）即使在服务需求发生变化或网络部分受损的情况下，该框架也能很好地工作，无需再训练.
Network functions virtualization (NFV) realizes diverse and flexible network services by executing network functions on generic hardware as virtual network functions (VNFs). A certain network service is regarded as a sequence of VNFs, called service chain. The service chaining (SC) problem aims at finding an appropriate service path from an origin node to a destination node while executing the VNFs at the intermediate nodes in the required order under resource constraints on nodes and links. The SC problem belongs to the complexity class NP-hard. In our previous work, we modeled the SC problem as an integer linear program (ILP) based on the capacitated shortest path tour problem (CSPTP) where the CSPTP is an extended version of the SPTP with the node and link capacity constraints. We also developed the Lagrangian heuristics to achieve the balance between optimality and computational complexity. In this paper, we further propose a deep reinforcement learning (DRL) framework with the graph neural network (GNN) to realize the CSPTP-based SC adaptive to changes in service demand and/or network topology. Numerical results show that (1) the proposed framework achieves almost the same optimality as the ILP for the CSPTP-based SC and (2) it also works well without retraining even when the service demand changes or the network is partly damaged.