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

We consider the Adversarial Queuing Theory (AQT) model, where packet arrivals are subject to a maximum average rate $0\le \rho \le 1$ and burstiness $\sigma \ge 0$. 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\mathrm{/}k})$ space suffice, where $d$ is the number of distinct destinations and $k=\lfloor 1\mathrm{/}\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^{\mathrm{\prime }}+\sigma$ where $d^{\mathrm{\prime }}$ is the maximum number of destinations on any root-leaf path.