\documentclass[11pt]{article}
\usepackage{xspace}
\usepackage{times}
\usepackage{psfig}
\usepackage{amsmath}
\newcommand{\module} {{\em module}\@\xspace}
\newcommand{\modules} {{\em modules}\@\xspace}
\newcommand{\finder} {{\em Finder}\@\xspace}
\newcommand{\cm} {{\em CM}\@\xspace}
\textwidth 6.5in
\topmargin 0.0in
\textheight 8.5in
\headheight 0in
\headsep 0in
\oddsidemargin 0in
%\date{}
\title{Error Handling in XORP}
\author{First pass: Mark Handley}
%\twocolumn
\begin{document}
\parsep 0ex
\parskip 1.0ex
\parindent 0em
\noindent
\maketitle                            
\section{Introduction}
A XORP router consists of a number of user-space modules communicating
via XRLs, a Forwarding Engine Abstraction process (which is
effectively a kernel proxy) and a kernel forwarding path.  State is
communicated between these modules during the normal operation of the
router.  In this document we attempt to map out what the correct
actions should be when XORP modules unexpectedly restart, in terms of
who is responsible for removing the now-obsolete state, and who is
responsible for re-instantiating the state to get back to operational
status.

This document assumes roughly the process structure in Figure
\ref{modules}.  The RouterManager process is responsible for starting
up all other processes, and for monitoring their health using periodic
XRL status messages.

\begin{figure}[htb]
\centerline{\psfig{figure=processes3.ps,width=0.6\textwidth}}  
\caption{XORP Modules}
\label{modules}
\end{figure}

\section{General Infrastructure}

\subsection{RouterManager Restart}
A router manager restart is considered a fatal event; all router
processes will be terminated and restarted.

\subsection{Finder Restart}
The XRL mechanism should include a keepalive mechanism that allows
each process to detect when the Finder has failed.  Each process's XRL
library will then repeated attempt to re-connect to the Finder.  When
the reconnect succeeds, the state that was registered with the old
Finder instance will then be re-registered, allowing normal router
operation to resume.  This whole process is handled in the XRL library
code, so no explicit action needs to be taken by any process, except
for the RouterManager which must restart the Finder process.

During the Finder restart process, some services will be temporarily
unavailable if a client does not have a cached resolved copy of an XRL
for a request it wishes to make.  All processes should gracefully
handle a NO\_FINDER error during regular operation and simply
periodically retry the request.  It should be noted that after a
Finder restart, there may be a period of time when the new Finder has
incomplete state, and may return a FINDER\_INITIALIZING error because
the destination module has not yet had a chance to re-register.
Processes should gracefully handle such an event, and generally retry the
request.  Outside of this period, FINDER\_INITIALIZING will not be
returned; instead RESOLVE\_FAILED will be returned, and should be
treated as an error in the normal way.

Since the Finder has no way of knowing what the appropriate end of
its initialization period is, it may be able to use the RouterManger
to tell it all of the processes it should expect to hear from.  The
Finder could then infer the end of the initialization period when each
process has registered its mappings.  The entering of mappings into
the Finder by client processes may need modifying so that initial
mappings are done in one transaction to facilitate the end of
initialization detection.

\subsection{CLI Restart}
A CLI restart will terminate all terminal sessions with that CLI
instance.  However, the CLI itself will not generally store
configuration state, so a CLI restart should not cause any process
other than the RouterManager to take any remedial action.

\section{Unicast Routes}

\subsection{FEA Restart}
\subsubsection*{State teardown}
The FEA is stateless with respect to unicast routes.  FEA termination
does not cause the forwarding kernel to remove forwarding state.  The
URIB will detect that the FEA has changed from XRL keepalive message
timeout, but it takes no immediate action on this event.

The RouterManager process will detect the FEA failure,
either from a SIGCHILD, or from XRL keepalive message timeout.  It
should log the event, and attempt to restart the FEA.

\subsubsection*{State re-instantiation}
The URIB will repeatedly attempt to contact the new FEA (sending a XRL
status request) until it is successful.  While the FEA is not
responding, routing changes may occur; these cannot be passed to the
FEA, but this failure should be silent.  Upon detecting successful FEA
restart, the URIB will send a {\tt flush\_all\_routes}, and then dump
its entire forwarding table into the FEA.

If the URIB fails to detect FEA restart after a suitable period of
time (eg 10 seconds), it should send a {\tt forwarding\_engine\_failure}
message to the routing protocol processes that are registered with
it. On receipt of such a message, a routing process should send
appropriate messages to its peers withdrawing all routing information
that may cause forwarding through this router.  If the URIB
subsequently succeeds in contacting the FEA, it should send a
{\tt forwarding\_engine\_alive} message to the routing protocol
processes, which re-enables normal operation.

\subsection{URIB Restart}

\subsubsection*{State Teardown}
The FEA is not required to monitor the status of the URIB.  Even if it
does detect the URIB failure, it should not take any action.

Each routing protocol will detect URIB failure from XRL keepalive
message timeout.  The default behavior on a routing process detecting
URIB failure should be to immediately send appropriate messages to its
peers withdrawing all routing information that may cause forwarding
through this router. In general, the routing protocol should not
drop its peerings unless this is the only way to prevent forwarding.  

The RouterManager process will detect the URIB failure,
either from a SIGCHILD, or from XRL keepalive message timeout.  It
should log the event, and attempt to restart the URIB.

\subsubsection*{State re-instantiation}

After detecting URIB failure, routing processes should repeatedly
attempt to re-contact the URIB (sending a XRL status request) until it
is successful.  Upon success, they should re-send their routing table
to the URIB, and re-register any nexthop information that they need to
hear from the URIB.  After this is done, they should re-advertise the
router to their peers as being available for forwarding.

