bgp.tex

BCAST Implementation for NS2

old route MUST be freed because no-one else can do so.  If the input
route is not modified, the filter MUST NOT free the route because it
is stored elsewhere.

\subsection{CacheTable Class}

The CacheTable class has one parent RouteTable and one child
RouteTable.  Its purpose is to ensure that routes changed by preceding
filter-banks are actually stored somewhere.  Primarily it is an
optimization to prevent the filters from having to be applied every
time {\tt lookup\_route} is called, but it also simplifies memory management
because downstream tables no longer need to be concerned with whether
a route needs to be freed or not. 

The CacheTable takes as input InternalMessages from its parent, and
passes them through downstream to its child.  If the route in the
message does not have the Changed flag set, then the CacheTable is a
no-op.  If the route in the message has the Changed flag set, then the
CacheTable will store the route (or delete it from storage in the case
of {\tt delete\_route}).  Thus all InputMessages sent downstream have the
Changed flag cleared.

A CacheTable in the outgoing branch is flushed (all stored routes
deleted) when the peering corresponding to the relevant plumbing
branch down.  This is because when the peering comes back up, the
outgoing branch should restart with no stored state.  The incoming
branch CacheTable is not explicitly flushed, because the routes will
be removed as the DeletionTable gets round to deleting them.
Prematurely flushing the input branch CacheTables would potentially
result in the DecisionTable seeing inconsistent inputs.

Note that assertion failures in the CacheTable usually indicate that
the code upstream is incorrectly propagating changes (for example
either a delete with no add, two deletes, or two adds).

\subsection{NhLookupTable Class}

The BGP decision process implemented in DecisionTable is relatively
complex, and takes into account many possible factors including ``IGP
distance''.  IGP distance is the IGP routing metric for the route to
reach the BGP NextHop (which is often a number of IP hops away in the
case of IBGP).  Also of interest is whether the BGP NextHop is
actually reachable according to the IGP protocols.  Because of the
multi-process architecture of XORP, BGP does not know the IGP distance
or whether the nexthop is reachable.  To find out this information,
BGP must query the RIB, and this is done by the NextHopResolver class
instance.  If DecisionTable had to perform this lookup, it would
become very complex because it would have to handle suspending the
decision process while waiting for results from the RIB.  A
multi-threaded implementation would solve this problem, but would
cause other issues.

To solve these problems we insert an NhLookupTable upstream of the
DecisionTable.  NhLookupTable queues any updates with NextHop
information that the NextHopResolver does not know about, pending the
response from the RIB process.  Thus by the time an update reaches the
DecisionTable, the NextHopResolver already has access to the IGP
information related to the BGP NextHop.

A complication comes with {\tt lookup\_route}:
\begin{itemize}
\item if the lookup matches an {\tt add\_route} in the NhLookupTable queue,
the NhLookupTable must return ``lookup unsuccessful''.
\item if the lookup matches a
{\tt replace\_route} entry in the NhLookupTable's queue, the old
answer must be given.
\end{itemize}
In general, the behaviour should be as if the queued updates had not
yet been received from the relevant peer.  Note that the time for the
RIB to respond should normally be very small compared to the usual
delays for propagating Update messages between peers.

\subsection{DecisionTable Class}

The DecisionTable is the core of the BGP process.  It takes route
changes from the input branches, and decides whether those changes are
better or worse than the routes it has already seen.

When DecisionTable receives an {\tt add\_route} from one input branch,
it queries the other peers input branches using {\tt lookup\_route}.
\begin{itemize}
\item If none of the other branches returns an answer, then the route is a
new one, and can be passed on downstream so long as the BGP NextHop is
resolvable.  
\item If one or more of the other branches returns an
answer, one of these answers will have been the previous winner.  The
new route is compared against the previous winner - if it is better
then a {\tt replace\_route} message is propagated downstream.  If it
is worse, then no further action is taken.
\end{itemize}

When DecisionTable receives a {\tt delete\_route} from one input
branch, it queries the other peers' input branches in the same way:
\begin{itemize}
\item If none of the other branches returns an answer, the the {\tt
delete\_route} can be passed on downstream so long as the BGP NextHop
was previously resolvable.
\item If one or more of the other branches returns an
answer, one of these answers will be the new winner.  The routes are
compared, and a {\tt replace\_route} will be sent downstream.
\end{itemize}

The processing for {\tt replace\_route} is similar to that for {\tt
delete\_route} followed by {\tt add\_route}, except that only a single
replace (or delete in the case where the new nexthop is unreachable
and there are no alternatives) will be sent downstream.

\subsection{NextHopResolver Class}

