unicast.tex

柯老师网站上找到的

\chapter{Unicast Routing}
\label{chap:unicast}

This section describes the structure of unicast routing in \ns.
We begin by describing
\href{the interface to the user}{Section}{sec:API},
through methods in the \clsref{Simulator}{../ns-2/ns-lib.tcl}
and the \clsref{RouteLogic}{../ns-2/ns-lib.tcl}.
We then describe
\href{configuration mechanisms for specialised routing}{%
        Section}{sec:uni:specroute}
such as asymmetric routing, or equal cost multipath routing
The next section describes the
\href{the configuration mechanisms for individual routing strategies
and protocols}{Section}{sec:uni:protconfig}.
We conclude with a comprehensive look at 
\href{the internal architecture}{Section}{sec:rtg-internals}
of routing in \ns.

The procedures and functions described in this chapter can be found in
\nsf{tcl/lib/ns-route.tcl}, \nsf{tcl/rtglib/route-proto.tcl}, 
\nsf{tcl/mcast/McastProto.tcl}, and \nsf{rtProtoDV.\{cc, h\}}.

\section{The Interface to the Simulation Operator (The API)}
\label{sec:API}

The user level simulation script requires one command:
to specify the unicast routing strategy or protocols for the simulation.
A routing strategy is a general mechanism by which \ns\
will compute routes for the simulation.
There are three routing strategies in \ns:
Static, Session, and Dynamic.
Conversely, a routing protocol is a realisation of a specific algorithm.
Currently, Static and Session routing use
the
\fcnref{Dijkstra's all-pairs SPF algorithm \cite{}}{../ns-2/route.cc}{%
        RouteLogic::compute\_routes};
one type of dynamic routing strategy is currently implemented: the
\fcnref{Distributed Bellman-Ford algorithm \cite{}}{../ns-2/route-proto.tcl}{%
        Agent/rtProto/DV::compute\_routes}.
In \ns, we blur the distinction between strategy and protocol for
static and session routing, considering them simply as protocols%
\footnote{The consideration is that static and session routing
  strategies/protocols are implemented as agents derived from
  the \clsref{Agent/rtProto},
  similar to how the different dynamic routing protocols are implemented;
  hence the blurred distinctions.}.

\fcnref{\proc[]{rtproto}}{../ns-2/route-proto.tcl}{Simulator::rtproto}
is the instance procedure in the \clsref{Simulator}{../ns-2/ns-lib.tcl}
that specifies the unicast routing protocol to be used in the simulation.
It takes multiple arguments, the first of which is mandatory;
this first argument identifies the routing protocol to be used.
Subsequent arguments specify the nodes
that will run the instance of this protocol.
The default is to run the same routing protocol
on all the nodes in the topology.
As an example, the following commands illustrate the use of the
\proc[]{rtproto} command.
\begin{program}
        $ns rtproto Static            \; Enable static route strategy for the simulation;
        $ns rtproto Session           \; Enable session routing for this simulation;
        $ns rtproto DV $n1 $n2 $n3    \; Run DV agents on nodes $n1, $n2, and $n3;
\end{program}
If a simulation script does not specify any \proc[]{rtproto} command,
then \ns\ will run Static routing on all the nodes in the topology.

Multiple \proc[]{rtproto} lines for the same or different routing 
protocols can occur in a simulation script.
However, a simulation cannot use both
centralised routing mechanisms such as static or session routing and 
detailed dynamic routing protocols such as DV.

In dynamic routing, each node can be running more than one routing protocol.
In such situations, more than one routing protocol can have a route to the
same destination.
Therefore, each protocol affixes a preference value to each of its routes.
These values are non-negative integers in the range 0\ldots255.
The lower the value, the more preferred the route.
When multiple routing protocol agents have a route to the same destination,
the most preferred route is chosen and
installed in the node's forwarding tables.
If more than one agent has the most preferred routes,
the ones with the lowest metric is chosen.
We call the least cost route from the most preferred protocol the
``candidate'' route.
If there are multiple candidate routes from the same or different protocols,
then, currently,
one of the agent's routes is randomly chosen\footnote{%
This really is undesirable, and may be fixed at some point.
The fix will probably be to favor the agents in class preference order.
A user level simulation relying on this behavior,
or getting into this situation in specific topologies is
not recommended.}.

