A Multi-Objective Approach for VNE Problems using multiple ILP formulations

Authors

  • Cristian Aceval Centro Nacional de Computación, Universidad Nacional de Asunción, Paraguay
  • Enrique Dávalos Facultad Politécnica, Universidad Nacional de Asunción, Paraguay
  • Víctor Franco Facultad Politécnica, Universidad Nacional de Asunción, Paraguay
  • Benjamín Barán National University of Asuncion, Paraguay

DOI:

https://doi.org/10.19153/cleiej.19.2.1

Keywords:

ILP, VNE, Virtual network embedding, Network virtualization, Multi-objective optimization

Abstract

Network Virtualization is a key technology for the Future Internet, allowing the deployment of multiple independent virtual networks that use resources of the same basic infrastructure. An important challenge in the dynamic provision of virtual networks resides in the optimal allocation of physical resources (nodes and links) to requirements of virtual networks. This problem is known as Virtual Network Embedding (VNE).
For the resolution of this problem, previous research has focused on designing algorithms based on the optimization of a single objective. On the contrary, in this work we present a multi-objective algorithm, called VNE-MO-ILP, for solving dynamic VNE problem, which calculates an approximation of the Pareto Front considering simultaneously resource utilization and load balancing. Experimental results show evidences that the proposed algorithm is better or at least comparable to a state-of-the-art algorithm. Two performance metrics were simultaneously evaluated: (i) Virtual Network Request Acceptance Ratio and (ii) Revenue/Cost Relation.
The size of test networks used in the experiments shows that the proposed algorithm scales well in execution times, for networks of 84 nodes.

Author Biography

Cristian Aceval, Centro Nacional de Computación, Universidad Nacional de Asunción, Paraguay

Network Virtualization is a key technology for the Future Internet, allowing the deployment of multiple independent virtual networks that use resources of the same basic infrastructure. An important challenge in the dynamic provision of virtual networks resides in the optimal allocation of physical resources (nodes and links) to requirements of virtual networks. This problem is known as Virtual Network Embedding (VNE).
For the resolution of this problem, previous research has focused on designing algorithms based on the optimization of a single objective. On the contrary, in this work we present a multi-objective algorithm, called VNE-MO-ILP, for solving dynamic VNE problem, which calculates an approximation of the Pareto Front considering simultaneously resource utilization and load balancing. Experimental results show evidences that the proposed algorithm is better or at least comparable to a state-of-the-art algorithm. Two performance metrics were simultaneously evaluated: (i) Virtual Network Request Acceptance Ratio and (ii) Revenue/Cost Relation.
The size of test networks used in the experiments shows that the proposed algorithm scales well in execution times, for networks of 84 nodes.

Downloads

Published

2016-08-01

Issue

Vol. 19 No. 2 (2016): Special issue devoted to CLEI 2015 (part 2)

Section

Articles

License

CLEIej is supported by its home institution, CLEI, and by the contribution of the Latin American and international researchers community, and it does not apply any author charges whatsoever for submitting and publishing. Since its creation in 1998, all contents are made publicly accesibly. The current license being applied is a (CC)-BY license (effective October 2015; between 2011 and 2015 a (CC)-BY-NC license was used).