Sliding window

From Wikipedia, the free encyclopedia

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 acknowledgement is received or before a specified event occurs.

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

For example, supposing a fixed window size of $m$ packets, a sender may send out packets $[n \ldots (n+m-1)]$ before receiving any acknowledgement. If acknowledgement arrives from the receiver for packet $n$ , then the range (window) of unacknowledged packets slides to $[(n+1) \ldots (n+m)]$ , and the sender is able to send out packet $(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, $2 m$ packets and $2 m$ 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 packets 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.

[edit] Sliding Window Algorithm

The sliding window algorithm allows for efficient stream transmission. Without the use of the sliding window algorithm, the sender must wait until it receives an acknowledgment for each frame from the receiver before transmitting the next frame. This is extremely inefficient. A well tuned sliding window protocol will keep the network saturated with packets. (Comer, 1995)

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 it does not overflow the window, to ensures that the window size is greater than the last frame sent minus the last acknowledgment received.

When the sender transmits a frame, it increments the last frame sent by one and start a timer. The frame is sent with the sequence number so that the receiver knows which frame to acknowledge when it receives it. It continues this until the buffer of unacknowledged frames is as large as the send window size, at which point it 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 acknowledgment 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 largest acceptable frame, and the last frame received.

When a frame arrives, the receiver evaluates the frame to determine if it is outside of the receiver's window. If the sequence number is either higher than the largest acceptable frame or it is less than or equal to the last frame received, it considers it outside the window and discards it. Otherwise, it accepts it.

When it accepts the frame, the receiver decides if it should send an ACK to the sender. The receiver keeps track of the highest unacknowledged sequence number for which all frames with lower sequence numbers have already been acknowledged. If the incoming frame is equal to this value, it sends an acknowledgment. Once it sends out the ACK, it updates its value for the last frame received with the recently acknowledged frame's sequence number, and updates the largest acceptable frame. This slides the window on the receiver side.

Otherwise, the frame arrived out of sequence and it waits until the proper frame arrives. (Peterson & Davie, 2000)