\paragraph{Preference Assignment and Control}
Each protocol agent stores an array of route preferences, \code{rtpref_}.
There is one element per destination, indexed by the node handle.
The default preference values used by each protocol are derived from
a class variable, \code{preference_}, for that protocol.
The current defaults are:
\begin{program}
        Agent/rtProto set preference_ 200               \; global default preference;
        Agent/rtProto/Direct\footnote{Direct is a special routing strategy that is used in conjunction with Dynamic routing.  We will describe this in greater detail as part of the route architecture description.} set preference_ 100
        Agent/rtProto/DV set preference_ 120
\end{program}
A simulation script can control routing by altering the preference
for routes in one of three ways:
alter the preference 
for a specific route learned \via\ a particular protocol agent,
alter the preference for all routes learned by the agent, or
alter the class variables for the agent before the agent is created.

\paragraph{Link Cost Assignment and Control}
In the currently implemented route protocols,
the metric of a route to a destination, at a node,
is the cost to reach the destination from that node.
It is possible to change the link costs at each of the links.
The instance procedure
\fcnref{\proc[]{cost}}{../ns-2/route-proto.tcl}{Simulator::cost}
%XXX MOVE TO NS-LIB.TCL
is invoked as \code{$ns cost \tup{node1} \tup{node2} \tup{cost}},
and sets the cost of the link from \tup{node1} to \tup{node2}
to \tup{cost}.
\begin{program}
        $ns cost $n1 $n2 10        \; set cost of link \textbf{from} $n1 \textbf{to} $n2 to 10;
        $ns cost $n2 $n1  5        \; set cost of link in reverse direction to 5;
        [$ns link $n1 $n2] cost?   \; query cost of link from $n1 to $n2;
        [$ns link $n2 $n1] cost?   \; query cost of link in reverse direction;
\end{program}
Notice that the procedure sets the cost along one direction only.
Similarly, the procedure
\fcnref{\proc[]{cost?}}{../ns-2/route-proto.tcl}{Link::cost?}
returns the cost of traversing the specified unidirectional link.
The default cost of a link is 1.

\section{Other Configuration Mechanisms for Specialised Routing}
\label{sec:uni:specroute}

It is possible to adjust preference and cost mechanisms to get two
special types of route configurations: 
asymmetric routing, and multipath routing.

\paragraph{Asymetric Routing}
Asymetric routing occurs when the path from node $n_1$ to node $n_2$
is different from the path from $n_2$ to $n_1$.
The following shows a simple topology, and cost configuration
that can achieve such a result:

\hfil
\begin{minipage}{1.85in}
Nodes $n_1$ and $n_2$ use different paths to reach each other.
All other pairs of nodes use symmetric paths to reach each other.
\end{minipage}
\hfil
\begin{minipage}{1.in}
  \begin{pspicture}(-1,-1)(1,1)
    \cnodeput( 0, 1){r1}{$r_1$}
    \cnodeput( 0,-1){r2}{$r_2$}
    \cnodeput( 1, 0){n2}{$n_2$}
    \cnodeput(-1, 0){n1}{$n_1$}
    \ncline{n1}{r1}\ncline{r1}{n2}\ncline{n2}{r2}\ncline{r2}{n1}
  \end{pspicture}
\end{minipage}
\hfil
\begin{minipage}{1.85in}
  \begin{program}
    $ns cost $n1 $r1 2
    $ns cost $n2 $r2 2
    $ns cost $r1 $n2 3
  \end{program}
\end{minipage}
\hfil

Any routing protocol that uses link costs as the metric can observe
such asymmetric routing if the link costs are appropriately configured%
\footnote{Link costs can also be used to favour or disregard
specific links in order to achieve particular topology configurations.}.

\paragraph{MultiPath Routing}
Each node can be individually configured
to use multiple separate paths to a particular destination.
The instance variable \code{multiPath_} determines whether or not
that node will use multiple paths to any destination.
Each node initialises its instance variable from a class variable
of the same name.
If multiple candidate routes to a destination are available,
all of which are learned through the same protocol,
then that node can use
all of the different routes to the destination simultaneously.
A typical configuration is as shown below:
\begin{program}
        Node set multiPath_ 1 \; All new nodes in the simulation use multiPaths where applicable;
{\rm or alternately}
        set n1 [$ns Node] \; only enable $n1 to use multiPaths where applicable;
        $n1 set multiPath_ 1
\end{program}
Currently, only DV routing can generate multipath routes.

\section{Protocol Specific Configuration Parameters}
\label{sec:uni:protconfig}

