Mobile Networks and Management. Third International ICST Conference, MONAMI 2011, Aveiro, Portugal, September 21-23, 2011, Revised Selected Papers

Research Article

Virtual Network Mapping – An Optimization Problem

  • @INPROCEEDINGS{10.1007/978-3-642-30422-4_14,
        author={M\^{a}rcio Melo and Jorge Carapinha and Susana Sargento and Luis Torres and Phuong Tran and Ulrich Killat and Andreas Timm-Giel},
        title={Virtual Network Mapping -- An Optimization Problem},
        proceedings={Mobile Networks and Management. Third International ICST Conference, MONAMI 2011, Aveiro, Portugal, September 21-23, 2011, Revised Selected Papers},
        keywords={Embedding ILP Model Mapping NP-hard Optimization Virtual Networks},
  • Márcio Melo
    Jorge Carapinha
    Susana Sargento
    Luis Torres
    Phuong Tran
    Ulrich Killat
    Andreas Timm-Giel
    Year: 2012
    Virtual Network Mapping – An Optimization Problem
    DOI: 10.1007/978-3-642-30422-4_14
Márcio Melo,*, Jorge Carapinha1,*, Susana Sargento2,*, Luis Torres3,*, Phuong Tran3,*, Ulrich Killat3,*, Andreas Timm-Giel3,*
  • 1: Portugal Telecom Inovação
  • 2: University of Aveiro
  • 3: Hamburg University of Technology
*Contact email:,,,,,,


Network Virtualization is claimed to be a key component of the Future Internet by enabling the coexistence of heterogeneous (virtual) networks on the same physical infrastructure, providing the dynamic creation and support of different networks with different paradigms and mechanisms in the same physical network. A major challenge in the dynamic provision of virtual networks resides on the efficient embedding of virtual resources into physical ones. Since this problem is known to be -hard, previous research focused on designing heuristic-based 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  −  formulation is used and the multi-commodity flow 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 is evaluated by means of simulation. Simulation experiments show significant improvements of the virtual network acceptance ratio, in average additional 10% of the virtual network requests are accepted when using the integer linear programming formulation, which corresponds, in average, to more 7 virtual networks accommodated on the physical network.