--- a/doc/manual/routing.texi Fri May 29 06:40:34 2009 -0700
+++ b/doc/manual/routing.texi Sat May 30 10:38:27 2009 -0700
@@ -2,40 +2,213 @@
@chapter Routing overview
@menu
-* Routing-Overview::
-* Support for multiple routing protocols::
-* Roadmap and Future work::
-* Static routing::
+* Routing architecture::
+* Global centralized routing::
* Unicast routing::
* Multicast routing::
-* Global centralized routing::
-* Global Unicast Routing API::
-* Global Routing Implementation::
-* Optimized Link State Routing (OLSR)::
@end menu
-This chapter describes the overall design of routing in the
-@code{src/internet-stack}
-module, and some details about the routing approachs currently
-implemented.
+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.
-@node Routing-Overview
-@section Overview
+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.
+
+@subsection Global Unicast Routing API
-We intend to support traditional routing approaches and protocols,
-ports of open source routing implementations, and facilitate research
-into unorthodox routing techniques.
-For simulations that are not primarily focused on routing and that
-simply want correct routing tables to occur somehow, we have an
-global centralized routing capability. A singleton object
-(GlobalRouteManager) be instantiated, builds a network map, and
-populates a forwarding table on each node at time t=0 in the
-simulation. Simulation script writers can use the same node
-API to manually enter routes as well.
+The public API is very minimal. User scripts include the following:
+@verbatim
+#include "ns3/global-route-manager.h"
+@end verbatim
+
+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
+ GlobalRouteManager::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
+ GlobalRouteManager::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),&GlobalRouteManager::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.
-@node Support for multiple routing protocols
-@section Support for multiple routing protocols
+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
@@ -50,163 +223,54 @@
routing) is used to determine the next hop, and on-demand
routing approaches where packets must be cached.
-There are presently two 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})
-@end itemize
-but first we describe how multiple routing protocols are supported.
-
-@subsection class Ipv4RoutingProtocol
-
-@code{class Ipv4RoutingProtocol} derives from ns-3 Object which means
-that it supports interface aggregation and reference counting. Routing
-protocols should inherit from this class, defined in src/node/ipv4.cc.
+@subsubsection Ipv4ListRouting::AddRoutingProtocol
-The main function that must be supported by these protocols is called
-@code{RequestRoute}.
-@verbatim
- * This method is called whenever a node's IPv4 forwarding engine
- * needs to lookup a route for a given packet and IP header.
- *
- * The routing protocol implementation may determine immediately it
- * should not be handling this particular the route request. For
- * instance, a routing protocol may decline to search for routes for
- * certain classes of addresses, like link-local. In this case,
- * RequestRoute() should return false and the routeReply callback
- * must not be invoked.
- *
- * If the routing protocol implementations assumes it can provide
- * the requested route, then it should return true, and the
- * routeReply callback must be invoked, either immediately before
- * returning true (synchronously), or in the future (asynchronous).
- * The routing protocol may use any information available in the IP
- * header and packet as routing key, although most routing protocols
- * use only the destination address (as given by
- * ipHeader.GetDestination ()). The routing protocol is also
- * allowed to add a new header to the packet, which will appear
- * immediately after the IP header, although most routing do not
- * insert any extra header.
- */
- virtual bool RequestRoute (uint32_t interface,
- const Ipv4Header &ipHeader,
- Ptr<Packet> packet,
- RouteReplyCallback routeReply) = 0;
-@end verbatim
-
-This class also provides a typedef (used above) for a special Callback
-that will pass to the callback function the Ipv4Route that is found (see the
-Doxygen documentation):
-@verbatim
- typedef Callback<void, bool, const Ipv4Route&, Ptr<Packet>, const Ipv4Header&> RouteReplyCallback;
-@end verbatim
-
-@subsection Ipv4::AddRoutingProtocol
-
-Class Ipv4 provides a pure virtual function declaration for the
+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 Ipv4L3Protocol in the internet-stack
+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.
-When the class Ipv4L3Protocol is instantiated, a single routing
-protocol (Ipv4StaticRouting, introduced below) is added at priority
-zero. Internally, a list of Ipv4RoutingProtocols is stored, and
+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
- m_ipv4->AddRoutingProtocol (m_routingTable, -10);
-@end verbatim
-
-@subsection Ipv4L3Protocol::Lookup
-
-The main function for obtaining a route is shown below:
-@verbatim
-Ipv4L3Protocol::Lookup (
- uint32_t interface,
- Ipv4Header const &ipHeader,
- Ptr<Packet> packet,
- Ipv4RoutingProtocol::RouteReplyCallback routeReply)
-@end verbatim
-
-This function will search the list of routing protocols, in priority order,
-until a route is found. It will then invoke the RouteReplyCallback
-and no further routing protocols will be searched. If the caller does
-not want to constrain the possible interface, it can be wildcarded
-as such:
-@verbatim
- Lookup (Ipv4RoutingProtocol::IF_INDEX_ANY, ipHeader, packet, routeReply);
+ Ptr<MyRoutingProtocol> myRoutingProto = CreateObject<MyRoutingProtocol> ();
+ listRoutingPtr->AddRoutingProtocol (myRoutingProto, -10);
@end verbatim
-@node Roadmap and Future work
-@section Roadmap and Future work
+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)
-Some goals for future support are:
+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.
-Users should be able to trace (either debug print, or redirect to a trace
-file) the routing table in a format such as used in an
-Unix implementation:
+The following commands will enable OLSR in a simulation.
+
@verbatim
-# netstat -nr (or # route -n)
-Kernel IP routing table
-Destination Gateway Genmask Flags MSS Window irtt Iface
-127.0.0.1 * 255.255.255.255 UH 0 0 0 lo
-172.16.1.0 * 255.255.255.0 U 0 0 0 eth0
-172.16.2.0 172.16.1.1 255.255.255.0 UG 0 0 0 eth0
-
-# ip route show
-192.168.99.0/24 dev eth0 scope link
-127.0.0.0/8 dev lo scope link
-default via 192.168.99.254 dev eth0
+ 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
-Global computation of multicast routing should be implemented as well.
-This would ignore group membership and ensure that a copy of every
-sourced multicast datagram would be delivered to each node.
-This might be implemented as an RPF mechanism that functioned on-demand
-by querying the forwarding table,
-and perhaps optimized by a small multicast forwarding cache. It is
-a bit trickier to implement over wireless links where the input
-interface is the same as the output interface; other aspects of the
-packet must be considered and the forwarding logic slightly changed
-to allow for forwarding out the same interface.
-
-In the future, work on bringing XORP or quagga routing to ns, but it will
-take several months to port and enable.
-
-There are presently no roadmap plans for IPv6.
-
-@node Static routing
-@section Static routing
-
-The internet-stack module provides one routing protocol (Ipv4StaticRouting)
-by default. This routing protocol allows one to add unicast or multicast
-static routes to a node.
-
-@node Unicast routing
-@section Unicast routing
-
-The unicast static routing API may be accessed via the functions
-@verbatim
-void Ipv4::AddHostRouteTo ()
-void Ipv4::AddNetworkRouteTo ()
-void Ipv4::SetDefaultRoute ()
-uint32_t Ipv4::GetNRoutes ()
-Ipv4Route Ipv4::GetRoute ()
-@end verbatim
-
-@uref{http://www.nsnam.org/doxygen/index.html,,Doxygen} documentation
-provides full documentation of these methods. These methods are forwarding
-functions to the actual implementation in Ipv4StaticRouting, when using
-the internet-stack module.
+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
@@ -288,113 +352,4 @@
void RemoveMulticastRoute (uint32_t index);
@end verbatim
-@node Global centralized routing
-@section Global centralized routing
-Presently, global centralized IPv4 @emph{unicast} routing over both
-point-to-point and shared (CSMA) links is supported.
-The global centralized routing will be modified in the future to
-reduce computations once profiling finds the performance bottlenecks.
-
-@node Global Unicast Routing API
-@section Global Unicast Routing API
-
-The public API is very minimal. User scripts include the following:
-@verbatim
-#include "ns3/global-route-manager.h"
-@end verbatim
-
-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
- GlobalRouteManager::PopulateRoutingTables ();
-@end verbatim
-
-@emph{Note:} A reminder that the wifi NetDevice is not yet supported
-(only CSMA and PointToPoint).
-
-It is possible to call this function again in the midst of a simulation
-using the following additional public function:
-@verbatim
- GlobalRouteManager::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),&GlobalRouteManager::RecomputeRoutingTables);
-@end verbatim
-
-@node Global Routing Implementation
-@section Global Routing Implementation
-
-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 Optimized Link State Routing (OLSR)
-@section 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.
-