Internet Packet Routing with the Boost Graph Library

Like this article? We recommend

Boost Graph Library, The: User Guide and Reference Manual

Learn More Buy

Like this article? We recommend

Like this article? We recommend 

Boost Graph Library, The: User Guide and Reference Manual

Learn More Buy

Dijkstra and Link-State Routing

By the early 1980s, concerns began to arise about the scalability of distance-vector routing. Two particular aspects caused problems:

• In environments in which the topology of the network changes frequently, distance-vector routing converges too slowly to maintain accurate distance information.

• Update messages contain distances to all nodes, so the message size grows with the size of the entire network.

As a result of these problems, link-state routing was developed. With link-state routing, each router stores a graph representing the topology of the entire network and computes its routing table based on the graph using Dijkstra's single-source shortest-paths algorithm. To keep the graph up-to-date, routers share information about which links are up and which are down (the link state). When connectivity changes are detected, the information is flooded throughout the network in what is called a link-state advertisement.

Because only local information (neighbor connectivity) has to be shared, link-state routing does not have the message size problems of distance vector routing. Also, because each router computes its own shortest paths, it takes much less time to react to changes in the network and recalculate accurate routing tables. One disadvantage of link-state routing is that it places more of a burden on each router in terms of computation and memory use. Even so, it has proved to be an effective protocol and is now formalized in the Open Shortest Path First (OSPF) protocol (see RFC 1583), which is currently one of the preferred interior gateway routing protocols.

So how does the OSPF protocol work? As mentioned previously, it uses Dijkstra's algorithm. This algorithm finds all the shortest paths from the source vertex to every other vertex by iteratively growing the set of vertices (S) to which it already knows the shortest path. At each step of the algorithm, the vertex in the set V – S with the smallest distance label is added to S (V is the set of all vertices in the graph). Then the out edges of the vertex (call it vertex u) are "relaxed"—that is, for each edge (u,v), the distance of vertex v is updated according to this statement: d[v] = min(w(u,v) + d[u], d[v]) (where w(u,v) is the weight of the edge (u,v) and d[u] gives the shortest known distance to vertex u). The algorithm then loops back, processing the next vertex in V – S with the lowest distance label. The algorithm finishes when S contains all vertices reachable from the source vertex.

The rest of this article shows how to use the BGL dijkstra_shortest_paths function to solve the single-source shortest-path problem for a network of routers and illustrates how this information is used to compute a routing table. Figure 2 shows the example network described in RFC 1583. In the figure, RT stands for router, N stands for network (which is a group of addresses treated as a single destination entity), and H stands for host.

Figure 2 A directed graph representing a group of Internet routers using the same routing protocol. The edges are weighted with the cost of transmission.

To demonstrate Dijkstra's algorithm, you will compute the shortest-path tree for Router 6. The main steps of the program are as follows:

#include <fstream> // for file I/O
#include <boost/graph/graphviz.hpp> // for read/write_graphviz()
#include <boost/graph/dijkstra_shortest_paths.hpp>
#include <boost/lexical_cast.hpp>
int main()
{
  using namespace boost;
  · Read directed graph in from Graphviz dot fileÒ
  · Copy the graph, converting string labels to integer weightsÒ
  · Find router sixÒ
  · Setup parent property map to record the shortest-paths treeÒ
  · Run the Dijkstra algorithmÒ
  · Set the color of the edges in the shortest-paths tree to blackÒ
  · Write the new graph to a Graphviz dot fileÒ
  · Write the routing table for router sixÒ
  return EXIT_SUCCESS;
}

The first step is to create the graph. I have stored the graph from Figure 2 in a Graphviz dot file. The Graphviz package provides tools that automatically lay out and draw graphs; it is available at http://www.graphviz.org. The Graphviz tools use a special file format for graphs, called dot files. BGL includes a parser for reading this file format into a BGL graph. The parser can be accessed through the read_graphviz function defined in boost/graph/graphviz.hpp. Because the graph is directed, you use the GraphvizDigraph type. For an undirected graph, you would use the GraphvizGraph type.

·Read directed graph in from Graphviz dot file Ò∫ 
 GraphvizDigraph g_dot;
 read_graphviz("figs/ospf-graph.dot", g_dot);

The GraphvizDigraph type stores the properties of vertices and edges as strings. Although strings might be convenient for file I/O and display purposes, edge weights must be represented as integers so that they can be easily manipulated inside Dijkstra's algorithm. Therefore, g_dot is copied to a new graph. Each edge in the GraphvizDigraph type has a set of attributes stored in a std::map<std::string, std::string>. The edge weights from Figure 2 are stored in the label attribute of each edge. The label is converted to an int using boost::lexical_cast; then the edge is inserted into the new graph. Because the Graph type and GraphvizDigraph are both based on adjacency_list with VertexList=vecS, the vertex descriptor types for both graphs are integers. The result of source(*ei, g_dot) can thus be used directly in the call to add_edge on graph g.

