Step 1 Introduction to Go-back-N and Selective-repeat-protocols

• Go Back N allows the transmission of new packets before earlier ones are acknowledged.
• Go back N uses a window mechanism where the sender can send packets that are within a “window” (range) of packets.
– The window advances as acknowledgements for earlier packets are received.

Features of Go Back N:

Window size = N
– Sender cannot send packet i+N until it has received the ACK for packet i
• Receiver operates just like in Stop and Wait
– Receive packets in order
– Receiver cannot accept packet out of sequence
– Send RN = i + 1 => ACK for all packets up to and including i.

Efficiency of Go-Back-N’s:

Efficiency = N/(1+2a)
Where a = Propagation delay / Transmission delay
Buffers = N + N
Sequence number = N(sender side) + N ( Receiver Side)

The go-back-n protocol works well if errors are less, but if the line is poor it wastes a lot of bandwidth on retransmitted frames. An alternative strategy, the selective repeat protocol, is to allow the receiver to accept and buffer the frames following a damaged or lost one.

Selective Repeat attempts to retransmit only those packets that are actually lost (due to errors) :

Receiver must be able to accept packets out of order.
Since receiver must release packets to higher layer in order, the receiver must be able to buffer some packets.

Efficiency of Selective Repeat Protocol (SRP) is same as GO-Back-N’s efficiency :

Efficiency = N/(1+2a)
Where a = Propagation delay / Transmission delay
Buffers = N + N
Sequence number = N(sender side) + N ( Receiver Side)

Step 2 Solution

As per the above question when we consider the Go-Back-N and selective-repeat protocols, suppose the sequence number space is of size k then the largest allowable sender window that will avoid the occurrence of problems for each of these protocols are assigned below :

When we have the sequence number space size as k , we will obtain

[K, K+n-1]

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.

Here when we have the acknowledgements are still on their way to senderthe possible values of the ACK field in the messages currently propagating back to the sender at a time ‘t’ are :

cknowledgement 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.

Consider the Go-Back-N and selective-repeat protocols, suppose the sequence number space is of size k. What is the largest allowable sender window that will avoid the occurrence of problems for each of these protocols?

Public Answer