Introduction

Backoff is the method of choice for resolving contention in the use of multiple-access 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 [3] local-area network. When several packets attempt to use the multiple-access 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 shared-memory 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 Strategies

As 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 worst-case 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 multiple-access 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.

Results

We investigate the worst-case 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 delay-sequence 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 r-exponential backoff algorithm in which W_k=Θ(r^k) has makespan &Theta(n lg^lg rn). We also show that for any constant r > 1, the r-polynomial 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 Work

Our 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 multiple-access 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 [4]? 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 real-time constraints. We are optimistic that further research on backoff algorithms, using techniques such as adversarial queueing theory, will lead to more stable and higher-performing computer systems.

Research Support

This research was supported in part by the Singapore-MIT Alliance and by NSF Grants ACI-0324974, EIA-0112849, CNS-0305606 and CCR-0208670.

References

[1] M. P. Herlihy, V. Luchangco, M. Mor, and W. M. Scherer III. Software transactional memory for dynamic-sized data structures. In Proceedings of the Twenty-Second Annual ACM SIGACT-SIGOPS Symposium on Principles ofDistributed Computing (PODC), pages 92--101, Boston, Massachusetts, July 2003.

[2] Maurice Herlihy and J. Eliot B. Moss. Transactional memory: Architectural support for lock-free 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.), pages 289--300, San Diego, California, 1993.

[3] Robert M. Metcalfe and David R. Boggs. Ethernet: Distributed packet switching for local computer networks. Communications of the ACM, 19(7):395--404, July 1976.

[4] Ravi Rajwar and James R. Goodman. Transactional lock-free execution of lock-based programs. In Tenth International Conference on Architectural Supportfor Programming Languages and Operating Systems, pages 5-17, San Jose, California, October 5-9 2002.