**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^{9} bits per sec

= 10000 bits

**Problem-03:**

A 2 km long broadcast LAN has 10^{7} bps bandwidth and uses CSMA / CD. The signal travels along the wire at 2 x 10^{8} 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
^{7}bps - Speed = 2 x 10
^{8}m/sec

**Calculating Propagation Delay-**

Propagation delay (T_{p})

= Distance / Propagation speed

= 2 km / (2 x 10^{8} m/sec)

= 2 x 10^{3} m / (2 x 10^{8} 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^{7} 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}-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
^{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^{5} 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
^{5}km/sec - Bandwidth = 1 Mbps

Substituting these values, we get-

Minimum size of data packet

= 2 x (90 km / 3 x 10^{5} km per sec) x 1 Mbps

= 2 x 30 x 10^{-5} sec x 10^{6} 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.**