6.4: Epilog and Exercises
 Page ID
 11139
This completes our discussion of the slidingwindows algorithm in the abstract setting. We will return to concrete implementations of this in 11.4.1 TFTP and the Sorcerer (stopandwait) and in 12.14 TCP Sliding Windows; the latter is one of the most important mechanisms on the Internet.
Exercises
Exercises are given fractional (floating point) numbers, to allow for interpolation of new exercises. Exercise 1.5 is distinct, for example, from exercises 1.0 and 2.0. Exercises marked with a ♢ have solutions or hints at 24.6 Solutions for Sliding Windows.
1.0 Sketch a ladder diagram for stopandwait if Data[3] is lost the first time it is sent, assuming no sender timeout (but the sender retransmits on duplicate), and a receiver timeout of 2 seconds. Continue the diagram to the point where Data[4] is successfully transmitted. Assume an RTT of 1 second.
1.5 Redraw the Sorcerer’s Apprentice diagram of 6.1.2 Sorcerer’s Apprentice Bug, assuming the sender now does not retransmit on duplicates, though the receiver still does. ACK[3] is, as before, delayed until the sender retransmits Data[3].
2.0 Suppose a stopandwait receiver has an implementation flaw. When Data[1] arrives, ACK[1] and ACK[2] are sent, separated by a brief interval; after that, the receiver transmits ACK[N+1] when Data[N] arrives, rather than the correct ACK[N].
2.5♢ Consider the alternative model of 6.3.1 Simple fixedwindowsize analysis:
3.0 Create a table as in 6.3.1 Simple fixedwindowsize analysis for the original A───R1───R2───R3───R4───B network with winsize = 8. As in the text examples, assume 1 packet/sec bandwidth delay for the R1⟶R2, R2⟶R3, R3⟶R4 and R4⟶B links. The A–R1 link and all reverse links (from B to A) are infinitely fast. Carry out the table for 10 seconds.
4.0 Create a table as in 6.3.1 Simple fixedwindowsize analysis for a network A───R1───R2───B. The A–R1 ink is infinitely fast; the R1–R2 and R2–B each have a 1second propagation delay, in each direction, and zero bandwidth delay (that is, one packet takes 1.0 sec to travel from R1 to R2; two packets also take 1.0 sec to travel from R1 to R2). Assume winsize=6. Carry out the table for 8 seconds. Note that with zero bandwidth delay, multiple packets sent together will remain together until the destination; propagation delay behaves very differently from bandwidth delay!
5.0 Suppose RTT_{noLoad} = 4 seconds and the bottleneck bandwidth is 1 packet every 2 seconds.
6.0 Create a table as in 6.3.1 Simple fixedwindowsize analysis for a network A───R1───R2───R3───B. The A–R1 link is infinitely fast. The R1–R2 and R3–B links have a bandwidth delay of 1 packet/second with no additional propagation delay. The R2–R3 link has a bandwidth delay of 1 packet / 2 seconds, and no propagation delay. The reverse B⟶A direction (for ACKs) is infinitely fast. Assume winsize = 6.
Hint: The column for “R2 sends” (or, more accurately, “R2 is in the process of sending”) should look like this:
T 
R2 sends 

0 

1 
1 
2 
1 
3 
2 
4 
2 
5 
3 
6 
3 
… 
… 
7.0 Argue that, if A sends to B using sliding windows, and in the path from A to B the slowest link is not the first link out of A, then eventually A will have the entire window outstanding (except at the instant just after each new ACK comes in).
7.5♢ Suppose RTT_{noLoad} is 100 ms and the available bandwidth is 1,000 packets/sec. Sliding windows is used.
8.0 Suppose RTT_{noLoad} is 50 ms and the available bandwidth is 2,000 packets/sec. Sliding windows is used for transmission.
8.5 Suppose stopandwait is used (winsize=1), and assume that while packets may be lost, they are never reordered (that is, if two packets P1 and P2 are sent in that order, and both arrive, then they arrive in that order). Show that at the point the receiver is waiting for Data[N], the only two packet arrivals possible are Data[N] and Data[N1]. (A consequence is that, in the absence of reordering, stopandwait can make do with 1bit packet sequence numbers.) Hint: if the receiver is waiting for Data[N], it must have just received Data[N1] and sent ACK[N1]. Also, once the sender has sent Data[N], it will never transmit a Data[K] with K<N.
✰9.0♢ Suppose winsize=4 in a slidingwindows connection, and assume that while packets may be lost, they are never reordered (that is, if two packets P1 and P2 are sent in that order, and both arrive, then they arrive in that order). Show that if Data[8] is in the receiver’s window (meaning that everything up through Data[4] has been received and acknowledged), then it is no longer possible for even a late Data[0] to arrive at the receiver. (A consequence of the general principle here is that – in the absence of reordering – we can replace the packet sequence number with (sequence_number) mod (2×winsize+1) without ambiguity.)
10.0 Suppose winsize=4 in a slidingwindows connection, and assume as in the previous exercise that while packets may be lost, they are never reordered. Give an example in which Data[8] is in the receiver’s window (so the receiver has presumably sent ACK[4]), and yet Data[1] legitimately arrives. (Thus, the latepacket bound in the previous exercise is the best possible.)
11.0 Suppose the network is A───R1───R2───B, where the A–R1 ink is infinitely fast and the R1–R2 link has a bandwidth of 1 packet/second each way, for an RTT_{noLoad} of 2 seconds. Suppose also that A begins sending with winsize = 6. By the analysis in 6.3.1.3 Case 3: winsize = 6, RTT should rise to winsize/bandwidth = 6 seconds. Give the RTTs of the first eight packets. How long does it take for RTT to rise to 6 seconds?
12.0 In this exercise we look at the relationship between bottleneck bandwidth and winsize/RTT_{actual} when the former changes suddenly. Suppose the network is as follows
A───R1───R2───R3───B
The A──R1 link is infinitely fast. The R1→R2 link has a 1 packet/sec bandwidth delay in the R1→R2 direction. The remaining links R2→R3 and R3→B have a 1 sec bandwidth delay in the direction indicated. ACK packets, being small, travel instantaneously from B back to A.
A sends to B using a winsize of three. Three packets P0, P1 and P2 are sent at times T=0, T=1 and T=2 respectively.
At T=3, P0 arrives at B. At this instant the R1→R2 bandwidth is suddenly halved to 1 packet / 2 sec; P3 is transmitted at T=3 and arrives at R2 at T=5. It will arrive at B at T=7.
T 
A sends 
R1’s queue 
R1 sends 
R2 sends 
R3 sends 
B recvs/ACKs 

2 
P2 

P2 
P1 
P0 

3 
P3 

P3 
P2 
P1 
P0 
4 
P4 
P4 
P3 cont 

P2 
P1 
5 
P5 
P5 
P4 
P3 

P2 
6 

P5 
P4 cont 

P3 

7 
P6 




P3 
8 


9 
P7 

10 


11 
P8 