Daily Archives: May 20, 2012

Models for Random Access Channels

Posted on by
1

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 \nu, 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 f^{-1}. We hope that the backlog, that is N_t the number of stations with packets to retransmit at time t eventually clears. Say Z_t is the number of attempts in (t,t+1)$, proportional to Y_t+\text{Bin}(N_t,f) where Y is the number of arrivals in (t,t+1), and then N_{t+1}=N_t+Y_t-1_{Z_t=1}.

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 \sim n(1-f)^{n-1} and so \sum p(n)<\infty. 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 f=\frac{1}{n}, 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:

S_{t+1}=\max\left(1,S_t+a1_{Z_t=0}+b1_{Z_t=1}+c1_{Z_t=*}\right)

Then transmission happens with probability f=\frac{1}{S_t}, with the idea that S tracks N well, especially when N is large. Observe that

\mathbb{E}[S_{t+1}-S_t|N_t=n,S_t=s]\rightarrow (a-c)e^{-k}+(b-c)ke^{-k}+c

where k=\frac{n}{s}. 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

\mathbb{E}[N_{t+1}-N_t|N_t=n,S_t=s]\rightarrow \nu-ke^{-k}

so demanding \nu-ke^{-k}<k is what we require when \nu<e^{-1}, 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 B_r chosen uniformly from [1,\ldots,2^r]. This is called binary exponential backoff. When \nu<\log 2, 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

\nu=\pi_1e^{-\nu}+\pi_0\nu e^{-\nu}\quad\Rightarrow\quad \nu\leq e^{-\nu}\quad\Rightarrow\quad \nu<0.567

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

Advertisement