To describe a situation where, for example, mobile phones compete for the use of a satellite for transmitting their messages, we consider a random access network. Here, we assume packets arrive at (necessarily different) stations at Poisson rate , and times of transmissions are discrete. A station will always attempt to transmit a packet which has just arrived, then, if that fails, will retransmit after a time given by a independent random variables. Transmissions fail if at least two stations attempt to use the same window. For the ALOHA protocol, we assume these RVs are geometric with mean . We hope that the backlog, that is the number of stations with packets to retransmit at time *t* eventually clears. Say is the number of attempts in (t,t+1)$, proportional to where Y is the number of arrivals in (t,t+1), and then .

Then the drift in N is positive once N gets large. This is, however, not enough to prove that the system is transient. Instead we compute p(n), the probability that the channel unjams (that is, an instance where no transmissions are attempted) before the backlog increases, given that the backlog is currently n. We can calculate that this probability is and so . Applying Borel-Cantelli to the record process, that is the times at which the backlog increases, it can be shown that almost surely, the channel unjams only finitely many times.

To maximise throughput, we would take , but of course the individual stations don’t know what *n *is. However, they could guess. Suppose they view the process and keep a counter:

Then transmission happens with probability , with the idea that S tracks N well, especially when N is large. Observe that

where . So (a,b,c)=(2-e,0,1) for example gives negative S drift when k>1, and positive drift when k<1, which is required to draw S towards N. But S might still diverge asymptotically away from N? We don’t want N to increase too fast when k>1, but

so demanding is what we require when , which is satisfied by the example suggested.

If a station only knows its own transmission attempts, we can use Ethernet, where after r unsuccessful attempts, wait for a time chosen uniformly from . This is called *binary exponential backoff*. When , get infinitely many successful transmissions almost surely. But for positive recurrence, would have an equilibrium distribution, so by Little’s Law, we can equate arrival and departure rates. Considering the probabilities of 0 and 1 transmissions, obtain

So can be non-recurrent, but have infinitely many successful transmissions!

Pingback: 100k Views | Eventually Almost Everywhere