CSMA CD Flowchart | Gate Vidyalay

Tag: CSMA CD Flowchart

CSMA CD | BackOff Algorithm | Problems

CSMA / CD Protocol-

Before you go through this article, make sure that you have gone through the previous article on CSMA / CD Protocol.

We have discussed-

CSMA / CD allows a station to transmit data if it senses the carrier free.
After undergoing collision, station waits for random back off time before transmitting again.
Back Off Algorithm is used to calculate back off time.

Also Read- Back Off Algorithm

In this article, we will discuss practice problems based on CSMA / CD and Back Off Algorithm.

PRACTICE PROBLEMS BASED ON CSMA / CD AND BACK OFF ALGORITHM-

Problem-01:

After the k^th consecutive collision, each colliding station waits for a random time chosen from the interval-

(0 to 2^k) x RTT
(0 to 2^k-1) x RTT
(0 to 2^k-1) x Maximum Propagation delay
(0 to 2^k-1) x Maximum Propagation delay

Solution-

Clearly, Option (B) is correct.

Problem-02:

In a CSMA / CD network running at 1 Gbps over 1 km cable with no repeaters, the signal speed in the cable is 200000 km/sec. What is minimum frame size?

Solution-

Given-

Bandwidth = 1 Gbps
Distance = 1 km
Speed = 200000 km/sec

Calculating Propagation Delay-

Propagation delay (T_p)

= Distance / Propagation speed

= 1 km / (200000 km/sec)

= 0.5 x 10^-5 sec

= 5 x 10^-6 sec

Calculating Minimum Frame Size-

Minimum frame size

= 2 x Propagation delay x Bandwidth

= 2 x 5 x 10^-6 sec x 10⁹ bits per sec

= 10000 bits

Problem-03:

A 2 km long broadcast LAN has 10⁷ bps bandwidth and uses CSMA / CD. The signal travels along the wire at 2 x 10⁸ m/sec. What is the minimum packet size that can be used on this network?

50 B
100 B
200 B
None of the above

Solution-

Given-

Distance = 2 km
Bandwidth = 10⁷ bps
Speed = 2 x 10⁸ m/sec

Calculating Propagation Delay-

Propagation delay (T_p)

= Distance / Propagation speed

= 2 km / (2 x 10⁸ m/sec)

= 2 x 10³ m / (2 x 10⁸ m/sec)

= 10^-5 sec

Calculating Minimum Frame Size-

Minimum frame size

= 2 x Propagation delay x Bandwidth

= 2 x 10^-5 sec x 10⁷ bits per sec

= 200 bits or 25 bytes

Thus, Option (D) is correct.

Problem-04:

A and B are the only two stations on Ethernet. Each has a steady queue of frames to send. Both A and B attempts to transmit a frame, collide and A wins first back off race. At the end of this successful transmission by A, both A and B attempt to transmit and collide. The probability that A wins the second back off race is ___ .

0.5
0.625
0.75
1.0

Solution-

According to question, we have-

1st Transmission Attempt-

Both the stations A and B attempts to transmit a frame.
A collision occurs.
Back Off Algorithm runs.
Station A wins and successfully transmits its 1^st data packet.

2nd Transmission Attempt-

Station A attempts to transmit its 2^nd data packet.
Station B attempts to retransmit its 1^st data packet.
A collision occurs.

Now,

We have been asked the probability of station A to transmit its 2^nd data packet successfully after 2^nd collision.
After the 2^nd collision occurs, we have-

At Station A-

2^nd data packet of station A undergoes collision for the 1^st time.
So, collision number for the 2^nd data packet of station A = 1.
Now, station A randomly chooses a number from the range [0,2¹-1] = [0,1].
Then, station A waits for back off time and then attempts to retransmit its data packet.

At Station B-

1^st data packet of station B undergoes collision for the 2^nd time.
So, collision number for the 1^st data packet of station B = 2.
Now, station B randomly chooses a number from the range [0,2²-1] = [0,3].
Then, station B waits for back off time and then attempts to retransmit its data packet.

Following 8 cases are possible-

Station A	Station B	Remark
0	0	Collision
0	1	A wins
0	2	A wins
0	3	A wins
1	0	B wins
1	1	Collision
1	2	A wins
1	3	A wins

From here,

Probability of A winning the 2^nd back off race = 5 / 8 = 0.625.
Thus, Option (B) is correct.

Problem-05:

Suppose nodes A and B are on same 10 Mbps Ethernet segment and the propagation delay between two nodes is 225 bit times. Suppose A and B send frames at t=0, the frames collide then at what time, they finish transmitting a jam signal. Assume a 48 bit jam signal.

Solution-

Propagation delay (T_p)

= 225 bit times

= 225 bit / 10 Mbps

