Virtual Network Embedding with Changeable Action Space: An Approach Based on Graph Neural Network and Reinforcement Learning

Network virtualization technology is envisioned as the new paradigm for modern Internet by virtue of its flexible management and allocation of physical resources, as well as fast provisioning of customized network services. Virtual network embedding (VNE), one of the main issues faced by network virtualization, has attracted interests of numerous researches due to its importance and proven NP-hardness. However, existing works addressing this issue have limitations such as inadequate generality, heavily relying on hand-craft features, inefficient to the changeable action space of the VNE problem, etc. Towards this end, we propose a VNE scheme in this paper with a new environment interpretation mechanism and a duel network based decision making architecture, which has the automatically feature extraction ability for both physical and virtual networks, and the capability of adapting to the VNE environment with changeable action space. Comparison results with existing works demonstrate the superiority of our proposal, which can bring higher acceptance ratio and larger average revenue on both synthetic and real physical networks.