%
% $XORP: xorp/docs/design_arch/error_handling.tex,v 1.40 2006/08/02 05:43:31 pavlin Exp $
%

\documentclass[11pt]{article}

%\usepackage[dvips]{changebar}

\usepackage{subfigure}
\usepackage{fullpage}
\usepackage{setspace}
\usepackage{times}
\usepackage{latexsym}
\usepackage{epsfig}
\usepackage{graphicx}
\usepackage{xspace}
\usepackage{color}
\usepackage{amsmath}
\usepackage{rotating}
\usepackage{moreverb}
\usepackage{listings}
\usepackage{alltt}
\usepackage{stmaryrd}
%\usepackage[dvipdf]{graphics}
%\usepackage[dvips]{graphicx}
%\usepackage{xorp}

\definecolor{gray}{rgb}{0.5,0.5,0.5}
\newcommand{\etc}{\emph{etc.}\xspace}
\newcommand{\ie}{\emph{i.e.,}\xspace}
\newcommand{\eg}{\emph{e.g.,}\xspace}
%\newcommand{\comment}[1]{{\color{gray}[\textsf{#1}]}}
%\newcommand{\comment}[1]{}

\newcommand{\xorp} {{\em XORP}\@\xspace}
\newcommand{\module} {{\em module}\@\xspace}
\newcommand{\modules} {{\em modules}\@\xspace}
\newcommand{\finder} {{\em Finder}\@\xspace}
\newcommand{\xorpsh} {{\em Xorpsh}\@\xspace}
\newcommand{\cm} {{\em CM}\@\xspace}
\newcommand{\xrl} {{\em XRL}\@\xspace}
\newcommand{\xt} {{\em XRL Target}\@\xspace}
\newcommand{\rtrmgr} {{\em rtrmgr}\@\xspace}


% Changebar stuff
% \newenvironment{colorcode}{\color{blue}}{}
% \renewcommand{\cbstart}{\begin{colorcode}}
% \renewcommand{\cbend}{\end{colorcode}}

% \pagestyle{empty}

\begin{document}

\title{XORP Error Handling \\
\vspace{1ex}
Version 1.3}
\author{ XORP Project					\\
	 International Computer Science Institute	\\
	 Berkeley, CA 94704, USA			\\
         {\it http://www.xorp.org/}			\\
	 {\it feedback@xorp.org}
}
\date{August 2, 2006}

\maketitle


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Introduction}

A \xorp router is made up of a number of processes that communicate
via XRLs \cite{xorp:xrl} (a messaging system developed for \xorp). In
this document we will focus on how to deal with errors that are
generated directly or indirectly by \xrl calls, and discuss how to
handle process failures and the subsequent restart of failed
processes.  Of course, in an ideal world processes would not fail, but
when they do fail, our goals are to keep as much router
functionality working as possible, to avoid permanent inconsistencies
at all costs, and for the remainder of the functionality to be
restored as quickly as possible.

Many \xorp processes share routing state that must remain
synchronised. For example, the BGP process sends the result of its
routing decisions to the RIB process, which passes these routes on to
the FEA and hence to the forwarding engine's Forwarding Information
Base (FIB). If the RIB process fails, then BGP would lose the ability
to manipulate the FIB, and forwarding would not match the BGP routing
table.  Thus, BGP should withdraw all routes that it told its peers, or
alternatively it might drop all peerings until the RIB has
successfully restarted.

A critical component of the system is the router manager process
(\rtrmgr) which is responsible for starting and stopping routing
processes. When a \xorp process starts or terminates, that
process's XRL client library ensures that the \finder is notified. If
a process has an interest in the status of another process it can
register interest with the \finder.

In a \xorp router, as with any complex system, errors can occur. These
errors can range from a \xorp process simply failing, to an attempt to
install a route into the forwarding engine that already exists. Errors
need to be dealt with in a consistent manner. The types
of error that may occur are categorized below.

The first type of error is {\em Process Failure}.

The second type of error is {\em Communication Error}. At the most
basic level an attempt to send an \xrl has failed. The process that
was the recipient of the \xrl may have failed or be slow to respond.
The message that was being sent may have been lost in transit.

The third type of error, {\em Execution Error}, is when an XRL call
returns an error due to some underlying interaction failure. A simple
example of this type of error is a ``route add'' failing. The attempt to
add a route may fail for many reasons. The identical route may already
be present or a different route may be installed. The error may occur
due to a bug in the router code, because routing state has been
manipulated by non \xorp processes, or due to resource starvation in
the forwarding engine.

The fourth type of error, {\em Type Error}, is when an XRL call fails
because the arguments passed to an XRL are invalid. This error will
most likely be due to a version mismatch between \xorp processes. If
all the processes in a \xorp router have been built from the same
source tree this error should not occur. As we are building an
extensible router it may be the case that a process built from a
different source tree may encounter compatibility problems.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{\label{pfailure}Process Failure}

A \xorp router is made up of a number of distinct processes. There are
dependencies between these processes. We define the critical
dependencies and what action to take on detecting failure.

The most critical component of a \xorp router is the \rtrmgr/\finder
process. One of the functions of this component is to start/re-start
processes. If process A is dependent on the status (\eg alive, dead,
restarted) of process B, then process A registers this interest with
the \finder. This dependency on the \rtrmgr/\finder for managing and
monitoring process liveness state means that a \xorp router cannot
survive the failure of this process. If we attempted to survive a
\finder restart, it is conceivable that, in the same time window,
another monitored process could restart, in which case the restarting
of the monitored process could be missed by the \finder. To guard
against this possible race, a \xorp process that detects the loss of
the \finder must exit. There is one exception to this rule, the
\xorpsh process, that will be discussed later in section \ref{xorpsh}.

Each process in a \xorp router is described with how it should behave
when another process in the system fails. Processes can explicitly
register interest in the status of other processes through the
\finder. If process A is dependent on the state of process B then
process A must register interest in process B.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Implementing process failure detection}

The \finder process will send keepalive messages to all processes at
thirty second intervals. If a process does not respond to a keepalive
it is considered dead. The keepalive messages are sent over a reliable
transport such as TCP. A process dying should therefore be easy to
detect.

The \rtrmgr might also be able to detect that a process has died (but
not if it is simply not responding), as it will normally receive a
SIGCHILD signal.  On discovering a process has died, the \rtrmgr will
send a hint to the \finder, which will immediately try and send a
keepalive.  Again if the process has died it should be easy to detect.

If a process is not responding to keepalives but it is still alive, it
will be marked as dead and all interested processes will be notified.
Most importantly, the \rtrmgr will be notified and it will kill the
running process and start a new process.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Actions to take on detecting process failure}

Table \ref{failure_table} indicates what action a process should take on
detecting failure in other processes~\footnote{Note that currently this
document does not describe the policy manager. Such description will be
included in the future. For all practical reasons, the policy manager is
as important as the rtrmgr/finder, even though it is running as a
separate process.}. The ``(G)'' denotes that the process should attempt
to exit gracefully. Figure \ref{failure_fig} shows the relationship
between the various processes. The thick arrows should be modelled as a
signal sent from a process dying to its dependent processes.

\begin{figure}
  \begin{center}
    \includegraphics[width=0.9\textwidth]{figs/error_dependency.eps}
    \caption{Process relationship on failure}
    \label{failure_fig}
  \end{center}
\end{figure}

\begin{table}[ht]
\begin{center}
\begin{tabular}{|c|c|c|c|c|c|c|c|c|c|c|}
\hline
Process fails   &                 &          &      &      &      &         &      &      &      &         \\\hline
                & \rtrmgr/        & FEA      & MFEA & RIB  & IGMP & PIM     & BGP  & RIP  & OSPF & \xorpsh \\
                & \finder         &          &      &      &      &         &      &      &      &         \\\hline
\rtrmgr/        & /               & Withdraw & Exit & Exit & Exit & Exit    & Exit & Exit & Exit & Report  \\
\finder         &                 & All      &      &      &      &         &      &      &      & Problem \\
                &                 & Unicast  &      &      &      &         &      &      &      & Wait    \\
                &                 & Routes   &      &      &      &         &      &      &      &         \\
                &                 & Exit     &      &      &      &         &      &      &      &         \\\hline
FEA(*)          &  Restart        & /        & Exit & Exit & Exit & Exit    & Exit & Exit & Exit & -       \\\hline
MFEA(*)         &  Restart        & -        & /    & -    & Exit & Exit    & -    & -    & -    & -       \\\hline
RIB             &  Restart        & Withdraw & /    & -    & Exit & Exit    & Exit & Exit & Exit & -       \\
                &                 & All      &      &      & (G)  & (G)     & (G)  & (G)  & (G)  &         \\
                &                 & Unicast  &      &      &      &         &      &      &      &         \\
                &                 & Routes   &      &      &      &         &      &      &      &         \\\hline
IGMP            &  Restart        & -        & -    & -    & /    & Delete  & -    & -    & -    & -       \\
                &                 &          &      &      &      & Local   &      &      &      &         \\
                &                 &          &      &      &      & Members &      &      &      &         \\
                &                 &          &      &      &      & After   &      &      &      &         \\
                &                 &          &      &      &      & Timeout &      &      &      &         \\\hline
PIM             &  Restart        & -        & -    & -    & -    & /       & -    & -    & -    & -       \\\hline
BGP             &  Restart        & -        & -    & -    & -    & -       & /    & -    & -    & -       \\\hline
BGP             &  Restart        & -        & -    & -    & -    & -       & /    & -    & -    & -       \\\hline
RIP             &  Restart        & -        & -    & -    & -    & -       & -    & /    & -    & -       \\\hline
OSPF            &  Restart        & -        & -    & -    & -    & -       & -    & -    & /    & -       \\\hline
\xorpsh         &  Restart        & -        & -    & -    & -    & -       & -    & -    & -    & /       \\\hline
\end{tabular}
\end{center}
{\small Note(*): Typically, the MFEA would be part of the FEA process}
\caption{\label{failure_table}Action to take on detecting process failure}
\end{table}

%%%%%%%%%%%%%%%%%%%%%%
\subsubsection{\rtrmgr/\finder - Router manager}

If the \rtrmgr/\finder dies then all bets are off and all processes
should exit apart from the \xorpsh.

If a \xorp process exits unexpectedly the \rtrmgr/\finder should
attempt to restart the process.

%%%%%%%%%%%%%%%%%%%%%%
\subsubsection{FEA - Forwarding Engine Abstraction}

The FEA primarily accepts routes from the RIB and places them in the
kernel. The FEA should tag all routes that it has installed in the
kernel.  On restart, the FEA should remove all routes that a previous
incarnation of the FEA has placed in the kernel. When an FEA is
exiting it should attempt to remove all routes that it has installed
in the kernel.

The FEA process should register interest in the RIB. If the RIB fails
the FEA should withdraw all routes that the RIB has sent to it.

%%%%%%%%%%%%%%%%%%%%%%
\subsubsection{MFEA - Multicast Forwarding Engine Abstraction}

The MFEA is multicast analogue to the unicast FEA. If should be noted
that typically the MFEA would be part of the FEA process.

Similar to the FEA, on restart or exit the MFEA should remove all
multicast forwarding entries that were installed in the kernel. Note
that the MFEA does not contain a copy of the multicast forwarding entries
that were installed in the kernel, so it should utilize a
mechanism that removes all multicast forwarding entries at once.  In
case of UNIX-based systems, closing the multicast routing socket will
automatically remove all entries.

If the multicast routing process that has installed the multicast
forwarding entries exits, then the MFEA should remove all multicast
forwarding entries from the kernel. Currently, PIM is the only
multicast routing process. In the future, the XORP multicast routing
architecture may contain a special coordinator among all multicast
routing protocol instances, analogous to the function of the unicast
RIB process. If that coordinator exits, the MFEA should remove all
multicast forwarding entries from the kernel.

%%%%%%%%%%%%%%%%%%%%%%
\subsubsection{RIB - Routing Information Base}

Routes from the routing processes are sent to the RIB; the winners are
sent to the FEA.

The RIB should register interest in the FEA. If the FEA fails the RIB
should exit. All routing processes that interact with the RIB should,
on detecting the shutdown of the RIB, also terminate gracefully.

%%%%%%%%%%%%%%%%%%%%%%
\subsubsection{IGMP/MLD}

If the FEA/MFEA process exits then this process should exit.

%%%%%%%%%%%%%%%%%%%%%%
\subsubsection{PIM}

If the RIB or the FEA/MFEA process exits then this process should exit.

%%%%%%%%%%%%%%%%%%%%%%
\subsubsection{BGP}

Currently the only other process in the system that BGP interacts
with is the RIB. If the BGP process detects that the RIB has died then
it should gracefully terminate its sessions and exit.

In the future the TCP connections that BGP makes will be mediated
through FEA, at which time the BGP process should also register
interest in the state of the FEA. If the BGP process detects the death
of the FEA it should exit immediately.

%%%%%%%%%%%%%%%%%%%%%%
\subsubsection{RIP}

The RIP process should register interest in the FEA and the RIB. If
the RIB dies then the RIP process should attempt to exit gracefully.
If the FEA dies the RIP process should exit immediately.

%%%%%%%%%%%%%%%%%%%%%%
\subsubsection{IS-IS}

The IS-IS process should register interest in the FEA and the RIB. If
the RIB dies then the IS-IS process should attempt to exit gracefully.
If the FEA dies the IS-IS process should exit immediately.

%%%%%%%%%%%%%%%%%%%%%%
\subsubsection{OSPF}

The OSPF process should register interest in the FEA and the RIB. If
the RIB dies then the OSPF process should attempt to exit gracefully.
If the FEA dies the OSPF process should exit immediately.

%%%%%%%%%%%%%%%%%%%%%%
\subsubsection{\label{xorpsh}\xorpsh}

The \xorpsh provides a command line interface to the XORP router.
Other processes in the system exiting should never cause it to
exit. The \rtrmgr/\finder process exiting should generate
warning output to the user and then the \xorpsh should wait for the
router to restart.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{XRL Communication Errors}

Interprocess communication in \xorp is achieved using XRLs. In this
section we will consider what should be done when an XRL call fails
due to a communication error.

XRLs can be sent over unreliable transports such as UDP or reliable
transports such as TCP. The type of transport used is decided by the
XRL library based on the specification of each interface.  For the
purposes of error handling, the reliable and unreliable transports are
the same in all regards, except that reliable transports in XORP never
explicitly report a timeout error.

XRL communication is asynchronous: applications request the dispatch
of an XRL and expect to have a callback invoked when the dispatch
result is available.  This presents opportunities for immediate and
deferred error indications.  Immediate error indications occur when
the request for XRL dispatch is made: the canonical example occurring
when no more buffer space is available within the XRL library is
available. An application is able to detect these errors
synchronously: the dispatch request indicates an error in its return
value.  Deferred error indications happen through the dispatch
callbacks.  These callbacks are required to take an XrlError object as
an argument.  An XrlError object is comprised of an enumerated error
code and an optional string containing specific information relating
to the error.  The set of enumerated error codes is presented below.

Immediate and deferred errors are exclusive.  If the \xt dispatching
an XRL got an immediate error, it will not receive a callback
indicating a deferred error.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection*{Standard Dispatch XRL Error Values}

The standard XRL return values are returned to the requesting \xt by
the dispatching \xt.  When any of these values are returned, the XRL
communication has been successful.

\begin{description}

  \item [OKAY] XRL dispatch successful.  Additional parameters in
  XRL callback contain return values.

  \item [COMMAND\_FAILED] XRL reached dispatcher, but could not be
  dispatched. The reason for failure may be specified in the note
  associated with the XrlError object.

  \item [BAD\_ARGS] XRL reached dispatcher, but argument types did not match
  those expected by the dispatcher.

\end{description}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection*{Finder XRL Error Values}

\begin{description}

  \item [NO\_FINDER] This error occurs when an \xt cannot communicate
  with the \finder. This always indicates a serious problem with the
  router, as the \finder should always be present. The application
  SHOULD treat this error as fatal.

  \item [RESOLVE\_FAILED] This error occurs when a \xt process tries to
  resolve an XRL the \finder has no result for.  This may be because the
  target specified in the XRL does not exist or exists, but is still in
  the process of registering the XRL it exports.

  RESOLVE\_FAILED errors may happen because of a benign cause, namely
  that processes started up in a less than perfect order, so a target's
  user has initialized before the target itself. Applications SHOULD
  handle this type of transient RESOLVE\_FAILED error with a
  retransmission strategy.  Applications may avoid this error by using
  the Finder event observer interface to detect when the particular
  target becomes ready.

  \item [NO\_SUCH\_METHOD] This error occurs when the named \xt is running and
  has registered 
  it's XRLs, but it does not support the method named in the XRL.
  NO\_SUCH\_METHOD generally indicates a version mismatch between two
  processes. This error may be considered fatal, or (for example) the
  application might react by trying to access an older version of the
  interface. The application can expect, however, that NO\_SUCH\_METHOD
  errors are not transient: If an XRL access gets a NO\_SUCH\_METHOD
  error, then that XRL will always result in a NO\_SUCH\_METHOD error,
  at least until the target process restarts.

\end{description}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection*{Transport and Internal Xrl Error Values}

\begin{description}

  \item [SEND\_FAILED] The underlying XRL transport mechanism has failed.
  For example, the TCP connection has been reset, or a UDP connection
  gets a port-unreachable message. The expectation is that no further
  communication with the specific endpoint will succeed.

  \item [SEND\_FAILED\_TRANSIENT] This error occurs when the XRL library
  temporarily cannot send a particular XRL. Usually, this will be
  because of congestion or a slow receiver: the kernel has run out of
  buffer space. Note that the XRL library performs some buffering
  itself, to ensure that XRL requests are either completely transmitted
  or not transmitted at all.
  \emph{Note: The XRL library does not yet implement this error.}

  \item [REPLY\_TIMED\_OUT] -- The target did not reply within a
  transport-protocol-specific period of time. Possible reasons include
  network congestion, peer failure, network interface failure, and so
  on. As in all network communications, when a timeout occurs we don't
  know if the last unacknowledged XRL request was received and processed
  by the peer. This error occurs in unreliable transmit only.

\end{description}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Handling XRL Errors}

XRLs may be directed to a class of target or a particular instance of
a target.  The first instance of a target that registers with the
\finder is considered to be the primary instance of its class and XRLs
addressed to that are directed to that instance.  The XRL library MAY
hide certain REPLY\_TIMED\_OUT and SEND\_FAILED errors for XRLs
directed towards classes, \ie should the instance which is acting as
the primary instance fail or exit, then another instance in that
class, will receive the class directed XRL requests.

%When communication with a particular
%instance of the target fails, the XRL library thus MAY search for
%another instance by contacting the \finder. The XRL library MUST NOT
%perform this retransmission, however, unless it can guarantee that the
%request was not acted on by any instance. (This rules out most
%unreliable transports.) If it cannot guarantee this, or if
%retransmission fails, the XRL will get an error -- either
% REPLY\_TIMED\_OUT, SEND\_FAILED, NO\_FINDER, or RESOLVE\_FAILED.
%
% XXX This is very MIT a la Gabriel's Worse-is-Better :-)  I like it,
% but would rather not commit to this just now
%

The XRL errors of NO\_FINDER, RESOLVE\_FAILED, and to some extent
NO\_SUCH\_METHOD generally represent serious problems with the router.
SEND\_FAILED represents a serious problem with the target, such as
that an instance of the target has died; this problem may or may not
be transient. The SEND\_FAILED\_TRANSIENT and REPLY\_TIMED\_OUT errors
are
potentially common errors, and should be handled by the
application. However, the likelihood of SEND\_FAILED\_TRANSIENT can
often be reduced, making it a ``fatal'' error from the application's
point of view, by limiting the rate at which requests are sent.

NO\_FINDER, RESOLVE\_FAILED, NO\_SUCH\_METHOD, and
SEND\_FAILED\_TRANSIENT, are all indications that the XRL was not
communicated to its target. They are therefore called \emph{send
failures}.  The other two errors, REPLY\_TIMED\_OUT and SEND\_FAILED,
may be generated even if the target received the request. They are
therefore called \emph{receive failures}.

If a peer dies, we will receive notification of this explicitly and
will deal with it as specified in section \ref{pfailure}. Thus most
XRL transport errors SHOULD NOT be taken as an indication that the
peer is definitely dead. If an application cares that the peer has
died or restarted, it SHOULD register with the finder to receive
notifications of process restarts. Thus, a process SHOULD assume that
an XRL transport problem will be transient until it receives an
explicit confirmation that the destination has failed, particularly
when the XRL interface is unreliable.

In addition to an XRL interface being reliable or unreliable, the way
the application uses an XRL interface can by pipelined or
non-pipelined.  In the pipelined case, multiple requests can be
outstanding simultaneously; in the non-pipelined case at most one
request can be outstanding at a time.

It is useful for us to categorize XRL interfaces along these two axes:
reliable/unreliable and pipelined/non-pipelined. 

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection*{Unreliable, Non-pipelined}

If an XRL send failure occurs, the sending application MAY choose to
retransmit the XRL, or ignore the failure as it sees fit.  

In an XRL receive failure occurs, the sending application MAY also choose
to retransmit the XRL, or ignore the failure as it sees fit. However, if
the application chooses to re-send the XRL, the interface MUST be written
in such a way that the receipt of a duplicate request will not damage the
system. (XXX Isn't this true anyway? Network duplicates?)

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection*{Reliable, Non-pipelined}

If a SEND\_FAILED\_TRANSIENT error occurs, the sending application MAY
retransmit the XRL.

SEND\_FAILED, NO\_FINDER, and most RESOLVE\_FAILED and
NO\_SUCH\_METHOD errors are unrecoverable.  The application should
cause this XRL interface to go dormant, in the expectation that it
will authoritatively discover from the finder that the target has
died.

REPLY\_TIMED\_OUT cannot happen on reliable interfaces.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection*{Unreliable, Pipelined}

The same issues apply as with unreliable, non-pipelined, but the
situation is more complicated.  An interface that uses unreliable
transport and pipelining is one that explicitly permits loss \emph{and
re-ordering} of requests.  It is up to the application to choose
whether to retransmit XRLs that return SEND\_FAILED\_TRANSIENT or
REPLY\_TIMED\_OUT, but the application must only do so if it is
certain that the re-ordering caused by retransmission will not be a
problem.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection*{Reliable, Pipelined}

The XRL library ensures that pipelined messages sent to a reliable target
are delivered in order. In particular, if a request $R$ to a given target
gets an error, then no \emph{outstanding} requests to that target
\emph{registered later than $R$} will successfully complete -- they will
all get the same error, and none of them will be delivered to the receiving
application. Once the error is delivered, this error state is wiped out,
and later requests to the target may succeed -- perhaps because the target
was restarted.

Again, SEND\_FAILED, NO\_FINDER, and most RESOLVE\_FAILED and
NO\_SUCH\_METHOD errors are unrecoverable.
The application SHOULD cause this XRL interface to go dormant, in the
expectation that it will authoritatively discover from the finder that
the target has died.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Execution Error}

A XORP router is partitioned into many processes; most of the operating
system specific interactions are performed by the FEA. In a router the
most frequent operation will be the adding and deleting of routes.
Consider BGP adding a route. First the BGP process will send the route
to the RIB, then the route may be sent to the FEA. If the addition of the
route from the RIB to the FEA fails, then there is no way of
propagating this failure back to the BGP process due to the
asynchronous nature of XRLs. If adding/deleting a route fails a very
drastic way of propagating this failure back to the BGP process would
be for either or both the FEA and RIB processes to exit, in which case
the process failure responses already described would be used and BGP
would exit. Process exit is an extreme response to failing
to add a route, but at least the error handling code for process exit
exists already. It is important though not
to mask over implementation problems by ignoring errors. In the rest
of this section we will outline how to deal with a number of common
errors.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Adding/Deleting route failures}

