Chapter 3 Problems

R1The network layer accepts a segment of at most 1,200 bytes plus a destination host address, and guarantees to deliver it. Many application processes run on the destination host.

The operating system on the destination host has given every running process a 4-byte port number.

R2On some planet everyone lives in a family of six. Each house has a unique address. Each person in a house has a unique name. The mail service carries letters from house to house, and requires that the letter be in an envelope with the destination house address written on it, and nothing more. Each family has one delegate who collects and hands out letters.

This is the household analogy from section 3.1, turned into a question. Ann and Bill are the delegates; the mail service is the network layer.

R3On a TCP connection between Host A and Host B, the segments from A to B carry source port x and destination port y. What are the source and destination ports on the segments travelling from B to A?

R4Why might an application developer choose to run an application over UDP rather than TCP?

R5Why is voice and video traffic often sent over TCP in today's Internet? The answer has nothing to do with congestion control.

R6Can an application have reliable data transfer even though it runs over UDP? If so, how?

R7A process on Host C has a UDP socket with port number 6789. Host A and Host B each send a UDP segment to Host C with destination port 6789.

R8A Web server runs on Host C on port 80. It uses persistent connections and is currently serving requests from two different hosts, A and B.

R9In the rdt protocols of section 3.4, why did we need to introduce sequence numbers?

R10In the rdt protocols, why did we need to introduce timers?

R11Suppose the round-trip delay between sender and receiver is constant and known to the sender. Would a timer still be necessary in rdt3.0, assuming packets can be lost?

R12Visit the Go-Back-N interactive animation at the companion Web site.

You do not need the companion site — this section's own Go-Back-N widget does the same three experiments. Answer from the mechanism, then check with the widget.

R13Repeat R12 with the Selective Repeat animation. How are Selective Repeat and Go-Back-N different?

R14True or false?

R15Host A sends two TCP segments back to back to Host B. The first has sequence number 90; the second has sequence number 110.

R16In the Telnet example of section 3.5, the user types the letter C. A few seconds later the user types the letter R. After typing R, how many segments are sent, and what is in their sequence-number and acknowledgement-number fields?

In Figure 3.36 the client's initial sequence number is 42 and the server's is 79. The letter C has already been typed, echoed and acknowledged. Assume Host A is the client and Host B is the server.

R17Two TCP connections share a bottleneck link of rate R bits per second. Both have a huge file to send in the same direction, and both start at the same time. What transmission rate would TCP like to give each connection?

R18True or false? In TCP congestion control, when the timer expires at the sender, ssthresh is set to one half of its previous value.

R19The TCP splitting sidebar in section 3.7 claims the response time is approximately 4·RTT_FE + RTT_BE + processing time. Justify the claim.

RTT_FE is the round-trip time between the client and a nearby front-end server. RTT_BE is the round-trip time between the front end and the distant data centre.

P1Client A starts a Telnet session with Server S. At about the same time, Client B also starts a Telnet session with Server S.

Telnet's well-known server port is 23. Client ports are chosen by the operating system from the ephemeral range, above 1023.

P2Consider Figure 3.5. What are the source and destination port values in the segments flowing from the server back to the clients' processes? What are the IP addresses in the network-layer datagrams carrying those segments?

In Figure 3.5, host A sends from port 26145 to server C's port 80, and host B sends from ports 7532 and 26145 to the same server port 80.

P3UDP and TCP use ones-complement arithmetic for their checksums. You have three 8-bit bytes: 01010011, 01100110, 01110100. What is the ones complement of their sum?

The real protocols use 16-bit words. This problem uses 8-bit words to keep the arithmetic short. The section 3.3 widget on this page will do the same sum bit by bit.

P4More ones-complement arithmetic.

P5A UDP receiver computes the Internet checksum for a received segment and finds it matches the value in the checksum field. Can the receiver be absolutely certain that no bit errors occurred?

P6Show that the receiver in Figure 3.60, operating with the rdt2.1 sender of Figure 3.11, can lead sender and receiver into a deadlock, where each waits for an event that will never occur.

The incorrect receiver of Figure 3.60 replies NAK when it gets a corrupted packet **or** when it gets a packet with the sequence number it is not expecting. The correct rdt2.1 receiver replies with an acknowledgement in the second case.

