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