Optimal query strategies improve internet bottleneck detection
Optimal Non-Adaptive Vantage Point Selection
Data Structures and Algorithms
Summary
This paper looks at how to best pick points in a network to learn about the weakest links, called bottlenecks, without knowing the network details upfront. The authors find the best way to make queries from selected points to reveal the most information about these bottlenecks. They show mathematically the limits of how well any method can do and provide algorithms that match these limits pretty closely. This helps in diagnosing network capacity problems more efficiently.
What this means in practice
- •For network engineers: Design efficient monitoring strategies that select measurement points to uncover critical capacity limits in large communication networks.
- •For data center operators: Plan non-adaptive probes to detect network bottlenecks rapidly without prior knowledge of link capacities.
A theory result. No direct application yet.
Authors
Jie Gao, Nicole Wein, Chang Wu
Abstract
We study the \emph{vantage point selection} problem, introduced by Ashvinkumar, Chowdhury, Gao, Goswami, Mitchell, and Polishchuk [WADS'25] to model the problem of estimating bottleneck capacities on the Internet. The input is a weighted undirected graph with unique shortest paths where every edge has a distinct unknown \emph{capacity}. When the algorithm \emph{queries} a vertex $v$, it reveals the minimum-capacity edge on the shortest path from $v$ to every other vertex reachable from $v$. The goal is to maximize the total number of revealed edges. The quality of an algorithm is measured by its competitive ratio against an optimal algorithm that knows all edge capacities a priori. We first consider the foundational single-query setting, where both the algorithm and the optimal algorithm are restricted to a single query. There is a trivial upper bound of $O(n)$ on the competitive ratio and the best known lower bound was $\tildeΩ(\sqrt{n})$. We provide an algorithm and matching lower bound (up to polylogarithmic factors) showing that the best possible competitive ratio is $\tildeΘ(n^{2/3})$. Furthermore, we extend our results to the general setting where the optimal algorithm is allowed $k$ queries and our algorithm is allowed $αk$ queries for $α\geq 1$. We present a randomized non-adaptive algorithm and matching lower bound (up to polylogarithmic factors) showing that the best possible expected competitive ratio for non-adaptive algorithms is the following surprisingly complex bound: $$ \tildeΘ\left( \min\left\{ \frac{n}{αk}, \max\left( \sqrt{\frac{n}α}, \frac{n^{2/3}}{αk^{1/3}} \right) \right\} \right). $$