In the previous tutorial, we have studied about TDM and polling. Now, we will learn about CSMA/CD in this tutorial. We will also learn about back off algorithm used in CSMA/CD.

What is CSMA/CD?

CSMA/CD stands for carrier sense multiple access with Collision detection.

Let’s say we have a multiple stations connected to a LAN. Now, when one station wants to transmit a frame, it checks if the medium is free. Note that absence of any current (or the presence of residual background current) tells that no one else is transmitting the data. If the medium is free, the station starts transmitting the data. It also monitors the current level to detect any collision. If it detects a collision, it stops transmitting that frame and transmits a jam signal to inform all other stations about the collision. Then, the station waits for a random time interval before retrying to send the frame.

CSMA/CD

Problems

– Standing at one point station cannot sense if the entire channel is free.
– There is no acknowledgement for the collisions.

Collision detection

– Sender should detect collisions if any.

CSMA/CD Collision

– When A and B see this collision signal, they think that whichever collision signal is coming back doesn’t correspond to our data. This could be someone else’s data.

– A will know that it’s packet was involved in collision only if it is still transmitting and it gets a collision signal i.e. if packet is large enough that by the time collision comes back there is still some data to transmit. Similar situation lies for B.

Thus, worst case time for a station to detect collision is ${TT >= {2*{TP}}$.

Question 1

What should be the length of data to detect collision?

Solution
TT >= 2*TP
L/B >= 2*TP
L>= 2*TP*B

– Efficiency of CSMA/CD= $( \frac {TT}{c*2*{TP} + TT + TP} )$
Where, c = no. of collisions
On further calculation it was found out to be =$( \frac {1}{1+6.44 a} )$
        – Where $a = ( \frac {TT}{TP} ) $
        – CSMA/CD is suitable only for LANs and not WANs.

Back off Algorithm for CSMA/CD

CSMA/CD backoff

Let us assume that A and B start transmitting data and collision occurs. Now, A and B know that there is a collision and they stop transmitting.

Now, question is
When should A and B again start transmission?

Solution:
Soon after the collision is detected retransmission is done.
– If another collision occurs, A and B retransmit again. Thus, we need an algorithm to check that after collision A and B don’t start retransmitting at the same time. We use back off algorithm for this purpose.

What is Back off Algorithm?

It uses waiting time i.e. if a station is involved in retransmission, time after which it will start retransmitting again. This waiting time is called back off time.

Back Off Algorithm Diagram

– Time slots are set in such a way that even if B tries to send after waiting time it will check if the carrier is free.

Question 1.

What is the probability of A or B winning after the first collision?
Answer –
P(A) = ¼
P(B) = ¼

Probability of another collision given that first collision has already occurred: 2/4

Disadvantage of Back off Algorithm

Capture Effect: If a host wins a collision for the first time, it’s probability of winning after next collision increases.

That was all about CSMA/CD and the back off algorithm. In our next tutorial, we will study about token passing
[latexpage]