queue_mgmt.tex

柯老师网站上找到的

%
% personal commentary:
%        DRAFT DRAFT DRAFT
%        - KFALL
%
\chapter{Queue Management and Packet Scheduling}
\label{chap:qmgmt}

Queues represent locations where packets may be held (or dropped).
Packet scheduling refers to the decision process used to choose
which packets should be serviced or dropped.
Buffer management refers to any particular discipline used
to regulate the occupancy of a particular queue.
At present, support is included for drop-tail (FIFO) queueing,
RED buffer management, CBQ (including a priority and round-robin scheduler), 
and
variants of Fair Queueing including, Fair Queueing (FQ),
Stochastic Fair Queueing (SFQ), and Deficit Round-Robin (DRR).
In the common case where a {\em delay} element is downstream from
a queue, the queue may be {\em blocked} until it is re-enabled
by its downstream neighbor.
This is the mechanism by which transmission delay is simulated.
In addition, queues may be forcibly blocked or unblocked at arbitrary
times by their neighbors (which is used to implement multi-queue
aggregate queues with inter-queue flow control).
Packet drops are implemented in such a way that queues contain
a ``drop destination''; that is, an object that receives all packets
dropped by a queue.
This can be useful to (for example) keep statistics on dropped packets.

\section{The C++ Queue Class}
\label{sec:qclass}

The \code{Queue} class is derived from a \code{Connector} base class.
It provides a base class used by particular types of (derived) queue classes,
as well as a call-back function to implement blocking (see next section).
The following definitions are provided in \code{queue.h}:
\begin{program}
        class Queue : public Connector \{
         public:
                virtual void enque(Packet*) = 0;
                virtual Packet* deque() = 0;
                void recv(Packet*, Handler*);
                void resume();
                int blocked();
                void unblock();
                void block();
         protected:
                Queue();
                int command(int argc, const char*const* argv);
                int qlim_;         \* maximum allowed pkts in queue */
                int blocked_;
                int unblock_on_resume_; \* unblock q on idle? */
                QueueHandler qh_;
        \};
\end{program}
The \code{enque} and \code{deque} functions are pure virtual, indicating
the \code{Queue} class is to be used as a base class;
particular queues are derived
from \code{Queue} and implement these two functions as necessary.
Particular queues do not, in general, override the \code{recv} function
because it invokes the
the particular \code{enque} and \code{deque}.

The \code{Queue} class does not contain much internal state.
Often these are
\href{special monitoring objects}{Chapter}{chap:trace}.
The \code{qlim_} member is constructed to dictate a bound on the maximum
queue occupancy, but this is not enforced by the \code{Queue} class itself; it
must be used by the particular queue subclasses if they need this value.
The \code{blocked_} member is a boolean indicating whether the
queue is able to send a packet immediately to its downstream neighbor.
When a queue is blocked, it is able to enqueue packets but not send them.

\subsection{Queue blocking}
\label{sec:qblock}

A queue may be either blocked or unblocked at any given time.
Generally, a queue is blocked when a packet is in transit between it
and its downstream neighbor (most of the time if the queue is occupied).
A blocked queue will remain blocked as long as it downstream link is
busy and the queue has at least one packet to send.
A queue becomes unblocked only when its \code{resume} function is
invoked (by means of a downstream neighbor scheduling it via
a callback), usually when no packets are queued.
The callback is implemented by using the following class and
methods:
\begin{program}
        class QueueHandler : public Handler \{
        public:
                inline QueueHandler(Queue& q) : queue_(q) \{\}
                void handle(Event*); /* calls queue_.resume() */
         private:
                Queue& queue_;
        \};
        void QueueHandler::handle(Event*)
        \{
                queue_.resume();
        \}

        Queue::Queue() : drop_(0), blocked_(0), qh_(*this)
        \{
                Tcl& tcl = Tcl::instance();
                bind("limit_", &qlim_);
        \}
        void Queue::recv(Packet* p, Handler*)
        \{
                enque(p);
                if (!blocked_) \{
                        /*
                         * We're not block.  Get a packet and send it on.
                         * We perform an extra check because the queue
                         * might drop the packet even if it was
                         * previously empty!  (e.g., RED can do this.)
                         */
                        p = deque();
                        if (p != 0) \{
                                blocked_ = 1;
                                target_->recv(p, &qh_);
                        \}
                \}
        \}
        void Queue::resume()
        \{
                Packet* p = deque();
                if (p != 0)
                        target_->recv(p, &qh_);
                else \{
                        if (unblock_on_resume_)
                                blocked_ = 0;
                        else
                                blocked_ = 1;
                \}
        \}
\end{program}
The handler management here is somewhat subtle.
When a new \code{Queue} object is created,
it includes a \code{QueueHandler} object (\code{qh_})
which is initialized to contain a reference to the new \code{Queue} object
(\code{Queue& QueueHandler::queue_}).
This is performed by the \code{Queue} constructor using the expression
\code{qh_(*this)}.
When a Queue receives a packet it calls the subclass
(i.e. queueing discipline-specific) version of
the \code{enque} function with the packet.
If the queue is not blocked, it is allowed to send a packet and
calls the specific \code{deque} function which determines which
packet to send, blocks the queue (because a packet is now in transit), and
sends the packet to the queue's downstream neighbor.
Note that any future packets received from upstream neighbors
will arrive to a blocked queue.
When a downstream neighbor wishes to cause the queue to become unblocked
it schedules the QueueHandler's \code{handle} function by
passing \code{&qh_} to the simulator scheduler.
The \code{handle} function invokes \code{resume}, which
will send the next-scheduled packet downstream (and leave the queue blocked),
or unblock the queue when no packet is ready to be sent.
This process is made more clear by also referring to the
\href{\fcn[]{LinkDelay::recv} method}{Section}{sec:delayclass}.

