Sliding Window is an
algorithm used in
TCP for
reliable data transfer over an
unreliable network (such as the
Internet).
The algorithm is similar to Stop and Wait. However, Stop and Wait is rather simplistic, as you can only have one packet in transit at once. Sliding Window allows multiple packets to be in transit at once.
Transmission
Suppose we are sending a stream of data to a remote machine (eg.
uploading a file). We have some packets in transit which we have sent. This can be seen as a
window on the stream, the window being the range of data we are currently sending.
Suppose we have reached position 1000 in the stream, and our window size is 1000. Then our send window might look like this:
1000 2000
==================(=============)=================
past data window future data
When the remote machine receives data, it sends back an
ACK, containing the position it has reached in the stream. This allows us to advance our window. For example, suppose we get an ACK up to position 1200, then our window would now look like this:
1200 2200
=====================(=============)=================
past data window future data
We can now send more data to the remote machine as our window advances. If we do not receive an ACK for a packet, we
resend the data until we do.
The window allows us to send more than one packet at once, which increases throughput drastically. However, we have to be careful not to send more than data than we can send due to channel capacity. Setting a maximum window size allows us to control this.
Receiving
On the
receiving end, we have a
receive window. This is a
buffer into which we place data as it arrives. If we have data at the start of the buffer, we can advance the stream and send an
ACK to the sender (though, if we receive
duplicated data from before the start of the receive window, we must also send an ACK, as it is possible this means our previous ACK was lost).
The receive window allows the system to deal with out of order packets. There is no guarantee with IP that packets will arrive in the order they were sent, so this is important.
When the receiver sends an ACK, it also sends a window advertisement. This allows flow control. Data is typically read into the receive window by the Operating System, and a user program then reads data out of the buffer. However, if the program stops reading data for some reason, it is important to be able to stop the stream from sending more data until it does. It works something like this:
1000 2000
=============( )
old data receive window
data is received:
1000 1200 2000
=============(#### )
old data receive window
ACK up to 1200 is sent, with window advertisement as 800. The
sender then sets their send window size to be a maximum of 800.
Program reads data out of buffer, and window advances (we could now send a window advertisement of 1000):
1200 2200
==================( )
old data receive window
If the program stops reading data out of the buffer, the buffer will steadily fill up, but the send window size will eventually decrease to 0. This stops the sender from sending more data than the receiver can fit in its buffers.
Conclusion
Sliding Window is good because it allows throughput to be increased up to the full channel capacity, while maintaining the
self clocking nature of Stop and Wait. Furthermore, it is able to deal with the fact that on
the Internet you cannot rely on packets arriving in the order they were sent.