Complexity of the Virtual Network Embedding with uniform demands
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915107546595328 |
|---|---|
| author | Benhamiche, Amal Fouilhoux, Pierre Létocart, Lucas Perrot, Nancy Schneider, Alexis |
| author_facet | Benhamiche, Amal Fouilhoux, Pierre Létocart, Lucas Perrot, Nancy Schneider, Alexis |
| contents | We study the complexity of the Virtual Network Embedding Problem (VNE), which is the combinatorial core of several telecommunication problems related to the implementation of virtualization technologies, such as Network Slicing. VNE is to find an optimal assignment of virtual demands to physical resources, encompassing simultaneous placement and routing decisions. The problem is known to be strongly NP-hard, even when the virtual network is a uniform path, but is polynomial in some practical cases. This article aims to draw a cohesive frontier between easy and hard instances for VNE. For this purpose, we consider uniform demands to focus on structural aspects, rather than packing ones. To this end, specific topologies are studied for both virtual and physical networks that arise in practice, such as trees, cycles, wheels and cliques. Some polynomial greedy or dynamic programming algorithms are proposed, when the physical network is a tree or a cycle, whereas other close cases are shown NP-hard. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2501_10154 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Complexity of the Virtual Network Embedding with uniform demands Benhamiche, Amal Fouilhoux, Pierre Létocart, Lucas Perrot, Nancy Schneider, Alexis Discrete Mathematics Networking and Internet Architecture We study the complexity of the Virtual Network Embedding Problem (VNE), which is the combinatorial core of several telecommunication problems related to the implementation of virtualization technologies, such as Network Slicing. VNE is to find an optimal assignment of virtual demands to physical resources, encompassing simultaneous placement and routing decisions. The problem is known to be strongly NP-hard, even when the virtual network is a uniform path, but is polynomial in some practical cases. This article aims to draw a cohesive frontier between easy and hard instances for VNE. For this purpose, we consider uniform demands to focus on structural aspects, rather than packing ones. To this end, specific topologies are studied for both virtual and physical networks that arise in practice, such as trees, cycles, wheels and cliques. Some polynomial greedy or dynamic programming algorithms are proposed, when the physical network is a tree or a cycle, whereas other close cases are shown NP-hard. |
| title | Complexity of the Virtual Network Embedding with uniform demands |
| topic | Discrete Mathematics Networking and Internet Architecture |
| url | https://arxiv.org/abs/2501.10154 |