Homework 1: 22C:178 & 055:134

Computer Communications Fall 1998


1 [10 points] How can the stability and robustness of a routing algorithm come into conflict?

The robustness of a routing protocol is evaluated by the protocol's ability to quickly respond to changes in cost metrics (not just link failures); stability is the property that a protocol makes small changes in routing for small changes in link costs, so that the change to links costs is ``smooth'' over time. Quick changes can oppose stability, since stability is often implemented by a delay strategy in the routing protocol.
2 [5 points] Explain why bridges and extended LANs use a spanning tree algorithm.
A tree has no cycles; by routing only through the tree links, there will be no looping frames.
3 [5 points] What is RSVP in networking?
See textbook: it's a proposed protocol for adding QoS-like facilities to an IP network.
4 [10 points] What are two different techniques to make the Internet routing more scalable than just using link state or distance vector routing algorithms?
The first principle is to use hierarchical routing, exemplified by the network of autonomous systems; the second principle is route or address aggregation, so that similar addresses can have collapsed representations in the routing tables.
5 [5 points] Describe a situation where congestion interferes with routing.
Since routing is the process of determining the routing tables, congestion can interfere with that process by causing the loss of messages between switches used to build and adjust the routing tables.
6 [10 points] ATM uses fixed length cells of 53 bytes with 48 bytes of payload per cell. In what sense does the small cell size improve switch performance compared to switching larger packets (for instance, 4KB packets)?
First, small cells allow better time division, resulting in a fairer performance (whereas long packets could block output lines for some time). Second, the small predictable size makes it possible to build efficient and even parallel hardware to switch cells in quantity. Third, the small fixed cell size enables the prediction of delay over lines and through switches, which is important for some voice applications. Other miscellaneous factors are that less data needs to be resent if there are occasional errors, perhaps some hardware optimizations are easier related to noise for the smaller cell size, and similar low-level concerns.
7 [5 points] Shortest-path routing is called dynamic if it adjusts to changes in link costs as they occur and all packets are forwarded on shortest-path routes. Why is dynamic shortest-path routing easier to implement for an IP network than for an ATM network?
ATM provides virtual circuits, which guarantee in-order delivery of the cells sent: ATM is connection-oriented. Changing the path in the middle of a connection wouldn't guarantee in-order delivery; to change the path, the VC should be torn down and a new one set up. Better yet, the new VC should be all set up before the old one is torn down, and there needs to be a careful path migration algorithm to do this. Datagrams, on the other hand, can be rerouted or arbitrarily switched at any time, so dynamic adjustments are easily tolerated.
8 [5 points] Suppose a routing algorithm makes shortest path selection based on link costs defined as follows. The cost C.m of a link m is C.m = 1 + Q.m where Q.m is, at any given moment, the current amount of bytes queued up to be sent on link m. What would be a disadvantage of such a cost definition? How could it be improved?
The two main disadvantages are the uniform treatment of unequal links and the instability of the cost metric. For the unequal links, the metric should take into account other factors, such as delay, utilization, bandwidth, and such. For the instability, two ideas are to compress the range of possible values (instead of strictly measuring a byte count) and to time-average the queue length for a reasonable period to obtain the cost.
9 [5 points] Consider a special purpose network for a battlefield, where hosts are mobile (moving around) and links are highly unreliable, What would be the best routing algorithm for urgent messages in this type of network?
Flooding is the most reliable form of routing in conditions where links and hosts crash frequently; broadcasting is a similar idea.
10 [5 points] Self-routing fabrics such as the Banyan (or Batcher-Banyan, or the Sunshine switch) are able to switch multiple packets in parallel, whereas a conventional workstation architecture forwards packets one at a time. Are there situations where self-routing fabrics do not perform better than a traditional workstation architecture switch?
Several situations are possible. One is where packets arrive so slowly that workstations can keep up with the flow of forwarding tasks. Another situation is where packet destinations require inherently sequential processing, such as all going to the same output queue -- and that output queue is the bottleneck, not the switching speed.
11 [5 points] The following is taken from the output of the netstat command executed on the host tempest while the server for the final project was running.
   Active Internet connections
   Proto Recv-Q Send-Q  Local Address  Foreign Address        (state)
   tcp        4      0  tempest.7700   fog.divms.uiowa..4344  CLOSE_WAIT
The output from man netstat defines Recv-Q as ``The count of bytes not copied by the user program connected to this socket.'' It defines CLOSE_WAIT as ``The remote end has shut down, waiting for the socket to close.'' With your knowledge of TCP, explain (or speculate on) the current situation of the server from looking at this output.
The client has closed the connection, which cause it to send a FIN request to the server. This put the server's TCP into the CLOSE_WAIT state. Meanwhile, the server still hasn't read 4 bytes previously sent by the client. After the server reads these 4 bytes, the connection will close on the server side as well.
12 [5 points] What factors determine how many bits are needed to represent a TCP connection number?
The answer ``it depends on the maximum number of concurrent connections'' is only a superficial response. The main concern is to ensure that old connection datagrams are not confused with newer connections. To do that we must not re-use connection numbers until certain that the old connection numbers are inactive. This is a function of the maximum datagram lifetime, the maximum number of TCP connects per second, the network capacity, and in the case of randomly selected TCP connection numbers (actually the initial values on window byte sequence numbers), the probability of a random duplication between distinct connections.
13 [10 points] Does congestion cause the TCP AdvertisedWindow to become small? Why or why not?
No: congestion causes TCP's CongestionWindow to decrease, not the AdvertisedWindow -- this is done to decrease the rate of flow on a connection, backing off and hopefully easing the congestion.
14 [5 points] What should endpoints in a TCP connection measure to estimate contention in switches between the two endpoints?
The endpoints should measure RTT statistics by calculating the time for an ACK on a packet to return (except for resent / lost packets).
15 [5 points] A conferencing application uses ATM to make virtual circuits between members of the conference. The application specifies constant bit rate (CBR) during the VC setup to guarantee voice fidelity for its QoS. The audio signals are digitized using PCM. The digitized audio could further be compressed using MPEG or a similar method, but even though compression reduces the size of transmitted data by 70% on average, there is no guarantee that data will be reduced (it depends on what kind of audio signal the data has). Would it be helpful to use data compression in this case? Why or why not?
The answer is no from the point of view of the endpoints of the circuit. The CBR is calculated to cover the worst case needs of the application, so there is no benefit to compression. However the answer could be yes from the point of view of the switches: if an application sends out fewer cells per second, then there will be extra room for other ABR traffic on the lines.
16 [5 points] For the problem of secure identification between two parties in a network, why is randomness an important tool for protecting against an eavesdropper? For what technical reason does randomness help?
At a simple level, the randomness hides patterns so that Eve cannot deduce the contents of messages during an identification procedure. More technically, the hash function has a random distribution of output values, and if the interactive proof procedure is used, then the questions and answers will be randomly chosen so that a replay cannot forge identification. In case RSA encryption is used, the randomness of the large prime numbers makes factoring the public key a difficult problem.