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?

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
 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 attempt 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 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 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-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?

Solution-

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

Aloha | Pure Aloha | Slotted Aloha

Access Control in Networking-

Efficiency-

Efficiency of Pure Aloha (η) = G x e-2G

where G = Number of stations willing to transmit data

Maximum Efficiency-
 For maximum efficiency,
 We put dη / dG = 0
 Maximum value of η occurs at G = 1/2
 Substituting G = 1/2 in the above expression, we get-

Maximum efficiency of Pure Aloha

= 1/2 x e-2 x 1/2
= 1 / 2e
= 0.184
= 18.4%

Thus,

Maximum Efficiency of Pure Aloha (η) = 18.4%

The maximum efficiency of Pure Aloha is very less due to large number of collisions.

2. Slotted Aloha-

 Slotted Aloha divides the time of shared channel into discrete intervals called
as time slots.
 Any station can transmit its data in any time slot.
 The only condition is that station must start its transmission from the beginning of
the time slot.
 If the beginning of the slot is missed, then station has to wait until the beginning of
the next time slot.
 A collision may occur if two or more stations try to transmit data at the beginning of
the same time slot.

Efficiency-

Efficiency of Slotted Aloha (η) = G x e-G

 where G = Number of stations willing to transmit data at the beginning of the same
time slot

Maximum Efficiency-

For maximum efficiency,

 We put dη / dG = 0
 Maximum value of η occurs at G = 1
 Substituting G = 1 in the above expression, we get-

Maximum efficiency of Slotted Aloha = 1 x e-1

=1/e
= 0.368
= 36.8%

Thus,

Maximum Efficiency of Slotted Aloha (η) = 36.8%

The maximum efficiency of Slotted Aloha is high due to less number of collisions.

Difference Between Pure Aloha And Slotted Aloha-

 Pure Aloha Slotted Aloha

Any station can transmit the data at the

Any station can transmit the data at any time.
beginning of any time slot.

The time is continuous and not globally

The time is discrete and globally synchronized.
synchronized.

Vulnerable time in which collision may occur Vulnerable time in which collision may occur
= 2 x Tt = Tt

Probability of successful transmission of data Probability of successful transmission of data

packet packet
= G x e-2G = G x e-G

Maximum efficiency = 18.4% Maximum efficiency = 36.8%

(Occurs at G = 1/2) ( Occurs at G = 1)

The main advantage of slotted aloha is that it

The main advantage of pure aloha is its
reduces the number of collisions to half and
simplicity in implementation.
doubles the efficiency of pure aloha.

PRACTICE PROBLEM BASED ON PURE ALOHA

AND SLOTTED ALOHA-

Problem-

A group of N stations share 100 Kbps slotted ALOHA channel. Each station output a
500 bits frame on an average of 5000 ms even if previous one has not been sent.
What is the required value of N?

Solution-

Throughput Of One Station-

Throughput of each station = Number of bits sent per second

= 500 bits / 5000 ms
= 500 bits / (5000 x 10-3 sec)
= 100 bits/sec
Throughput Of Slotted Aloha-

Throughput of slotted aloha = Efficiency x Bandwidth

= 0.368 x 100 Kbps
= 36.8 Kbps

Total Number Of Stations-

Throughput of slotted aloha = Total number of stations x Throughput of each station

Substituting the values, we get-
36.8 Kbps = N x 100 bits/sec
∴ N = 368
Thus, required value of N = 368.