Talk:Sliding window protocol

Origin in SEALink?

I remember reading SEAlink documentation on sliding window. It was driven by Fidonet transcontinental that were high bandwidth, but large lag. It was latter incorporated in to the much more widely used Z-modem. The cited RFC is dated 1992 for the TCP. I think it is noteworthy that SEAlink was the original protocol to use this technique. However, I am not 100% sure this is true. This document is similar to what I recalled, but I specifically remember examples with traffic to Japan. Maybe it was a magazine article on the protocol. 184.144.115.253 (talk) 18:36, 16 February 2022 (UTC)

I added a 'See also SEAlink' to the end of the introductory paragraphs after RTS/CTS sent my back to this page. It is at least contradictory that Xmodem did not have this capability as the goal of SEAlink was to be backwards compatible, but add sliding window. The Zmodem protocol was an incompatible change in the protocol. Kermit also supports sliding window. 184.144.115.253 (talk) 15:06, 17 March 2022 (UTC)

Redirect from sliding window

Currently, "sliding window" redirects here. I'm not sure that's appropriate given the different meaning of the term in dictionary data compression techniques like. (LZ77, etc.) 46.230.143.33 (talk) 10:20, 19 January 2021 (UTC)

There is an explanation in the redirect for this Sliding window based part-of-speech tagging. You could add a link to a compression variant. The redirect has Protocol which should be quickly clear that this information is for a communication protocol. If you have a compression based article that you think is relevant, why not put it here or update the redirect template? Be bold. 184.144.115.253 (talk) 15:11, 17 March 2022 (UTC)

I added a link to LZ77 and LZ78 which seems like the most relevant source. Feel free to provide a better article. 184.144.115.253 (talk) 15:25, 17 March 2022 (UTC)

Peculiarity

The sliding window protocol does not work exactly as mentioned if both the communicating systems start sending at exactly the same time. The article must explain this. Ref:Page 216, Ch3, Computer Networks by A.Tanenbaum. --Sylvestersteele (talk) 18:00, 1 May 2008 (UTC)

Since you seem to be familiar with the subject, is there any chance you could write up an explanation yourself? If you're worried about not knowing how to properly integrate the explanation to the article, you could always try to explain the issue here and let someone else make the actual changes to the article. Or just edit the article yourself and let someone else fix it if it needs fixing. —Ilmari Karonen (talk) 22:44, 1 May 2008 (UTC)

It might be better to describe the protocol seperately in different stub for the different usage for data link and data transmission. —Preceding unsigned comment added by 82.46.170.138 (talk) 14:41, 3 May 2008 (UTC)

Waaaait. That's not true!

the transmitter will only receive acknowledgments in the range n_a to n_t, inclusive. Since it guarantees that n_t−n_a ≤ w_t, there are at most w_t+1 possible sequence numbers that could arrive at any given time. Thus, the transmitter can unambiguously decode the sequence number as long as N > w_t.

Translating to English:

the transmitter will only receive acknowledgements for packets from the lowest acknowledgement it's already had, to the highest packet it's sent. Since it guarantees that both of these fall within one window's length, it only needs a window's length's worth of unique packet IDs. Plus one, apparently, because somehow it can get lots of acks for the lowest acnowledgement it's already had, but no lower.

How can these assumptions ever hold on a laggy network?

Example of failure case on a stateful protocol like TCP: The window size is set to 4. Alice is transmitter, Bob receiver.

• Alice sends packets 1 to 4.
• Bob gets each one, and acks.
• The acks are delayed: Bob has lousy ADSL upstream.
• Alice resends packets 1 to 4.
• Bob gets them and acks again.
• Alice now gets the first set of Acks, raising the lowest acknowledgement she's had ("n_a") to 4.
• Then she sends the next 4 packets, 5 to 8. She numbers them 5, 1, 2, 3.
• Bob gets 5, but not 6, 7, or 8.
• Alice gets Bob's second set of acks, plus his new ack for 5.
• But she THINKS he means "I got packets 6, 7, 8 and 5, and also this unknown packet 4".

