Selective Repeat Protocol-

 

Before you go through this article, make sure that you have gone through the previous article on Selective Repeat Protocol.

 

We have discussed-

• Sliding Window Protocols allow the sender to send multiple frames before needing acknowledgements.
• Selective Repeat is an implementation of a sliding window protocol.

 

In this article, we will discuss practice problems based on selective repeat protocol.

 

 

PRACTICE PROBLEMS BASED ON SELECTIVE REPEAT PROTOCOL-

 

Problem-01:

 

The maximum window size for data transmission using the selective repeat protocol with n bit frame sequence numbers is-

1. 2ⁿ
2. 2^n-1
3. 2ⁿ-1
4. 2^n-2

 

Solution-

 

We know-

• With n bits, total number of sequence numbers possible = 2ⁿ.
• In SR Protocol, sender window size = receiver window size = W (say)

 

For any sliding window protocol to work without any problems,

 

Min Available Sequence Numbers = Sender window size + Receiver window size

 

So, we have-

2ⁿ = W + W

2ⁿ = 2W

W = 2^n-1

Therefore, maximum window size possible of sender and receiver = 2^n-1

Thus, Option (B) is correct.

 

Problem-02:

 

In SR protocol, suppose frames through 0 to 4 have been transmitted. Now, imagine that 0 times out, 5 (a new frame) is transmitted, 1 times out, 2 times out and 6 (another new frame) is transmitted.

At this point, what will be the outstanding packets in sender’s window?

 

1. 341526
2. 3405126
3. 0123456
4. 654321

 

Solution-

 

In SR Protocol, only the required frame is retransmitted and not the entire window.

 

Step-01:

 

Frames through 0 to 4 have been transmitted-

4 , 3 , 2 , 1 , 0

 

Step-02:

 

0 times out. So, sender retransmits it-

0 , 4 , 3 , 2 , 1

 

Step-03:

 

5 (a new frame) is transmitted-

5 , 0 , 4 , 3 , 2 , 1

 

Step-04:

 

1 times out. So, sender retransmits it-

1 , 5 , 0 , 4 , 3 , 2

 

Step-05:

 

2 times out. So, sender retransmits it-

2 , 1 , 5 , 0 , 4 , 3

 

Step-06:

 

6 (another new frame) is transmitted-

6 , 2 , 1 , 5 , 0 , 4 , 3

 

Thus, Option (B) is correct.

 

Problem-03:

 

The selective repeat protocol is similar to Go back N except in the following way-

 

1. Frame Formats are similar in both the protocols
2. The sender has a window defining maximum number of outstanding frames in both the protocols
3. Both uses piggybacked acknowledgements where possible and does not acknowledge every frame explicitly.
4. Both uses piggyback approach that acknowledges the most recently received frame

 

Solution-

 

Also Read- Go back N Protocol

 

Option (A)-

 

• Both the protocols use the same frame formats because both are sliding window protocols.
• The variation occurs only in the coding and implementation.

 

Option (B)-

 

• In both the protocols, sender has a window which defines the maximum number of outstanding frames.

 

Option (C)-

 

• Both the protocols use piggybacked acknowledgements wherever possible.
• Sending acknowledgements along with the data are called as piggybacked acknowledgements.
• But Go back N protocol uses cumulative acknowledgements and does not acknowledge every frame explicitly.
• On the other hand, Selective repeat protocol acknowledges each frame independently.

 

Option (D)-

 

• Both the protocols use piggyback approach.
• Go back N acknowledges the most recently received frame by sending a cumulative acknowledgement which includes the acknowledgement for previous packets too if any.
• On the other hand, Selective Repeat protocol acknowledges all the frames independently and not only the recently received frame.

 

Thus, Options (C) and (D) are correct.

 

Problem-04:

 