\subsection{PacketQueue Class}
\label{sec:packetqclass}

The \code{Queue} class may implement buffer management and scheduling but
do not implement the low-level operations on a particular queue.
The \code{PacketQueue} class is used for this purpose, and is defined as follows
(see \code{queue.h}):
\begin{program}
        class PacketQueue \{
        public:
                PacketQueue();
                int length(); /* queue length in packets */
                void enque(Packet* p);
                Packet* deque();
                Packet* lookup(int n);
                /* remove a specific packet, which must be in the queue */
                void remove(Packet*);
        protected:
                Packet* head_;
                Packet** tail_;
                int len_;               // packet count
        \};
\end{program}
This class maintains a linked-list of packets, and is commonly
used by particular scheduling and buffer management disciplines
to hold an ordered set of packets.
Particular scheduling or buffer management schemes may make
use of several \code{PacketQueue} objects.
The \code{PacketQueue} class maintains current counts of the number of
packets held in the queue which is returned by the \fcn[]{length} method.
The \code{enque} function places the specified packet at the end of
the queue and updates the \code{len_} member variable.
The \code{deque} function returns the packet at the head of the
queue and removes it from the queue (and updates the counters), or
returns NULL if the queue is empty.
The \code{lookup} function returns the $n$th packet from the head
of the queue, or NULL otherwise.
The \code{remove} function deletes the packet stored in the given address
from the queue (and updates the counters).
It causes an abnormal program termination if the packet does not exist.

\section{Example: Drop Tail}
\label{sec:droptail}

The following example illustrates the implementation of the
\code{Queue/DropTail} object,
which implements FIFO scheduling and
drop-on-overflow buffer management typical of most present-day
Internet routers.
The following definitions declare the class and its OTcl linkage:
\begin{program}
        /*
         * {\cf A bounded, drop-tail queue}
         */
        class DropTail : public Queue \{
         protected:
                void enque(Packet*);
                Packet* deque();
                PacketQueue q_;
        \};
\end{program}
The base class \code{Queue},
from which \code{DropTail} is derived, provides most
of the needed functionality.
The drop-tail queue maintains exactly one FIFO queue, implemented
by including an object of the \code{PacketQueue} class.
Drop-tail implements its own versions of \code{enque} and \code{deque}
as follows:
\begin{program}
        /*
         * {\cf drop-tail}
         */
        void DropTail::enque(Packet* p)
        \{
                q_.enque(p);
                if (q_.length() >= qlim_) \{
                        q_.remove(p);
                        drop(p);
                \}
        \}

        Packet* DropTail::deque()
        \{
                return (q_.deque());
        \}
\end{program}
Here, the \code{enque} function first stores the packet in the
internal packet queue (which has no size restrictions), and then
checks the size of the packet queue versus \code{qlim_}.
Drop-on-overflow is implemented by dropping the packet most recently
added to the packet queue if the limit is reached or exceeded.
Simple FIFO scheduling is implemented in the \code{deque} function
by always returning the first packet in the packet queue.


\section{Different types of Queue objects}
\label{sec:queueobjects}
A queue object is a general class of object capable of holding and
possibly marking or discarding packets as they travel through the
simulated topology. Configuration Parameters used for queue objects are:
\begin{description}
\item[limit\_] The queue size in packets. 

\item[blocked\_] Set to false by default, this is true if the queue is
blocked (unable to send a packet to its downstream neighbor). 

\item[unblock\_on\_resume\_] Set to true by default, indicates a queue
should unblock itself at the time the last packet packet sent has been
transmitted (but not necessarily received). 
\end{description}

Other queue objects derived from the base class Queue are drop-tail, FQ,
SFQ, DRR, RED and CBQ queue objects. Each are described as follows:
\begin{itemize}

\item Drop-tail objects:
Drop-tail objects are a subclass of Queue objects that implement simple
FIFO queue. There are no methods, configuration parameter, or state
variables that are specific to drop-tail objects. 

\item FQ objects:
FQ objects are a subclass of Queue objects that implement Fair queuing.
There are no methods that are specific to FQ objects. 
Configuration Parameters are:
\begin{description}
\item[secsPerByte\_] 
\end{description}
There are no state variables associated with this object. 

\item SFQ objects:
SFQ objects are a subclass of Queue objects that implement Stochastic Fair
queuing. There are no methods that are specific to SFQ objects. 
Configuration Parameters are:
\begin{description}
\item[maxqueue\_]

\item[buckets\_]
\end{description}
There are no state variables associated with this object. 

\item DRR objects:
DRR objects are a subclass of Queue objects that implement deficit round
robin scheduling. These objects implement deficit round robin scheduling
amongst different flows ( A particular flow is one which has packets with
the same node and port id OR packets which have the same node id alone).
Also unlike other multi-queue objects, this queue object implements a
single shared buffer space for its different flows. Configuration
Parameters are:
\begin{description}
\item[buckets\_] Indicates the total number of buckets to be used for