rio.cc

Go to the documentation of this file.

/* -*-  Mode:C++; c-basic-offset:8; tab-width:8; indent-tabs-mode:t -*- */
/*
 * Copyright (c) 1990-1997 Regents of the University of California.
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 * 3. All advertising materials mentioning features or use of this software
 *    must display the following acknowledgement:
 *      This product includes software developed by the Computer Systems
 *      Engineering Group at Lawrence Berkeley Laboratory.
 * 4. Neither the name of the University nor of the Laboratory may be used
 *    to endorse or promote products derived from this software without
 *    specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
 * SUCH DAMAGE.
 *
 *
 * Here is one set of parameters from one of Sally's simulations
 * (this is from tcpsim, the older simulator):
 * 
 * ed [ q_weight=0.002 thresh=5 linterm=30 maxthresh=15
 *         mean_pktsize=500 dropmech=random-drop queue-size=60
 *         plot-file=none bytes=false doubleq=false dqthresh=50 
 *         wait=true ]
 * 
 * 1/"linterm" is the max probability of dropping a packet. 
 * There are different options that make the code
 * more messy that it would otherwise be.  For example,
 * "doubleq" and "dqthresh" are for a queue that gives priority to
 *   small (control) packets, 
 * "bytes" indicates whether the queue should be measured in bytes 
 *   or in packets, 
 * "dropmech" indicates whether the drop function should be random-drop 
 *   or drop-tail when/if the queue overflows, and 
 *   the commented-out Holt-Winters method for computing the average queue 
 *   size can be ignored.
 * "wait" indicates whether the gateway should wait between dropping
 *   packets.
 */

#ifndef lint
static const char rcsid[] =
    "@(#) $Header: /nfs/jade/vint/CVSROOT/ns-2/queue/rio.cc,v 1.11 2002/03/21 01:42:36 johnh Exp $ (LBL)";
#endif

#include "rio.h"
#include "tclcl.h"
#include "packet.h"
#include "random.h"
#include "flags.h"
#include "delay.h"
#include "template.h"
#include "red.h"

static class RIOClass : public TclClass {
public:
        RIOClass() : TclClass("Queue/RED/RIO") {}
        TclObject* create(int, const char*const*) {
                return (new RIOQueue);
        }
} class_rio;

RIOQueue::RIOQueue() : in_len_(0), in_bcount_(0), in_idle_(1)
{
        bind("in_thresh_", &edp_in_.th_min);        // In_minthresh
        bind("in_maxthresh_", &edp_in_.th_max);     // In_maxthresh
        bind("out_thresh_", &edp_out_.th_min);      // Out_minthresh
        bind("out_maxthresh_", &edp_out_.th_max);   // Out_maxthresh
        bind("in_linterm_", &edp_in_.max_p_inv);

        /* added by ratul- allows a finer control over the policy.
           gentle automatically means both the below are gentle */
        bind_bool("in_gentle_",&edp_in_.gentle);    // drop prob. slowly
        bind_bool("out_gentle_",&edp_out_.gentle);  // when ave queue
                                                    // exceeds maxthresh
        bind("in_ave_", &edv_in_.v_ave);            // In average queue sie
        bind("out_ave_", &edv_out_.v_ave);          // Out average queue sie
        bind("in_prob1_", &edv_in_.v_prob1);        // In dropping probability
        bind("out_prob1_", &edv_out_.v_prob1);      // Out dropping probability
        bind("priority_method_", &priority_method_); // method for setting
                                                    // priority
//      q_ = new PacketQueue();                     // underlying queue
//      pq_ = q_;
//      reset();

}

