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