classify_route.tex

柯老师网站上找到的

%
% personal commentary:
%        DRAFT DRAFT DRAFT
%        - KFALL
%
\section{\shdr{Packet Fowarding}{classifier.h}{sec:classroute}}

Routing generally refers to the selection of a packet's path
through the network in conjunction with the machinery
to accomplish packet forwarding at each node.
The path selection is ordinarily accomplished by means
of a distributed algorithm capable of detecting link
failures and adjusting switch nodes to route packets
around failed links (if possible).
Path selection may also be statically configured.
Packet fowarding refers to the delivery of a packet
at a routing node to its downstream neighbor(s), and
relies on a {\em routing table} having been previously
set up by the path selection algorithm.

In this section, we explain how the packet forwarding
function is carried out.
This function may be subdivided into unicast and
multicast fowarding, which operate somewhat differently.
Routing table set-up, as accomplished by
dynamic routing protocols, are
described elsewhere (see section \ref{sec:dynroute}).

A packet arriving at a node is inspected to determine
its destination (and possibly source) address fields.
The field values are used to map the packet to a
simulator object representing the next downstream recipient
of the packet.
Overall, this process is called {\em classifying} the packet, and
is performed by a \code{Classifier} object.
In the case of unicast packet delivery, the destination address
is used to find an entry in the node's routing table
indicating the proper next hop address.
For multicasting, the destination specifies the
{\em group} identifier; any node subscribed to the specified
group will receive the packet.
In the multicast case, the routing table contains a reference
to a special objects which {\em replicate} packets to
multiple destinations, implying multiple copies of the packet may emerge
from a single router.
Furthermore, the source address is used in multicast
routing to determine which links the packet should {\em not}
be forwarded across (see below).

\subsection{\shdr{the Classifier Classes}{classifier.h}{sec:classifiers}}

A classifier provides a way to match a packet against some
logical criteria and retrieve a reference to another simulation
object based on the match results.
Each classifier contains a table of simulation objects indexed
by {\em slot number}.
The job of a classifier is to determine the slot number associated
with a received packet and return the corresponding object reference
from the table.
The C++ class \code{Classifier} provides a base class for all such
derived classes.  It is defined in \code{classifier.h} as follows:
\begin{small}
\begin{verbatim}
        class Classifier : public NsObject {
         public:
                ~Classifier();
                void recv(Packet*, Handler* h = 0);
         protected:
                Classifier();
                void install(int slot, NsObject*);
                void clear(int slot);
                virtual int command(int argc, const char*const* argv);
                virtual int classify(Packet *const) = 0;
                void alloc(int);
                NsObject** slot_;       /* table that maps slot number to a NsObject */
                int nslot_;
                int maxslot_;
        };
\end{verbatim}
\end{small}
The \code{classify} function is pure virtual, indicating the
class \code{Classifier} is to be used only as a base class.
The \code{alloc} function dynamically allocates enough space
in the table to hold the specified number of slots.
The \code{install} and \code{clear} functions add to or remove
objects from the table.
The \code{recv} function and OTcl interface is implemented
as follows in \code{classifier.cc}:
\begin{small}
\begin{verbatim}
        /*
         * objects only ever see "packet" events, which come either
         * from an incoming link or a local agent (i.e., packet source).
         */
        void Classifier::recv(Packet* p, Handler*)
        {
                NsObject* node;
                int cl = classify(p);
                if (cl < 0 || cl >= nslot_ || (node = slot_[cl]) == 0) {
                        Tcl::instance().evalf("%s no-slot %d", name(), cl);
                        Packet::free(p);
                        return;
                }
                node->recv(p);
        }

        int Classifier::command(int argc, const char*const* argv)
        {
                Tcl& tcl = Tcl::instance();
                if (argc == 3) {
                        /*
                         * $classifier clear $slot
                         */
                        if (strcmp(argv[1], "clear") == 0) {
                                int slot = atoi(argv[2]);
                                clear(slot);
                                return (TCL_OK);
                        }
                } else if (argc == 4) {
                        /*
                         * $classifier install $slot $node
                         */
                        if (strcmp(argv[1], "install") == 0) {
                                int slot = atoi(argv[2]);
                                NsObject* node = (NsObject*)TclObject::lookup(argv[3]);
                                install(slot, node);
                                return (TCL_OK);
                        }
                }
                return (NsObject::command(argc, argv));
        }
\end{verbatim}
\end{small}
The primary execution path through a classifier is through the
\code{recv} function, which uses the derived class' version of
the \code{classify} method to determine the slot index.
Assuming an object exists in the table at the returned index that
object is given the packet.
If the \code{classify} function returns a slot index outside
the allocated range of objects or the object reference is
null, then the tcl procedure \code{Classifier no-slot} is invoked
with the slot number.
Presently this OTcl procedure prints an error message and terminates
the simulation.
The primary Otcl interface is provided by the \code{command} function,
which provides for adding or removing objects to/from the
object table.

\subsection{\shdr{Address Classifiers}{classifier-addr.cc}{sec:classaddr}}

An address classifier is used in supporting unicast packet
forwarding.
It applies a bitwise shift and mask operation to a packet's destination
address to produce a slot number.
The slot number is returned from the \code{classify} function.
The \code{AddressClassifier} class is defined in
\code{classifier-addr.cc} as follows:
\begin{small}
\begin{verbatim}
        class AddressClassifier : public Classifier {
        public:
                AddressClassifier() : mask_(~0), shift_(0) {
                        bind("mask_", (int*)&mask_);
                        bind("shift_", &shift_);
                }
        protected:
                int classify(Packet *const p) {
                        IPHeader *h = IPHeader::access(p->bits());
                        return ((h->dst() >> shift_) & mask_);
                }
                nsaddr_t mask_;
                int shift_;
        };
\end{verbatim}
\end{small}
The class imposes no direct semantic meaning on a packet's destination
address field.
Rather, it returns some number of the high-order bits as the slot
number used in the \code{Classifier::recv()} function.
The \code{mask\_} and \code{shift\_} values are set through OTcl.

\subsection{\shdr{Multicast Classifiers}{classifier-mcast.cc}{sec:classmcast}}

The multicast classifier classifies packets according to both source
and destination (group) addresses.
It maintains a (chained hash) table mapping source/group pairs to slot
numbers.
When a packet arrives containing a source/group unknown to the
classifier, it invokes an Otcl procedure \code{MultiNode new-group} to
add an entry to its table.
This OTcl procedure may use the method \code{set-hash} to add
new (source, group, slot) 3-tuples to the classifier's table.
The multicast classifier is defined in \code{classifier-mcast.cc}
as follows:
\begin{small}
\begin{verbatim}
        static class MCastClassifierClass : public TclClass {
        public:
                MCastClassifierClass() : TclClass("Classifier/Multicast") {}
                TclObject* create(int argc, const char*const* argv) {
                        return (new MCastClassifier());
                }
        } class_mcast_classifier;

        class MCastClassifier : public Classifier {
        public:
                MCastClassifier();
                ~MCastClassifier();
        protected:
                int command(int argc, const char*const* argv);
                int classify(Packet *const p);
                int findslot();
                void set_hash(nsaddr_t src, nsaddr_t dst, int slot);
                int hash(nsaddr_t src, nsaddr_t dst) const {
                        u_int32_t s = src ^ dst;
                        s ^= s >> 16;
                        s ^= s >> 8;
                        return (s & 0xff);
                }
                struct hashnode {