Adversarial contention resolution for simple channels

This paper analyzes the worst-case performance of randomized backoff on simple multiple-access channels. Most previous analysis of backoff has assumed a statistical arrival model. For batched arrivals, in which all n packets arrive at time 0, we show the following tight high-probability bounds. Randomized binary exponential backoff has makespan Θ(n lg n), and more generally, for any constant r, r-exponential backoff has makespan Θ(n log^lgr n). Quadratic backoff has makespan Θ((n/lg n)^3/2), and more generally, for r > 1, r-polynomial backoff has make-span Θ((n/ lg n)^1+1/r). Thus, for batched inputs, both exponential and polynomial backoff are highly sensitive to backoff constants. We exhibit a monotone superpolynomial subexponential backoff algorithm, called loglog-iterated backoff, that achieves makespan Θ(n lg lg n/ lg lg lg n). We provide a matching lower bound showing that this strategy is optimal among all monotone backoff algorithms. Of independent interest is that this lower bound was proved with a delay sequence argument. In the adversarial-queuing model, we present the following stability and instability results for exponential backoff and log log-iterated backoff. Given a (λ, T)-stream, in which at most n = λT packets arrive in any interval of size T, exponential backoff is stable for arrival rates of λ = O(l/ lg n) and unstable for arrival rates of λ = Ω(lg lg n/lg n); loglog-iterated backoff is stable for arrival rates of λ = O(1/(lg lg n lg n)) and unstable for arrival rates of λ = Ω(1 / lg n). Our instability results show that bursty input is close to being worst-case for exponential backoff and variants and that even small bursts can create instabilities in the channel.