For stateful protocols, then, I think you need at least unique ID numbers for at least twice as many packets as you can fit into a window (that's N = 2w_t for you random letter fetishists).

Example of failure case on a stateless protocol like UDP:

• Alice sends packets 1 to 4.
• Bob gets each one, and acks.
• The acks stop off at McDonald's for a sammich.
• Alice doesn't get the acks yet, resends packets 1 to 4.
• Bob gets them and acks again.
• Alice gets the second set of Acks.
• She sends many more packets, all of which are acknowledged in reasonable time.
• Eventually, Alice has almost finished sending the file, and is sending her very last window, packets 123,456,781, 123,456,782, 123,456,783, 123,456,784, which she numbers 1, 2, 3, and 4 for brevity.
• Those packets never reach Bob.
• However, the original acks from the very first packets have finished off their sammiches, and drop by Alice's to see if she still needs them.
• Alice interprets them as being acks for the identically-numbered packets she just sent, and stops transmission, happy that her job is done.

For stateless protocols, then, I think you need to use a unique ID number for every packet (that's "N = x" for you random letter fetishists). —Preceding unsigned comment added by 83.217.164.35 (talk) 15:46, 14 April 2010 (UTC)

I think part of your confusion comes from the level at which this protocol is implemented. First off, TCP and UDP are transport layer protocols, and this is a link layer protocol. The link layer is what allows the transport layer to work and the link layer has no knowledge of the transport layer. The fact that your analysis is divided according to TCP and UDP says that there are some things you don't understand. Second, packets are always numbered in a ring using modulus arithmetic. Packets 123,456,781-4 are not numbered 1-4 for brevity, they actually are packet numbered 1-4. So for example, if we are working modulo 8, counting does not work as we normally think it does (1,2,3,4,5,6,7,8,9,10,11,...). Instead we number packets modulo 8 (0,1,2,3,4,5,6,7,0,1,2,3,4,5,6,7,0,1...). Hope this helps a little bit. —Preceding unsigned comment added by 174.16.145.171 (talk) 06:22, 17 April 2010 (UTC)

Huh? The Transmission Control Protocol article currently says "TCP uses a sliding window flow control protocol." If the TCP "sequence number" and "window size" etc. are not implementing a sliding window protocol, then what is it implementing? --DavidCary (talk) 01:56, 30 April 2015 (UTC)

User:83.217.164.35, I agree with your analysis.

The article now has some additional text saying

Thus, the transmitter can unambiguously decode the sequence number as long as N > w_t.

A stronger constraint is imposed by the receiver. ... It might therefore seem that we must have N ≥ 2w_t. However, the actual limit is ... Thus, it is only necessary that N ≥ w_t+w_r.

At first glance, the article seems to be saying 2 contradictory things about the wrap-around point (N) used to truncate the sequence number (only the truncated sequence number is transmitted in each packet and in each Ack). One part says the wrap-around point needs to be larger than the size of the transmit window (N > w_t). Another part says the wrap-around point needs to be larger than the total of the both windows (N ≥ w_t+w_r).

So which one is correct?

Is there some way of clarifying that there are 2 independent constraints on N (the transmitter-side and the receiver-side constraints), and to get the sliding window protocol to work properly, N must be at least as much as the larger of the two?

Should this article maybe not actually state the exact transmitter-side constraint, but instead merely mention that it is smaller than the receiver-side constraint, and so its exact value is irrelevant?

We seem to be talking about 2 cases: in-order and out-of-order networks.

User:83.217.164.35, your second example seems to assume an out-of-order network.

If the Acks that Alice receives are not in the same order as when Bob transmitted them, then the problem you pointed out occurs no matter what value you pick for N, unless you pick N so huge that Alice's sequence numbers never roll-over and get re-used.

I agree that on such a network, every packet apparently requires a unique ID number for the sliding window protocol to work correctly.

Many networks are in-order networks -- the network may drop some of the Acks that Bob sends, but the network delivers the remaining Acks to Alice in exactly the order that Bob sent them.

Small networks with only one physical path (which may be many hops) from Bob to Alice are always in-order networks.

Even networks that have many physical paths between Alice and Bob, so 2 packets could in principle get sent down 2 different paths and arrive out-of-order, often use a deterministic routing algorithm. Since only one path is used at any one time, it is much easier to guarantee that, although some packets may be lost, the remaining packets all arrive in the order they were sent.

Should we mention in-order and out-of-order networks in this article?

How can we make this article better? --DavidCary (talk) 01:56, 30 April 2015 (UTC)

Later I realize that some TCP congestion-avoidance algorithms estimate the round-trip delay time (RTT) between the sender and the receiver, and estimate the maximum number of packets in-flight. If there are several paths between Alice and Bob, packets may arrive "slightly out-of-order" -- when a new link is installed between Alice and Bob, a packet sent through that link may arrive out of order -- earlier than all of the other packets currently in-flight through slower link(s) that were sent previously.

Because TCP apparently works with networks that have out-of-order delivery, therefore the sliding window protocol apparently works for such a "slightly out-of-order" network, even with truncated sequence numbers, as long as the wrap-around point (N) is "large enough".

Is the total of the both windows (N ≥ w_t+w_r) mentioned in the article large enough? If not, how much bigger does it need to handle such slightly out-of-order networks?

On the other hand, if the sliding window protocol works fine, why do we need the Protection Against Wrapped Sequence numbers (PAWS) mentioned in Transmission Control Protocol#TCP timestamps? --DavidCary (talk) 14:38, 30 April 2015 (UTC)