Virtual Network Embedding with Coordinated Node and Link Mapping

TLDR

Network virtualization is proposed to overcome Internet ossification by allowing multiple heterogeneous virtual networks to share a common substrate, but the NP‑hard VN embedding problem—efficiently mapping virtual nodes and links—has been traditionally tackled with separate heuristic node and link mapping phases. This work introduces VN embedding algorithms that coordinate node and link mapping to improve overall performance. The authors formulate the embedding as a mixed‑integer program with substrate augmentation, relax it to a linear program, and develop deterministic (D‑ViNE) and randomized (R‑ViNE) rounding algorithms. Simulation results demonstrate higher acceptance ratios and revenue, and lower long‑term substrate costs compared to prior approaches.

Abstract

Recently network virtualization has been proposed as a promising way to overcome the current ossification of the Internet by allowing multiple heterogeneous virtual networks (VNs) to coexist on a shared infrastructure. A major challenge in this respect is the VN embedding problem that deals with efficient mapping of virtual nodes and virtual links onto the substrate network resources. Since this problem is known to be NP-hard, previous research focused on designing heuristic-based algorithms which had clear separation between the node mapping and the link mapping phases. This paper proposes VN embedding algorithms with better coordination between the two phases. We formulate the VN embedding problem as a mixed integer program through substrate network augmentation. We then relax the integer constraints to obtain a linear program, and devise two VN embedding algorithms D-ViNE and R-ViNE using deterministic and randomized rounding techniques, respectively. Simulation experiments show that the proposed algorithms increase the acceptance ratio and the revenue while decreasing the cost incurred by the substrate network in the long run.