Manual: Queue Management and Packet Scheduling

From nsnam
Revision as of 01:04, 20 June 2008 by Lachlan (Talk | contribs)

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search

Chapter 7

Previous Chapter (6) | Index | Next Chapter (8)

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 delay element is downstream from a queue, the queue may be 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.

The C++ Queue Class

The Queue class is derived from a 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 queue.h:

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_;
};

The enque and deque functions are pure virtual, indicating the Queue class is to be used as a base class; particular queues are derived from Queue and implement these two functions as necessary. Particular queues do not, in general, override the recv function because it invokes the the particular enque and deque.

The Queue class does not contain much internal state. Often these are special monitoring objects (Chapter 26). The qlim_ member is constructed to dictate a bound on the maximum queue occupancy, but this is not enforced by the Queue class itself; it must be used by the particular queue subclasses if they need this value. The 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.

Queue blocking

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 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:

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;
   }
}

The handler management here is somewhat subtle. When a new Queue object is created, it includes a QueueHandler object (qh_) which is initialized to contain a reference to the new Queue object (Queue& QueueHandler::queue_). This is performed by the Queue constructor using the expression qh_(*this). When a Queue receives a packet it calls the subclass (i.e. queueing discipline-specific) version of the enque function with the packet. If the queue is not blocked, it is allowed to send a packet and calls the specific 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 handle function by passing &qh_ to the simulator scheduler. The handle function invokes 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 LinkDelay::recv() method (Section 8.1).

PacketQueue Class

The Queue class may implement buffer management and scheduling but do not implement the low-level operations on a particular queue. The PacketQueue class is used for this purpose, and is defined as follows (see queue.h):

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
};

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 PacketQueue objects. The PacketQueue class maintains current counts of the number of packets held in the queue which is returned by the length() method. The enque function places the specified packet at the end of the queue and updates the len_ member variable. The 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 lookup function returns the nth packet from the head of the queue, or NULL otherwise. The 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.

Example: Drop Tail

The following example illustrates the implementation of the 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:

/*
* A bounded, drop-tail queue
*/
class DropTail : public Queue {
protected:
   void enque(Packet*);
   Packet* deque();
   PacketQueue q_;
};

The base class Queue, from which 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 PacketQueue class. Drop-tail implements its own versions of enque and deque as follows:

