rib.tex

xorp源码hg

%
% $XORP: xorp/docs/rib/rib.tex,v 1.24 2007/03/15 00:43:15 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 Routing Information Base (RIB) Process \\
\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 Routing Information
Base (RIB) process.  It is intended to provide a starting point for
software developers wishing to understand or modify this software.

The RIB process takes routing information from multiple routing
protocols, stores these routes, and decides which routes should be
propagated on to the forwarding engine.  The RIB performs the following
tasks:

\begin{itemize}

  \item Stores routes provided by the routing protocols running on a XORP
  router.

  \item If more than one routing protocol provides a route for the same
  subnet, the RIB decides which route will be used.

  \item The winning unicast routes are propagated to the Forwarding
  Engine Abstraction (FEA) process and hence on to the forwarding
  engine. Multicast routes are not propagated to the FEA - they are only
  used to provide topology information to multicast routing protocols.

  \item Protocols such as BGP may supply to the RIB routes that have a
  nexthop that is not an immediate neighbor.  Such nexthops are resolved
  by the RIB so as to provide a route with an immediate neighbor to the
  FEA.

  \item Protocols such as BGP need to know routing metric and
  reachability information to nexthops that are not immediate neighbors.
  The RIB provides a way to register interest in such routing
  information, in such a way that the routing protocol will be notified
  if a change occurs.

  \item Protocols such as RIB need to announce routes to the neighbors
  (\eg routes from directly connected subnets, static routes, etc).
  The RIB provides the mechanism for redistributing the routes from
  a specific table to parties that have registered interest in that
  table.

\end{itemize}

By default, the RIB process holds four separate RIBs:

\begin{itemize}
  \item Unicast IPv4 RIB
  \item Unicast IPv6 RIB
  \item Multicast IPv4 RIB
  \item Multicast IPv6 RIB
\end{itemize}

C++ templates are used to build specialized IPv4 and IPv6 versions
from the same code.  Routing protocols such as Multiprotocol BGP are
capable of supplying routes that are multicast-only, and these would
be stored in the multicast RIBs.  The unicast and multicast RIBs
primarily differ in that only unicast routes are propagated to the
forwarding engine.

Note that we do not currently support multiple RIBs for other
purposes, such as VPN support, but the RIB architecture will permit
such extensions.

\section{Structure of a RIB}
The RIB process may hold multiple RIBs.  Figure~\ref{fig:rib_overview} gives
an overview of the structure of a unicast RIB.

\begin{figure}[htb]
  \centerline{\psfig{figure=figs/overview.ps,width=1.0\textwidth}}
  \vspace{.05in}
  \caption{\label{fig:rib_overview}Overview of a RIB}
\end{figure}

In general, routing protocols supply routes to the OriginTables.
These routes then flow though the tree structure from left to right,
until they reach the RedistTable, where they are propagated to the
Forwarding Engine Abstraction (FEA) process.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Plumbing}

The RIB plumbing code dynamically creates and maintains the tree of
tables as shown in Figure~\ref{fig:rib_overview}.  When a new routing protocol
registers with the RIB, a new OriginTable will be created, and a
MergeTable or an ExtIntTable will be created to plumb that OriginTable
into the RIB tree at an appropriate location.  Similarly, if a routing
protocol deregisters with the RIB, the relevant OriginTable and
additional tables will be deleted and the RIB tree simplified again.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{OriginTable}

The OriginTable accepts {\tt route\_add} requests from a single routing
protocol, stores the route, and propagates it downstream.  It also
answers {\tt lookup\_route} requests from downstream from the routes it
has stored.

An OriginTable for the ``connected'' protocol always exists, to handle
routes for directly connected interfaces.  It gets its information
via the VifManager from the Forwarding Engine Abstraction (FEA)
process.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{MergeTable}

A MergeTable has two upstream (parent) tables and one downstream
(child) table.

Multiple OriginTables may hold different routes for the same subnet.
Thus, when an {\tt add\_route} request reaches a MergeTable from one
parent, the MergeTable performs a route lookup on the other parent to
see if the route already exists.  If it does, then the new route is
only propagated if it is better than the existing route, where
``better'' is determined based on the relative administrative distance
of the routes.

