TY - GEN
T1 - Near-Shortest Path Routing in Hybrid Communication Networks
AU - Coy, Sam
AU - Czumaj, Artur
AU - Feldmann, Michael
AU - Hinnenthal, Kristian
AU - Kuhn, Fabian
AU - Scheideler, Christian
AU - Schneider, Philipp
AU - Struijs, Martijn A.C.
PY - 2022/2/28
Y1 - 2022/2/28
N2 - Hybrid networks, i.e., networks that leverage different means of communication, become ever more widespread. To allow theoretical study of such networks, [Augustine et al., SODA'20] introduced the HYBRID model, which is based on the concept of synchronous message passing and uses two fundamentally different principles of communication: a local mode, which allows every node to exchange one message per round with each neighbor in a local communication graph; and a global mode where any pair of nodes can exchange messages, but only few such exchanges can take place per round. A sizable portion of the previous research for the HYBRID model revolves around basic communication primitives and computing distances or shortest paths in networks. In this paper, we extend this study to a related fundamental problem of computing compact routing schemes for near-shortest paths in the local communication graph. We demonstrate that, for the case where the local communication graph is a unit-disc graph with n nodes that is realized in the plane and has no radio holes, we can deterministically compute a routing scheme that has constant stretch and uses labels and local routing tables of size O(log n) bits in only O(log n) rounds.
AB - Hybrid networks, i.e., networks that leverage different means of communication, become ever more widespread. To allow theoretical study of such networks, [Augustine et al., SODA'20] introduced the HYBRID model, which is based on the concept of synchronous message passing and uses two fundamentally different principles of communication: a local mode, which allows every node to exchange one message per round with each neighbor in a local communication graph; and a global mode where any pair of nodes can exchange messages, but only few such exchanges can take place per round. A sizable portion of the previous research for the HYBRID model revolves around basic communication primitives and computing distances or shortest paths in networks. In this paper, we extend this study to a related fundamental problem of computing compact routing schemes for near-shortest paths in the local communication graph. We demonstrate that, for the case where the local communication graph is a unit-disc graph with n nodes that is realized in the plane and has no radio holes, we can deterministically compute a routing scheme that has constant stretch and uses labels and local routing tables of size O(log n) bits in only O(log n) rounds.
KW - Hybrid networks
KW - Overlay networks
UR - https://arxiv.org/abs/2202.08008
UR - http://www.scopus.com/inward/record.url?scp=85127433048&partnerID=8YFLogxK
U2 - 10.4230/LIPIcs.OPODIS.2021.11
DO - 10.4230/LIPIcs.OPODIS.2021.11
M3 - Conference contribution
VL - 217
T3 - Leibniz International Proceedings in Informatics, LIPIcs
SP - 11:1-11:23
BT - 25th International Conference on Principles of Distributed Systems (OPODIS 2021)
A2 - Bramas, Quentin
A2 - Gramoli, Vincent
A2 - Gramoli, Vincent
A2 - Milani, Alessia
PB - Schloss Dagstuhl - Leibniz-Zentrum für Informatik
ER -