Home | Routing Introduction | Terminology | Overview | The Topology Database | Establishing Neighbors | Exchanging Topology Information | Creating The Routing Table | OSPF Routing

The SPF problem

The OSPF protocol, as has been stated before, calculates the routing table for each router by solving the SPF problem on the topology graph stored at that router. In the literature, this problem is also referred to as the "Single-Source Shortest Paths" problem. The definition of the SPF problem is this:

"Given a directed weighted graph and a vertex in it, find a sub-graph of the graph which is a tree graph, on which the weight along the path from the specified vertex to any other vertex is equal to the lowest weight path from the same source to the same destination on the original graph".

For each router's topology graph a solution to the SPF problem will be calculated, and from that tree the routing table will be constructed. Note that in our case, the weight of the edge is the cost of the link.

Dijkstra's algorithm - a solution to SPF

One proven and well-known algorithm to solve the SPF problem for a given weighted directed graph and a vertex in it is the Dijkstra algorithm. Dijkstra's algorithm assumes all the weights on the graph are non-negative, but, since in OSPF there is no reason to assign negative numbers, it can and in fact is used in the OSPF protocol.

To describe the algorithm, let's first explain the various symbols that will be used in its description. The directed weighted graph will be denoted G, its group of vertices will be denoted V, and its group of edges will be denoted E. An edge will be denoted as a pair of vertices. For example, (v,u) will denote and edge starting from v and ending in u. The weight associated with the edge (v,u) will be denoted w(v,u). The algorithm works by maintaining a set S of vertices for whom we already figured out the minimum cost of path from the given vertex. The denomination d[v] will state the lowest cost of route from the given vertex to vertex v we found at a certain time. The algorithm also keeps a priority queue Q of the vertices in G, in which the vertices are ordered according to their d[v] values. In addition to all of those, for each vertex v the algorithm also denoted by p[v] the predecessor of v. The p[v] value can be either NULL or a vertex, and, when the algorithm is complete, for every vertex other than the source vertex for which the algorithm is run will have a non-NULL predecessor, and determining the lowest-cost path from v to the source vertex will be easily done by running on the predecessor of v, and the predecessor of the predecessor of v, and so on, until arriving at the source vertex.

So, given a weighted graph G and a source vertex s, the algorithm is the following:

  1. For every vertex v in V such that v isn't s, set d[v]=infinity and p[v]=NULL. Also set p[s]=NULL, and d[s]=0.
  2. S is now an empty set.
  3. Insert into the priority queue Q all the vertices in V.
  4. While Q isn't empty, do:
    1. Mark u as the minimum item in the priority queue Q.
    2. Add u to S.
    3. For every vertex v in the adjacency of u, if d[v] > d[u] + w(u,v), then do:
      • d[v]=d[u]+w(u,v)
      • p[v]=u
The algorithm's proof shows that the algorithm ends in a finite time, and in the end, for a given vector v and the source vector s, the path of:

s->p[p[p[p[p...[p[p[p[v]]]...]]]]] -> ... -> p[p[v]] -> p[v] -> v

is a path that is in G, and it has a cost that is equal to the lowest cost of a path from s to v in G.

Thus, Dijkstra's algorithm finds the shortest paths tree from the source vertex to every other vertex in G. Here's an example of running the algorithm on a relatively straightforward directed weighted graph:

example run of the algorithm

Creating the routing table using the Dijkstra algorithm

We use Dijkstra's algorithm for creating the routing table for each OSPF router in the following manner. First, we determine, for each network and link, what is its cost. Then, for each router, we run Dijkstra's algorithm on the topography graph (stored in its topography database), with itself as the source vertex.

Now, for every network in the AS, we will look at its vertex in the graph. We already saw how to get the path to that vertex from the result of the algorithm, but in the routing table we only need the next hop, so we take the first router that appears in path which isn't the source router, and that, clearly, is the next hop router (since no two networks are connected with an edge). If there is no such router, then the next hop does not exist and the packet to be routed is locally generated and the router does not forward it.

We're just about done. We've constructed the discovered neighbors, exchanged topology information, and built the routing table. All that is left to discuss is how weights are determined in the graph.

The weights on each link are of course determined by the network administrators, which can have their own reasoning as to how to assign costs, but in most circumstances, three elements should effect the decision of determining the cost:
Line delay, Connection throughput and Network connectivity. Delay and throughput are especially important when routing according to type of service (which will be described later), and the connectivity of the network (how good is the connect, how often does it break down) is naturally a topology factor as well. One OSPF standard uses the bandwidth itself as the direct basis to computing the weights of links and networks, by determining that the weight of a line is 10^8 divided by the bandwidth of the line. Thus for example the cost of a 56Kbps link is 10^8 / 56000 = 1785, the cost of a T1 link is 10^8 / 1544000 = 64, and the cost of a 100MB Ethernet is 10^ 8 / (100 * 10^6) = 1.

Created 2002 by Meir Marom & Gil Berkovski