Sliding Window Mechanism in Data Transmission

Silan Liu

Sliding window is a flow control technique which belongs to the Data Link layer of the OSI model. It solves the problem of missing frames during data transmission between two upper layers, so that they can send and receive frames in order.

Two Acknowledgement Schemes

In sliding window mechanism, receiver sends out acknowledgement to sender to notify of receiving or missing of frames. There are two acknowledgement schemes.

ACK scheme is used on a noisy link, in which receiver sends an ACK for every frame received (note that when the receiver sends an acknowledge for frame s, this is understood to mean that all frames up to and including s have been received).

NAK (negative acknowledgement) is used on a reliable link on which message loss is not frequent. In this scheme receiver only sends an ACK for a lost frame.

Sliding Window

With a stop-and-wait protocol, the sender waits for an acknowledgment after transmitting every frame. As a result, there is at most a single outstanding frame on the channel at any given time, which may be far less than the channel's capacity. For maximum throughput, the amount of data in transit at any given time should be (channel bandwidth) * (channel delay).

The key feature of the sliding-window protocol is that it permits pipelined communication to better utilize the channel capacity. The sender can send a maximum N frames without acknowledgement. N is called the window size of the sliding window. The sliding window maps to the frames in sender’s buffer that are to be sent, or have been sent and now are just waiting for acknowledgement.

The sender assigns a sequence number to each frame. At any time, the sender maintains the list of sequence numbers corresponding to frames it is permitted to send. For example, TCP connection establishment involves the sender and receiver exchanging their start squence numbers in the SYN/ACK packets

Since frames currently within the sender's window may ultimately be lost or damaged in transit, the sender must keep all these frames in its memory for possible retransmission. Thus, the sender must have a buffer of at least the size of the sliding window.

The sender records the time at which each packet is sent. If the sender does not receive an acknowledgment for a frame after timeout, it retransmits the this frame.

For a receiver using selective repeat, the sliding window is the group of frames that its receiving buffer maps to. A receiver using Go-back-N does not have a buffer and thus does not have a concept of window.

Sophisticated protocols can dynamically adapt the window size, trying to find a size suitable for both sender and receiver. Receiver can indicate the new desired window size in the acknowledgement.

All following examples uses a window size of 8.

Receiver Logic in Go-back-N

In Go-back-N, receiver does not need a buffer.

When it first receives frame 0, it pass it on to higher protocol and returns ACK0 to sender. Then it receives 1, 2, 3, 4 and does the same thing. After it receives 4, it receives 6, and it knows that frame 5 is missing. So it will discard frame 6 and all later frames (7, 0, 1, ..), until it receives frame 5.

Receiver Logic in Selective Repeat

In Selective Repeat, receiver has a buffer of the window size to cope with out-of-order frames. It always tries to pass on as many frames as possible in the buffer to higher protocol layer.

Suppose the receiver has just passed on frame 4, and the buffer is now empty. Now frame 5 arrives. It will pass it on straight-away and returns ACK5 to sender. Then comes frame 6, 7, 0, 1, 2, 3 and it does the same thing. The buffer is kept empty.

After frame 3 arrives, there comes frame 5, and the receiver knows that frame 4 is missing. It will not directly pass frame 5 on, nor will it discard it. Instead it puts frame 5 in the second place in the buffer, and returns ACK5. When later frames arrives, the receiver puts them sequentially in the buffer and returns ACK for each of them, until the buffer is full. Then it will discard all following frames and do not acknowledge them. All through this process it will not pass on any frame until the first missing one arrives. Suppose in the following frames 1 is missing and all others arrive, the buffer will be as follow:

| - | 5 | 6 | 7 | 0 | - | 2 | 3 |

When frame 4 is resent and finally arrives, the receiver will pass on all frames up to the next empty place, and shift the rest including the empty one to the beginning of the buffer:

| - | 2 | 3 | - | - | - | - | - |

Later arrived frames will be filled in the following empty places, until the buffer is full or the empty/missing one is received.

This way the sender needs to send only the missing frame, and the receiver can still pass on frames in order.

Sender Logic

After sender sends out its full window, it waits for ACK. If it has received ACK for all frames up to frame n, it will move its window to contain following frames, so that the first frame in the window is frame (n + 1). Then it sends out all unsent frames in this window and waits for new ACK.

Suppose sender has sent out its full window 0 ~ 7 and is now waiting for ACK, and frame 3 is lost. It will first receive ACK 0, 1, 2, and it moves its window to 3, 4, 5, 6, 7, 0, 1, 2 and sends unsent frames 0, 1, 2, and continue to wait. Suppose 0, 1, 2 is received by the receiver.

If it is Go-back-N, it will not receive any more ACK after ACK 0, 1, 2. After time out, it knows that frame 3 and all following frames are lost. So it will resend all frames in the window: 3, 4, 5, 6, 7, 0, 1, 2.

If it is Selective Repeat, it will receive ACK 4, 5, 6, 7, 0, 1, 2 after receiving ACK 2. It will not move window because the first frame in the window (frame 3) hasn’t been acknowledged. It will just wait until time out. Then it knows that frame 3 is missing, so it will resend frame 3 only, and continue to wait, until ACK 3 is received or timeout again. Then the content of the whole window has been acknowledged. It will move to next window and send the 8 new frames.

Overview

Selective repeat ARQ is seldom used because of its requirement on receiver’s buffer.