Consider a 128 x 10³ bits/sec satellited communication link  with one way propagation delay of 150 msec. Selective Retransmission (repeat) protocol is used on this link to send data with a frame size of 1 KB. Neglect the transmission time of acknowledgement. The minimum number of bits required for the sequence number field to achieve 100% utilization is ________ .

 

Solution-

 

Given-

• Bandwidth = 128 x 10³ bits/sec
• Propagation delay (T_p) = 150 msec
• Frame size = 1 KB

 

Now,

• To achieve 100% utilization, efficiency must be 100%.
• Efficiency is 100% when sender window size is optimal i.e. 1+2a

 

Calculating Transmission Delay-

 

Transmission delay (T_t)

= Frame size / Bandwidth

= 1 KB / (128 x 10³ bits per sec)

= (1 x 2¹⁰ x 8 bits) / (128 x 10³ bits per sec)

= 64 msec

 

Calculating Value of ‘a’-

 

a = T_p / T_t

a = 150 msec / 64 msec

a = 2.34

 

Calculating Optimal Sender Window Size-

 

Optimal sender window size

= 1 + 2a

= 1 + 2 x 2.34

= ⌈5.68⌉

= 6

 

Calculating Number Of Sequence Numbers Required-

 

In SR Protocol, sender window size and receiver window size are same.

So, sender window size = receiver window size = 6

 

Now,

For any sliding window protocol, minimum number of sequence numbers required

= Sender window size + Receiver window size

= 6 + 6

= 12

 

Calculating Bits Required in Sequence Number Field-

 

To have 12 sequence numbers,

Minimum number of bits required in sequence number field

= ⌈log₂(12)⌉

= 4

 

Thus,

• Minimum number of bits required in sequence number field = 4
• With 4 bits, number of sequence numbers possible = 16
• We use only 12 sequence numbers and rest 4 remains unused.

 

Next Article- Comparison Table Of Sliding Window Protocols

 

Get more notes and other study material of Computer Networks.

Watch video lectures by visiting our YouTube channel LearnVidFun.

Sliding Window Protocol-

 

Before you go through this article, make sure that you have gone through the previous article on Sliding Window Protocol.

 

The two well known implementations of sliding window protocol are-

 

 

1. Go back N Protocol
2. Selective Repeat Protocol

 

In this article, we will discuss about Selective Repeat protocol.

Learn about Go back N Protocol.

 

Selective Repeat Protocol-

 

Selective Repeat protocol or SR protocol is an implementation of a sliding window protocol.

The features and working of this protocol are explained in the following points-

 

Point-01:

 

In SR protocol, sender window size is always same as receiver window size.

 

In SR protocol,

• Sender window size = Receiver window size
• The size is of course greater than 1 otherwise the protocol will become Stop and Wait ARQ.
• If n bits are available for sequence numbers, then-

Sender window size = Receiver window size = 2ⁿ/2 = 2^n-1

 

Point-02:

 

SR protocol uses independent acknowledgements only.

 

In SR protocol,

• Receiver acknowledges each frame independently.
• As receiver receives a new frame from the sender, it sends its acknowledgement.

 

Point-03:

 

SR protocol does not accept the corrupted frames but does not silently discard them.

 

In SR protocol,

• If receiver receives a frame that is corrupted, then it does not silently discard that frame.
• Receiver handles the situation efficiently by sending a negative acknowledgement (NACK).
• Negative acknowledgement allows early retransmission of the corrupted frame.
• It also avoids waiting for the time out timer to expire at the sender side to retransmit the frame.

 

Point-05:

 

SR protocol accepts the out of order frames.

 

In SR protocol,

• Consider receiver receives a frame whose sequence number is not what the receiver expects.
• Then, it does not discard that frame rather accepts it and keeps it in its window.

 

Point-06:

 

SR protocol requires sorting at the receiver’s side.

 

In SR protocol,

• Receiver window is implemented as a linked list.
• When receiver receives a new frame, it places the new frame at the end of the linked list.
• When the received frames are out of order, receiver performs the sorting.
• Sorting sorts the frames in the correct order.

 

