A sliding window protocol is a feature of packet-based data transmission
protocols. Sliding window protocols are used where reliable in-order delivery of
packets is required, such as in the Data Link Layer as well as in the
Transmission Control Protocol. Conceptually, each portion of the
transmission is assigned a unique consecutive sequence number, and the
receiver uses the numbers to place received packets in the correct order,
discarding duplicate packets and identifying missing ones. The problem
with this is that there is no limit on the size of the sequence number that can
be required. By placing limits on the number of
packets that can be transmitted or received at any given time, a sliding
window protocol allows an unlimited number of packets to be communicated
using fixed-size sequence numbers. The term "window" on the transmitter side
represents the logical boundary of the total number of packets yet to be
acknowledged by the receiver. The receiver informs the transmitter in each
acknowledgment packet the current maximum receiver buffer size. The TCP
header uses a 16 bit field to report the receive window size to the sender.
Therefore, the largest window that can be used is 216 = 64 kilobytes. In
slow-start mode, the transmitter starts with low packet count and increases the
number of packets in each transmission after receiving acknowledgment packets
from receiver. For every ack packet received, the window slides by one
packet to transmit one new packet. When the window threshold is reached, the
transmitter sends one packet for one ack packet received. If the window limit is
10 packets then in slow start mode the transmitter may start transmitting one
packet followed by two packets, followed by three packets and so on until 10
packets. But after reaching 10 packets, further transmissions are restricted to
one packet transmitted for one ack packet received. In a simulation this
appears as if the window is moving by one packet distance for every ack packet
received. On the receiver side also the window moves one packet for every packet
received. The sliding window method ensures that traffic congestion on the
network is avoided. The application layer will still be offering data for
transmission to TCP without worrying about the network traffic congestion
issues as the TCP on sender and receiver side implement sliding windows of packet
buffer. The window size may vary dynamically depending on network
traffic. For the highest possible throughput, it
is important that the transmitter is not forced to stop sending by the sliding
window protocol earlier than one round-trip delay time. The limit on the
amount of data that it can send before stopping to wait for an acknowledgment
should be larger than the bandwidth-delay product of the
communications link. If it is not, the protocol will limit the effective
bandwidth of the link. Motivation
In any communication protocol based on automatic repeat request for error
control, the receiver must acknowledge received packets. If the transmitter
does not receive an acknowledgment within a reasonable time, it re-sends
the data. A transmitter that does not hear an
acknowledgment cannot know if the receiver actually received the packet;
it may be that it was lost or damaged in transmission. If error detection reveals
corruption, the packet will be ignored by the receiver and no acknowledgement
will be sent. Similarly, the receiver is usually uncertain about whether its
acknowledgements are being received. It may be that an acknowledgment was sent,
but was lost or corrupted in the transmission medium. In this case, the
receiver must acknowledge the retransmission to prevent the data being
continually resent, but must otherwise ignore it.
Protocol operation The transmitter and receiver each have a
current sequence number nt and nr, respectively. They each also have a
window size wt and wr. The window sizes may vary, but in simpler implementations
they are fixed. The window size must be greater than zero for any progress to be
made. As typically implemented, nt is the next
packet to be transmitted, i.e. the sequence number of the first packet not
yet transmitted. Likewise, nr is the first packet not yet received. Both
numbers are monotonically increasing with time; they only ever increase.
The receiver may also keep track of the highest sequence number yet received;
the variable ns is one more than the sequence number of the highest sequence
number received. For simple receivers that only accept packets in order, this
is the same as nr, but can be greater if wr > 1. Note the distinction: all
packets below nr have been received, no packets above ns have been received, and
between nr and ns, some packets have been received.
When the receiver receives a packet, it updates its variables appropriately and
transmits an acknowledgment with the new nr. The transmitter keeps track of the
highest acknowledgment it has received na. The transmitter knows that all
packets up to, but not including na have been received, but is uncertain about
packets between na and ns; i.e. na ≤ nr ≤ ns.
The sequence numbers always obey the rule that na ≤ nr ≤ ns ≤ nt ≤ na + wt.
That is: na ≤ nr: The highest acknowledgement
received by the transmitter cannot be higher than the highest nr acknowledged
by the receiver. nr ≤ ns: The span of fully received
packets cannot extend beyond the end of the partially received packets.
ns ≤ nt: The highest packet received cannot be higher than the highest packet
sent. nt ≤ na + wt: The highest packet sent is
limited by the highest acknowledgement received and the transmit window size.
= Transmitter operation = Whenever the transmitter has data to
send, it may transmit up to wt packets ahead of the latest acknowledgment na.
That is, it may transmit packet number nt as long as nt nr, the packet is
stored until all preceding packets have been received. If x≥ns, the latter is
updated to ns=x+1. If the packet's number is not within the
receive window, the receiver discards it and does not modify nr or ns.
Whether the packet was accepted or not, the receiver transmits an acknowledgment
containing the current nr. Note that there is no point having the
receive window wr larger than the transmit window wt, because there is no
need to worry about receiving a packet that will never be transmitted; the
useful range is 1 ≤ wr ≤ wt. = Sequence number range required =
So far, the protocol has been described as if sequence numbers are of unlimited
size, ever-increasing. However, rather than transmitting the full sequence
number x in messages, it is possible to transmit only x mod N, for some finite
N. For example, the transmitter will only
receive acknowledgments in the range na to nt, inclusive. Since it guarantees
that nt−na ≤ wt, there are at most wt+1 possible sequence numbers that could
arrive at any given time. Thus, the transmitter can unambiguously decode the
sequence number as long as N > wt. A stronger constraint is imposed by the
receiver. The operation of the protocol depends on the receiver being able to
reliably distinguish new packets from retransmissions of old packets. This can
be done given knowledge of the transmitter's window size. After
receiving a packet numbered x, the receiver knows that x x−wt. Thus,
packets numbered x−wt will never again be retransmitted.
The lowest sequence number we will ever receive in future is ns−wt
The receiver also knows that the transmitter's na cannot be higher than
the highest acknowledgment ever sent, which is nr. So the highest sequence
number we could possibly see is nr+wt ≤ ns+wt.
Thus, there are 2wt different sequence numbers that the receiver can receive at
any one time. It might therefore seem that we must have N ≥ 2wt. However, the
actual limit is lower. The additional insight is that the
receiver does not need to distinguish between sequence numbers that are too
low or that are too high. In either case, the receiver ignores the packet
except to retransmit an acknowledgment. Thus, it is only necessary that N ≥
wt+wr. As it is common to have wr1, but a fixed wr=1. The receiver refuses to
accept any packet but the next one in sequence. If a packet is lost in
transit, following packets are ignored until the missing packet is
retransmitted, a minimum loss of one round trip time. For this reason, it is
inefficient on links that suffer frequent packet loss.
Ambiguity example Suppose that we are using a 3-bit
sequence number, such as is typical for HDLC. This gives N=2³=8. Since wr=1, we
must limit wt≤7. This is because, after transmitting 7 packets, there are 8
possible results: Anywhere from 0 to 7 packets could have been received
successfully. This is 8 possibilities, and the transmitter needs enough
information in the acknowledgment to distinguish them all.
If the transmitter sent 8 packets without waiting for acknowledgment, it
could find itself in a quandary similar to the stop-and-wait case: does the
acknowledgment mean that all 8 packets were received successfully, or none of
them? = Selective repeat =
The most general case of the sliding window protocol is Selective Repeat ARQ.
This requires a much more capable receiver, which can accept packets with
sequence numbers higher than the current nr and store them until the gap is
filled in. The advantage, however, is that it is
not necessary to discard following correct data for one round-trip time
before the transmitter can be informed that a retransmission is required. This
is therefore preferred for links with low reliability and/or a high
bandwidth-delay product. The window size wr need only be larger
than the number of consecutive lost packets that can be tolerated. Thus,
small values are popular; wr=2 is common.
Ambiguity example The extremely popular HDLC protocol uses
a 3-bit sequence number, and has optional provision for selective repeat.
However, if selective repeat is to be used, the requirement that nt+nr ≤ 8
must be maintained; if wr is increased to 2, wt must be decreased to 6.
Suppose that wr =2, but an unmodified transmitter is used with wt =7, as is
typically used with the go-back-N variant of HDLC. Further suppose that
the receiver begins with nr =ns =0. Now suppose that the receiver sees the
following series of packets: 0 1 2 3 4 5 6 0
Because wr =2, the receiver will accept and store the final packet 0, while
requesting a retransmission of packet 7. However, it is also possible that the
transmitter failed to receive any acknowledgments and has retransmitted
packet 0. In this latter case, the receiver would accept the wrong packet
as packet 8. . The solution is for the transmitter to limit wt ≤6. With this
restriction, the receiver knows, after receiving packet 6, that the
transmitter's na ≥1, and thus the following packet numbered 0 must be
packet 8. If all acknowledgements were lost, then the transmitter would have to
stop after packet 5. Extensions
There are many ways that the protocol can be extended:
The above examples assumed that packets are never reordered in transmission;
they may be lost in transit, but will never appear out of order. The protocol
can be extended to support packet reordering, as long as the distance can
be bounded; the sequence number modulus N must be expanded by the maximum
misordering distance. It is possible to not acknowledge every
packet, as long as an acknowledgment is sent eventually if there is a pause. For
example, TCP normally acknowledges every second packet.
It is common to inform the transmitter immediately if a gap in the packet
sequence is detected. HDLC has a special REJ packet for this.
The transmit and receive window sizes may be changed during communication, as
long as their sum remains within the limit of N. Normally, they are each
assigned maximum values that respect that limit, but the working value at any
given time may be less than the maximum. In particular:
It is common to reduce the transmit window size to slow down transmission to
match the link's speed, avoiding saturation or congestion.
One common simplification of selective-repeat is so called SREJ-REJ
ARQ. This operates with wr=2 and buffers packets following a gap, but only allows
a single lost packet; while waiting for that packet, wr=1 and if a second packet
is lost, no more packets are buffered. This gives most of the performance
benefit of the full selective-repeat protocol, with a simpler implementation.
See also Federal Standard 1037C
Compound TCP Serial number arithmetic
References Comer, Douglas E. "Internetworking with
TCP/IP, Volume 1: Principles, Protocols, and Architecture", Prentice Hall, 1995.
ISBN 0-13-216987-8 Peterson, Larry L. & Davie, Bruce S.
"Computer Networks: A Systems Approach", Morgan Kaufmann, 2000. ISBN 1558605142
External links RFC 1323 - TCP Extensions for High
Performance TCP window scaling and broken routers,
2004 Sliding Window Demo