  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.
