1. Consider the following network example. With the indicated link costs along each link in the figure, use Dijkstra's shortest-path algorithm to compute the shortest path from x to all network nodes. Show how the algorithm works by computing a table.
Answer: Let N' denote the set of nodes whose distance have been known so far, D(s) be the distance to a node s, and p(s) be the parent node of the node s on the shortest path from s to node x. We then construct the following table.
2. Consider the following network example. Suppose that the distance vector (DV) routing algorithm is used to compute the distance between nodes.
(a) Show the procedure of nodes X, Y and W computes their Distance Vector for network illustrated by Figure (a), i.e., link costs are C(xw)=1, C(xy)=4, and C(yw)=8.
Answer: In the following, each column shows the node X, Y and Z's table update respectively:
(b) Assume that after the DV is computed by all nodes, the link cost of xy changed from 4 to 20. Show the procedure of nodes X, Y and W updates their Distance Vector for network illustrated by Figure (b), i.e., link costs are C(xw)=1, C(xy)=20, and C(yw)=8.
Answer: In the following, each column shows the node X, Y and Z's table update respectively:
* If not enough, add more tables by yourself
3. We studied Dijkstra's link-state routing algorithm for computing the unicast paths that are individually the shortest paths from the source to all destinations. The union of these paths might be thought of as forming a shortest path tree. If each links has an associated cost and the cost of a tree is the sum of the link costs, then a spanning tree whose cost is the minimum of all of the spanning trees is called a minimum spanning tree. Both shortest path tree and minimum-spanning tree can be used for broadcast routing. By constructing a counterexample, show that the least-cost path tree is not always the same as a minimum spanning tree.