Random Multi-access Algorithms - A Mean Field analysis

Charles Bordenave 1 David Mcdonald Alexandre Proutière
1 TREC - Theory of networks and communications
DI-ENS - Département d'informatique de l'École normale supérieure, Inria Paris-Rocquencourt
Abstract : In this paper, using mean field techniques, we present a performance analysis of random back-off algorithms, such as the exponential back-off algorithm, in the case of a finite number of saturated sources. We prove that when the number of sources grows large, the system is decoupled, i.e., source behaviors become mutually independent. These results are applied in the specific case of exponential back-off algorithms, where the transient and stationary distributions of the back-off processes are explicitly characterized. This work provides a theoretical justification of decoupling arguments used by many authors, e.g. Bianchi [4], to analyze the performance of random algorithms in Wireless LANs.
Document type :
Complete list of metadatas

Cited literature [11 references]  Display  Hide  Download

Contributor : Rapport de Recherche Inria <>
Submitted on : Friday, May 19, 2006 - 8:18:45 PM
Last modification on : Friday, May 25, 2018 - 12:02:04 PM
Long-term archiving on : Sunday, April 4, 2010 - 9:04:22 PM


  • HAL Id : inria-00070375, version 1



Charles Bordenave, David Mcdonald, Alexandre Proutière. Random Multi-access Algorithms - A Mean Field analysis. [Research Report] RR-5632, INRIA. 2005, pp.12. ⟨inria-00070375⟩



Record views


Files downloads