08-02-2013, 04:53 PM
Sliding window protocol
Sliding window protocol.docx (Size: 347.76 KB / Downloads: 32)
INTRODUCTION:-
To guarantee lossless delivery, a unique (increasing) sequence number (ID) is attached to every message. The combination of the message's sender address and its ID identifies every message uniquely. To overcome message loss, sender and receiver agree on some start ID, e.g. TCP connection establishment involves the sender and receiver exchanging their start sequence numbers in the SYN/ACK packets. Now the IDs of messages received from a sender S always have to monotonically increase: if message 56 was received from S, the next message has to be 57. If a gap is detected, the receiver sends a retransmission request to the sender of the message. Upon receiving a retransmission request, the sender resends the message with the requested ID. Being able to resend old messages requires the senders to store recently sent messages for some time, usually until it is know that the receiver(s) has/have received all messages below a certain ID. In this case the messages below this ID may be deleted. When a receiver only sends retransmission requests when a gap is detected, the mechanism is called negative acknowledgment NAK. NAK is used in systems where message loss is infrequent, so NAKs would only rarely have to be used to retransmit lost messages.
When communication links are noisy and loss rate high, ACK schemes are preferred: a sender has to receive an acknowledgment from each receiver of a message. If ACKs are not received, the message is resent until an ACK has been received.
The idea of sliding windows is to keep track of the acknowledgements for each ID. However, a scheme in which a sender send a single message (e.g. to multiple receivers in a group) and then waits for all ACKs is to slow: a sender should be able to send a number of messages and a separate thread should receive ACKs, and resend messages with ACKs missing.
The senders and receivers each maintain a window of messages for which no ACKs have been received: a window is essentially a sequence of message IDs, starting with a low water mark and bounded by a high water mark. Whenever an ACK is received, the low and high water marks are advanced by 1, this allows 1 more ACK to be received, therefore sliding the window 1 to the right. When the window is full, an ACK is either discarded, or some kind of flow control is used to throttle the sender until there is more space available.
Sliding windows usually start out with a given size, however, more sophisticated protocols will dynamically adapt the window size, trying to find an agreed-upon size between sender and receiver.
The characteristics of sliding windows used at the sender and receiver usually involve (but do not have to !)
a. error correction (by retransmission),
b. flow control and
c. message ordering by sender (FIFO).
The latter property can easily be incorporated in a sliding window protocol, but sometimes, it is preferred to be implemented as a separate protocol for easier maintenance / replaceability.
Sliding window is used by most connection oriented network protocol, among others, the Point-to-Point protocol (PPP) which many people use to establish their home PC as temporary Internet node via a phone-line connection to an existing node. In fact, TCP also uses sliding window.
Sliding Window Protocols
Remember conventions DA, NA, DB, NB
Full duplex.
Data frames and ack frames going in same direction.
Tell difference using "kind" field in header.
Piggybacking
Instead of sending ack frame on its own, if there is an outgoing data frame in the next short interval, attach the ack to it (using "ack" field in header).
Better use of bandwidth. Ack is only a few bits (here 1 bit). Costly to have to construct an entire frame for it.
If no data frame going out after timeout, just send ack frame on its own.
Q. Can't just wait for next data frame to send ack. Why not?
assumes two-way communication (full duplex). It uses two types of frames:
1. Data
2. Ack (sequence number of last correctly received frame)
The basic idea of sliding window protocol is that both sender and receiver keep a ``window'' of acknowledgment. The sender keeps the value of expected acknowledgment; while the receiver keeps the value of expected receiving frame. When it receives an acknowledgment from the receiver, the sender advances the window. When it receives the expected frame, the receiver advances the window.
Sliding window size 1. Sequence nos. 0 to 7.
(a) At start. Receiver waits for 0.
(b) Sender sends 0.
© Receiver receives 0. Waits for 1.
(d) Sender got ack for 0. Hasn't got 1 from its Network layer yet.
More complex Data Link layer, as more freedom about the order in which it sends and receives frames.
Sender may have n unacknowledged frames at any time (window size n).
Needs n buffers to hold them all for possible re-transmit.
If window grows to its maximum size, DA must shut off NA.
This is all hidden from NB - still receives packets in exact same order.
1. Sender window might grow as it receives more frames to send and still has ones un-ack'ed.
Starts with nothing to send, then NA gives it frames to send.
Later, window may shrink as frames are ack-ed and NA has no more.
2. Receiver window constant size.
Receiver window size 1 means will only accept them in order.
Size n means will receive out of order (e.g. receive later ones after earlier frame is lost)
and then must buffer them before sending to NB (must send to NB in order).
e.g. DB has buffers to receive frames 0..7
Receives 1..7 in varying orders. Still waiting on 0. Can't send frames to NB yet.
0 got lost and was re-sent. Eventually gets 0.
Can now send all of 0..7 to NB
and re-use these slots.
e.g. consider frames numbered 0..7 but DB only has 2 buffers
Currently the sliding window is over 4,5
If get 4 can send it to NB and move window to 5,6
If get 5 have to wait for 4, then send both, and advance window to 6,7
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. The term "window" on 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 (window boundary). 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 (logically) 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 (before transmitting two packets, one packet ack has to be received), 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 (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.
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.[1] If x≥ns, the latter is updated to ns=x+1.