Point-07:

 

SR protocol requires searching at the sender’s side.

 

In SR protocol,

• Receiver does not reject the out of order frames.
• Receiver accepts the out of order frames and sort them later.
• Thus, only the missing frame has to be sent by the sender.
• For sending the missing frame, sender performs searching and finds the missing frame.
• Then, sender selectively repeats that frame.
• Thus, only the selected frame is repeated and not the entire window.
• That is why, the protocol has been named as “Selective Repeat Protocol“.

 

Point-08:

 

SR protocol leads to retransmission of lost frames after expiry of time out timer.

 

In SR protocol,

• Consider a frame being sent to the receiver is lost on the way.
• Then, it is retransmitted only after time out timer expires for that frame at sender’s side.

 

Efficiency of SR Protocol-

 

Efficiency of any flow control protocol is given by-

 

Efficiency = Sender Window Size in Protocol / (1 + 2a)

 

In selective repeat protocol, if sender window size = N, then-

 

Efficiency of SR Protocol = N / (1 + 2a)

 

To gain better understanding about Selective Repeat ARQ,

Watch this Video Lecture

 

Next Article- Practice Problems On Selective Repeat Protocol

 

Get more notes and other study material of Computer Networks.

Watch video lectures by visiting our YouTube channel LearnVidFun.

Go Back N Protocol-

 

Before you go through this article, make sure that you have gone through the previous article on Go back N Protocol.

 

We have discussed-

• Sliding window protocols allow the sender to send multiple frames before needing acknowledgements.
• Go back N is an implementation of a sliding window protocol.

 

In this article, we will discuss practice problems based on Go back N protocol.

 

PRACTICE PROBLEMS BASED ON GO BACK N PROTOCOL-

 

Problem-01:

 

A 20 Kbps satellite link has a propagation delay of 400 ms. The transmitter employs the “go back n ARQ” scheme with n set to 10.

Assuming that each frame is 100 bytes long, what is the maximum data rate possible?

1. 5 Kbps
2. 10 Kbps
3. 15 Kbps
4. 20 Kbps

 

Solution-

 

Given-

• Bandwidth = 20 Kbps
• Propagation delay (T_p) = 400 ms
• Frame size = 100 bytes
• Go back N is used where N = 10

 

Calculating Transmission Delay-

 

Transmission delay (T_t)

= Frame size / Bandwidth

= 100 bytes / 20 Kbps

= (100 x 8 bits) / (20 x 10³ bits per sec)

= 0.04 sec

= 40 msec

 

Calculating Value Of ‘a’-

 

a = T_p / T_t

a = 400 msec / 40 msec

a = 10

 

Calculating Efficiency-

 

Efficiency (η)

= N / (1+2a)

= 10 / (1 + 2 x 10)

= 10 / 21

= 0.476

= 47.6 %

 

Calculating Maximum Data Rate Possible-

 

Maximum data rate possible or Throughput

= Efficiency x Bandwidth

= 0.476 x 20 Kbps

= 9.52 Kbps

≅ 10 Kbps

 

Thus, Correct Option is (B)

 

Problem-02:

 

Consider the Go back N protocol with a sender’s window size of ‘n’. Suppose that at time ‘t’, the next inorder packet the receiver is expecting has a sequence number of ‘K’. Assume that the medium does not reorder messages.

Answer the following questions-

 

Part-01:

 

What are the possible sets of sequence numbers inside the sender’s window at time ‘t’. Assume the sender has already received the ACKs.

 

1. [K-1, K+n-1]
2. [K, K+n-1]
3. [K, K+n]
4. [K+n, K-1]

 

Part-02:

 

If acknowledgements are still on their way to sender, what are all possible values of the ACK field in the messages currently propagating back to the sender at a time ‘t’?

 

1. [K-n, K-1]
2. [K-1, K-n]
3. [K, K-n]
4. [K-n, K+1]

 

