TU Berlin

Algorithmics and Computational Complexity Research GroupTalk 23.05.2019



zur Navigation

Es gibt keine deutsche Übersetzung dieser Webseite.

Virtual Network Embeddings: From Theory To Practice

Matthias Rost (TU Berlin)


Today, servers and the network connecting them are virtualized to allow the efficient sharing of both the computational and network resources. Accordingly, several novel resource allocation problems have arisen, with the Virtual Network Embedding Problem (VNEP) being the most prominent one. Specifically, the VNEP asks to embed virtual networks on a physical network by mapping virtualized nodes to physical nodes and establishing virtualized edges via paths in the physical network, while obeying capacity and other mapping restrictions. In this talk, several recent core results on the VNEP are presented.

(1) The VNEP is shown to be NP-complete for many combinations of mapping restrictions. Furthermore, it is shown that these results pertain when virtual networks are planar, hence, ruling out polynomial-time approximations for this graph class.

(2) To overcome the hardness of the VNEP, parametrized approximations are considered. In particular, the first XP-time approximations for the offline VNEP are presented under the treewidth parametrization. The approximations rely on the solving of linear programming formulations using column generation, where the separation problem is solved using dynamic programming on the tree decompositions of the virtual networks.

(3) As the approximations come at the price of exceeding resource capacities, heuristics respecting capacities are derived. In a large scale computational evaluation, the potential benefit over other common heuristics is shown.


Matthias Rost
TEL 512

Back to the research colloquium site.

Nach oben



Schnellnavigation zur Seite über Nummerneingabe