Packet Forwarding with a Locally Bursty Adversary

Author Will Rosenbaum



PDF
Thumbnail PDF

File

LIPIcs.DISC.2022.34.pdf
  • Filesize: 0.78 MB
  • 18 pages

Document Identifiers

Author Details

Will Rosenbaum
  • Amherst College, MA, USA

Acknowledgements

This work was born from numerous discussions with Boaz Patt-Shamir, to whom I am eternally grateful. I thank the anonymous reviewers for their thoughtful commentary which helped improve this paper.

Cite AsGet BibTex

Will Rosenbaum. Packet Forwarding with a Locally Bursty Adversary. In 36th International Symposium on Distributed Computing (DISC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 246, pp. 34:1-34:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.DISC.2022.34

Abstract

We consider packet forwarding in the adversarial queueing theory (AQT) model introduced by Borodin et al. We introduce a refinement of the AQT (ρ, σ)-bounded adversary, which we call a locally bursty adversary (LBA) that parameterizes injection patterns jointly by edge utilization and packet origin. For constant (O(1)) parameters, the LBA model is strictly more permissive than the (ρ, σ) model. For example, there are injection patterns in the LBA model with constant parameters that can only be realized as (ρ, σ)-bounded injection patterns with ρ + σ = Ω(n) (where n is the network size). We show that the LBA model (unlike the (ρ, σ) model) is closed under packet bundling and discretization operations. Thus, the LBA model allows one to reduce the study of general (uniform) capacity networks and inhomogenous packet sizes to unit capacity networks with homogeneous packets. On the algorithmic side, we focus on information gathering networks - i.e., networks in which all packets share a common destination, and the union of packet routes forms a tree. We show that the Odd-Even Downhill (OED) forwarding protocol described independently by Dobrev et al. and Patt-Shamir and Rosenbaum achieves buffer space usage of O(log n) against all LBAs with constant parameters. OED is a local protocol, but we show that the upper bound is tight even when compared to centralized protocols. Our lower bound for the LBA model is in contrast to the (ρ, σ)-model, where centralized protocols can achieve worst-case buffer space usage O(1) for ρ, σ = O(1), while the O(log n) upper bound for OED is optimal only for local protocols.

Subject Classification

ACM Subject Classification
  • Theory of computation → Routing and network design problems
  • Networks → Packet scheduling
  • Theory of computation → Distributed algorithms
  • Theory of computation → Distributed computing models
Keywords
  • packet forwarding
  • packet scheduling
  • adversarial queueing theory
  • network calculus
  • odd-even downhill forwarding
  • locally bursty adversary
  • local algorithms

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads

References

  1. Micah Adler and Adi Rosén. Tight bounds for the performance of longest-in-system on dags. In Helmut Alt and Afonso Ferreira, editors, STACS 2002: 19th Annual Symposium on Theoretical Aspects of Computer Science, Antibes - Juan les Pins, France, March 14-16, 2002 Proceedings, pages 88-99, Berlin, Heidelberg, 2002. Springer Berlin Heidelberg. URL: https://doi.org/10.1007/3-540-45841-7_6.
  2. Allan Borodin, Jon Kleinberg, Prabhakar Raghavan, Madhu Sudan, and David P. Williamson. Adversarial queuing theory. J. ACM, 48(1):13-38, January 2001. URL: https://doi.org/10.1145/363647.363659.
  3. Johannes Bund, Matthias Függer, Christoph Lenzen, Moti Medina, and Will Rosenbaum. PALS: plesiochronous and locally synchronous systems. In 26th IEEE International Symposium on Asynchronous Circuits and Systems, ASYNC 2020, Salt Lake City, UT, USA, May 17-20, 2020, pages 36-43. IEEE, 2020. URL: https://doi.org/10.1109/ASYNC49171.2020.00013.
  4. R. L. Cruz. A calculus for network delay, part I: Network elements in isolation. IEEE Transactions on Information Theory, 37(1):114-131, January 1991. URL: https://doi.org/10.1109/18.61109.
  5. R.L. Cruz. A calculus for network delay. ii. network analysis. IEEE Transactions on Information Theory, 37(1):132-141, 1991. URL: https://doi.org/10.1109/18.61110.
  6. Stefan Dobrev, Manuel Lafond, Lata Narayanan, and Jaroslav Opatrny. Optimal local buffer management for information gathering with adversarial traffic. In Christian Scheideler and Mohammad Taghi Hajiaghayi, editors, Proceedings of the 29th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA 2017, Washington DC, USA, July 24-26, 2017, pages 265-274. ACM, 2017. URL: https://doi.org/10.1145/3087556.3087577.
  7. S. Kundu and S. Chattopadhyay. Network-on-Chip: The Next Generation of System-on-Chip Integration. CRC Press, 2018. Google Scholar
  8. Avery Miller and Boaz Patt-Shamir. Buffer size for routing limited-rate adversarial traffic. In DISC 2016: Proceedings of the 30th International Symposium on Distributed Computing, Paris, France, September 27-29, 2016, pages 328-341. Springer, 2016. URL: https://doi.org/10.1007/978-3-662-53426-7_24.
  9. Avery Miller, Boaz Patt-Shamir, and Will Rosenbaum. With great speed come small buffers: Space-bandwidth tradeoffs for routing. In Peter Robinson and Faith Ellen, editors, Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, PODC 2019, Toronto, ON, Canada, July 29 - August 2, 2019, pages 117-126. ACM, 2019. URL: https://doi.org/10.1145/3293611.3331614.
  10. Boaz Patt-Shamir and Will Rosenbaum. The space requirement of local forwarding on acyclic networks. In Elad Michael Schiller and Alexander A. Schwarzmann, editors, PODC 2017: Proceedings of the ACM Symposium on Principles of Distributed Computing, Washington, DC, USA, July 25-27, 2017, pages 13-22. ACM, 2017. URL: https://doi.org/10.1145/3087801.3087803.
  11. Boaz Patt-Shamir and Will Rosenbaum. Space-optimal packet routing on trees. In 2019 IEEE Conference on Computer Communications, INFOCOM 2019, Paris, France, April 29 - May 2, 2019, pages 1036-1044. IEEE, 2019. URL: https://doi.org/10.1109/INFOCOM.2019.8737596.
  12. David Salyers, Yingxin Jiang, Aaron Striegel, and Christian Poellabauer. Jumbogen: Dynamic jumbo frame generation for network performance scalability. SIGCOMM Comput. Commun. Rev., 37(5):53-64, October 2007. URL: https://doi.org/10.1145/1290168.1290174.
  13. Stefan Schmid and Jukka Suomela. Exploiting locality in distributed sdn control. In Proceedings of the Second ACM SIGCOMM Workshop on Hot Topics in Software Defined Networking, HotSDN '13, pages 121-126, New York, NY, USA, 2013. Association for Computing Machinery. URL: https://doi.org/10.1145/2491185.2491198.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail