Access Control in Networking-

 

Before you go through this article, make sure that you have gone through the previous article on Access Control.

 

We have discussed-

• Access Control is a mechanism that controls the access of stations to the transmission link.
• Broadcast links require the access control mechanism.
• There are various access control methods-

 

 

1. Time Division Multiplexing
2. Polling
3. CSMA / CD
4. Token Passing
5. Aloha

 

In this article, we will discuss about CSMA / CD.

 

CSMA / CD-

 

CSMA / CD stands for Carrier Sense Multiple Access / Collision Detection.

 

This access control method works as follows-

 

Step-01: Sensing the Carrier-

 

• Any station willing to transmit the data senses the carrier.
• If it finds the carrier free, it starts transmitting its data packet otherwise not.

 

How?

 

• Each station can sense the carrier only at its point of contact with the carrier.
• It is not possible for any station to sense the entire carrier.
• Thus, there is a huge possibility that a station might sense the carrier free even when it is actually not.

 

Example-

 

Consider the following scenario-

 

 

At the current instance,

• If station A senses the carrier at its point of contact, then it will find the carrier free.
• But the carrier is actually not free because station D is already transmitting its data.
• If station A starts transmitting its data now, then it might lead to a collision with the data transmitted by station D.

 

Step-02: Detecting the Collision-

 

In CSMA / CD,

• It is the responsibility of the transmitting station to detect the collision.
• For detecting the collision, CSMA / CD implements the following condition.
• This condition is followed by each station-

 

Transmission delay >= 2 x Propagation delay

 

Meaning-

 

According to this condition,

• Each station must transmit the data packet of size whose transmission delay is at least twice its propagation delay.
• If the size of data packet is smaller, then collision detection would not be possible.

 

Length Of Data Packet-

 

We know-

• Transmission delay = Length of data packet (L) / Bandwidth (B)
• Propagation delay = Distance between the two stations (D) / Propagation speed (V)

 

Substituting values in the above condition, we get-

 L / B >= 2 x D / V

Thus,

 

L >= 2 x B x D / V

 

Understanding the Condition To Detect Collision With Example   Consider at time 10:00 am, station A senses the carrier. It finds the carrier free and starts transmitting its data packet to station D. Let the propagation delay be 1 hour. (We are considering station D for the worst case)     Let us consider the scenario at time 10:59:59:59 when the packet is about to reach the station D. At this time, station D senses the carrier. It finds the carrier free and starts transmitting its data packet. Now, as soon as station D starts transmitting its data packet, a collision occurs with the data packet of station A at time 11:00 am.     After collision occurs, the collided signal starts travelling in the backward direction. The collided signal takes 1 hour to reach the station A after the collision has occurred. For station A to detect the collided signal, it must be still transmitting the data. So, transmission delay of station A must be >= 1 hour + 1 hour >= 2 hours to detect the collision. That is why, for detecting the collision, condition is Tt >= 2Tp.

 

Two cases are possible-

 

Case-01:

 

If no collided signal comes back during the transmission,

• It indicates that no collision has occurred.
• The data packet is transmitted successfully.

 

Case-02:

 

If the collided signal comes back during the transmission,

• It indicates that the collision has occurred.
• The data packet is not transmitted successfully.
• Step-03 is followed.

 

Step-03: Releasing Jam Signal-

 

• Jam signal is a 48 bit signal.
• It is released by the transmitting stations as soon as they detect a collision.
• It alerts the other stations not to transmit their data immediately after the collision.
• Otherwise, there is a possibility of collision again with the same data packet.
• Ethernet sends the jam signal at a frequency other than the frequency of data signals.
• This ensures that jam signal does not collide with the data signals undergone collision.

 

Step-04: Waiting For Back Off Time-

 

• After the collision, the transmitting station waits for some random amount of time called as back off time.
• After back off time, it tries transmitting the data packet again.
• If again the collision occurs, then station again waits for some random back off time and then tries again.
• The station keeps trying until the back off time reaches its limit.
• After the limit is reached, station aborts the transmission.
• Back off time is calculated using Back Off Algorithm.

 

CSMA / CD Flowchart-

 

The following CSMA / CD flowchart represents the CSMA / CD procedure-

 

Efficiency-

 

Efficiency (η) = Useful Time / Total Time

 

Before a successful transmission,

• There may occur many number of collisions.
• 2 x T_p time is wasted during each collision.

 

Thus,

• Useful time = Transmission delay of data packet = T_t
• Useless time = Time wasted during collisions + Propagation delay of data packet = c x 2 x T_p + T_p
• Here, c = Number of contention slots / collision slots.

 

Thus,

 

 

Here,

• c is a variable.
• This is because number of collisions that might occur before a successful transmission are variable.

 

Probabilistic Analysis shows-

 

Average number of collisions before a successful transmission = e

 

Substituting c = e in the above relation, we get-

 

 

Probabilistic Analysis-

 

Let us perform the probabilistic analysis to find the average number of collisions before a successful transmission.

 

Consider-

• Number of stations connected to a CSMA / CD network = n
• Probability of each station to transmit the data = p

 

 

Transmission will be successful only when-

• One station transmits the data
• Other (n-1) stations do not transmit the data.

 

Thus, Probability of successful transmission is given by-

 

 

Now, let us find the maximum value of P_{successful transmission}.

For maximum value, we put-

 

 

On solving,

 

At p = 1/n, we get the maximum value of Psuccessful transmission

 

Thus,

(P_{successful transmission})_max

= ⁿC₁ x 1/n x (1 – 1/n)^n-1

= n x 1/n x (1 – 1/n)^n-1

= (1 – 1/n)^n-1

 

(Psuccessful transmission)max = (1 – 1/n)n-1

 

If there are sufficiently large number of stations i.e. n → ∞, then we have-

 

 

Number of times a station must try before successfully transmitting the data packet

= 1 / P_max         (Using Poisson’s distribution)

= 1 / (1/e)

= e

 

From here, we conclude-

Average number of collisions that might occur before a successful transmission = e

 

Important Notes-

 

Note-01:

 

• CSMA / CD is used in wired LANs.
• CSMA / CD is standardized in IEEE 802.3

 

Note-02:

 

• CSMA / CD only minimizes the recovery time.
• It does not take any steps to prevent the collision until it has taken place.

 

Important Formulas-

 

• Condition to detect collision: Transmission delay >= 2 x Propagation delay
• Minimum length of data packets in CSMA / CD = 2 x Bandwidth x Distance / Speed
• Efficiency of CSMA / CD = 1 / (1 + 6.44 x a) where a = T_p / T_t
• Probability of successful transmission = ⁿC₁ x p x (1-p)^n-1
• Average number of collisions before a successful transmission = e

 

To gain better understanding about CSMA / CD,

Watch this Video Lecture

 

Next Article- Binary Exponential Back Off Algorithm

 

Get more notes and other study material of Computer Networks.

Watch video lectures by visiting our YouTube channel LearnVidFun.