Random Access Protocols – ALOHA, CSMA, CSMA/CA, CSMA/CD

In this tutorial, you will learn about Random Access Protocols. After reading this tutorial, you will get the basic knowledge of ALOHA and its types, CSMA, Persistence Methods, CSMA/CD, and CSMA/CA.

Contents:

  1. What is Random Access?
  2. What is ALOHA?
  3. Pure ALOHA
  4. Slotted ALOHA
  5. Carrier Sense Multiple Access (CSMA)
  6. Persistence Methods
  7. CSMA with Collision Detection Protocol (CSMA/CD)
  8. CSMA/CA: CSMA with Collision Avoidance

What is Random Access?

In random access, no device is superior to any other device connected to a channel, and no device has control over the other device. Any device can transmit whenever it wants, so the transmission between devices is random. Hence, these methods are known as random access.

  • In random access, no device permits another device to send frames on a channel.
  • At any time, the device uses the protocol when it wants to send a frame. Depending on the protocol, the device will decide whether to send or not.
  • Here, there is no scheduled time for a device to transmit the frame. Transmission occurs randomly over a channel between devices.
  • In random access, there is no rule as to which device is next to send the frame. So the devices compete with each other to access the channel to transmit the frame.
  • Frames will either be lost or modified if more than one device sends over a shared channel. So devices use a protocol to overcome this problem. We will study these protocols in this tutorial.
  • The two random access protocols are as follows:
    1. ALOHA
    2. CSMA

What is ALOHA?

ALOHA is a random access method used in wireless LANs and on any shared media. In ALOHA, media is shared between devices.

  • It may be possible that when a device sends data over a channel, another station may attempt to send the data at the same time.
  • When multiple devices try to send data over the same channel, they collide, and the data gets distorted.
  • ALOHA includes a simple and elegant way to solve the problem of channel allocation.
  • ALOHA is applicable for systems in which uncoordinated devices are competing for access to a shared channel.
  • There are two types of Aloha methods as follows:
    1. Pure ALOHA
    2. Slotted ALOHA

advertisement
advertisement

Pure ALOHA

The idea of the ALOHA system is simple that devices can transmit data whenever they have data to send. When more than one device sends data at the same time, a collision occurs between the frames. Therefore, the sender has to detect this problem when it is on the channel.

  • The device can listen for collisions when transmitting in some systems, such as a wired LAN.
  • If the frame is lost or destroyed, the sender waits for a random amount of time and resends it. Here, the wait time is random.
  • A system in which multiple devices share a channel has conflict is known as a contention system.

The figure below explains the Pure ALOHA system.

Pure ALOHA system
  • As shown in the above figure, there are 4 devices connected on a shared channel. Each device sends two frames on a single channel.
  • As you can see, only frame-1.1 and frame-4.2 survive and reach the destination, while other frames are lost during transmission due to collisions with each other.
  • Pure Aloha, when a receiver device successfully receives a frame, it sends an acknowledgment to the sending device.
  • If the acknowledgment is not received after the time-out period, the sender assumes that the frame has been destroyed and resends the frame.
  • After the timeout, collisions between frames occur when all devices resend the lost frame at once. To avoid collisions, each device waits a random amount of time before resending its frame.
  • Random timing helps to avoid more collisions known as back-off time Tb.

Pure Aloha also has a second method to prevent congesting the channel with re-transmitted frames.

  • In this method, there are maximum K-max attempts to retransmit the frame. The value of K-max is usually 15.
  • If the device retransmits the frame for K-max times, the device should give up and try again.
  • Here the back-off time Tb depends on the number of failed transmissions, which is K.
  • The time taken to transmit a frame is known as Transmission Time (Tfr). In Pure ALOHA, the vulnerable time is twice the transmission time.
  • The throughput of pure ALOHA can be calculated as,
    • S = G x e(-2G)
    • Where S = average number of successful transmissions for pure ALOHA,
    • G = the average number of frames generated by the device during transmission time of one frame.
    • Pure ALOHA has maximum throughput S-max = 0.184 when G = (1/2)

Slotted ALOHA

In Pure Aloha, no rules determine when a device can send frames over a channel. A device can send frames on the channel in two conditions. First, immediately after the transmission of another device has started. Second, immediately before the transmission of another device begins. But this increases the chances of a collision. So, slotted ALOHA solves this problem and is used to improve the efficiency of pure ALOHA.

  • In slotted ALOHA, time is divided into Tfr slots, so the device can only send at the beginning of the time slot.
  • The device is only allowed to send at the beginning of the synchronized time slot. If it misses, it will have to wait until the start of the next time slot.
  • If two devices try to send at the beginning of the same time slot, the possibility of a collision between the devices still exists.

The below diagram explains the slotted ALOHA system.

