Problem 5. Link State Routing (30 pt.)

Consider the following network.

a. (16 pt.) With the indicated link costs, use Dijkstras shortest-path algorithm to compute the shortest path from w to all network nodes. Show how the algorithm works by computing the table below. Note: If there exists any tie in each step, choose the left-most column first.

Step	N	D(s), p(s)	D(t), p(t)	D(u), p(u)	D(v), p(v)	D(x), p(x)	D(y), p(y)	D(z), p(z)
0
1
2
3
4
5
6
7

b. (7 pt.) Construct the shortest path tree from the above routing table (Hint: Slide 4-86).

c. (7 pt.) Construct a forwarding table from the above routing table (Hint: Slide 4-86).

Destination	Link

12 39 u 5 1 2 3 3 4 3 6 12 39 u 5 1 2 3 3 4 3 6