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 kth consecutive collision, each colliding station waits for a random time chosen from the interval-

  1. (0 to 2k) x RTT
  2. (0 to 2k-1) x RTT
  3. (0 to 2k-1) x Maximum Propagation delay
  4. (0 to 2k-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 (Tp)

= 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 109 bits per sec

= 10000 bits

 

Problem-03:

 

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

  1. 50 B
  2. 100 B
  3. 200 B
  4. None of the above

 

Solution-

 

Given-

  • Distance = 2 km
  • Bandwidth = 107 bps
  • Speed = 2 x 108 m/sec

 

Calculating Propagation Delay-

 

Propagation delay (Tp)

= Distance / Propagation speed

= 2 km / (2 x 108 m/sec)

= 2 x 103 m / (2 x 108 m/sec)

= 10-5 sec

 

Calculating Minimum Frame Size-

 

Minimum frame size

= 2 x Propagation delay x Bandwidth

= 2 x 10-5 sec x 107 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 ___ .

  1. 0.5
  2. 0.625
  3. 0.75
  4. 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 1st data packet.

 

2nd Transmission Attempt-

 

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

 

Now,

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

 

At Station A-

 

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

 

At Station B-

 

  • 1st data packet of station B undergoes collision for the 2nd time.
  • So, collision number for the 1st data packet of station B = 2.
  • Now, station B randomly chooses a number from the range [0,22-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 AStation BRemark
00Collision
01A wins
02A wins
03A wins
10B wins
11Collision
12A wins
13A wins

 

From here,

  • Probability of A winning the 2nd 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 (Tp)

= 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 105 km/sec. If sender sends at 1 Mbps, what could be the minimum size of the packet?

  1. 600 bits
  2. 400 bits
  3. 6000 bits
  4. 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 105 km/sec
  • Bandwidth = 1 Mbps

 

Substituting these values, we get-

Minimum size of data packet

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

= 2 x 30 x 10-5 sec x 106 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.

Summary
CSMA CD | BackOff Algorithm | Problems
Article Name
CSMA CD | BackOff Algorithm | Problems
Description
Practice Problems based on CSMA / CD and Back Off Algorithm. CSMA / CD protocol stands for Carrier Sense Multiple Access / Collision Detection. Back Off Algorithm or Binary Exponential BackOff Algorithm is used to calculate back off time.
Author
Publisher Name
Gate Vidyalay
Publisher Logo