2

Let's say there is a network that sometimes delivers data with extreme delays. And there is a protocol that uses a "sliding window" algorithm for tracking packets acknowledgement. And imagine such a situation:

  1. The transmitter sends a packet and then re-transmits it because it didn't get an acknowledgement.
  2. Some of these re-transmitted packets get delayed.
  3. Then it finally gets an acknowledgement and the transmission proceeds.
  4. The receiver window finally makes a full round-trip and is being positioned at the position when the excessive re-transmitting was done in 1..
  5. Some of re-transmitted packets delayed in 2. finally arrive.
  6. Receiver mistakenly thinks that they belong to the current window "cycle" and process them while it shouldn't be done because they are duplicate.

So essentially a question is - how to detect duplicate packets from previous window "cycles"? What are commonly used methods for dealing with such situations?

Improve this question
3

I'm also of the view this is phenomenally unlikely and poses no real problem in any network I know about. So the answer to "commonly-used methods" against it is that there aren't any.

However, you could build a malicious router which would do this: capture (in flight somewhere) a few packets, wait for the sequence numbers to go round, then replay them and we'd trigger this situation. What would happen would depend on the upstairs protocols, which in real life would have to be something like scp or rsync (copy big file) or some streaming service (cctv up for ever?). What else will keep a TCP open for 4GByte? (So perhaps the answer is: "situation is usually prevented because the stream never wraps its sequence numbers because it is too short."

For protocol issues, I note that RFC 7323 "TCP extensions for high performance" covers this exact issue with "PAWS" (protection against wrapped sequences). https://tools.ietf.org/html/rfc7323#section-5

A quick search shows there's some mention of this in haiku-os and Linux kernel, but I've no knowledge of how much is actually implemented.

Kind regards,

Jonathan.

Improve this answer
1

Your number 6:

Receiver mistakenly thinks that they belong to the current window "cycle" and process them while it shouldn't be done because they are duplicate.

That isn't what happens. For example, TCP has a Sequence Number field in the TCP segment header. If the segment has already been received, the duplicate segment is ignored.

From RFC 793, Transmission Control Protocol:

Reliability:

The TCP must recover from data that is damaged, lost, duplicated, or delivered out of order by the internet communication system. This is achieved by assigning a sequence number to each octet transmitted, and requiring a positive acknowledgment (ACK) from the receiving TCP. If the ACK is not received within a timeout interval, the data is retransmitted. At the receiver, the sequence numbers are used to correctly order segments that may be received out of order and to eliminate duplicates. Damage is handled by adding a checksum to each segment transmitted, checking it at the receiver, and discarding damaged segments.

As long as the TCPs continue to function properly and the internet system does not become completely partitioned, no transmission errors will affect the correct delivery of data. TCP recovers from internet communication system errors.

Flow Control:

TCP provides a means for the receiver to govern the amount of data sent by the sender. This is achieved by returning a "window" with every ACK indicating a range of acceptable sequence numbers beyond the last segment successfully received. The window indicates an allowed number of octets that the sender may transmit before receiving further permission.

-and-

2.6. Reliable Communication

A stream of data sent on a TCP connection is delivered reliably and in order at the destination.

Transmission is made reliable via the use of sequence numbers and acknowledgments. Conceptually, each octet of data is assigned a sequence number. The sequence number of the first octet of data in a segment is transmitted with that segment and is called the segment sequence number. Segments also carry an acknowledgment number which is the sequence number of the next expected data octet of transmissions in the reverse direction. When the TCP transmits a segment containing data, it puts a copy on a retransmission queue and starts a timer; when the acknowledgment for that data is received, the segment is deleted from the queue. If the acknowledgment is not received before the timer runs out, the segment is retransmitted.

An acknowledgment by TCP does not guarantee that the data has been delivered to the end user, but only that the receiving TCP has taken the responsibility to do so.

To govern the flow of data between TCPs, a flow control mechanism is employed. The receiving TCP reports a "window" to the sending TCP. This window specifies the number of octets, starting with the acknowledgment number, that the receiving TCP is currently prepared to receive.

Also, see Section 3.3. Sequence Numbers.

Edit:

Based on the comments and discussion, it appears that you forget that you are asking about sliding windows, where the size of the window is adjusted to meet the network conditions. if the network conditions are so bad (you write, "extreme"), the window size will be very small. When it gets to the point of being so small that it is for a single segment, then there is no problem because any duplicate segments will be for a different window, and they will be dropped.

Improve this answer
  • But the sequence number could be duplicated because it is stored in a fixed-size field and when sequence numbers exceed it's capacity number is is reset. – Gill Bates Oct 7 '17 at 14:56
  • The sequence number is huge, and you would need to transfer 2^32=4,294,967,296 bytes of data for it to roll over. There is no window that is that large. – Ron Maupin♦ Oct 7 '17 at 15:10
  • 1. It's not a big amount of data (only 4 Gb). 2. In different protocols different sequence number sizes could be used - so it could be smaller. 3. Is it possible to eliminate such an assumption that "the old duplicate packets are dead before the sequence number is reset" in a protocol design? – Gill Bates Oct 7 '17 at 15:15
  • There will be no window that is larger than 4 GB (not Gb). Here, we deal with real-world answers, and TCP is the protocol used in the real world. It works, and you want to argue with success. TCP is the example of how to do this. – Ron Maupin♦ Oct 7 '17 at 15:18
  • Please, be specific. Not the size of the window matters but the speed of it's "round-trip". Sequence number field also could be smaller than 32 bit. So window could round do it's round-trip relatively quickly and the receiver could mistakenly take the sequence numbers of the packets from the previous "cycles" of the window as the sequence numbers of the current "cycle". – Gill Bates Oct 7 '17 at 15:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.