Virtual Network Embedding via Hierarchical Reinforcement Learning1
Yulei Wu, Jingguo Ge, Tong Li · 2022
Virtual network embedding (VNE) is a major challenge for network virtualization, which is one of the most promising technologies for future networks. Essentially, the effectiveness and efficiency of network embedding are determined by the performance of embedding algorithms. In an VNE task, the algorithm is designed to detect the substrate network state automatically and make embedding decisions according to the network state. Due to the unpredictability and the huge search space of virtual network requests (VNR), the VNE problem is known to be NP-hard, and traditional methods fail to provide automatic embedding solutions in an acceptable time. To achieve better performance, reinforcement-learning methods have been applied to the VNE problem. However, existing RL-based methods focus on the current VNR and treat all VNRs equally, which neglect the long-term impact and waste many resources in the process of embedding infeasible VNRs (i.e. VNRs that cannot be embedded completely). To address these problems, a proactive virtual network-embedding algorithm can benefit from hierarchical reinforcement learning (HRL), which is proposed in this chapter. Regarding the algorithm, a two-level agent is responsible for executing the VNE task, considering both the long-term impact and short-term impact. At the high level, the agent selects a feasible VNR from a window-based batch, which aims to maximize the long-term revenue. At the low level, the agent manages to embed the selected VNR with the minimum cost. Extensive simulation results show that the algorithm achieves the best performance compared with the existing state-of-the-art solutions.