void RIOQueue::reset()
{
        /*
         * If queue is measured in bytes, scale min/max thresh
         * by the size of an average packet (which is specified by user).
         */

        if (qib_) {
                edp_in_.th_min *= edp_.mean_pktsize;
                edp_in_.th_max *= edp_.mean_pktsize;

                edp_out_.th_min *= edp_.mean_pktsize;
                edp_out_.th_max *= edp_.mean_pktsize;
        }

        //modified - ratul
        if (edp_.gentle) {
                edp_in_.gentle = true;
                edp_out_.gentle = true;
        }
        if (edp_in_.gentle) {
                edv_in_.v_c = ( 1.0 - 1 / edp_in_.max_p_inv ) / edp_in_.th_max;
                edv_in_.v_d = 2 / edp_in_.max_p_inv - 1.0;
        }               
        if (edp_out_.gentle) {
                edv_out_.v_c = ( 1.0 - 1 / edp_.max_p_inv ) / edp_out_.th_max;
                edv_out_.v_d = 2 / edp_.max_p_inv - 1.0;
        }

        /* Added by Wenjia */
        edv_in_.v_ave = 0.0;
        edv_in_.v_slope = 0.0;
        edv_in_.drops = 0;
        edv_in_.count = 0;
        edv_in_.count_bytes = 0;
        edv_in_.old = 0;
        edv_in_.v_a = 1 / (edp_in_.th_max - edp_in_.th_min);
        edv_in_.v_b = - edp_in_.th_min / (edp_in_.th_max - edp_in_.th_min);

        /* Added by Wenjia */
        edv_out_.v_ave = 0.0;
        edv_out_.v_slope = 0.0;
        edv_out_.drops = 0;
        edv_out_.count = 0;
        edv_out_.count_bytes = 0;
        edv_out_.old = 0;
        edv_out_.v_a = 1 / (edp_out_.th_max - edp_out_.th_min);
        edv_out_.v_b = - edp_out_.th_min / (edp_out_.th_max - edp_out_.th_min);

        in_idle_ = 1;
        if (&Scheduler::instance() == NULL) {
                in_idletime_ = 0.0; /* sched not instantiated yet */
        }     
        REDQueue::reset();
}

/*
 * Return the next packet in the queue for transmission.
 */
Packet* RIOQueue::deque()
{
        Packet *p;
        p = REDQueue::deque();
        // printf( "qlen %d %d\n", q_->length(), length());
        if (p != 0) {
                hdr_flags* hf = hdr_flags::access(p);
                if (hf->pri_) {   
                  /* Regular In packets */
                  in_idle_ = 0;
                  in_bcount_ -= hdr_cmn::access(p)->size();
                  --in_len_;
                }
        } else {
                in_idle_ = 1;
        }
        return (p);
}

/*
 * should the packet be dropped/marked due to a probabilistic drop?
 */
int
RIOQueue::drop_in_early(Packet* pkt)
{
        hdr_cmn* ch = hdr_cmn::access(pkt);

        edv_in_.v_prob1 = REDQueue::calculate_p(edv_in_.v_ave, edp_in_.th_max, 
          edp_in_.gentle, edv_in_.v_a, edv_in_.v_b, edv_in_.v_c, 
          edv_in_.v_d, edp_in_.max_p_inv);
        edv_in_.v_prob = REDQueue::modify_p(edv_in_.v_prob1, edv_in_.count, 
          edv_in_.count_bytes, edp_.bytes, edp_.mean_pktsize, edp_.wait, 
          ch->size());

        // drop probability is computed, pick random number and act
        double u = Random::uniform();
        if (u <= edv_in_.v_prob) {
                // DROP or MARK
                edv_in_.count = 0;
                edv_in_.count_bytes = 0;
                hdr_flags* hf = hdr_flags::access(pickPacketForECN(pkt));
                if (edp_.setbit && hf->ect() && 
                                edv_in_.v_ave < edp_in_.th_max) {
                        hf->ce() = 1;   // mark Congestion Experienced bit
                        return (0);     // no drop
                } else {
                        return (1);     // drop
                }
        }
        return (0);                     // no DROP/mark
}

/*
 * Obsolete note from original version of code:
 * The rationale here is that if the edv_in_.v_ave is close
 * to the edp_in_.th_max, (we are about to turn over to the
 * congestion control phase, presumably because of Out packets),
 * then we should drop Out packets more severely.
 */

int RIOQueue::drop_out_early(Packet* pkt)
{
        hdr_cmn* ch = hdr_cmn::access(pkt);

        edv_out_.v_prob1 = REDQueue::calculate_p(edv_.v_ave, edp_out_.th_max, 
          edp_out_.gentle, edv_out_.v_a, edv_out_.v_b, edv_out_.v_c, 
          edv_out_.v_d, edp_.max_p_inv);
        edv_out_.v_prob = REDQueue::modify_p(edv_out_.v_prob1, edv_out_.count, 
          edv_out_.count_bytes, edp_.bytes, edp_.mean_pktsize, edp_.wait, 
          ch->size());

        // drop probability is computed, pick random number and act
        double u = Random::uniform();
        if (u <= edv_out_.v_prob) {
                // DROP or MARK
                edv_out_.count = 0;
                edv_out_.count_bytes = 0;
                hdr_flags* hf = hdr_flags::access(pickPacketForECN(pkt));
                if (edp_.setbit && hf->ecn_capable_ &&
                                edv_.v_ave < edp_out_.th_max) {
                        hf->ce() = 1;   // mark Congestion Experienced bit
                        return (0);     // no drop
                } else {
                        return (1);
                }
        }
        return (0);  // no DROP/mark
}