Solution-

 

Part-01:

 

• In Go back N protocol, the receiver window size is 1.
• It is given that receiver expects the packet having sequence number ‘K’.
• It means it has processed all the packets ranging from 0 to K-1.
• It is given that sender has received the acknowledgement for all these packets.
• So, outstanding packets in sender’s window waiting for the acknowledgement starts from K.
• Sender window size = n.
• Therefore, last packet in sender’s window will have sequence number K+n-1.

 

Thus, Option (B) is correct.

 

Part-02:

 

• Acknowledgement number is the next expected sequence number by the receiver.
• Receiver expects the packet having sequence number ‘K’ at time ‘t’.
• It means it has received the packets ranging from 0 to K-1 whose acknowledgements are are on the way.
• For the (K-1)^th packet, acknowledgement number would be ‘K’.
• For the (K-2)^th packet, acknowledgement number would be ‘K-1’ and so on.

 

Now,

• At any time, maximum number of outstanding packets can be ‘n’.
• This is because sender’s window size is ‘n’.
• Therefore, the possible values of acknowledgement number ranges from [K-n+1, ……, K-3, K-2, K-1, K] (total n values)
• Here, we have assumed that the acknowledgement for all the packets are sent independently.

 

Thus, Option (C) is correct.

 

Problem-03:

 

Station A needs to send a message consisting of 9 packets to station B  using a sliding window (window size 3) and go back n error control strategy. All packets are ready and immediately available for transmission.

If every 5th packet that A transmits gets lost (but no ACKs from B ever get lost), then what is the number of packets that A will transmit for sending the message to B?

1. 12
2. 14
3. 16
4. 18

 

Solution-

 

Given-

• Total number of packets to be sent = 9
• Go back N is used where N = 3
• Every 5th packet gets lost

 

Step-01:

 

Since sender window size is 3, so sender sends 3 packets (1, 2, 3)-

 

Total packets sent till now from sender side = 3

 

Step-02:

 

After receiving the acknowledgement for packet-1, sender slides its window and sends packet-4.

 

Total packets sent till now from sender side = 4

 

Step-03:

 

After receiving the acknowledgement for packet-2, sender slides its window and sends packet-5.

 

Total packets sent till now from sender side = 5

 

Step-04:

 

After receiving the acknowledgement for packet-3, sender slides its window and sends packet-6.

 

Total packets sent till now from sender side = 6

 

Step-05:

 

After receiving the acknowledgement for packet-4, sender slides its window and sends packet-7.

 

Total packets sent till now from sender side = 7

 

Step-06:

 

• According to question, every 5th packet gets lost.
• So, packet-5 gets lost and when time out occurs, sender retransmits packet-5.
• In Go back N, all the following packets are also discarded by the receiver.
• So, packet-6 and packet-7 are discarded by the receiver and they are also retransmitted.
• Thus, the entire window is retransmitted.

 

So, we have-

Total packets sent till now from sender side = 10

 

Now, the next 5th packet that will be lost will be packet-7. (6, 7, 5, 6, 7)

 

Step-07:

 

After receiving the acknowledgement for packet-5, sender slides its window and sends packet-8.

 

Total packets sent till now from sender side = 11

 

Step-08:

 

After receiving the acknowledgement for packet-6, sender slides its window and sends packet-9.

 

Total packets sent till now from sender side = 12

 

Step-09:

 

• According to question, every 5th packet gets lost.
• So, packet-7 gets lost and when time out occurs, sender retransmits packet-7 and the following packets.
• Thus, the entire window is retransmitted.

 

So, we have-

Total packets sent till now from sender side = 15

 

Now, the next 5th packet that will be lost will be packet-9. (8, 9, 7, 8, 9)

 

Step-10:

 

After receiving the acknowledgement for packet-7, sender slides its window.

 

Total packets sent till now from sender side = 15

 

Step-11:

 

