Sliding Window Protocol


The sliding window protocol is a useful protocol in network communications. Many important protocol such as TCP, SPX etc, carry the idea of Sliding window protocol. The sliding window protocol provides flow control in data communication over an unreliable connection. The key feature of the sliding window protocol is that it permits pipelined communication. In contrast, with a simple 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 equal to (channel bandwidth) X (channel delay).

Originally, the TFTP protocol use a stop and wait protocol. This is a simple but not efficient protocol. In my project I tried to modify it to be a go back N sliding window protocol and made some statistics.

 

There are three types of Sliding Window protocols. The three differ among themselves in terms of efficiency, complexity, and buffer requirements. In all sliding window protocols, each outbound frame contains a sequence number, ranging from 0 up to some maximum. The maximum is usually 2n-1 so the sequence number fits nicely in an n-bit field. The essence of all sliding window protocols is that at any instant of time, the sender maintains a set of sequence number corresponding to frames it is permitted to send. These frames are said to fall within the sending window. Similarly there is a receiving window corresponding to the set of frames it is permitted to accept on receiver side.

Generally speaking, the Sliding window protocol works this way:

The sequence number within the senderís window, represent frames sent out but as yet not acknowledged. Whenever a new packet arrives from the network layer, it is given the next highest sequence number, and the upper edge of the window is advanced by one. When an acknowledgment arrives, the lower edge of the window is advanced by one. So the window continuously maintain a list of unacknowledgement frames.

Since frame 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 if the window size is n, the sender needs n buffers to hold all unacknowledgement frames. If the window ever grows to its maixmum size, the sender must forcibly shut off the network layer until another buffer becomes free.

The receiving data link layerís window corresponds to the frames it may accept. Any frame falling outside the window is discarded without comment. Only the packets with sequence number fall in the receiverís window size is accepted. And an acknowlegment will be generate accordingly. Other packets will be discarded. If the receiverís window size is equal to 1, the receiver will only accept frames in order.

The most complicate sliding window protocol is Selective Repeat. Both sender and receiver maintains a window which size is greater than 1. Because the receiver has a window size greater than 1, that means the receiver can accept frames out of order as long as the sequence number is within the window. So certain method has to be applied to send ordered frame to upper layer.

The most simply sliding window protocol is that the window size equal to 1. This is stop and wait protocol. Which is used in TFTP protocol. I enhanced my TFTP program by using a go back N protocol instead of stop and wait protocol. To provide a higher efficiency.

In go back n protocol, the senderís window size is greater than 1. The receiverís window size is 1. So the sender can send multiple frames before it receives an ackolegement. The receiver will discards all frames which sequence number is greater than the next one. If the expected frame lost during transmission, the sender will eventually get a time out event and retransmit this frame and flowing frame.