Sliding window protocol

A sliding window protocol is a feature of packet-based data transmission protocols. Sliding window protocols are used where reliable in-order delivery of packets is required, such as in the data link layer (OSI layer 2) as well as in the Transmission Control Protocol (i.e., TCP windowing). They are also used to improve efficiency when the channel may include high latency.

Packet-based systems are based on the idea of sending a batch of data, the packet, along with additional data that allows the receiver to ensure it was received correctly, perhaps a checksum. The paradigm is similar to a window sliding sideways to allow entry of fresh packets and reject the ones that have already been acknowledged. When the receiver verifies the data, it sends an acknowledgment signal, or ACK, back to the sender to indicate it can send the next packet. In a simple automatic repeat request protocol (ARQ), the sender stops after every packet and waits for the receiver to ACK. This ensures packets arrive in the correct order, as only one may be sent at a time.

The time that it takes for the ACK signal to be received may represent a significant amount of time compared to the time needed to send the packet. In this case, the overall throughput may be much lower than theoretically possible. To address this, sliding window protocols allow a selected number of packets, the window, to be sent without having to wait for an ACK. Each packet receives a sequence number, and the ACKs send back that number. The protocol keeps track of which packets have been ACKed, and when they are received, sends more packets. In this way, the window slides along the stream of packets making up the transfer.

Sliding windows are a key part of many protocols. It is a key part of the TCP protocol, which inherently allows packets to arrive out of order, and is also found in many file transfer protocols like UUCP-g and ZMODEM as a way of improving efficiency compared to non-windowed protocols like XMODEM. See also SEAlink.

Basic concept

Conceptually, each portion of the transmission (packets in most data link layers, but bytes in TCP) is assigned a unique consecutive sequence number, and the receiver uses the numbers to place received packets in the correct order, discarding duplicate packets and identifying missing ones. The problem with this is that there is no limit on the size of the sequence number that can be required.

By placing limits on the number of packets that can be transmitted or received at any given time, a sliding window protocol allows an unlimited number of packets to be communicated using fixed-size sequence numbers. The term window on the transmitter side represents the logical boundary of the total number of packets yet to be acknowledged by the receiver. The receiver informs the transmitter in each acknowledgment packet the current maximum receiver buffer size (window boundary). The TCP header uses a 16 bit field to report the receiver window size to the sender. Therefore, the largest window that can be used is 2¹⁶ = 64 kilobytes.

In slow-start mode, the transmitter starts with low packet count and increases the number of packets in each transmission after receiving acknowledgment packets from receiver. For every ack packet received, the window slides by one packet (logically) to transmit one new packet. When the window threshold is reached, the transmitter sends one packet for one ack packet received.

If the window limit is 10 packets then in slow start mode the transmitter may start transmitting one packet followed by two packets (before transmitting two packets, one packet ack has to be received), followed by three packets and so on until 10 packets. But after reaching 10 packets, further transmissions are restricted to one packet transmitted for one ack packet received. In a simulation this appears as if the window is moving by one packet distance for every ack packet received. On the receiver side also the window moves one packet for every packet received.

The sliding window method ensures that traffic congestion on the network is avoided. The application layer will still be offering data for transmission to TCP without worrying about the network traffic congestion issues as the TCP on sender and receiver side implement sliding windows of packet buffer. The window size may vary dynamically depending on network traffic.

For the highest possible throughput, it is important that the transmitter is not forced to stop sending by the sliding window protocol earlier than one round-trip delay time (RTT). The limit on the amount of data that it can send before stopping to wait for an acknowledgment should be larger than the bandwidth-delay product of the communications link. If it is not, the protocol will limit the effective bandwidth of the link.

Motivation

In any communication protocol based on automatic repeat request for error control, the receiver must acknowledge received packets. If the transmitter does not receive an acknowledgment within a reasonable time, it re-sends the data.

A transmitter that does not get an acknowledgment cannot know if the receiver actually received the packet; it may be that it was lost or damaged in transmission. If the error detection mechanism reveals corruption, the packet will be ignored by the receiver and a negative or duplicate acknowledgement will be sent by the receiver. The receiver may also be configured to not send any acknowledgement at all. Similarly, the receiver is usually uncertain about whether its acknowledgements are being received. It may be that an acknowledgment was sent, but was lost or corrupted in the transmission medium. In this case, the receiver must acknowledge the retransmission to prevent the data being continually resent, but must otherwise ignore it.

Protocol operation

The transmitter and receiver each have a current sequence number n_t and n_r, respectively. They each also have a window size w_t and w_r. The window sizes may vary, but in simpler implementations they are fixed. The window size must be greater than zero for any progress to be made.

As typically implemented, n_t is the next packet to be transmitted, i.e. the sequence number of the first packet not yet transmitted. Likewise, n_r is the first packet not yet received. Both numbers are monotonically increasing with time; they only ever increase.

