# Item

ITEM ACTIONSEXPORT

Released

Paper

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

##### 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.