@node Routing overview

@chapter Routing overview

@menu

* Routing architecture::

* Global centralized routing::

* Unicast routing::

* Multicast routing::

@end menu

ns-3 is intended to support traditional routing approaches and protocols,

support ports of open source routing implementations, and facilitate research

into unorthodox routing techniques.  The overall routing architecture

is described below in @ref{Routing architecture}.  Users who wish to 

just read about how to configure global routing for wired topologies

can read @ref{Global centralized routing}.  Unicast routing protocols 

are described in @ref{Unicast routing}.  Multicast routing is documented in

@ref{Multicast routing}.

@node Routing architecture

@section Routing architecture

@float Figure,fig:routing

@caption{Overview of routing}

@image{figures/routing, 6in}

@end float

Figure 11-1 shows the overall routing architecture for Ipv4.  The key objects

are Ipv4L3Protocol, Ipv4RoutingProtocol(s) (a class to which all 

routing/forwarding has been delegated from Ipv4L3Protocol), and Ipv4Route(s).

Ipv4L3Protocol must have at least one Ipv4RoutingProtocol added to

it at simulation setup time.  This is done explicitly by calling

Ipv4::SetRoutingProtocol ().

The abstract base class Ipv4RoutingProtocol () declares a minimal interface,

consisting of two methods:  RouteOutput () and RouteInput ().  

For packets traveling outbound from a host, the transport protocol will query

Ipv4 for the Ipv4RoutingProtocol object interface, and will request

a route via Ipv4RoutingProtocol::RouteOutput ().

A Ptr to Ipv4Route object is returned.  This is analagous to a

dst_cache entry in Linux.  The Ipv4Route is carried down to the

Ipv4L3Protocol to avoid a second lookup there.  However, some

cases (e.g. Ipv4 raw sockets) will require a call to RouteOutput()

directly from Ipv4L3Protocol.

For packets received inbound for forwarding or delivery, 

the following steps occur.  Ipv4L3Protocol::Receive() calls 

Ipv4RoutingProtocol::RouteInput().

This passes the packet ownership to the Ipv4RoutingProtocol object.  There

are four callbacks associated with this call:

@itemize @bullet

@item LocalDeliver 

@item UnicastForward

@item MulticastForward

@item Error

@end itemize  

The Ipv4RoutingProtocol must eventually call one of these callbacks for each

packet that it takes responsibility for.  This is basically

how the input routing process works in Linux.

@float Figure,fig:routing-specialization

@caption{Ipv4Routing specialization}

@image{figures/routing-specialization, 5in}

@end float

This overall architecture is designed to support different routing

approaches, including (in the future) a Linux-like policy-based routing

implementation, proactive and on-demand routing protocols, and simple

routing protocols for when the simulation user does not really care

about routing.

@ref{fig:routing-specialization} illustrates how multiple routing protocols

derive from this base class.  A class Ipv4ListRouting

(implementation class Ipv4ListRoutingImpl) provides the existing

list routing approach in ns-3.  Its API is the same as base class

Ipv4Routing except for the ability to add multiple prioritized routing

protocols 

(Ipv4ListRouting::AddRoutingProtocol(), Ipv4ListRouting::GetRoutingProtocol()).

The details of these routing protocols are described below in

@ref{Unicast routing}.  For now, we will first start with a basic

unicast routing capability that is intended to globally build routing

tables at simulation time t=0 for simulation users who do not care

about dynamic routing.

@node Global centralized routing

@section Global centralized routing

Global centralized routing is sometimes called ''God'' routing; it

is a special implementation that walks the simulation topology and

runs a shortest path algorithm, and populates each node's routing

tables.  No actual protocol overhead (on the simulated links) is incurred

with this approach.  It does have a few constraints:

@itemize @bullet

@item @strong{Wired only:}  It is not intended for use in wireless networks.

@item @strong{Unicast only:} It does not do multicast.

@item @strong{Scalability:}  Some users of this on large topologies 

(e.g. 1000 nodes) 

have noticed that the current implementation is not very scalable.  

The global centralized routing will be modified in the future to

reduce computations and runtime performance.

@end itemize

Presently, global centralized IPv4 unicast routing over both 

point-to-point and shared (CSMA) links is supported.

By default, when using the ns-3 helper API and the default InternetStackHelper,

global routing capability will be added  to the node, and global routing

will be inserted as a routing protocol with lower priority than the

static routes (i.e., users can insert routes via Ipv4StaticRouting API

and they will take precedence over routes found by global routing).

@subsection Global Unicast Routing API

The public API is very minimal.  User scripts include the following:

@verbatim

#include "ns3/helper-module.h"

@end verbatim

If the default InternetStackHelper is used, then an instance of