P7In rdt3.0, the acknowledgement packets flowing from receiver to sender have no sequence numbers of their own, although they do carry the sequence number of the packet they acknowledge. Why do the acknowledgements not need sequence numbers?

P8Draw the finite state machine for the receiver side of rdt3.0.

P9Give a trace of rdt3.0 when data packets and acknowledgement packets are garbled, similar to the trace in Figure 3.16.

P10A channel can lose packets, but has a known maximum delay. Modify rdt2.1 to include a sender timeout and retransmission. Argue informally why your protocol works.

P11Look at the rdt2.2 receiver in Figure 3.14 and the packet it builds in its self-transitions: `sndpkt = make_pkt(ACK, 1, checksum)` in the wait-for-0 state, and `sndpkt = make_pkt(ACK, 0, checksum)` in the wait-for-1 state. Would the protocol still work if this action were removed?

P12The rdt3.0 sender ignores every received packet that is in error or has the wrong `acknum`. Suppose instead it retransmitted the current data packet in those circumstances. Would the protocol still work?

The hint says: consider a channel with bit errors only — no losses — but where premature timeouts can occur. Count how many times the nth packet is sent as n grows.

P13Draw a diagram showing that if the channel between sender and receiver can reorder messages, the alternating-bit protocol will not work correctly. Say clearly in what sense it fails.

P14Consider a reliable transfer protocol that uses only negative acknowledgements. Would a NAK-only protocol be preferable when the sender sends data infrequently? What if the sender has a lot of data to send and the connection loses little?

P15Consider the cross-country example of Figure 3.17. How large must the window be for channel utilisation to exceed 98 percent? A packet is 1,500 bytes, including headers.

From Figure 3.17: the link runs at 1 Gbps and the round-trip propagation delay is 30 ms.

P16An application uses rdt3.0. Because stop-and-wait has very low utilisation, its designers let the receiver keep sending back several alternating ACK 0 and ACK 1 packets, even when the corresponding data has not arrived. Would this increase channel utilisation? Are there problems?

P17Two entities A and B are joined by a perfect two-way channel: nothing is corrupted, lost or reordered. They must deliver messages to each other strictly in turn — A to B, then B to A, then A to B, and so on. If an entity is asked to send when it is not its turn, it answers with `rdt_unable_to_send(data)`. Draw one finite state machine for A and one for B.

P18In the generic Selective Repeat protocol the sender transmits a message as soon as it is available, if it is in the window. Design a Selective Repeat variant that sends messages **two at a time**: it sends a pair, and sends the next pair only when it knows both messages of the first pair arrived correctly. The channel may lose messages but will not corrupt or reorder them.

P19Host A wants to send packets to Hosts B and C at the same time, over a broadcast channel: a packet sent by A is carried to both. The channel can independently lose and corrupt packets, so a packet may reach B correctly but not C. Design a stop-and-wait-like protocol so that A does not take new data from the layer above until it knows **both** B and C have received the current packet. Give machines for A and C, and the packet formats.

P20Hosts A and B both send messages to Host C. A and C are joined by a channel that can lose and corrupt messages but not reorder them; B and C are joined by an independent channel with the same properties. The transport layer at C must **alternate** in delivering messages upward: first a message from A, then one from B, then one from A, and so on. Design a stop-and-wait-like protocol. Give machines for A and C, and the packet formats.

P21Entity B has data messages for entity A. When A is asked by the layer above for the next data message, A must send a request message R to B. Only on receiving an R may B send a data message D back. A must deliver exactly one copy of each D to the layer above. R messages can be lost, but not corrupted. D messages, once sent, always arrive correctly. Delays on both channels are unknown and variable. Give a finite state machine for a protocol using only the mechanisms that are absolutely necessary.

P22Go-Back-N with a sender window of 4 and a sequence-number range of 1,024. At time t, the next in-order packet the receiver expects has sequence number k. The medium does not reorder messages.

P23Consider Go-Back-N and Selective Repeat with a sequence-number space of size k. What is the largest allowable sender window that avoids the problem in Figure 3.27?

P24True or false, with a brief justification.

P25An application may choose UDP because UDP offers finer control than TCP over **what** data is sent in a segment, and **when**. Explain both.

P26An enormous file of L bytes is transferred from Host A to Host B. The maximum segment size is 536 bytes.

P27Hosts A and B are communicating over a TCP connection, and B has already received all bytes from A up through byte 126. A now sends two segments back to back, carrying 80 and 40 bytes of data. In the first segment the sequence number is 127, the source port is 302 and the destination port is 80. B acknowledges every segment it receives.

