multicast.tex

柯老师网站上找到的

	internal routine to execute ``\code{op}'' with ``\code{args}''
	on all protocol instances active at that node. \\
\proc[]{start} & \\
\proc[]{stop} &
	start/stop execution of all protocols. \\
\proc[dummy]{notify} &
	is called when a topology change occurs. The dummy argument is
	currently not used.\\
{\let\[=[\let\]=]
\proc[file-handle, \[grp\], \[src\]]{dump-mroutes}} &
	dump multicast routes to specified file-handle. \\
\proc[G, S]{join-group} &
	signals all protocol instances to join \tup{S, G}. \\
\proc[G, S]{leave-group} &
	signals all protocol instances to leave \tup{S, G}. \\
\proc[code, s, g, iif]{upcall} &
	signalled by node on forwarding errors in classifier;
	this routine in turn signals the protocol instance that owns
	the incoming interface (\code{iif}) by invoking the
	appropriate handle function for that particular code.\\ 
\proc[rep, s, g, iif]{drop} &
	Called on packet drop, possibly to prune an interface. \\
\end{alist}

In addition, the mrtObject class supports the concept of well known
groups, \ie, those groups that do not require explicit protocol support.
Two well known groups, \code{ALL_ROUTERS} and \code{ALL_PIM_ROUTERS}
are predefined in \ns.

The \clsref{mrtObject}{../ns-2/tcl/mcast/McastProto.tcl} defines
two class procedures to set and get information about these well known groups.
\begin{alist}
\proc[name]{registerWellKnownGroups} & 
	assigns \code{name} a well known group address. \\
\proc[name]{getWellKnownGroup} &
	returns the address allocated to well known group, \code{name}.
	If \code{name} is not registered as a well known group,
	then it returns the address for \code{ALL\_ROUTERS}.
\end{alist}

\paragraph{McastProtocol class}
This is the base class for the implementation of all the multicast protocols.
It contains basic multicast functions:
\begin{alist}
\proc[]{start}, \proc[]{stop} &
	Set the \code{status\_} of execution of this protocol instance. \\
\proc[]{getStatus} &
	return the status of execution of this protocol instance. \\
\proc[]{getType} &
	return the type of protocol executed by this instance. \\
\proc[code args]{upcall} &
	invoked when the node classifier signals an error, either due to 
	a cache-miss or a wrong-iif for incoming packet.  This routine
	invokes the protocol specific handle, \proc{handle-\tup{code}} with
	specified \code{args} to handle the signal. \\
\end{alist}

A few words about interfaces.  Multicast implementation in \ns\
assumes duplex links i.e. if there is a simplex link from node~1 to
node~2, there must be a reverse simplex link from node~2 to node~1.
To be able to tell from which link a packet was received, multicast
simulator configures links with an interface labeller at the end of
each link, which labels packets with a particular and unique label
(id).  Thus, ``incoming interface'' is referred to this label and is a
number greater or equal to zero.  Incoming interface value can be
negative (-1) for a special case when the packet was sent by a local
to the given node agent.

In contrast, an ``outgoing interface'' refers to an object handler,
usually a head of a link which can be installed at a replicator.  This
destinction is important: \textit{incoming interface is a numeric label to
a packet, while outgoing interface is a handler to an object that is
able to receive packets, e.g. head of a link.}
 
\subsection{Extensions to other classes in \ns}
In \href{the earlier chapter describing nodes in
\ns}{Chapter}{chap:nodes}, we described the internal structure of the
node in \ns.  To briefly recap that description, the node entry for a
multicast node is the
\code{switch\_}.  It looks at the highest bit to decide if the
destination is a multicast or unicast packet.  Multicast packets are
forwarded to a multicast classifier which maintains a list of
replicators; there is one replicator per \tup{source, group} tuple.
Replicators copy the incoming packet and forward to all outgoing
interfaces.