The receiver may also keep track of the highest sequence number yet received; the variable n_s is one more than the sequence number of the highest sequence number received. For simple receivers that only accept packets in order (w_r = 1), this is the same as n_r, but can be greater if w_r > 1. Note the distinction: all packets below n_r have been received, no packets above n_s have been received, and between n_r and n_s, some packets have been received.

When the receiver receives a packet, it updates its variables appropriately and transmits an acknowledgment with the new n_r. The transmitter keeps track of the highest acknowledgment it has received n_a. The transmitter knows that all packets up to, but not including n_a have been received, but is uncertain about packets between n_a and n_s; i.e. n_a ≤ n_r ≤ n_s.

The sequence numbers always obey the rule that n_a ≤ n_r ≤ n_s < n_t ≤ n_a + w_t. That is:

n_a ≤ n_r: The highest acknowledgement received by the transmitter cannot be higher than the highest n_r acknowledged by the receiver.
n_r ≤ n_s: The span of fully received packets cannot extend beyond the end of the partially received packets.
n_s < n_t: The highest packet received cannot be higher than the highest packet yet to be sent.
n_t ≤ n_a + w_t: The highest packet sent is limited by the highest acknowledgement received and the transmit window size.

Transmitter operation

Whenever the transmitter has data to send, it may transmit up to w_t packets ahead of the latest acknowledgment n_a. That is, it may transmit packet number n_t as long as n_t < n_a+w_t.

In the absence of a communication error, the transmitter soon receives an acknowledgment for all the packets it has sent, leaving n_a equal to n_t. If this does not happen after a reasonable delay, the transmitter must retransmit the packets between n_a and n_t.

Techniques for defining reasonable delay can be extremely elaborate, but they only affect efficiency; the basic reliability of the sliding window protocol does not depend on the details.

Receiver operation

Every time a packet numbered x is received, the receiver checks to see if it falls in the receive window, n_r ≤ x < n_r+w_r. (The simplest receivers only have to keep track of one value n_r=n_s.) If it falls within the window, the receiver accepts it. If it is numbered n_r, the receive sequence number is increased by 1, and possibly more if further consecutive packets were previously received and stored. If x > n_r, the packet is stored until all preceding packets have been received.^[1] If x≥n_s, the latter is updated to n_s=x+1.

If the packet's number is not within the receive window, the receiver discards it and does not modify n_r or n_s.

Whether the packet was accepted or not, the receiver transmits an acknowledgment containing the current n_r. (The acknowledgment may also include information about additional packets received between n_r and n_s, but that only helps efficiency.)

Note that there is no point having the receive window w_r larger than the transmit window w_t, because there is no need to worry about receiving a packet that will never be transmitted; the useful range is 1 ≤ w_r ≤ w_t.

Sequence number range required

So far, the protocol has been described as if sequence numbers are of unlimited size, ever-increasing. However, rather than transmitting the full sequence number x in messages, it is possible to transmit only x mod N, for some finite N. (N is usually a power of 2.)

For example, 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.

A stronger constraint is imposed by the receiver. The operation of the protocol depends on the receiver being able to reliably distinguish new packets (which should be accepted and processed) from retransmissions of old packets (which should be discarded, and the last acknowledgment retransmitted). This can be done given knowledge of the transmitter's window size. After receiving a packet numbered x, the receiver knows that x < n_a+w_t, so n_a > x−w_t. Thus, packets numbered x−w_t will never again be retransmitted.

The lowest sequence number we will ever receive in future is n_s−w_t

The receiver also knows that the transmitter's n_a cannot be higher than the highest acknowledgment ever sent, which is n_r. So the highest sequence number we could possibly see is n_r+w_t ≤ n_s+w_t.

Thus, there are 2w_t different sequence numbers that the receiver can receive at any one time. It might therefore seem that we must have N ≥ 2w_t. However, the actual limit is lower.

The additional insight is that the receiver does not need to distinguish between sequence numbers that are too low (less than n_r) or that are too high (greater than or equal to n_s+w_r). In either case, the receiver ignores the packet except to retransmit an acknowledgment. Thus, it is only necessary that N ≥ w_t+w_r. As it is common to have w_r<w_t (e.g. see Go-Back-N below), this can permit larger w_t within a fixed N.

Examples

The simplest sliding window: stop-and-wait

Although commonly distinguished from the sliding-window protocol, the stop-and-wait ARQ protocol is actually the simplest possible implementation of it. The transmit window is 1 packet, and the receive window is 1 packet. Thus, N = 2 possible sequence numbers (conveniently represented by a single bit) are required.

Ambiguity example

