6.4: Epilog and Exercises

This completes our discussion of the sliding-windows algorithm in the abstract setting. We will return to concrete implementations of this in 11.4.1 TFTP and the Sorcerer (stop-and-wait) 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 stop-and-wait 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 Re-draw 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 stop-and-wait 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].

(a). Draw a diagram, including at least three RTTs.

(b). What is the average throughput, in data packets per RTT? (For normal stop-and-wait, the average throughput is 1.)

(c). Is there anything the sender can do to detect this receiver behavior before the final packet, assuming the sender must respond to each ACK as soon as it arrives?

2.5♢ Consider the alternative model of 6.3.1 Simple fixed-window-size analysis:

(a). Using the formulas of 6.3.2 RTT Calculations, calculate the steady-state queue usage for a window size of 6.

(b). Again for a window size of 6, create a table like those in 6.3.1 Simple fixed-window-size analysis up through T=8 seconds.

3.0 Create a table as in 6.3.1 Simple fixed-window-size 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 fixed-window-size analysis for a network A───R1───R2───B. The A–R1 ink is infinitely fast; the R1–R2 and R2–B each have a 1-second 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.

(a). What window size is needed to remain just at the knee of congestion?

(b). Suppose winsize=6. What is the eventual value of RTT_actual?

(c). Again with winsize=6, how many packets are in the queue at the steady state?

6.0 Create a table as in 6.3.1 Simple fixed-window-size 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.

(a). Carry out the table for 10 seconds. Note that you will need to show the queue for both R1 and R2.

(b). Continue the table at least partially until T=18, in sufficient detail that you can verify that RTT_actual for packet 8 is as calculated in exercise 5.0. To do this you will need more than 10 packets, but fewer than 16; the use of hex labels A, B, C for packets 10, 11, 12 is a convenient notation.

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.

(a). What is the transit capacity for the connection?

(b). If RTT_actual rises to 130 ms (due to use of a larger winsize), how many packets are in a queue at any one time?

(c). If winsize increases by 50, what is RTT_actual?

8.0 Suppose RTT_noLoad is 50 ms and the available bandwidth is 2,000 packets/sec. Sliding windows is used for transmission.

(a). What window size is needed to remain just at the knee of congestion?

(b). If RTT_actual rises to 60 ms (due to use of a larger winsize), how many packets are in a queue at any one time?

(c). What value of winsize would lead to RTT_actual = 60 ms?

(d). What value of winsize would make RTT_actual rise to 100 ms?

8.5 Suppose stop-and-wait 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[N-1]. (A consequence is that, in the absence of reordering, stop-and-wait can make do with 1-bit packet sequence numbers.) Hint: if the receiver is waiting for Data[N], it must have just received Data[N-1] and sent ACK[N-1]. 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 sliding-windows 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 sliding-windows 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 late-packet 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.

(a). Complete the following table of packet arrival times

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

(b). For each of P2, P3, P4 and P5, calculate the througput given by winsize/RTT over the course of that packet’s round trip. Obtain each packet’s RTT from the completed table above.

(c). Once the steady state is reached in which RTT_actual = 6, how much time does each packet spend in transit? How much time does each packet spend in R1’s queue?