\paragraph{Class Node}
Node support for multicast is realized in two primary ways: it serves
as a focal point for access to the multicast protocols, in the areas
of address allocation, control and management, and group membership
dynamics; and secondly, it provides primitives to access and control
interfaces on links incident on that node.
\begin{alist}
\proc[]{expandaddr}, & \\
\proc[]{allocaddr} &
	Class procedures for address management.
	\proc[]{expandaddr} increases the address space from 128
	multicast capable nodes to $2^{30} - 1$.
	\proc[]{allocaddr} allocates the next available multicast
	address.\\[2ex]
\proc[]{start-mcast}, & \\
\proc[]{stop-mcast} &
	To start and stop multicast routing at that node. \\
\proc[]{notify-mcast} &
	\proc[]{notify-mcast} signals the mrtObject at that node to
	recompute multicastroutes following a topology change or
	unicast route update from a neighbour.  \\[2ex]
\proc[]{getArbiter} &
	returns a handle to mrtObject operating at that node. \\
\proc[file-handle]{dump-routes} &
	to dump the multicast forwarding tables at that node. \\[2ex]
\proc[s g iif code]{new-group} &
	When a multicast data packet is received, and the multicast
	classifier cannot find the slot corresponding to that data
	packet, it invokes \proc[]{Node~nstproc~new-group} to
	establish the appropriate entry.  The code indicates the
	reason for not finding the slot.  Currently there are two
	possibilities, cache-miss and wrong-iif.  This procedure
	notifies the arbiter instance to establish the new group. \\
\proc[a g]{join-group} &
	An \code{agent} at a node that joins a particular group invokes
	``\code{node join-group <agent> <group>}''.  The
	node signals the mrtObject to join the particular \code{group},
	and adds \code{agent} to its list of agents at that
	\code{group}.  It then adds \code{agent} to all replicators
	associated with \code{group}. \\
\proc[a g]{leave-group} &
	\code{Node~instproc~leave-group} reverses the process
	described earlier.  It disables the outgoing interfaces to the
	receiver agents for all the replicators of the group, deletes
	the receiver agents from the local \code{Agents\_} list; it
	then invokes the arbiter instance's
	\proc[]{leave-group}.\\[2ex]
\proc[s g iif oiflist]{add-mfc} &
	\code{Node~instproc~add-mfc} adds a \textit{multicast forwarding cache}
	entry for a particular \tup{source, group, iif}.
	The mechanism is:
	\begin{itemize}
	\item create a new replicator (if one does not already exist),
	\item update the \code{replicator\_} instance variable array at the node,
	\item add all outgoing interfaces and local agents to the
	    appropriate replicator,
	\item invoke the multicast classifier's \proc[]{add-rep}
	    to create a slot for the replicator in the multicast
	    classifier.
	\end{itemize} \\
\proc[s g oiflist]{del-mfc} &
	disables each oif in \code{oiflist} from the replicator for \tup{s, g}.\\
\end{alist}

The list of primitives accessible at the node to control its interfaces are listed below.
\begin{alist}
\proc[ifid link]{add-iif}, & \\
\proc[link if]{add-oif} &
	Invoked during link creation to prep the node about its 
	incoming interface label and outgoing interface object. \\

\proc[]{get-all-oifs} &
	Returns all oifs for this node. \\
\proc[]{get-all-iifs} &
	Returns all iifs for this node. \\

\proc[ifid]{iif2link} &
	Returns the link object labelled with given interface
	label. \\
\proc[link]{link2iif} &
	Returns the incoming interface label for the given
	\code{link}. \\

\proc[oif]{oif2link} &
	Returns the link object corresponding to the given outgoing
	interface. \\
\proc[link]{link2oif} &
	Returns the outgoing interface for the \code{link} (\ns\
	object that is incident to the node).\\

\proc[src]{rpf-nbr} &
	Returns a handle to the neighbour node that is its next hop to the 
	specified \code{src}.\\

\proc[s g]{getReps} &
	Returns a handle to the replicator that matches \tup{s, g}.
	Either argument can be a wildcard (*). \\
\proc[s g]{getReps-raw} &
	As above, but returns a list of \tup{key, handle} pairs. \\
\proc[s g]{clearReps} &
	Removes all replicators associated with \tup{s, g}. \\[2ex]
\end{alist}