The transmitter alternately sends packets marked odd and even. The acknowledgments likewise say odd and even. Suppose that the transmitter, having sent an odd packet, did not wait for an odd acknowledgment, and instead immediately sent the following even packet. It might then receive an acknowledgment saying "expecting an odd packet next". This would leave the transmitter in a quandary: has the receiver received both of the packets, or neither?

Go-Back-N

Go-Back-N ARQ is the sliding window protocol with w_t>1, but a fixed w_r=1. The receiver refuses to accept any packet but the next one in sequence. If a packet is lost in transit, following packets are ignored until the missing packet is retransmitted, a minimum loss of one round-trip time. For this reason, it is inefficient on links that suffer frequent packet loss.

Ambiguity example

Suppose that we are using a 3-bit sequence number, such as is typical for HDLC. This gives N=2³=8. Since w_r=1, we must limit w_t≤7. This is because, after transmitting 7 packets, there are 8 possible results: Anywhere from 0 to 7 packets could have been received successfully. This is 8 possibilities, and the transmitter needs enough information in the acknowledgment to distinguish them all.

If the transmitter sent 8 packets without waiting for acknowledgment, it could find itself in a quandary similar to the stop-and-wait case: does the acknowledgment mean that all 8 packets were received successfully, or none of them?

Selective repeat

The most general case of the sliding window protocol is Selective Repeat ARQ. This requires a much more capable receiver, which can accept packets with sequence numbers higher than the current n_r and store them until the gap is filled in.

The advantage, however, is that it is not necessary to discard following correct data for one round-trip time before the transmitter can be informed that a retransmission is required. This is therefore preferred for links with low reliability and/or a high bandwidth-delay product.

The window size w_r need only be larger than the number of consecutive lost packets that can be tolerated. Thus, small values are popular; w_r=2 is common.

Ambiguity example

The extremely popular HDLC protocol uses a 3-bit sequence number, and has optional provision for selective repeat. However, if selective repeat is to be used, the requirement that n_t+n_r ≤ 8 must be maintained; if w_r is increased to 2, w_t must be decreased to 6.

Suppose that w_r =2, but an unmodified transmitter is used with w_t =7, as is typically used with the go-back-N variant of HDLC. Further suppose that the receiver begins with n_r =n_s =0.

Now suppose that the receiver sees the following series of packets (all modulo 8):

0 1 2 3 4 5 6 (pause) 0

Because w_r =2, the receiver will accept and store the final packet 0 (thinking it is packet 8 in the series), while requesting a retransmission of packet 7. However, it is also possible that the transmitter failed to receive any acknowledgments and has retransmitted packet 0. In this latter case, the receiver would accept the wrong packet as packet 8.

The solution is for the transmitter to limit w_t ≤6. With this restriction, the receiver knows that if all acknowledgments were lost, the transmitter would have stopped after packet 5. When it receives packet 6, the receiver can infer that the transmitter received the acknowledgment for packet 0 (the transmitter's n_a ≥1), and thus the following packet numbered 0 must be packet 8.

Extensions

There are many ways that the protocol can be extended:

The above examples assumed that packets are never reordered in transmission; they may be lost in transit (error detection makes corruption equivalent to loss), but will never appear out of order. The protocol can be extended to support packet reordering, as long as the distance can be bounded; the sequence number modulus N must be expanded by the maximum misordering distance.
It is possible to not acknowledge every packet, as long as an acknowledgment is sent eventually if there is a pause. For example, TCP normally acknowledges every second packet.
- It is common to inform the transmitter immediately if a gap in the packet sequence is detected. HDLC has a special REJ (reject) packet for this.
The transmit and receive window sizes may be changed during communication, as long as their sum remains within the limit of N. Normally, they are each assigned maximum values that respect that limit, but the working value at any given time may be less than the maximum. In particular:
- It is common to reduce the transmit window size to slow down transmission to match the link's speed, avoiding saturation or congestion.
- One common simplification of selective-repeat is so called SREJ-REJ ARQ. This operates with w_r=2 and buffers packets following a gap, but only allows a single lost packet; while waiting for that packet, w_r=1 and if a second packet is lost, no more packets are buffered. This gives most of the performance benefit of the full selective-repeat protocol, with a simpler implementation.

References

^ Peterson, Larry L. & Davie, Bruce S. "[1]", Morgan Kaufmann, 2000. ISBN 1-55860-577-0

Comer, Douglas E. "Internetworking with TCP/IP, Volume 1: Principles, Protocols, and Architecture", Prentice Hall, 1995. ISBN 0-13-216987-8

External links

RFC 1323 - TCP Extensions for High Performance
TCP window scaling and broken routers, 2004

[1] Peterson, Larry L. & Davie, Bruce S. "[1]", Morgan Kaufmann, 2000. ISBN 1-55860-577-0

[1]