开通博客赚积分
发布资源赚积分
分类

源码开发语言/平台
当前位置：首页 > 源码/资料 > Windows编程 > 通讯编程 > 查看源码
red.cc
资源名称：ns-allinone-2.33.tar.gz　[点击查看]
上传用户：rrhhcc
上传日期：2015-12-11
资源大小：54129k
文件大小：29k
源码类别：

通讯编程

开发平台：

Visual C++

red.cc：源码内容
  1.  /* -*- Mode:C++; c-basic-offset:8; tab-width:8; indent-tabs-mode:t -*- */
  2. /*
  3.  * Copyright (c) 1990-1997 Regents of the University of California.
  4.  * All rights reserved.
  5.  *
  6.  * Redistribution and use in source and binary forms, with or without
  7.  * modification, are permitted provided that the following conditions
  8.  * are met:
  9.  * 1. Redistributions of source code must retain the above copyright
  10.  *    notice, this list of conditions and the following disclaimer.
  11.  * 2. Redistributions in binary form must reproduce the above copyright
  12.  *    notice, this list of conditions and the following disclaimer in the
  13.  *    documentation and/or other materials provided with the distribution.
  14.  * 3. All advertising materials mentioning features or use of this software
  15.  *    must display the following acknowledgement:
  16.  * This product includes software developed by the Computer Systems
  17.  * Engineering Group at Lawrence Berkeley Laboratory.
  18.  * 4. Neither the name of the University nor of the Laboratory may be used
  19.  *    to endorse or promote products derived from this software without
  20.  *    specific prior written permission.
  21.  *
  22.  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  23.  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  24.  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  25.  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  26.  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  27.  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  28.  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  29.  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  30.  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  31.  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  32.  * SUCH DAMAGE.
  33.  *
  34.  *
  35.  * Here is one set of parameters from one of Sally's simulations
  36.  * (this is from tcpsim, the older simulator):
  37.  * 
  38.  * ed [ q_weight=0.002 thresh=5 linterm=30 maxthresh=15
  39.  *         mean_pktsize=500 dropmech=random-drop queue-size=60
  40.  *         plot-file=none bytes=false doubleq=false dqthresh=50 
  41.  *    wait=true ]
  42.  * 
  43.  * 1/"linterm" is the max probability of dropping a packet. 
  44.  * There are different options that make the code
  45.  * more messy that it would otherwise be.  For example,
  46.  * "doubleq" and "dqthresh" are for a queue that gives priority to
  47.  *   small (control) packets, 
  48.  * "bytes" indicates whether the queue should be measured in bytes 
  49.  *   or in packets, 
  50.  * "dropmech" indicates whether the drop function should be random-drop 
  51.  *   or drop-tail when/if the queue overflows, and 
  52.  *   the commented-out Holt-Winters method for computing the average queue 
  53.  *   size can be ignored.
  54.  * "wait" indicates whether the gateway should wait between dropping
  55.  *   packets.
  56.  */
  58. #ifndef lint
  59. static const char rcsid[] =
  60.      "@(#) $Header: /cvsroot/nsnam/ns-2/queue/red.cc,v 1.88 2007/10/23 06:55:54 seashadow Exp $ (LBL)";
  61. #endif
  63. #include <math.h>
  64. #include <sys/types.h>
  65. #include "config.h"
  66. #include "template.h"
  67. #include "random.h"
  68. #include "flags.h"
  69. #include "delay.h"
  70. #include "red.h"
  72. static class REDClass : public TclClass {
  73. public:
  74. REDClass() : TclClass("Queue/RED") {}
  75. TclObject* create(int argc, const char*const* argv) {
  76. //printf("creating RED Queue. argc = %dn", argc);
  78. //mod to enable RED to take arguments
  79. if (argc==5) 
  80. return (new REDQueue(argv[4]));
  81. else
  82. return (new REDQueue("Drop"));
  83. }
  84. } class_red;
  86. /* Strangely this didn't work. 
  87.  * Seg faulted for child classes.
  88. REDQueue::REDQueue() { 
  89. REDQueue("Drop");
  90. }
  91. */
  93. /*
  94.  * modified to enable instantiation with special Trace objects - ratul
  95.  */
  96. REDQueue::REDQueue(const char * trace) : link_(NULL), de_drop_(NULL), EDTrace(NULL), tchan_(0), idle_(1), idletime_(0.0)
  97. {
  98. initParams();
  100. // printf("Making trace type %sn", trace);
  101. if (strlen(trace) >=20) {
  102. printf("trace type too long - allocate more space to traceType in red.h and recompilen");
  103. exit(0);
  104. }
  105. strcpy(traceType, trace);
  106. bind_bool("bytes_", &edp_.bytes);     // boolean: use bytes?
  107. bind_bool("queue_in_bytes_", &qib_);     // boolean: q in bytes?
  108. // _RENAMED("queue-in-bytes_", "queue_in_bytes_");
  110. bind("thresh_", &edp_.th_min_pkts);     // minthresh
  111. bind("thresh_queue_", &edp_.th_min);
  112. bind("maxthresh_", &edp_.th_max_pkts);     // maxthresh
  113. bind("maxthresh_queue_", &edp_.th_max);
  114. bind("mean_pktsize_", &edp_.mean_pktsize);  // avg pkt size
  115. bind("idle_pktsize_", &edp_.idle_pktsize);  // avg pkt size for idles
  116. bind("q_weight_", &edp_.q_w);     // for EWMA
  117. bind("adaptive_", &edp_.adaptive);          // 1 for adaptive red
  118. bind("cautious_", &edp_.cautious);          // 1 for cautious marking
  119. bind("alpha_", &edp_.alpha);         // adaptive red param
  120. bind("beta_", &edp_.beta);                  // adaptive red param
  121. bind("interval_", &edp_.interval);     // adaptive red param
  122. bind("feng_adaptive_",&edp_.feng_adaptive); // adaptive red variant
  123. bind("targetdelay_", &edp_.targetdelay);    // target delay
  124. bind("top_", &edp_.top);     // maximum for max_p
  125. bind("bottom_", &edp_.bottom);     // minimum for max_p
  126. bind_bool("wait_", &edp_.wait);
  127. bind("linterm_", &edp_.max_p_inv);
  128. bind("mark_p_", &edp_.mark_p);
  129. bind_bool("use_mark_p_", &edp_.use_mark_p);
  130. bind_bool("setbit_", &edp_.setbit);     // mark instead of drop
  131. bind_bool("gentle_", &edp_.gentle);         // increase the packet
  132.     // drop prob. slowly
  133.     // when ave queue
  134.     // exceeds maxthresh
  136. bind_bool("summarystats_", &summarystats_);
  137. bind_bool("drop_tail_", &drop_tail_);     // drop last pkt
  138. // _RENAMED("drop-tail_", "drop_tail_");
  140. bind_bool("drop_front_", &drop_front_);     // drop first pkt
  141. // _RENAMED("drop-front_", "drop_front_");
  143. bind_bool("drop_rand_", &drop_rand_);     // drop pkt at random
  144. // _RENAMED("drop-rand_", "drop_rand_");
  146. bind_bool("ns1_compat_", &ns1_compat_);     // ns-1 compatibility
  147. // _RENAMED("ns1-compat_", "ns1_compat_");
  149. bind("ave_", &edv_.v_ave);     // average queue sie
  150. bind("prob1_", &edv_.v_prob1);     // dropping probability
  151. bind("curq_", &curq_);     // current queue size
  152. bind("cur_max_p_", &edv_.cur_max_p);        // current max_p
  155. q_ = new PacketQueue();     // underlying queue
  156. pq_ = q_;
  157. //reset();
  158. #ifdef notdef
  159. print_edp();
  160. print_edv();
  161. #endif
  163. }
  166. /*
  167.  * Note: if the link bandwidth changes in the course of the
  168.  * simulation, the bandwidth-dependent RED parameters do not change.
  169.  * This should be fixed, but it would require some extra parameters,
  170.  * and didn't seem worth the trouble...
  171.  */
  172. void REDQueue::initialize_params()
  173. {
  174. /*
  175.  * If q_weight=0, set it to a reasonable value of 1-exp(-1/C)
  176.  * This corresponds to choosing q_weight to be of that value for
  177.  * which the packet time constant -1/ln(1-q_weight) per default RTT 
  178.  * of 100ms is an order of magnitude more than the link capacity, C.
  179.  *
  180.  * If q_weight=-1, then the queue weight is set to be a function of
  181.  * the bandwidth and the link propagation delay.  In particular, 
  182.  * the default RTT is assumed to be three times the link delay and 
  183.  * transmission delay, if this gives a default RTT greater than 100 ms. 
  184.  *
  185.  * If q_weight=-2, set it to a reasonable value of 1-exp(-10/C).
  186.  */
  187. if (edp_.q_w == 0.0) {
  188. edp_.q_w = 1.0 - exp(-1.0/edp_.ptc);
  189.   } else if (edp_.q_w == -1.0) {
  190. double rtt = 3.0*(edp_.delay+1.0/edp_.ptc);
  191. //printf("delay: %5.4f rtt: %5.4fn", edp_.delay, rtt);
  192. if (rtt < 0.1) 
  193. rtt = 0.1;
  194. edp_.q_w = 1.0 - exp(-1.0/(10*rtt*edp_.ptc));
  195. } else if (edp_.q_w == -2.0) {
  196. edp_.q_w = 1.0 - exp(-10.0/edp_.ptc);
  197. }
  199. // printf("ptc: %7.5f bandwidth: %5.3f pktsize: %dn", edp_.ptc, link_->bandwidth(), edp_.mean_pktsize);
  200.         // printf("th_min_pkts: %7.5f th_max_pkts: %7.5fn", edp_.th_min_pkts, edp_.th_max);
  201. if (edp_.th_min_pkts == 0) {
  202. edp_.th_min_pkts = 5.0;
  203. // set th_min_pkts to half of targetqueue, if this is greater
  204. //  than 5 packets.
  205. double targetqueue = edp_.targetdelay * edp_.ptc;
  206. if (edp_.th_min_pkts < targetqueue / 2.0 )
  207. edp_.th_min_pkts = targetqueue / 2.0 ;
  208.         }
  209. if (edp_.th_max_pkts == 0) 
  210. edp_.th_max_pkts = 3.0 * edp_.th_min_pkts;
  211.         //printf("th_min_pkts: %7.5f th_max_pkts: %7.5fn", edp_.th_min_pkts, edp_.th_max);
  212. //printf("q_w: %7.5fn", edp_.q_w);
  213. if (edp_.bottom == 0) {
  214. edp_.bottom = 0.01;
  215. // Set bottom to at most 1/W, for W the delay-bandwidth 
  216. //   product in packets for a connection with this bandwidth,
  217. //   1000-byte packets, and 100 ms RTTs.
  218. // So W = 0.1 * link_->bandwidth() / 8000 
  219. double bottom1 = 80000.0/link_->bandwidth();
  220. if (bottom1 < edp_.bottom) 
  221. edp_.bottom = bottom1;
  222. //printf("bottom: %9.7fn", edp_.bottom);
  223. }
  224. }
  226. void REDQueue::initParams() 
  227. {
  228. edp_.mean_pktsize = 0;
  229. edp_.idle_pktsize = 0;
  230. edp_.bytes = 0;
  231. edp_.wait = 0;
  232. edp_.setbit = 0;
  233. edp_.gentle = 0;
  234. edp_.th_min = 0.0;
  235. edp_.th_min_pkts = 0.0;
  236. edp_.th_max = 0.0;
  237. edp_.th_max_pkts = 0.0;
  238. edp_.max_p_inv = 0.0;
  239. edp_.q_w = 0.0;
  240. edp_.adaptive = 0;
  241. edp_.cautious = 0;
  242. edp_.alpha = 0.0;
  243. edp_.beta = 0.0;
  244. edp_.interval = 0.0;
  245. edp_.targetdelay = 0.0;
  246. edp_.top = 0.0;
  247. edp_.bottom = 0.0;
  248. edp_.feng_adaptive = 0;
  249. edp_.ptc = 0.0;
  250. edp_.delay = 0.0;
  252. edv_.v_ave = 0.0;
  253. edv_.v_prob1 = 0.0;
  254. edv_.v_slope = 0.0;
  255. edv_.v_prob = 0.0;
  256. edv_.v_a = 0.0;
  257. edv_.v_b = 0.0;
  258. edv_.v_c = 0.0;
  259. edv_.v_d = 0.0;
  260. edv_.count = 0;
  261. edv_.count_bytes = 0;
  262. edv_.old = 0;
  263. edv_.cur_max_p = 1.0;
  264. edv_.lastset = 0;
  265. }
  268. void REDQueue::reset()
  269. {
  271.         //printf("3: th_min_pkts: %5.2fn", edp_.th_min_pkts); 
  272. /*
  273.  * Compute the "packet time constant" if we know the
  274.  * link bandwidth.  The ptc is the max number of (avg sized)
  275.  * pkts per second which can be placed on the link.
  276.  * The link bw is given in bits/sec, so scale mean psize
  277.  * accordingly.
  278.  */
  279.         if (link_) {
  280. edp_.ptc = link_->bandwidth() / (8.0 * edp_.mean_pktsize);
  281. initialize_params();
  282. }
  283. if (edp_.th_max_pkts == 0) 
  284. edp_.th_max_pkts = 3.0 * edp_.th_min_pkts;
  285. /*
  286.  * If queue is measured in bytes, scale min/max thresh
  287.  * by the size of an average packet (which is specified by user).
  288.  */
  289.         if (qib_) {
  290. //printf("1: th_min in pkts: %5.2f mean_pktsize: %d n", edp_.th_min_pkts, edp_.mean_pktsize); 
  291.                 edp_.th_min = edp_.th_min_pkts * edp_.mean_pktsize;  
  292.                 edp_.th_max = edp_.th_max_pkts * edp_.mean_pktsize;
  293. //printf("2: th_min in bytes (if qib): %5.2f mean_pktsize: %d n", edp_.th_min, edp_.mean_pktsize); 
  294.         } else {
  295. edp_.th_min = edp_.th_min_pkts;
  296. edp_.th_max = edp_.th_max_pkts;
  297. }
  298.  
  299. edv_.v_ave = 0.0;
  300. edv_.v_slope = 0.0;
  301. edv_.count = 0;
  302. edv_.count_bytes = 0;
  303. edv_.old = 0;
  304. double th_diff = (edp_.th_max - edp_.th_min);
  305. if (th_diff == 0) { 
  306. //XXX this last check was added by a person who knows
  307. //nothing of this code just to stop FP div by zero.
  308. //Values for thresholds were equal at time 0.  If you
  309. //know what should be here, please cleanup and remove
  310. //this comment.
  311. th_diff = 1.0; 
  312. }
  313. edv_.v_a = 1.0 / th_diff;
  314. edv_.cur_max_p = 1.0 / edp_.max_p_inv;
  315. edv_.v_b = - edp_.th_min / th_diff;
  316. edv_.lastset = 0.0;
  317. if (edp_.gentle) {
  318. edv_.v_c = ( 1.0 - edv_.cur_max_p ) / edp_.th_max;
  319. edv_.v_d = 2.0 * edv_.cur_max_p - 1.0;
  320. }
  322. idle_ = 1;
  323. if (&Scheduler::instance() != NULL)
  324. idletime_ = Scheduler::instance().clock();
  325. else
  326. idletime_ = 0.0; /* sched not instantiated yet */
  328. if (debug_) 
  329. printf("Doing a queue resetn");
  330. Queue::reset();
  331. if (debug_) 
  332. printf("Done queue resetn");
  333. }
  335. /*
  336.  *  Updating max_p, following code from Feng et al. 
  337.  *  This is only called for Adaptive RED.
  338.  *  From "A Self-Configuring RED Gateway", from Feng et al.
  339.  *  They recommend alpha = 3, and beta = 2.
  340.  */
  341. void REDQueue::updateMaxPFeng(double new_ave)
  342. {
  343. if ( edp_.th_min < new_ave && new_ave < edp_.th_max) {
  344. edv_.status = edv_.Between;
  345. }
  346. if (new_ave < edp_.th_min && edv_.status != edv_.Below) {
  347. edv_.status = edv_.Below;
  348. edv_.cur_max_p = edv_.cur_max_p / edp_.alpha;
  349. //double max = edv_.cur_max_p; double param = edp_.alpha;
  350. //printf("max: %5.2f alpha: %5.2fn", max, param);
  351. }
  352. if (new_ave > edp_.th_max && edv_.status != edv_.Above) {
  353. edv_.status = edv_.Above;
  354. edv_.cur_max_p = edv_.cur_max_p * edp_.beta;
  355. //double max = edv_.cur_max_p; double param = edp_.alpha;
  356. //printf("max: %5.2f beta: %5.2fn", max, param);
  357. }
  358. }
  360. /*
  361.  *  Updating max_p to keep the average queue size within the target range.
  362.  *  This is only called for Adaptive RED.
  363.  */
  364. void REDQueue::updateMaxP(double new_ave, double now)
  365. {
  366. double part = 0.4*(edp_.th_max - edp_.th_min);
  367. // AIMD rule to keep target Q~1/2(th_min+th_max)
  368. if ( new_ave < edp_.th_min + part && edv_.cur_max_p > edp_.bottom) {
  369. // we increase the average queue size, so decrease max_p
  370. edv_.cur_max_p = edv_.cur_max_p * edp_.beta;
  371. edv_.lastset = now;
  372. } else if (new_ave > edp_.th_max - part && edp_.top > edv_.cur_max_p ) {
  373. // we decrease the average queue size, so increase max_p
  374. double alpha = edp_.alpha;
  375.                         if ( alpha > 0.25*edv_.cur_max_p )
  376. alpha = 0.25*edv_.cur_max_p;
  377. edv_.cur_max_p = edv_.cur_max_p + alpha;
  378. edv_.lastset = now;
  379. } 
  380. }
  382. /*
  383.  * Compute the average queue size.
  384.  * Nqueued can be bytes or packets.
  385.  */
  386. double REDQueue::estimator(int nqueued, int m, double ave, double q_w)
  387. {
  388. double new_ave, old_ave;
  390. new_ave = ave;
  391. while (--m >= 1) {
  392. new_ave *= 1.0 - q_w;
  393. }
  394. old_ave = new_ave;
  395. new_ave *= 1.0 - q_w;
  396. new_ave += q_w * nqueued;
  398. double now = Scheduler::instance().clock();
  399. if (edp_.adaptive == 1) {
  400. if (edp_.feng_adaptive == 1)
  401. updateMaxPFeng(new_ave);
  402. else if (now > edv_.lastset + edp_.interval)
  403. updateMaxP(new_ave, now);
  404. }
  405. return new_ave;
  406. }
  408. /*
  409.  * Return the next packet in the queue for transmission.
  410.  */
  411. Packet* REDQueue::deque()
  412. {
  413. Packet *p;
  414. if (summarystats_ && &Scheduler::instance() != NULL) {
  415. Queue::updateStats(qib_?q_->byteLength():q_->length());
  416. }
  417. p = q_->deque();
  418. if (p != 0) {
  419. idle_ = 0;
  420. } else {
  421. idle_ = 1;
  422. // deque() may invoked by Queue::reset at init
  423. // time (before the scheduler is instantiated).
  424. // deal with this case
  425. if (&Scheduler::instance() != NULL)
  426. idletime_ = Scheduler::instance().clock();
  427. else
  428. idletime_ = 0.0;
  429. }
  430. return (p);
  431. }
  433. /*
  434.  * Calculate the drop probability.
  435.  */
  436. double
  437. REDQueue::calculate_p_new(double v_ave, double th_max, int gentle, double v_a, 
  438. double v_b, double v_c, double v_d, double max_p)
  439. {
  440. double p;
  441. if (gentle && v_ave >= th_max) {
  442. // p ranges from max_p to 1 as the average queue
  443. // size ranges from th_max to twice th_max 
  444. p = v_c * v_ave + v_d;
  445.         } else if (!gentle && v_ave >= th_max) { 
  446.                 // OLD: p continues to range linearly above max_p as
  447.                 // the average queue size ranges above th_max.
  448.                 // NEW: p is set to 1.0 
  449.                 p = 1.0;
  450.         } else {
  451.                 // p ranges from 0 to max_p as the average queue
  452.                 // size ranges from th_min to th_max 
  453.                 p = v_a * v_ave + v_b;
  454.                 // p = (v_ave - th_min) / (th_max - th_min)
  455.                 p *= max_p; 
  456.         }
  457. if (p > 1.0)
  458. p = 1.0;
  459. return p;
  460. }
  462. /*
  463.  * Calculate the drop probability.
  464.  * This is being kept for backwards compatibility.
  465.  */
  466. double
  467. REDQueue::calculate_p(double v_ave, double th_max, int gentle, double v_a, 
  468. double v_b, double v_c, double v_d, double max_p_inv)
  469. {
  470. double p = calculate_p_new(v_ave, th_max, gentle, v_a,
  471. v_b, v_c, v_d, 1.0 / max_p_inv);
  472. return p;
  473. }
  475. /*
  476.  * Make uniform instead of geometric interdrop periods.
  477.  */
  478. double
  479. REDQueue::modify_p(double p, int count, int count_bytes, int bytes, 
  480.    int mean_pktsize, int wait, int size)
  481. {
  482. double count1 = (double) count;
  483. if (bytes)
  484. count1 = (double) (count_bytes/mean_pktsize);
  485. if (wait) {
  486. if (count1 * p < 1.0)
  487. p = 0.0;
  488. else if (count1 * p < 2.0)
  489. p /= (2.0 - count1 * p);
  490. else
  491. p = 1.0;
  492. } else {
  493. if (count1 * p < 1.0)
  494. p /= (1.0 - count1 * p);
  495. else
  496. p = 1.0;
  497. }
  498. if (bytes && p < 1.0) {
  499. p = (p * size) / mean_pktsize;
  500. //p = p * (size / mean_pktsize);
  502. }
  503. if (p > 1.0)
  504. p = 1.0;
  505.   return p;
  506. }
  508. /*
  509.  * 
  510.  */
  512. /*
  513.  * should the packet be dropped/marked due to a probabilistic drop?
  514.  */
  515. int
  516. REDQueue::drop_early(Packet* pkt)
  517. {
  518. hdr_cmn* ch = hdr_cmn::access(pkt);
  520. edv_.v_prob1 = calculate_p_new(edv_.v_ave, edp_.th_max, edp_.gentle, 
  521.      edv_.v_a, edv_.v_b, edv_.v_c, edv_.v_d, edv_.cur_max_p);
  522. edv_.v_prob = modify_p(edv_.v_prob1, edv_.count, edv_.count_bytes,
  523.   edp_.bytes, edp_.mean_pktsize, edp_.wait, ch->size());
  525. // drop probability is computed, pick random number and act
  526. if (edp_.cautious == 1) {
  527.  // Don't drop/mark if the instantaneous queue is much
  528.  //  below the average.
  529.  // For experimental purposes only.
  530. int qsize = qib_?q_->byteLength():q_->length();
  531. // pkts: the number of packets arriving in 50 ms
  532. double pkts = edp_.ptc * 0.05;
  533. double fraction = pow( (1-edp_.q_w), pkts);
  534. // double fraction = 0.9;
  535. if ((double) qsize < fraction * edv_.v_ave) {
  536. // queue could have been empty for 0.05 seconds
  537. // printf("fraction: %5.2fn", fraction);
  538. return (0);
  539. }
  540. }
  541. double u = Random::uniform();
  542. if (edp_.cautious == 2) {
  543.                 // Decrease the drop probability if the instantaneous
  544. //   queue is much below the average.
  545. // For experimental purposes only.
  546. int qsize = qib_?q_->byteLength():q_->length();
  547. // pkts: the number of packets arriving in 50 ms
  548. double pkts = edp_.ptc * 0.05;
  549. double fraction = pow( (1-edp_.q_w), pkts);
  550. // double fraction = 0.9;
  551. double ratio = qsize / (fraction * edv_.v_ave);
  552. if (ratio < 1.0) {
  553. // printf("ratio: %5.2fn", ratio);
  554. u *= 1.0 / ratio;
  555. }
  556. }
  557. if (u <= edv_.v_prob) {
  558. // DROP or MARK
  559. edv_.count = 0;
  560. edv_.count_bytes = 0;
  561. hdr_flags* hf = hdr_flags::access(pickPacketForECN(pkt));
  562. if (edp_.setbit && hf->ect() && 
  563.                      (!edp_.use_mark_p || edv_.v_prob1 < edp_.mark_p)) { 
  564. hf->ce() = 1;  // mark Congestion Experienced bit
  565. // Tell the queue monitor here - call emark(pkt)
  566. return (0); // no drop
  567. } else {
  568. return (1); // drop
  569. }
  570. }
  571. return (0); // no DROP/mark
  572. }
  574. /*
  575.  * Pick packet for early congestion notification (ECN). This packet is then
  576.  * marked or dropped. Having a separate function do this is convenient for
  577.  * supporting derived classes that use the standard RED algorithm to compute
  578.  * average queue size but use a different algorithm for choosing the packet for 
  579.  * ECN notification.
  580.  */
  581. Packet*
  582. REDQueue::pickPacketForECN(Packet* pkt)
  583. {
  584. return pkt; /* pick the packet that just arrived */
  585. }
  587. /*
  588.  * Pick packet to drop. Having a separate function do this is convenient for
  589.  * supporting derived classes that use the standard RED algorithm to compute
  590.  * average queue size but use a different algorithm for choosing the victim.
  591.  */
  592. Packet*
  593. REDQueue::pickPacketToDrop() 
  594. {
  595. int victim;
  597. if (drop_front_)
  598. victim = min(1, q_->length()-1);
  599. else if (drop_rand_)
  600. victim = Random::integer(q_->length());
  601. else /* default is drop_tail_ */
  602. victim = q_->length() - 1;
  604. return(q_->lookup(victim)); 
  605. }
  607. /*
  608.  * Receive a new packet arriving at the queue.
  609.  * The average queue size is computed.  If the average size
  610.  * exceeds the threshold, then the dropping probability is computed,
  611.  * and the newly-arriving packet is dropped with that probability.
  612.  * The packet is also dropped if the maximum queue size is exceeded.
  613.  *
  614.  * "Forced" drops mean a packet arrived when the underlying queue was
  615.  * full, or when the average queue size exceeded some threshold and no
  616.  * randomization was used in selecting the packet to be dropped.
  617.  * "Unforced" means a RED random drop.
  618.  *
  619.  * For forced drops, either the arriving packet is dropped or one in the
  620.  * queue is dropped, depending on the setting of drop_tail_.
  621.  * For unforced drops, the arriving packet is always the victim.
  622.  */
  624. #define DTYPE_NONE 0 /* ok, no drop */
  625. #define DTYPE_FORCED 1 /* a "forced" drop */
  626. #define DTYPE_UNFORCED 2 /* an "unforced" (random) drop */
  628. void REDQueue::enque(Packet* pkt)
  629. {
  631. /*
  632.  * if we were idle, we pretend that m packets arrived during
  633.  * the idle period.  m is set to be the ptc times the amount
  634.  * of time we've been idle for
  635.  */
  637. /*  print_edp(); */
  638. int m = 0;
  639. if (idle_) {
  640. // A packet that arrives to an idle queue will never
  641. //  be dropped.
  642. double now = Scheduler::instance().clock();
  643. /* To account for the period when the queue was empty. */
  644. idle_ = 0;
  645. // Use idle_pktsize instead of mean_pktsize, for
  646. //  a faster response to idle times.
  647. if (edp_.cautious == 3) {
  648. double ptc = edp_.ptc * 
  649.    edp_.mean_pktsize / edp_.idle_pktsize;
  650. m = int(ptc * (now - idletime_));
  651. } else
  652.                  m = int(edp_.ptc * (now - idletime_));
  653. }
  655. /*
  656.  * Run the estimator with either 1 new packet arrival, or with
  657.  * the scaled version above [scaled by m due to idle time]
  658.  */
  659. edv_.v_ave = estimator(qib_ ? q_->byteLength() : q_->length(), m + 1, edv_.v_ave, edp_.q_w);
  660. //printf("v_ave: %6.4f (%13.12f) q: %d)n", 
  661. // double(edv_.v_ave), double(edv_.v_ave), q_->length());
  662. if (summarystats_) {
  663. /* compute true average queue size for summary stats */
  664. Queue::updateStats(qib_?q_->byteLength():q_->length());
  665. }
  667. /*
  668.  * count and count_bytes keeps a tally of arriving traffic
  669.  * that has not been dropped (i.e. how long, in terms of traffic,
  670.  * it has been since the last early drop)
  671.  */
  673. hdr_cmn* ch = hdr_cmn::access(pkt);
  674. ++edv_.count;
  675. edv_.count_bytes += ch->size();
  677. /*
  678.  * DROP LOGIC:
  679.  * q = current q size, ~q = averaged q size
  680.  * 1> if ~q > maxthresh, this is a FORCED drop
  681.  * 2> if minthresh < ~q < maxthresh, this may be an UNFORCED drop
  682.  * 3> if (q+1) > hard q limit, this is a FORCED drop
  683.  */
  685. register double qavg = edv_.v_ave;
  686. int droptype = DTYPE_NONE;
  687. int qlen = qib_ ? q_->byteLength() : q_->length();
  688. int qlim = qib_ ? (qlim_ * edp_.mean_pktsize) : qlim_;
  690. curq_ = qlen; // helps to trace queue during arrival, if enabled
  692. if (qavg >= edp_.th_min && qlen > 1) {
  693. if (!edp_.use_mark_p && 
  694. ((!edp_.gentle && qavg >= edp_.th_max) ||
  695. (edp_.gentle && qavg >= 2 * edp_.th_max))) {
  696. droptype = DTYPE_FORCED;
  697. } else if (edv_.old == 0) {
  698. /* 
  699.  * The average queue size has just crossed the
  700.  * threshold from below to above "minthresh", or
  701.  * from above "minthresh" with an empty queue to
  702.  * above "minthresh" with a nonempty queue.
  703.  */
  704. edv_.count = 1;
  705. edv_.count_bytes = ch->size();
  706. edv_.old = 1;
  707. } else if (drop_early(pkt)) {
  708. droptype = DTYPE_UNFORCED;
  709. }
  710. } else {
  711. /* No packets are being dropped.  */
  712. edv_.v_prob = 0.0;
  713. edv_.old = 0;
  714. }
  715. if (qlen >= qlim) {
  716. // see if we've exceeded the queue size
  717. droptype = DTYPE_FORCED;
  718. }
  720. if (droptype == DTYPE_UNFORCED) {
  721. /* pick packet for ECN, which is dropping in this case */
  722. Packet *pkt_to_drop = pickPacketForECN(pkt);
  723. /* 
  724.  * If the packet picked is different that the one that just arrived,
  725.  * add it to the queue and remove the chosen packet.
  726.  */
  727. if (pkt_to_drop != pkt) {
  728. q_->enque(pkt);
  729. q_->remove(pkt_to_drop);
  730. pkt = pkt_to_drop; /* XXX okay because pkt is not needed anymore */
  731. }
  733. // deliver to special "edrop" target, if defined
  734. if (de_drop_ != NULL) {
  736. //trace first if asked 
  737. // if no snoop object (de_drop_) is defined, 
  738. // this packet will not be traced as a special case.
  739. if (EDTrace != NULL) 
  740. ((Trace *)EDTrace)->recvOnly(pkt);
  742. reportDrop(pkt);
  743. de_drop_->recv(pkt);
  744. }
  745. else {
  746. reportDrop(pkt);
  747. drop(pkt);
  748. }
  749. } else {
  750. /* forced drop, or not a drop: first enqueue pkt */
  751. q_->enque(pkt);
  753. /* drop a packet if we were told to */
  754. if (droptype == DTYPE_FORCED) {
  755. /* drop random victim or last one */
  756. pkt = pickPacketToDrop();
  757. q_->remove(pkt);
  758. reportDrop(pkt);
  759. drop(pkt);
  760. if (!ns1_compat_) {
  761. // bug-fix from Philip Liu, <phill@ece.ubc.ca>
  762. edv_.count = 0;
  763. edv_.count_bytes = 0;
  764. }
  765. }
  766. }
  767. return;
  768. }
  770. int REDQueue::command(int argc, const char*const* argv)
  771. {
  772. Tcl& tcl = Tcl::instance();
  773. if (argc == 2) {
  774. if (strcmp(argv[1], "reset") == 0) {
  775. reset();
  776. return (TCL_OK);
  777. }
  778. if (strcmp(argv[1], "early-drop-target") == 0) {
  779. if (de_drop_ != NULL)
  780. tcl.resultf("%s", de_drop_->name());
  781. return (TCL_OK);
  782. }
  783. if (strcmp(argv[1], "edrop-trace") == 0) {
  784. if (EDTrace != NULL) {
  785. tcl.resultf("%s", EDTrace->name());
  786. if (debug_) 
  787. printf("edrop trace exists according to REDn");
  788. }
  789. else {
  790. if (debug_)
  791. printf("edrop trace doesn't exist according to REDn");
  792. tcl.resultf("0");
  793. }
  794. return (TCL_OK);
  795. }
  796. if (strcmp(argv[1], "trace-type") == 0) {
  797. tcl.resultf("%s", traceType);
  798. return (TCL_OK);
  799. }
  800. if (strcmp(argv[1], "printstats") == 0) {
  801. print_summarystats();
  802. return (TCL_OK);
  803. }
  804. } 
  805. else if (argc == 3) {
  806. // attach a file for variable tracing
  807. if (strcmp(argv[1], "attach") == 0) {
  808. int mode;
  809. const char* id = argv[2];
  810. tchan_ = Tcl_GetChannel(tcl.interp(), (char*)id, &mode);
  811. if (tchan_ == 0) {
  812. tcl.resultf("RED: trace: can't attach %s for writing", id);
  813. return (TCL_ERROR);
  814. }
  815. return (TCL_OK);
  816. }
  817. // tell RED about link stats
  818. if (strcmp(argv[1], "link") == 0) {
  819. LinkDelay* del = (LinkDelay*)TclObject::lookup(argv[2]);
  820. if (del == 0) {
  821. tcl.resultf("RED: no LinkDelay object %s",
  822. argv[2]);
  823. return(TCL_ERROR);
  824. }
  825. // set ptc now
  826. link_ = del;
  827. edp_.ptc = link_->bandwidth() /
  828. (8.0 * edp_.mean_pktsize);
  829. edp_.delay = link_->delay();
  830. if (
  831.   (edp_.q_w <= 0.0 || edp_.th_min_pkts == 0 ||
  832. edp_.th_max_pkts == 0))
  833.                          initialize_params();
  834. return (TCL_OK);
  835. }
  836. if (strcmp(argv[1], "early-drop-target") == 0) {
  837. NsObject* p = (NsObject*)TclObject::lookup(argv[2]);
  838. if (p == 0) {
  839. tcl.resultf("no object %s", argv[2]);
  840. return (TCL_ERROR);
  841. }
  842. de_drop_ = p;
  843. return (TCL_OK);
  844. }
  845. if (strcmp(argv[1], "edrop-trace") == 0) {
  846. if (debug_) 
  847. printf("Ok, Heren");
  848. NsObject * t  = (NsObject *)TclObject::lookup(argv[2]);
  849. if (debug_)  
  850. printf("Ok, Here toon");
  851. if (t == 0) {
  852. tcl.resultf("no object %s", argv[2]);
  853. return (TCL_ERROR);
  854. }
  855. EDTrace = t;
  856. if (debug_)  
  857. printf("Ok, Here too too too %dn", ((Trace *)EDTrace)->type_);
  858. return (TCL_OK);
  859. }
  860. if (!strcmp(argv[1], "packetqueue-attach")) {
  861. delete q_;
  862. if (!(q_ = (PacketQueue*) TclObject::lookup(argv[2])))
  863. return (TCL_ERROR);
  864. else {
  865. pq_ = q_;
  866. return (TCL_OK);
  867. }
  868. }
  869. }
  870. return (Queue::command(argc, argv));
  871. }
  873. /*
  874.  * Routine called by TracedVar facility when variables change values.
  875.  * Currently used to trace values of avg queue size, drop probability,
  876.  * and the instantaneous queue size seen by arriving packets.
  877.  * Note that the tracing of each var must be enabled in tcl to work.
  878.  */
  880. void
  881. REDQueue::trace(TracedVar* v)
  882. {
  883. char wrk[500];
  884. const char *p;
  886. if (((p = strstr(v->name(), "ave")) == NULL) &&
  887.     ((p = strstr(v->name(), "prob")) == NULL) &&
  888.     ((p = strstr(v->name(), "curq")) == NULL) &&
  889.     ((p = strstr(v->name(), "cur_max_p"))==NULL) ) {
  890. fprintf(stderr, "RED:unknown trace var %sn",
  891. v->name());
  892. return;
  893. }
  895. if (tchan_) {
  896. int n;
  897. double t = Scheduler::instance().clock();
  898. // XXX: be compatible with nsv1 RED trace entries
  899. if (strstr(v->name(), "curq") != NULL) {
  900. sprintf(wrk, "Q %g %d", t, int(*((TracedInt*) v)));
  901. } else {
  902. sprintf(wrk, "%c %g %g", *p, t,
  903. double(*((TracedDouble*) v)));
  904. }
  905. n = strlen(wrk);
  906. wrk[n] = 'n'; 
  907. wrk[n+1] = 0;
  908. (void)Tcl_Write(tchan_, wrk, n+1);
  909. }
  910. return; 
  911. }
  913. /* for debugging help */
  914. void REDQueue::print_edp()
  915. {
  916. printf("mean_pktsz: %dn", edp_.mean_pktsize); 
  917. printf("bytes: %d, wait: %d, setbit: %dn",
  918. edp_.bytes, edp_.wait, edp_.setbit);
  919. printf("minth: %f, maxth: %fn", edp_.th_min, edp_.th_max);
  920. printf("max_p: %f, qw: %f, ptc: %fn",
  921. (double) edv_.cur_max_p, edp_.q_w, edp_.ptc);
  922. printf("qlim: %d, idletime: %fn", qlim_, idletime_);
  923. printf("mark_p: %f, use_mark_p: %dn", edp_.mark_p, edp_.use_mark_p);
  924. printf("=========n");
  925. }
  927. void REDQueue::print_edv()
  928. {
  929. printf("v_a: %f, v_b: %fn", edv_.v_a, edv_.v_b);
  930. }
  932. void REDQueue::print_summarystats()
  933. {
  934. //double now = Scheduler::instance().clock();
  935. printf("True average queue: %5.3f", true_ave_);
  936. if (qib_) 
  937. printf(" (in bytes)");
  938.         printf(" time: %5.3fn", total_time_);
  939. }
  941. /************************************************************/
  942. /*
  943.  * This procedure is obsolete, and only included for backward compatibility.
  944.  * The new procedure is REDQueue::estimator
  945.  */ 
  946. /*
  947.  * Compute the average queue size.
  948.  * The code contains two alternate methods for this, the plain EWMA
  949.  * and the Holt-Winters method.
  950.  * nqueued can be bytes or packets
  951.  */
  952. void REDQueue::run_estimator(int nqueued, int m)
  953. {
  954. double f, f_sl, f_old;
  956. f = edv_.v_ave;
  957. f_sl = edv_.v_slope;
  958. #define RED_EWMA
  959. #ifdef RED_EWMA
  960. while (--m >= 1) {
  961. f_old = f;
  962. f *= 1.0 - edp_.q_w;
  963. }
  964. f_old = f;
  965. f *= 1.0 - edp_.q_w;
  966. f += edp_.q_w * nqueued;
  967. #endif
  968. #ifdef RED_HOLT_WINTERS
  969. while (--m >= 1) {
  970. f_old = f;
  971. f += f_sl;
  972. f *= 1.0 - edp_.q_w;
  973. f_sl *= 1.0 - 0.5 * edp_.q_w;
  974. f_sl += 0.5 * edp_.q_w * (f - f_old);
  975. }
  976. f_old = f;
  977. f += f_sl;
  978. f *= 1.0 - edp_.q_w;
  979. f += edp_.q_w * nqueued;
  980. f_sl *= 1.0 - 0.5 * edp_.q_w;
  981. f_sl += 0.5 * edp_.q_w * (f - f_old);
  982. #endif
  983. edv_.v_ave = f;
  984. edv_.v_slope = f_sl;
  985. }