global routing will be aggregated to each node.

After IP addresses are configured, the following function call will

cause all of the nodes that have an Ipv4 interface to receive

forwarding tables entered automatically by the GlobalRouteManager:

@verbatim

  Ipv4GlobalRoutingHelper::PopulateRoutingTables ();

@end verbatim

@emph{Note:} A reminder that the wifi NetDevice will work but does not

take any wireless effects into account.  For wireless, we recommend

OLSR dynamic routing described below.

It is possible to call this function again in the midst of a simulation

using the following additional public function:

@verbatim

  Ipv4GlobalRoutingHelper::RecomputeRoutingTables ();

@end verbatim

which flushes the old tables, queries the nodes for new interface information,

and rebuilds the routes.

For instance, this scheduling call will cause the tables to be rebuilt

at time 5 seconds:

@verbatim

  Simulator::Schedule (Seconds (5),&Ipv4GlobalRoutingHelper::RecomputeRoutingTables);

@end verbatim

@subsection Global Routing Implementation

This section is for those readers who care about how this is implemented.

A singleton object (GlobalRouteManager) is responsible for populating

the static routes on each node, using the public Ipv4 API of that node.

It queries each node in the topology for a "globalRouter" interface.

If found, it uses the API of that interface to obtain a "link state

advertisement (LSA)" for the router.  Link State Advertisements

are used in OSPF routing, and we follow their formatting.

The GlobalRouteManager populates a link state database with LSAs

gathered from the entire topology.  Then, for each router in the topology,

the GlobalRouteManager executes the OSPF shortest path first (SPF)

computation on the database, and populates the routing tables on each

node.