\paragraph{Static Routing}
The static route computation strategy is
the default route computation mechanism  in \ns.
This strategy uses the
\fcnref{Dijkstra's all-pairs SPF algorithm \cite{}}{../ns-2/route.cc}{%
        RouteLogic::compute\_routes}.
The route computation algorithm is run exactly once
prior to the start of the simulation.
The routes are computed
using an adjacency matrix and link costs of all the links in the topology.

\paragraph{Session Routing}
The static routing strategy described earlier
only computes routes for the topology once in the course of a simulation.
If the above static routing is used and the topology changes while the
simulation is in progress, some sources and destinations may become
temporarily unreachable from each other for a short time.

Session routing strategy is almost identical to static routing,
in that it runs the Dijkstra all-pairs SPF algorithm
prior to the start of the simulation, using the
adjacency matrix and link costs of the links in the topology.
However, it will also run the same algorithm to recompute routes
in the event that the topology changes during the course of a
simulation. 
In other words, route recomputation and recovery is done
instantaneously and there will not be transient routing outage as in
static routing. 

Session routing provides complete and instantaneous routing changes 
in the presence of topology dynamics.
If the topology is always connected, there is
end-to-end connectivity at all times during the course of the simulation.
However, the user should note that the instantaneous route recomputation 
of session routing does not prevent temporary violations of causality,
such as packet reordering, around the instant that the topology
changes. 

\paragraph{DV Routing}
DV routing is the implementation of
Distributed Bellman-Ford (or Distance Vector) routing in \ns.
The implementation sends periodic route updates every \code{advertInterval}.
This variable is a class variable in the \clsref{Agent/rtProto/DV}{../ns-2/tcl/rtglib/route-proto.tcl}.
Its default value is 2 seconds.

In addition to periodic updates, each agent also sends triggered updates;
it does this whenever the forwarding tables in the node change.
This occurs either due to changes in the topology, 
or because an agent at the node received a route update,
and recomputed and installed new routes.

Each agent employs the split horizon with poisoned reverse mechanisms
to advertise its routes to adjacent peers.
``Split horizon'' is the mechanism by which an agent will not advertise
the route to a destination out of the interface that it is using to
reach that destination.
In a ``Split horizon with poisoned reverse'' mechanism,
the agent will advertise that route out of that interface with 
a metric of infinity.

Each DV agent uses a default \code{preference_} of 120.
The value is determined by the class variable of the same name.

Each agent uses the class variable \code{INFINITY} (set at 32)
to determine the validity of a route.

\section{Internals and Architecture of Routing}
\label{sec:rtg-internals}

We start with a discussion of the classes associated with
unicast routing, and the code path used to configure and execute
each of the different routing protocols.
We conclude with a description of
the interface between unicast routing and network dynamics, and
that between unicast and multicast routing.

\subsection{The classes}
There are four main classes,
the class RouteLogic, the class rtObject, the class rtPeer, and the
base class Agent/rtProto for all protocols.
In addition, the routing architecture extends 
the classes Simulator, Link, Node and Classifier.

\paragraph{\protect\clsref{RouteLogic}{../ns-2/route-proto.tcl}}
This class defines two methods to configure unicast routing,
and one method to query it for route information.
It also defines an instance procedure that is applicable when
the topology is dynamic.
We discuss this last procedure in conjunction
with the interface to network dynamics.
\begin{itemize}
\item The instance procedure
\fcnref{\proc[]{register}}{../ns-2/route-proto.tcl}{RouteLogic::register}
is invoked by \proc[]{Simulator::rtproto}.
It takes the protocol and a list of nodes as arguments,
and constructs an instance variable, \code{rtprotos_}, as an array;
the array index is the name of the protocol, and the value is the list
of nodes that will run this protocol.
\item The
\fcnref{\proc[]{configure}}{../ns-2/route-proto.tcl}{RouteLogic::configure}
reads the \code{rtprotos_} instance variable, and 
for each element in the array, 
invokes route protocol methods to perform the appropriate initializations.
It is invoked by
\fcnref{the simulator run procedure}{../ns-2/ns-lib.tcl}{Simulator::run}.

For each protocol \tup{rt-proto} indexed in the \code{rtprotos_} array,
this routine invokes
\code{Agent/rtProto/\tup{rt-proto} init-all rtprotos_(\tup{rt-proto})}.

If there are no elements in \code{rtprotos_},
the routine invokes Static routing, as
\code{Agent/rtProto/Static init-all}.