P28Hosts A and B are directly connected by a 100 Mbps link, with one TCP connection between them. A is sending B an enormous file. A can push application data into its socket at up to 120 Mbps, but B can read out of its receive buffer at only 50 Mbps. Describe the effect of TCP flow control.

P29SYN cookies, from section 3.5.6.

P30Consider Scenario 2 of section 3.6.1. Both sending hosts A and B have fixed timeout values.

P31Five measured round-trip-time samples are 106 ms, 120 ms, 140 ms, 90 ms and 115 ms. Compute EstimatedRTT, DevRTT and TimeoutInterval after each sample.

Use α = 0.125 and β = 0.25. Just before the first sample, EstimatedRTT was 100 ms and DevRTT was 5 ms. The formulas are in section 3.5.3.

P32Consider TCP's procedure for estimating the round-trip time, with α = 0.1. Let SampleRTT₁ be the most recent sample, SampleRTT₂ the next most recent, and so on.

P33Why do you think TCP avoids measuring the round-trip-time sample for retransmitted segments?

P34What is the relationship between the variable SendBase of section 3.5.4 and the variable LastByteRcvd of section 3.5.5?

P35What is the relationship between the variable LastByteRcvd of section 3.5.5 and the variable y of section 3.5.4?

In the section 3.5.4 pseudocode, y is the acknowledgement number carried in an arriving acknowledgement segment.

P36TCP waits until it has received three duplicate acknowledgements before performing a fast retransmit. Why did the designers choose not to retransmit after the very first duplicate acknowledgement?

P37Compare Go-Back-N, Selective Repeat and TCP without delayed acknowledgements. Host A sends five data segments to Host B and the **second** one is lost. All timeouts are long enough that five segments and their acknowledgements can be exchanged before any timer fires. In the end all five segments are correctly received.

P38In the description of TCP in Figure 3.53, ssthresh is set to cwnd/2 in several places, and is described as half the window size when a loss event occurred. Must the rate at which the sender was sending when the loss occurred be approximately cwnd segments per round-trip time? If not, can you suggest a different way to set ssthresh?

The book cites Figure 3.53 here. In the 8th edition the congestion-control state machine is **Figure 3.51**; 3.53 is a different figure. This is a misprint.

P39Consider Figure 3.46(b). If λ′in increases beyond R/2, can λout increase beyond R/3? Now consider Figure 3.46(c). If λ′in increases beyond R/2, can λout increase beyond R/4, given that a packet is forwarded twice on average from the router to the receiver?

Scenario 2 of section 3.6.1: two connections share one router whose output link runs at R, so each connection can get at most R/2. λ′in is the offered load including retransmissions; λout is the useful data delivered.

P40Consider Figure 3.61, assuming TCP Reno is the protocol shown.

Reading the figure: cwnd is 1, 2, 4, 8, 16, 32 in rounds 1–6; then 33 up to 42 in rounds 7–16; then it drops to 24 and climbs to 29 in rounds 17–22; then it drops to 1 and doubles to 8 in rounds 23–26.

P41Figure 3.55 illustrates the convergence of TCP's additive-increase, multiplicative-decrease algorithm. Suppose that instead of a multiplicative decrease, TCP decreased the window by a constant amount. Would the resulting additive-increase, additive-decrease algorithm converge to an equal share?

The book cites Figure 3.55 here. In the 8th edition the convergence diagram is **Figure 3.56**; 3.55 is the fairness picture that precedes it. This is a misprint, and it repeats a slip made in section 3.7.3 itself.

P42Section 3.5.4 discussed doubling the timeout interval after a timeout. That is itself a form of congestion control. Why does TCP need a window-based congestion-control mechanism in addition?

P43Host A is sending an enormous file to Host B over a TCP connection. There is never any packet loss and the timers never expire. The link from A to the Internet runs at R bits per second. The process on A can push data into its socket at S = 10R. The receive buffer is large enough for the whole file; the send buffer holds only one percent of the file. What prevents the process on Host A from continuously passing data at rate S? Flow control? Congestion control? Something else?

P44A large file is sent over a TCP connection with no loss. TCP uses additive increase and multiplicative decrease without slow start. cwnd increases by 1 MSS for each batch of acknowledgements, and the round-trip time is approximately constant.