The quagga (http://www.quagga.net) OSPF implementation was used as the

basis for the routing computation logic.

One benefit of following an existing OSPF SPF implementation is that

OSPF already has defined link state advertisements for all common

types of network links:

@itemize @bullet

@item point-to-point (serial links)

@item point-to-multipoint (Frame Relay, ad hoc wireless)

@item non-broadcast multiple access (ATM)

@item broadcast (Ethernet)

@end itemize

Therefore, we think that enabling these other link types will be more

straightforward now that the underlying OSPF SPF framework is in place.

Presently, we can handle IPv4 point-to-point, numbered links, as well

as shared broadcast (CSMA) links, and we do not do equal-cost multipath.  

The GlobalRouteManager first walks the list of nodes and aggregates

a GlobalRouter interface to each one as follows:

@verbatim

  typedef std::vector < Ptr<Node> >::iterator Iterator;

  for (Iterator i = NodeList::Begin (); i != NodeList::End (); i++)

    {

      Ptr<Node> node = *i;

      Ptr<GlobalRouter> globalRouter = CreateObject<GlobalRouter> (node);

      node->AggregateObject (globalRouter);

    }

@end verbatim

This interface is later queried and used to generate a Link State

Advertisement for each router, and this link state database is

fed into the OSPF shortest path computation logic.  The Ipv4 API

is finally used to populate the routes themselves. 

@node Unicast routing

@section Unicast routing

There are presently four routing protocols defined:

@itemize @bullet

@item class Ipv4StaticRouting (covering both unicast and multicast)

@item  Optimized Link State Routing (a MANET protocol defined in

@uref{http://www.ietf.org/rfc/rfc3626.txt,,RFC 3626})

@item class Ipv4ListRouting (used to store a prioritized list of routing

protocols)

@item class Ipv4GlobalRouting (used to store routes computed by the global

route manager, if that is used)

@end itemize

In the future, this architecture should also allow someone to implement

a Linux-like implementation with routing cache, or a Click modular

router, but those are out of scope for now.

@subsection Ipv4ListRouting

This section describes the current default ns-3 Ipv4RoutingProtocol.

Typically, multiple routing protocols are supported in user space and

coordinate to write a single forwarding table in the kernel.  Presently

in @command{ns-3}, the implementation instead allows for multiple routing 

protocols to build/keep their own routing state, and the IPv4 implementation

will query each one of these routing protocols (in some order determined

by the simulation author) until a route is found.  

We chose this approach because it may better

be difficult to coordinate the writing to a single table, approaches

where more information than destination IP address (e.g., source

routing) is used to determine the next hop, and on-demand

routing approaches where packets must be cached.  

@subsubsection Ipv4ListRouting::AddRoutingProtocol

Class Ipv4ListRouting provides a pure virtual function declaration for the

method that allows one to add a routing protocol:

@verbatim

  void AddRoutingProtocol (Ptr<Ipv4RoutingProtocol> routingProtocol,

                           int16_t priority);

@end verbatim

This method is implemented by class Ipv4ListRoutingImpl in the internet-stack

module.

The priority variable above governs the priority in which the routing

protocols are inserted.  Notice that it is a signed int.

By default in ns-3, the helper classes will instantiate a Ipv4ListRoutingImpl

object, and add to it an Ipv4StaticRoutingImpl object at priority zero. 

Internally, a list of Ipv4RoutingProtocols is stored, and

and the routing protocols are each consulted in decreasing order

of priority to see whether a match is found.  Therefore, if you

want your Ipv4RoutingProtocol to have priority lower than the static

routing, insert it with priority less than 0; e.g.:

@verbatim

  Ptr<MyRoutingProtocol> myRoutingProto = CreateObject<MyRoutingProtocol> ();

  listRoutingPtr->AddRoutingProtocol (myRoutingProto, -10);

@end verbatim

Upon calls to RouteOutput() or RouteInput(), the list routing object will 

search the list of routing protocols, in priority order, until a route 

is found.  Such routing protocol will invoke the appropriate callback

and no further routing protocols will be searched.  

@subsection Optimized Link State Routing (OLSR)

This is the first dynamic routing protocol for @command{ns-3}.  The implementation

is found in the src/routing/olsr directory, and an example script is in

examples/simple-point-to-point-olsr.cc.

The following commands will enable OLSR in a simulation.  

@verbatim

  olsr::EnableAllNodes ();  // Start OLSR on all nodes

  olsr::EnableNodes(InputIterator begin, InputIterator end); // Start on

    // a list of nodes

  olsr::EnableNode (Ptr<Node> node);  // Start OLSR on "node" only

@end verbatim

Once instantiated, the agent can be started with the Start() command,

and the OLSR "main interface" can be set with the SetMainInterface()

command.  A number of protocol constants are defined in olsr-agent-impl.cc.

@node Multicast routing

@section Multicast routing

The following function is used to add a static multicast route

to a node:

@verbatim

void 

Ipv4StaticRouting::AddMulticastRoute (Ipv4Address origin,

                          Ipv4Address group,

                          uint32_t inputInterface,

                          std::vector<uint32_t> outputInterfaces);

@end verbatim

A multicast route must specify an origin IP address, a multicast group and

an input network interface index as conditions and provide a vector of

output network interface indices over which packets matching the conditions

are sent.

Typically there are two main types of multicast routes:  routes of the 

first kind are used during forwarding.  All of the conditions must be

of a local node.  The difference is in the input interface.  Routes for

forwarding will always have an explicit input interface specified.  Routes

off of a node will always set the input interface to a wildcard specified

by the index Ipv4RoutingProtocol::IF\_INDEX\_ANY.

For routes off of a local node wildcards may be used in the origin and

multicast group addresses.  The wildcard used for Ipv4Adresses is that 

address returned by Ipv4Address::GetAny () -- typically "0.0.0.0".  Usage

of a wildcard allows one to specify default behavior to varying degrees.

For example, making the origin address a wildcard, but leaving the 

multicast group specific allows one (in the case of a node with multiple

interfaces) to create different routes using different output interfaces

for each multicast group.

If the origin and multicast addresses are made wildcards, you have created

essentially a default multicast address that can forward to multiple 

interfaces.  Compare this to the actual default multicast address that is

limited to specifying a single output interface for compatibility with

existing functionality in other systems.

Another command sets the default multicast route:

@verbatim

void 

Ipv4StaticRouting::SetDefaultMulticastRoute (uint32_t outputInterface);

@end verbatim

This is the multicast equivalent of the unicast version SetDefaultRoute.

We tell the routing system what to do in the case where a specific route

to a destination multicast group is not found.  The system forwards 

packets out the specified interface in the hope that "something out there"

knows better how to route the packet.  This method is only used in 

initially sending packets off of a host.  The default multicast route is

not consulted during forwarding -- exact routes must be specified using

AddMulticastRoute for that case.

Since we're basically sending packets to some entity we think may know

better what to do, we don't pay attention to "subtleties" like origin

address, nor do we worry about forwarding out multiple  interfaces.  If the

default multicast route is set, it is returned as the selected route from 

LookupStatic irrespective of origin or multicast group if another specific

route is not found.

Finally, a number of additional functions are provided to fetch and

remove multicast routes:

@verbatim

  uint32_t GetNMulticastRoutes (void) const;

  Ipv4MulticastRoute *GetMulticastRoute (uint32_t i) const;

  Ipv4MulticastRoute *GetDefaultMulticastRoute (void) const;

  bool RemoveMulticastRoute (Ipv4Address origin,

                             Ipv4Address group,

                             uint32_t inputInterface);

  void RemoveMulticastRoute (uint32_t index);

@end verbatim