Chapter 4

Multiple Access Techniques II

In random access technique, there is no coordination among the stations that want to send frame
over a transmission medium. Each station devises its own strategies to send its frames with an aim
to reduce the collision as much as possible. The term collision means the situation in which two
stations transmit over a transmission medium simultaneously, thereby resulting in an unsuccessful
transmission for both stations. Higher rate of collisions causes lower throughput. Next, different
categories of random-access technique will be discussed.

4.1 ALOHA
ALOHA is the earliest random-access technique. Due to its simplicity, it is still being used in
wireless networks. In ALOHA, whenever a station has data to send, it sends it. It does not care
whether the transmission medium is currently being used by others or the medium is free now to
use. However, it waits for a pre-specified time which is equal to twice the propagation time to get
an acknowledgement (ACK) from the receiver to be sure that the frame is successfully received
by the destination. If the frame cannot reach the destination within the specified time, this indicates
a collision among the signals sent by different stations. In this case, the sender sends its frame
again. The flow chart of the operation of ALOHA is given in Fig. 4.1.

Figure 4.1 Flow chart of ALOHA

ALOHA has a second method to prevent congesting the channel with retransmitted frames. After
a maximum number of retransmission attempts 𝐾𝑚𝑎𝑥 , a station must give up and try later. Fig. 4.1
shows the procedure for pure ALOHA based on the above strategy. The time-out period is equal
to the maximum possible round-trip propagation delay, which is twice the amount of time required
to send a frame between the two most widely separated stations (2 × 𝑇p ). The backoff time 𝑇B is a
random value that normally depends on K (the number of attempted unsuccessful transmissions).
The formula for 𝑇𝐵 depends on the implementation. One common formula is the binary
exponential backoff. In this method, for each retransmission, a multiplier R = 0 to 2K - 1 is
randomly chosen and multiplied by 𝑇𝑝 (maximum propagation time) or 𝑇fr (the average time
required to send out a frame) to find 𝑇𝐵 . Note that in this procedure, the range of the random
numbers increases after each collision. The value of 𝐾𝑚𝑎𝑥 is usually chosen as 15.

A collision occurs when frames from two or more stations are on the transmission medium
at the same time. Fig. 4.2 shows the scenarios when collision can occur. There are three stations
which share the transmission medium. At the beginning, only Station 1 sends its frame; so there is
no collision. Then, only Station 2 sends its frame; hence there is no collision. Then, we see both
Station 1 and Station 3 send their frames (frames 1.2 and 3.1) at the same time, which results in a
complete overlap of the frames, thereby causing a collision. Thereafter, we see Station 1 and 2
starts sending frames (1.2 and 2.2) in different times. Still there is a collision between end of frame
1.2 and start of 2.2. This is a partial collision.

Figure 4.2 Collision in ALOHA

Throughput is the amount of data a sender can successfully send to the receiver. It can be
defined as the product of the average number of frames that are sent and the probability of
succeeding a frame to reach its destination. That is, higher success rate ensures better throughput.
Thus, the throughput S can be formulated as
𝑆 = 𝐺𝑃 (1)
Where G and P are the average number of frames and the probability of a successful
transmission. Consider a packet scheduled for transmission at some time ‘t’. This packet will be
successful if no other packet is scheduled for transmission in the interval (t-T, t+T) (this period of
2T is called the vulnerable period). The probability of this happening, that is, the probability of
success, is that no packet is scheduled in an interval of length 2T.
 Let us find the vulnerable time, the length of time in which there is a possibility of collision.
We assume that the stations send fixed-length frames with each frame taking 𝑡𝑓𝑟 seconds to send.
Figure 4.3 shows the vulnerable time for station B. Station B starts to send a frame at time t. Now
imagine station A has started to send its frame after t -𝑡𝑓𝑟 . This leads to a collision between the
frames from station B and station A. On the other hand, suppose that station C starts to send a
frame before time t + 𝑡𝑓𝑟 . Here, there is also a collision between frames from station B and station
C. Looking at Fig. 3, we see that the vulnerable time during which a collision may occur in pure
ALOHA is 2 times the frame transmission time.

Figure 4.3 Vulnerable time of