After receiving the acknowledgement for packet-8, sender slides its window.

 

Total packets sent till now from sender side = 15

 

Step-12:

 

• According to question, every 5th packet gets lost.
• So, packet-9 gets lost and when time out occurs, sender retransmits packet-9.

 

So, we have-

Total packets sent till now from sender side = 16

 

Finally, all the 9 packets got transmitted which took total 16 number of transmissions.

Thus, Correct Option is (C).

 

Problem-04:

 

In Go back 4, if every 6th packet that is being transmitted is lost and if total number of packets to be sent is 10, then how many transmissions will be required?

 

Solution-

 

• Try yourself!
• We have to solve in exactly the same way as we have solved Problem-03.
• Total number of transmissions required will be 17.

 

Problem-05:

 

A 1 Mbps satellite link connects two ground stations. The altitude of the satellite is 36504 km and speed of the signal is 3 x 10⁸ m/sec. What should be the packet size for a channel utilization of 25% for a satellite link using go back 127 sliding window protocol?

1. 120 bytes
2. 60 bytes
3. 240 bytes
4. 90 bytes

 

Solution-

 

Given-

• Bandwidth = 1 Mbps
• Distance = 2 x 36504 km = 73008 km
• Propagation speed = 3 x 10⁸ m/sec
• Efficiency = 25% = 1/4
• Go back N is used where N = 127

 

Let the packet size be L bits.

 

Calculating Transmission Delay-

 

Transmission delay (T_t)

= Packet size / Bandwidth

= L bits / 1 Mbps

= L μsec

 

Calculating Propagation Delay-

 

Propagation delay (T_p)

= Distance / Speed

= (73008 x 10³ m) / (3 x 10⁸ m/sec)

= 24336 x 10^-5 sec

= 243360 μsec

 

Calculating Value of ‘a’-

 

a = T_p / T_t

a = 243360 μsec / L μsec

a = 243360 / L

 

Calculating Packet Size-

 

Efficiency (η) = N / (1+2a)

Substituting the values, we get-

1/4 = 127 / (1 + 2 x 243360 / L)

1/4 = 127 x L / (L + 486720)

L + 486720 = 508 x L

507 x L = 486720

L = 960

 

From here, packet size = 960 bits or 120 bytes.

Thus, Correct Option is (A).

 

Problem-06:

 

Consider a network connecting two systems located 8000 km apart. The bandwidth of the network is 500 x 10⁶ bits per second. The propagation speed of the media is 4 x 10⁶ meters per second. It is needed to design a Go back N sliding window protocol for this network. The average packet size is 10⁷ bits. The network is to be used to its full capacity.

Assume that processing delays at nodes are negligible. Then, the minimum size in bits of the sequence number field has to be ______ ?

 

Solution-

 

Given-

• Distance = 8000 km
• Bandwidth = 500 x 10⁶ bps
• Propagation speed = 4 x 10⁶ m/sec
• Packet size = 10⁷ bits

 

Now,

• For using the network to its full capacity, Efficiency (η) = 1
• Efficiency (η) = 1 when sender window size = 1+2a

 

Calculating Transmission Delay-

 

Transmission delay (T_t)

= Packet size / Bandwidth

= 10⁷ bits / (500 x 10⁶ bits per sec)

= 1 / 50 sec

= 0.02 sec

 

Calculating Propagation Delay-

 

Propagation delay (T_p)

= Distance / Speed

= 8000 km / (4 x 10⁶ m/sec)

= 2 sec

 

Calculating Value of ‘a’-

 

a = T_p / T_t

a = 2 sec / 0.02 sec

a = 100

 

Calculating Sender Window Size-

 

Sender window size

= 1 + 2a

= 1 + 2 x 100

= 201

 

Calculating Minimum Size Of Sequence Number Field-

 

Minimum number of bits required in the sequence number field

= ⌈log₂(1+2a)⌉

= ⌈log₂(201)⌉