= 22.5 x 10^-6 sec

= 22.5 μsec

At t = 0,

Nodes A and B start transmitting their frame.
Since both the stations start simultaneously, so collision occurs at the mid way.
Time after which collision occurs = Half of propagation delay.
So, time after which collision occurs = 22.5 μsec / 2 = 11.25 μsec.

At t = 11.25 μsec,

After collision occurs at t = 11.25 μsec, collided signals start travelling back.
Collided signals reach the respective nodes after time = Half of propagation delay
Collided signals reach the respective nodes after time = 22.5 μsec / 2 = 11.25 μsec.
Thus, at t = 22.5 μsec, collided signals reach the respective nodes.

At t = 22.5 μsec,

As soon as nodes discover the collision, they immediately release the jam signal.
Time taken to finish transmitting the jam signal = 48 bit time = 48 bits/ 10 Mbps = 4.8 μsec.

Thus,

Time at which the jam signal is completely transmitted

= 22.5 μsec + 4.8 μsec

= 27.3 μsec or 273 bit times

Problem-06:

Suppose nodes A and B are attached to opposite ends of the cable with propagation delay of 12.5 ms. Both nodes attempt to transmit at t=0. Frames collide and after first collision, A draws k=0 and B draws k=1 in the exponential back off protocol. Ignore the jam signal. At what time (in seconds), is A’s packet completely delivered at B if bandwidth of the link is 10 Mbps and packet size is 1000 bits.

Solution-

Given-

Propagation delay = 12.5 ms
Bandwidth = 10 Mbps
Packet size = 1000 bits

Time At Which Collision Occurs-

Collision occurs at the mid way after time

= Half of Propagation delay

= 12.5 ms / 2

= 6.25 ms

Thus, collision occurs at time t = 6.25 ms.

Time At Which Collision is Discovered-

Collision is discovered in the time it takes the collided signals to reach the nodes

= Half of Propagation delay

= 12.5 ms / 2

= 6.25 ms

Thus, collision is discovered at time t = 6.25 ms + 6.25 ms = 12.5 ms.

Scene After Collision-

After the collision is discovered,

Both the nodes wait for some random back off time.
A chooses k=0 and then waits for back off time = 0 x 25 ms = 0 ms.
B chooses k=1 and then waits for back off time = 1 x 25 ms = 25 ms.
From here, A begins retransmission immediately while B waits for 25 ms.

Waiting Time For A-

After winning the back off race, node A gets the authority to retransmit immediately.
But node A does not retransmit immediately.
It waits for the channel to clear from the last bit aborted by it on discovering the collision.
Time taken by the last bit to get off the channel = Propagation delay = 12.5 ms.
So, node A waits for time = 12.5 ms and then starts the retransmission.
Thus, node A starts the retransmission at time t = 12.5 ms + 12.5 ms = 25 ms.

Time Taken in Delivering Packet To Node B-

Time taken to deliver the packet to node B

= Transmission delay + Propagation delay

= (1000 bits / 10 Mbps) + 12.5 ms

= 100 μs + 12.5 ms

= 0.1 ms + 12.5 ms

= 12.6 ms

Thus, At time t = 25 ms + 12.6 ms = 37.6 ms, the packet is delivered to node B.

Problem-07:

The network consists of 4 hosts distributed as shown below-

Assume this network uses CSMA / CD and signal travels with a speed of 3 x 10⁵ km/sec. If sender sends at 1 Mbps, what could be the minimum size of the packet?

600 bits
400 bits
6000 bits
1500 bits

Solution-

CSMA / CD is a Access Control Method.
It is used to provide the access to stations to a broadcast link.
In the given network, all the links are point to point.
So, there is actually no need of implementing CSMA / CD.
Stations can transmit whenever they want to transmit.

In CSMA / CD,

The condition to detect collision is-

Packet size >= 2 x (distance / speed) x Bandwidth

To solve the question,

We assume that a packet of same length has to be used in the entire network.
To get the minimum length of the packet, what distance we should choose?
To get the minimum length of the packet, we should choose the minimum distance.
But, then collision would be detected only in the links having distance less than or equal to that minimum distance.
For the links, having distance greater than the minimum distance, collision would not be detected.
So, we choose the maximum distance so that collision can be detected in all the links of the network.

So, we use the values-

Distance = 90 km
Speed = 3 x 10⁵ km/sec
Bandwidth = 1 Mbps

Substituting these values, we get-

Minimum size of data packet

= 2 x (90 km / 3 x 10⁵ km per sec) x 1 Mbps

= 2 x 30 x 10^-5 sec x 10⁶ bits per sec

= 600 bits

Thus, Option (A) is correct.

Next Article- Token Passing | Access Control Method

Get more notes and other study material of Computer Networks.

