TWiki home TWiki > Simulation > Tutorials > PopulatingTheRoutingTableAutomaticallyDijkstra TWiki webs:
Main | TWiki | Know | Sandbox
Simulation . { Changes | Index | Search | Go }

Step 14: Populating the Routing Table Automatically with Dijkstra's Shortest Path Algorithm

Populating the routing tables in each node is unwieldy and certainly not scalable. Fortunately OMNeT++ provides ways for us to access the topology information for the network we have defined, and once this information is known, it is not hard to calculate what the routing tables should be.

In this tutorial we use some OMNeT++ commands to access the topology and use this information to implement Dijkstra's shortest-path algorithm to calculate the routing tables. A detailed discussion of the operation of Dijkstra's shortest-path algorithm can be found here. Note that, OMNeT++ has also an internal implementation for finding the shortest paths but we will not use it here. See the Section 6.7 (Routing Support: cTopology) of the OMNeT++ Manual for further details.

We use a cTopology object to store all of the topology information: 

    cTopology network;
The topology information and the number of nodes in the network found are placed in this object: 
    network.extractByModuleType("Txc14",NULL);
    int V = network.nodes();
Each node has a number of links attached to it: 
    numLinks=network.node(u)->outLinks();
The topology information allows us to access the nodes connected to the remote ends of these links: 
    n = network.node(u)->out(i)->remoteNode();
These constructs allow us to access all of the information needed for Dijkstra's algoritm. The algorithm produces a predecessor sub-graph that tells us the last node that is transversed on the shortest path to a given destination. By backtracking through this we can work out the first hop on the shortest path and using the following construct, work out which gate on the source connects to the shortest path: 
    rt[i] = network.node(i)->in(v)->remoteGate()->index();
With the routing tables are now correctly populated, the same code used in the previous exercise forwards messages out the correct interface for the shortest path from source to destination.

Exercise: Now that the routing tables are populated automatically, try altering the topology by editing the .ned file to see what happens to the mean hop count in different network topologies. You can try large rings, and see what happens when extra links are added.

Here are the files:

(This tutorial is BrettPentland's creation. Thanks Brett.)

Topic PopulatingTheRoutingTableAutomaticallyDijkstra . { Edit | Attach | Ref-By | Printable | Diffs | r1.1 | More }
Revision r1.1 - 29 Sep 2005 - 00:49 GMT - AhmetSekercioglu
Parents: WebHome > Tutorials 		Copyright © 1999-2003 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback.