Geometric lower bounds for the steady-state occupancy of processing networks with limited connectivity
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_ | 1866909001018507264 |
|---|---|
| author | Goldsztajn, Diego Ferragut, Andres |
| author_facet | Goldsztajn, Diego Ferragut, Andres |
| contents | We consider processing networks where multiple dispatchers are connected to single-server queues by a bipartite compatibility graph, modeling constraints that are common in data centers and cloud networks due to geographic reasons or data locality issues. We prove lower bounds for the steady-state occupancy, i.e., the complementary cumulative distribution function of the empirical queue length distribution. The lower bounds are geometric with ratios given by two flexibility metrics: the average degree of the dispatchers and a novel metric that averages the minimum degree over the compatible dispatchers across the servers. Using these lower bounds, we establish that the asymptotic performance of a growing processing network cannot match that of the classic Power-of-$d$ or JSQ policies unless the flexibility metrics approach infinity in the large-scale limit. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2505_08974 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Geometric lower bounds for the steady-state occupancy of processing networks with limited connectivity Goldsztajn, Diego Ferragut, Andres Probability Performance 60K25 (Primary) 68M20 (Secondary) We consider processing networks where multiple dispatchers are connected to single-server queues by a bipartite compatibility graph, modeling constraints that are common in data centers and cloud networks due to geographic reasons or data locality issues. We prove lower bounds for the steady-state occupancy, i.e., the complementary cumulative distribution function of the empirical queue length distribution. The lower bounds are geometric with ratios given by two flexibility metrics: the average degree of the dispatchers and a novel metric that averages the minimum degree over the compatible dispatchers across the servers. Using these lower bounds, we establish that the asymptotic performance of a growing processing network cannot match that of the classic Power-of-$d$ or JSQ policies unless the flexibility metrics approach infinity in the large-scale limit. |
| title | Geometric lower bounds for the steady-state occupancy of processing networks with limited connectivity |
| topic | Probability Performance 60K25 (Primary) 68M20 (Secondary) |
| url | https://arxiv.org/abs/2505.08974 |