Unlike most of the previous classes, NextHopResolver is not a
RouteTable sub-class.  A BGP implementation has a single NextHopResolver
instance per address family.  The NextHopResolver takes requests to
resolve a BGP NextHop address and attempts to resolve the address to
that of the immediate neighbor router that would be used to forward
packets to the NextHop address.

When it receives an address to resolve, the NextHopResolver first
checks its own routing table.  If the nexthop address can be resolved
there, then the answer can be returned immediately.  Alternatively, if
its own routing table indicates that the address definitely cannot be
resolved, then a negative response can be given immediately.
Otherwise it needs to contact the XORP RIB using XRLs to answer the
question.  

In this way, the NextHopResolver obtains a copy of the relevant subset
of the RIBs database related to the NextHops given by BGP.  The RIB
will also keep track of the subset that it has told BGP about.  If
this information changes in any way BGP will be informed by the RIB,
either directly of the change or that some information is no longer
correct and BGP must query again.

The information held by the NextHopResolver is reference-counted so
that it can be removed when it is no longer relevant.  If the
information contained changes, a notification of the change will be
passed to the DecisionTable, which will propagate the notification
back upstream to the RibIn tables.

\subsection{FanoutTable Class}

The principle task of the FanoutTable is to distribute route changes
that passed the DecisionTable, and therefore are real changes not just
possible changes.  FanoutTable passes a change to all the output
branches except the one where the change originated.  In the case of
{\tt add\_route} or {\tt delete\_route}, this is simple but a {\tt
replace\_route} may contain an old route and a new route that
originate from different peers, so it may be propagated as an {\tt
add\_route} to the peer where the old route originated, as a {\tt
delete\_route} to the peer where the new route originated, and as a
{\tt replace\_route} to all the other peers.

The secondary task of the FanoutTable is to serve as a queuing point
for changes when the BGP peers are not capable of keeping up with
updates at the rate we are propagating them.  The advantage of queuing
updates in the FanoutTable as opposed to in the RibOut or PeerHandler
is that only one copy of the change needs to be kept, no matter how
many peers are not keeping up.  This is particularly important in the
case where the peer from which we heard most of our routes goes down,
and a large number of deletions occur in a short period of time.
These deletions need to go to all the remaining peers, and it is
likely that we can generate them faster than TCP can transfer them to
the peer.

Thus there is a single update queue in the FanoutTable, and a separate
pointer into this queue is maintained for each outgoing branch (and
hence each peer).  If a output branch indicates it is busy, the
FanoutTable will stop propagating changes to it, and instead queue the
changes.  Only when a change has been propagated to all the intended
peers will it be removed from the queue.  

\subsection{RibOutTable Class}

The purpose of the RibOutTable is to communicate changes to the
outgoing PeerHandler and hence on to the relevant BGP peer.  The
RibOutTable class accumulates changes (add, delete or replace) in a
queue, and waits for a flush request.  The reason for the queue is
that the incoming PeerHandler split up a single incoming Update message
into many changes, each with the same Path Attributes.  On output, we
want to accumulate these changes again, so that we can send them on to
our peers in a single Update message.  Thus, after the incoming
PeerHandler has sent the last change to the RibIn, it sends a flush
message through.  When this reaches the RibOut, it is the signal to
take all the changes that have been queued, and build one or more
Update messages from them.  Of course the nature of the decision
process and filters mean that changes that arrived together do not
always result in outgoing changes that share the same Path
Attributes.  Thus multiple passes over the RibOut queue are required,
each accumulating changes that share the same Path Attributes so that
they can be sent on in the same Update message.

In principle, the RibOut could also store pointers to the routing
information that was passed on to the peer so that Route Refresh
(RFC 2918) could be handled efficiently.  In our current implementation
we do not do this - the RibOut maintains no record of the routes
passed to the peer.

\subsection{RibIpcHandler Class}

The RibIpcHandler class is a subclass of PeerHandler, with basically
the same interface as far as communication with the RibIn and RibOut
are concerned. However, instead of communicating with BGP peers, the
RibIpcHandler communicates routes to and from the XORP RIB.  Routes
are received from the RIB if the RIB has been configured to
redistribute routes to BGP.  In addition, all routes we pass to other
peers are also communicated to the XORP RIB, and hence on to the
forwarding engine, so that we can forward packets based on the routing
information.

\section{Background Tasks}

The XORP BGP implementation, like all XORP processes, is
single-threaded.  However, certain simple events can cause BGP to
perform a great deal of work.  For example:
\begin{itemize}
\item When a peering goes down, all the routes in the RibIn associated
with that peer must be deleted, which either results in Withdraws
being sent to all remaining peers, or Updates being sent to indicate