As stated above, a highly likely error is failures when adding or
deleting routes. Typically the interaction will occur between the RIB
and FEA. When an error occurs it should be logged by the FEA and the
cause returned to the RIB. The RIB can be configured with policy on
how to react to different errors.

Adding a route will typically fail because a route already exists.
Firstly, if a route already exists it is either the same or different
to the one that we attempted to add. Secondly, either the FEA
installed the route or a third party installed it. Therefore when
adding a route fails the FEA should return if the current route is the
same or different to the one we attempted to add, as well as who
installed the route originally. The RIB on receiving the error state
from the FEA can decide as a matter of policy how to proceed. If an
attempt to add a route fails because a different route exists the RIB
could choose to delete the old route and add the new route.

The most common reason for a route deletion to fail would be that the
route is no longer present. The FEA should log that it has been asked
to delete a route that doesn't exist. The RIB should decide if this
problem should be considered fatal.

%%%%%%%%%%%%%%%%%%%%%%
\subsubsection{Route Add Failure due to Resource Starvation}

When a routing process sends a route to the RIB, the asynchronous
nature of XRL handling means that the RIB will typically accept the
route before it has finished processing the addition, and certainly
before it attempts to pass the route to the FEA, and hence on into the
forwarding engine.  It is possible for the route addition to fail due
to memory exhaustion in either the RIB or in the forwarding engine
itself.  Should this occur, it is important for the routing protocol
to be made aware of the event, because the routing information will
now be out of synchronization with the forwarding information.

