RDAM: A Reinforcement Learning Based Dynamic Attribute Matrix Representation for Virtual Network Embedding

Network virtualization makes it possible to manage multiple virtual networks simultaneously on substrate physical networks. Virtual network embedding (VNE) is the critical step of network virtualization that maps virtual network requests to substrate physical networks. The majority of current virtual network embedding algorithms utilize heuristic algorithm, and manually customize a series of rules and assumptions. Therefore, these experimental results are not particularly convincing. This paper proposes a reinforcement learning based dynamic attribute matrix representation (RDAM) algorithm for virtual network embedding. The RDAM algorithm decomposes the process of node mapping into the following three steps: (1) static representation of substrate physical network. (2) dynamic update of substrate physical network. (3) Reinforcement-Learning-Based algorithm. To our best knowledge, RDAM algorithm is the first algorithm to apply spectral analysis and perturbation theory to virtual network embedding. Meanwhile, the method training virtual network embedding algorithm by reinforcement learning is also non-trivial. Furthermore, we compare RDAM algorithm with three other virtual network embedding algorithms. The results show that RDAM algorithm outperforms the other three algorithms in terms of several evaluation metrics, such as long-term average revenue, long-term revenue consumption ratio, and acceptance ratio.