sliding window

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 is transmitted. Throughout the communication, it maintains the send window size, the last acknowledgment received, and the last frame sent. To ensure that the window does not overflow, the sender ensures that the window size is greater than the sequence number of last frame sent minus the sequence number last acknowledgment received.

When the sender transmits a frame, it increments the sequence number by one and starts a timer. The sequence number is sent with the frame so that 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 large as the send window size. The sender then waits until it receives acknowledgments before transmitting more frames.

Whenever the sender receives an acknowledgment from the receiver, it increments the value of the last acknowledgement received, thereby sliding the "sliding window" to the right. If the timer for the frame expires before the sender receives an acknowledgment for the frame, it assumes 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 if it falls within the receiver's window. The size of the receiver's window is determined 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 exists between 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 frame was 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 the intervening frames in the sequence arrive .

Variants

There are two variants:

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

Search another word or see sliding windowon Dictionary | Thesaurus |Spanish
Copyright © 2014 Dictionary.com, LLC. All rights reserved.
  • Please Login or Sign Up to use the Recent Searches feature
FAVORITES
RECENT

;