The Library
Near-shortest path routing in hybrid communication networks
Tools
Tools
Tools
Coy, Sam, Czumaj, Artur, Feldmann, Michael, Hinnenthal, Kristian, Kuhn, Fabian, Scheideler, Christian, Schneider, Philipp and Struijs, Martijn (2022) Near-shortest path routing in hybrid communication networks. In: 25th International Conference on Principles of Distributed Systems (OPODIS 2021), Strasbourg, France, 13–15 Dec 2021. Published in: 25th International Conference on Principles of Distributed Systems (OPODIS 2021), 217 11:1-11:23. ISBN 9783959772198. doi:10.4230/LIPIcs.OPODIS.2021.11
|
PDF
WRAP-Near-shortest-path-routing-hybrid-communication-networks-2022.pdf - Published Version - Requires a PDF viewer. Available under License Creative Commons Attribution 4.0. Download (1135Kb) | Preview |
Official URL: https://doi.org/10.4230/LIPIcs.OPODIS.2021.11
Abstract
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.
| Item Type: | Conference Item (Paper) | |||||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Subjects: | Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software | |||||||||
| Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | |||||||||
| Library of Congress Subject Headings (LCSH): | Computer networks, Neural networks (Computer science), Routing (Computer network management), Hybrid computers, Electronic data processing -- Distributed processing -- Mathematical models | |||||||||
| Series Name: | Leibniz International Proceedings in Informatics (LIPIcs) | |||||||||
| Journal or Publication Title: | 25th International Conference on Principles of Distributed Systems (OPODIS 2021) | |||||||||
| Publisher: | Schloss Dagstuhl — Leibniz-Zentrum für Informatik | |||||||||
| Place of Publication: | Dagstuhl, Germany | |||||||||
| ISBN: | 9783959772198 | |||||||||
| Official Date: | 28 February 2022 | |||||||||
| Dates: |
|
|||||||||
| Volume: | 217 | |||||||||
| Page Range: | 11:1-11:23 | |||||||||
| DOI: | 10.4230/LIPIcs.OPODIS.2021.11 | |||||||||
| Status: | Peer Reviewed | |||||||||
| Publication Status: | Published | |||||||||
| Access rights to Published version: | Open Access (Creative Commons) | |||||||||
| Date of first compliant deposit: | 21 March 2022 | |||||||||
| Date of first compliant Open Access: | 22 March 2022 | |||||||||
| RIOXX Funder/Project Grant: |
|
|||||||||
| Conference Paper Type: | Paper | |||||||||
| Title of Event: | 25th International Conference on Principles of Distributed Systems (OPODIS 2021) | |||||||||
| Type of Event: | Conference | |||||||||
| Location of Event: | Strasbourg, France | |||||||||
| Date(s) of Event: | 13–15 Dec 2021 | |||||||||
| Related URLs: |
Request changes or add full text files to a record
Repository staff actions (login required)
 |
View Item |
Downloads
Downloads per month over past year
