22C178 / 055:134 Final Examination
Note: to make the answers readable, longer forms (exceeding the maximum number of words) in complete sentences are provided after the questions.
1 [5 points, 20 words] What distinguishes congestion control from flow control ?
Flow control deals with the issue of a sender overrunning the receiver's buffers, whereas congestion control deals with senders overrunning the network buffering capacity.2 [5 points, 15 words] How do contention and congestion differ in how a router behaves?
With contention, a router must queue incoming packets before sending them to output links; but for congestion, routers drop packets.3 [5 points, 15 words] Why is the window size used in a TCP connection not a fixed number?
Because the network is dynamic, controlling for congestion and changing delays, the window size dynamically adjusts, attempting to optimize.4 [5 points, 25 words] In the Internet, it can be that a datagram actually travels over an ATM network as it travels from source to destination. Thus, IP can be implemented by ATM links. Explain why the converse (implementing ATM with IP) is not feasible.
ATM supports virtual circuits with QoS guarantees and cells are always delivered in the order sent (at least the ones that successfully arrive). IP datagrams are delivered on a best-effort basis, with no QoS guarantees. This lack of a guarantee makes implementation infeasible.5 [5 points, 15 words] The end result of both distance-vector and link-state algorithms are routing databases, which have entries for each destination and the ``next hop'' for that destination. Why then does the textbook claim that the link-state algorithm requires more memory than the distance-vector algorithm?
For the link-state algorithm, a switch must first collect LSP's for the entire network -- which is not necessary in the distance-vector calculation.6 [5 points, 25 words] The ftp application uses TCP to make a connection for file transfer. The ftp application uses CRC-32 to verify that file transfer is correct (i.e. no bytes in the file have been corrupted). However, each packet in a TCP connection also has a checksum field; moreover, each IP packet has a checksum field as well. It would seem like these checksums are redundant, since the CRC-32 field will detect any transmission errors in a file transfer. Explain why the checksum fields are still advantageous in this situation.
The textbook's discussion of the end-to-end argument in Chapter 6 provides one answer. Although the lower level CRC fields are redundant, they improve performance by detecting and retransmitting at a lower level in the network. Also, the IP and TCP checksums only cover headers, not the data -- they protect routing and multiplexing from erroneous behavior. Full credit answers mention the performance advantage.7 [5 points, 20 words] The congestion control algorithm devised by Van Jacobson is self-clocking and only the endpoints participate in the algorithm. This algorithm sometimes shows a ``sawtooth pattern'' in its throughput over time. What causes this pattern?
The answer to this question can be summed up in the phrase ``additive increase, multiplicative decrease'' which describes how TCP adjusts its window size as it reacts to timeouts.8 [5 points, 30 words] Congestion control is not usually an issue for the telephone companies, since they use virtual circuits preallocating buffers -- which avoids the issue of congestion. Explain how congestion can (at least partially) be avoided even in a datagram network.
This question is an invitation to cite one of the congestion avoidance mechanisms described in Chapter 8 of the textbook: TCP Vegas, RED gateways, etc. Citing ``reservation based on flows'' isn't a full credit answer -- mention of the ``soft state'' would also be needed to emphasize that no formal reservation policy is used. Keep in mind that there don't need to be flows in a datagram network, though usually there are flows in the short term.9 [5 points, 25 words] What is head-of-line blocking ?
The definition is given in the chapter on switching. Basically, an input queue at a switch contains items for several output lines, and one of the output lines is currently idle. Yet because the input queue is handled in FIFO order, some packet behind the head of the queue that should be allowed to leave on an idle output line cannot because it waits for the head of the queue to finish on another output line (this question is best answered with a picture, as shown in the book).10 [5 points, 10 words] Does the Border Gateway Protocol use the link-state or the distance-vector protocol?
It uses neither approach, but instead uses a path-based routing algorithm described in the textbook.11 [5 points, 15 words] A programmer claims that TCP's three-way handshake can be simplified to a two-way handshake if RSA public-key encryption were used with a random DES session key to secure each connection. What justifies the programmer's claim?
Using RSA and a random DES key makes it extremely unlikely to confuse different incarnations of a TCP connection, hence we may reduce the handshake from three-way to two-way (in practice this would be difficult because the header formats would need to change so that the encrypted fields could be used.)12 [5 points, 25 words] Bridges can be used to connect LANS without the overhead of routing algorithms. What is a disadvantage of the bridge technique? (For full credit, you need specific disadvantages -- the answer ``not scalable'' is too vague for credit.)
From the textbook: (1) there is no provision for a hierarchy on the extended LAN, (2) bridges do not generalize to all forms form of LANs, for instance there is no way to combine Ethernet and ATM, (3) transparency can result in unexpected behavior (congestion at bridges, unpredictable latency).13 [5 points, 40 words] Give an example of how congestion control is useful even if no routing decisions are involved in sending packets from source to destination.
Even on a single link, congestion can occur if too many flows inject packets faster than the link can handle. Congestion control will slow down the rates of these flows so that the link can keep up. Note that this is not flow control, because overflow of a receiver's buffer is not the issue.14 [5 points, 30 words] Suppose a network uses source routing to switch packets through the network. Which routing algorithm would be better as a starting point to implementing source routing, distance-vector or link-state? (Neither of these directly supports source routing, but will require modification.) Explain why your answer is better than the other alternative.
The easiest way to enable source routing is if the sender has a complete picture of the network. The link-state algorithm provides just this kind of input (although port numbers would have to be added to the LSPs). The distance-vector algorithm does not provide enough information to neighbors about entire paths, so it is not so easily used.15 [5 points, 25 words] One way to define the ``cost'' or ``routing metric'' of a link is the current delay packets experience between the time they arrive at the router and are sent on the output link. What is a disadvantage of this routing metric? (For full credit, you must explain your answer.)
The textbook considers using delay as a routing metric, but notes that it leads to instability because it can change frequently and can have large variance.16 [5 points, 20 words] Suppose you have an application running on an internet using TCP to transmit data between two endpoints. One of the network links in the connection is actually an ATM network maintaining a permanent virtual path to support the link. Should your application be coded so that it only writes byte streams of 48 bytes or less? Why or why not?
The purpose of the AAL 3/4 and AAL 5 layers is exactly this, to segment and reassemble from sender to receiver -- your application need not do this itself. In fact, the AAL layers may be able to do a better job of it than your application could by using special hardware assistance. Why not use the services that are available?17 [5 points, 20 words] The spanning tree bridge protocol supports multicast operations as well as unicast transmissions. What change is needed by hosts participating in the multicast so that the bridge protocol works properly?
The textbook explains that, in order for bridges to automatically ``learn'' the members of a group, the members should periodically send messages as well as receive messages from others in the group.18 [5 points, 10 words] Consider a banyan network with 16 input and 16 output ports. There are 32 switching elements, each of which is a 2x2 element, and these elements are arranged in 4 columns with 8 elements in each column. Consider the fifth switching element from the top in the first column of the network, call it M. Element M has two input ports and two output ports. What two switches in the second column are connected to M?
The fifth element from the top in the first column is actually at the top of the bottom half. In the wiring between first and second columns, one line goes horizontally to the corresponding element in the second column. The other line goes to the top of the top half in the second column. So the answer is ``the first and fifth switching elements of the second column''. (Note: other books use different banyan layouts and could give a different, but isomorphic solution. Tom Leighton's authoritative book Introduction to Parallel Algorithms and Architectures defines a banyan network to be any network for which there is a unique path from each input to each output. But we follow the layout of our textbook for this question and solution.)19 [5 points, 15 words] A certain Data Communications class at the University of Iowa decides to experiment with a microwave Ethernet, where students can carry laptops around the building and have wireless connections to the Ethernet at about 150Kbps. These connections are noisier than the usual 10base-T hardware, resulting in data errors as often as 8% of the time. The students observe that while logins to departmental machines seem to have normal delay and are near the expected bandwidth of 150Kbps, the bandwidth to remote sites (such as www.yahoo.com) is often considerably less. What could explain this situation? (Students working on the regular hardwired Ethernet do not observe this behavior of reduced bandwidth while connecting to remote sites.)
Note that TCP cannot distinguish between packets being dropped due to congestion and some drops due to errors. Packets lost cause a multiplicative decrease in congestion window size. For this problem, latency is a significant factor. For connections within the building, latency is not as important -- the addititive increase in the congestion window size will result in fairly rapid resumption of adequate bandwidth. But for remote sites, the additive increase could take longer because of the longer RTT, so ramping up to normal bandwidth will be noticeable to users.20 [5 points, 45 words] Consider the following queuing algorithm for contention management. To choose the next packet to be sent on an output link, the router chooses packets in round-robin order from all input flows directed to the output link, skipping over flows that do not have any input packets ready to send. Why is this algorithm unfair? Under which circumstances would the algorithm be fair?
Large packets essentially get favorable treatment, since after sending a small packet from one queue, the algorithm just goes to the next queue. For the algorithm to be fair, all packets should be the same size. Even this is not quite fair -- there are some situations with uneven arrival rates where certain queues are skipped more than others. We could also specify that arrival rates should be equal.