pim_arch.tex

xorp源码hg

\begin{itemize}
  \item \verb=pim/pim_vif.hh=
  \item \verb=libxorp/vif.hh=
  \item \verb=libproto/proto_unit.hh=
\end{itemize}

PimVif contains state such as PIM Hello related information, and
protocol-related statistics for this virtual interface. Also, all
the PIM-specific methods for parsing or constructing PIM control
messages when a PIM packet is received or sent are implemented as
methods in PimVif. The parsing or construction of each message type is
implemented in a separate file with a name prefix of \verb=pim_proto=.
For example, \verb=pim_proto_cand_rp_adv.cc= implements sending and
receiving of PIM Candidate-RP-Advertisement messages. The handing of
other message types is implemented in similarly named files.

By default, each PimVif is disabled; therefore, on startup it must be
enabled explicitly. 


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{PimScopeZoneTable Description}

PimScopeZoneTable is a table that contains information about scoped
zones. There is one such table per PimNode. This table is used to check
whether various control messages are allowed to be sent or accepted a
specific network interface~\footnote{Note that in the current implementation
(March 2007) the PimScopeZoneTable is used only for PIM
Bootstrap messages. In the future, the scope zone information would be
used for other control messages as well.}.

By default, PimScopeZoneTable is empty; \ie there are no scoping zone
restrictions.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{PimMrt Description}

PimMrt is the PIM-specific multicast routing table. It is the central
and most important component: its state is modified by the PIM control
messages, and the output of it is the multicast forwarding state
information that is installed in the multicast forwarding engine.

The multicast routing table is composed of four tables. Each table
contains PimMre entries (described in file \verb=pim/pim_mre.hh=):

\begin{itemize}

  \item (*,*,RP) multicast routing table. This table contains all
  (*,*,RP) multicast routing entries~\footnote{(*,*,RP) entry is an
  entry that matches all multicast groups that use one specific
  RP.}. For simplicity of implementation, this table contains an
  (*,*,RP) entry for each RP in the RpTable, even if no (*,*,RP) Join
  messages for that RP were received.  The iterator for this table
  returns the entries ordered by their RP address: the numerically
  smallest addresses first. Note that each PimMre entry in this table
  has the source address set to the RP address, and the group address
  set to zero (\ie \verb=IPvX::ZERO()=).

  \item (*,G) multicast routing table. This table contains all (*,G)
  multicast routing entries. Each entry in that table contains a pointer
  to the corresponding (*,*,RP) entry for that group, or NULL if the
  group has no RP yet. The iterator for this table returns the entries
  ordered by their group address: the numerically smallest addresses
  first. Note that each PimMre entry in this table has the source
  address set to zero (\ie \verb=IPvX::ZERO()=).

  \item (S,G) multicast routing table. This table contains all (S,G)
  multicast routing entries. Each entry in that table contains a pointer
  to the corresponding (*,G) entry for that group, or NULL if there is
  no (*,G) entry. It also contains a pointer to the corresponding
  (S,G,rpt) entry if such entry exists (seen below). There are two iterators
  for this table: an iterator for the entries ordered by the numerically
  smallest source address first, and an iterator for the entries ordered
  by the numerically smallest group address first.

  \item (S,G,rpt) multicast routing table. This table contains all
  (S,G,rpt) multicast routing entries. Each entry in that table contains
  a pointer to the corresponding (*,G) entry for that group, or NULL if
  there is no (*,G) entry. It also contains a pointer to the
  corresponding (S,G) entry if such entry exists. There are two
  iterators for this table: an iterator for the entries ordered by the
  numerically smallest source address first, and an iterator for the
  entries ordered by the numerically smallest group address first.

\end{itemize}

For simplicity of implementation, currently (March 2007) PimMrt
contains one more table: PimMrtMfc PIM-specific table with Multicast
Forwarding Cache (PimMfc) entries (in the future, this table may be
moved out of PimMrt to PimNode). This table contains all
entries that have been installed in the multicast forwarding table in
the multicast forwarding engine. Currently (March 2007), those
entries are source-group-specific, and are installed ``on-demand'' (\ie
only if there is an active source for some multicast group). In the future,
group-specific entries may be supported as well (assuming that that
multicast forwarding engine supports (*,G) multicast forwarding
entries).

In addition to the above tables, PimMrt contains a mechanism for
tracking dependencies among the PimMre and PimMfc entries, as well as
the PimMre and PimMfc dependencies on external state such as the RP set
or the MRIB information. For example, if the MRIB for a specific network
prefix changes, then all PimMre and PimMfc entries that depend on that
network prefix must be updated accordingly. A single change may trigger
a number of operations that must be performed on a number of entries,
therefore we need to carefully track the state dependency. Below is a
summary of some of the events that may trigger actions to process
entries in PimMrt:

