CS 118 Spring 2011 : Homework 4Problem 1In the rdt3.0 protocol, the ACK packets that flow from the receiver back to the sender don’t have sequencenumbers, even though they do have an ACK field that contains the sequence number of the data packet thatthey are acknowledging. Why don’t these ACK packets need sequence numbers?Consider why we needed sequence numbers in the first place. We saw that the sender needs sequence numbersso that the receiver can tell if a data packet is a duplicate of an already received data packet. In the caseof ACKs, the sender does not need this info (i.e., a sequence number on an ACK) to tell detect a duplicateACK. A duplicate ACK is obvious to the rdt3.0 receiver, since when it has received the original ACK ittransitioned to the next state. The duplicate ACK is not the ACK that the sender needs and hence is ignoredby the rdt3.0 sender.Problem 2Consider the Go-Back-N (GBN) protocol with a sender window size (N) of 3 and a sufficiently large sequencenumber range. Suppose that, at time t, the next in-order packet that the receiver is expecting has a sequencenumber of k. Assume that the medium does not reorder messages.a. What are all possible values of the ACK field in all possible messages currently propagating back tothe sender at time t? Justify your answer.b. Following (a), what are the possible sets of sequence numbers inside the sender’s window at time t?Justify your answer.a. Given that the receiver is waiting for packet k, then it has already received (and ACKed) packet k-1and the N-1 packets before that. If none of those N ACKs have been yet received by the sender, thenACK messages with values of [k − N, k − 1] (i.e., [k − 3, k − 1]) may still be propagating back.b. Let’s discuss two boundary situation:Suppose all of these ACKs in (a) have been received by the sender, then sender’s window is [k, k+N −1](i.e., [k, k + 2]).Suppose none of the ACKs have been yet received at the sender. In this second case, the sender’swindow contains k − 1 and the N packets up to and including k − 1. The sender’s window is thus[k − N, k − 1] (i.e., [k − 3, k − 1]).By these arguments, the senders window is of size 3 and begins somewhere in the range of k − 3 and k.Problem 3Consider an HTTP client that needs to retrieve a single object of size O = 100 KBytes from an HTTPserver. Assume we are using non-persistent HTTP. If the maximum segment size S is 536 Bytes, RTT =100 msec, and the transport protocol is TCP with a static window size W :a. For a transmission rate of 28 kbps (that’s kilobits per second), determine the minimum possible latency.Determine the minimum window size that achieves this latency.b. Repeat (a) for 100 kbps.c. Repeat (a) for 10 Mbps.Problem 3 continued on next page. . . Page 1 of 2CS 118 Spring 2011 : Homework 4The object consists of 100 KBytes/536 Byte ∼ 187 packets (segments).The minimum window needs to be greater than the (bandwidth-delay product/536) to fully utilize the link,and no greater than 187.a. Latency = TCP setup + request/response = 0.1 sec + [0.1 sec + (800 kb / 28 kbps)] = 28.77 secW ≥ 0.1 sec * 28 kbps / 536 byte + 1 = 1.65The minimum window size is 2.b. Latency = 0.1 sec + 0.1 sec + (800 kb / 100 kbps) = 8.2 secW ≥ 0.1 sec * 100 kbps / 536 byte + 1 = 3.33The minimum window size is 4.c. Latency = 0.1 sec + 0.1 sec + (800 kb / 10000 kbps) = 0.28 secW ≥ 0.1 sec * 10000 kbps / 536 byte + 1 = 234.20The minimum window size is 187 (235 > 187).Usually the window size is expressed in number of segments.Here we allow you to express it in bytes: 2*536 bytes, 4*536 bytes, 187*536 bytes.Problem 4This problem is about estimating round-trip times (RTTs). Given α = 0.1, let SampleRT Tnbe the mostrecent sample RTT, let SampleRT Tn−1be the next most recent sample RTT, and so on.a. In a TCP connection, suppose four acknowledgments have been returned with corresponding sampleRTTs SampleRT T1, SampleRT T2, SampleRT T3, and SampleRT T4. Express EstimatedRTT, theestimated RTT after all four ACKs have been received, in terms of the four sample RTTs.b. Express this as a general formula for n sample RTTs.a. If EstimatedRTTnis the estimate after the nth sample:EstimatedRT T1=SampleRT T1EstimatedRT T2=x · SampleRT T2+ (1 − x) · SampleRT T1EstimatedRT T3=x · SampleRT T3+ (1 − x) · EstimatedRT T2=x · SampleRT T3+ (1 − x)[x · SampleRT T2+ (1 − x) · SampleRT T1]=x · SampleRT T3+ (1 − x) · x · SampleRT T2+ (1 − x)2· SampleRT T1EstimatedRT T4=x · SampleRT T4+ (1 − x) · EstimatedRT T3=x · SampleRT T4+ (1 − x) · x · SampleRT T3+ (1 − x)2· x · SampleRT T2+ (1 − x)3· SampleRT T1b. EstimatedRT Tn= x ·Pnj=2(1 − x)(n−j)· SampleRT Tj+ (1 − x)(n−1)· SampleRT T1Page 2 of
View Full Document
Unlocking...