I've added some notes on sliding windows, which try to give different perspectives on what's in the text. They also correct a couple typos.
There is a subtle assumption in
this chapter thatwe are doing transport only over a single link, which generally
impliesthat delivered packets cannot arrive out of order. Most common
individual links essentially never reorder packets. However, reordering
is possible (in fact, common) once switches and routers are introduced
. The only place this matters, though,is in how many bits of the sequence
number are actually transmitted; everything works out fine if, for the time
being, you just imagine that sequence numbers are infinite-precision (that
is, they never wrap around).
The section on TCP (chapter 5) will address additional mechanisms beyond
sliding windows for dealing with reordering.
The text includes some code implementing the sliding window algorithm; you may skip this part although there are some interesting data-structuring issues.
New stuff on sliding windows
Exercises 27 and 28 can be hard, so here are a few hints. First of all, some notation. Suppose MaxSeqNum = 5, so the transmitted sequence numbers are all sent mod 5. Data[5] is still the fifth data packet, but it would be sent with sequence number 0; we will write this as Data[5/0] when there is ambiguity. Similarly we might have Data[6/1]. What is at issue here is whether there is some circumstance when the receiver is expecting Data[5/0], say, but receives Data[0/0], and, unable to distinguish between them, accepts it incorrectly.
Here is an example. Suppose MaxSeqNum = 5 and SWS = 4. The sender sends
Data[0] through Data[3], or, in our new notation, Data[0/0]...Data[3/3].
The receiver now sends the Ack for all this, and is then expecting Data[4]...Data[7], ie Data[4/4], Data[5/0], Data[6/1], and Data[7/2] (7 mod 5 = 2). The sender resends Data[0/0] through Data[3/3], but:
receiver accepts Data[0/0] as Data[5/0], in the receive window
receiver accepts Data[1/1] as Data[6/1], in the receive window
receiver accepts Data[2/2] as Data[7/2], in the receive window
Eventually the sender may send the real Data[5/0], but the receiver will ignore
it as a duplicate, and the mistakenly accepted Data[0/0] will have been written
at that point in the output stream. The mistake has been made.
For #28, here are a few observations:
1. Once 0 is no longer in the sending window, Data[0] can't be sent.
It may, however, still arrive, having been in transit.
2. Once 0 is no longer in the sending window, and something sent after that point (eg Data[3]) does arrive, then Data[0] can no longer arrive. If it did, it would be a case of Data[0] sent before Data[3] but arriving after, which we've explicitly disallowed by hypothesis (a hypothesis the Internet as a whole does not abide by, but that's for chapter 4).
So, showing Data[3] had arrived would imply Data[0] cannot arrive again.
One important consequence is that Ethernet supports true broadcast ,where one node can send a message to every other.
Another important issue for Ethernet is that the underlying unsynchronized transmission strategy allows collisions to occur, and these must then bedealt with. This is discussed in the text in the section Transmitter Algorithm.
Further information can be found at my Ethernetpage.