A decomposition approach for large virtual network embedding
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_ | 1866917157030330368 |
|---|---|
| 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 | Virtual Network Embedding (VNE) is the core combinatorial problem of Network Slicing, a 5G technology which enables telecommunication operators to propose diverse service-dedicated virtual networks, embedded onto a common substrate network. VNE asks for a minimum-cost mapping of a virtual network on a substrate network, encompassing simultaneous node placement and edge routing decisions. On a benchmark of large virtual networks with realistic topologies we compiled, the state-of-the art heuristics often provide expensive solutions, or even fail to find a solution when resources are sparse. We introduce a new integer linear formulation together with a decomposition scheme based on an automatic partition of the virtual network. This results in a column generation approach whose pricing problems are also VNE problems. This method allows to compute better lower bounds than state-of-the-art methods. Finally, we devise an efficient Price-and-Branch heuristic for large instances. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2512_17414 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | A decomposition approach for large virtual network embedding Benhamiche, Amal Fouilhoux, Pierre Létocart, Lucas Perrot, Nancy Schneider, Alexis Discrete Mathematics Networking and Internet Architecture Virtual Network Embedding (VNE) is the core combinatorial problem of Network Slicing, a 5G technology which enables telecommunication operators to propose diverse service-dedicated virtual networks, embedded onto a common substrate network. VNE asks for a minimum-cost mapping of a virtual network on a substrate network, encompassing simultaneous node placement and edge routing decisions. On a benchmark of large virtual networks with realistic topologies we compiled, the state-of-the art heuristics often provide expensive solutions, or even fail to find a solution when resources are sparse. We introduce a new integer linear formulation together with a decomposition scheme based on an automatic partition of the virtual network. This results in a column generation approach whose pricing problems are also VNE problems. This method allows to compute better lower bounds than state-of-the-art methods. Finally, we devise an efficient Price-and-Branch heuristic for large instances. |
| title | A decomposition approach for large virtual network embedding |
| topic | Discrete Mathematics Networking and Internet Architecture |
| url | https://arxiv.org/abs/2512.17414 |