fred.cc

里面包含fred,util,csfq这三种演算法的程式码,适用于NS2开发环境

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

/*  This is a FRED implementation heavly based on the RED code
 *  (red.cc) found in ns-2 version 2.0. The differences from red.cc
 *  are highlighted by comments containing "FRED" word. The changes
 *  were based on the FRED pseudocode published in SIGCOMM'97 
 * 
 * Contact: Ion Stoica ([e-mail]) 
 */

#ifndef lint
static const char rcsid[] =
    "@(#) $Header: /afs/cs/project/cmcl-ns2/NetBSD1.2.1/ns-allinone/ns-2/RCS/fred.cc,v 1.2 1998/09/12 16:43:27 istoica Exp istoica $ (LBL)";
#endif

#include "fred.h"

//#define FRED_LOG

#ifndef max
#define max(x, y) (x > y ? x : y)
#endif

void droplog(int flowId, int type);

static class FREDClass : public TclClass {
public:
	FREDClass() : TclClass("Queue/FRED") {}
	TclObject* create(int, const char*const*) {
		return (new FREDQueue);
	}
} class_fred;

FREDQueue::FREDQueue() : link_(NULL), bcount_(0), de_drop_(NULL), idle_(1)
{
  for (int i = 0; i < MAXFLOWS; ++i) { // FRED 
    fs_[i].qlen    = 0;                // FRED 
    fs_[i].strike  = 0;                // FRED 
    fs_[i].present = 0;                // FRED 
#ifdef SRCID
    hashid_[i]     = 0;                // FRED 
#endif
  }                                    // FRED
  maxq  = MINQ;                        // FRED
  nactive = 0;                         // FRED 
  many_flows_ = 0;                     // FRED  
 
  memset(&edp_, '\0', sizeof(edp_));
  memset(&edv_, '\0', sizeof(edv_));
  
  bind_bool("bytes_", &edp_.bytes);	    // boolean: use bytes?
  bind_bool("queue-in-bytes_", &qib_);	    // boolean: q in bytes?
  bind("thresh_", &edp_.th_min);		    // minthresh
  bind("maxthresh_", &edp_.th_max);	    // maxthresh
  bind("mean_pktsize_", &edp_.mean_pktsize);  // avg pkt size
  bind("q_weight_", &edp_.q_w);		    // for EWMA
  bind_bool("wait_", &edp_.wait);
  bind("linterm_", &edp_.max_p_inv);
  bind_bool("setbit_", &edp_.setbit);	    // mark instead of drop
  bind_bool("drop-tail_", &drop_tail_);	    // drop last pkt or random
  bind_bool("many-flows_", &many_flows_);   // specifies the mode in which 
                                            // FRED works
  q_ = new PacketQueue();		    // underlying queue
  reset();
  
#ifdef notdef
  print_edp();
  print_edv();
#endif

}

void FREDQueue::reset()
{
  /*
   * if queue is measured in bytes, scale min/max thresh
   * by the size of an average packet
   */
  
  if (qib_) {
    edp_.th_min *= edp_.mean_pktsize;
    edp_.th_max *= edp_.mean_pktsize;
  }
  /*
   * 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
   */
  
  if (link_)
    edp_.ptc = link_->bandwidth() /
      (8. * edp_.mean_pktsize);
  edv_.v_ave = 0.0;
  edv_.v_slope = 0.0;
  edv_.count = 0;
  edv_.count_bytes = 0;
  edv_.old = 0;
  edv_.v_a = 1 / (edp_.th_max - edp_.th_min);
  edv_.v_b = - edp_.th_min / (edp_.th_max - edp_.th_min);
  
  idle_ = 1;
  if (&Scheduler::instance() != NULL)
    idletime_ = Scheduler::instance().clock();
  else
    idletime_ = 0.0; /* sched not instantiated yet */
  Queue::reset();
  
  bcount_ = 0;
}

