/* -*- 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/red.cc,v 1.80 2004/10/28 23:35:37 haldar Exp $ (LBL)";
#endif
#include <math.h>
#include <sys/types.h>
#include "config.h"
#include "template.h"
#include "random.h"
#include "flags.h"
#include "delay.h"
#include "red.h"
static class REDClass : public TclClass {
public:
REDClass() : TclClass("Queue/RED") {}
TclObject* create(int argc, const char*const* argv) {
//printf("creating RED Queue. argc = %d\n", argc);
//mod to enable RED to take arguments
if (argc==5)
return (new REDQueue(argv[4]));
else
return (new REDQueue("Drop"));
}
} class_red;
/* Strangely this didn't work.
* Seg faulted for child classes.
REDQueue::REDQueue() {
REDQueue("Drop");
}
*/
/*
* modified to enable instantiation with special Trace objects - ratul
*/
REDQueue::REDQueue(const char * trace) : link_(NULL), de_drop_(NULL), EDTrace(NULL), tchan_(0), idle_(1)
{
initParams();
// printf("Making trace type %s\n", trace);
if (strlen(trace) >=20) {
printf("trace type too long - allocate more space to traceType in red.h and recompile\n");
exit(0);
}
strcpy(traceType, trace);
bind_bool("bytes_", &edp_.bytes); // boolean: use bytes?
bind_bool("queue_in_bytes_", &qib_); // boolean: q in bytes?
// _RENAMED("queue-in-bytes_", "queue_in_bytes_");
bind("thresh_", &edp_.th_min_pkts); // minthresh
bind("thresh_queue_", &edp_.th_min);
bind("maxthresh_", &edp_.th_max_pkts); // maxthresh
bind("minthresh_queue_", &edp_.th_max);
bind("mean_pktsize_", &edp_.mean_pktsize); // avg pkt size
bind("idle_pktsize_", &edp_.idle_pktsize); // avg pkt size for idles
bind("q_weight_", &edp_.q_w); // for EWMA
bind("adaptive_", &edp_.adaptive); // 1 for adaptive red
bind("cautious_", &edp_.cautious); // 1 for cautious marking
bind("alpha_", &edp_.alpha); // adaptive red param
bind("beta_", &edp_.beta); // adaptive red param
bind("interval_", &edp_.interval); // adaptive red param
bind("feng_adaptive_",&edp_.feng_adaptive); // adaptive red variant
bind("targetdelay_", &edp_.targetdelay); // target delay
bind("top_", &edp_.top); // maximum for max_p
bind("bottom_", &edp_.bottom); // minimum for max_p
bind_bool("wait_", &edp_.wait);
bind("linterm_", &edp_.max_p_inv);
bind("mark_p_", &edp_.mark_p);
bind_bool("setbit_", &edp_.setbit); // mark instead of drop
bind_bool("gentle_", &edp_.gentle); // increase the packet
// drop prob. slowly
// when ave queue
// exceeds maxthresh
bind_bool("summarystats_", &summarystats_);
bind_bool("drop_tail_", &drop_tail_); // drop last pkt
// _RENAMED("drop-tail_", "drop_tail_");
bind_bool("drop_front_", &drop_front_); // drop first pkt
// _RENAMED("drop-front_", "drop_front_");
bind_bool("drop_rand_", &drop_rand_); // drop pkt at random
// _RENAMED("drop-rand_", "drop_rand_");
bind_bool("ns1_compat_", &ns1_compat_); // ns-1 compatibility
// _RENAMED("ns1-compat_", "ns1_compat_");
bind("ave_", &edv_.v_ave); // average queue sie
bind("prob1_", &edv_.v_prob1); // dropping probability
bind("curq_", &curq_); // current queue size
bind("cur_max_p_", &edv_.cur_max_p); // current max_p
q_ = new PacketQueue(); // underlying queue
pq_ = q_;
//reset();
#ifdef notdef
print_edp();
print_edv();
#endif
}
/*
* Note: if the link bandwidth changes in the course of the
* simulation, the bandwidth-dependent RED parameters do not change.
* This should be fixed, but it would require some extra parameters,
* and didn't seem worth the trouble...
*/
void REDQueue::initialize_params()
{
/*
* If q_weight=0, set it to a reasonable value of 1-exp(-1/C)
* This corresponds to choosing q_weight to be of that value for
* which the packet time constant -1/ln(1-q_weight) per default RTT
* of 100ms is an order of magnitude more than the link capacity, C.
*
* If q_weight=-1, then the queue weight is set to be a function of
* the bandwidth and the link propagation delay. In particular,
* the default RTT is assumed to be three times the link delay and
* transmission delay, if this gives a default RTT greater than 100 ms.
*
* If q_weight=-2, set it to a reasonable value of 1-exp(-10/C).
*/
if (edp_.q_w == 0.0) {
edp_.q_w = 1.0 - exp(-1.0/edp_.ptc);
} else if (edp_.q_w == -1.0) {
double rtt = 3.0*(edp_.delay+1.0/edp_.ptc);
//printf("delay: %5.4f rtt: %5.4f\n", edp_.delay, rtt);
if (rtt < 0.1)
rtt = 0.1;
edp_.q_w = 1.0 - exp(-1.0/(10*rtt*edp_.ptc));
} else if (edp_.q_w == -2.0) {
edp_.q_w = 1.0 - exp(-10.0/edp_.ptc);
}
// printf("ptc: %7.5f bandwidth: %5.3f pktsize: %d\n", edp_.ptc, link_->bandwidth(), edp_.mean_pktsize);
// printf("th_min_pkts: %7.5f th_max_pkts: %7.5f\n", edp_.th_min_pkts, edp_.th_max);
if (edp_.th_min_pkts == 0) {
edp_.th_min_pkts = 5.0;
// set th_min_pkts to half of targetqueue, if this is greater
// than 5 packets.
double targetqueue = edp_.targetdelay * edp_.ptc;
if (edp_.th_min_pkts < targetqueue / 2.0 )
edp_.th_min_pkts = targetqueue / 2.0 ;
}
if (edp_.th_max_pkts == 0)
edp_.th_max_pkts = 3.0 * edp_.th_min_pkts;
//printf("th_min_pkts: %7.5f th_max_pkts: %7.5f\n", edp_.th_min_pkts, edp_.th_max);
//printf("q_w: %7.5f\n", edp_.q_w);
if (edp_.bottom == 0) {
edp_.bottom = 0.01;
// Set bottom to at most 1/W, for W the delay-bandwidth
// product in packets for a connection with this bandwidth,
// 1000-byte packets, and 100 ms RTTs.
// So W = 0.1 * link_->bandwidth() / 8000
double bottom1 = 80000.0/link_->bandwidth();
if (bottom1 < edp_.bottom)
edp_.bottom = bottom1;
//printf("bottom: %9.7f\n", edp_.bottom);
}
}
void REDQueue::initParams()
{
edp_.mean_pktsize = 0;
edp_.idle_pktsize = 0;
edp_.bytes = 0;
edp_.wait = 0;
edp_.setbit = 0;
edp_.gentle = 0;
edp_.th_min = 0.0;
edp_.th_min_pkts = 0.0;
edp_.th_max = 0.0;
edp_.th_max_pkts = 0.0;
edp_.max_p_inv = 0.0;
edp_.mark_p = 0.0;
edp_.q_w = 0.0;
edp_.adaptive = 0;
edp_.cautious = 0;
edp_.alpha = 0.0;
edp_.beta = 0.0;
edp_.interval = 0.0;
edp_.targetdelay = 0.0;
edp_.top = 0.0;
edp_.bottom = 0.0;
edp_.feng_adaptive = 0;
edp_.ptc = 0.0;
edp_.delay = 0.0;
edv_.v_ave = 0.0;
edv_.v_prob1 = 0.0;
edv_.v_slope = 0.0;
edv_.v_prob = 0.0;
edv_.v_a = 0.0;
edv_.v_b = 0.0;
edv_.v_c = 0.0;
edv_.v_d = 0.0;
edv_.count = 0;
edv_.count_bytes = 0;
edv_.old = 0;
edv_.cur_max_p = 1.0;
edv_.lastset = 0;
}
void REDQueue::reset()
{
//printf("3: th_min_pkts: %5.2f\n", edp_.th_min_pkts);
/*
* Compute the "packet time constant" if we know the
* link bandwidth. The ptc is the max number of (avg sized)
* pkts per second which can be placed on the link.
* The link bw is given in bits/sec, so scale mean psize
* accordingly.
*/
if (link_) {
edp_.ptc = link_->bandwidth() / (8. * edp_.mean_pktsize);
initialize_params();
}
if (edp_.th_max_pkts == 0)
edp_.th_max_pkts = 3.0 * edp_.th_min_pkts;
/*
* If queue is measured in bytes, scale min/max thresh
* by the size of an average packet (which is specified by user).
*/
if (qib_) {
//printf("1: th_min in pkts: %5.2f mean_pktsize: %d \n", edp_.th_min_pkts, edp_.mean_pktsize);
edp_.th_min = edp_.th_min_pkts * edp_.mean_pktsize;
edp_.th_max = edp_.th_max_pkts * edp_.mean_pktsize;
//printf("2: th_min in bytes (if qib): %5.2f mean_pktsize: %d \n", edp_.th_min, edp_.mean_pktsize);
} else {
edp_.th_min = edp_.th_min_pkts;
edp_.th_max = edp_.th_max_pkts;
}
edv_.v_ave = 0.0;
edv_.v_slope = 0.0;
edv_.count = 0;
edv_.count_bytes = 0;
edv_.old = 0;
double th_diff = (edp_.th_max - edp_.th_min);
if (th_diff == 0) {
//XXX this last check was added by a person who knows
//nothing of this code just to stop FP div by zero.
//Values for thresholds were equal at time 0. If you
//know what should be here, please cleanup and remove
//this comment.
th_diff = 1.0;
}
edv_.v_a = 1.0 / th_diff;
edv_.cur_max_p = 1.0 / edp_.max_p_inv;
edv_.v_b = - edp_.th_min / th_diff;
edv_.lastset = 0.0;
if (edp_.gentle) {
edv_.v_c = ( 1.0 - edv_.cur_max_p ) / edp_.th_max;
edv_.v_d = 2 * edv_.cur_max_p - 1.0;
}
idle_ = 1;
if (&Scheduler::instance() != NULL)
idletime_ = Scheduler::instance().clock();
else
idletime_ = 0.0; /* sched not instantiated yet */
if (debug_)
printf("Doing a queue reset\n");
Queue::reset();
if (debug_)
printf("Done queue reset\n");
}
/*
* Updating max_p, following code from Feng et al.
* This is only called for Adaptive RED.
* From "A Self-Configuring RED Gateway", from Feng et al.
* They recommend alpha = 3, and beta = 2.
*/
void REDQueue::updateMaxPFeng(double new_ave)
{
if ( edp_.th_min < new_ave && new_ave < edp_.th_max) {
edv_.status = edv_.Between;
}
if (new_ave < edp_.th_min && edv_.status != edv_.Below) {
edv_.status = edv_.Below;
edv_.cur_max_p = edv_.cur_max_p / edp_.alpha;
//double max = edv_.cur_max_p; double param = edp_.alpha;
//printf("max: %5.2f alpha: %5.2f\n", max, param);
}
if (new_ave > edp_.th_max && edv_.status != edv_.Above) {
edv_.status = edv_.Above;
edv_.cur_max_p = edv_.cur_max_p * edp_.beta;
//double max = edv_.cur_max_p; double param = edp_.alpha;
//printf("max: %5.2f beta: %5.2f\n", max, param);
}
}
/*
* Updating max_p to keep the average queue size within the target range.
* This is only called for Adaptive RED.
*/
void REDQueue::updateMaxP(double new_ave, double now)
{
double part = 0.4*(edp_.th_max - edp_.th_min);
// AIMD rule to keep target Q~1/2(th_min+th_max)
if ( new_ave < edp_.th_min + part && edv_.cur_max_p > edp_.bottom) {
// we increase the average queue size, so decrease max_p
edv_.cur_max_p = edv_.cur_max_p * edp_.beta;
edv_.lastset = now;
} else if (new_ave > edp_.th_max - part && edp_.top > edv_.cur_max_p ) {
// we decrease the average queue size, so increase max_p
double alpha = edp_.alpha;
if ( alpha > 0.25*edv_.cur_max_p )
alpha = 0.25*edv_.cur_max_p;
edv_.cur_max_p = edv_.cur_max_p + alpha;
edv_.lastset = now;
}
}
/*
* Compute the average queue size.
* Nqueued can be bytes or packets.
*/
double REDQueue::estimator(int nqueued, int m, double ave, double q_w)
{
double new_ave, old_ave;
new_ave = ave;
while (--m >= 1) {
new_ave *= 1.0 - q_w;
}
old_ave = new_ave;
new_ave *= 1.0 - q_w;
new_ave += q_w * nqueued;
double now = Scheduler::instance().clock();
if (edp_.adaptive == 1) {
if (edp_.feng_adaptive == 1)
updateMaxPFeng(new_ave);
else if (now > edv_.lastset + edp_.interval)
updateMaxP(new_ave, now);
}
return new_ave;
}
/*
* Return the next packet in the queue for transmission.
*/
Packet* REDQueue::deque()
{
Packet *p;
if (summarystats_ && &Scheduler::instance() != NULL) {
Queue::updateStats(qib_?q_->byteLength():q_->length());
}
p = q_->deque();
if (p != 0) {
idle_ = 0;
} else {
idle_ = 1;
// deque() may invoked by Queue::reset at init
// time (before the scheduler is instantiated).
// deal with this case
if (&Scheduler::instance() != NULL)
idletime_ = Scheduler::instance().clock();
else
idletime_ = 0.0;
}
return (p);
}
/*
* Calculate the drop probability.
*/
double
REDQueue::calculate_p_new(double v_ave, double th_max, int gentle, double v_a,
double v_b, double v_c, double v_d, double max_p)
{
double p;
if (gentle && v_ave >= th_max) {
// p ranges from max_p to 1 as the average queue
// size ranges from th_max to twice th_max
p = v_c * v_ave + v_d;
} else {
// p ranges from 0 to max_p as the average queue
// size ranges from th_min to th_max
p = v_a * v_ave + v_b;
p *= max_p;
}
if (p > 1.0)
p = 1.0;
return p;
}
/*
* Calculate the drop probability.
* This is being kept for backwards compatibility.
*/
double
REDQueue::calculate_p(double v_ave, double th_max, int gentle, double v_a,
double v_b, double v_c, double v_d, double max_p_inv)
{
double p = calculate_p_new(v_ave, th_max, gentle, v_a,
v_b, v_c, v_d, 1.0 / max_p_inv);
return p;
}
/*
* Make uniform instead of geometric interdrop periods.
*/
double
REDQueue::modify_p(double p, int count, int count_bytes, int bytes,
int mean_pktsize, int wait, int size)
{
double count1 = (double) count;
if (bytes)
count1 = (double) (count_bytes/mean_pktsize);
if (wait) {
if (count1 * p < 1.0)
p = 0.0;
else if (count1 * p < 2.0)
p /= (2 - count1 * p);
else
p = 1.0;
} else {
if (count1 * p < 1.0)
p /= (1.0 - count1 * p);
else
p = 1.0;
}
if (bytes && p < 1.0) {
p = p * size / mean_pktsize;
}
if (p > 1.0)
p = 1.0;
return p;
}
/*
*
*/
/*
* should the packet be dropped/marked due to a probabilistic drop?
*/
int
REDQueue::drop_early(Packet* pkt)
{
hdr_cmn* ch = hdr_cmn::access(pkt);
edv_.v_prob1 = calculate_p_new(edv_.v_ave, edp_.th_max, edp_.gentle,
edv_.v_a, edv_.v_b, edv_.v_c, edv_.v_d, edv_.cur_max_p);
edv_.v_prob = modify_p(edv_.v_prob1, edv_.count, edv_.count_bytes,
edp_.bytes, edp_.mean_pktsize, edp_.wait, ch->size());
// drop probability is computed, pick random number and act
if (edp_.cautious == 1) {
// Don't drop/mark if the instantaneous queue is much
// below the average.
// For experimental purposes only.
int qsize = qib_?q_->byteLength():q_->length();
// pkts: the number of packets arriving in 50 ms
double pkts = edp_.ptc * 0.05;
double fraction = pow( (1-edp_.q_w), pkts);
// double fraction = 0.9;
if ((double) qsize < fraction * edv_.v_ave) {
// queue could have been empty for 0.05 seconds
// printf("fraction: %5.2f\n", fraction);
return (0);
}
}
double u = Random::uniform();
if (edp_.cautious == 2) {
// Decrease the drop probability if the instantaneous
// queue is much below the average.
// For experimental purposes only.
int qsize = qib_?q_->byteLength():q_->length();
// pkts: the number of packets arriving in 50 ms
double pkts = edp_.ptc * 0.05;
double fraction = pow( (1-edp_.q_w), pkts);
// double fraction = 0.9;
double ratio = qsize / (fraction * edv_.v_ave);
if (ratio < 1.0) {
// printf("ratio: %5.2f\n", ratio);
u *= 1.0 / ratio;
}
}
if (u <= edv_.v_prob) {
// DROP or MARK
edv_.count = 0;
edv_.count_bytes = 0;
hdr_flags* hf = hdr_flags::access(pickPacketForECN(pkt));
if (edp_.setbit && hf->ect() && edv_.v_prob1 < edp_.mark_p) {
hf->ce() = 1; // mark Congestion Experienced bit
// Tell the queue monitor here - call emark(pkt)
return (0); // no drop
} else {
return (1); // drop
}
}
return (0); // no DROP/mark
}
/*
* Pick packet for early congestion notification (ECN). This packet is then
* marked or dropped. Having a separate function do this is convenient for
* supporting derived classes that use the standard RED algorithm to compute
* average queue size but use a different algorithm for choosing the packet for
* ECN notification.
*/
Packet*
REDQueue::pickPacketForECN(Packet* pkt)
{
return pkt; /* pick the packet that just arrived */
}
/*
* Pick packet to drop. Having a separate function do this is convenient for
* supporting derived classes that use the standard RED algorithm to compute
* average queue size but use a different algorithm for choosing the victim.
*/
Packet*
REDQueue::pickPacketToDrop()
{
int victim;
if (drop_front_)
victim = min(1, q_->length()-1);
else if (drop_rand_)
victim = Random::integer(q_->length());
else /* default is drop_tail_ */
victim = q_->length() - 1;
return(q_->lookup(victim));
}
/*
* 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 queue size exceeded some threshold and no
* randomization was used in selecting the packet to be dropped.
* "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 REDQueue::enque(Packet* pkt)
{
/*
* 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;
if (idle_) {
// A packet that arrives to an idle queue will never
// be dropped.
double now = Scheduler::instance().clock();
/* To account for the period when the queue was empty. */
idle_ = 0;
// Use idle_pktsize instead of mean_pktsize, for
// a faster response to idle times.
if (edp_.cautious == 3) {
double ptc = edp_.ptc *
edp_.mean_pktsize / edp_.idle_pktsize;
m = int(ptc * (now - idletime_));
} else
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]
*/
edv_.v_ave = estimator(qib_ ? q_->byteLength() : q_->length(), m + 1, edv_.v_ave, edp_.q_w);
//printf("v_ave: %6.4f (%13.12f) q: %d)\n",
// double(edv_.v_ave), double(edv_.v_ave), q_->length());
if (summarystats_) {
/* compute true average queue size for summary stats */
Queue::updateStats(qib_?q_->byteLength():q_->length());
}
/*
* 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();
/*
* 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;
int droptype = DTYPE_NONE;
int qlen = qib_ ? q_->byteLength() : q_->length();
int qlim = qib_ ? (qlim_ * edp_.mean_pktsize) : qlim_;
curq_ = qlen; // helps to trace queue during arrival, if enabled
if (qavg >= edp_.th_min && qlen > 1) {
if ((!edp_.gentle && qavg >= edp_.th_max) ||
(edp_.gentle && qavg >= 2 * edp_.th_max)) {
droptype = DTYPE_FORCED;
} else if (edv_.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_.count = 1;
edv_.count_bytes = ch->size();
edv_.old = 1;
} else if (drop_early(pkt)) {
droptype = DTYPE_UNFORCED;
}
} else {
/* No packets are being dropped. */
edv_.v_prob = 0.0;
edv_.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);
q_->remove(pkt_to_drop);
pkt = pkt_to_drop; /* XXX okay because pkt is not needed anymore */
}
// deliver to special "edrop" target, if defined
if (de_drop_ != NULL) {
//trace first if asked
// if no snoop object (de_drop_) is defined,
// this packet will not be traced as a special case.
if (EDTrace != NULL)
((Trace *)EDTrace)->recvOnly(pkt);
reportDrop(pkt);
de_drop_->recv(pkt);
}
else {
reportDrop(pkt);
drop(pkt);
}
} else {
/* forced drop, or not a drop: first enqueue pkt */
q_->enque(pkt);
/* drop a packet if we were told to */
if (droptype == DTYPE_FORCED) {
/* drop random victim or last one */
pkt = pickPacketToDrop();
q_->remove(pkt);
reportDrop(pkt);
drop(pkt);
if (!ns1_compat_) {
// bug-fix from Philip Liu, <phill@ece.ubc.ca>
edv_.count = 0;
edv_.count_bytes = 0;
}
}
}
return;
}
int REDQueue::command(int argc, const char*const* argv)
{
Tcl& tcl = Tcl::instance();
if (argc == 2) {
if (strcmp(argv[1], "reset") == 0) {
reset();
return (TCL_OK);
}
if (strcmp(argv[1], "early-drop-target") == 0) {
if (de_drop_ != NULL)
tcl.resultf("%s", de_drop_->name());
return (TCL_OK);
}
if (strcmp(argv[1], "edrop-trace") == 0) {
if (EDTrace != NULL) {
tcl.resultf("%s", EDTrace->name());
if (debug_)
printf("edrop trace exists according to RED\n");
}
else {
if (debug_)
printf("edrop trace doesn't exist according to RED\n");
tcl.resultf("0");
}
return (TCL_OK);
}
if (strcmp(argv[1], "trace-type") == 0) {
tcl.resultf("%s", traceType);
return (TCL_OK);
}
if (strcmp(argv[1], "printstats") == 0) {
print_summarystats();
return (TCL_OK);
}
}
else if (argc == 3) {
// attach a file for variable tracing
if (strcmp(argv[1], "attach") == 0) {
int mode;
const char* id = argv[2];
tchan_ = Tcl_GetChannel(tcl.interp(), (char*)id, &mode);
if (tchan_ == 0) {
tcl.resultf("RED: trace: can't attach %s for writing", id);
return (TCL_ERROR);
}
return (TCL_OK);
}
// tell RED about link stats
if (strcmp(argv[1], "link") == 0) {
LinkDelay* del = (LinkDelay*)TclObject::lookup(argv[2]);
if (del == 0) {
tcl.resultf("RED: no LinkDelay object %s",
argv[2]);
return(TCL_ERROR);
}
// set ptc now
link_ = del;
edp_.ptc = link_->bandwidth() /
(8. * edp_.mean_pktsize);
edp_.delay = link_->delay();
if (
(edp_.q_w <= 0.0 || edp_.th_min_pkts == 0 ||
edp_.th_max_pkts == 0))
initialize_params();
return (TCL_OK);
}
if (strcmp(argv[1], "early-drop-target") == 0) {
NsObject* p = (NsObject*)TclObject::lookup(argv[2]);
if (p == 0) {
tcl.resultf("no object %s", argv[2]);
return (TCL_ERROR);
}
de_drop_ = p;
return (TCL_OK);
}
if (strcmp(argv[1], "edrop-trace") == 0) {
if (debug_)
printf("Ok, Here\n");
NsObject * t = (NsObject *)TclObject::lookup(argv[2]);
if (debug_)
printf("Ok, Here too\n");
if (t == 0) {
tcl.resultf("no object %s", argv[2]);
return (TCL_ERROR);
}
EDTrace = t;
if (debug_)
printf("Ok, Here too too too %d\n", ((Trace *)EDTrace)->type_);
return (TCL_OK);
}
if (!strcmp(argv[1], "packetqueue-attach")) {
delete q_;
if (!(q_ = (PacketQueue*) TclObject::lookup(argv[2])))
return (TCL_ERROR);
else {
pq_ = q_;
return (TCL_OK);
}
}
}
return (Queue::command(argc, argv));
}
/*
* 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
REDQueue::trace(TracedVar* v)
{
char wrk[500], *p;
if (((p = strstr(v->name(), "ave")) == NULL) &&
((p = strstr(v->name(), "prob")) == NULL) &&
((p = strstr(v->name(), "curq")) == NULL) &&
((p = strstr(v->name(), "cur_max_p"))==NULL) ) {
fprintf(stderr, "RED: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 (strstr(v->name(), "curq") != NULL) {
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 REDQueue::print_edp()
{
printf("mean_pktsz: %d\n", edp_.mean_pktsize);
printf("bytes: %d, wait: %d, setbit: %d\n",
edp_.bytes, edp_.wait, edp_.setbit);
printf("minth: %f, maxth: %f\n", edp_.th_min, edp_.th_max);
printf("max_p: %f, qw: %f, ptc: %f\n",
(double) edv_.cur_max_p, edp_.q_w, edp_.ptc);
printf("qlim: %d, idletime: %f\n", qlim_, idletime_);
printf("=========\n");
}
void REDQueue::print_edv()
{
printf("v_a: %f, v_b: %f\n", edv_.v_a, edv_.v_b);
}
void REDQueue::print_summarystats()
{
//double now = Scheduler::instance().clock();
printf("True average queue: %5.3f", true_ave_);
if (qib_)
printf(" (in bytes)");
printf(" time: %5.3f\n", total_time_);
}
/************************************************************/
/*
* This procedure is obsolete, and only included for backward compatibility.
* The new procedure is REDQueue::estimator
*/
/*
* Compute the average queue size.
* The code contains two alternate methods for this, the plain EWMA
* and the Holt-Winters method.
* nqueued can be bytes or packets
*/
void REDQueue::run_estimator(int nqueued, int m)
{
double f, f_sl, f_old;
f = edv_.v_ave;
f_sl = edv_.v_slope;
#define RED_EWMA
#ifdef RED_EWMA
while (--m >= 1) {
f_old = f;
f *= 1.0 - edp_.q_w;
}
f_old = f;
f *= 1.0 - edp_.q_w;
f += edp_.q_w * nqueued;
#endif
#ifdef RED_HOLT_WINTERS
while (--m >= 1) {
f_old = f;
f += f_sl;
f *= 1.0 - edp_.q_w;
f_sl *= 1.0 - 0.5 * edp_.q_w;
f_sl += 0.5 * edp_.q_w * (f - f_old);
}
f_old = f;
f += f_sl;
f *= 1.0 - edp_.q_w;
f += edp_.q_w * nqueued;
f_sl *= 1.0 - 0.5 * edp_.q_w;
f_sl += 0.5 * edp_.q_w * (f - f_old);
#endif
edv_.v_ave = f;
edv_.v_slope = f_sl;
}
syntax highlighted by Code2HTML, v. 0.9.1