Compact routing methods improve path efficiency with low memory use
Optimal (Randomized) Compact Routing Schemes
Data Structures and AlgorithmsNetworking and Internet Architecture
Summary
Routing messages efficiently in networks is tricky when each node can only remember a small amount of information. The authors study how to balance short travel paths for messages with minimal storage at each node in various routing models. They present new schemes that reduce the average path stretch (extra distance traveled) while keeping memory use low, sometimes using randomness in routing decisions. Their schemes improve on previous methods and are even proven optimal under certain theoretical assumptions. These improvements apply to both weighted and unweighted networks.
What this means in practice
- •For network engineers: Implement more efficient message routing in large-scale networks with limited memory per node, reducing overall communication delays.
- •For distributed systems developers: Design routing protocols that handle dynamic addresses with minimal storage and guaranteed path efficiency, improving system scalability.
Authors
Shiri Chechik, Avi Kadria, Gur Lifshitz, Liam Roditty
Abstract
Compact routing schemes route messages along short paths while every vertex stores little information. We study the trade-off between the stretch and the storage of compact routing schemes in undirected graphs, in four models: labeled and name-independent schemes, with average or worst-case local storage. We improve the best known stretch in all four models. Our main result is a labeled routing scheme with expected stretch $2k-1$ and $\widetilde O(n^{1/k})$ average local storage, in which only the routing is randomized. Under the Erdős girth conjecture, no scheme with this storage has stretch below $2k-1$, so our scheme is optimal, up to polylogarithmic factors in the storage. With deterministic routing, we obtain stretch $\approx2.47k$, the best known deterministic stretch with average storage. Worst-case local storage is the classical setting of compact routing. The leading coefficient $4$ in the stretch $4k-5$ of Thorup and Zwick~[SPAA'01] was improved only by Chechik~[PODC'13], to $\approx3.68$ in unweighted graphs. In unweighted graphs, we obtain expected stretch $(\frac83k+O(1),O(k))$, and deterministic stretch $\approx3.05k$. Name-independent routing is harder, since the source knows only the name of the destination. The best known stretch with $\widetilde O(n^{1/k})$ local storage in unweighted graphs was $96k$, by Abraham, Gavoille, and Malkhi~[DISC'04]. We improve it by more than a factor of $8$. With average storage, we obtain expected stretch $4k-5$, which matches the labeled scheme of Thorup and Zwick. With worst-case storage in unweighted graphs, we obtain expected stretch $(8k+O(1),O(k))$. All our schemes for unweighted graphs extend to weighted graphs with a small loss in the stretch, and still improve the previous unweighted bounds.