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.
 */

/* Bugreport about rio.cc:
 *
 * David Ros and LuiWei have both reported, in June 2002 and in May 2001,
 * that rio.cc has a bug in that RIO does not calculate a new average
 * queue length when an OUT packet arrives.
 * 
 * This bug has not been checked or repaired.
 */

#ifndef lint
static const char rcsid[] =
    "@(#) $Header: /nfs/jade/vint/CVSROOT/ns-2/queue/rio.cc,v 1.12 2004/05/25 03:23:05 sfloyd 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);
}

---