\subsection{Routing Protocol Restart}

\subsubsection*{State Teardown}

The URIB should detect the failure of a routing protocol from XRL
keepalive message timeout.  It should then delete all the routes that
it has stored from that routing protocol, propagating the deletions to
both the kernel and to other routing protocols that have notification
entries set for these routes.

The RouterManager process will detect the routing process failure,
either from a SIGCHILD, or from XRL keepalive message timeout.  It
should log the event, and attempt to restart the routing process.

\subsubsection*{State re-instantiation}

Routing state re-instantiation after a routing protocol restart is
handled the same as if that routing protocol started up for the first
time - no special action is required.

\section{Multicast Routes}

\subsection{FEA Restart}

\subsubsection*{State teardown}
The kernel should detect that the routing socket has closed.  On
closure of the routing socket, all multicast forwarding state is
flushed from the kernel.

The MFIB process (which may or may not be a part of PIM-SM) will
detect the FEA failure from XRL keepalive message timeout, or from
timeout of an attempt to modify multicast routing state.  The MFIB
must assume that the FEA will be restarted, and so it will attempt to
re-contact the FEA periodically.

PIM-SM should not take any special action.

The RouterManager process will detect the FEA failure, either from a
SIGCHILD, or from XRL keepalive message timeout.  It should log the
event, and attempt to restart the FEA.

\subsubsection*{State re-instantiation}
No special action is required for state re-instantiation after the FEA
has restarted.  When a multicast data packet arrives, it will generate
a CACHEMISS event, which will be signaled to the FEA.  The FEA
doesn't have state for this (S,G) or (*,G), so the CACHEMISS is then
propagated to the MFIB process. 
\begin{itemize}
\item If the MFIB has the appropriate forwarding information, this
will be sent to the FEA which will then send it to the kernel so that
the packet can be forwarded correctly.  
\item If the MFIB has state, but the packet arrived on the wrong
interface, the MFIB should also send this forwarding information to the
FEA, but it should also signal WRONGIIF to the appropriate multicast
routing process.
\item If the MFIB has no forwarding state that matches this (S,G),
CACHEMISS is signaled to the appropriate multicast routing process.
\end{itemize}
In this way, as data packets arrive, they cause both the FEA and the
kernel's multicast forwarding state to be re-instantiated.

\section*{XRL Error Handling}
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.

All XRL calls will ultimately get a response. In the normal case the
response returns the status of the call (good or bad). In addition to
error responses produced by the application, the XRL library can also
return the following error responses:
\begin{itemize}
\item NO\_FINDER
\item RESOLVE\_FAILED
\item SEND\_FAILED
\item REPLY\_TIMED\_OUT
\end{itemize}
From an application point or view, the first three errors are
equivalent: the XRL was not communicated to the destination.  We will
discuss these below using the generic term {\em XRL send failure}.

However, its not clear what can be inferred from a timeout
response. The reasons for a timeout can be: the peer has died, peer is
slow to respond, the network cable has been removed. 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.

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

XRLs can be sent over unreliable transports such as UDP or reliable
transports such as TCP. The type of transport that should be used will
be specified when defining the interface. In the case of reliable
transport, the errors above should generally not occur, but in any
event we need general rules about how to handle them should something
fail in an unexpectedly way.

In addition, 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 categorise XRL interfaces along these two axes:
reliable/unreliable and pipelined/non-pilelined.

\subsubsection*{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 timeout 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 if this XRL had previously been received,
this will not cause a further failure.

\subsubsection*{Reliable, Non-pipelined}

If an XRL send failure occurs, the sending application SHOULD
retransmit the XRL.  In an XRL timeout occurs the sending application
SHOULD also retransmit the XRL.  Further requests using this interface
MUST be queued until the XRL has successfully been received.

The interface should be written in such a way that if this XRL had
previously been received, this will not cause a further failure.

An alternative strategy is possible.  If the XRL in question changes
state at the receiving application, the interface may also support a
query mechanism.  If the XRL fails with a timeout, the sending
application may opt not to blindly re-transmit the XRL, but instead
send a query (retransmitted as necessary) to determine whether the
state at the remote system is as it would be if the XRL had been
received.  Only if it the query indicates that the state was not
received would the original XRL be retransmitted.

This alternative is more complicated, and so it should only be
prefered when the consequences of receiving the same XRL twice
outweight the additional complexity.

\subsubsection*{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 and {\em
re-ordering} of requests.  It is up to the application to choose
whether to retransmit XRLs that return XRL send failed or timeout, but
the application must only do so if it is certain that the re-ordering
caused by retransmission will not be a problem.

\subsubsection*{Reliable, Pipelined}

Reliable, pipelined interfaces are the most difficult in which to
handle XRL errors.  Three issues need to be considered:
\begin{itemize}
\item The XRL that failed due to a transport error may be followed by
pipelined XRLs that succeeded.
\item The XRL that failed due to a transport error may be followed by
pipelined XRLs that failed at the application level due to the state
caused by the first failed XRL not being instantiated.
\item If a failed XRL was followed by pipelined XRLs that succeeded,
retransmitting that XRL will cause a re-ordering that might leave the
destination in a different state than it would be if the XRLs had
arrived in order.
\end{itemize}
To avoid all these problems we require that a reliable XRL transport
fail to deliver all subsequent XRLs in the pipeline if a single XRL
fails.  Thus the reliable pipelined interface falls back to a
reliable, non-pipelined interface after a failure.  A subsequent XRL
that succeeds then permits pipelined operation to resume.

\bibliographystyle{plain}
\bibliography{xorp}
\end{document}
