bgp.tex

BCAST Implementation for NS2

an alternative path is now the winner.  As there can be many thousands
of routes in a RibIn, this process can take some time.
\item When a new peering comes up, all the winning routes must be sent
to that peer.  This can also take some time.
\item When the IGP information related to a BGP nexthop changes, all
the routes that specify this nexthop must be re-evaluated to see if
the change affects the choice of route.  In BGP it is fairly common
for a very large number of routes to share the same BGP nexthop, so
this re-evaluation can take some time.
\end{itemize}
The XORP BGP process cannot simply process such events to completion -
in particular it must keep processing XRL requests from other
processes or the IPC mechanism may declare a failure.  In any event,
it is important that a single slow peer cannot cause route forwarding
between other peers to stall.  Thus we process the events above as
``background tasks''.  

In a multithreaded architecture, such tasks might be separate threads,
but the locking issues soon become very complex.  In our single
threaded architecture, there are no complex locking issues, but the
background nature of such tasks needs to be explicitly coded.  We do
this by dividing the background task into small enough segments.  At
completion of such a segment we schedule a zero-second timer to
schedule execution of the next segment, and drop back to the main
event loop.  Execution will then be restarted after pending network
events and expired timers have been processed by the main event loop.
Care must of course be taken to ensure that when execution returns,
the processing of events or other background tasks has not rendered
incorrect the state the background task needed to restart.  However,
as the processing of each background task segment is naturally atomic
in a single-threaded architecture, there are fewer possibilities for
bad interactions.  Even so, the state stored by these background tasks
to enable their correct restart involves some rather complex
algorithms.

\subsection{DeletionTable Class}

When a peering goes down, the routing table stored in the RibIn is
moved to a DeletionTable that is plumbed in directly after the RibIn,
as shown in figure \ref{del_table}.
\begin{figure}[htb]
\centerline{\includegraphics[width=0.7\textwidth]{figs/del_table}}
\vspace{.05in}
\caption{\label{del_table}Dynamic insertion of Deletion Table on
Peering Failure}
\end{figure}
The task of the deletion table is to delete all the routes that were
previously stored in the RibIn, but to do so as a background task
allowing the BGP process to continue to handle new events.

Deletion is scheduled in series of phases.  In a single phase, all the
routes that share a single set of Path Attributes are deleted.  In
this way, if there are alternative routes in a different RibIn that
also share a path attribute list (a fairly common occurrence), then the
chance of preferred route may be batched in such a way that it might be
possible to use a single update message might convey the change to
each neighbor.  At the end of a phase, the DeletionTable schedules
execution of the next deletion phase using a zero-second timer.  This
allows all pending timer or network events to be handled before
deletion resumes.

The DeletionTable must respond to {\tt lookup\_route} requests from
downstream just as a RibIn table would - even though the deletion
table knows the routes it holds will be deleted, it must respond as if
they had not yet been deleted until it has had a chance to send the
relevant {\tt delete\_route} message downstream.  In this way, the
DeletionTable provides a consistent view to the downstream tables - if
they earlier performed a {\tt lookup\_route} and got a specific answer,
then they will still get the same answer unless they have received a
{\tt delete\_route} or {\tt replace\_route} informing them of a
change.

When the last route is deleted from the DeletionTable, the table
unplumbs itself from the BGP plumbing, and deletes itself.

A small complication is added by the possibility that the peering
might come back up before the DeletionTable has finished deleting all
the old routes.  Thus if the DeletionTable receives an {\tt
add\_route} from upstream for a route that in present in the
DeletionTable, then this route would be passed on downstream as a {\tt
replace\_route}, and the route would then immediately be removed from
the DeletionTable.  {\tt add\_route}, {\tt replace\_route} and {\tt
delete\_route} for routes not present in the DeletionTable are simply
passed from parent to child without modification.

Should the peering come up and go down again before all the routes in
the first DeletionTable have been deleted, a second deletion table
would be inserted before the first one.  By virtue of the normal
functioning of the DeletionTable, if there are two such cascaded
DeletionTables, then they will not hold the same route, so this does
not add any additional complication.

\subsection{DumpTable Class}

When a peering comes up, all the currently winning routes from the
other peers must be sent to the new peer.  This process is managed by
an instance of the DumpTable class, which is inserted between the
fanout table and the first table on the output branch to the peer that
came up (see Figure \ref{dump_table}).
\begin{figure}[htb]
\centerline{\includegraphics[width=0.6\textwidth]{figs/dump_table}}
\vspace{.05in}
\caption{\label{dump_table}Dynamic insertion of DumpTable on
a peering coming up.}
\end{figure}

