Published Articles >> Table of Contents >> Abstract

18th International Parallel and Distributed Processing Symposium (IPDPS'04) - Workshop 10   p. 203
Adversarial Analyses of Window Backoff Strategies
Michael A. Bender, State University of New York at Stony Brook
Martin Farach-Colton, Rutgers University
Simai He, State University of New York at Stony Brook
Bradley C. Kuszmaul, Massachusetts Institute of Technology
Charles E. Leiserson, Massachusetts Institute of Technology

Full Article Text:

DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/IPDPS.2004.1303230
Send link to a friend

Abstract
Backoff strategies have typically been analyzed by making statistical assumptions on the distribution of problem inputs. Although these analyses have provided valuable insights into the efficacy of various backoff strategies, they leave open the question as to which backoff algorithms perform best in the worst case or on inputs, such as bursty inputs, that are not covered by the statistical models. This paper analyzes randomized backoff strategies using worst-case assumptions on the inputs. Specifically, we analyze algorithms for simple multiple-access channels, where the only feedback from each attempt to send a packet is a single bit indicating whether the transmission succeeded or the packet collided with another packet. We analyze a class of strategies, called window strategies, where each packet partitions time into a sequence (W1,W2, . . .) of windows. Within each window, the packet makes an access attempt during a single randomly selected slot. If its transmission is unsuccessful, it waits for its slot in the next window before retrying. We use delay-sequence arguments to show that for the batch problem, in which n packets all arrive at time 0, if every window has size W = Θ(n), then with high probability, all packets successfully transmit with makespan n lg lg n ± O(n). We use this result to analyze window backoff strategies with varying window sizes. Specifically, we show that the familiar binary exponential backoff algorithm, where Wk = Θ(2k), has makespan Θ(n lg n), and that more generally, for any constant r > 1, the r-exponential backoff algorithm in which Wk = Θ(rk) has makespan Θ(n lglg r n). We also show that for any constant r > 1, the r-polynomial backoff algorithm, in which Wk = Θ(kr), has makespan Θ((n/ lg n)1+1/r). All of these batch strategies are monotonic, in the sense that the window size monotonically increases over time. We exhibit a monotonic backoff algorithm that achieves makespan Θ(n lg lg n/ lg lg lg n). We prove that this algorithm, whose backoff is superpolynomial and subexponential, is optimal over all monotonic backoff schemes. In addition, we exhibit a simple backoff/backon algorithm, having window sizes that vary nonmonotonically according to a "sawtooth" pattern, that achieves the optimal makespan of Θ(n). We study the online setting using an adversarial queueing model. We define a (λ, Τ)-stream to be an input stream of packets in which at most n =λΤ packets arrive during any time interval of size Τ. In this model, to evaluate a given backoff algorithm (which does not know λ or Τ), we analyze the worst-case behavior of the algorithm over the class of (λ, Τ)-streams. Our results for the online setting focus on exponential backoff. We show that for any arrival rate λ, there exists a sufficiently large interval size Τ such that the throughput goes to 0 for some (λ, Τ)-stream. Moreover, there exists a sufficiently large constant c such that for any interval size Τ, if λ ≥ c lg lg n/ lg n, the system is unstable in the sense that the arrival rate exceeds the throughput in the worst case. If, on the other hand, we have λ ≤ c/ lg n for a sufficiently small constant c, then the system is stable. Surprisingly, the algorithms that guarantee smaller makespans in the batch setting require lower arrival rates to achieve stability than does exponential backoff, but when they are stable, they have better response times.
Back to Top Additional Information
Citation:  Michael A. Bender, Martin Farach-Colton, Simai He, Bradley C. Kuszmaul, Charles E. Leiserson, "Adversarial Analyses of Window Backoff Strategies," ipdps, p. 203,  18th International Parallel and Distributed Processing Symposium (IPDPS'04) - Workshop 10,  2004