pim_arch.tex

xorp源码hg

unit per PimNode. The main purpose of the PimBsr is to run the Bootstrap
mechanism, and to update accordingly the RpTable with the current RP-Set.

The data contained in PimBsr is organized as described below.
PimBsr keeps three lists of BsrZone entries: one list for the active BSR
zones, a second list that contains information about expiring Candidate-RPs for
group prefixes that the lastest Bootstrap message did not contain information
about, and a third list for the locally configured Cand-BSR zones and/or
Cand-RP information. On startup, the active and expire BSR zone lists are
empty. If the node is configured as a Candidate-BSR and/or a Candidate-RP,
this information will be added to the third list; otherwise that list is 
also empty.

Each scope zone is identified by a scope zone ID, and a flag.
The flag, if true, indicates that this is scoped zone, otherwise the
zone is non-scoped. The scope zone ID is the network prefix address that
corresponds to that zone. By definition, scoped zones cannot overlap,
therefore it is not permitted to configure the PimBsr with overlapping
scoped zones and/or to accept Bootstrap messages with scoped zones that
overlap. If the zone is non-scoped, then the scope zone ID is set to the
multicast base prefix address (\ie 224.0.0.0/4 for IPv4 or FF00::/8 for
IPv6).

Each BsrZone contains information about the current BSR for that zone,
and a list of BsrGroupPrefix entries for that zone. Each BsrGroupPrefix
corresponds to a multicast group prefix within that zone that has
Candidate-RPs, and contains the list of BsrRp entries for each
Candidate-RP for that prefix.

All information from the Bootstrap and Candidate-RP messages is kept in
the above data structures. Further, those structures are used to keep
various timers such as to timeout Candidate RPs or to timeout the current BSR.
If the RP-Set is changed after receiving a Bootstrap message or after a
timeout of an Candidate-RP, then the RpTable is updated accordingly.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{RpTable Description}

RpTable is the table that contains the current RP-Set. There is one
table per PimNode. This table is updated by PimBsr if the RP-Set is
propagated through the Bootstrap mechanism, or by PimConfig if the
RP-Set is configured manually.

RpTable contains a list of all RPs with one PimRp entry per RP per
multicast group prefix. To compute the RP for a given group,
we just scan the whole list to find the RP.
Typically, the list of RPs would be relatively short, therefore for
simplicity we scan the whole list. If the overhead becomes too large,
then the scan can be optimized by grouping the Candidate-RPs
for each group prefix, and by considering only the Candidate-RPs with
the highest priority.

If the RP-Set is modified, then all affected PimMre and PimMfc entries
must be updated accordingly. For this reason, each PimRp entry contains
lists of the PimMre and PimMfc entries that map to that RP. If the RP
is removed, then each of the entries on those lists is re-mapped to the
new RP for its group.
This is achieved by scheduling a PimMreTask by the PimMrt,
that performs the appropriate dependency actions for each entry.

The RpTable may contain one special PimRp entry with an RP address of
all-zeroes (\ie \verb=IPvX::ZERO()=). This entry is used to keep the
lists of all PimMre and
PimMfc entries that have no RP yet. If a new RP is added to the RpTable,
then all entries that have no RP yet are processed to find if some
of them may map to this new RP. Those who do map to the new RP are moved to
the appropriate list for that RP.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{PimMribTable Description}

PimMribTable is the table with the MRIB information. The MRIB is used
to compute the Reverse-Path Forwarding information toward the RPs
(needed by the (*,*,RP), (*,G) and (S,G,rpt) state), and toward
each active multicast sender (needed by the (S,G) state). This
information contains the next-hop router address and the interface
toward that router, the routing metric and the metric preference:

{\small
\begin{verbatim}
// Reverse-Path Forwarding information (MRIB payload entry)
class Mrib {
    ...
    IPvXNet     _dest_prefix;          // The destination prefix address
    IPvX        _next_hop_router_addr; // The address of the next-hop router
    uint32_t    _next_hop_vif_index;   // The vif index to the next-hop router
    uint32_t    _metric_preference;    // The metric preference to the
                                       // destination
    uint32_t    _metric;               // The metric to the destination
};
\end{verbatim}
} % \small


The MRIB information is obtained from the RIB
module; if the RIB changes, the
PimMribTable is updated as well. Examples when the MRIB information
may change are: the unicast routing changes the next-hop router address
toward a destination, local configuration changes some of the routing
preference metrics, or local interface configuration changes the virtual
interface and/or the next-hop router toward a destination.

An update to the PimMribTable may affect a number of PimMre and PimMfc
entries in the PimMrt table. The update of the affected entries is
handled by the dependency-tracking and time-slice processing mechanism
implemented by the PimMrt table. Note that we do not need to link all
PimMre and PimMfc entries into lists of entries that depend on a
particular entry in the PimMribTable. The reason is because the
dependency is implied by the network prefix address covered by an entry
in the PimMribTable, that overlaps the RP or source address of a given
PimMre or PimMfc entry.

%%%%%%%%%%%%%%%%%%%%%%
\subsubsection{MRIB Changes Update}

In general, there are two mechanisms to inform the PIM-SM module about
MRIB changes:

\begin{itemize}
  \item \emph{Filtering at the PIM-SM module:}
  Whenever there are any changes about the MRIB information kept inside
  the RIB module, the RIB module informs the PIM-SM module
  about the changes. Then the PIM-SM module processes those changes to
  find whether they would affect in any way the current multicast
  routing.

  \item \emph{Filtering at the RIB module:}
  The PIM-SM module ``registers'' in advance with the RIB module about
  the particular destination addresses/prefixes it is interested at, and
  only if the MRIB information about any of those registered destinations
  is changed, the RIB module informs the PIM-SM module about the change.

\end{itemize}

The basic difference between the above two methods is where we move the
complexity about the MRIB changes: at the RIB side, or the PIM-SM side.
Some other differences are:

\begin{itemize}
  
  \item If we perform filtering at the PIM-SM module, and if the unicast
  routing is changing quite rapidly, and if most of those changes do not
  affect the PIM-SM module, this will add unnecessary overhead to the
  communication from the RIB to the PIM-SM module.
  
  \item If we perform filtering at the RIB module, and if there is a
  large number of destinations the PIM-SM module needs to be informed
  about, registering all of those destinations at the RIB may introduce
  an ``explosion'' of communication from the RIB to the PIM-SM module
  in case when there is a change in the routing information about a
  large number of destinations.
  
  \item If we perform filtering at the PIM-SM module, the implementation
  may require the PIM-SM to keep a local (simplified) copy of all the
  RIB information, therefore it may increase notably the memory usage.
  This copy however can be used to perform the proper comparison and
  modification whenever MRIB update is received from the RIB module.
  
\end{itemize}

It may be possible to use some hybrid methods of propagating the MRIB
changes from the RIB module to the PIM-SM module, but based on the
above comparison it seems that \emph{filtering at the PIM-SM module} is
the simpler and more appropriate solution. Therefore, the RIB module
needs to inform the PIM-SM module whenever the MRIB information for any
destination prefix is changed.  The simplest solution for the RIB
module would be whenever any entry is changed, the RIB module would
``dump'' all RPF entries. This however may increase the communication
overhead, and may complicate additionally the PIM-SM module. A better
solution would be if the RIB modules sends only atomic updates of the
RPF information to the PIM-SM module. For example, a single message
would contain all affected entries: \eg a list of \emph{MRIB\_ADD} and
\emph{MRIB\_DELETE} commands, and the particular ordering of those
entries would specify also the order the PIM-SM module should apply
them.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{PimConfig Description}

PimConfig handles the PIM-specific configuration~\footnote{Currently
(March 2007), PimConfig is not implemented; rather, all state is
kept inside PimNode instead.}. This configuration is used to configure the
following units:

\begin{itemize}

  \item PimVif: protocol version, Hello-related options and timer
  values, etc.

  \item PimScopeZone table: add and delete information about scoped zones.

  \item PimBsr: configure the local routing unit as a Candidate-BSR or a
  Candidate-RP.

  \item RpTable: add static RPs to the RP-Set.

\end{itemize}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%     APPENDIX
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\appendix
\section{Modification History}

\begin{itemize}

  \item December 11, 2002: Initial version 0.1 completed.

  \item March 10, 2003: Updated to match XORP release 0.2.

  \item June 9, 2003: Updated the version to 0.3, and the date.

  \item August 28, 2003: Updated the version to 0.4, and the date.

  \item November 6, 2003: Updated to match XORP release 0.5: added brief info
  about retrieving protocol-related statistics.

  \item July 8, 2004: Updated to match XORP release 1.0.

  \item January 27, 2005: Removed MFEA+MRIB-related text, because the MFEA
  does not deal with the MRIB information anymore.

  \item April 13, 2005: Updated the version to 1.1, and the date.

  \item March 8, 2006: Updated the version to 1.2, and the date.

  \item August 2, 2006: Updated the version to 1.3, and the date.

  \item March 20, 2007: Updated the version to 1.4, and the date.

\end{itemize}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%     BIBLIOGRAPHY
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\bibliography{../tex/xorp}
\bibliographystyle{plain}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\end{document}