
Research
Abstracts  2006 
Adversarial Analyses of Window Backoff Strategies for Simple MultipleAccess ChannelsMichael A. Bender (SUNY Stony Brook), Martin FarachColton (Rutgers), Simai He (SUNY Stony Brook), Bradley C. Kuszmaul & Charles E. LeisersonIntroductionBackoff is the method of choice for resolving contention in the use of multipleaccess channels. The idea of backoff is that whenever a packet experiences a collision in the use of the channel, it retries, but with a diminished probability of transmission in subsequent time slots. If all packets cooperate in using this strategy and the channel is not oversubscribed, all packets eventually can be transmitted without interference from other packets. Randomized backoff is perhaps best known in the context of the Ethernet [4] localarea network. When several packets attempt to use the multipleaccess Ethernet channel at the same time, a collision occurs, and no packets are successfully transmitted. Ethernet's exponential backoff hardware resolves this contention by retrying packet transmissions with exponentially decreasing frequency. Specifically, whenever an attempted transmission fails due to network contention, the hardware responsible for transmitting the packet doubles the value of a counter, and then it waits for a random amount of time whose expectation is proportional to the value of the counter before trying to transmit the packet again. Backoff has proved itself to be an effective and practical method for contention resolution in a myriad of settings besides Ethernet, including radio and satellite networks, email retransmission, TCP congestion control, Sun RPC congestion control, HTTP congestion control, DHCP retry, setting power levels on radio transmitters, barrier synchronization in sharedmemory multiprocessors, optical switching, contention resolution in PRAMs, randomized routing on fat trees, transaction conflict resolution in databases, and distributed databases, transactional memory access, lock conflicts, etc. Given the prominent role played by randomized backoff in computer systems, it is surprising how many aspects of backoff are not yet understood. Asymptotic Analysis of Backoff StrategiesAs part of the Transactions Everywhere project in the Supercomputing Technologies Group (Supertech), we are investigating algorithmic questions about the performance of backoff strategies. We address the following questions: How do backoff algorithms perform in the worstcase when the arrivals of packets are governed by an adversary rather than a statistical queueing model? How do backoff algorithms behave under the assumption that all packets arrive at the same time versus when they arrive individually over time? What is the proper rate for backing off: exponential, quadratic, or something else? Is there any advantage to "backing on," or should the probability of retransmission simply diminish over time? The answers to these questions depends on the model for the multipleaccess channel. Packets may have different sizes, taking different amounts of time to transmit. Furthermore, a collision of several packets may allow one or more packet transmissions to succeed, as opposed to all packets failing. The efficiency of a protocol can depend on how much information is fed back to the sender when a transmission fails due to a conflict. ResultsWe investigate the worstcase performance of randomized backoff algorithms for simple multiple access channels. In this model, all packets take unit time for transmission, and if several packets collide on the channel, none is successfully delivered. The only feedback to the backoff algorithm is the fact that the message was not delivered. Moreover, the algorithm cannot "listen" to the channel and glean information without actually attempting a transmission. We use delaysequence arguments to show that for the batch arrivals, if every window has size W = Θ(n) then with high probability, all packets successfully transmit with makespan n lg lg n ± O(n). We then use this result to analyze window backoff strategies with varying window sizes. We show that the binary exponential backoff has makespan Θ(n lg n), and that more generally, for any constant r > 1, the rexponential backoff algorithm in which W_{k}=Θ(r^{k}) has makespan &Theta(n lg^{lg r}n). We also show that for any constant r > 1, the rpolynomial backoff algorithm, in which W_{k}=Θ(k^{r}) has makespan Θ((n/lg n)^{1+1/r}).. All of these batch strategies are monotonic. 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 subexponentional, 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 O(n) We next study adversarial packet arrivals. Our results focus on exponential backoff. We show that for any arrival rate λ, there exists a sufficiently large interval size T such that the throughput goes to 0 for some (λ,T)stream. Moreover, there exists a sufficiently large constant c such that for any interval size T, binary exponential backoff is unstable with respect to some (λ,T)stream if λ ≥ c lg lgn/lg n, while there is a sufficiently small c such that binary exponential backoff is stable with respect to any (λ,T)adversary if λ≤c/lg n for a sufficiently small contant c. 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. Conclusion and Future WorkOur future work is targeted towards backoff and other schemes for transaction contention resolution. In this application, there are several directions for future work. First, in our target setting of contention resolution for transactional memory, some packets can be orders of magnitude larger than others. How can we generalize existing backoff schemes when there is heterogeneity of packet size? Second, we wish to employ backoff schemes in a multipleaccess channel where more information is available from an unsuccessful transmission than is provided by the simple multipleaccess channel. For example, a sender may know when others are transmitting, as in the 802.11 wireless standard. Error codes can be used to determine whether a packet collides with exactly one other packet or several. Can this information be used to improve performance? What happens if during a collision, one of the packets succeeds, as in [5]? What happens if packets take different amounts of time to transmit? How can we merge backoff schemes with other methods for contention resolution such as priority schemes based on aging? These questions appear particularly relevant for online settings, which occur more commonly in practice than batch settings. Currently, most computer engineers rely on simulations, not theoretical analyses, to gain confidence in backoff algorithms. As a consequence, systems employing backoff are generally nonalgorithmic, in the sense that performance is not guaranteed, not even statistically. Consequently, systems can exhibit wildly unpredictable performance, making it difficult or impossible to meet realtime constraints. We are optimistic that further research on backoff algorithms, using techniques such as adversarial queueing theory, will lead to more stable and higherperforming computer systems. This work appeared in [1]. Research SupportThis research was supported in part by the SingaporeMIT Alliance and by NSF Grants ACI0324974, EIA0112849, CNS0305606 and CCR0208670. References[1] Michael A. Bender, Martin FarachColton, Simai He, Bradley C. Kuszmaul, and Charles E. Leiserson. Adversarial Contention Resolution for Simple Channels. In The 17th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 2005), pp. 325332, Las Vegas, Nevada, July 2005, [2] M. P. Herlihy, V. Luchangco, M. Mor, and W. M. Scherer III. Software transactional memory for dynamicsized data structures. In Proceedings of the TwentySecond Annual ACM SIGACTSIGOPS Symposium on Principles of Distributed Computing (PODC), pp. 92101, Boston, Massachusetts, July 2003. [3] Maurice Herlihy and J. Eliot B. Moss. Transactional memory: Architectural support for lockfree data structures. In Proceedings of the 20th International Conference on Computer Architecture. (Also published as ACM SIGARCH Computer Architecture News, Volume 21, Issue 2, May 1993.), pp. 289300, San Diego, California, 1993. [4] Robert M. Metcalfe and David R. Boggs. Ethernet: Distributed packet switching for local computer networks. Communications of the ACM, 19(7):395404, July 1976. [5] Ravi Rajwar and James R. Goodman. Transactional lockfree execution of lockbased programs. In Tenth International Conference on Architectural Supportfor Programming Languages and Operating Systems, pp. 517, San Jose, California, October 59 2002. 

