Annals of Probability 15 (1987), 1557-1568.
Available from
JSTOR, or
here.
We consider infinite source collision detect random access schemes. For such schemes we establish that the number of packets successfully transmitted is infinite with probability 0 or 1 according as the arrival rate is greater than or less than a critical value.
AMS 1980 subject classifications. Primary 60K99; secondary 60F20, 94A99.
Keywords and phrases. Random access, exponential backoff.
The simplest example of such a retransmission policy is the Aloha scheme (see, for example, [4]). Under this scheme, packets arriving during the interval $(t-1,t)$ are first transmitted in slot $(t,t+1)$, the first complete slot after their arrival. Also, backlogged packets are independently retransmitted with probability $f\in (0,1)$ in slot $(t,t+1)$. Thus, the retransmission delay following an unsuccessful attempt is geometrically distributed with parameter $1-f$. A more sophisticated retransmission policy is the Ethernet scheme. Under this scheme a station which has attempted unsuccessfully to transmit a packet $r$ times, retransmits after a further delay which has a discrete uniform distribution on $B_r=\{ 1,2,3,\ldots ,\lfloor b^r\rfloor\}$. Here $b>1$ is the backoff factor and the case $b=2$ is termed binary exponential backoff [11].
In this paper we prove that for a general collision detect random access scheme there exists a critical value $\nu_c\in [0,\infty ]$, with the property that the number of packets successfully transmitted is finite with probability 0 or 1 according as $\nu <\nu_c$ or $\nu >\nu_c$. For example, for the Aloha scheme $\nu_c=0$. More generally, we show that $\nu_c=0$ for any scheme with slower than exponential backoff. For the Ethernet scheme with backoff factor $b$ we prove that $\nu_c=\log b$.
The organization of this paper is as follows. In Section 2 we formally define the model and a number of examples, and in Section 3 we obtain our main results. In Section 4 we consider an unslotted version of the model, in which it is not assumed that stations are synchronized, and indicate how our results are altered in this case. For example, we find that an unslotted Ethernet scheme with backoff factor $b$ has a critical value of $\frac12\log b$.
Some of the results of this paper are described in [8] as part of a brief essay on probabilistic problems in random access communications. For a much fuller review of the area, the reader is referred to the collection [10]. In particular, the papers of Gallager [4] and Hajek [7] discuss in detail the assumptions underlying the basic model considered in this paper.