/*
 * 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 FREDQueue::run_estimator
(int nqueued, int m)
{
  float f, f_sl, f_old;
  
  f = edv_.v_ave;
  f_sl = edv_.v_slope;
#define FRED_EWMA
#ifdef FRED_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 FRED_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;
}

/*
 * Output the average queue size and the dropping probability. 
 */
void FREDQueue::plot()
{
#ifdef notyet
  double t = Scheduler::instance().clock();
  sprintf(trace_->buffer(), "a %g %g", t, edv_.v_ave);
  trace_->dump();
  sprintf(trace_->buffer(), "p %g %g", t, edv_.v_prob);
  trace_->dump();
#endif
}

/*
 * print the queue seen by arriving packets only
 */
void FREDQueue::plot1(int)
{
#ifdef notyet
  double t =  Scheduler::instance().clock();
  sprintf(trace_->buffer(), "Q %g %d", t, length);
  trace_->dump();
#endif
}

/*
 * Return the next packet in the queue for transmission.
 */
Packet* FREDQueue::deque()
{
  Packet  *p;
  
  check();  /* FRED: check consistency of flows' states */
  
  p = q_->deque();
  
  if (p) {                                         // FRED
    
    hdr_ip*  hip    = hdr_ip::access(p); /* (hdr_ip*)p->access(off_ip_); // FRED */
#ifdef SRCID
    int flowId = getId(hip->src());                // FRED
#else
    int flowId = hip->flowid();                    // FRED 
#endif                  
    --fs_[flowId].qlen;                            // FRED
    reset_flow_state(flowId);                      // FRED
  }                                                // FRED
  run_estimator(q_->length(), 1);                  // FRED 
  
  if (p != 0) {
    idle_ = 0;
    bcount_ -= hdr_cmn::access(p)->size();
  } 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);
}

int FREDQueue::drop_early(Packet* pkt)
{
   hdr_cmn* ch = hdr_cmn::access(pkt); 
   double p = edv_.v_a * edv_.v_ave + edv_.v_b;
   hdr_ip*  hip = hdr_ip::access(pkt); /* (hdr_ip*)pkt->access(off_ip_); // FRED */
#ifdef SRCID
   int      flowId = getId(hip->src());          // FRED 
#else
   int      flowId = hip->flowid();              // FRED 
#endif

   /* random drop from robust flows only */
   if (fs_[flowId].qlen >= max(MINQ, int(edv_.v_ave/nactive))) { // FRED

     p /= edp_.max_p_inv;
     edv_.v_prob1 = p;
     if (edv_.v_prob1 > 1.0)
       edv_.v_prob1 = 1.0;
     double count1 = edv_.count;
     if (edp_.bytes)
       count1 = (double) (edv_.count_bytes/edp_.mean_pktsize);
     if (edp_.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 (edp_.bytes && p < 1.0) {
       p = p * ch->size() / edp_.mean_pktsize;
     }
     if (p > 1.0)
       p = 1.0;
     edv_.v_prob = p;
     
     // drop probability is computed, pick random number and act
     double u = Random::uniform();
     if (u <= edv_.v_prob) {
       // DROP or MARK
       edv_.count = 0;
       edv_.count_bytes = 0;
       if (edp_.setbit) {
	 hdr_flags* hf = hdr_flags::access(pkt); 
	 hf->ecn_to_echo_ = 1; 
       } else {
	 return (1);
       }
     }
   }  // FRED 
   return (0);  // no DROP/mark
}

/*
 * Pick packet to drop. Having a separate function do this is convenient for
 * supporting derived classes that use the standard FRED algorithm to compute
 * average queue size but use a (slightly) different algorithm for choosing
 * the victim.
 */
Packet*
FREDQueue::pickPacketToDrop() {
  drop_tail_ = 1; /* FRED */
  int victim = drop_tail_ ? q_->length() - 1 : Random::integer(q_->length());
  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.
 */

#define	DTYPE_FORCED	1	/* a "forced" drop */
#define	DTYPE_UNFORCED	2	/* an "unforced" (random) drop */

void FREDQueue::enque(Packet* pkt)
{
  double now = Scheduler::instance().clock();