slotted ALOHA system
  • As shown in the figure, four devices shared a channel. Each device is sending two frames on a single channel.
  • Here the collisions are less as compared to pure ALOHA because they send the frame only when the particular time slot starts.
  • Out of 8 frames, 4 frames (Frame-1.1, Frame-2.1, Frame-4.1, and Frame-3.2) were successfully transmitted, and other frames were lost during transmission.
  • Slotted ALOHA vulnerable time is half that of pure ALOHA.
  • In slotted ALOHA, throughput can be measured as follows:
    • S = G x e(-G)
    • Slotted ALOHA has maximum throughput S-max = 0.368 when G = 1.

Carrier Sense Multiple Access (CSMA)

CSMA is developed to enhance the performance of the network by reducing the possibility of collisions. In CSMA, the device senses the channel before trying to use it to reduce the possibility of a collision. In Carrier sense protocol, devices listen to a carrier or transmission and act accordingly.

  • CSMA uses the “sense before transmit” or “listen before talk” principle, allowing the device to sense the channel before using it.
  • CSMA minimizes the possibility of collisions but does not provide any guarantee to eliminate it because the propagation delay for sending frames from one device to another may cause collisions on a channel.
  • When a device sends a frame, it takes very little time for the first bit to reach each device and each device to understand it. Simply put, a device can sense the channel and find it idle because the first bit sent by another device has not yet been received.

The diagram below explains the Carrier Sense Multiple Access Protocol.

advertisement
Carrier Sense Multiple Access Protocol
  • As shown in the figure, station B sends the frame at time t1, as it senses the channel and finds it idle.
  • Station-C senses the channel at time t2 and finds it idle because still, it has not received the first bit of Station-B, sent by Station-B on the channel. Now, both the signals will collide on a channel, and the frame destroyed.
  • Here the time required for the propagation of the signal from one end of the channel to the other is known as a propagation or vulnerable time TP.
  • A collision occurs when two devices send a frame at the same time. But if the first bit of the frame reaches the end of the channel, each station receives the first bit of the sending station, so they will not start broadcasting the frame until the station, transmitting the frame, has completed the transmission.

Persistence Methods

We learned that a station broadcasts the frame only after it finds the channel to be idle. But what should a station do if the channel is busy or idle? So, there are three ways to solve these problems.

  1. 1-Persistent method
  2. Non-Persistent method
  3. P-Persistent method

1-Persistent Method: This method is simple and straightforward. In 1-persistent, when the device finds the channel idle, without waiting, it immediately sends its frame with probability 1.

  • In this method, frames are more likely to collide, as more than two devices can find the channel idle and send their frames immediately and simultaneously.

The figure below shows the 1-persistent method.

1-Persistent Method

As shown in the figure, the station continuously senses the channel, as soon as it finds the channel idle, it immediately sends the frame. So there is a high chance of collision in this method.

advertisement

Non-Persistent Method: In this method, a station senses the channel and immediately sends the frame if it finds the channel idle. But if the channel is not idle, it waits for a random amount of time and then starts sensing the channel again.

  • The non-persistence approach minimizes the possibility of a collision because it is rare that two devices will wait and re-transmit the frame simultaneously.
  • This method affects the efficiency of the network as there may be stations to send frames when the channel is idle.

The diagram below explains the non-persistent method.

Non-Persistent Method

As shown in the diagram, the station senses the channel and finds it busy, so it will wait for a random time. After that, it starts sensing the channel, and it immediately sends the frame if it finds the channel idle.

P-Persistent Method: In the p-persistent method, the channel has allocated a time slot for the transmission of frames, and the time slot has a slot duration in which the transmission has to complete. Here, the slot duration can be greater than or equal to the maximum propagation delay.

  • P-persistent improves efficiency and combines the strategies of the above two methods.
  • The station sends a frame with probability p. The station waits for the next time slot to start and senses the channel again with probability q = 1-p. If it finds the channel idle, it sends the frame. Otherwise, it acts as if a collision has occurred and uses the back-off procedure.

The below diagram explains the p-persistent method.

p-persistent method
  • As shown in the figure, the station senses the channel continuously. When the station finds the channel idle, it checks the probability result.
  • If the probability result is greater than the probability p, it waits for a slot and senses the channel again. If it finds the channel busy, it uses the back-off procedure, though a collision occurred. Otherwise, it checks the probability result.
  • If the probability result is less than or equal to p, the station will send the frame.

CSMA with Collision Detection Protocol (CSMA/CD)

