The number of packets transmitted by collision detect random access schemes

F. P. Kelly
I. M. MacPhee

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.


An infinite number of stations share a single communication channel. Packets for transmission arrive in a Poisson stream of rate $\nu >0$ from time $t=0$ onward and no station ever has more than one packet arrive at it. All stations are synchronized and the time axis is slotted so that one packet can be successfully transmitted in the slot $(t,t+1),t=1,2,\ldots$. However, if two or more stations transmit in a slot, there is a collision and none of the packets involved is successfully transmitted. When a station transmits a packet, it learns at the end of the slot whether the packet has been successfully transmitted or whether a collision has occurred. Call the collection of packets that have collided and await transmission the backlog. A station with a backlogged packet waits for a random time and then retransmits the packet, repeating this procedure until the packet is successfully transmitted. In this paper we consider the case where the only information a station has concerning other stations or the use of the channel is the history of its own transmission attempts. Retransmission policies which use only this information are called collision detect (or acknowledgment based) random access schemes.

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.

Citations, from Google Scholar.
Frank Kelly's papers