SpiderDAN: Matching Augmentation in Demand-Aware Networks
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866929595347894272 |
|---|---|
| author | Figiel, Aleksander Melnyk, Darya Nichterlein, André Pourdamghani, Arash Schmid, Stefan |
| author_facet | Figiel, Aleksander Melnyk, Darya Nichterlein, André Pourdamghani, Arash Schmid, Stefan |
| contents | Graph augmentation is a fundamental and well-studied problem that arises in network optimization. We consider a new variant of this model motivated by reconfigurable communication networks. In this variant, we consider a given physical network and the measured communication demands between the nodes. Our goal is to augment the given physical network with a matching, so that the shortest path lengths in the augmented network, weighted with the demands, are minimal.We prove that this problem is NP-hard, even if the physical network is a cycle. We then use results from demand-aware network design to provide a constant-factor approximation algorithm for adding a matching in case that only a few nodes in the network cause almost all the communication. For general real-world communication patterns, we design and evaluate a series of heuristics that can deal with arbitrary graphs as the underlying network structure. Our algorithms are validated experimentally using real-world traces (from e.g., Facebook) of data centers. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2411_11426 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | SpiderDAN: Matching Augmentation in Demand-Aware Networks Figiel, Aleksander Melnyk, Darya Nichterlein, André Pourdamghani, Arash Schmid, Stefan Data Structures and Algorithms Networking and Internet Architecture Graph augmentation is a fundamental and well-studied problem that arises in network optimization. We consider a new variant of this model motivated by reconfigurable communication networks. In this variant, we consider a given physical network and the measured communication demands between the nodes. Our goal is to augment the given physical network with a matching, so that the shortest path lengths in the augmented network, weighted with the demands, are minimal.We prove that this problem is NP-hard, even if the physical network is a cycle. We then use results from demand-aware network design to provide a constant-factor approximation algorithm for adding a matching in case that only a few nodes in the network cause almost all the communication. For general real-world communication patterns, we design and evaluate a series of heuristics that can deal with arbitrary graphs as the underlying network structure. Our algorithms are validated experimentally using real-world traces (from e.g., Facebook) of data centers. |
| title | SpiderDAN: Matching Augmentation in Demand-Aware Networks |
| topic | Data Structures and Algorithms Networking and Internet Architecture |
| url | https://arxiv.org/abs/2411.11426 |