bgp.tex

BCAST Implementation for NS2

\documentclass[11pt]{article}
\usepackage{graphicx}
\usepackage{times}
\textwidth 6.5in
\topmargin 0.0in
\textheight 8.5in
\headheight 0in
\headsep 0in
\oddsidemargin 0in

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

%\twocolumn
\begin{document}
\maketitle                            
\section{Introduction}
This document provides an overview of the XORP BGP Routing Daemon.  It
is intended to provide a starting point for software developers
wishing to modify this software.

A router running BGP takes routes from peer routers, filters them,
decides which of the alternative routes is the best, and passes the
winner on to the other peers, possibly applying filters before passing
the route on.

Our chosen architecture for our BGP implementation emphasizes
extensibility and the separable testing of subsystems, rather than
high performance or minimal memory footprint.  However we believe that
the performance and memory usage will be acceptable, even for backbone
router implementations.

We implement BGP as a connected pipeline of ``routing tables'', each
performing a specialized task.  Figure \ref{overview} gives the
general overview of classes involved in the core of the BGP process,
but excludes the classes involved in handling peerings with peers.
\begin{figure}[htb]
\centerline{\includegraphics[width=1.0\textwidth]{figs/overview}}
\vspace{.05in}
\caption{\label{overview}Overview of BGP process}
\end{figure}
Route information flows from left to right in this figure.  Typically
an Update or Withdraw message arrives from a BGP peer, is split up
into separate {\tt add\_route} or {\tt delete\_route} commands by the PeerHandler,
and then the update flows through the tables towards the
DecisionTable.  If the route is better than the best alternative, then
it passes through the DecisionTable, and is then fanned out to all the
output branches except the one it arrived un.  The outgoing
PeerHandler then sends the route on to the corresponding BGP peer.

There is one input branch and one corresponding output branch for each
BGP peer, plus one branch that handles routes sent to BGP from the
XORP RIB, and sends BGP routes to the XORP RIB and hence on to the
forwarding engine.  The general structure of the RIB branch is
identical to that of a peer-related branch, but a special version of
the PeerHandler is used.

\section{Major BGP Classes}
In this section we discuss each of the classes from Figure \ref{overview} in
turn, before discussing how each BGP peer is handled.  Most of these
classes are implemented using C++ templates for the address family, so
they are capable of handling IPv4 and IPv6 in an identical manner.
\subsection{PeerHandler Class}
The PeerHandler acts as the interface between the BGP Peer class
(which handles BGP peering connections) and all the RouteTables that
comprise the BGP plumbing.  A single PeerHandler instance receives 
BGP Update messages coming from the BGP peer and constructs new BGP
Update messages to send to that peer.

A BGP Update Message consists of three parts:
\begin{itemize}
\item A list of withdrawn route subnets (route prefixes).
\item Path Attribute information for announced routes.
\item A list of subnets (route prefixes) that are being announced.
The Path Attribute information applies to all these subnets.
\end{itemize}

The PeerHandler splits an incoming update message up, and constructs a
series of messages (InternalMessage class) to send to the plumbing.

Each of the withdrawn route subnets is passed to the plumbing using a
separate {\tt delete\_route} call.

Each of the announced route subnets is passed to the plumbing using a
separate {\tt add\_route} call, which includes all the Path Attribute
information.

On the output side, the PeerHandler receives a series of {\tt add\_route},
{\tt delete\_route}, or \\
{\tt replace\_route} calls.  Each batch of calls is for
routes that share the same path attribute list.  The PeerHandler then
constructs an Update Message from each batch, and passes it on to the
classes that handle the peering for transmission to the relevant BGP
peer router. 

In some cases the PeerHandler can receive routes from BGP faster than
the connection to the relevant peer can handle them.  The PeerHandler
can communicate this information back upstream to regulate the flow of
changes to a rate that can be accommodated.  The actual queuing then
happens upstream in the FanoutTable.

Because of the way BGP encodes IPv6 routes, the PeerHandler class
handles IPv4 and IPv6 routing information differently.

\subsection{RibInTable Class}

The RibInTable class is responsible for receiving routes from the
PeerHandler and storing them.  These are the raw routes, unfiltered
and unmodified except for syntactic correctness, as received and
decoded from the BGP Peering session.

