fea.tex

BCAST Implementation for NS2

%
% $XORP: xorp/docs/fea/fea.tex,v 1.9 2003/11/06 23:38:10 hodson Exp $
%

\documentclass[11pt]{article}

%\usepackage[dvips]{changebar}

\usepackage{subfigure}
\usepackage{fullpage}
\usepackage{setspace}
\usepackage{times}
\usepackage{latexsym}
\usepackage{psfig}
\usepackage{graphicx}
\usepackage{xspace}
\usepackage{color}
\usepackage{amsmath}
%\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]{}

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

% \pagestyle{empty}

\begin{document}

\title{XORP Forwarding Engine Abstraction \\
\vspace{1ex}
Version 0.5}
\author{ XORP Project					\\
	 International Computer Science Institute	\\
	 Berkeley, CA 94704, USA			\\
	 {\it [e-mail]}
}
\date{November 6, 2003}

\maketitle

\thispagestyle{empty}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Introduction}
\label{sec:introduction}

The role of the Forwarding Engine Abstraction (FEA) in XORP is to
provide a uniform interface to the underlying forwarding engine.  It
shields XORP processes from concerns over variations between
platforms.  As a result, XORP processes need not be concerned whether
the router is comprised of a single machine, or cluster of machines;
or whether the network interfaces are simple, like a PCI Ethernet
adapter, or are smart and have processing resources, like an Intel IXP
cards.

The FEA performs three distinct roles: \emph{interface management},
\emph{forwarding table management}, and \emph{interface specific
packet I/O}.  Those are described briefly in
Section~\ref{sec:introduction:interface_management},
Section~\ref{sec:introduction:forwarding_table_management},
and Section~\ref{sec:introduction:interface_specific_packet_io}
respectively.
Section~\ref{sec:design_and_implementation} presents
the design and implementation of the FEA components.
FEA status summary is in Section~\ref{sec:status}.

In a standard XORP system, the Multicast Forwarding Engine Abstraction
(MFEA) is part of the FEA.  The MFEA is conceptually distinct from
FEA, but in practice requires access to similar data as the FEA.
Combining the MFEA with the FEA reduces the load on system.  For
information about the MFEA architecture, see \cite{xorp:mfea}.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Interface Management}
\label{sec:introduction:interface_management}

In the normal course of interaction, the RouterManager process is the
principal source of interface configuration requests to the FEA.  The
RouterManager constructs the interface configuration from the router
configuration files and the input it receives at the command line.
The type of requests the RouterManager sends to the FEA are to enable
interfaces, create virtual interfaces, set interface MTU's, and so
forth.  The FEA interprets and executes these requests in a manner
appropriate for the underlying forwarding plane.

Processes can register with the FEA to be notified of changes in
interface configuration.  The registered processes are notified of
changes, and may query the FEA on the receipt of an update notification
to determine the change that occurred.  These notifications are
primarily of interest to routing protocols since these need to know
what the state of each interface is at a given time.

\begin{figure}[htbp]
  \begin{center}
    \includegraphics[width=0.80\textwidth]{figs/ifmgmt}
    \caption{FEA Interface Management interaction with other XORP processes}
    \label{fig:ifmgmt}
  \end{center}
\end{figure}

Both of the above interactions are depicted in Figure~\ref{fig:ifmgmt}.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Forwarding Table Management}
\label{sec:introduction:forwarding_table_management}

The FEA primarily receives forwarding table configuration information from the
RIB process.  The RIB arbitrates between the routes proposed by the
different routing processes, and propagates the results into the FEA's
forwarding table interface.  The FEA accepts requests to insert and
remove routing entries and propagates the necessary changes into the
forwarding plane.  The FEA also supports queries on the current
contents of the forwarding table.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Interface Specific Packet I/O}
\label{sec:introduction:interface_specific_packet_io}

Routing protocols, such as OSPF, need to be able to send and receive
packets on specific interfaces in the forwarding plane in order to
exchange routing information and to determine the liveness of
connected paths.  Since the forwarding plane may be distributed across
multiple machines, these routing protocols delegate the I/O operations
on these packets to the FEA.  The FEA supports sending and receiving
raw and UDP~\footnote{Currently (November 2003), UDP support
is not present.}  packets on specific interfaces.  The transmission of
packets through the FEA is straightforward, the routing process simply
hands the FEA a packet and indicates which interface it should be sent
on.  The reception of packets is handled through a register-notify
interface where the routing process registers which types of packets
on which interfaces it is interested.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Design and Implementation}
\label{sec:design_and_implementation}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Overview}

The FEA fulfills three discrete roles: Interface Management, Forwarding
Table Management, and Interface Specific Packet I/O.  The Interface
Management and Forwarding Table Management roles follow a similar
design pattern since both relate to the setting and getting of
configuration state.  The Interface Specific Packet I/O has little in
common with the other two roles.  

The Interface Management and Forwarding Table Management roles use
transactions for setting configuration state.  The transactions are a
collection of grouped operations that are queued until committed or
aborted.  Transactions provide atomic updates to the forwarding plane,
which has the virtue of ensuring a consistent state at any particular
instant of time.  In addition, forwarding plane updates may incur per
update costs, and grouping operations may help to reduce
these. Queries of the configuration state happen on the immediate
state, and are independent of any transactions that are in progress.

The FEA, as with other XORP processes, uses the XRL mechanism for
inter-process communication and each role of the FEA is represented by
a distinct XRL interface.  The Interface Management and Interface
Specific Packet I/O roles support the notion of clients that notified
when event occur and client processes are expected to implement known
interfaces.  The FEA XRL and FEA XRL client interfaces are shown in
Table~\ref{tbl:xifs}.

\begin{table}[h]
\begin{center}
\begin{tabular}{|l|l|l|}\hline
Role & XRL Interface file & Client XRL Interface\\ \hline\hline
Interface Management 		& fea\_ifmgr.xif	& fea\_ifmgr\_client.xif\\
Forwarding Table Management	& fti.xif 		& \\
Interface Specific Packet I/O	& fea\_rawpkt.xif 	& fea\_rawpkt\_client.xif\\ \hline
\end{tabular}
\caption{FEA XRL Interfaces (defined in {\tt \$XORP/xrl/target/fea.tgt})}
\label{tbl:xifs}
\end{center}
\end{table}

The XRL handling code is found in {\tt
\$XORP/fea/xrl\_target.\{hh,cc\}}.  Each XRL interface is handled by
an XRL-aware helper class.  The helper class understands the semantics
of the implementation, and maps errors and responses to the appropriate
XRL forms.  The helper classes and their relations to the interfaces
are depicted in Figure~\ref{fig:xrl_ifs}.

\clearpage
\begin{figure}[htbp]
  \begin{center}
    \includegraphics[angle=90,height=0.90\textheight]{figs/xrl_ifs}
    \caption{XRL Interfaces in relation to FEA classes}
    \label{fig:xrl_ifs}
  \end{center}
\end{figure}
\clearpage


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Interface Management}

To succinctly explain the interface management classes and how they
interact we first describe the representation of interface
configuration state.  Interface configuration state is held within
{\tt IfTree} class.  The {\tt IfTree} structure is used and