Random Access Protocols
Methods where no station is superior to another.
Context
In the Multiple-Access Protocols taxonomy (introduced in the previous module),Random Access is the first branch. These protocols are also known asContention Methods because stations compete to access the medium.
Key Concepts
Random Transmission
There is no scheduled time for a station to transmit. Transmission is truly random among the stations.
Contention & Collision
No rules specify which station should send next. Stations compete with one another. If two stations send at the same time, a Collision occurs, and frames may be destroyed.
Pure ALOHA
The original ALOHA protocol. It is simple but elegant. The idea is that each station sends a frame whenever it has a frame to send. However, since there is only one channel to share, there is the possibility of collision between frames from different stations.
Procedure
Vulnerable Time
We assume that stations send fixed-length frames taking Tfr to send.
If Station A sends at time t:
- Station B could have started at t - Tfr (its end collides with A's start).
- Station C could start at t + Tfr (its start collides with A's end).
Throughput / Efficiency
The throughput for Pure ALOHA is the probability that a frame is successfully transmitted.
Let G be the average number of frames generated by the system during one frame transmission time.
Slotted ALOHA
Slotted ALOHA was invented to improve the efficiency of Pure ALOHA. In this method, the time is divided into discrete intervals called slots of length Tfr.
Rule: A station is allowed to send only at the beginning of a time slot. If a station misses the beginning is must wait for the next slot.
Vulnerable Time
Because a station is only allowed to send at the beginning of a synchronized slot, if a station starts sending, it is the only one in that slot (unless another station also starts at the exact same slot start).
The vulnerable time is reduced to exactly one frame transmission time.
Throughput / Efficiency
With the vulnerable time halved, the probability of collision is reduced.
Carrier Sense Multiple Access (CSMA)
To minimize the chance of collision and increase performance, CSMA was developed. The chance of collision can be reduced if a station senses the medium before trying to use it.
Rule: "Sense before transmit" or "Listen before talk".
Why Collisions Still Occur?
Even though stations listen before talking, collisions still occur because of Propagation Delay. When a station sends a frame, it takes time for the first bit to reach every other station.
The "Blind" Transmission Problem
Once a station starts sending data, it stops sensing the medium. It assumes the channel is clear once transmission begins.
- The station is unaware that a collision has occurred during its transmission.
- The only way it realizes the failure is when it does not receive an ACK (Acknowledgment) within the time-out period.
- This inefficiency leads to wasted bandwidth as the station continues transmitting a corrupted frame.
Vulnerable Time
The vulnerable time for CSMA is the propagation time Tp.
This is the time needed for a signal to propagate from one end of the medium to the other.
- If a station sends a frame, and any other station starts sending before the first bit reaches the end of the medium, a collision occurs.
- Once the first bit reaches the end of the medium, every station hears it and refrains from sending.
Real-World Analogy: The River & The Dam
Imagine a dry riverbed where villagers (stations) often go down to play or work because there's no water.
Upstream, there is a large dam. When the dam opens, water releases into the riverbed.
The dam opens (Transmitter starts), but the water hasn't reached the village yet (Propagation Delay). The villagers see a dry bed and think it's safe to enter.
They enter the riverbed right before the water wall hits them. They were unaware of the danger because the information (water) hadn't propagated to their location yet.
Once the water finally reaches the village, no one enters the riverbed anymore because they can see the danger.
Persistence Strategies
When a station senses the line, there are different strategies it can follow based on the state of the channel (Idle or Busy). These strategies determine the behavior of the CSMA protocol.
1-Persistent
Used in CSMA/CD (Ethernet)
Non-Persistent
Better capacity utilization
P-Persistent
Used in CSMA/CA (WiFi) - Updated
CSMA/CD (Carrier Sense Multiple Access with Collision Detection)
Concept & Operation
In this method, a station monitors the medium while it sends a frame to see if the transmission was successful. If so, the station is finished. If, however, there is a collision, the frame is sent again.
Key Difference from CSMA: The station does not stop sensing after it starts transmitting. It continues to listen for collisions.
Minimum Frame Size Constraint
For CSMA/CD to work, we need a restriction on the minimum frame size. Before sending the last bit of the frame, the sending station must detect a collision, if any, and abort the transmission.
This is because once the entire frame is sent, the station stops monitoring the line. Therefore, the frame transmission time ( $T_{fr}$) must be at least two times the maximum propagation time ($T_p$).
Worst-Case Scenario
Media Suitability
Wired Networks (Good)
CSMA/CD works well in wired connections (like Ethernet) because the signal strength is consistent, making it easy to detect collisions (voltage spikes).
Wireless Networks (Bad)
Not effective for wireless. Received signals are much weaker than transmitted ones (attenuation), so a station cannot "hear" a collision while it is "shouting" (transmitting).
Issues like the "Hidden Terminal Problem" also make detection impossible.
CSMA/CA (Carrier Sense Multiple Access with Collision Avoidance)
Why Collision Avoidance?
In wireless networks, collisions are hard to detect because the transmitted energy is much higher than the received signal (which fades over distance). A collision might add only 5-10% extra energy, which is negligible.
Therefore, we use Collision Avoidance (CSMA/CA) instead of detection.
Three Strategies
- 1Interframe Space (IFS)A brief pause after finding the channel idle. It allows higher priority stations to transmit first.
- 2Contention WindowA random wait time (in slots) to reduce collision probability if multiple stations are waiting.
- 3Acknowledgment (ACK)Positive confirmation of receipt. If no ACK is received, the data is assumed lost.