## CMSC 417-F02 |
## EXAM 2 SOLUTION |
## Fall 2002 |

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.

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.

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}.

- 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.

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.