1. [15 points] The network shown below uses distance-vector routing. Assume that the given link costs apply to both directions and do not change over time. What are the contents of the routing table (i.e. next hops and distances) at node C after the routing updates have stabilized.

      destn  next hop  distance
     ---------------------------------
      A       A         2
     ---------------------------------
      B       A         3
     ---------------------------------
      C       -         -
     ---------------------------------
      D       D         1
     ---------------------------------
      E       D         3
 or   E       A         3
     ---------------------------------

GRADING. Roughly 3 points for each line.

2. [15 points] Briefly explain two significant advantages and one significant disadvantage of hierarchical routing?

(advantage) Routing table sizes are smaller because a router does not have to keep track of individual nodes in other networks (or clusters).

(advantage) Next-hop (or route) calculation is quicker because the routing table is smaller.

(advantage) Less communication cost because smaller network state to be propogated.

(advantage) Each network can run a distinct routing algorithm.

(disadvantage) There can be nonoptimal routes between nodes in different networks, say X and Y, because routes between any two nodes X.i and Y.j are forced to use the same network-level hops, say X, U, V, Y, and this may not be optimal for some node pairs.

GRADING. 5 points for each advantage or disadvantage with explanation. 2 to 3 points if no explanation given.

3. [10 points] Consider a network where the links can fail and recover very frequently, for example, as often as once every 100 ms. What kind of routing algorithm would you use here and why?

The network connectivity changes too rapidly for an adaptive approach; i.e., it would be too expensive and inaccurate to track the changes. Hence FLOODING is the only option.

GRADING. Mostly all or nothing.

4. [25 points] A host's sends to a network via a token bucket. The token bucket has a capacity of 15 Mbits and is filled with tokens at the rate of 5 Mbits/sec. Data is buffered if it arrives at the token bucket when there are no tokens. How long does it take for 30 Mbits to enter the network assuming that the host sends at a peak rate of 20 Mbits/sec and the token bucket is initially full.

  Host ----------> Token bucket ---------------> Network
        20 Mbps   capacity 15 Mb
                  rate 5 Mbps

GRADING. 5 points for the basic idea of token bucket. 10 points if you ignored the token bucket being initially full, and hence got 6 seconds (from 30 Mbits at 5 Mbps). 20 points if you ignored the tokens that arrive while the first 15 Mbits is being sent and hence sent 15 Mbits in your burst; the answers ranged from 3 seconds to 4 seconds (depending on how much time was chosen for the burst).

5. [35 points] A TCP connection uses the standard congestion control mechanism to transfer a file of 100 Kbytes using maximum segment size of 2 Kbytes. The receive window size is always 20 Kbytes. The threshold is initially 16 Kbytes. The roundtrip time estimate is initially 100 msec. No losses occur during the file transfer. The measured roundtrip time is always 60 msec.

How much time does it take to transfer the file? What is the roundtrip time estimate after the fourth transmission? What is the roundtrip time estimate at the last transmission? Assume alpha (for roundtrip time calculation) equals 1/2.

 trans#  cong wnd size     total sent   rtt (estimate)

   1       2 K                2 K        100
   2       4 K                6 K        80 (=(100+60)/2)
   3       8 K               14 K        70 (=(80+60)/2)
   4      16 K (=threshold)  30 K        65 (=(70+60)/2)
   5      18 K               48 K        62.5 (=(65+60)/2)
   6      20 K (=rec wnd)    68 K        61.25 (=(62.5+60)/2)
   7      20 K               88 K        60.625 (=(61.25+60)/2)
   8      12 K              100 K        60.3125 (=(60.625+60)/2)