17.2.4 Routing

The current status of routing is that it is incomplete. Ideally, one should be able to run all existing ns routing protocols over satellite links. However, many of the existing routing protocols implemented in OTcl require that the conventional ns links be used. Contributions in this area are welcome, but unfortunately it is not a trivial change.

With that being said, the current routing implementation is similar to Session routing described in Chapter 30, except that it is implemented entirely in C++. Upon each topology change, a centralized routing genie determines the global network topology, computes new routes for all nodes, and uses the routes to build a forwarding table on each node. Currently, the slot table is kept by a routing agent on each node, and packets not destined for agents on the node are sent by default to this routing agent. For each destination for which the node has a route, the forwarding table contains a pointer to the head of the corresponding outgoing link. As noted in Chapter 30, the user is cautioned that this type of centralized routing can lead to minor causality violations.

The routing genie is a class SatRouteObject and is created and invoked with the following OTcl commands:

set satrouteobject_ [new SatRouteObject]
$satrouteobject_ compute_routes

where the call to compute_routes is performed after all of the links and nodes in the simulator have been instantiated. Like the Scheduler, there is one instance of a SatRouteObject in the simulation, and it is accessed by means of an instance variable in C++. For example, the call to recompute routes after a topology change is:

SatRouteObject::instance().recompute();

Despite the current use of centralized routing, the design of having a routing agent on each node was mainly done with distributed routing in mind. Routing packets can be sent to port 255 of each node. The key to distributed routing working correctly is for the routing agent to be able to determine from which link a packet arrived. This is accomplished by the inclusion of a class NetworkInterface object in each link, which uniquely labels the link on which the packet arrived. A helper function NsObject* intf_to_target(int label) can be used to return the head of the link corresponding to a given label. The use of routing agents parallels that of the mobility extensions, and the interested reader can turn to those examples to see how to implement distributed routing protocols in this framework.

The shortest-path route computations use the current propagation delay of a link as the cost metric. It is possible to compute routes using only the hop count and not the propagation delays; in order to do so, set the following default variable to "false":

SatRouteObject set metric_delay_ "true"

Finally, for very large topologies (such as the Teledesic example), the centralized routing code will produce a very slow runtime because it executes an all-pairs shortest path algorithm upon each topology change even if there is no data currently being sent. To speed up simulations in which there is not much data transfer but there are lots of satellites and ISLs, one can disable handoff-driven and enable data-driven route computations. With data-driven computations, routes are computed only when there is a packet to send, and furthermore, a single-source shortest-path algorithm (only for the node with a packet to send) is executed instead of an all-pairs shortest path algorithm. The following OTcl variable can configure this option (which is set to "false" by default):

SatRouteObject set data_driven_computation_ "false"