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.
Network virtualization is a promising solution that can prevent network ossification by allowing multiple heterogeneous
virtual networks to cohabit on a shared substrate network. Thus using virtualization multiple customizable networks can
be run on the same underlying substrate network resulting in an increase in network flexibility and services. A key issue
that needs to be addressed in virtualization is the mapping of the virtual networks to the resources of the underlying
physical network. In this paper we present an improved virtual network mapping algorithm based on subgraph
isomorphism, which not only improves on the cost or resource efficiency of the mapping but is also computationally
efficient.
Network Virtualization Technology is serving as an effective method for providing a flexible and highly adaptable
shared substrate network to satisfy the diversity of demands. But the problem of efficiently embedding Virtual Network
(VN) onto substrate network is intractable since it is NP-hard. How to guarantee survivability of the embedding
efficiently is another great challenge. In this paper, we investigate the Survivable Virtual Network Embedding (SVNE)
problem and propose two efficient algorithms for solving this problem efficiently. Firstly, we formulate the model with
minimum-cost objective of survivable network virtualization problem by Mixed Integer Linear Programming (MILP).
We then devise two efficient relaxation-based algorithms for solving survivable virtual network embedding problem: (1)
Lagrangian Relaxation based algorithm, called LR-SVNE in this paper; (2) Decomposition based algorithm called DSVNE
in this paper. The results of simulation experiments show that these two algorithms both have good performance
on time efficiency but LR-SVNE can guarantee the solution converge to optimal one under small scale substrate
network.
Access to the requested content is limited to institutions that have purchased or subscribe to SPIE eBooks.
You are receiving this notice because your organization may not have SPIE eBooks access.*
*Shibboleth/Open Athens users─please
sign in
to access your institution's subscriptions.
To obtain this item, you may purchase the complete book in print or electronic format on
SPIE.org.
INSTITUTIONAL Select your institution to access the SPIE Digital Library.
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.