License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.DISC.2022.34
URN: urn:nbn:de:0030-drops-172254
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/17225/
Go to the corresponding LIPIcs Volume Portal

Rosenbaum, Will

Packet Forwarding with a Locally Bursty Adversary

pdf-format:
LIPIcs-DISC-2022-34.pdf (0.8 MB)

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.

BibTeX - Entry

@InProceedings{rosenbaum:LIPIcs.DISC.2022.34,
  author =	{Rosenbaum, Will},
  title =	{{Packet Forwarding with a Locally Bursty Adversary}},
  booktitle =	{36th International Symposium on Distributed Computing (DISC 2022)},
  pages =	{34:1--34:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-255-6},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{246},
  editor =	{Scheideler, Christian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2022/17225},
  URN =		{urn:nbn:de:0030-drops-172254},
  doi =		{10.4230/LIPIcs.DISC.2022.34},
  annote =	{Keywords: packet forwarding, packet scheduling, adversarial queueing theory, network calculus, odd-even downhill forwarding, locally bursty adversary, local algorithms}
}

Keywords: packet forwarding, packet scheduling, adversarial queueing theory, network calculus, odd-even downhill forwarding, locally bursty adversary, local algorithms
Collection: 36th International Symposium on Distributed Computing (DISC 2022)
Issue Date: 2022
Date of publication: 17.10.2022

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI