pim_arch.tex

来自「BCAST Implementation for NS2」· TEX 代码 · 共 734 行 · 第 1/3 页

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
    uint16_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~\footnote{Currently (November 2003), the information is
received from the MFEA instead.}; 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.

Note that as we mentioned earlier, currently (November 2003), the MRIB
information is received from the MFEA, which reads directly the unicast
forwarding table from the (UNIX) kernel, and PIM-SM keeps a local copy
of the whole table. The MFEA periodically reads (\eg every 10 seconds)
the unicast forwarding table, and if there is any change, it sends the
changes to all interested modules (that includes the PIM-SM module).
Similarly, the MFEA informs PIM-SM about any virtual interfaces
information changes (\eg an address has been added or
deleted)~\footnote{Strictly speaking, the VIF (Virtual InterFace)
abstraction is based on 
information that can be obtained directly from the kernel. However, the
VIF information is also related with the RIB information as well,
therefore for consistency reason, probably it is better if any VIF
information changes is propagated via the RIB module to the PIM-SM
module, especially because any change in the VIF information may affect
the unicast routing as well. This is an open issue, therefore in the
future the current behavior may be changed.}.

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

PimConfig handles the PIM-specific configuration~\footnote{Currently
(November 2003), 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: Version 0.1 completed.

  \item March 10, 2003: Updated to match XORP version 0.2 release code;
  cleanup.

  \item June 9, 2003: Bump-up the version to 0.3, and the date.

  \item August 28, 2003: Bump-up the version to 0.4, and the date.

  \item November 6, 2003: Bump-up the version to 0.5, and the date;
  add brief info about retrieving protocol-related statistics; minor edits.

\end{itemize}


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

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