Slotted Aloha Protocol Tutorial With Example

In the previous tutorial, we brushed up and got ourselves familiar to Pure ALOHA. In this tutorial, we will study about the advanced version of Pure ALOHA called slotted ALOHA protocol, its working, advantages and disadvantages of slotted ALOHA protocol.

What is Slotted ALOHA Protocol?

Slotted ALOHA Protocol was invented to improve the efficiency of pure ALOHA as chances of collision in pure ALOHA are very high. Though there is still a possibility of collision if two stations try to send data at the beginning of the same time slot. Slotted ALOHA protocol still has an edge over pure ALOHA as chances of collision are reduced to almost one half.

Working of Slotted ALOHA Protocol

Below picture clearly depicts working of slotted aloha protocol.

Tutorialwing Slotted Aloha Example of Slotted Aloha protocol

Slotted Aloha Example

Where,
Blue Block represents data being transferred.
White Block represents data being transferred at the same time or in the same block.

Slotted ALOHA assumes of exactly L bits. Time is divided into time slots of size L / R seconds (i.e. one slot is the time to transmit one frame). Here, L means “Constant size of frame in slotted aloha” and R means “transmission time of frame L”. The nodes start to transmit the frame only at the beginnings of slots. The nodes are synchronized so that each node knows when slots begin. If two or more frames collide in on particular slot, then, all the nodes detect the collision event before the slot ends. Let us look at the algorithmic working of slotted ALOHA.

While there is a new frame A to send to - 
   1. Send frame A at a slot boundary and wait for ACK
   2. If after some time ACK is received, successful transmission of frame.
   3. If there is a collision, the node detects the collision before the end of the slot.
   4. Wait a random amount of time and go to 1
End

The node retransmits its frame in each subsequent slot with probability p until the frame is transmitted without a collision.

Analysis of Slotted ALOHA

Let us consider N stations that have packets to send.
Assume each packet transmits in slot with probability p and probability of successful transmission S is:

  • By a specific single node: S = $ p * {(1-p)}^{(n-1)} $
  • By any of the N nodes: S = $ N * p * {(1-p)}^{(n-1)} $

For Optimum ‘p’ as N -> infinity
S = $ ( \frac {1}{e} ) $ = 0.37

Thus, the best possible use of the channel for transmission is 37 % of the time.

Tutorialwing Vulnerable time for Slotted Aloha protocol

Vulnerable time for Slotted Aloha

If we look at the calculations carefully, we realise that the vulnerable time is reduced to almost half in slotted ALOHA.

Throughput of Slotted ALOHA

The probability of no collision is given by
P(0) = $ {e}^{-G} $

So, The throughput S is
S = G * P(0) = G * ${e}^{-G}$

The maximum throughput of slotted ALOHA = $S_{max} = \frac {1}{e} = 0.37 $

Advanatages of Slotted ALOHA

  • Single active node can continuously transmit at full rate of channel
  • Highly decentralized: only slots in nodes need to be in sync
  • It is a simple protocol.

Disadvantages of Slotted ALOHA

  • Collision still occur in slotted ALOHA and thus a lot of slots are wasted.
  • Many a times, a lot of slots remain idle.
  • Nodes may be able to detect collision in less than time to transmit packet.
  • Clock synchronisation can not be achieved.

Important Points to Remember

  • Time is divided into slots. Each station is allowed to transmit only at the beginning of TT slot. If it misses one slot it has to wait for next.
  • Vulnerable time: Collision is possible in only current slot.
  • Efficiency of slotted aloha = G * $ {e}^{-G} $
    where, G = no of stations who wants to transmit in TT slot,
    TT stands for transmission time.
  • On calculation, it was found that efficiency of slotted aloha = 36.8%

Questions on Slotted Aloha

Q1. Consider a simplified time slotted MAC protocol, where each host always has data to send and transmits with probability p = 0.2 in every slot. There is no backoff and one frame can be transmitted in one slot. If more than one host transmits in the same slot, then the transmissions are unsuccessful due to collision. What is the maximum number of hosts which this protocol can support, if each host has to be provided a minimum through put of 0.16 frames per time slot? Gate Question (IT 2004)

(A) 1
(B) 2
(C) 3
(D) 4

Answer:

Correct option is (B).

The question talks about slotted MAC protocol i.e. if one station is transmitting data at a time, no other station can transmit data in that time.
Let us assume the probability of transmitting data by a single station be ‘p’ and let ‘n’ be the number of stations that are eligible to transmit.
Since no other station can transmit at a time, there will (n-1) stations that will not transmit having probability (1-p).
For one station, a minimum throughput of 0.16 frames per slot of time needs to be given (as given in the question). Thus, for ‘n’ stations, the throughput is given by 0.16 * n, and every station always has some data to transmit with the probability of p = 0.2 in every time slot.

So, 0.16 * n
=> n * 0.2 * ${0.8}^{(n-1)} $
=> 0.8 = ${0.8}^{(n-1)} $
=> n = 2.

This was all about Slotted ALOHA Protocol. We conclude our topic on access control methods. In the next tutorial, we will look at the differences between flow control methods and access control methods.

[latexpage]

Leave a Reply