Creating and sharing knowledge for telecommunications

Virtual Network Mapping - An Optimization Problem

Melo, M. ; Carapinha, J. ; Sargento, S. ; Torres, L. ; Tran-Phuong, N. Tran-Phuong ; Killat, U. Killat ; Timm-Giel, A.

Virtual Network Mapping - An Optimization Problem, Proc ICST Conf. on Mobile Networks and Management (MONAMI), Aveiro, Portugal, Vol. NA, pp. NA - NA, September, 2011.

Digital Object Identifier: 10.1007/978-3-642-30422-4_14

Download Full text PDF ( 540 KBs)

Network Virtualization is acclaimed to be a key component
for the Future Internet by enabling the coexistence of heterogeneous
(virtual) networks on the same physical infrastructure, providing
the dynamic creation and support of di erent networks with di erent
paradigms and mechanisms in the same physical network. A major challenge
in the dynamic provision of virtual networks resides on the ecient
embedding of virtual resources into physical ones. Since this problem is
known to be NP-hard, previous research focused on designing heuristicbased
algorithms; most of them do not consider a simultaneous optimization
of the node and the link mapping, leading to non optimal solutions.
This paper proposes an integer linear programming formulation to solve
the Virtual Network embedding problem, as a simultaneous optimization
of virtual nodes and links placement, providing the optimal boundary
for each virtual network mapping. A link􀀀node formulation is used and
the multi-commodity
ow constrain is applied. In addition, a heuristic
algorithm for virtual network embedding is also proposed and compared
against the optimal formulation. The performance of the Integer Linear
Programming formulation and of the heuristic are evaluated by means of
simulation. Simulation experiments show signi cant improvements of the
virtual network acceptance ratio, in average additional 10% of the virtual
network requests are accepted when using the proposed formulation,
which corresponds, in average, to more 7 virtual networks accommodated
on the physical network.