Geometric lower bounds for the steady-state occupancy of processing networks with limited connectivity
This work addresses performance bottlenecks in data centers and cloud networks with limited connectivity, providing theoretical lower bounds that are incremental to existing queueing theory.
The paper tackles the problem of performance limitations in processing networks with constrained connectivity, proving geometric lower bounds for steady-state occupancy using two flexibility metrics. It shows that asymptotic performance cannot match classic policies like Power-of-d or JSQ unless flexibility metrics become infinite in large-scale limits.
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.