Some notes on sliding windows

This is covered in section 2.5 of Peterson & Davie.  There are some
confusing points there, and also some typographical errors, and the
purpose of this note is to make the section clearer.

But first of all, here's a SIMPLIFIED VIEW.
The idea of sliding windows is simply to have multiple
packets "in flight" at the same time, at different
points along the path. Assume for the moment that the
sender window size (SWS) is 10, and that the sender
is in fact able to keep 10 packets "en route" at any
given time. This means that, during one RTT, 10 packets
will be delivered, for potentially tenfold more bandwidth
than with stop-and-wait, where during each RTT only one
packet is delivered. (Potentially, since it is possible
that the packets "en route" are all queued up somewhere,
and thus RTT has been artificially inflated.)

One way for 10 packets to be all in transit at the same time
is for there to be four routers in between the sender and
receiver:

	sender----R1----R2----R3----R4----receiver

There are thus five links. At a given instant, five data
packets can be simultaneously going from sender to receiver,
one on each link, and five returning ACK packets can be 
simultaneously going in the other direction, again one per link,
for a total of ten packets in flight.

(Some link types do support multiple packets on *one* link at a time, too.)

Another way to visualize this is to think of hauling water in 
buckets, say from a pond to a fire. Suppose it takes 10 seconds
to walk there and back, ie RTT=10. One person alone can deliver
1 bucket every 10 seconds. But 10 people, all simultaneously
in transit (but in an orderly line) can deliver 10 buckets
in 10 seconds; at any instant, 5 full buckets are heading out
and 5 empties are coming back.

==============

Now for the details. The material in the book on page 106 is 
pretty accurate for the sender; the sender is allowed to have
up to SWS packets "in flight", that is, sent but not yet
acknowledged. SWS=1 is stop-and-wait; SWS=infinity means 
send the entire file, in effect, before requiring an ACK.

The three variables involved are
	SWS	sender window size, fixed (generally)
	LAR	last ack received, just below "bottom" of window
	LFS	last frame sent, "top" of window

One source of confusion, though, is whether the sender actually 
*does* have SWS packets in flight; it may have "up to" SWS packets
in flight. In general it does indeed have the max quota of SWS many,
except for brief intervals immediately after an ACK arrives but before
the next corresponding data packet (one windowful later in sequence)
can be sent. If we assume that the sender always responds "instantaneously"
to new opportunities to send, then the first inequality on page 106
becomes an equality:

	LFS - LAR = SWS (versus <= in the text)

that is, the sender has always sent SWS packets ahead of the last one
ACKed, numbered LAR+1, LAR+2, ..., LAR+SWS (the last is equal to LFS).

==============

For the receiver, there are some typos, and there's also the issue
that the receiver is "passive", and doesn't have to *do* anything
(involving the network) in order to update its window. (It has to 
send an ACK, but technically that can be done before or after the
window update). So there's no issue of whether the receiver responds
"instantaneously"; it does so simply by updating LFR. For what it's worth, 
the receiver end is less crucial; one simplified way of thinking about 
the receive window is that the receiver maintains RWS many buffers, 
in order to accept out-of-order deliveries that get at most RWS many 
packets ahead.

Here are the corresponding three variables:
	RWS	Receiver Window Size
	LFR	Last *cumulative* frame received, just below window bottom
		The receiver sends its cumulative ACK for data up through this point.
	LAF	Last Acceptable Frame, at window top

It's not at all clear from the text that LFR is being used in a 
cumulative sense, that is, if we've received packets 1,2,3,5,6,
then LFR is 3, not 6, because we've received all packets up to and 
including 3, but not yet 4. Because LFR is in fact cumulative,
we know that LFR+1 is always not yet received; it is in fact
the Next Frame Expected, or NFE (an abbreviation used without 
explanation in Figure 2.23).

Now the typos. First, the second inequality on page 106 should be
an equality,
	LAF - LFR == RWS
which says that at any point we're allowed to receive up to RWS many
packets beyond what we've received cumulatively, and we don't have
to "do" anything to restore this relationship when a new packet arrives.
(If a new packet arrives, then LFR is incremented and thus LAF is 
immediately incremented as well.)

The other error is that LAF is spelled LFA in figure 2.23 (and, of course,
the above-mentioned NFE is used instead of LFR).

One last point: in general, in between packet/ack arrivals, the sender has sent 
all the frames in the sender window, the receiver has *not* received any 
packets in its receive window. On receipt of data (assuming it is NFE),
the receive window immediately slides forward, and a new ACK is sent.
On receipt of an ACK (for LAR+1), the sender window immediately slides
forward and a new DATA packet is sent.