classify_route.tex

柯老师网站上找到的

                        int slot;
                        nsaddr_t src;
                        nsaddr_t dst;
                        hashnode* next;
                };
                hashnode* ht_[256];
                const hashnode* lookup(nsaddr_t src, nsaddr_t dst) const;
        };

        int MCastClassifier::classify(Packet *const pkt)
        {
                IPHeader *h = IPHeader::access(pkt->bits());
                nsaddr_t src = h->src() >> 8; /*XXX*/
                nsaddr_t dst = h->dst();
                const hashnode* p = lookup(src, dst);
                if (p == 0) {
                        /*
                         * Didn't find an entry.
                         * Call tcl exactly once to install one.
                         * If tcl doesn't come through then fail.
                         */
                        Tcl::instance().evalf("%s new-group %u %u", name(), src, dst);
                        p = lookup(src, dst);
                        if (p == 0)
                                return (-1);
                }

                return (p->slot);
        }
\end{verbatim}
\end{small}
The \code{MCastClassifier} class implements a chained has table
with hash function on the packet source and destination addresses.
The hash function returns the slot number used to index the \code{slot\_}
table in the underlying \code{Classifier} object.
A hash miss implies packet delivery to a previously-unknown group is
occurring and OTcl is called to handle this situation.
The OTcl code is expected to insert an appropriate entry into the
hash table.
The way this insertion is performed is in section\ref{sec:classotcl}, below.

\subsection{\shdr{Replicator}{replicator.cc}{sec:classreplicator}}

To support multicast packet forwarding, a classifier receiving a
multicast packet from source $S$
destined for group $G$ computes a hash function $h(S,G)$ giving
a ``slot number'' in the classifier's object table.
Thus, the maximum size of the table is $O(|S|\times|G|)$.
In multicast delivery, the packet must be copied once for
each link leading to nodes subscribed to $G$ minus one.
Production of additional copies of the packet is performed
by a \code{Replicator} class, defined in \code{replicator.cc}:
\begin{small}
\begin{verbatim}
        /*
         * A replicator is not really a packet classifier but
         * we simply find convenience in leveraging its slot table.
         * (this object used to implement fan-out on a multicast
         * router as well as broadcast LANs)
         */
        class Replicator : public Classifier {
        public:
                Replicator();
                void recv(Packet*, Handler* h = 0);
                virtual int classify(Packet* const) {};
        protected:
                int ignore_;
        };

        void Replicator::recv(Packet* p, Handler*)
        {
                IPHeader *iph = IPHeader::access(p->bits());
                if (maxslot_ < 0) {
                        if (!ignore_)
                                Tcl::instance().evalf("%s drop %u %u", name(), 
                                        iph->src(), iph->dst());
                        Packet::free(p);
                        return;
                }
                for (int i = 0; i < maxslot_; ++i) {
                        NsObject* o = slot_[i];
                        if (o != 0)
                                o->recv(p->copy());
                }
                /* we know that maxslot is non-null */
                slot_[maxslot_]->recv(p);
        }
\end{verbatim}
\end{small}
This class is derived from \code{Classifier}, but does not really
classify packets.
Rather, it replicates a packet, one for each entry in its
table, and delivers the copies to each of the nodes listed
in the table.
The last entry in the table gets the ``original'' packet.
The class over-rides the base class version of \code{recv} with its
own member function and defines the \code{classify} function as empty.
This function first determines if there are any downstream nodes to deliver
the packet to.
If not, this generally indicates no downstream node
is interested in receiving packets destined for the packet's group and that
a {\em prune} message should be sent to cut the multicast distribution
subtree rooted at the local node off from the overall distribution tree
(see section \ref{sec:mcastprune}).


\subsection{\shdr{OTcl Support: Nodes and MultiNodes}{ns-mcast.tcl}{sec:classotcl}}

The simulator may be configured in one of two modes, with support
for multicast delivery optionally enabled.
When only unicast delivery is enabled, the simulator object
itself is of the class \code{Simulator} and nodes in the simulation
topology are of class \code{Node}.
With multicasting enabled, subclasses of these two classes,
\code{MultiSim} and \code{MultiNode}, are used in their places.

