2
$\begingroup$

I've read in a few places (like here that the throughput - that is, the amount of good useful messages relative to capacity - of the ALOHA protocol for networks is roughly 0.18%.

But its not clear how we arrived at that number.

Can someone explain it?

$\endgroup$
5
$\begingroup$

This number is reached first by assuming that messages will be produced and sent according to a Poisson process.

$$P[(N(t + \tau) - N(t)) = x] = \frac{{e^{ - \lambda\tau } (\lambda\tau) ^x }}{{x!}}$$

This means, that the probability of $x$ messages arriving for the given interval $[t, t+\tau]$ where $\lambda$ messages are expected to arrive, is equal to right side of the equation. In other words, if we are expecting 10 messages to arrive per hour, the chances of 6 messages arriving in an hour is roughly 6.3%.

Now, messages sent by ALOHA need to be alone in order to make it to all other the nodes undisturbed. In other words, no other nodes can be sending messages at the moment we want our message to be sent and must stay silent until our message is completely sent.

This means we want to find: $$P(exactly\space1\space\space message\space arriving) * P(exactly\space0\space\space messages\space arriving\space in\space next\space t)$$

The odds of exactly one message arriving is

$$P[(N(t + 1) - N(t)) = 1] = \frac{{e^{ - \lambda\tau } (\lambda\tau) ^ 1 }}{{1!}} = \lambda\tau e^{ - \lambda\tau} = \lambda e^{ - \lambda}$$

The odds of 0 messages arriving for $t$ is:

$$P[(N(t + 1) - N(t)) = 0] = \frac{{e^{ - \lambda\tau } (\lambda\tau) ^ 0 }}{{0!}} = e^{ - \lambda\tau} = e^{ - \lambda}$$

and together they make

$$\lambda e^{ - \lambda} \times e^{ - \lambda} = \lambda e^{ -2 \lambda}$$.

This function tells us the throughput of the Aloha for all values of $\lambda$. So which $\lambda$ offers the highest throughput? To find out, we take the derivative of $\lambda e^{ -2 \lambda}$ and get:

$$ e^{ -2 \lambda} - 2\lambda e^{ -2 \lambda}$$ set to 0 and solve for $\lambda$ and we get

$$\lambda = \frac{1}{2}$$

This means that in order to have the highest throughput (i.e. be most efficient) we should have an expected rate of incoming messages to be $\frac{1}{2}$ per timeslot.

And after all that, what is the maximum throughput that we get when we have an expected rate of $\frac{1}{2}$? Simply, plug it into our equation $\lambda e^{ -2 \lambda}$ and we get:

$$\frac{1}{2} e^{ -1} = 0.18393.... $$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.