CSMA/CD enhances the algorithm to handle collisions during transmission. Detects whether there is a collision on a channel or not. In this method, a device monitors the channel after sending the frame to see if the transmission was successful. The channel shall notify the station in case of collision during transmission.

  • CSMA/CD uses persistence methods to understand the channel. Transmission and collision detection is a continuous process in CSMA/CD.
  • In CSMA/CD, the station transmits and receives frames continuously and simultaneously.
  • The station continuously monitors the channel to see if a broadcast has ended or a collision is detected on a channel. If the collision is not detected, it means that the transmission is complete.
  • The maximum throughput of CSMA/CD depends on the value of G and the persistence methods. Its throughput value is higher than that of Aloha’s two protocols.
  • For the 1-persistent and non-persistent methods, the maximum throughput is approximately 50% (G=1) and 90% (between G=3 and 8), respectively.

The below diagram explains the CSMA/CD method.

CSMA with Collision Detection Protocol
  • As shown in the figure, Station-A has performed its persistence process and starts sending bits of the frame at time t1.
  • Station-C has not yet realized the bit sent by A at the time of t2, so it performs the persistence method and starts sending bits of its frame.
  • The collision on the channel occurs at time t3 when Station-C receives the first bit of Station-A. At time t4, Station-C detects a collision on the channel and aborts transmission.
  • On the other hand, when the first bit of Station-C’s frame collides with Station-A’s frame at time t5, Station-A detects the collision and stops transmission.
  • So, station-A transmits for t5-t1 and station-C for t4-t2.

CSMA/CA: CSMA with Collision Avoidance

In CSMA/CD, when there is a collision on the channel, the station gets to know about it. It receives its own signal when there is no collision and receives its own and another station’s signal when a collision is detected. CSMA/CA was invented to avoid collisions over a wireless channel, as wireless networks cannot detect collisions.

Collision is avoided by using three strategies of CSMA/CA.

  1. Inter-Frame Space (IFS)
  2. Contention Window
  3. Acknowledgments

Inter-Frame System: When a station finds the channel idle, it does not transmit the frame immediately. It waits for some time which is known as inter-frame space or IFS.

  • When the channel is idle after the IFS time, the station sends the frame after waiting for some time, equal to the contention time.
  • IFS is used to define the priority of a station on a channel. For example, a station with a short IFS has the highest priority among all stations.

Contention Window: The content window is the time that comes immediately after IFS. It is divided into smaller time slots to prevent multiple accesses on a single channel between devices. The station ready to send the frame chooses a random number of slots as its waiting time.

  • The content window is first set to one slot, and if the station cannot detect an idle channel after IFS time, the slot in the window is doubled each time.
  • The content window is somehow similar to the P-persistent scheme, but here on a channel, the random outcome defines the total slots occupied by the waiting station.
  • Station senses the channel after each time slot in the content window. If the station finds the channel busy, it does not resume the processing of the content window. It stops the timer and senses the channel. If the station finds the channel idle, it restarts the timer.

Acknowledgments: Collisions can occur on a single channel resulting in loss of frames. So, the receiver uses the acknowledgment to acknowledge to the sender that it has received the frame. The positive acknowledgment and time-out clock guarantee that the receiver has received the frame sent by the sender.

The diagram below explains the CSMA/CA process.

CSMA/CA Protocol
  • As shown in the figure, the channel is sensed by the station before and after IFS. The station also senses the channel during contention time and for each time slot of the contention window.
  • In the idle channel, the timer is continuous. If the channel is busy, the channel timer stops, and the channel continues after the timer becomes idle again.

Key Points to Remember

Here is the list of key points we need to remember about “Random Access Protocols”.

  • In random access, no device is superior to any other device connected to a channel, and no device has control over the other device.
  • The two random access protocols are as follows:
    1. ALOHA
    2. CSMA
  • ALOHA is applicable for systems in which uncoordinated devices are competing for access to a shared channel. There are two types of Aloha methods as follows:
    1. Pure ALOHA
    2. Slotted ALOHA
  • In a pure ALOHA system, devices can transmit data whenever they have data to send. In slotted ALOHA, time is divided into Tfr slots, so the device can only send at the beginning of the time slot.
  • Pure ALOHA has maximum throughput S-max = 0.184 when G = (1/2). Slotted ALOHA has maximum throughput S-max = 0.368 when G = 1.
  • CSMA uses the “sense before transmit” or “listen before talk” principle, allowing the device to sense the channel before using it.
  • What the station will do when the channel is idle or busy can be solved by persistence methods.
    1. 1-Persistent method
    2. Non-Persistent method
    3. P-Persistent method
  • CSMA/CD uses persistence methods to understand the channel. Transmission and collision detection is a continuous process in CSMA/CD.
  • Collision is avoided by using three strategies of CSMA/CA.
    1. Inter-Frame Space (IFS)
    2. Contention Window
    3. Acknowledgments

If you find any mistake above, kindly email to [email protected]

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.