1 [10 pts]. Solution

Time       At B, dist to E        At C, dist to E        At D, dist to E
            via C  via E           via B   via D           via C   via E

0.1          3*     8               4*       2               3        1*

1.0          3*     8               4*      12              13        1*

1.1          5*     8               4*      12              15        1*

2.1          5*     8               6*      12              15        1*

3.1          7*     8               6*      12              17        1*

4.1          7*     8               8*      12              17        1*

5.1          9      8*              8*      12              19        1*

6.1          9      8*              9*      12              19        1*

7.1         10      8*              9*      12              20        1*

8.1         10      8*              9*      12              20        1*

* indicates the minimum distance entry

Stable at time 7.1.

GRADING:

• Entry at time 1.0 did not count toward grade.
• Max 2 points for stating that stable by time 2.1 or 3.1.
• Max 6 points for not getting it correct but showing that the min distance decreases by 2 every two iterations.
• Lose 1 point if everything correct but stabilization time.
• Lose 2 points if everything correct but started at time 2.1 (instead of time 1.1).
• Lose 2 points if only one line is wrong.

2 [10 pts]. Solution

a.

b.

          

          

c.

GRADING:

• Part a: 2 points for spanning tree. 2 points for aggregate flows.
• Part b: 1 point for each spanning tree.
• Part c: 2 points for aggregate flows.

3 [5 pts]. Solution treating "111" as "255"

Part a.

ISP A has 128.8.100.000 to 128.8.255.255, which can be advertised in many ways:

• The simplest way is to advertise {128.8.100.000/24, 128.8.101.000/24, ..., 128.8.255.000/24}.
• The optimal way to advertise {128.8.100.000/22, 128.8.104.000/21, 128.8.112.000/20, 128.8.128.000/17}.

01100100
01100101
01100110
01100111
          above addresses can be advertised as 128.8.100.000/22
01101000
01101001
 ...
01101111
          above addresses can be advertised as 128.8.104.000/21
01110000
 ...
01111111
          above addresses can be advertised as 128.8.112.000/20
10000000
 ...
11111111
          above addresses can be advertised as 128.8.128.000/17

ISP B can similarly advertise its addresses in many ways:

• The simplest is {129.6.100.000/24, 129.6.101.000/24, ..., 129.6.255.000/24}.
• The optimal is {129.6.100.000/22, 129.6.104.000/21, 129.6.112.000/20, 129.6.128.000/17}.

Part b.

• The simplest is {128.8.102.000/24, 128.8.103.000/24, ..., 128.8.255.000/24}.
• The optimal is {128.8.102.000/23, 128.8.104.000/21, 128.8.112.000/20, 128.8.128.000/17}.

ISP B has its old addresses and the addresses 128.8.100.000/24 and 128.8.101.000/24, which can be advertised in many ways:

• The simplest is {128.8.100.000/24, 128.8.101.000/24, 129.6.100.000/24, 129.6.101.000/24, ..., 129.6.255.000/24}.
• The optimal is {128.8.100.000/23, 129.6.100.000/22, 129.6.104.000/21, 129.6.112.000/20, 129.6.128.000/17}

GRADING:

• Part a: 3 points. 1 point for using a netmask of reasonable value.
• Part b: 2 points. 1 point for showing that ISP B advertises an additional range of addresses.

3 [5 pts]. Solution treating "111" as "111"

4 [5 pts]. Solution

a. Because the link state algorithm floods link cost updates, the updates originating at a node, say X, can arrive out of order at another node, say Y (because they took different paths and hence incurred different delays; note that each link itself introduces no reordering). So sequence numbers are needed for Y to ignore an older update than it has already received.

b. Because updates in the distance-vector algorithm travel only one link (they are not flooded), the updates that a node Y receives from another node X are always in order (some may get lost, but never reordered). So sequence numbers are not needed.

GRADING:

• Part a: 2 points. It is not sufficient to say that a node can receive old updates; what is important is that an old update not overwrite a more recent update. Flooding also is not a sufficient reason; flooding can be controlled simply by the TTL.
• Part b: 3 points.