A Novel and One-Stage Embedding Algorithm for Mapping Virtual Networks
Haotong Cao, Jinbo Chen, Yongan Guo, Hongbo Zhu, Longxiang Yang · 2018
Virtual network embedding (VNE) refers to the resource allocation problem in network virtualization (NV). In the literature, researchers have proposed multiple VNE algorithms. These algorithms aim at embedding more and more requested virtual networks (VNs) onto the underlying networks and maximizing embedding revenues. Prior VNE algorithms mostly belong to the two-stage (separated node and link embedding) mapping algorithm category. Some other VNE algorithms embed each VN in one stage by using mixed integer linear programming (MILP) approach. There is a lack of one-stage heuristic algorithm, enabling to embed nodes and links in one mapping stage. In addition, each requested VN needs to be mapped in polynomial time so as to be promoted to future dynamic VN service application and real-time VNs embedding. Therefore, we propose a real-time and one-stage heuristic mapping algorithm (VNE-RTOS). Numerical simulations are conducted to validate that our VNE-RTOS earns more embedding revenues by approximately 3.4% over typical two-stage heuristic embedding algorithms (e.g. GRD-VNE) while achieving the same substrate resource utilization.