P45Consider Figure 3.54. Suppose that at t₃ the sending rate at which congestion loss next occurs drops to 0.75·Wmax, without the senders knowing. Show the evolution of both TCP Reno and TCP CUBIC for two more rounds each.

Figure 3.54 compares Reno and CUBIC after a loss at Wmax. The hint warns that the two protocols may no longer react to loss at the same moments.

P46Consider Figure 3.54 again. Suppose that at t₃ the rate at which congestion loss occurs **increases** to 1.5·Wmax. Show the evolution of both TCP Reno and TCP CUBIC for two more rounds each.

P47Recall the macroscopic description of TCP throughput. As the connection's rate goes from W/(2·RTT) to W/RTT, only one packet is lost, right at the end of the period.

P48A single TCP Reno connection uses one 10 Mbps link which does not buffer any data, and it is the only congested link on the path. The sender has a huge file to send and the receive buffer is much larger than the congestion window. Each TCP segment is 1,500 bytes; the two-way propagation delay is 150 ms; and the connection is always in congestion avoidance — ignore slow start.

P49Take the scenario of P48, but now let the 10 Mbps link buffer a finite number of segments. Argue that to keep the link always busy sending data, the buffer should be at least the product of the link speed C and the two-way propagation delay.

P50Repeat P48 with the 10 Mbps link replaced by a 10 Gbps link. You will find that recovery takes a very long time. Sketch a solution.

The book says "repeat Problem 46". In the 8th edition the problem being referred to is **P48**; the numbering slipped by two. Everything else is unchanged: 1,500-byte segments, 150 ms two-way propagation delay, no buffering, always in congestion avoidance.

P51Let T, measured in round-trip times, be the time a TCP connection takes to increase its congestion window from W/2 to W, where W is the maximum window. Argue that T is a function of TCP's average throughput.

P52A simplified additive-increase, multiplicative-decrease algorithm measures the congestion window in segments. Additive increase adds one segment per round trip. Multiplicative decrease halves the window, rounding down. Two connections C1 and C2 share a congested link of speed 30 segments per second, both in congestion avoidance. C1's round-trip time is 50 ms; C2's is 100 ms. When the data rate in the link exceeds the link's speed, all connections lose a segment.

P53The same network as P52, but now both connections have a round-trip time of 100 ms. At t₀, C1's window is 15 segments and C2's is 10.

P54Consider a modification to TCP's congestion control. Instead of additive increase, use multiplicative increase: the sender increases its window by a small positive constant a, with 0 < a < 1, whenever it receives a valid acknowledgement. Find the relationship between the loss rate L and the maximum window W. Argue that this modified TCP always takes the same time to increase its window from W/2 to W, whatever its average throughput.

P55The book notes that to achieve a throughput of 10 Gbps, TCP could only tolerate a segment loss probability of about 2 × 10⁻¹⁰. Show the derivation, using the round-trip time and segment size given in section 3.7. What would the tolerable loss be for a 100 Gbps connection?

This problem refers to a "TCP futures" subsection that **does not exist in the 8th edition** — it was in earlier editions and was removed. Its constants were a 1,500-byte segment size and a 100 ms round-trip time; use those. The problem also states its own figure two different ways: 2 × 10⁻¹⁰ is one loss in 5,000,000,000 segments, and the printed "1 out of 5,000,000" is a misprint.

P56Section 3.7 assumed the TCP sender always had data to send. Suppose instead the sender sends a large amount of data and then goes idle at t₁, stays idle for a long time, and wants to send again at t₂. What are the advantages and disadvantages of using the cwnd and ssthresh values from t₁ when restarting at t₂? What would you recommend?

P57Does UDP or TCP provide any degree of end-point authentication?

P58Consider the delay introduced by TCP slow start. A client and a Web server are directly connected by one link of rate R. The client retrieves an object of exactly 15·S bytes, where S is the maximum segment size. The round-trip time is a constant RTT. Ignoring protocol headers, find the time to retrieve the object, including connection establishment.

Because 15·S = (2⁴ − 1)·S, slow start delivers the object in exactly four windows of 1, 2, 4 and 8 segments. After sending a window of 2^(k−1) segments, the server must wait for the first acknowledgement of that window, which arrives S/R + RTT after the window began. So the idle time after window k is max(0, S/R + RTT − 2^(k−1)·S/R).