An Improved Stability Bound for Binary Exponential Backoff |
| |
Authors: | H Al-Ammal L A Goldberg P MacKenzie |
| |
Affiliation: | (1) Department of Computer Science, University of Bahrain, P.O. Box 32038, Isa Town, Bahrain hmea@batelco.com.bh , BH;(2) Department of Computer Science, University of Warwick, Coventry, CV4 7AL, England leslie@dcs.warwick.ac.uk , UK;(3) Information Sciences Center, Bell Laboratories, Lucent Technologies, 600 Mountain Avenue, Murray Hill, NJ 07974-0636, USA philmac@research.bell-labs.com, US |
| |
Abstract: | Goodman, Greenberg, Madras and March gave a lower bound of n
-Ω(log
n
) for the maximum arrival rate for which the n -user binary exponential backoff protocol is stable. Thus, they showed that the protocol is stable as long as the arrival
rate is at most n
-Ω(log
n
) . We improve the lower bound, showing that the protocol is stable for arrival rates up to O(n
-(0.75+δ)
) , for any δ>0 .
Received October 15, 1999, and in final form November 13, 2000. Online publication February 26, 2001. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|