/*
 * Receive a new packet arriving at the queue.
 * The average queue size is computed.  If the average size
 * exceeds the threshold, then the dropping probability is computed,
 * and the newly-arriving packet is dropped with that probability.
 * The packet is also dropped if the maximum queue size is exceeded.
 *
 * "Forced" drops mean a packet arrived when the underlying queue was
 * full or when the average q size exceeded maxthresh.
 * "Unforced" means a RED random drop.
 *
 * For forced drops, either the arriving packet is dropped or one in the
 * queue is dropped, depending on the setting of drop_tail_.
 * For unforced drops, the arriving packet is always the victim.
 */

#define DTYPE_NONE      0       /* ok, no drop */
#define DTYPE_FORCED    1       /* a "forced" drop */
#define DTYPE_UNFORCED  2       /* an "unforced" (random) drop */

void RIOQueue::enque(Packet* pkt)
{
        /* Duplicate the RED algorithm to carry out a separate
         * calculation for Out packets -- Wenjia */
        hdr_flags* hf = hdr_flags::access(pkt);
        hdr_ip* iph = hdr_ip::access(pkt);
        if (priority_method_ == 1) {
                hf->pri_ = iph->flowid();
        }

        //printf("RIOQueue::enque queue %d queue-length %d priority %d\n", 
        //      q_, q_->length(), hf->pri_);
        if (hf->pri_) {  /* Regular In packets */

        /*
         * if we were idle, we pretend that m packets arrived during
         * the idle period.  m is set to be the ptc times the amount
         * of time we've been idle for
         */

        int m = 0;
        int m_in = 0;
        double now = Scheduler::instance().clock();
        /* To account for the period when the queue was empty.  */
        if (in_idle_) {
                in_idle_ = 0;
                m_in = int(edp_.ptc * (now - idletime_));
        } 
        if (idle_) {
                idle_ = 0;
                m = int(edp_.ptc * (now - idletime_));
        }

        /*
         * Run the estimator with either 1 new packet arrival, or with
         * the scaled version above [scaled by m due to idle time]
         */

        // printf( "qlen %d\n", q_->length());
        edv_.v_ave = REDQueue::estimator(qib_ ? q_->byteLength() : q_->length(), m + 1,
                edv_.v_ave, edp_.q_w);
        edv_in_.v_ave = REDQueue::estimator(qib_ ? in_bcount_ : in_len_,
                m_in + 1, edv_in_.v_ave, edp_.q_w);

        /*
         * count and count_bytes keeps a tally of arriving traffic
         * that has not been dropped (i.e. how long, in terms of traffic,
         * it has been since the last early drop)
         */

        hdr_cmn* ch = hdr_cmn::access(pkt);
        ++edv_.count;
        edv_.count_bytes += ch->size();

        /* added by Yun */
        ++edv_in_.count;
        edv_in_.count_bytes += ch->size();

        /*
         * DROP LOGIC:
         *      q = current q size, ~q = averaged q size
         *      1> if ~q > maxthresh, this is a FORCED drop
         *      2> if minthresh < ~q < maxthresh, this may be an UNFORCED drop
         *      3> if (q+1) > hard q limit, this is a FORCED drop
         */

        // register double qavg = edv_.v_ave;
        register double in_qavg = edv_in_.v_ave;
        int droptype = DTYPE_NONE;
        int qlen = qib_ ? q_->byteLength() : q_->length();
        int in_qlen = qib_ ? in_bcount_ : in_len_;
        int qlim = qib_ ? (qlim_ * edp_.mean_pktsize) : qlim_;

        curq_ = qlen;   // helps to trace queue during arrival, if enabled

        if (in_qavg >= edp_in_.th_min && in_qlen > 1) {
                if ((!edp_in_.gentle && in_qavg >= edp_in_.th_max) ||
                        (edp_in_.gentle && in_qavg >= 2 * edp_in_.th_max)) {
                        droptype = DTYPE_FORCED;
                } else if (edv_in_.old == 0) {
                        /* 
                         * The average queue size has just crossed the
                         * threshold from below to above "minthresh", or
                         * from above "minthresh" with an empty queue to
                         * above "minthresh" with a nonempty queue.
                         */
                        edv_in_.count = 1;
                        edv_in_.count_bytes = ch->size();
                        edv_in_.old = 1;
                } else if (drop_in_early(pkt)) {
                        droptype = DTYPE_UNFORCED;
                }
        } else {
                /* No packets are being dropped.  */
                edv_in_.v_prob = 0.0;
                edv_in_.old = 0;                
        }
        if (qlen >= qlim) {
                // see if we've exceeded the queue size
                droptype = DTYPE_FORCED;
        }

        if (droptype == DTYPE_UNFORCED) {
                /* pick packet for ECN, which is dropping in this case */
                Packet *pkt_to_drop = pickPacketForECN(pkt);
                /* 
                 * If the packet picked is different that the one that just
                 * arrived, add it to the queue and remove the chosen packet.
                 */
                if (pkt_to_drop != pkt) {
                        q_->enque(pkt);
                        // printf( "in: qlen %d %d\n", q_->length(), length());
                        ++in_len_;
                        in_bcount_ += ch->size();
                        q_->remove(pkt_to_drop);
                        // printf("remove qlen %d %d\n",q_->length(),length());
                        if (hdr_flags::access(pkt_to_drop)->pri_)
                           {
                             in_bcount_ -= 
                                     hdr_cmn::access(pkt_to_drop)->size();
                             --in_len_;
                           }
                        pkt = pkt_to_drop; /* ok 'cause pkt not needed anymore */
                }
                // deliver to special "edrop" target, if defined
                if (de_drop_ != NULL)
                        de_drop_->recv(pkt);
                else
                        drop(pkt);
        } else {
                /* forced drop, or not a drop: first enqueue pkt */
                q_->enque(pkt);
                // printf( "in: qlen %d %d\n", q_->length(), length());
                ++in_len_;
                in_bcount_ += ch->size();

                /* drop a packet if we were told to */
                if (droptype == DTYPE_FORCED) {
                        /* drop random victim or last one */
                        pkt = pickPacketToDrop();
                        q_->remove(pkt);
                        // printf("remove qlen %d %d\n",q_->length(),length());
                        if (hdr_flags::access(pkt)->pri_) {
                          in_bcount_ -= hdr_cmn::access(pkt)->size(); 
                          --in_len_;
                          }
                        drop(pkt);
                        if (!ns1_compat_) {
                                // bug-fix from Philip Liu, <phill@ece.ubc.ca>
                                edv_.count = 0;
                                edv_.count_bytes = 0;
                                edv_in_.count = 0;
                                edv_in_.count_bytes = 0;
                        }
                }
            }
        }

        else {     /* Out packets and default regular packets */
          /*
           * count and count_bytes keeps a tally of arriving traffic
           * that has not been dropped (i.e. how long, in terms of traffic,
           * it has been since the last early drop)
           */

          hdr_cmn* ch = hdr_cmn::access(pkt);
          ++edv_.count;
          edv_.count_bytes += ch->size();

          /* added by Yun */
          ++edv_out_.count;
          edv_out_.count_bytes += ch->size();

          /*
           * DROP LOGIC:
           *    q = current q size, ~q = averaged q size
           *    1> if ~q > maxthresh, this is a FORCED drop
           *    2> if minthresh < ~q < maxthresh, this may be an UNFORCED drop
           *    3> if (q+1) > hard q limit, this is a FORCED drop
           */

                /* if the average queue is below the out_th_min
                 * then we have no need to worry.
                 */

          register double qavg = edv_.v_ave;
          // register double in_qavg = edv_in_.v_ave;
          int droptype = DTYPE_NONE;
          int qlen = qib_ ? q_->byteLength() : q_->length();
          /* added by Yun, seems not useful */
          // int out_qlen = qib_ ? out_bcount_ : q_->out_length();

          int qlim = qib_ ?  (qlim_ * edp_.mean_pktsize) : qlim_;

          curq_ = qlen; // helps to trace queue during arrival, if enabled

          if (qavg >= edp_out_.th_min && qlen > 1) {
                  if (!edp_out_.gentle && qavg >= edp_out_.th_max ||
                      (edp_out_.gentle && qavg >= 2 * edp_out_.th_max)) {
                        droptype = DTYPE_FORCED;  // ? not sure, Yun
                  } else if (edv_out_.old == 0) {
                        /* 
                         * The average queue size has just crossed the
                         * threshold from below to above "minthresh", or
                         * from above "minthresh" with an empty queue to
                         * above "minthresh" with a nonempty queue.
                         */
                        edv_out_.count = 1;
                        edv_out_.count_bytes = ch->size();
                        edv_out_.old = 1;
                  } else if (drop_out_early(pkt)) {
                        droptype = DTYPE_UNFORCED; // ? not sure, Yun
                  }
          } else {
                  edv_out_.v_prob = 0.0;
                  edv_out_.old = 0;              // explain
          }
          if (qlen >= qlim) {
                  // see if we've exceeded the queue size
                  droptype = DTYPE_FORCED;   //need more consideration, Yun
          }

          if (droptype == DTYPE_UNFORCED) {
                  /* pick packet for ECN, which is dropping in this case */
                  Packet *pkt_to_drop = pickPacketForECN(pkt);
                  /*
                   * If the packet picked is different that the one that just
                   * arrived, add it to the queue and remove the chosen packet.
                   */
                  if (pkt_to_drop != pkt) {
                          q_->enque(pkt);
                          //printf("out: qlen %d %d\n", q_->length(), length());
                          q_->remove(pkt_to_drop);
                          //printf("remove qlen %d %d\n",q_->length(),length());
                          if (hdr_flags::access(pkt_to_drop)->pri_)
                          {
                             in_bcount_ -=hdr_cmn::access(pkt_to_drop)->size();
                             --in_len_;
                          }
                          pkt = pkt_to_drop;/* ok cause pkt not needed anymore */
                  }
                  // deliver to special "edrop" target, if defined
                  if (de_drop_ != NULL)
                          de_drop_->recv(pkt);
                  else
                          drop(pkt);
          } else {
                  /* forced drop, or not a drop: first enqueue pkt */
                  q_->enque(pkt);
                  //printf("out: qlen %d %d\n", q_->length(), length());

                  /* drop a packet if we were told to */
                  if (droptype == DTYPE_FORCED) {
                          /* drop random victim or last one */
                          pkt = pickPacketToDrop();
                          q_->remove(pkt);
                          //printf("remove qlen %d %d\n",q_->length(),length());
                          if (hdr_flags::access(pkt)->pri_)
                          {
                            in_bcount_ -= hdr_cmn::access(pkt)->size();
                            --in_len_;
                          }
                          drop(pkt);
                  }
          }
        }

        return;
}