/*
* 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());
}

Here, the 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 qlim_. Drop-on-overflow is implemented by dropping the packet most recently added to the packet queue if the limit is reached or exceeded. Note: in the implementation of enque above, setting qlim_ to n actually means a queue size of n-1. Simple FIFO scheduling is implemented in the deque function by always returning the first packet in the packet queue.

Different types of Queue objects

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:

limit_ The queue size in packets.
blocked_ Set to false by default, this is true if the queue is blocked (unable to send a packet to its downstream neighbor).
unblock_on_resume_ Set to true by default, indicates a queue should unblock itself at the time the last packet sent has been transmitted (but not necessarily received).

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:

  • 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.
  • 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:
secsPerByte_

There are no state variables associated with this object.

  • 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:
maxqueue_
buckets_

There are no state variables associated with this object.

  • 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:

buckets_ Indicates the total number of buckets to be used for hashing each of the flows.
blimit_ Indicates the shared buffer size in bytes.
quantum_ Indicates (in bytes) how much each flow can send during its turn.
mask_ mask_, when set to 1, means that a particular flow consists of packets having the same node id (and possibly different port ids), otherwise a flow consists of packets having the same node and port ids.
  • RED objects: RED objects are a subclass of Queue objects that implement random early-detection gateways. The object can be configured to either drop or “mark” packets. There are no methods that are specific to RED objects. Configuration Parameters are:
bytes_ Set to "true" to enable “byte-mode” RED, where the size of arriving packets affect the likelihood of marking (dropping) packets.
queue-in-bytes_ Set to "true" to measure the average queue size in bytes rather than packets. Enabling this option also causes thresh_ and maxthresh_ to be automatically scaled by mean_pktsize_ (see below).
thresh_ The minimum threshold for the average queue size in packets.
maxthresh_ The maximum threshold for the average queue size in packets.
mean_pktsize_ A rough estimate of the average packet size in bytes. Used in updating the calculated average queue size after an idle period.
q_weight_ The queue weight, used in the exponential-weightedmoving average for calculating the average queue size.
wait_ Set to true to maintain an interval between dropped packets.
linterm_ As the average queue size varies between "thresh_" and "maxthresh_", the packet dropping probability varies between 0 and "1/linterm".
setbit_ Set to "true" to mark packets by setting the congestion indication bit in packet headers rather than drop packets.
drop-tail_ Set to true to use drop-tail rather than randomdrop when the queue overflows or the average queue size exceeds "maxthresh_". For a further explanation of these variables, see [2].

None of the state variables of the RED implementation are accessible.

  • CBQ objects: CBQ objects are a subclass of Queue objects that implement class-based queueing.
$cbq insert <class>
Insert traffic class class into the link-sharing structure associated with link object cbq.
$cbq bind <cbqclass> <id1> [$id2]
Cause packets containing flow id id1 (or those in the range id1 to id2 inclusive) to be associated with the traffic class cbqclass.
$cbq algorithm <alg>
Select the CBQ internal algorithm. <alg> may be set to one of: "ancestor-only", "top-level", or "formal".
  • CBQ/WRR objects: CBQ/WRR objects are a subclass of CBQ objects that implementweighted round-robin scheduling among classes of the same priority level. In contrast, CBQ objects implement packet-by-packet round-robin scheduling among classes of the same priority level. Configuration Parameters are:
maxpkt_ The maximum size of a packet in bytes. This is used only by CBQ/WRR objects in computing maximum bandwidth allocations for the weighted round-robin scheduler.

CBQCLASS objects

CBQClass objects implement the traffic classes associated with CBQ objects.

$cbqclass setparams <parent> <okborrow> <allot> <maxidle> <prio> <level>

Sets several of the configuration parameters for the CBQ traffic class (see below).

$cbqclass parent <cbqcl|none>

specify the parent of this class in the link-sharing tree. The parent may be specified as “none” to indicate this class is a root.

$cbqclass newallot <a>

Change the link allocation of this class to the specified amount (in range 0.0 to 1.0). Note that only the specified class is affected.

$cbqclass install-queue

Install a Queue object into the compound CBQ or CBQ/WRR link structure. When a CBQ object is initially created, it includes no internal queue (only a packet classifier and scheduler).

Configuration Parameters are:

okborrow_ is a boolean indicating the class is permitted to borrow bandwidth from its parent.
allot_ is the maximum fraction of link bandwidth allocated to the class expressed as a real number between 0.0 and 1.0.
maxidle_ is the maximum amount of time a class may be required to have its packets queued before they are permitted to be forwarded
priority_ is the class’ priority level with respect to other classes. This value may range from 0 to 10, and more than one class may exist at the same priority. Priority 0 is the highest priority.
level_ is the level of this class in the link-sharing tree. Leaf nodes in the tree are considered to be at level 1; their parents are at level 2, etc.
extradelay_ increase the delay experienced by a delayed class by the specified time

QUEUE-MONITOR objects

QueueMonitor Objects are used to monitor a set of packet and byte arrival, departure and drop counters. It also includes support for aggregate statistics such as average queue size, etc.

$queuemonitor

reset all the cumulative counters described below (arrivals, departures, and drops) to zero. Also, reset the integrators and delay sampler, if defined.

$queuemonitor set-delay-samples <delaySamp_>

Set up the Samples object delaySamp_ to record statistics about queue delays. delaySamp_ is a handle to a Samples object, i.e., the Samples object should have already been created.

$queuemonitor get-bytes-integrator

Returns an Integrator object that can be used to find the integral of the queue size in bytes.

$queuemonitor get-pkts-integrator

Returns an Integrator object that can be used to find the integral of the queue size in packets.

$queuemonitor get-delay-samples

Returns a Samples object delaySamp_ to record statistics about queue delays.

There are no configuration parameters specific to this object. State Variables are:

size_ Instantaneous queue size in bytes.
pkts_ Instantaneous queue size in packets.
parrivals_ Running total of packets that have arrived.
barrivals_ Running total of bytes contained in packets that have arrived.
pdepartures_ Running total of packets that have departed (not dropped).
bdepartures_ Running total of bytes contained in packets that have departed (not dropped).
pdrops_ Total number of packets dropped.
bdrops_ Total number of bytes dropped.
bytesInt_ Integrator object that computes the integral of the queue size in bytes. The sum_ variable of this object has the running sum (integral) of the queue size in bytes.
pktsInt_ Integrator object that computes the integral of the queue size in packets. The sum_ variable of this object has the running sum (integral) of the queue size in packets.

QUEUEMONITOR/ED objects

This derived object is capable of differentiating regular packet drops from early drops. Some queues distinguish regular drops (e.g. drops due to buffer exhaustion) from other drops (e.g. random drops in RED queues). Under some circumstances, it is useful to distinguish these two types of drops.

State Variables are:

epdrops_ The number of packets that have been dropped “early”.
ebdrops_ The number of bytes comprising packets that have been dropped “early”.

Note: because this class is a subclass of QueueMonitor, objects of this type also have fields such as pdrops_ and bdrops_. These fields describe the total number of dropped packets and bytes, including both early and non-early drops.

QUEUEMONITOR/ED/FLOWMON objects

These objects may be used in the place of a conventional QueueMonitor object when wishing to collect per-flow counts and statistics in addition to the aggregate counts and statistics provided by the basic QueueMonitor.

$fmon classifier <cl>

This inserts (read) the specified classifier into (from) the flow monitor object. This is used to map incoming packets to which flows they are associated with.

$fmon dump

Dump the current per-flow counters and statistics to the I/O channel specified in a previous attach operation.

$fmon flows

Return a character string containing the names of all flow objects known by this flow monitor. Each of these objects are of type QueueMonitor/ED/Flow.

$fmon attach <chan>

Attach a tcl I/O channel to the flow monitor. Flow statistics are written to the channel when the dump operation is executed.

Configuration Parameters are:

enable_in_ Set to true by default, indicates that per-flow arrival state should be kept by the flow monitor. If set to false, only the aggregate arrival information is kept.
enable_out_ Set to true by default, indicates that per-flow departure state should be kept by the flow monitor. If set to false, only the aggregate departure information is kept.
enable_drop_ Set to true by default, indicates that per-flow drop state should be kept by the flow monitor. If set to false, only the aggregate drop information is kept.
enable_edrop_ Set to true by default, indicates that per-flow early drop state should be kept by the flow monitor. If set to false, only the aggregate early drop information is kept.

QUEUEMONITOR/ED/FLOW objects

These objects contain per-flow counts and statistics managed by a QueueMonitor/ED/Flowmon object. They are generally created in an OTcl callback procedure when a flow monitor is given a packet it cannot map on to a known flow. Note that the flow monitor’s classifier is responsible for mapping packets to flows in some arbitrary way. Thus, depending on the type of classifier used, not all of the state variables may be relevant (e.g. one may classify packets based only on flow id, in which case the source and destination addresses may not be significant). State Variables are:

src_ The source address of packets belonging to this flow.
dst_ The destination address of packets belonging to this flow.
flowid_ The flow id of packets belonging to this flow.

Commands at a glance

Following is a list of queue commands used in simulation scripts:

$ns_ queue-limit <n1> <n2> <limit>

This sets a limit on the maximum buffer size of the queue in the link between nodes <n1> and <n2>.

$ns_ trace-queue <n1> <n2> <optional:file>

This sets up trace objects to log events in the queue. If tracefile is not passed, it uses traceAllFile_ to write the events.

$ns_ namtrace-queue <n1> <n2> <optional:file>

Similar to trace-queue above, this sets up nam-tracing in the queue.

$ns_ monitor-queue <n1> <n2> <optional:qtrace> <optional:sampleinterval>

This command inserts objects that allows us to monitor the queue size. This returns a handle to the object that may be queried to determine the average queue size. The default value for sampleinterval is 0.1.

Queue/JoBS

JoBS is developed and contributed by Nicolas Christin <nicolas at cs.virginia.edu>.

This chapter describes the implementation of the Joint Buffer Management and Scheduling (JoBS) algorithm in ns. This chapter is in three parts. The first part summarizes the objectives of the JoBS algorithm. The second part explains how to configure a JoBS queue in ns. The third part focuses on the tracing mechanisms implemented for JoBS.

The procedures and functions described in this chapter can be found in ns/jobs.{cc, h}, ns/marker.{cc, h}, ns/demarker.{cc,h}. Example scripts can be found in ns/tcl/ex/jobs-{lossdel, cn2002}.tcl.

Additional information can be found at http://qosbox.cs.virginia.edu.

The JoBS algorithm

This section gives an overview of the objectives the JoBS algorithm aims at achieving, and of the mechanisms employed to reach these objectives. The original JoBS algorithm, as described in [20], was using the solution to a non-linear optimization problem. This ns-2 implementation uses the feedback-control based heuristic described in [8]. Important Note: This ns-2 implementation results from the merge between old code for ns-2.1b5, and code derived from the BSD kernel-level implementation of the JoBS algorithm. It is still considered experimental. Due to the absence of binding facilities for arrays between Tcl and C++ in tclcl at the moment, the number of traffic classes is statically set to 4 and cannot be changed without modifying the C++ code.

The JoBS documentation has not yet been copied from the LaTeX manual.


Previous Chapter (6) | Index | Next Chapter (8)