A DumpTable is perhaps the most complex part of the BGP machinery.
While the dump is taking place, it must cope with:
\begin{itemize}
\item New routing information being propagated.
\item Other peers going down and coming back, possibly repeatedly.
\end{itemize}
It must do this without propagating inconsistent information downstream,
such as a {\tt replace\_route} or a {\tt delete\_route} without
sending an {\tt add\_route} first.  It must ensure that all the routes
what passed decision are dumped to the new peer. And it must cope when
the routes just before and just after the most recent route it dumped
are deleted, without losing track of where it is in the dump process.

The process is complex enough to merit description here in detail.

Each DumpTable contains a DumpIterator instance which holds all the
state related to the current state of that particular route dump.  The
DumpIterator contains the following state:
\begin{itemize}
\item A list of the remaining peers to dump, initialized at the start
of the dump.  Peers are removed from this list when the dump of the
routes received from that peer is complete, or when the peer does down
during the dump.  Peers are never added to this list during the dump.
\item A list of the peers that went down before we'd finished dumping
them.  Along with each peer is stored enough state to know how far
we'd got though the route dump from that peer before it went down.
\item The current peer whose routes are being dumped.
\item A trie iterator pointing to the next RibIn trie entry to be dumped
on the current peer (we call this the Route Iterator)
\item The last subnet dumped from the current peer.
\item A flag that indicates whether the Route Iterator is currently
valid.
\item The last GenID seen.  The GenID of the RibIn is incremented each
time the peering comes up.
\end{itemize}
At startup the DumpTable initialized the list of remaining peers in
the DumpIterator to be the set of peers that are currently up.  Then
it iterates through this list dumping all the routes from each RibIn
in turn.

The DumpTable calls {\tt dump\_next\_route} on its parent table, passing the
DumpIterator as a parameter.  The {\tt dump\_next\_route} request is relayed
upstream to the DecisionTable.  DecisionTable relays the request to
the input branch of the first peer listed in the list of remaining
peers, and from there it is relayed back to the relevant RibIn.

To allow routes in the RibIn to be deleted during the route dump
without the Route Iterator becoming invalid, we use a special trie and
trie iterator in RibIn, where the route in the trie will not actually
be deleted until no trie iterator is pointing at it.  This is
implemented using reference counts in the Trie nodes themselves.

{\tt dump\_next\_route} in the RibIn checks the Route Iterator to see
if it points to the end of the Trie.  If the previous call to {\tt
dump\_next\_route} had left the Route Iterator pointing to a node that has
subsequently been deleted, this comparison transparently causes the
Route Iterator to move on to the next non-deleted node, or to the end
of the Trie if there are no subsequent deleted nodes.  This updating
of the Route Iterator is transparent to the user of the iterator.

The route pointed to by the Route Iterator is then propated downstream
from the RibIn to the DumpTable as a {\tt route\_dump} call.  The
DumpTable turns this into an {\tt add\_route} call which it propagates
downstream to the new peer.

At the end of {\tt dump\_next\_route}, the RibIn increments the
RouteIterator ready for next time.  

DumpTable then schedules the next call to {\tt dump\_next\_route} using a
zero-second timer to allow other pending events to be processed.

On returning from the timer, the DumpTable checks to see if any route
changes have been queued upstream in the FanoutTable due to output
flow control.  If so, it processes all these route changes before
dumping the next route.  This is necessary, or the DumpTable will not
be able to tell which changes it needs to propagate downstream because
we've already passed their location in the dump process, and which are
unnecessary because we will get round to dumping them eventually.

In general, a route
change needs to be propagated downstream if:
\begin{itemize}
\item It comes from a peer that is not in our remaining peers list.
\item It comes from the peer currently being dumped, but its route is
before the location of the route in the DumpIterator.
\item It comes from a peer that went down, and its subnet is before the
subnet we had reached while dumping that peer's RibIn when the peer
went down.
\item It comes from a peer that went down, and the RibIn GenID later
than that peers GenID was when it went down.  This would happen
because the peering has since come back up, and is now injecting new
routes.
\end{itemize}

When all the routes in the RibIn of a particular peer have been
dumped, that peer is removed from the remaining peers list in the
DumpIterator, and the next {\tt dump\_next\_route} will be sent to the RibIn
of the next peer in the list.

When there are no peers in the remaining peers list, the dump is
complete.  The DumpTable then unplumbs itself from the plumbing, and
deletes itself.

Note that at any time there may be multiple DumpTables in operation,
each dumping to a different peer.  All the dump state is held in the
DumpIterators, so this does not cause any problem.
\end{document}