\begin{figure}[h]
\centerline{\psfig{figure=node.eps,width=3in,height=3in}}
\caption{\label{pic:node}A Node object containing
two address classifiers.
The top classifier is used in unicast packet delivery to downstream
nodes.
The lower classifier is used for delivering packets to agents
on the same node.}
\end{figure}

\subsubsection{\shdr{Nodes}{ns-node.tcl}{sec:node}}

Figure \ref{pic:node} depicts a (unicast) node.
This class is defined entirely in OTcl (it has no C++ shadow object),
but makes use of a number of the C++ objects described above.
The \code{neighbor\_} member variable is a list containing the
OTcl handles for each downstream neighbor in the topology.
The OTcl function \code{Node add-neighbor} adds a node to this list.
The \code{agents\_} member variable is a list containing the
OTcl handles for each of the agents present on this node.
Each of the agents has a {\em port} number associated with it
which is currently encoded in the low-order 8 bits of the destination
address of each packet (XXX will this change? XXX).
The \code{classifier\_} variable holds a reference to an address
classifier which inspects an incoming packet to determine
if it should be locally delivered or forwarded.
In the case of local delivery, the packet is passed through another
classifier which inspects the port identifier to determine which
agent on the local node should receive the packet.

Nodes are typically created and initialized by the
\code{Simulator node} method.
This method creates a new \code{Node} object, places a reference to
it in the array \code{Node\_} (a member of the \code{Simulator} class,
indexed by node id number), and returns the newly-created node.
When a new node is created it's initialization procedure
\code{Node init} assigns a new unique node identifier and
creates the address classifier used to route to downstream nodes.
At this point the classifier's object table (i.e. routing table) is empty
and it has no attached agents.

A collection of OTcl methods in the \code{Node} class allow
for manipulating the routing and agent dispatch tables.
The \code{add-route} function adds an entry in the 
routing table causing packets destined for the specified destination address
to be delivered to the specified object.
The \code{attach} method adds an agent to the node.
It updates the \code{agent\_} list, allocates a new port ID and gives it
to the agent, updates the {\em local entry} in the routing table, and
updates the \code{dmux\_} classifier to point to the agent given the
corresponding port ID.
The \code{port} method looks up an agent on a node given its port ID.
The \code{reset} method resets all agents on the node by calling
their individual \code{reset} methods.

\begin{figure}[h]
\centerline{\psfig{figure=multinode.eps,width=4in}}
\caption{\label{pic:mnode}A MultiNode object includes all
linkage as a Node object described above, plus a
special set of replicators used to deliver copies of
packets to all interested downstream neighbors.}
\end{figure}

\subsubsection{\shdr{MultiNodes}{ns-mcast.tcl}{sec:multinode}}

Figure \ref{pic:mnode} depicts a multicast node.
It is derived from the \code{Node} class and is also implemented
entirely in OTcl.
The \code{switch\_} member variable
contains a reference to a classifier used to separate
multicast from unicast delivery.
This object is set up such that all unicast traffic is
passed through slot zero to the next classifier which operates
identically to the routing classifier described in section~\ref{sec:node}.
The other classifier is of type \code{Classifier/Multicast/Replicator}
(in OTcl) which is shadowed by an object of type
\code{Classifier/Multicast} in C++
(and defined in section~\ref{sec:classmcast}).
Its object entries are indexed by source/group pair and refer to
\code{Classifier/Replicator/Demuxer} objects which contain
the per-source/group set of next-hop objects.
These objects are shadowed by C++ objects of the
class \code{Classifier/Replicator}, described in section
\ref{sec:classreplicator}.

The operation of MultiNode objects is closely related to
the exchange of {\em prune} and {\em graft} messages used
to establish multicast distribution trees.
This is further explained in section\ref{sec:unknown}
(XXX this needs to be written XXX).

%%\begin{figure}[h]
%%\centerline{\psfig{figure=mcast_classes.eps,width=4in}}
%%\caption{\label{pic:mcastclasses}Classes used to support multicasting
%%and other related classes.  Class names in {\bf bold} indicate
%%the OTcl classes are shadowed by C++ objects.}
%%\end{figure}
%%
%%A number of classes are used in support of multicast delivery.
%%Figure \ref{pic:mcastclasses} illustrates their inheritance relationship.
%%All classes depicted exist in the OTcl name space, and those in bold
%%face type have underlying C++ classes as well.