= ⌈7.65⌉

= 8

Thus, Minimum size of sequence number field = 8 bits.

 

Next Article- Selective Repeat Protocol

 

Get more notes and other study material of Computer Networks.

Watch video lectures by visiting our YouTube channel LearnVidFun.

Sliding Window Protocol-

 

Before you go through this article, make sure that you have gone through the previous article on Sliding Window Protocol.

 

The two well known implementations of sliding window protocol are-

 

 

1. Go back N Protocol
2. Selective Repeat Protocol

 

In this article, we will discuss about Go back N protocol.

 

Go back N Protocol-

 

Go back N protocol is an implementation of a sliding window protocol.

The features and working of this protocol are explained in the following points-

 

Point-01:

 

In Go back N, sender window size is N and receiver window size is always 1.

 

In Go back N,

• Sender window size = N. Example in Go back 10, sender window size will be 10.
• Receiver window size is always 1 for any value of N.

 

Point-02:

 

Go back N uses cumulative acknowledgements.

 

In Go back N,

• Receiver maintains an acknowledgement timer.
• Each time the receiver receives a new frame, it starts a new acknowledgement timer.
• After the timer expires, receiver sends the cumulative acknowledgement for all the frames that are unacknowledged at that moment.

 

NOTE-

 

• A new acknowledgement timer does not start after the expiry of old acknowledgement timer.
• It starts after a new frame is received.

 

Point-03:

 

Go back N may use independent acknowledgements too.

 

• The above point does not mean that Go back N can not use independent acknowledgements.
• Go back N may use independent acknowledgements too if required.
• The kind of acknowledgement used depends on the expiry of acknowledgement timer.

 

Example-

 

• Consider after the expiry of acknowledgement timer, there is only one frame left to be acknowledged.
• Then, Go back N sends the independent acknowledgement for that frame.

 

Point-04:

 

Go back N does not accept the corrupted frames and silently discards them.

 

In Go back N,

• If receiver receives a frame that is corrupted, then it silently discards that frame.
• The correct frame is retransmitted by the sender after the time out timer expires.
• Silently discarding a frame means-

“Simply rejecting the frame and not taking any action”

(like not sending a NACK to the sender to send the correct frame)

 

Point-05:

 

Go back N does not accept out of order frames and silently discards them.

 

In Go back N,

• If receiver receives a frame whose sequence number is not what the receiver expects, then it silently discards that frame.
• All the following frames are also discarded.
• This is because receiver window size is 1 and therefore receiver can not accept out of order frames.

 

Point-06:

 

Go back N leads to retransmission of entire window if for any frame, no ACK is received by the sender.

 

In Go back N,

• Receiver silently discards the frame if it founds the frame to be either corrupted or out of order.
• It does not send any acknowledgement for such frame.
• It silently discards the following frames too.

 

Thus,

• If for any particular frame, sender does not receive any acknowledgement, then it understands that along with that frame, all the following frames must also have been discarded by the receiver.
• So, sender has to retransmit all the following frames too along with that particular frame.
• Thus, it leads to the retransmission of entire window.
• That is why, the protocol has been named as “Go back N“.

 

Point-07:

 

Go back N leads to retransmission of lost frames after expiry of time out timer.

 

In Go back N,

• Consider a frame being sent to the receiver is lost on the way.
• Then, it is retransmitted only after time out timer expires for that frame at sender’s side.

 

Efficiency of Go back N-

 

Efficiency of any flow control protocol is given by-

 

Efficiency = Sender Window Size in Protocol / (1 + 2a)

 

In Go back N protocol, sender window size = N.

Thus,

 

Efficiency of Go back N = N / (1 + 2a)

 

To gain better understanding about Go back N ARQ,

Watch this Video Lecture

 

Next Article- Practice Problems On Go Back N Protocol

 

Get more notes and other study material of Computer Networks.

Watch video lectures by visiting our YouTube channel LearnVidFun.