/*
 * Routine called by TracedVar facility when variables change values.
 * Currently used to trace values of avg queue size, drop probability,
 * and the instantaneous queue size seen by arriving packets.
 * Note that the tracing of each var must be enabled in tcl to work.
 */

void
RIOQueue::trace(TracedVar* v)
{
        char wrk[500], *p;

        if (((p = strstr(v->name(), "ave")) == NULL) &&
            ((p = strstr(v->name(), "in_ave")) == NULL) &&
            ((p = strstr(v->name(), "out_ave")) == NULL) &&
            ((p = strstr(v->name(), "prob")) == NULL) &&
            ((p = strstr(v->name(), "in_prob")) == NULL) &&
            ((p = strstr(v->name(), "out_prob")) == NULL) &&
            ((p = strstr(v->name(), "curq")) == NULL)) {
                fprintf(stderr, "RIO:unknown trace var %s\n",
                        v->name());
                return;
        }

        if (tchan_) {
                int n;
                double t = Scheduler::instance().clock();
                // XXX: be compatible with nsv1 RED trace entries
                if (*p == 'c') {
                        sprintf(wrk, "Q %g %d", t, int(*((TracedInt*) v)));
                } else {
                        sprintf(wrk, "%c %g %g", *p, t,
                                double(*((TracedDouble*) v)));
                }
                n = strlen(wrk);
                wrk[n] = '\n'; 
                wrk[n+1] = 0;
                (void)Tcl_Write(tchan_, wrk, n+1);
        }
        return; 
}

/* for debugging help */
void RIOQueue::print_edp()
{
        REDQueue::print_edp();
        printf("in_minth: %f, in_maxth: %f\n", edp_in_.th_min, edp_in_.th_max);
        printf("out_minth: %f, out_maxth: %f\n", 
                edp_out_.th_min, edp_out_.th_max);
        printf("qlim: %d, in_idletime: %f\n", qlim_, in_idletime_);
        printf("=========\n");
}

void RIOQueue::print_edv()
{
        REDQueue::print_edv();
        printf("in_v_a: %f, in_v_b: %f\n", edv_in_.v_a, edv_in_.v_b);
        printf("out_v_a: %f, out_v_b: %f\n", edv_out_.v_a, edv_out_.v_b);
}

---