sweedler@yale.UUCP (05/15/87)
I got enough requests for an explanation of sliding window protocols to
make a news posting, so here it is. Sorry for the delay. Here is what I
considered the best explanation of sliding window protocols (along with
a few miscellaneous comments from other people).
A "sliding window protocol" is a subspecies of packet
protocols. Suppose two machines, S (sender) and R (receiver).
A message is broken into packets of, say, 512 bytes. For each
packet, S prepends a serial number, and sends it. When R receives
it, it sends back an 'acknowledgement', containing the sequence
number of the packet it just got. S does not send another packet
until it gets the ACK for the current packet.
That would be a typical packet protocol. Of course, a packet
could get lost in transit. Suppose packet 473 gets lost on the
way to R. After a time, S doesn't see an ACK for packet 473, so
it sends packet 473 again. In this way, packet protocols ensure
that the whole message gets through.
Problem, though, is that the ACK for 473 may just have been
delayed. So we implement a "sliding window protocol", with a
window size of, say, 10 packets. In this protocol, after S sends
packet 473, it goes right on and sends 474, and 475, and so on up
to 482. If S hasn't got an ACK for 473 by then, it must wait
until the ACK arrives, or until S times out and retransmits 473.
This scheme makes better use of available time.
(Look closely, and you'll see that the original protocol is
really a "sliding window protocol" with a window size of 1
packet.)
There are several improvements that can be made. First, it's
not necessary to send an individual ACK message for every packet R
receives. It could just send one ACK, for the highest packet
number received correctly. Suppose, in the previous example, that
all packets 473 to 482 except 480 get through. R sends an ACK for
479. S continues sending packets up to 489, but times out. R is
still looking for 480. So S resends 480 (and 481...), and R ACKs
480.
This is the type of protocol that UUCP uses. The window size
is (normally) 3, but some sites have raised it. The sequence
numbers in UUCP range from 0 to 7, so the maximum window size is
7. (You must always have one valid sequence number that is
outside of the current window.)
Note, though, that this requires a retransmission of all
packets in the window when one packet is dropped. We can add
"negative acknowledgements" (NAK) to the protocol. With this,
when 480 is dropped (but everything up to 482 has been sent), R
sends out NAK-480 ACK-482. S resends 480, then continues on with
483. 481 and 482 do not need to be resent. This scheme requires
that the receiver maintain buffer space to reassemble the message,
since packets can now arrive out of sequence.
This is, obviously, a very shallow treatment of what can be a
full semester course. Consult the college library for a book on
the subject. It's not hard in theory, but there are a tremendous
number of perverse failures that can cause everything from delay
to total collapse.
---
David S. Hayes, The Merlin of Avalon PhoneNet: (202) 694-6900
UUCP: *!seismo!sundc!hqda-ai!merlin ARPA: merlin%hqda-ai.uucp@brl.arpa
Andrew Tanenbaum's textbook "Computer Networks" (Prentice-Hall) is a good
book to consult.
---
Bennett Todd, Duke User Services, Durham, NC 27706-7756; +1 919 684 3695
UUCP: ...{philabs,akgua,decvax,ihnp4}!mcnc!ecsvax!dukeac!bet
BITNET: DBTODD@TUCC
Sliding window protocols are especially good when the round trip
time is large (ie with sattelites) since you just keep sending
packets and assume the receiver has gotten them. The optimum window
size is twice the number of packets that can be sent before a nak
could ever be seen.
---
Jim Prescott rochester!moscom!jgp
--
UUCP: ...!{seismo,decvax}!yale!sweedler
ARPA: sweedler@yale.arpa Jonathan Sweedler
BITNET: sweedler@yalecs.bitnet