CSMA CD Protocol | CSMA CD Flowchart

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 Tp time is wasted during each collision.

 

Thus,

  • Useful time = Transmission delay of data packet = Tt
  • Useless time = Time wasted during collisions + Propagation delay of data packet = c x 2 x Tp + Tp
  • 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 Psuccessful transmission.

For maximum value, we put-

 

 

On solving,

 

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

 

Thus,

(Psuccessful transmission)max

= nC1 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 / Pmax         (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 = Tp / Tt
  • Probability of successful transmission = nC1 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.

Summary
CSMA CD Protocol | CSMA CD Flowchart
Article Name
CSMA CD Protocol | CSMA CD Flowchart
Description
CSMA / CD protocol stands for Carrier Sense Multiple Access / Collision Detection. CSMA / CD in computer networks is an access control method. CSMA / CD allows the stations to sense the carrier and send the data if it is free.
Author
Publisher Name
Gate Vidyalay
Publisher Logo
Liked this article? Share it with your friends and classmates now-