Watch video lectures by visiting our YouTube channel LearnVidFun.

Binary Exponential BackOff Algorithm | CSMA CD

Computer Networks

CSMA / CD Protocol-

Before you go through this article, make sure that you have gone through the previous article on CSMA / CD Protocol.

We have discussed-

CSMA / CD stands for Carrier Sense Multiple Access / Collision Detection.
It allows the stations to sense the carrier and transmit data if the carrier is free.

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

Back Off Time-

In CSMA / CD protocol,

After the occurrence of collision, station waits for some random back off time and then retransmits.
This waiting time for which the station waits before retransmitting the data is called as back off time.
Back Off Algorithm is used for calculating the back off time.

Back Off Algorithm-

After undergoing the collision,

Transmitting station chooses a random number in the range [0, 2ⁿ-1] if the packet is undergoing collision for the n^th time.
If station chooses a number k, then-

Back off time = k x Time slot

where value of one time slot = 1 RTT

Example-

Consider the following scenario where stations A and D start transmitting their data simultaneously-

For simplicity,

We consider the value of time slot = 1 unit.
Thus, back off time = K units.

Scene-01: For 1st Data Packet Of Both Stations-

Both the stations start transmitting their 1^st data packet simultaneously.
This leads to a collision.
Clearly, the collision on both the packets is occurring for the 1^st time.
So, collision number for the 1^st data packet of both the stations = 1.

At Station A-

After detecting the collision,

Station A randomly chooses a number in the range [0, 2¹-1] = [0,1].
If station A chooses the number K_A, then back off time = K_A units.

At Station D-

After detecting the collision,

Station D randomly chooses a number in the range [0, 2¹-1] = [0,1].
If station D chooses the number K_D, then back off time = K_D units.

Following 4 cases are possible-

K_A	K_D	Remarks
0	0	In this case, both the stations start retransmitting their data immediately. This case leads to a collision again.
0	1	In this case, station A starts retransmitting its data immediately while station D waits for 1 unit of time. This case leads to A successfully retransmitting its data after the 1^st collision.
1	0	In this case, station A waits for 1 unit of time while station D starts retransmitting its data immediately. This case leads to D successfully retransmitting its data after the 1^st collision.
1	1	In this case, both the stations wait for 1 unit of time and then starts retransmitting their data simultaneously. This case leads to a collision again.

From here,

Probability of station A to successfully retransmit its data after the 1^st collision = 1 / 4
Probability of station D to successfully retransmit its data after the 1^st collision = 1 / 4
Probability of occurrence of collision again after the 1^st collision = 2 / 4 = 1 / 2

Now,

Consider case-02 occurs.
This causes station A to successfully retransmit its 1^st packet after the 1^st collision.

Scene-02: For 2nd Data Packet Of Station A And 1st Data Packet Of Station D-

Consider after some time,

Station A starts transmitting its 2^nd data packet and station D starts retransmitting its 1^st data packet simultaneously.
This leads to a collision.

At Station A-

The 2^nd data packet of station A undergoes collision for the 1^st time.
So, collision number for the 2^nd data packet of station A = 1.
Now, station A randomly chooses a number in the range [0, 2¹-1] = [0,1].
If station A chooses the number K_A, then back off time = K_A units.

At Station D-

The 1^st data packet of station D undergoes collision for the 2^nd time.
So, collision number for the 1^st data packet of station D = 2.
Now, station D randomly chooses a number in the range [0, 2²-1] = [0,3].
If station D chooses the number K_D, then back off time = K_D units.

Following 8 cases are possible-

K_A	K_D	Remarks
0	0	In this case, both the stations start retransmitting their data immediately. This case leads to a collision again.
0	1	In this case, station A starts retransmitting its data immediately while station D waits for 1 unit of time. This case leads to A successfully retransmitting its data after the 2^nd collision.
0	2	In this case, station A starts retransmitting its data immediately while station D waits for 2 unit of time. This case leads to A successfully retransmitting its data after the 2^nd collision.
0	3	In this case, station A starts retransmitting its data immediately while station D waits for 3 unit of time. This case leads to A successfully retransmitting its data after the 2^nd collision.
1	0	In this case, station A waits for 1 unit of time while station D starts retransmitting its data immediately. This case leads to D successfully retransmitting its data after the 2^nd collision.
1	1	In this case, both the stations wait for 1 unit of time and then starts retransmitting their data simultaneously. This case leads to a collision again.
1	2	In this case, station A waits for 1 unit of time while station D waits for 2 unit of time. This case leads to A successfully retransmitting its data after the 2^nd collision.
1	3	In this case, station A waits for 1 unit of time while station D waits for 3 unit of time. This case leads to A successfully retransmitting its data after the 2^nd collision.

From here,

