Why is window size less than or equal to half the sequence number in SR protocol?

Question

In selective repeat protocol, the window size must be less than or equal to half the size of the sequence number space for the SR protocol. Why is this so, and how?

Answer 1

This is to avoid packets being recognized incorrectly.

If the windows size is greater than half the sequence number space, then if an ACK is lost, the sender may send new packets that the receiver believes are retransmissions.

For example, if our sequence number range is 0-3 and the window size is 3, this situation can occur.

A -> 0 -> B

A -> 1 -> B

A -> 2 -> B

A <- 2ack <- B (this is lost)

A -> 0 -> B

A -> 1 -> B

A -> 2 -> B

After the lost packet, B now expects the next packets to have sequence numbers 3, 0, and 1.

But, the 0 and 1 that A is sending are actually retransmissions, so B receives them out of order.

By limiting the window size to 2 in this example, we avoid this problem because B will be expecting 2 and 3, and only 0 and 1 can be retransmissions.

Answer 2

The sequence space wraps to zero after max number is reached. Consider the corner case where all ACKs are lost - sender does not move its window, but receiver does (since it's unaware the sender is not getting the ACKs). If we don't limit the window size to half the sequence space, we end up with overlapping sender "sent but not acknowledged" and receiver "valid new" sequence spaces. This would result in retransmissions being interpreted as new packets.

Answer 3

Because the receiver will fail to distinguish between an old packet or a new packet. The receiver identifies packets based on sequence numbers, and there is a finite number of unique numbers for each connection. You can't have an infinite buffer.

Lets look at a obvious fail scenario:

The window size is greater than the sequence number space. Lets say we have sequence numbers 0, 1, 2. And our window size is 4. This means that the window has two occurrences of 0.

0,1,2,0 <- modulo wrap. When we get a package with a seq of 0. Is it the first packet or the fourth? No clue. Now, this problem will occur insofar as the window size is greater than half of the sequence number space. Why? Because there's always the possibility that the receiver is looking at a sequence number that MAY be contained in a packet coming from the sender that is NEW or OLD. Does it always happen? No. But when it does, here's what happens:

Case 1:

Receiver window after properly receiving packets 0,1,2. 0,1,2,[3,0,1],2 But what if the ACKs sent are lost? Well, the sender will resend 0,1,2. But are 0,1 OLD or NEW? The receiver can't tell.

Case 2:

Same window on receiving end. The three packets are received.

0,1,2,[3,0,1],2

Now, the receiver receives ALL the acks but ONE correctly. Lets pick the 2nd one (1). Now, it's going to resend 1. But the receiver is looking at 1! So is this the new one as it expects (nope), or the old one?

Therefore, to ensure that the window is never expecting sequence numbers that could possibly be used by potential outstanding packets (either coming from a normal transmission or re-transmission of a missing ack) we have to either decrease the window size or increase sequence numbers.

Look what happens when we increase the sequence number space to, say 6.

0,1,2,3,4,5.

No matter how we position the window, it's never at risk of receiving a packet with a old sequence number.

0,1,2,[3,4,5]0,1...

By the time the window wraps around, we are positive that we've received the previous ones in order.