## Abstract

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.

Original language | English (US) |
---|---|

Pages | 325-332 |

Number of pages | 8 |

DOIs | |

State | Published - 2005 |

Event | Seventeenth Annual ACM Symposium on Parallelism in Algorithms and Architectures - Las Vegas, NV, United States Duration: Jul 18 2005 → Jul 20 2005 |

### Other

Other | Seventeenth Annual ACM Symposium on Parallelism in Algorithms and Architectures |
---|---|

Country/Territory | United States |

City | Las Vegas, NV |

Period | 7/18/05 → 7/20/05 |

## All Science Journal Classification (ASJC) codes

- Engineering(all)

## Keywords

- Batch
- Exponential Back-off
- On-line
- Polynomial Backoff
- Worst-Case Backoff Performance