ALOHA
Next we will derive the maximum throughput that can be achieved using ALOHA.
Using Poisson distribution, Probability of generating ‘k’ interfering frames (when average
number of frames = G) is,
P (k) = ( 𝑮𝒌 . 𝒆−𝑮 ) / k! (2)
The vulnerability of pure ALOHA is 2 time frames. For the time duration of two time frames
on an average 2G frames are produced. Thus, probability that no other traffic is initiated in this
duration (2T) (hence k = 0) is, that is probability of successful transmission without interference
can be obtained by putting k = 0 in Eq. (2)
P (0) = ((2𝐺)0 *𝑒 −2𝐺 ) / 0!
P = 𝑒 −2𝐺
Putting the value of P in Eq. 1, we get,
S = G𝒆−𝟐𝑮 (3)
We see that throughput S depends on occurrence of frames/frame time, G, to get maximum
throughput, we differentiate the throughput (Eq. 3) with respect to G.
𝑑𝑆
= 𝑒 −2𝐺 + G*(-2) 𝑒 −2𝐺
𝑑𝐺

For maxima, above equation is to be equated to zero. Therefore,

0 = 𝑒 −2𝐺 + G*(-2) 𝑒 −2𝐺
 1
𝐺=
2

Putting the value of G in Eq. 3, we get

S=e/2
This is the maximum throughput of ALOHA technique.

4.2 CSMA
To minimize the chance of collision and, therefore, increase the performance, the CSMA method
was developed. The chance of collision can be reduced if a station senses the medium before trying
to use it. Carrier sense multiple access (CSMA) requires that each station first listen to the
medium (or check the state of the medium) before sending. In other words, CSMA is based on the
principle “sense before transmit” or “listen before talk.” If a station finds the medium free, it sends
its frame; otherwise it continue to sense the channel to get it free. The flow chart of CSMA is given
in Fig. 4.4.

Figure 4.4 Flow chart of CSMA

What should a station do if the channel is busy? What should a station do if the channel is
idle? Three methods have been devised to answer these questions: the 1-persistent method, the
nonpersistent method, and the p-persistent method.

Figure 4.5 Carrier sense in 1-persistent Figure 4.6 Flow chart of 1-persistent

1-Persistent
The 1-persistent method is simple and straightforward. In this method, after the station finds the
line idle, it sends its frame immediately (with probability 1). This method has the highest chance
of collision because two or more stations may find the line idle and send their frames immediately.
Fig. 4.5 and 4.6 shows the carrier sense procedure and flow chart of 1-persistent techniques,
respectively.

Figure 4.7 Carrier sense in nonpersistent Figure 4.8 Flow chart of nonpersistent

Nonpersistent
In the nonpersistent method, a station that has a frame to send senses the line. If the line is idle, it
sends immediately. If the line is not idle, it waits a random amount of time and then senses the line
again. The nonpersistent approach reduces the chance of collision because it is unlikely that two
or more stations will wait the same amount of time and retry to send simultaneously. However,
this method reduces the efficiency of the network because the medium remains idle when there
may be stations with frames to send. Fig. 4.7 and 4.8 shows the carrier sense procedure and flow
chart of nonpersistent techniques, respectively.

Figure 4.9 Carrier sense in p- Figure 4.10 Flow chart of p-persistent

persistent
p-Persistent
The p-persistent method is used if the channel has time slots with a slot duration equal to or greater
than the maximum propagation time. The p-persistent approach combines the advantages of the
other two strategies. It reduces the chance of collision and improves efficiency. Fig. 4.9 and 4.10
shows the carrier sense procedure and flow chart of p-persistent techniques, respectively.
In this method, after the station finds the line idle it follows these steps:
1. With probability p, the station sends its frame.
2. With probability q = 1 - p, the station waits for the beginning of the next time slot
and checks the line again.
a. If the line is idle, it goes to step 1.
 b. If the line is busy, it acts as though a collision has occurred and uses the backoff
procedure.

