%
% $XORP: xorp/docs/olsr/olsr.tex,v 1.1 2008/04/24 15:20:09 bms Exp $
% 

\chapter{OLSR}
\label{olsr}
\section{OLSR Terminology and Concepts}

OLSR is the Optimized Link State Routing protocol. It is part of a new
generation of routing protocols which are responsible for connectivity
in diverse, dynamic network topologies, typically wireless and mobile in
nature. It is a link-state protocol with superficial similarities to OSPF.

The first version of OLSR was specified in RFC 3626, and was specified
for both IPv4 and IPv6. A popular enhancement for OLSRv1 is the use of
Expected Transmission Count (ETX) as a metric.

ETX requires the use of alternative HELLO and TC messages in the OLSRv1
protocol. No Internet-Draft exists for this extension, however, a very
informal description may be found at:
\linebreak
{\stt http://www.olsr.org/docs/README-Link-Quality.html}.

XORP's implementation of OLSR supports the RFC 3626 compliant protocol,
for IPv4 only. It does not yet support the ETX link metrics, or IPv6.
These will be be supported in the next revision. Currently only unicast
routing is supported. Multicast support is planned for a future release.

For consistency with our other protocols, OLSRv1 for IPv4 is {\tt olsr4}
in the router configuration.


\subsection{Key OLSR Concepts}

OLSR is part of the IETF's Mobile Ad-hoc Network (MANET) family of
experimental protocols. It is not yet considered standards track.

As deployed, OLSR makes extensive use of IPv4 broadcast. This can lead
to subtle issues with the host platform's IPv4 stack, which the XORP FEA
will attempt to work around.

OLSR runs within a single routing domain. There is no concept of
segmentation within the domain, as exists in OSPF with its
concept of areas. This limitation may be addressed in OLSRv2.

The concept of statically configured peerings does not exist in OLSR;
adjacencies are established dynamically using HELLO messages. Most
of the OLSR protocol concerns the population of the neighborhood
link state database for nodes up to 2 hops away.

The protocol is based on flooding. This may be optimized using a
technique known as Multi-Point Relays ({\tt MPR}).
The {\tt MPR} algorithm attempts to reduce the amount of redundant flooding
of state that would otherwise occur in such a network, by selecting
nodes in the local neighborhood which have the highest degree and
coverage based on the learned topology information, and flooding
only to these nodes where possible.
The {\tt MPR} algorithm described in RFC 3626 is specified to run for each
configured OLSR interface. Currently XORP's OLSR implementation
supports a modified version which runs for all configured interfaces.

OLSR uniquely identifies each node in the topology using its ``main address''.
Nodes with multiple interfaces configured for OLSR must announce this state
to all other nodes, by periodically flooding Multiple Interface Declaration
(MID) messages.

Link state about nodes further than the local neighborhood is periodically
flooded to all other nodes using Topology Control (TC) messages.
A popular optimization for the flooding of TC messages is known as
``fish-eye'' and will be supported in the next revision.

The OLSR protocol has explicit support for redistributing routes from
other protocols, using the Host and Network Association (HNA) message.
As specified in RFC 3626, however, this support is very limited.

Only the redistributed network prefix may be announced in an HNA
message; there is no support for explicit preference or metrics in such
routes; and the node which makes the announcement is always considered the
last hop in the OLSR topology for the external route. XORP's implementation
of OLSR fully integrates with XORP's existing policy routing capabilities.

OLSR does not have a strong concept of difference in functionality
between nodes; they are generally considered the same. Each OLSR node may
declare its willingness to forward traffic. This variable affects MPR
selection and forwarding decisions by other nodes in the OLSR domain.

\section{Standards}

XORP OLSR complies with the following standards:
\begin{description}
\item{\bf RFC 3626}: Optimized Link State Routing Protocol (Experimental)
\end{description}

\newpage
\section{Configuring OLSR}

\subsection{Configuration Syntax}

The configuration syntax for XORP OLSRv1 is given below.

\vspace{0.1in}
\noindent\framebox[\textwidth][l]{\scriptsize
\begin{minipage}{6in}
\begin{alltt}
\begin{tabbing}
xx\=xx\=xx\=xx\=xx\=xx\=xx\=xx\=xx\=xx\=xx\=xx\=\kill
protocols \{\\
\>olsr4 \{\\
\>\>targetname: {\it text}\\
\>\>main-address: {\it IPv4}\\
\\
\>\>willingness: {\it uint(0..7)}\\
\>\>mpr-coverage: {\it uint(1..32)}\\
\\
\>\>hello-interval: {\it uint(1..128)}\\
\>\>refresh-interval: {\it uint(1..128)}\\
\>\>mid-interval: {\it uint(1..128)}\\
\\
\>\>dup-hold-time: {\it uint(1..128)}\\
\\
\>\>interface {\it text} \{\\
\>\>\>vif {\it text} \{\\
\>\>\>\>address {\it IPv4} \{\\
\>\>\>\>\>local-port: {\it uint(1..65535)}\\
\\
\>\>\>\>\>all-nodes-address: {\it IPv4}\\
\>\>\>\>\>all-nodes-port: {\it uint(1..65535)}\\
\\
\>\>\>\>\>interface-cost: {\it uint(1..65535)}\\
\\
\>\>\>\>\>disable: {\it bool}\\
\>\>\>\>\}\\
\>\>\>\}\\
\>\>\}\\
\\
{\rm continued overleaf....}
\end{tabbing}
\end{alltt}
\end{minipage}
}
\vspace{0.1in}

\newpage
\vspace{0.1in}
\noindent\framebox[\textwidth][l]{\scriptsize
\begin{minipage}{6in}
\begin{alltt}
\begin{tabbing}
xx\=xx\=xx\=xx\=xx\=xx\=xx\=xx\=xx\=xx\=xx\=xx\=\kill
\\
\>\>topology \{\\
\>\>\>interval: {\it uint(1..128)}\\
\>\>\>redundancy: {\it text}\\
\>\>\}\\
\\
\>\>external \{\\
\>\>\>interval: {\it uint(1..128)}\\
\>\>\}\\
\\
\>\>traceoptions \{\\
\>\>\>flag \{\\
\>\>\>\>all \{\\
\>\>\>\>\>disable: {\it bool}\\
\>\>\>\>\}\\
\>\>\>\}\\
\>\>\}\\
\\
\>\>import: {\it text}\\
\>\>export: {\it text}\\
\>\}\\
\}
\end{tabbing}
\end{alltt}
\end{minipage}
}
\vspace{0.1in}

\noindent
The OLSRv1 configuration has the following limitations:
\begin{itemize}
\item OLSR supports a single address per interface/vif. All parameters
  are set below the address node.
\item OLSR does not support authentication at this time.
\end{itemize}

The configuration parameters are used as follows:
\begin{description}
\item{\tt protocols}: This delimits the configuration for all routing
  protocols in the XORP router configuration.  It is mandatory that
  OLSR configuration is under the {\stt protocols} node in the
  configuration.
\item{\tt olsr4}: This delimits the OLSR configuration part of the XORP
  router configuration.
\item{\tt targetname}: This is the name for this instance of OLSR.  It
  defaults to ``{\stt olsr4}'', and it is not recommended that this
  default is overridden under normal usage scenarios.
\item{\tt main-address}: This is a unique IPv4 address within the
MANET. The smallest IP address of an interface belonging
to the router is a good choice. The required format of the {\stt
main-address} is a dotted-decimal IPv4 address.
\item{\tt willingness}: This is how willing the node is to forward
traffic for other nodes. A value of 0 means the node is not willing
to forward traffic.
\item{\tt mpr-coverage}: This is how many one-hop neighbors the MPR
selection algorithm should attempt to select in order to reach the
node's two-hop neighbors when flooding control packets.
\item{\tt hello-interval}: This is the time in seconds between sending
HELLO messages.
\item{\tt refresh-interval}: This is the time in seconds for which
received HELLO information is expected to be valid.
\item{\tt mid-interval}: This is the time in seconds between sending
MID messages.
\item{\tt dup-hold-time}: This is the time in seconds for which
a previously flooded message is recorded as a duplicate.

\item{\tt interface}: This specifies a network interface that should
  be used by OLSR for routing.  See Chapter \ref{interfaces} in
  the User Manual for details of interfaces.  The interface must be configured
  in the {\stt interfaces} part of the router configuration.
\begin{description}
\item{\tt vif}: This specifies a vif that should be used by OLSR for routing.
  See Chapter \ref{interfaces} in the User Manual for details of vifs.
\begin{description}
\item{\tt address}: This specifies an IPv4 address that should be used
  by OLSR for routing.  OLSR will attempt to form links with other nodes
  on this {\stt interface/vif} using this {\stt address}.  The address must be a
  valid configured address for this vif.
  Only a single IPv4 address may be specified for each interface/vif.
\begin{description}
\item{\tt local-port}:  The port upon which OLSR listens for control traffic.
\item{\tt all-nodes-address}:  The address where OLSR sends its
  control traffic.
  At this time this must either be the IPv4 directed broadcast address
  configured for this {\stt interface/vif} and {\stt address}, or the undirected
  broadcast address {\stt 255.255.255.255}.
\item{\tt all-nodes-port}:  The port where OLSR sends its control traffic.
\item{\tt interface-cost}: The cost for this address that is used to
calculate routes using the Shortest Path Tree.
\item{\tt disable}:  This takes the value {\stt true} or {\stt
false}. The default setting is {\stt false} it can be set to {\stt
true} to disable OLSR on this {\stt address} without removing all the configuration.
\end{description}
\end{description}
\end{description}

\item{\tt topology}: This specifies options for Topology Control (TC)
  messages.
\begin{description}
\item{\tt interval}: This is the time in seconds between flooding
  TC messages to the rest of the network.
\item{\tt redundancy}: This selects the amount of topology information
  that will be sent in each TC message: {\stt mprs},
  {\stt mprs-and-selectors} or {\stt all}.
  As this is a text value, it must be delimited by double quotes.
\end{description}

\item{\tt external}: This specifies options for Host and Network
  Assocation (HNA) messages.
\begin{description}
\item{\tt interval}: This is the time in seconds between sending
  HNA messages.
\end{description}

\item{\tt traceoptions}: This directive if present will enable all tracing.

\end{description}

\subsection{Example Configurations}

\vspace{0.1in}
\noindent\framebox[\textwidth][l]{\scriptsize
\begin{minipage}{6in}
\begin{alltt}
\begin{tabbing}
xx\=xx\=xx\=xx\=xx\=\kill
protocols \{\\
\>olsr4 \{\\
\>\>main-address: 192.0.2.1\\
\\
\>\>interface eth0 \{\\
\>\>\>vif eth0 \{\\
\>\>\>\>address 192.0.2.1 \{\\
\>\>\>\>\}\\
\>\>\>\}\\
\>\>\}\\
\>\}\\
\}\\
\\
\end{tabbing}
\end{alltt}
\end{minipage}
}

This configuration is an example of the minimal possible
configuration. OLSR is running on a single interface/vif;
the {\tt main-address} is set to the interface/vif address.

\newpage
\section{Clearing OLSR database}

It may be necessary to drop all links and clear the OLSR
database. After the clear command is run, all links, neighbors,
two-hop neighbors, topology entries, and learned HNA routes will have been
removed. Interface bindings and routes exported into HNA will not be removed.

\vspace{0.1in}
\noindent\framebox[\textwidth][l]{\scriptsize
\begin{minipage}{6in}
\begin{alltt}
\begin{tabbing}
xx\=xxxxxxxxxxxxxxxxxxxxx\=\kill
user@hostname> \textbf{clear olsr4 database}\\
\end{tabbing}
\end{alltt}
\end{minipage}
}

\newpage
\section{Monitoring OLSR}

On a router running OLSR, the OLSR routing state can be displayed
using the {\stt show olsr4} family of operational-mode commands.

As always, command completion using $<$TAB$>$ or ? will display the
available sub-commands and parameters:

\vspace{0.1in}
\noindent\framebox[\textwidth][l]{\scriptsize
\begin{minipage}{6in}
\begin{alltt}
\begin{tabbing}
xx\=xxxxxxxxxxxxxxxxxxxxx\=\kill
user@hostname> \textbf{show olsr4 ?}\\
Possible completions:\\
\>external\>Show OLSRv1 external routes\\
\>interface\>Show OLSRv1 interface status\\
\>link\>Show OLSRv1 link status\\
\>mid\>Show OLSRv1 Multiple Interface database\\
\>neighbor\>Show OLSRv1 one-hop neighbor status\\
\>topology\>Show OLSRv1 Topology Control database\\
\>twohop-link\>Show OLSRv1 two-hop link status\\
\>twohop-neighbor\>Show OLSRv1 two-hop neighbor status\\
\end{tabbing}
\end{alltt}
\end{minipage}
}

The {\stt show olsr4 external} command will display information about the
routes which have been learned from the HNA sub-protocol.

\vspace{0.1in}
\noindent\framebox[\textwidth][l]{\scriptsize
\begin{minipage}{6in}
\begin{alltt}
\begin{tabbing}
user@hostname> \textbf{show olsr4 external}\\
\=xxxxxxxxxxxxxxxxxxx\=xxxxxxxxxxxxxxxx\=xxxxxxxxxx\=xxxxxx\=\kill
\>Destination\>Lasthop\>Distance\>Hold\\
\>192.0.1.0/24\>192.0.2.6\>1\>78\\
\end{tabbing}
\end{alltt}
\end{minipage}
}

The {\stt show olsr4 interface} command will show information about the
current OLSR interface bindings:

\vspace{0.1in}
\noindent\framebox[\textwidth][l]{\scriptsize
\begin{minipage}{6in}
\begin{alltt}
\begin{tabbing}
user@hostname> \textbf{show olsr4 interface}\\
\=xxxxxxxxxxx\=xxxxxxxxxxxxxxxxxxxxx\=xxxxxxxxxxxxxxxxxxxxx\=\kill
\>Interface\>LocalAddr\>AllNodesAddr\\
\>eth1/eth1\>192.0.2.17:698\>192.0.2.255:698\\
\end{tabbing}
\end{alltt}
\end{minipage}
}

The {\stt show olsr4 link} command will show information about the
links in the one-hop neighborhood, including the link state timers.

\vspace{0.1in}
\noindent\framebox[\textwidth][l]{\scriptsize
\begin{minipage}{6in}
\begin{alltt}
\begin{tabbing}
user@hostname> \textbf{show olsr4 link}\\
\=xxxxxxxxxxxxxxx\=xxxxxxxxxxxxxxx\=xxxxxxxxxxxxxxx\=xxxxx\=xxxxxx\=xxxxxx\=xxxxxx\=\kill
\>LocalAddr\>RemoteAddr\>Neighbor\>Type\>ASYM\>SYM\>Hold\\
\>192.0.2.17\>192.0.2.6\>192.0.2.6\>2\>86\>86\>86\\
\>192.0.2.17\>192.0.2.18\>192.0.2.18\>2\>5\>5\>5\\
\end{tabbing}
\end{alltt}
\end{minipage}
}

The {\stt show olsr4 mid} command will show information about nodes with
additional interfaces which have been learned from the MID sub-protocol.

\vspace{0.1in}
\noindent\framebox[\textwidth][l]{\scriptsize
\begin{minipage}{6in}
\begin{alltt}
\begin{tabbing}
user@hostname> \textbf{show olsr4 mid}\\
\=xxxxxxxxxxxxxxxx\=xxxxxxxxxxxxxxxxxxxx\=xxxxxxxxx\=xxxxxxxxxxxxxxxx\=xxxx\=\kill
\>MainAddr\>RemoteAddr\>Distance\>Hold\\
\>192.0.2.18\>192.0.1.18\>1\>10\\
\end{tabbing}
\end{alltt}
\end{minipage}
}

\newpage
The {\stt show olsr4 neighbor} command will show the known one-hop neighbors
in the local neighborhood. In particular the willingness-to-forward, degree,
number of links to the neighbor, and its two-hop links are shown.

The ADV flag indicates that this neighbor will appear in Topology Control (TC)
messages originated by this node, according to the current TC redundancy setting.

The SYM flag indicates that the adjacency formed with this neighbor is symmetric.

The MPR flag indicates that this neighbor has been selected as a Multi-Point Relay.

The MPRS flag indicates that this neighbor selects this XORP router as a Multi-Point Relay.

\vspace{0.1in}
\noindent\framebox[\textwidth][l]{\scriptsize
\begin{minipage}{6in}
\begin{alltt}
\begin{tabbing}
user@hostname> \textbf{show olsr4 neighbor}\\
\=xxxxxxxxxxxxxxx\=xxxxxx\=xxxxxxxx\=xxxxxxx\=xxxxxxx\=xxxx\=xxxx\=xxxx\=xxxx\=xxxx\=\kill
\>MainAddr\>Will\>Degree\>Links\>2links\>ADV\>SYM\>MPR\>MPRS\\
\>192.0.2.6\>4\>0\>1\>1\>*\>*\> \> \> \\
\>192.0.2.18\>3\>1\>1\>2\> \> *\>*\> \\
\end{tabbing}
\end{alltt}
\end{minipage}
}

The {\stt show olsr4 topology} command will show the Topology Control (TC)
records which have been learned by this node by destination.

TC records with a distance of less than 3 hops are ignored by XORP for the
purposes of routing, as they are considered redundant. Reachability information
should already exist in the one-hop and two-hop neighborhood for these destinations.
Messages containing such TC records are however forwarded.
This behaviour conforms to RFC 3626 section 10.3.

The Lasthop field shows the main address of the node which originated this TC record.

The Distance field shows the distance between the origin and this node, as measured
from the hop-count field of the OLSR message which contained this TC record.

The SeqNo field shows the Advertised Neighbor Sequence Number (ANSN) of the entry.

The Hold field shows the hold time, in seconds, for which the record is valid.

\vspace{0.1in}
\noindent\framebox[\textwidth][l]{\scriptsize
\begin{minipage}{6in}
\begin{alltt}
\begin{tabbing}
user@hostname> \textbf{show olsr4 topology}\\
\=xxxxxxxxxxxxxxxx\=xxxxxxxxxxxxxxxxxxxx\=xxxxxxxxx\=xxxxxxxxxxxxxxxx\=xxxx\=\kill
\>Destination\>Lasthop\>Distance\>SeqNo\>Hold\\
\>192.0.2.17\>192.0.2.6\>2\>22\>254\\
\>192.0.2.18\>192.0.2.6\>2\>22\>254\\
\>192.0.2.18\>192.0.1.2\>3\>1\>254\\
\>192.0.2.6\>192.0.2.18\>2\>2\>13\\
\>192.0.2.17\>192.0.2.18\>2\>2\>13\\
\>192.0.1.2\>192.0.2.18\>2\>2\>13\\
\end{tabbing}
\end{alltt}
\end{minipage}
}

\newpage
The {\stt show olsr4 twohop-link} command shows links in the two-hop neighborhood.

The Nexthop field shows the main address of the one-hop neighbor used to reach
the Destination. The Hold field shows the hold time, in seconds, for which the
record is valid.

\vspace{0.1in}
\noindent\framebox[\textwidth][l]{\scriptsize
\begin{minipage}{6in}
\begin{alltt}
\begin{tabbing}
user@hostname> \textbf{show olsr4 twohop-link}\\
\=xxxxxxxxxxxxxxxx\=xxxxxxxxxxxxxxxxxxxx\=xxxxxxxxx\=xxxxxxxxxxxxxxxx\=xxxx\=\kill
\>Destination\>Nexthop\>Hold\\
\>192.0.2.18\>192.0.1.2\>5\\
\>192.0.2.6\>192.0.2.18\>87\\
\>192.0.2.18\>192.0.2.6\>5\\
\end{tabbing}
\end{alltt}
\end{minipage}
}

The {\stt show olsr4 twohop-neighbor} command shows the two-hop neighbors.

The N1 field shows if the neighbor is also known to this node as a one-hop
neighbor. Such neighbors are not taken into consideration for MPR coverage
calculations, as they are already directly reachable.

The Coverage field shows the number of MPRs selected by XORP which cover this
two-hop neighbor. This field is updated after an MPR selection is triggered.

The Reachability field shows the number of one-hop neighbors which XORP considers
to be candidate MPRs, and which may be used to reach this two-hop neighbor. This
should not be confused with the reachability of a one-hop neighbor.

\vspace{0.1in}
\noindent\framebox[\textwidth][l]{\scriptsize
\begin{minipage}{6in}
\begin{alltt}
\begin{tabbing}
user@hostname> \textbf{show olsr4 twohop-neighbor}\\
\=xxxxxxxxxxxxxxxx\=xxx\=xxxxxxxxx\=xxxxxxxxxxxxxxxx\=xxxx\=\kill
\>MainAddr\>N1\>Coverage\>Reachability\\
\>192.0.1.2\> \>1\>1\\
\>192.0.2.18\>*\>1\>0\\
\>192.0.2.6\>*\>1\>0\\
\end{tabbing}
\end{alltt}
\end{minipage}
}