Similarly, if a {\tt delete\_route} request reaches a MergeTable, it
performs a route lookup on the other parent table.  If the route being
deleted was better than the alternative, then the delete is propagated
downstream followed by an {\tt add\_route} for the alternative.  If the
route being deleted was worse than the alternative, then the deletion
needs to be propagated no further.

When a MergeTable receives a {\tt lookup\_route} request from
downstream, it sends the request on to both parents.  The better of
the two answers is sent in response.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{ExtIntTable}

ExtIntTable functions very similarly to the MergeTable, but there is
an asymmetry between the parents.  On the Internal side, the
originating routing protocols always supply routes that have an
immediate neighbor as the nexthop.  On the External side, the
originating routing protocols may supply routes that have an immediate
neighbor as the nexthop, but they may also supply routes where the
nexthop is multiple IP hops away.  

When an {\tt add\_route} request arrives from the external parent, the
ExtIntTable does the same comparisons that happen with a MergeTable.
However, it also checks to see if the nexthop is an immediate
neighbor.  If it is not, then the ExtIntTable attempts to find a route
that indicates which immediate neighbor to use to reach the nexthop,
and the nexthop in the route that is propagated downstream will be
that of this immediate neighbor.  If no route exists to the nexthop,
the route will not be propagated downstream, but will be stored in a
table of unresolved routes in case a route that arrives later can
cause it to resolve.

Each RIB only contains a single ExtIntTable.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{RegisterTable}

RegisterTable takes registrations from routing protocols for routing
information related to specific destinations, answers the request, and
stores the registration.  If the routing information in the
answer changes, it will asynchronously notify the routing protocol of
the change.  The precise interface is described in section \ref{reg},
but the general idea is illustrated by this example:

Suppose the RIB contains routes for 1.0.0.0/16 and 1.0.2.0/24.  Now a
routing protocol expresses an interest in address 1.0.1.1.  This
matches against the routing entry for 1.0.0.0/16, so the answer contains
1.0.0.0/16 and the related nexthop and metric.

However we would like the routing protocol to be able to use the
answer if it also cares about other addresses, such as 1.0.0.1 or
1.0.2.1.  However, while the former matches against 1.0.0.0/16, the
latter matches against 1.0.2.0/24.  Thus if the RIB only returns
1.0.0.0/16, the routing protocol cannot tell whether it can use this
information for any other address than the one it asked about.

To rectify this, the RIB returns not only the answer (1.0.0.0/16, plus
metric and nexthop), but also the subset of this prefix for which the
answer is known to be good.  In this case, the answer is good for
1.0.0.0 to 1.0.1.255, which is returned as a subnet: 1.0.0.0/23.
Any address that the routing protocol cares about that falls within
1.0.0.0/23 does not require additional communication with the RIB.

The RegisterTable keeps track of which information it gave which
routing protocol, so that if this information becomes invalid, the
routing protocol can be informed.  For example, if a new route appears
for 1.0.1.0/24, then this would cause the registration covering
1.0.0.0/23 to be invalidated because 1.0.1.0/24 is more specific than
1.0.0.0/16 and overlaps the range 1.0.0.0/23 of the registration.

Each RIB only contains a single RegisterTable.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{RedistTable}

The purpose of a RedistTable is to redistribute the routes from any RIB
table to all external parties that have registered interest at that
table. Thus, a RedistTable can be used for the redistribution of the
configured (and possibly filtered) routes from one routing protocol to
another.  For example, routes from within an AS might be propagated from
OSPF to BGP for external advertisement.

A RedistTable can by dynamically plumbed into the tree of tables at any
point, and there may be many RedistTables in each RIB. Typically,
RedistTables are inserted immediately after an OriginTable, and at the
end of the tree of tables.

ResistTables are used also for redistributing the final routes to the
FEA and other interested processes. Both the unicast and multicast RIBs
have a RedistTable at the end (see Figure~\ref{fig:rib_overview}).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{XRL Interface}