Why is the throughput (performance) of the Slotted Aloha protocol ≈ 0.36

Question

I've read that the throughput - that is, the amount of good useful messages relative to capacity - of the Slotted ALOHA protocol for communication networks is roughly 0.36%.

But its not clear how we arrived at that number.

Can someone explain it?

Answer 1

Unlike in the regular ALOHA protocol, where other nodes can send messages that interfere with ours at any time, in the Slotted ALOHA protocol, the only other time a message can be sent to interfere with ours is if it's sent at the exact time ours is sent (since in Slotted ALOHA messages can only be sent at specific intervals, like every 5 seconds for example)

Therefore, the probability that our message will be the only one, and have no interference is the probability (in a Poisson Process) that only 1 message on the system (ours!) is sent on the mark

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

This gives us a function of the throughputs for all $\lambda$s.

To find the $\lambda$ with the highest throughput (that is, what expected rate gives us the highest throughput) we take the derivative and set to zero:

$$e^{-\lambda} - \lambda e^{-\lambda} = e^{-\lambda} (1 - \lambda) = 0 $$

$$\therefore \lambda = 1$$

In other words, when $\lambda$ is $1$, our throughput is highest. How high exactly? Just plug it back into the function we came up with, $\lambda e^{ - \lambda}$ and get:

$$ 1 * e^-1 = \frac{1}{e} = 0.36787....$$

Here's nice graph comparing the two ALOHAs, made by Reuven Cohen.

Answer 2

The answer to your question given is quoted directly for the most part from 'Computer Networking: A top down approach' by Kurose and Ross 4th Edition.

" we assume the following: • All frames consist of exactly L bits. • Time is divided into slots of size L/R seconds (that is, a slot equals the time to transmit one frame). • Nodes start to transmit frames only at the beginnings of slots. • The nodes are synchronized so that each node knows when the slots begin. • If two or more frames collide in a slot, then all the nodes detect the collision event before the slot ends.

Let p be a probability, that is, a number between 0 and 1. The operation of slotted ALOHA in each node is simple:

• When the node has a fresh frame to send, it waits until the beginning of the next slot and transmits the entire frame in the slot. • If there isn’t a collision, the node has successfully transmitted its frame and thus need not consider retransmitting the frame. (The node can prepare a new frame for transmission, if it has one.) • If there is a collision, the node detects the collision before the end of the slot. The node retransmits its frame in each subsequent slot with probability p until the frame is transmitted without a collision."

We make the following definition:

"A slot in which exactly one node transmits is said to be a successful slot. The efficiency of a slotted multiple access protocol is defined to be the long-run fraction of successful slots in the case when there are a large number of active nodes, each always having a large number of frames to send."

The derivation of the maximum efficiency - the answer to your question is given.

"To keep this derivation simple, let’s modify the protocol a little and assume that each node attempts to transmit a frame in each slot with probability p (That is, we assume that each node always has a frame to send and that the node transmits with probability p for a fresh frame as well as for a frame that has already suffered a collision.) Suppose there are N nodes. Then the probability that a given slot is a successful slot is the probability that one of the nodes transmits and that the remaining N – 1 nodes do not transmit. The probability that a given node transmits is p; the probability that the remaining nodes do not transmit is (1 – p)^N-1. Therefore the probability a given node has a success is p(1 – p)N-1. Because there are N nodes, the probability that any one of the N nodes has a success is Np(1 – p)^N-1."

To obtain the maximum efficiency we find a p* that maximizes the expression.

Also, to find maximum efficiency for a large number of nodes, we have to let N tend to infinity in Np*(1 – p*)^N-1. After performing the necessary calculation, you will get the maximum efficiency to be 0.37.