English
 
User Manual Privacy Policy Disclaimer Contact us
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT

Released

Paper

With Great Speed Come Small Buffers: Space-Bandwidth Tradeoffs for Routing

MPS-Authors
/persons/resource/persons230547

Rosenbaum,  Will
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

Locator
There are no locators available
Fulltext (public)

arXiv:1902.08069.pdf
(Preprint), 667KB

Supplementary Material (public)
There is no public supplementary material available
Citation

Miller, A., Patt-Shamir, B., & Rosenbaum, W. (2019). With Great Speed Come Small Buffers: Space-Bandwidth Tradeoffs for Routing. Retrieved from http://arxiv.org/abs/1902.08069.


Cite as: http://hdl.handle.net/21.11116/0000-0003-0CD3-2
Abstract
We consider the Adversarial Queuing Theory (AQT) model, where packet arrivals are subject to a maximum average rate $0\le\rho\le1$ and burstiness $\sigma\ge0$. In this model, we analyze the size of buffers required to avoid overflows in the basic case of a path. Our main results characterize the space required by the average rate and the number of distinct destinations: we show that $O(k d^{1/k})$ space suffice, where $d$ is the number of distinct destinations and $k=\lfloor 1/\rho \rfloor$; and we show that $\Omega(\frac 1 k d^{1/k})$ space is necessary. For directed trees, we describe an algorithm whose buffer space requirement is at most $1 + d' + \sigma$ where $d'$ is the maximum number of destinations on any root-leaf path.