Skip to main content
Springer Nature Link
Log in

Routing Schemes for Hybrid Communication Networks

  • Conference paper
  • First Online:
Structural Information and Communication Complexity (SIROCCO 2023)

Part of the book series: Lecture Notes in Computer Science ((LNCS,volume 13892))

Abstract

We consider the problem of computing routing schemes in the \(\textsf{HYBRID}\) model of distributed computing where nodes have access to two fundamentally different communication modes. In this problem nodes have to compute small labels and routing tables that allow for efficient routing of messages in the local network, which typically offers the majority of the throughput. Recent work has shown that using the \(\textsf{HYBRID}\) model admits a significant speed-up compared to what would be possible if either communication mode were used in isolation. Nonetheless, if general graphs are used as the input graph the computation of routing schemes still takes polynomial rounds in the \(\textsf{HYBRID}\) model.

We bypass this lower bound by restricting the local graph to unit-disc-graphs and solve the problem deterministically with running time \(O(|\mathcal H|^2 + \log n)\), label size \(O(\log n)\), and size of routing tables \(O(|\mathcal H|^2 \cdot \log n)\) where \(|\mathcal H|\) is the number of “radio holes” in the network. Our work builds on recent work by Coy et al., who obtain this result in the much simpler setting where the input graph has no radio holes. We develop new techniques to achieve this, including a decomposition of the local graph into path-convex regions, where each region contains a shortest path for any pair of nodes in it.

This paper takes the form of an extended abstract, summarizing our results, construction, and techniques. A full version is available at https://arxiv.org/abs/2210.05333: the section numbering is the same in both versions.

We would like to thank Martijn Struijs for valuable discussions concerning the geometric insights of the paper. Any errors remain our own.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
USD 29.95
Price excludes VAT (USA)
eBook
USD 84.99
Price excludes VAT (USA)
Softcover Book
USD 109.99
Price excludes VAT (USA)

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

Notes

  1. 1.

    Minimizing hop-distance in a unit-disc-graph essentially minimizes the Euclidean distance that the path covers, thus graph weights are not required.

  2. 2.

    Some previous papers that consider hybrid models use \(\lambda = \infty \), i.e., the \(\textsf{LOCAL}\) model as local mode.

  3. 3.

    Our methods also work for to the stricter \(\mathsf {NCC_0}\) model as the global network, where only incident nodes in the local network and those that have been introduced, can communicate globally.

  4. 4.

    These results are in the more powerful hybrid combination of \(\textsf{LOCAL}\) and \(\textsf{NCC}\).