\begin{itemize}

  \item RP-Set change: \eg if there is any change to the RP-Set that
  affects the group-to-RP mapping.

  \item MRIB change: any change in the underlying unicast routing that
  affects the Reverse-Path Forwarding information toward an RP or a
  source.

  \item Next-Hop PIM neighbor change: any change to the set of PIM
  neighbors that may affect the Next-Hop PIM Router toward a destination.

  \item Reception of a PIM Join/Prune message.

  \item Reception of a PIM Assert message.

  \item Add/deletion of a local multicast member.

  \item Change in the Designated Router on an interface.

  \item Change in the IP address or IP subnet on an interface.

  \item Start or stop a virtual interface.

  \item Addition or deletion of a PimMre entry.

\end{itemize}

A complete list of all input events that may trigger actions is in file
\verb=pim/pim_mre_track_state.hh= (see the
\verb=input_state_t INPUT_STATE_*= events).

In some cases, keeping track of the entries that need to be processed
for a given input event is relatively simple. For example, if the MRIB
for a network prefix changes, processing all (S,G) PimMre entries that
might be affected can be done by using the source-first iterator for the
(S,G) multicast routing table, and then iterating over all (S,G) PimMre
entries whose source address matches that network prefix. However, in
other cases we cannot use those table iterators. For example, if an RP is
deleted, we need to process all corresponding (*,G) entries that match
to that RP, and to reassign them to a new RP. In that case, to keep track
of the dependencies between the RP and the (*,G) entries, each RP entry
in the RpTable contains a list of PimMre entries that match to that
RP. Similarly, each PimNbr entry (an entry that contains information
about a PIM neighbor) contains a list of all PimMre entries that use
that PIM neighbor as the Next-Hop Router toward the RP or the source.

The dependency tracking mechanism needs to solve another problem: for
each input event, find all the operations and their ordering that need
to be performed on some of the PimMre and PimMfc entries.  The solution
chosen to solve this problem is to enumerate all possible input events
and output operations, and to compute in advance a table. Lookup to this
table for a given input event returns a list of the ordered output
operations that need to be performed for that event.

If there are just few input events and output operations, it might be
possible to create such table manually. However, there are tens of input
and output events, therefore it is not feasible to crate manually such
table. The solution is on startup to automatically compute this table
based on a set of rules about the various state dependencies as defined
in the PIM-SM spec. Those state dependencies are derived from the macros
in the PIM-SM protocol specification. For example, the specification
document contains macros like:

\begin{verbatim}
pim_include(S,G) =
    { all interfaces I such that:
      ( (I_am_DR( I ) AND lost_assert(S,G,I) == FALSE )
        OR AssertWinner(S,G,I) == me )
       AND  local_receiver_include(S,G,I) }
\end{verbatim}

Then, the corresponding state dependency rule in the implementation is:

\begin{verbatim}
void
PimMreTrackState::track_state_pim_include_sg(list<PimMreAction> action_list)
{
    track_state_i_am_dr(action_list);
    track_state_lost_assert_sg(action_list);
    track_state_assert_winner_sg(action_list);
    track_state_local_receiver_include_sg(action_list);
}
\end{verbatim}

In other words, if the value of \verb=lost_assert(S,G,I)= for example changes,
then the value of \verb=pim_include(S,G)= must be recomputed.
However, we may have some state dependency rules for
\verb=lost_assert(S,G,I)= itself, hence if we combine all state
dependency rules, we can represent the dependencies with a collection
of uni-directional graphs. Then, to create the list of actions for each
input entry, we need to consider all paths from the graph node for
that input entry to all reachable output actions.
The uni-directional graphs creation and the extraction of the lists of
actions for each input entry is performed once on startup. The result
lists are saved internally inside PimMrt, and used during processing of
input actions.

Finally, the last major problem that the dependency tracking mechanism
needs to solve is how to process a large number of entries triggered by
a single event without stopping processing of other components in the
router (\eg receiving PIM control packets, or responding to a command
sent by the CLI). This problem requires attention
because the implementation is single-threaded, therefore if processing a
single event takes too long, the rest of the pending events may
be processed too late (\eg if the periodic sending of PIM Hello messages
is delayed for too long, the PIM neighbors may timeout this
router). The solution of this problem is to voluntarily suspend
the processing if it is taking too long, then save the necessary state
to continue the processing sometime later, and finally return control to
the control loop which handles all events. Typically, the processing of
some event may take too
long if there is a large number of PimMre or PimMrt entries that
need to be processed (for example, thousands of (*,G) entries if the RP
for those entries changes). In that case, we use ``time-slices'' to
compute how long has taken the processing so far.
In the above example, we check the processing time after we process each
(*,G) entry: if the elapsed time is above a threshold (\eg 100ms),
we save the appropriate state to continue the
processing later (\eg in the above example we save the address of the
next multicast group to process).

All dependency tracking processing and time-slicing uses PimMreTask
entries to keep the appropriate state. There is a single list of
PimMreTask entries per PimNode, and the list is FIFO: new tasks are
added to the end of the lists, and the task at the front of the list is
processed until it is completed (\eg within one or several time-slices).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{PimBsr Description}

PimBsr is the PIM-Bootstrap mechanism unit. It implements the Bootstrap
mechanism as described in \cite{PIM-SM-BOOTSTRAP}. There is one PimBsr