Stability and Instability Conditions for Slotted Aloha with Exponential Backoff

Abstract

This paper provides stability and instability conditions for slotted Aloha under the exponential backoff (EB) model with geometric law $i\mapsto b^{-i-i_0}$, when transmission buffers are in saturation, i.e., always full. In particular, we prove that for any number of users and for $b>1$ the system is: (i) ergodic for $i_0>1$, (ii) null recurrent for $0<i_0\le 1$, and (iii) transient for $i_0=0$. Furthermore, when referring to a system with queues and Poisson arrivals, the system is shown to be stable whenever EB in saturation is stable with throughput ${\lambda }_0$ and the system input rate is upper-bounded as $\lambda <{\lambda }_0$.

22 pages, 1 figure. Submitted to the IEEE Trans. on Information Theory