A new algorithm with coordinated node and link mapping for virtual network embedding based on LP relaxation

Xiujiao Gao; Hongfang Yu; Vishal Anand; Gang Sun; Hao Di

doi:10.1117/12.887818

18 February 2011 A new algorithm with coordinated node and link mapping for virtual network embedding based on LP relaxation

Xiujiao Gao, Hongfang Yu, Vishal Anand, Gang Sun, Hao Di

Author Affiliations +

Proceedings Volume 7988, Optical Transmission Systems, Switching, and Subsystems VIII; 79881Y (2011) https://doi.org/10.1117/12.887818
Event: Asia Communications and Photonics Conference and Exhibition, 2010, Shanghai, Shanghai, China

Abstract

Network virtualization can help diversify the Internet by supporting multiple virtual network (VN) architectures on a shared substrate. Making efficient use of the underlying substrate network resources requires effective algorithms for virtual network embedding (VNE) that maps each virtual network (VN) to specific nodes and links in the substrate network. In this paper, we formulate the VNE problem as a mixed integer linear program (MILP), and then propose a progressively greedy VNE algorithm (PG-VNE) which has three main improvements over previous approaches. 1) Adding constraints after we relax the MILP to obtain STRICT_LP model which leads to better coordination between the node and link mapping stages, 2) Using the greedy idea to map virtual nodes and 3) Mapping virtual nodes progressively, i.e., mapping virtual nodes one by one. Simulation results show that PG-VNE algorithm realizes close coordination between node and link mapping stages and performs well in terms of revenue, cost and VN request acceptance ratio when compared with the well known D-ViNE and R-ViNE algorithms.

Citation Download Citation

Xiujiao Gao, Hongfang Yu, Vishal Anand, Gang Sun, and Hao Di "A new algorithm with coordinated node and link mapping for virtual network embedding based on LP relaxation", Proc. SPIE 7988, Optical Transmission Systems, Switching, and Subsystems VIII, 79881Y (18 February 2011); https://doi.org/10.1117/12.887818

ACCESS THE FULL ARTICLE

INSTITUTIONAL
Select your institution to access the SPIE Digital Library.

SELECT YOUR INSTITUTION

PERSONAL
Sign in with your SPIE account to access your personal subscriptions or to use specific features such as save to my library, sign up for alerts, save searches, etc.

PERSONAL SIGN IN

No SPIE Account? Create one

PURCHASE THIS CONTENT

SUBSCRIBE TO DIGITAL LIBRARY

50 downloads per 1-year subscription

Members: $195

Non-members: $335 ADD TO CART

25 downloads per 1 - year subscription

Members: $145

Non-members: $250 ADD TO CART

PURCHASE SINGLE ARTICLE

Includes PDF, HTML & Video, when available