Sliding Window Protocol

Sliding Window Protocol is a bi-directional data transmission protocol in the data link layer (OSI model). It is used to keep a record of the frame sequences sent and their respective acknowledgements received by both the users.

In transmit flow control, sliding window is a variable-duration window that allows a sender to transmit a specified number of data units before an acknowledgment is received or before a specified event occurs.

An example of a sliding window is one in which, after the sender fails to receive an acknowledgment for the first transmitted frame, the sender "slides" the window, i.e. resets the window, and sends a second frame. This process is repeated for the specified number of times before the sender interrupts transmission. Sliding window is sometimes (loosely) called "acknowledgment delay period".

For example, supposing a fixed window size of $m$ frames, a sender may send out $m$ frames ($[n\; ldots\; (n+m-1)]$) before receiving any acknowledgment. If acknowledgment arrives from the receiver for packet $n$, then the range (window) of unacknowledged frames slides to $[(n+1)\; ldots\; (n+m)]$, and the sender is able to send out frame $(n+m)$. In some way, "sliding" signifies a FIFO operation, trimming the range at one end, extending it at the other end.

The purpose of the sliding window is to increase throughput. Let's denote the round trip time with RTT. The time necessary to transfer and acknowledge $K$ (a big number of) packets is roughly $operatorname\{RTT\}\; cdot\; K/(2m)$ (in one round trip, $2m$ frames and $2m$ ACKs are delivered). However, the size of the window (in bytes) should not grow above "capacity of the path" (the sum of affected network buffer sizes of all hops along the path): windows that are too big do not increase throughput; they only increase latency, the number of frames transmitted out-of-order, and memory usage.

In practice, protocols often adapt the window size to the link's speed and actual saturation or congestion.

Concept

At any instant of time, the sender maintains a set of sequence numbers which correspond to the frames it is permitted to send. Such frames are said to be a set of the "sending window". Similarly, the receiver also maintains a "receiving window" which indicates the set of frames it is allowed to receive.

A window can be visualised as a circle divided into $(2^n)\; -\; 1$ parts where n is the number of bits required to represent, in binary, the maximum sequence number in a given sequence of packets.

The upper and lower edges of a sending window indicate the set of packets which are allowed to be sent but have not been acknowledged. The upper and lower edges of a receiving window indicate the set of packets it may accept.

Whenever the network layer sends a new frame, the upper edge of the sending window is advanced by one. As shown in the figure, when a new frame is sent from the network layer to the data link layer, the upper edge of the window advances to 1 which indicates that the data link layer is allowed to send the 0th and 1st frames as they are still unacknowledged. On receiving the 0th frame the receiving window in the data link layer of the recipient advances its lower edge by one indicating it has received the 0th frame and the recipient sends an acknowledgement. On receiving the acknowledgement, the sending window advances its lower edge by one, indicating that the transmission and subsequent reception of the 0th frame is complete.

Sliding Window Algorithm

The sliding window algorithm works as follows:

First, the sender creates a sequence number for each frame as it istransmitted. Throughout the communication, it maintains the "send window size", the "last acknowledgment received", and the "last frame sent". Toensure that the window does not overflow, the sender ensures that the windowsize is greater than the sequence number of last frame sent minus the sequence number last acknowledgmentreceived.

When the sender transmits a frame, it increments the sequence number byone and starts a timer. The sequence number is sent with the frame sothat the receiver can detect if a frame is received out of order. The sender continues sending frames until the buffer of unacknowledged frames is as largeas the send window size. The sender then waits until it receivesacknowledgments before transmitting more frames.

Whenever the sender receives an acknowledgment from the receiver, itincrements the value of the last acknowledgement received, therebysliding the "sliding window" to the right. If the timer for the frameexpires before the sender receives an acknowledgment for the frame, itassumes that the frame was lost and retransmits it.

The receiver holds onto three pieces of information as well: the"receive window size", the "last frame received", and the "next frame to acknowledge".

When a frame arrives, the receiver evaluates the frame to determine ifit falls within the receiver's window. The size of the receiver's window isdetermined by the number of frames the receiver can buffer before overflowing. The receiver can not process frames received out of order. A frame is out of order if a gap existsbetween the sequence numbers of the newly received frame and that of the last frame received.

If a frame is received with a sequence number that results in a gap larger than the size of the receiver's window, the frame is determined to be outside the window and is discarded. If a frame is received with a sequence number that is lower than or equal to that of the last frame received,this frame is by definition outside the window and must be a duplicate. It is also discarded.Packets with sequence numbers that fall within the window are accepted and put into the buffer.

After accepting the frame, the receiver again checks the sequence number to determine if the framewas received in the correct order. The receiver compares the incoming frame's sequence number to "next frame to acknowledge" sequence number. If they match the receiver sends an acknowledgment. The "next frame to acknowledge" and "last frame received" are both incremented, thus sliding the window along.

Frames which are within the window but arrived out of sequence remain in the buffer until theintervening frames in the sequence arrive. [Peterson, Larry L. & Davie, Bruce S. "Computer Networks: A Systems Approach", Morgan Kaufmann, 2000. ISBN 15586051428888]

Variants

There are two variants:
* Go back n
* Selective repeat (aka selective reject)

Go back n corresponds to the example above where the receiver's window size is one (the sender's window size is greater than one otherwise it's a trivial case). In this case, if an error occurs in receiving the nth frame the receiver simply discards subsequent frames and does not send the acknowledgement corresponding to the nth frame. This compels the sender to resend all frames starting with the nth and thereafter. This deteriorates the data rate.

In selective repeat, the receiver's window size is more than one, and the receiver can receive a fixed number of out of order frames equal to the window size. If a frame is received with an error it simply sends a 'negative acknowledgement' signal corresponding to the faulty frame prompting the sender to resend the frame. In the meantime, the recipient can store the subsequent frames, which have already been sent, in a buffer and wait for the remaining frame to be received. Once received, the frames are transferred in sequence to the network layer.

References

*Comer, Douglas E. "Internetworking with TCP/IP, Volume 1: Principles, Protocols, and Architecture", Prentice Hall, 1995. ISBN 0132169878
*Peterson, Larry L. & Davie, Bruce S. "Computer Networks: A Systems Approach", Morgan Kaufmann, 2000. ISBN 15586051428888

See also

* Federal Standard 1037C
* RFC 1323 - TCP Extensions for High Performance
* [http://lwn.net/Articles/92727/ TCP window scaling and broken routers] , 2004
* [http://www2.rad.com/networks/2004/sliding_window/ Sliding Window Demo] (Flash required)
* [http://www.humboldt.edu/~aeb3/telecom/SlidingWindow.html Sliding Window Demo] (Shockwave required)
* [http://www.netbook.cs.purdue.edu/anmtions/anim20_3.htm Yet Another TCP sliding window demo]
* [http://www.osischool.com/protocol/Tcp/slidingWindow/index.php Interactive sliding window demo]