Dynamic Virtual Network Embedding: Using Incremental Model Transformation and Integer Linear Programming Techniques

By: Stefan Tomaszek, Lars Fritsche, Andy Schürr

Abstract

Network virtualization enables flexible placement, migration, and execution of virtual networks and machines on physical hardware. This results in an NP- hard optimization problem called virtual network embedding (VNE). Ensuring hardware and (non-)functional constraints while finding an optimal solution for a wide range of scenarios is a challenging task in these highly dynamic environments.To develop and evaluate algorithms tailored for various environments, we present a model-driven approach to specify and solve dynamic VNE problems by using a high-level specification to declaratively specify the search space and constraints, incremental model transformation to prune the search space, and low-level ILP techniques to find an optimal solution in the pruned search space. This high-level specification is used to generate an executable program for solving dynamic VNE problems. Furthermore, we show in an evaluation that this generated program can solve a typical dynamic VNE problem in less time than a hand-crafted ILP-based program.

Keywords

virtual network embedding, incremental model transformation, data center, integer linear programming

Cite as:

Stefan Tomaszek, Lars Fritsche, Andy Schürr, “Dynamic Virtual Network Embedding: Using Incremental Model Transformation and Integer Linear Programming Techniques”, Journal of Object Technology, Volume 19, no. 2 (July 2020), pp. 9:1-21, doi:10.5381/jot.2020.19.2.a9.