Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

SR & GBN: Out-of-window ACKs

I'm currently studying fairly basic networking, and I'm currently on the subject of reliable transmission. I'm using the book Computer Networking by Kurrose & Ross, and two of the review questions were as follows:

With the selective-repeat/go-back-n protocol, it is possible for the sender to receive an ACK for a packet that falls outside of its current window?

For the SR version, my answer to the question was as follows:

Yes, if the window size is too big for the sequence number space. For example, a receiver gets a number of packets equal to the space of the sequence numbers. Its receive window has thus moved so that it is expecting a new set of packets with the same sequence numbers as the last one. The receiver now sends an ACK for each of the packets, but all of them are lost along the way. This eventually causes the sender to timeout for each of the previous set of packets, and retransmits each of them. The receiver think that this duplicate set of packets are really the new ones that it is expecting, and it sends ACKs for each of them that successfully reaches the sender. The sender now experiences a similar kind of confusion, where it thinks that the ACKs are confirmations that each of the old packets have been received, when they are really ACKs meant for the new, yet-to-be-sent packets.

I'm pretty sure this is correct (otherwise, please tell me!), since this kind of scenario seems to be the classic justification of why window size should be less than or equal to half the size of the sequence number space when it comes to SR protocols, but what about GBN?

Can the same kind of wraparound issue occur for it, making the answers mostly identical? If not, are there any other cases that can cause a typical GBN sender to receive an ACK outside of its window?

Regarding the later, the only example I can think of is the following:

A GBN sender sends packets A & B in order. The receiver receives both in order, and sends one cumulative ACK covering every packet before and up to A, and then another one covering every packet before and up to B (including A). The first one is so heavily delayed that the second one arrives first to the sender, causing its window to slide beyond A & B. When the first one finally arrives, it needlessly acknowledges that everything up to A has been correctly received, when A is already outside of the sender's window.

This example seems rather harmless and unlikely in contrast to the previous one, so I doubt that its correct (but again, correct me if I'm wrong, please!).

like image 491
NTRAFF Avatar asked Nov 12 '22 22:11

NTRAFF


1 Answers

In practical world, how about a duplicated ACK delayed long enough to fall out of the window?

The protocol is between the sender and the receiver, but it does not have control over how the media (network path) behaves.

The protocol would still be reliable according to design but the implementation shall be able to handle such out-of-window duplicated ACKs.

like image 199
Shu Avatar answered Dec 25 '22 06:12

Shu