References

  1. Anagnostides, I., Gouleakis, T.: Deterministic distributed algorithms and lower bounds in the hybrid model. In: Gilbert, S. (ed.) 35th International Symposium on Distributed Computing (DISC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Dagstuhl, Germany, vol. 209, pp. 5:1–5:19. Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021). https://doi.org/10.4230/LIPIcs.DISC.2021.5. https://drops.dagstuhl.de/opus/volltexte/2021/14807

  2. Asadi, A., Mancuso, V., Gupta, R.: An SDR-based experimental study of outband D2D communications. In: The 35th Annual IEEE International Conference on Computer Communications, IEEE INFOCOM 2016, pp. 1–9 (2016). https://doi.org/10.1109/INFOCOM.2016.7524372

  3. Augustine, J., Hinnenthal, K., Kuhn, F., Scheideler, C., Schneider, P.: Shortest paths in a hybrid network model. In: Proceedings of the Thirty-First Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2020, USA, pp. 1280–1299. Society for Industrial and Applied Mathematics (2020)

    Google Scholar 

  4. Bose, P., Morin, P., Stojmenovic, I., Urrutia, J.: Routing with guaranteed delivery in ad hoc wireless networks. Wirel. Netw. 7(6), 609–616 (2001). https://doi.org/10.1023/A:1012319418150

    Article  MATH  Google Scholar 

  5. Castenow, J., Kolb, C., Scheideler, C.: A bounding box overlay for competitive routing in hybrid communication networks. In: Proceedings of the 21st International Conference on Distributed Computing and Networking (ICDCN 2020), pp. 14:1–14:10 (2020). https://doi.org/10.1145/3369740.3369777

  6. Censor-Hillel, K., Leitersdorf, D., Polosukhin, V.: Distance computations in the hybrid network model via oracle simulations. In: Bläser, M., Monmege, B. (eds.) 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Dagstuhl, Germany, vol. 187, pp. 21:1–21:19. Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021). https://doi.org/10.4230/LIPIcs.STACS.2021.21. https://drops.dagstuhl.de/opus/volltexte/2021/13666

  7. Censor-Hillel, K., Leitersdorf, D., Polosukhin, V.: On sparsity awareness in distributed computations. In: Proceedings of the 33rd ACM Symposium on Parallelism in Algorithms and Architectures, SPAA 2021, pp. 151–161. Association for Computing Machinery, New York (2021). https://doi.org/10.1145/3409964.3461798

  8. Coy, S., et al.: Near-shortest path routing in hybrid communication networks. In: Bramas, Q., Gramoli, V., Milani, A. (eds.) 25th International Conference on Principles of Distributed Systems (OPODIS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Dagstuhl, Germany, vol. 217, pp. 11:1–11:23. Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022). https://doi.org/10.4230/LIPIcs.OPODIS.2021.11. https://drops.dagstuhl.de/opus/volltexte/2022/15786

  9. Elkin, M., Neiman, O.: On efficient distributed construction of near optimal routing schemes. In: Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing, pp. 235–244 (2016)

    Google Scholar 

  10. Feldmann, M., Hinnenthal, K., Scheideler, C.: Fast hybrid network algorithms for shortest paths in sparse graphs. In: Proceedings of the 24th International Conference on Principles of Distributed Systems (OPODIS 2020), pp. 31:1–31:16 (2020). https://doi.org/10.4230/LIPIcs.OPODIS.2020.31

  11. Kuhn, F., Schneider, P.: Computing shortest paths and diameter in the hybrid network model. In: Proceedings of the 39th Symposium on Principles of Distributed Computing, PODC 2020, pp. 109–118. Association for Computing Machinery, New York (2020). https://doi.org/10.1145/3382734.3405719

  12. Kuhn, F., Schneider, P.: Routing schemes and distance oracles in the hybrid model. In: International Symposium on Distributed Computing (DISC), vol. 246, pp. 28:1–28:22 (2022)

    Google Scholar 

  13. Kuhn, F., Wattenhofer, R, Zhang, Y., Zollinger, A.: Geometric ad-hoc routing: of theory and practice. In: Proceedings of the 22nd ACM Symposium on Principles of Distributed Computing (PODC 2003), pp. 63–72 (2003). https://doi.org/10.1145/872035.872044

  14. Kuhn, F., Wattenhofer, R., Zollinger, A.: Asymptotically optimal geometric mobile ad-hoc routing. In: Proceedings of the 6th International Workshop on Discrete Algorithms and Methods for Mobile Computing and Communications (DIAL-M 2002), pp. 24–33 (2002). https://doi.org/10.1145/570810.570814

  15. Kuhn, F., Wattenhofer, R., Zollinger, A.: Worst-case optimal and average-case efficient geometric ad-hoc routing. In: Proceedings of the 4th ACM International Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc 2003), pp. 267–278 (2003). https://doi.org/10.1145/778415.778447

  16. Lenzen, C., Patt-Shamir, B.: Fast routing table construction using small messages: extended abstract. In: Proceedings of the Forty-Fifth Annual ACM Symposium on Theory of Computing, STOC 2013, pp. 381–390. Association for Computing Machinery, New York (2013). https://doi.org/10.1145/2488608.2488656

  17. Lenzen, C., Patt-Shamir, B.: Fast partial distance estimation and applications. In: Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing, pp. 153–162 (2015)

    Google Scholar 

  18. Lynch, N.A.: Distributed Algorithms. Elsevier (1996)

    Google Scholar 

  19. Rozhoň, V., Grunau, C., Haeupler, B., Zuzic, G., Li, J.: Undirected (1+\(\varepsilon \))-shortest paths via minor-aggregates: near-optimal deterministic parallel and distributed algorithms. In: Symposium on Theory of Computing, pp. 478–487 (2022)

    Google Scholar 

  20. Sarma, A.D., et al.: Distributed verification and hardness of distributed approximation. SIAM J. Comput. 41(5), 1235–1265 (2012)

    Article  MathSciNet  MATH  Google Scholar 

  21. Schneider, P.: Power and limitations of Hybrid communication networks. Ph.D. thesis, University of Freiburg (2023). https://doi.org/10.6094/UNIFR/232804

Download references

Author information

Authors and Affiliations

  1. University of Warwick, Coventry, UK

    Sam Coy & Artur Czumaj

  2. University of Paderborn, Paderborn, Germany

    Christian Scheideler & Julian Werthmann

  3. University of Freiburg, Freiburg im Breisgau, Germany

    Philipp Schneider

Authors
  1. Sam Coy
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Artur Czumaj
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Christian Scheideler
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Philipp Schneider
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. Julian Werthmann
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Philipp Schneider .

Editor information

Editors and Affiliations

  1. National Autonomous University of Mexico, Mexico, Mexico

    Sergio Rajsbaum

  2. Gran Sasso Science Institute, L’Aquila, Italy

    Alkida Balliu

  3. Arizona State University, Tempe, AZ, USA

    Joshua J. Daymude

  4. Gran Sasso Science Institute, L’Aquila, Italy

    Dennis Olivetti

Rights and permissions

Reprints and permissions

Copyright information

© 2023 The Author(s), under exclusive license to Springer Nature Switzerland AG

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Coy, S., Czumaj, A., Scheideler, C., Schneider, P., Werthmann, J. (2023). Routing Schemes for Hybrid Communication Networks. In: Rajsbaum, S., Balliu, A., Daymude, J.J., Olivetti, D. (eds) Structural Information and Communication Complexity. SIROCCO 2023. Lecture Notes in Computer Science, vol 13892. Springer, Cham. https://doi.org/10.1007/978-3-031-32733-9_14

Download citation

  • DOI: https://doi.org/10.1007/978-3-031-32733-9_14

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-031-32732-2

  • Online ISBN: 978-3-031-32733-9

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation