Sliding Window Protocol
Encyclopedia
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
(OSI model
) as well as in the Transmission Control Protocol
(TCP).
Conceptually, each portion of the transmission (packets in most data link layers, but bytes in TCP) 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 of the size of the sequence numbers 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.
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
(RTT). 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.
A transmitter that does not hear an acknowledgment cannot know if the receiver actually received the packet; it may be that the packet was lost in transmission (or damaged; if error detection finds an error, the packet is ignored), or it may be that an acknowledgment was sent, but it was lost. In the latter case, the receiver must acknowledge the retransmission, but must otherwise ignore it.
Likewise, the receiver is usually uncertain about whether its acknowledgments are being received.
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 not 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 (wr=1), 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:
In the absence of a communication error, the transmitter soon receives an acknowledgment for all the packets it has sent, leaving na equal to nt. If this does not happen after a reasonable delay, the transmitter must retransmit the packets between na and nt.
Techniques for defining "reasonable delay" can be extremely elaborate, but they only affect efficiency; the basic reliability of the sliding window protocol does not depend on the details.
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. (The acknowledgment may also include information about additional packets received between nr or ns, but that only helps efficiency.)
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.
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. (N is usually a power of 2.)
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 (which should be accepted and processed) from retransmissions of old packets (which should be discarded, and the last acknowledgment retransmitted). This can be done given knowledge of the transmitter's window size. After receiving a packet numbered x, the receiver knows that x < na+wt, so na > 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 (less than nr) or that are too high (greater than or equal to ns+wr). 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 wr<wt (e.g. see Go-Back-N below), this can permit larger wt within a fixed N.
protocol is actually the simplest possible implementation of it. The transmit window is 1 packet, and the receive window is 1 packet. Thus, N=1+1=2 possible sequence numbers (conveniently represented by a single bit
) are required.
is the sliding window protocol with wt>1, 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.
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?
. 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.
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 (all modulo 8):
Because wr =2, the receiver will accept and store the final packet 0 (thinking it is packet 8 in the series), 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.
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.
Data transmission
Data transmission, digital transmission, or digital communications is the physical transfer of data over a point-to-point or point-to-multipoint communication channel. Examples of such channels are copper wires, optical fibres, wireless communication channels, and storage media...
protocols. Sliding window protocols are used where reliable in-order delivery of packets is required, such as in the Data Link Layer
Data link layer
The data link layer is layer 2 of the seven-layer OSI model of computer networking. It corresponds to, or is part of the link layer of the TCP/IP reference model....
(OSI model
OSI model
The Open Systems Interconnection model is a product of the Open Systems Interconnection effort at the International Organization for Standardization. It is a prescription of characterizing and standardizing the functions of a communications system in terms of abstraction layers. Similar...
) as well as in the Transmission Control Protocol
Transmission Control Protocol
The Transmission Control Protocol is one of the core protocols of the Internet Protocol Suite. TCP is one of the two original components of the suite, complementing the Internet Protocol , and therefore the entire suite is commonly referred to as TCP/IP...
(TCP).
Conceptually, each portion of the transmission (packets in most data link layers, but bytes in TCP) 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 of the size of the sequence numbers 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.
For the highest possible throughput
Throughput
In communication networks, such as Ethernet or packet radio, throughput or network throughput is the average rate of successful message delivery over a communication channel. This data may be delivered over a physical or logical link, or pass through a certain network node...
, it is important that the transmitter is not forced to stop sending by the sliding window protocol earlier than one round-trip delay time
Round-trip delay time
In telecommunications, the round-trip delay time or round-trip time is the length of time it takes for a signal to be sent plus the length of time it takes for an acknowledgment of that signal to be received...
(RTT). The limit on the amount of data that it can send before stopping to wait for an acknowledgment
Acknowledgment
Acknowledgment may refer to:*Acknowledgment , a statement of gratitude for assistance in producing a work...
should be larger than the bandwidth-delay product
Bandwidth-delay product
In data communications, bandwidth-delay product refers to the product of a data link's capacity and its end-to-end delay . The result, an amount of data measured in bits , is equivalent to the maximum amount of data on the network circuit at any given time, i.e. data that has been transmitted but...
of the communications link. If it is not, the protocol will limit the effective bandwidth
Bandwidth (computing)
In computer networking and computer science, bandwidth, network bandwidth, data bandwidth, or digital bandwidth is a measure of available or consumed data communication resources expressed in bits/second or multiples of it .Note that in textbooks on wireless communications, modem data transmission,...
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 the packet was lost in transmission (or damaged; if error detection finds an error, the packet is ignored), or it may be that an acknowledgment was sent, but it was lost. In the latter case, the receiver must acknowledge the retransmission, but must otherwise ignore it.
Likewise, the receiver is usually uncertain about whether its acknowledgments are being received.
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 not 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 (wr=1), 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 < na+wt.In the absence of a communication error, the transmitter soon receives an acknowledgment for all the packets it has sent, leaving na equal to nt. If this does not happen after a reasonable delay, the transmitter must retransmit the packets between na and nt.
Techniques for defining "reasonable delay" can be extremely elaborate, but they only affect efficiency; the basic reliability of the sliding window protocol does not depend on the details.
Receiver operation
Every time a packet numbered x is received, the receiver checks to see if it falls in the receive window, nr ≤ x < ns+wr. (The simplest receivers only have to keep track of one value nr=ns.) If it falls within the window, the receiver accepts it. If it is numbered nr, the receive sequence number is increased by 1, and possibly more if further consecutive packets were previously received and stored. If x > 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. (The acknowledgment may also include information about additional packets received between nr or ns, but that only helps efficiency.)
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
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 (which should be accepted and processed) from retransmissions of old packets (which should be discarded, and the last acknowledgment retransmitted). This can be done given knowledge of the transmitter's window size. After receiving a packet numbered x, the receiver knows that x < na+wt, so na > 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 (less than nr) or that are too high (greater than or equal to ns+wr). 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 wr<wt (e.g. see Go-Back-N below), this can permit larger wt within a fixed N.
The simplest sliding window: stop-and-wait
Although commonly distinguished from the sliding-window protocol, the stop-and-wait ARQStop-and-wait ARQ
Stop-and-wait ARQ is a method used in telecommunications to send information between two connected devices. It ensures that information is not lost due to dropped packets and that packets are received in the correct order. It is the simplest kind of automatic repeat-request method...
protocol is actually the simplest possible implementation of it. The transmit window is 1 packet, and the receive window is 1 packet. Thus, N=1+1=2 possible sequence numbers (conveniently represented by a single bit
Bit
A bit is the basic unit of information in computing and telecommunications; it is the amount of information stored by a digital device or other physical system that exists in one of two possible distinct states...
) are required.
Ambiguity example
The transmitter alternately sends packets marked "odd" and "even". The acknowledgments likewise say "odd" and "even". Suppose that the transmitter, having sent an odd packet, did not wait for an odd acknowledgment, and instead immediately sent the following even packet. It might then receive an acknowledgment saying "expecting an odd packet next". This would leave the transmitter in a quandary: has the receiver received both of the packets, or neither?Go-Back-N
Go-Back-N ARQGo-Back-N ARQ
Go-Back-N ARQ is a specific instance of the automatic repeat request protocol, in which the sending process continues to send a number of frames specified by a window size even without receiving an acknowledgement packet from the receiver...
is the sliding window protocol with wt>1, 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 ARQSelective Repeat ARQ
Selective Repeat ARQ / Selective Reject ARQ is a specific instance of the Automatic Repeat-Request protocol used for communications.-Concept:...
. 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
Bandwidth-delay product
In data communications, bandwidth-delay product refers to the product of a data link's capacity and its end-to-end delay . The result, an amount of data measured in bits , is equivalent to the maximum amount of data on the network circuit at any given time, i.e. data that has been transmitted but...
.
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 (all modulo 8):
- 0 1 2 3 4 5 6 (pause) 0
Because wr =2, the receiver will accept and store the final packet 0 (thinking it is packet 8 in the series), 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 (error detection makes corruption equivalent to loss), 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 after not receiving any packets for a while. 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 (reject) 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. In particular, it is common to reduce the transmit window size to slow down transmission to match the link's speed, avoiding saturationSaturation (telecommunications)In telecommunications, the term saturation has the following meanings:*In a communications system, the condition at which a component of the system has reached its maximum traffic-handling capacity...
or congestionNetwork congestionIn data networking and queueing theory, network congestion occurs when a link or node is carrying so much data that its quality of service deteriorates. Typical effects include queueing delay, packet loss or the blocking of new connections...
. - One common simplification of selective-repeat is so called SREJ-REJ ARQ. This operates with wr=2 and accepts following packets, but only allows a single lost packet; if a second packet is lost, no more packets are buffered. (I.e. wr=1 while waiting.) This gives most of the performance benefits of the full selective-repeat protocol, with a simpler implementation.
External links
- RFC 1323 - TCP Extensions for High Performance
- TCP window scaling and broken routers, 2004
- Sliding Window Demo (Flash required)
- Sliding Window Demo (ShockwaveMacromedia ShockwaveAdobe Shockwave is a multimedia platform used to add animation and interactivity to web pages. It allows Adobe Director applications to be published on the Internet and viewed in a web browser on any computer which has the Shockwave plug-in installed...
required) - TCP Sliding Window simulation (interactive animation)