@online{Miller_arXiv1902.08069,
TITLE = {With Great Speed Come Small Buffers: Space-Bandwidth Tradeoffs for Routing},
AUTHOR = {Miller, Avery and Patt-Shamir, Boaz and Rosenbaum, Will},
LANGUAGE = {eng},
URL = {http://arxiv.org/abs/1902.08069},
EPRINT = {1902.08069},
EPRINTTYPE = {arXiv},
YEAR = {2019},
MARGINALMARK = {$\bullet$},
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.},
}