4.3 CSMA/CD
The CSMA method does not specify the procedure following a collision. Carrier sense multiple
access with collision detection (CSMA/CD) augments the algorithm to handle the collision. In
this method, a station monitors the medium after 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. In
other words, the station that sends its data on the channel, continues to sense the channel even after
data transmission (see Fig. 4.11). If collision is detected, the station aborts its transmission and
waits for a random amount of time & sends its data again. As soon as a collision is detected, the
transmitting station release a jam signal. Jam signal alerts other stations. Stations are not supposed
to transmit immediately after the collision has occurred.

Figure 4.11 Flow chart of CSMA/CD

4.4 CSMA/CA
Carrier sense multiple access with collision avoidance (CSMA/CA) was invented for wireless
networks. In wireless networks, the collision detection is not possible due to the characteristics of
wireless signal propagation.

Figure 4.12 Illustration of difficulties in collision detection in wireless networks

Why do we need CSMA/CA?
Consider Fig. 12(a), where the station B transmits to station A. When a signal propagates, it
becomes weaker as it travels distance. Thus, the signal transmitted by station B remains strong
enough to be detected by A. So the communication is successful. However, as the signal of B
travels longer distance to reach station C, it becomes so weaker that station C cannot detect the
signal; hence station C assumes that there is no transmission in the designated band of frequency.
So, it also transmits in the same frequency. The same signal can be received by station A, but
remains undetectable in station B due the loss of signal strength after traveling longer distance.
Thus, A receives signals from A and B in the same frequency, which results in an interfering signal
and is unusable. On the other hand, B cannot detect the transmission of C and vise-versa. This is
a reason for which collision cannot be detection in wireless transmission.
Now consider the scenario given in Fig. 12(b). Both stations B and C are transmitting on the
same frequency band to A. However, there is a thick barrier (it can be a wall or hill) between B
and C. So the signal transmitted by C does not reach B as the microwave frequency cannot
penetrate the thick barrier. Similarly, C does not receive any signal from B, hence it remains
unaware about the B’s transmission on the same frequency band. For this reason, they cannot
detect the collision of signals that takes place in station A. Due to the mixing of signals, A cannot
receive any usable signal, which results in an unsuccessful transmission.

CSMA/CA Principle
In CSMA/CA, a station first sense the transmission medium to see whether it is free to send any
frame (see Fig. 4.13). If it finds busy, it continues to sense. However, it finds it free, it will wait a
random time duration. Since two different station may find the medium free at the same time, the
waiting of the random time duration reduces the probability of sending data by the both stations at
the same time. Since the waiting time is random, it is highly probable that the two stations wait for
different duration. The station whose time expires first sense the medium again, if it finds it free
now, it will send its data; otherwise, it starts sensing the medium again. The twice times sensing
and the random waiting greatly reduces the collision probability.
CSMA/CA uses three strategies to avoid collision: the interframe space, the contention
window, and acknowledgments

Figure 4.13 Flow chart of CSMA/CA

Interframe Space (IFS). First, collisions are avoided by deferring transmission even if the channel
is found idle. When an idle channel is found, the station does not send immediately. It waits for a
period of time called the interframe space or IFS. Even though the channel may appear idle when
it is sensed, a distant station may have already started transmitting. The distant station’s signal has
not yet reached this station. The IFS time allows the front of the transmitted signal by the distant
station to reach this station. After waiting an IFS time, if the channel is still idle, the station can
send, but it still needs to wait a time equal to the contention window (see Fig. 4.14).
Contention Window. The contention window is an amount of time divided into slots. A station
that is ready to send chooses a random number of slots as its wait time. The number of slots in the
window changes according to the binary exponential backoff strategy. This means that it is set to
one slot the first time and then doubles each time the station cannot detect an idle channel after the
IFS time (see Fig. 4.14). This is very similar to the p-persistent method except that a random
outcome defines the number of slots taken by the waiting station. One interesting point about the
contention window is that the station needs to sense the channel after each time slot. However, if
the station finds the channel busy, it does not restart the process; it just stops the timer and restarts
it when the channel is sensed as idle.

Figure 4.14 Carrier sense in contention window

Acknowledgment. With all these precautions, there still may be a collision resulting in destroyed
data. In addition, the data may be corrupted during the transmission. The positive acknowledgment
and the time-out timer can help guarantee that the receiver has received the frame.