00001 /* -*- Mode:C++; c-basic-offset:8; tab-width:8; indent-tabs-mode:t -*- */ 00002 /* 00003 * Copyright (c) 1990-1997 Regents of the University of California. 00004 * All rights reserved. 00005 * 00006 * Redistribution and use in source and binary forms, with or without 00007 * modification, are permitted provided that the following conditions 00008 * are met: 00009 * 1. Redistributions of source code must retain the above copyright 00010 * notice, this list of conditions and the following disclaimer. 00011 * 2. Redistributions in binary form must reproduce the above copyright 00012 * notice, this list of conditions and the following disclaimer in the 00013 * documentation and/or other materials provided with the distribution. 00014 * 3. All advertising materials mentioning features or use of this software 00015 * must display the following acknowledgement: 00016 * This product includes software developed by the Computer Systems 00017 * Engineering Group at Lawrence Berkeley Laboratory. 00018 * 4. Neither the name of the University nor of the Laboratory may be used 00019 * to endorse or promote products derived from this software without 00020 * specific prior written permission. 00021 * 00022 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 00023 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 00024 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 00025 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 00026 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 00027 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 00028 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 00029 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 00030 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 00031 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 00032 * SUCH DAMAGE. 00033 * 00034 * 00035 * Here is one set of parameters from one of my simulations: 00036 * 00037 * ed [ q_weight=0.002 thresh=5 linterm=30 maxthresh=15 00038 * mean_pktsize=500 dropmech=random-drop queue-size=60 00039 * plot-file=none bytes=false doubleq=false dqthresh=50 00040 * wait=true ] 00041 * 00042 * 1/"linterm" is the max probability of dropping a packet. 00043 * There are different options that make the code 00044 * more messy that it would otherwise be. For example, 00045 * "doubleq" and "dqthresh" are for a queue that gives priority to 00046 * small (control) packets, 00047 * "bytes" indicates whether the queue should be measured in bytes 00048 * or in packets, 00049 * "dropmech" indicates whether the drop function should be random-drop 00050 * or drop-tail when/if the queue overflows, and 00051 * the commented-out Holt-Winters method for computing the average queue 00052 * size can be ignored. 00053 * "wait" indicates whether the gateway should wait between dropping 00054 * packets. 00055 * 00056 * @(#) $Header: /cvsroot/nsnam/ns-2/queue/red.h,v 1.45 2007/07/03 02:11:34 sallyfloyd Exp $ (LBL) 00057 */ 00058 00059 #ifndef ns_red_h 00060 #define ns_red_h 00061 00062 #include "queue.h" 00063 00064 #include "trace.h" 00065 class LinkDelay; 00066 00067 /* 00068 * Early drop parameters, supplied by user 00069 */ 00070 struct edp { 00071 /* 00072 * User supplied. 00073 */ 00074 int mean_pktsize; /* avg pkt size, linked into Tcl */ 00075 int idle_pktsize; /* avg pkt size used during idle times */ 00076 int bytes; /* true if queue in bytes, false if packets */ 00077 int wait; /* true for waiting between dropped packets */ 00078 int setbit; /* true to set congestion indication bit */ 00079 int gentle; /* true to increases dropping prob. slowly * 00080 * when ave queue exceeds maxthresh. */ 00081 double th_min; /* minimum threshold of average queue size */ 00082 double th_min_pkts; /* always maintained in packets */ 00083 double th_max; /* maximum threshold of average queue size */ 00084 double th_max_pkts; /* always maintained in packets */ 00085 double max_p_inv; /* 1/max_p, for max_p = maximum prob. */ 00086 /* adaptive RED: the initial max_p_inv */ 00087 double mark_p; /* when p < mark_p, mark chosen packets */ 00088 /* when p > mark_p, drop chosen packets */ 00089 int use_mark_p; /* use mark_p only for deciding when to drop, */ 00090 /* if queue is not full */ 00091 /* Set use_mark_p true and set mark_p to 2.0 */ 00092 /* to always mark instead of drop */ 00093 /* when queue is not full */ 00094 double q_w; /* queue weight given to cur q size sample */ 00095 int adaptive; /* 0 for default RED */ 00096 /* 1 for adaptive RED, adapting max_p */ 00097 int cautious; /* 0 for default RED */ 00098 /* 1 for not dropping/marking when the */ 00099 /* instantaneous queue is much below the */ 00100 /* average */ 00101 double alpha; /* adaptive RED: additive param for max_p */ 00102 double beta; /* adaptive RED: multip param for max_p */ 00103 double interval; /* adaptive RED: interval for adaptations */ 00104 double targetdelay; /* adaptive RED: target queue size */ 00105 double top; /* adaptive RED: upper bound for max_p */ 00106 double bottom; /* adaptive RED: lower bound for max_p */ 00107 /* 0 for automatic setting */ 00108 int feng_adaptive; /* adaptive RED: Use the Feng et al. version */ 00109 00110 /* 00111 * Computed as a function of user supplied paramters. 00112 */ 00113 double ptc; /* packet time constant in packets/second */ 00114 double delay; /* link delay */ 00115 }; 00116 00117 /* 00118 * Early drop variables, maintained by RED 00119 */ 00120 struct edv { 00121 TracedDouble v_ave; /* average queue size */ 00122 TracedDouble v_prob1; /* prob. of packet drop before "count". */ 00123 double v_slope; /* used in computing average queue size */ 00124 /* obsolete */ 00125 double v_prob; /* prob. of packet drop */ 00126 double v_a; /* v_prob = v_a * v_ave + v_b */ 00127 double v_b; 00128 double v_c; /* used for "gentle" mode */ 00129 double v_d; /* used for "gentle" mode */ 00130 int count; /* # of packets since last drop */ 00131 int count_bytes; /* # of bytes since last drop */ 00132 int old; /* 0 when average queue first exceeds thresh */ 00133 TracedDouble cur_max_p; //current max_p 00134 double lastset; /* adaptive RED: last time adapted */ 00135 enum Status {Above, Below, Between}; // for use in Feng's Adaptive RED 00136 Status status; 00137 //edv() : v_ave(0.0), v_prob1(0.0), v_slope(0.0), v_prob(0.0), 00138 //v_a(0.0), v_b(0.0), v_c(0.0), v_d(0.0), count(0), 00139 // count_bytes(0), old(0), cur_max_p(1.0) { } 00140 }; 00141 00142 class REDQueue : public Queue { 00143 public: 00144 /* REDQueue();*/ 00145 REDQueue(const char * = "Drop"); 00146 protected: 00147 void initParams(); 00148 int command(int argc, const char*const* argv); 00149 void enque(Packet* pkt); 00150 virtual Packet *pickPacketForECN(Packet* pkt); 00151 virtual Packet *pickPacketToDrop(); 00152 Packet* deque(); 00153 void initialize_params(); 00154 void reset(); 00155 void run_estimator(int nqueued, int m); /* Obsolete */ 00156 double estimator(int nqueued, int m, double ave, double q_w); 00157 void updateMaxP(double new_ave, double now); 00158 void updateMaxPFeng(double new_ave); 00159 int drop_early(Packet* pkt); 00160 double modify_p(double p, int count, int count_bytes, int bytes, 00161 int mean_pktsize, int wait, int size); 00162 double calculate_p_new(double v_ave, double th_max, int gentle, 00163 double v_a, double v_b, double v_c, double v_d, double max_p); 00164 double calculate_p(double v_ave, double th_max, int gentle, 00165 double v_a, double v_b, double v_c, double v_d, double max_p_inv); 00166 virtual void reportDrop(Packet *pkt) {} //pushback 00167 void print_summarystats(); 00168 00169 00170 int summarystats_; /* true to print true average queue size */ 00171 00172 LinkDelay* link_; /* outgoing link */ 00173 int fifo_; /* fifo queue? */ 00174 PacketQueue *q_; /* underlying (usually) FIFO queue */ 00175 00176 int bcount_() { return q_->byteLength(); }; 00177 /* OBSOLETED - USE q_->byteLength() INSTEAD */ 00178 int qib_; /* bool: queue measured in bytes? */ 00179 NsObject* de_drop_; /* drop_early target */ 00180 00181 //added to be able to trace EDrop Objects - ratul 00182 //the other events - forced drop, enque and deque are traced by a different mechanism. 00183 NsObject * EDTrace; //early drop trace 00184 char traceType[20]; //the preferred type for early drop trace. 00185 //better be less than 19 chars long 00186 00187 Tcl_Channel tchan_; /* place to write trace records */ 00188 TracedInt curq_; /* current qlen seen by arrivals */ 00189 void trace(TracedVar*); /* routine to write trace records */ 00190 00191 /* 00192 * Static state. 00193 */ 00194 int drop_tail_; /* drop-tail */ 00195 int drop_front_; /* drop-from-front */ 00196 int drop_rand_; /* drop-tail, or drop random? */ 00197 int ns1_compat_; /* for ns-1 compatibility, bypass a */ 00198 /* small bugfix */ 00199 00200 edp edp_; /* early-drop params */ 00201 int doubleq_; /* for experiments with priority for small packets */ 00202 int dqthresh_; /* for experiments with priority for small packets */ 00203 00204 /* 00205 * Dynamic state. 00206 */ 00207 int idle_; /* queue is idle? */ 00208 double idletime_; /* if so, since this time */ 00209 edv edv_; /* early-drop variables */ 00210 int first_reset_; /* first time reset() is called */ 00211 00212 void print_edp(); // for debugging 00213 void print_edv(); // for debugging 00214 00215 }; 00216 00217 #endif