ViNEYard: Virtual Network Embedding Algorithms With Coordinated Node and Link Mapping

doi:10.1109/TNET.2011.2159308

ViNEYard: Virtual Network Embedding Algorithms With Coordinated Node and Link Mapping

2012-02-01

658

PRE

AI

M

Mosharaf Chowdhury *

M

Muntasir Raihan Rahman

R

Raouf Boutaba

DOI：10.1109/TNET.2011.2159308

Original

Original request for help

Save

Abstract

En 中文

Network virtualization allows multiple heterogeneous virtual networks (VNs) to coexist on a shared infrastructure. Efficient mapping of virtual nodes and virtual links of a VN request onto substrate network resources, also known as the VN embedding problem, is the first step toward enabling such multiplicity. Since this problem is known to be NP-hard, previous research focused on designing heuristic-based algorithms that had clear separation between the node mapping and the link mapping phases. In this paper, we present ViNEYard-a collection of VN embedding algorithms that leverage 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 online VN embedding algorithms D-ViNE and R-ViNE using deterministic and randomized rounding techniques, respectively. We also present a generalized window-based VN embedding algorithm (WiNE) to evaluate the effect of lookahead on VN embedding. Our simulation experiments on a large mix of VN requests 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.

Keywords:

Heuristics

network virtualization

online algorithms

optimization

resource allocation

virtual network embedding

ViNEYard: Virtual Network Embedding Algorithms With Coordinated Node and Link Mapping

Abstract

Journal

Organization