· Copy the graph, converting string labels to integer weights Ò∫ 
 typedef adjacency_list<vecS, vecS, directedS, no_property,
   property<edge_weight_t, int> > Graph;
 typedef graph_traits<Graph>::vertex_descriptor vertex_descriptor;
 Graph g(num_vertices(g_dot));
 property_map<GraphvizDigraph, edge_attribute_t>::type
   edge_attr_map = get(edge_attribute, g_dot);
 graph_traits<GraphvizDigraph>::edge_iterator ei, ei_end;
 for (tie(ei, ei_end) = edges(g_dot); ei != ei_end; ++ei) {
   int weight = lexical_cast<int>( edge_attr_map[*ei]["label"] );
   property<edge_weight_t, int> edge_property(weight);
   add_edge(source(*ei, g_dot), target(*ei, g_dot), edge_property, g);
 }

To use Router 6 as the source of the shortest-path search, the vertex descriptor for the router must be located. The program searches for the vertex with an attribute label of RT6.

· Find router six Ò∫ 
 vertex_descriptor router_six;
 property_map<GraphvizDigraph, vertex_attribute_t>::type
   vertex_attr_map = get(vertex_attribute, g_dot);
 graph_traits<GraphvizDigraph>::vertex_iterator vi, vi_end;
 for (tie(vi, vi_end) = vertices(g_dot); vi != vi_end; ++vi)
   if ("RT6" == vertex_attr_map[*vi]["label"]) {
     router_six = *vi; break;
   }

Together, the shortest paths from Router 6 to all other routers form a shortest-path tree. An efficient way to represent such a tree is to record the parent of each node in the tree. Here you simply use a std::vector to record the parents.

· Setup parent property map to record the shortest-paths tree Ò∫ 
 std::vector<vertex_descriptor> parent(num_vertices(g));
 // All vertices start out as their own parent
 typedef graph_traits<Graph>::vertices_size_type size_type;
 for (size_type p = 0; p < num_vertices(g); ++p)
  parent[p] = p;

You are now ready to invoke Dijkstra's algorithm. Pass in the parent array as the argument to the predecessor_map named parameter.

· Run the Dijkstra algorithm Ò∫ 
 dijkstra_shortest_paths(g, router_six, predecessor_map(&parent[0]));

Next, set the color attribute of the tree edges to black, in preparation for printing the graph to a Graphviz dot file. The tree edges have been recorded in the parent array. For every vertex i in the graph, edge (parent[i],i) is a tree edge, unless parent[i] = i, in which case i is the root vertex or an unreachable vertex.

· Set the color of the edges in the shortest-paths tree to black Ò∫ 
 graph_traits<GraphvizDigraph>::edge_descriptor e;
 for (size_type i = 0; i < num_vertices(g); ++i)
   if (parent[i] != i) {
     e = edge(parent[i], i, g_dot).first;
     edge_attr_map[e]["color"] = "black";
   }

Now write the graph to a dot file. The default color for the edges is set to gray (for nontree edges). Figure 3 shows the computed shortest-path tree for Router 6.

· Write the new graph to a Graphviz dot file Ò∫ 
 graph_property<GraphvizDigraph, graph_edge_attribute_t>::type&
   graph_edge_attr_map = get_property(g_dot, graph_edge_attribute);
 graph_edge_attr_map["color"]="gray";
 write_graphviz("figs/ospf-sptree.dot", g_dot);

Figure 3 The shortest-path tree for Router 6.

The last step is to compute the routing table for Router 6. The routing table has three columns: the destination, the next hop that should be taken to get to the destination, and the total cost to reach the destination. To populate the routing table, entries are created for each destination in the network. Fill in the information for each entry by following the shortest path backward from the destination to Router 6 using the parent map. A vertex that is its own parent is skipped because either the vertex is Router 6 (the source vertex) or the vertex is not reachable from Router 6.

· Write the routing table for router six Ò∫ 
 std::ofstream rtable("routing-table.dat");
 rtable << "Dest  Next Hop  Total Cost" << std::endl;
 for (tie(vi, vi_end) = vertices(g_dot); vi != vi_end; ++vi)
   if (parent[*vi] != *vi) {
     rtable << vertex_attr_map[*vi]["label"] << "  ";
     · Follow path backward to router six using parentsÒ
   }

While following the path from each destination to Router 6, the edge weights are accumulated into the total path_cost. You also record the child of the current vertex because, at loop termination, this is the vertex to use as the next hop.

·Follow path backward to router six using parents Ò∫ 
 vertex_descriptor v = *vi, child;
 int path_cost = 0;
 property_map<Graph, edge_weight_t>::type
 weight_map = get(edge_weight, g);
 do {
   path_cost += get(weight_map, edge(parent[v], v, g).first);
   child = v;
   v = parent[v];
 } while (v != parent[v]);
 rtable << vertex_attr_map[child]["label"] << "   ";
 rtable << path_cost << std::endl;

Table 1 shows the resulting routing table.

Table 1 Routing Table for Router 6, Computed from the Shortest Paths in Figure 3