\paragraph{Class Link and SimpleLink}
This class provides methods to check the type of link, and the label it 
affixes on individual packets that traverse it.
There is one additional method to actually place the interface objects on this link.
These methods are:
\begin{alist}
\proc[]{if-label?} & 
	returns the interface label affixed by this link to packets
	that traverse it. \\
\proc[]{enable-mcast} & 
	Internal procedure called by the SimpleLink constructor to add
	appropriate objects and state for multicast.  By default, (and
	for the point-to-point link case) it places a NetworkInterface
	object at the end of the link, and signals the nodes on
	incident on the link about this link.\\
\end{alist}

\paragraph{Class NetworkInterface}
This is a simple connector that is placed on each link.  It affixes
its label id to each packet that traverses it.  The packet id is used
by the destination node incident on that link to identify the link by
which the packet reached it.  The label id is configured by the Link
constructor.  This object is an internal object, and is not designed
to be manipulated by user level simulation scripts.  The object only
supports two methods:
\begin{alist}
\proc[ifid]{label} & 
	assigns \code{ifid} that this object will affix to each packet. \\
\proc[]{label} & 
	returns the label that this object affixes to each packet.\\
\end{alist}
The global class variable, \code{ifacenum\_}, specifies the next
available \code{ifid} number.

\paragraph{Class Multicast Classifier}
\code{Classifier/Multicast} maintains a \emph{multicast forwarding
cache}.  There is one multicast classifier per node. The node stores a
reference to this classifier in its instance variable
\code{multiclassifier\_}. When this classifier receives a packet, it
looks at the \tup{source, group} information in the packet headers,
and the interface that the packet arrived from (the incoming interface
or iif); does a lookup in the MFC and identifies the slot that should
be used to forward that packet.  The slot will point to the
appropriate replicator.

However, if the classifier does not have an entry for this
\tup{source, group}, or the iif for this entry is different, it will
invoke an upcall \proc[]{new-group} for the classifier, with one of
two codes to identify the problem:

\begin{itemize}
	\item \code{cache-miss} indicates that the classifier did not
	find any \tup{source, group} entries;

	\item \code{wrong-iif} indicates that the classifier found
	\tup{source, group} entries, but none matching the interface
	that this packet arrived on.
\end{itemize}
These upcalls to TCL give it a chance to correct the situation:
install an appropriate MFC--entry (for \code{cache-miss}) or change
the incoming interface for the existing MFC--entry (for
\code{wrong-iif}).  The \emph{return value} of the upcall determines
what classifier will do with the packet.  If the return value is
``1'', it will assume that TCL upcall has appropriately modified MFC
will try to classify packet (lookup MFC) for the second time.  If the
return value is ``0'', no further lookups will be done, and the packet
will be thus dropped.

\proc[]{add-rep} creates a slot in the classifier
and adds a replicator for \tup{source, group, iif} to that slot.

\paragraph{Class Replicator}
When a replicator receives a packet, it copies the packet to all of
its slots.  Each slot points to an outgoing interface for a particular
\tup{source, group}.

If no slot is found, the C++ replicator invokes the class instance
procedure \proc[]{drop} to trigger protocol specific actions.  We will
describe the protocol specific actions in the next section, when we
describe the internal procedures of each of the multicast routing
protocols.

There are instance procedures to control the elements in each slot:
\begin{alist}
\proc[oif]{insert} & inserting a new outgoing interface
                        to the next available slot.\\
\proc[oif]{disable} & disable the slot pointing to the specified oif.\\
\proc[oif]{enable} &  enable the slot pointing to the specified oif.\\
\proc[]{is-active} & returns true if the replicator has at least one active slot.\\
\proc[oif]{exists} & returns true if the slot pointing to the specified oif is active.\\
\proc[source, group, oldiif, newiif]{change-iface} & modified the iif entry for the particular replicator.\\
\end{alist}

\subsection{Protocol Internals}
\label{sec:mcastproto-internals}

We now describe the implementation of the different multicast routing
protocol agents.

\subsubsection{Centralized Multicast}
\code{CtrMcast} is inherits from \code{McastProtocol}.
One CtrMcast agent needs to be created for each node.  There is a