messages along these routes. You must use a link-state protocol, and use Dijkstr

ID: 3702468 • Letter: M

Question

messages along these routes. You must use a link-state protocol, and use Dijkstra's algorithm to compute routes. Requirements You should write one program, called router, which you will run multiple times on some combination of computers. A real router would have physical links to a few neighbors. Instead, your simulated router will exchange UDP packets with a few neighbor programs. a Your programs should not talk directly to non-neighbors:"*m just as on a real network, all communication to non- neighbors should be via neighbors. ck Interface Requirements Your program should accept arguments as follows: myhost%./router id port host! porti host2 port? .. an ( 5 The id is a number between 0 and 19 inclusive that Zo ho should be unique over all programs in a particular simulated network. The port is the number of a UDP port on which your program should send and receive packets. anutout clust

Explanation / Answer

To demonstrate Dijkstra's algorithm, one should compute the shortest-path tree for Router 6.

Following are the steps of the program:

#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;

}

Creating graph is the first step. Here graph is stored in Figure 2 in Graphviz dot file. This Graphviz package supplies tools which set up automatic tools and draw graphs which is available in http://www.graphviz.org. A special file format for graphs is used in Graphviz tools and is called dot files. BGL admits a parser for reading this file format as a BGL graph. The parser can be accessed through the read_graphviz function defined in boost/graph/graphviz.hpp. Because the graph is directed, we use the GraphvizDigraph type. For an undirected graph, we can use the GraphvizGraph type.

·Read directed graph in from Graphviz dot file Ò?

GraphvizDigraph g_dot;

read_graphviz("figs/ospf-graph.dot", g_dot);

the properties of vertices and edges are stored stores as strings in GraphvizDigraph type. Even though strings are convenient for I/O, edge weights must be represented as integers for easy manipulation inside Dijkstra's algorithm. Therefore, g_dot is copied to a new graph. Each and every 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 labelattribute 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);

}

The vertex descriptor for the router must be located to use Router 6 as the source of the shortest-path search. 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

Dest

Next Hop

Total Cost

RT1

RT3

RT2

RT3

RT4

RT3

RT5

RT7

RT10

RT8

RT10

RT9

RT10

RT11

RT10

RT12

RT10

RT3

RT10

N10

RT10

N12

RT10

N13

RT5

N14

RT5

N15

RT10

Dest

Next Hop

Total Cost

RT1

RT3

RT2

RT3

RT4

RT3

RT5

RT7

RT10

RT8

RT10

RT9

RT10

RT11

RT10

RT12

RT10

RT3

RT10

N10

RT10

N12

RT10

N13

RT5

N14

RT5

N15

RT10

Navigate

messages along these routes. You must use a link-state protocol, and use Dijkstr

mester Programming Projec This program should illustrate and simulate the ethica

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.

messages along these routes. You must use a link-state protocol, and use Dijkstr

Question

Explanation / Answer

Related Questions

Navigate