Optimal Virtual Network Embeddings for Tree Topologies
| Autor: | Stefan Schmid, Rolf Niedermeier, Leon Kellerhals, Philipp Zschoche, Matthias Rost, Aleksander Figiel |
|---|---|
| Jazyk: | angličtina |
| Rok vydání: | 2021 |
| Předmět: |
Networking and Internet Architecture (cs.NI)
FOS: Computer and information sciences Computational complexity theory Heuristic (computer science) Computer science Distributed computing Parameterized complexity 020206 networking & telecommunications 02 engineering and technology Network topology Dynamic programming Computer Science - Networking and Internet Architecture Tree (data structure) 020204 information systems Computer Science - Data Structures and Algorithms 0202 electrical engineering electronic engineering information engineering Data Structures and Algorithms (cs.DS) Virtual network Integer programming |
| Zdroj: | SPAA |
| Popis: | The performance of distributed and data-centric applications often critically depends on the interconnecting network. Applications are hence modeled as virtual networks, also accounting for resource demands on links. At the heart of provisioning such virtual networks lies the NP-hard Virtual Network Embedding Problem (VNEP): how to jointly map the virtual nodes and links onto a physical substrate network at minimum cost while obeying capacities. This paper studies the VNEP in the light of parameterized complexity. We focus on tree topology substrates, a case often encountered in practice and for which the VNEP remains NP-hard. We provide the first fixed-parameter algorithm for the VNEP with running time $O(3^r (s+r^2))$ for requests and substrates of $r$ and $s$ nodes, respectively. In a computational study our algorithm yields running time improvements in excess of 200x compared to state-of-the-art integer programming approaches. This makes it comparable in speed to the well-established ViNE heuristic while providing optimal solutions. We complement our algorithmic study with hardness results for the VNEP and related problems. An extended abstract of this work appears in the Proceedings of the 33rd ACM Symposium on Parallelism in Algorithms and Architectures (SPAA '21) |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|