bgp.tex

xorp源码hg

%
% $XORP: xorp/docs/bgp/bgp.tex,v 1.24 2007/03/15 00:53:48 pavlin Exp $
%

\documentclass[11pt]{article}

%\usepackage[dvips]{changebar}

\usepackage{subfigure}
\usepackage{fullpage}
\usepackage{setspace}
\usepackage{times}
\usepackage{latexsym}
\usepackage{epsfig}
\usepackage{graphicx}
\usepackage{xspace}
\usepackage{color}
\usepackage{amsmath}
\usepackage{rotating}
\usepackage{moreverb}
\usepackage{listings}
\usepackage{alltt}
\usepackage{stmaryrd}
%\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 BGP Routing Daemon \\
\vspace{1ex}
Version 1.4}
\author{ XORP Project					\\
	 International Computer Science Institute	\\
	 Berkeley, CA 94704, USA			\\
         {\it http://www.xorp.org/}			\\
	 {\it [e-mail]}
}
\date{March 20, 2007}

\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 peer
routers and some of the more specialized stages in the plumbing.
Figure \ref{plumbing} expands on the plumbing to include all the
plumbing stages in the current version of BGP, and broadly groups them
according to whether or not they modify or store routes.

\begin{figure}[htb]
\centerline{\includegraphics[width=1.0\textwidth]{figs/overview}}
\vspace{.05in}
\caption{\label{overview}Overview of BGP process}
\end{figure}

\begin{figure}[htb]
\centerline{\includegraphics[width=1.0\textwidth]{figs/bgp-pipeline}}
\vspace{.05in}
\caption{\label{plumbing}More detail of BGP Plumbing}
\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 fanned out to all the
output branches except the one it arrived on.  The outgoing
PeerHandler then sends the route 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 (August 2006) 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.