2025/03/17 by Kadria, Avi, Roditty, Liam · 1 citation
#FOS: Computer and information sciences #Networking and Internet Architecture (cs.NI)
paper · doi:10.48550/arxiv.2503.13753
In this paper, we study the problem of compact routing schemes in weighted undirected and directed graphs. For weighted undirected graphs, more than a decade ago, Chechik [PODC'13] presented a ≈3.68k-stretch compact routing scheme that uses O(n1/klogD) local storage, where D is the normalized diameter, for every k>1. We present a ≈ 2.64k-stretch compact routing scheme that uses O(n1/k) local storage on average in each vertex. This is the first compact routing scheme that uses total local storage of O(n1+1/k) while achieving a c ⋅ k stretch, for a constant c < 3. In real-world network protocols, messages are usually transformed as part of a communication session between two parties. Therefore, more than two decades ago, Thorup and Zwick [SPAA'01] considered compact routing schemes that establish a communication session using a handshake. In their handshake-based compact routing scheme, the handshake is routed along a (4k-5)-stretch path, and the rest of the communication session is routed along an optimal (2k-1)-stretch path. It is straightforward to improve the (4k-5)-stretch of the handshake to ≈3.68k-stretch using the compact routing scheme of Chechik [PODC'13]. We improve the handshake stretch to the optimal (2k-1), by borrowing the concept of roundtrip routing from directed graphs to undirected graphs. For weighted directed graphs, more than two decades ago, Roditty, Thorup, and Zwick [SODA'02 and TALG'08] presented a (4k+\eps)-stretch compact roundtrip routing scheme that uses O(n1/k) local storage for every k≥ 3. For k=3, this gives a (12+\eps)-roundtrip stretch using O(n1/3) local storage. We improve the stretch by developing a 7-roundtrip stretch routing scheme with O(n1/3) local storage.