For a large number of users the ALOHA protocol is considered. There are two versions of ALOHA that is Pure ALOHA and Slotted ALOHA. In Pure ALOHA no slotting was done but the efficiency was poor. In Slotted ALOHA, slots have been made, so that every frame transmission starts at the beginning of the slot and throughput is increased by a factor of 2.

ALOHA

If one node sends a frame to another node, there can be some error in the frame. For the same, we discussed some retransmission strategies to deal with the error. But, in case of allocating a single channel among N uncoordinated competing users, then the probability of collision will be high. Station accesses the channel and when their frames are ready. This is called random access. In an ALOHA network, one station will work as the central controller, and the other station will be connected to the central station. If, any of the stations want to transmit data among themselves, then, the station sends the data first to the central station, which broadcasts it to all the stations.

Here, the medium is shared between the stations. So, if two stations transmit a frame at an overlapping time then, collision will occur in the system. Here, no station is constrained; any station that has data /frame to transmit can transmit at any time. Once one station sends a frame (when it receives its own frame and assumes that the destination has received it) after 2 times the maximum propagation time. If the sender station does not receive its own frame during this time limit then, it retransmits this frame by using the Backoff algorithm that we will discuss later on. And if, after a number of repeats if it does receive its own pocket then the station gives up and stops retransmitting the same frame.

Let R be the bit rate of the transmission channel and L be the length of the frame. Here, we are assuming that the size of the frame will be constant, and hence, it will take constant time t= L/R for transmission of each packet.

Pure ALOHA

As in the case of Pure ALOHA protocol frames can be sent any time so, the probability of collision will be very high. Hence, to present a frame from colliding, no other frame should be sent within its transmission time. We will explain this with the help of the concept of vulnerable period as shown in Figure. Let a frame is that transmitted at time t₀ and t be the time required for its transmission. If, any other station sends a frame between t₀ and t₀+t then the end of the frame will collide with that earlier sent frame. Similarly, if any other station transmits a frame between the time interval t₀+t and t₀+2t again, it will result in a garbage frame due to collision with the reference frame. Hence, 2t is the vulnerable interval for the frame. In case a frame meets with collision that frame is retransmitted after a random delay.

Hence, for the probability of successful transmission, no additional frame should be transmitted in the vulnerable interval 2t.

To find the probability of no collision with a reference a frame, we assume that a number of users are generating new frames according to Poissons distribution. Let S be the arrival rate of new frames per frame time. As we find probability of no collision, S will represent the throughput of the system. Let G be the total arrival rate of frames including retransmission frames (also called a  load of the system). For finding the probability of transmission from the new and retransmitted frame, it is assumed that frames arrival is Poisson distributed with an average number of arrivals of G frames/ frame time. The probability of k frames transmission in 2t seconds is given by the Poisson distribution as follows:

The throughput of the system S is equal to total arrival rate G times the probability of successful transmission with no collision,

That is S=G * P (zero frame transmission in the vulnerable interval i.e., 2t seconds)

\[Since,~~P[K~frame~in~vulnerable~~interval~~2t]=\frac{\left( 2G \right){{e}^{-2G}}}{K!},K=0,1,2,3\]

Thus P [K = 0 in 2t] = – 2G. Hence, S = G * P = G . e^–2G Note that the averages load is G. Hence it is 2G in 2t S=G * e^-2G. The relationship between S vs. G can be shown in Figure:

As G is increasing, S is also increasing for small values of G. At G=1/2, S attains its peak value i.e., S=1/2e i.e., 0.18(approx). After that, it starts decreasing for increasing values of G. Here, the average number of successful transmission attempts/frames can be given as G/S = e^2G.

An average number of unsuccessful transmission attempts/frame is G/S – 1 = e^2G − 1.

By this, we know that the performance of ALOHA is not good as the unsuccessful transmission is increasing exponentially with load G. So, we will discuss Slotted ALOHA in the next to see how performance can be improved.

SLOTTED ALOHA

In this, we can improve performance by reducing the probability of collision. In the slotted ALOHA, stations are allowed to transmit frames in slots only. If more than one station transmits in the same slot, it will lead to a collision. This reduces the occurrence of collisions in the network system. Here, every station has to maintain the record of the time slot. The process of transmission will be initiated by any station at the beginning of the time slot only. Here also, frames are assumed to be of constant length and with the same transmission time. Here the frame will collide with the reference frame only if; it arrives in the interval t₀-t to t₀. Hence, here the vulnerable period is reduced that is to t seconds long. The throughput of the system S is equal to the total arrival rate G times the probability of successful transmission with no collision.

That is S = G * P (zero frame transmission in t seconds)

The probability of k frames transmission in t seconds and is given by the Poisson distribution as follows:

\[P\left[ k \right]=\frac{{{\left( G \right)}^{k}}*{{e}^{-G}}}{k!},k=0,1,2,3,….\]

Here average load in the vulnerable interval is G (one frame time) Hence, the probability of zero frames in t seconds = e^-G.

S= G * e^-G

The relationship between S vs G can be shown in Figure:

From the figure, we can see that the system is exhibiting its performance. Maximum throughput that can be achieved with Slotted ALOHA S=1/e= 36 % (Approx.)

However, with this performance also we are not able to utilize the medium in an efficient manner. Due to the high rate of collision systems, the bandwidth is which was designed to implement random access in LANs. So, we will discuss a new protocol called CSMA in the next post.

How does Slotted ALOHA improve the performance of the system over Pure ALOHA?

Slotted ALOHA follows synchronization for transmitting the frames that reduces the probability of collision and hence improves the efficiency.

Explain Back off Algorithm and give one example of where it is used.

After a collision is sensed by the channel, time is divided up into discrete slots. For example, if first collision identified then each station waits for either 0 or 1 slot time. Similarly, if third collision occurs then random interval will be 0 to 7 and for ith collision random number interval will be 0 to 2ⁱ -1. Subsequently, these many numbers of slots will be skipped before retransmission. This is called as binary exponential back off algorithm. CSMA/CD uses back off algorithm.