If the forwarding engine refuses the route due to resource starvation,
the FEA will receive the failure.  The FEA will then indicate
asynchronously to the RIB that the failure occurred.  The RIB will in
turn delete all state from all routing protocols that contributed
versions of this route, and asynchronously pass the failure up to
those routing protocols.  Each of those routing protocols will then
handle the failure in a protocol specific manner.

If the failure occurs due to resource starvation in the RIB, a similar
process will be initiated.  It is not currently clear how to reliably
notify a routing protocol in the case when the router is running out
of memory for user-space processes.

In the case of BGP, if a route fails to be added due to resource
starvation, the simplest mechanism is to take down the peering that
originated the route.  The normal peer reinitialization mechanism
(after some time delay) will ensure that all the routes are
re-instantiated after the resource starvation problem goes away.

In the case of RIP, if a route fails to be added due to resource
starvation, the simplest mechanism is to send our peers an infinite
metric route for this particular prefix and to delete the state for
this prefix.  The normal RIP periodic update will ensure that the
route is re-instantiated after the resource starvation problem goes
away.

In the case of link-state protocols such as OSPF and IS-IS, there is
no good way to deal with this situation.  A reasonable solution might
be to take down all adjacencies to avoid causing a blackhole, then to
bring up the adjacencies again but not propagate any link-state
advertisements to our neighbors (so they won't route via us) until all
the link-state advertisements have been received and we've
successfully installed all the routes in the kernel.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%     APPENDIX
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\appendix
\section{Modification History}

\begin{itemize}

  \item June 9, 2003: Initial version 0.3 completed.

  \item August 28, 2003: Updated the version to 0.4, and the date.

  \item November 6, 2003: Updated the version to 0.5, and the date.

  \item July 8, 2004: Updated the version to 1.0, and the date.

  \item April 13, 2005: Updated the version to 1.1, and the date.

  \item March 8, 2006: Added a footnote about the policy manager process.
  Updated the version to 1.2, and the date.

  \item August 2, 2006: Added ``Modification History'' appendix.
  Updated the version to 1.3, and the date.

\end{itemize}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%     BIBLIOGRAPHY
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\bibliography{../tex/xorp}
\bibliographystyle{plain}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\end{document}