Probability of station A to successfully retransmit its data after the 2^nd collision = 5 / 8
Probability of station D to successfully retransmit its data after the 2^nd collision = 1 / 8
Probability of occurrence of collision again after the 2^nd collision = 2 / 8 = 1 / 4

Now,

Consider case-03 occurs.
This causes station A to successfully retransmit its 2^nd packet after the 2^nd collision.

Scene-03: For 3rd Data Packet Of Station A And 1st Data Packet Of Station D-

Consider after some time,

Station A starts transmitting its 3^rd data packet and station D starts retransmitting its 1^st data packet simultaneously.
This leads to a collision.

At Station A-

The 3^rd data packet of station A undergoes collision for the 1^st time.
So, collision number for the 3^rd data packet of station A = 1.
Now, station A randomly chooses a number in the range [0, 2¹-1] = [0,1].
If station A chooses the number K_A, then back off time = K_A unit.

At Station D-

The 1^st data packet of station D undergoes collision for the 3^rd time.
So, collision number for the 1^st data packet of station D = 3.
Now, station D randomly chooses a number in the range [0, 2³-1] = [0,7].
If station D chooses the number K_D, then back off time = K_D unit.

Following 16 cases are possible-

K_A	K_D	Remarks
0	0	In this case, both the stations start retransmitting their data immediately. This case leads to a collision again.
0	1	In this case, station A starts retransmitting its data immediately while station D waits for 1 unit of time. This case leads to A successfully retransmitting its data after the 3^rd collision.
0	2	In this case, station A starts retransmitting its data immediately while station D waits for 2 unit of time. This case leads to A successfully retransmitting its data after the 3^rd collision.
0	3	In this case, station A starts retransmitting its data immediately while station D waits for 3 unit of time. This case leads to A successfully retransmitting its data after the 3^rd collision.
0	4	In this case, station A starts retransmitting its data immediately while station D waits for 4 unit of time. This case leads to A successfully retransmitting its data after the 3^rd collision.
0	5	In this case, station A starts retransmitting its data immediately while station D waits for 5 unit of time. This case leads to A successfully retransmitting its data after the 3^rd collision.
0	6	In this case, station A starts retransmitting its data immediately while station D waits for 6 unit of time. This case leads to A successfully retransmitting its data after the 3^rd collision.
0	7	In this case, station A starts retransmitting its data immediately while station D waits for 7 unit of time. This case leads to A successfully retransmitting its data after the 3^rd collision.
1	0	In this case, station A waits for 1 unit of time while station D starts retransmitting its data immediately. This case leads to D successfully retransmitting its data after the 3^rd collision.
1	1	In this case, both the stations wait for 1 unit of time and then starts retransmitting their data simultaneously. This case leads to a collision again.
1	2	In this case, station A waits for 1 unit of time while station D waits for 2 unit of time. This case leads to A successfully retransmitting its data after the 3^rd collision.
1	3	In this case, station A waits for 1 unit of time while station D waits for 3 unit of time. This case leads to A successfully retransmitting its data after the 3^rd collision.
1	4	In this case, station A waits for 1 unit of time while station D waits for 4 unit of time. This case leads to A successfully retransmitting its data after the 3^rd collision.
1	5	In this case, station A waits for 1 unit of time while station D waits for 5 unit of time. This case leads to A successfully retransmitting its data after the 3^rd collision.
1	6	In this case, station A waits for 1 unit of time while station D waits for 6 unit of time. This case leads to A successfully retransmitting its data after the 3^rd collision.
1	7	In this case, station A waits for 1 unit of time while station D waits for 7 unit of time. This case leads to A successfully retransmitting its data after the 3^rd collision.

From here,

Probability of station A to successfully retransmit its data after the 3^rd collision = 13 / 16
Probability of station D to successfully retransmit its data after the 3^rd collision = 1 / 16
Probability of occurrence of collision again after the 3^rd collision = 1 / 16

In the similar manner, the procedure continues.

Important Notes-

Note-01:

With each successive collision-

Back off time increases exponentially.
Collision probability decreases exponentially.

Note-02:

Back Off Algorithm is also known as Binary Exponential Back Off Algorithm because-

It works for only two stations.
The back off time increases exponentially.
Collision probability decreases exponentially.

Note-03:

One disadvantage of Back Off Algorithm is that it shows capture effect.
It means if a particular station wins the collision one time, then its probability of winning the successive collisions increases exponentially.

To gain better understanding about Back Off Algorithm,

Watch this Video Lecture

Next Article- Practice Problems On CSMA / CD & Back Off Algorithm

Get more notes and other study material of Computer Networks.

Watch video lectures by visiting our YouTube channel LearnVidFun.

CSMA CD Protocol | CSMA CD Flowchart

Computer Networks

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-

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 T_t >= 2T_p.

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,