Advanced TCP/IP networks midterm study guide solutions > 1. Give a timeline showing two packet drops in one TCP window, > for both Reno and NewReno implementations. Identify periods of > congestion window "inflation" (the upper end moves up but the > lower end does not) and "deflation" (the lower end moves up > but the upper end does not). In class, we focussed more on descriptions of Reno and NewReno in terms of "flightsize" than cwnd. That said, in Reno the second drop would result in another window reduction, while in NewReno we would end up resending the second dropped packet without further reducing the effective window size. =============== > 2. How do Reno and NewReno handle "partial ACKs"? That is, > suppose packet1 is lost, with a window size of 20. Both TCPs > would receive duplicate ACK0's, and would retransmit packet1. > If packet1 is the only packet lost, the response to the > retransmitted packet1 will be ACK20. However, if, say, packet12 > were also lost, then the response to the retransmitted packet1 > would be ACK11. This ACK11 represents a "partial ACK". > How does SACK TCP respond to partial ACKs? Let ACK[N] be a partial ACK. NewReno handles this by immediately inferring that DATA[N+1] is lost, and retransmits this. It may or may not also retransmit a new data packet, depending on whether the estFlightSize is below or above half of the original value of cwnd, respectively. Reno TCP exits congestion control upon receipt of a partial ACK. It will then get several more dupACKs of the partial ACK, and enter congestion control again, halving cwnd again. =============== > 3. Explain the connection between cwnd and estFlightSize, > both at loss-free times and in the presence of packet losses. Without losses, cwnd = estFlightsize, the number of packets in flight. If the highest packet ACKed is A, then only packets A+1, ..., A+cwnd are allowed to be in flight. Once losses have occurred, the lower edge of the congestion window is fixed. For example if packet A+1 is lost, then the highest packet that can be ACKed is A, at least until A+1 is retransmitted and received. In the meantime, both Reno and NewReno allow the receiver to infer from the dupACK[A]'s received that estFlightSize is shrinking steadily. At the point that estFlightSize = 0.5*W, where W is the original value of cwnd, the sender may resume sending; this leaves estFlightSize fixed at 0.5*W while cwnd may grow to cwnd+0.5W = 1.5W. As soon as the missing ACK[A+1] is received, however, cwnd is reset to 0.5*W, corresponding to the window A+W+1, ..., A+W+0.5*W; neither the estFlightSize nor the top edge of the window changes. =============== > 4. Explain why a longer RTT alone, with the same packet-loss risk, > can mean that a TCP connection gets less bandwidth. TCP windows are increased by one packet every RTT. With a larger RTT, the rate of window increase is thus slowed. =============== > 5. Discuss how to arrange for geographical routing in IP. > Discuss how, using BGP or some other method, routers in adjacent towns on > opposite sides of a state line could send traffic to each other directly, > while each sends other traffic to their state's respective state hub. Geographical routing can be implemented by assigning each local network to a region, and having each local network forward all its nonlocal traffic to its regional hub. More levels of regional aggregation can be provided if desired. This means that if two hosts are near each other but are in different regions, then packets from one to the other will go the long way around: A--R1--R2--B rather than A--B. R1---|----R2 \ | / \ | / A-|-B To fix this, one approach would be to have regional border routers advertise the local networks nearby each exit point. Thus, A would not just have a default route pointing to R1; it would also have an explicit entry for B. This would allow traffic from A to B to take the direct route. Traffic from B to A would take the direct route if B placed A into its routing tables. Note that this has nothing to do with the BGP multi_exit_disc values; that would apply if the right side above wanted traffic from R2 to A to go via B. =============== > 6. Suppose A sends to B via some routers and uses the sliding-window > algorithm with a fixed window size W; the RTT is 2.0 sec of > bandwidth-type delay (mostly for the A->B direction; ACKS, being > smaller, are delayed much less). Suppose the bandwidth is 2 packets/sec. > Describe what happens as W increases from 1. At what value of W > would an increased RTT be encountered? What causes this? > What happens if W is increased just a little more? > When might the sender encounter lost packets? The bandwidth*delay product here is 2 packets/sec * 2 sec = 4 packets. For W<4, the bottleneck link is not fully utilized. At W=4, the bottleneck link is fully utilized, but the average queue size is 0. If W>4, then packets pile up at a queue somewhere (possibly at the sender, if the first link is the bottleneck link), increasing the RTT. We will still have W = 2 pkts/sec * RTT_new; packet spend the additional time RTT_new - RTT waiting in queues. There will in general be W-4 packets at any given time in queues. When W is large enough -- quite a bit larger than 4 -- some queue may overflow and packet losses will begin. =============== > 7. (a). Explain why BGP speakers exchange full AS-paths to each > destination. > (b). Explain the tradeoff between route aggregation using CIDR > (eg of all routes to a provider's customers and subcustomers > into a single entry), and the use of AS-paths as above. > How is this usually resolved? BGP speakers exchange full AS-paths to be able to detect loops; if the same AS appears more than once, there is a loop. If CIDR aggregation is done, then ASs aggregated into one block may have different AS-paths: AS1------AS2------------AS3 200.0.0/24 200.0.1/24 In this picture, AS2 can announce both its address block and that of AS3 via the CIDRized prefix 200.0.0/23 (that is, the 24th bit can be either 0 or 1). However, the two blocks have different AS-paths: AS2's path is just , while that for AS3 is . AS2 can report the longer path, which guarantees that all loops will be detected, but which also makes reaching AS2 appear to involve two ASs. The usual solution is to split the path into AS-seq and AS-set; the AS-seq is the common prefix *sequence*, in this case , and the AS-set is the set of any other ASs that may or may not be involved in reaching the given destination, in this case {AS2}.