Paper Info
Title
Virtual network embedding: An optimal decomposition approach
Abstract
In network virtualization, a traditional ISP collapses into two independent tiers, where the infrastructure provider (InP) manages the physical (or substrate) networks and the service provider (SP) operates the service (or virtual) networks. In this work, we investigate the virtual network embedding (VNE) problem, which bridges above two tiers by mapping the virtual network request to the substrate networks. Existing VNE approaches are either optimal Integer Linear Programming formulations that suffer from extensive computational time, or relaxation/heuristics (mostly decompose the VNE problem into link mapping (LM) and node assignment (NA) sub-problems) that are unable to provide an optimal solution or near-optimal solution with guaranteed quality. In this paper, we attempt to fill this gap with a new VNE solution, which relies on an iterative process enabling feedbacks between the NA, and LM sub-problems (obtained based on the Primal-dual analysis of the VNE problem). With our approach, one can reach either an optimal solution or a near optimal solution with a per-instance guarantee on its closeness to the optimal solution.
Year
DOI
Venue
2014
10.1109/ICCCN.2014.6911723
ICCCN
Keywords
Field
DocType
isp,optimal decomposition approach,iterative process,integer programming,linear programming,primal-dual analysis,virtualisation,internet,link mapping,node assignment,virtual network embedding,network virtualization,vne problem,optimal integer linear programming,iterative methods
Computer science,Branch and price,Theoretical computer science,Virtual network embedding,Distributed computing
Conference
Citations 
PageRank 
References 
3
0.40
14
Authors
3
Name
Order
Citations
PageRank
Qian Hu1545.44
Yang Wang210212.48
Xiaojun Cao353074.55