Optimization Theory (DS2) HW#5
Shortest Path from Dijkstra to OSPF

Abstract

Is it true that OSPF and Dijkstra give the same result?

In class, I talked about two forms of Dijkstra’s algorithm:

  • •

    The source-destination form, which starts from a source and searches the graph until it finds the named destination, then quits.

  • •

    The all-destinations form, which builds a spanning tree that can be used to identify the shortest path to all possible destinations.

In this homework, we will look at the latter form and examine a specific set of paths. We’ll use the same graph we used during class, in Fig. 1.

The Internet’s Open Shortest Path First protocol (see RFCs 2328 and 5340), which I briefly described, uses Dijkstra’s algorithm. Each node collects information about the set of nodes and links, and the link costs, then independently calculates its own shortest path spanning tree. The Internet only works if the set of spanning trees calculated by the nodes are consistent enough to guarantee that packets don’t get stuck in a loop somewhere. In this homework, we are examining that proposition.

  1. 1.

    First, for single paths:

    1. (a)

      Identify the shortest path from A to E on the graph. Although the edges in the original graph are undirected, this path will be directed.

    2. (b)

      For each node in that path other than A and E, find the shortest (directed) path to E. (e.g., if the A-E path is four hops, you will have three other paths to E, one starting at each of the other nodes.) Is the set of edges in all of those paths a subset of the edges of the original A-E path? Are all of the edges oriented in the same direction?

  2. 2.

    Next, for trees:

    1. (a)

      Find the shortest path spanning tree (not the minimum cost spanning tree! Remember, they are (or can be) different.) for node A, including paths to all of the other nodes. Again, the edges should be directed.

    2. (b)

      Select a second node. Find the shortest path spanning tree for it.

    3. (c)

      Compare the two trees: Which portions of the trees are identical, which different?

    4. (d)

      Construct a “Next Hop” table for each of the two nodes. Describe any similarities or differences you see.

  3. 3.

    If the shortest path from A to some other node Z passes through nodes X and then Y, can it ever be the case that the shortest path from X to Z does not pass through Y? Why or why not?

Figure 1: Our nine-vertex, fourteen-edge figure from Intro to Algorithms.