Because BGP does not indicate in an Update message whether a route is
new or merely replaces an existing route, all routes are checked to
see if they are already stored in the RibIn.  If so, the {\tt add\_route} is
propagated downstream as a {\tt replace\_route}, otherwise it is propagated
as an {\tt add\_route}.

The RibIn serves several additional purposes:
\begin{itemize}
\item It can answer {\tt lookup\_route} requests from downstream.
\item When a new peer comes up, a route dump is initiated so that the
new peer learns all the feasible routes that we know.  The RibIn can
perform this dump as part of a background task, so as to allow further
updates while the dump is taking place.
\item When the peer associated with the RibIn goes down, a process to
delete all the routes learned from this peer is started.  This is done
by transferring the RibIn's entire routing table to a new RouteTable
called a DeletionTable that is plumbed in directly after the RibIn.
The DeletionTable handles the deletion of the routes as a background
task, leaving the RibIn ready to cope immediately if the peer comes
back up again.
\item When the routing information in the XORP RIB changes, the change
of IGP metric can change which routes should win the decision process.
The RibIn can be told that the routing information associated with the
indirect nexthop in a BGP route has changed, and it can initiate a
background task that re-sends all the relevant routes downstream as
{\tt replace\_route} messages, so that the DecisionTable can make its choice
again.
\end{itemize}

The RibIn does not do significant sanity checking on its inputs - it
is the responsibility of the receive code in the Peer classes to check
that received update messages are syntactically and semantically
valid.

The current (Mar 2003) version of XORP stores all routes in the RibIn,
irrespective of whether or not they will fail to pass a downstream
filter.  However, the RibIn has enough information (from the values
returned by the {\tt add\_route}, {\tt delete\_route} and {\tt
replace\_route} calls it makes downstream) to be able to store only
those routes that will not be filtered.

\subsection{FilterTable Class}

The FilterTable class has one parent (upstream) RouteTable and one
child (downstream) RouteTable.  It acts as a general purpose
filter-bank, passing, modifying, or dropping routing information that
travels from parent to child.

A FilterTable can hold many filters.  Current filters include:
\begin{itemize}
\item {\bf SimpleASFilter:}  Drops routes that contain the configured
AS in their AS Path.
\item {\bf ASPrependFilter:} Prepends the configured AS number to the
AS Path of all
routes that pass through the filter.
\item {\bf NexthopRewriteFilter:} Changes the NextHop attribute of all
routes that pass through the filter to the specified value.
\item {\bf IBGPLoopFilter:} Drops all routes that we heard through
IBGP.  This is primarily useful as an outbound filter to an IBGP peer.
\item {\bf LocalPrefInsertionFilter:} Inserts the configured value as
the BGP Local Preference attribute in all routes that pass through the
filter.  Typically used on input from an EBGP peer, before
route-specific filters.
\item {\bf LocalPrefRemovalFilter:} Removes the BGP Local Preference
attribute from all routes that pass through the filter.  Typically
used on output to an EBGP peer.
\item {\bf MEDInsertionFilter:} Adds a Multi-exit Descriminator
attribute based on the routes IGP metric to each route that passes
through the filter.  Typically used on output to an EBGP peer.  Note
that the MED to be inserted will have been added to the route by the
DecisionTable, so MEDInsertionFilter cannot be used as an input-branch
filter.
\item {\bf MEDRemovalFilter:} Removes the  Multi-exit Descriminator
attribute from all routes that pass through the filter.  Typically
used just before a MEDInsertionFilter to remove the MED received from
the previous AS.
\end{itemize}
Note that filters are not just for operator configured filtering -
they comprise part of the basic BGP processing mechanism.

Typically a FilterTable will receive an InternalMessage from its
parent containing a subnet route.  All the configured filters will be
applied in order to the route.  One of three things may happen:
\begin{itemize}
\item The route may be dropped by a filter.
\item The route may pass through all filters unchanged.
\item One or more filters may modify the route.  This is done by
creating a new copy of the route.
\end{itemize}
In the last case, the modified route will have the Changed flag set
before it is propagated downstream.  This flag indicates that no-one
upstream is storing a persistent copy of this route, so the downstream
tables are responsible for either storing the route or freeing the
memory it uses.

Filter implementors should be careful to note that if the route
received as input to a filter is already modified, and their filter
then drops the route or creates a modified copy of the route, then the