fred.cc

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

  hdr_cmn* ch = hdr_cmn::access(pkt); 
  hdr_ip*  hip = hdr_ip::access(pkt); 
#ifdef SRCID
  int      flowId = getId(hip->src());          // FRED 
#else
  int      flowId = hip->flowid();              // FRED 
#endif
  
  int droptype = -1;
  int m = 0;
  check();  // FRED: check consistency of flows' states

  if (flowId >= MAXFLOWS) {                                 // FRED 
    printf("Error: flow number is %d and should be < %d\n", // FRED 
	   flowId, MAXFLOWS);                               // FRED 
    exit (-1);                                              // FRED 
  }

  /*
   * Install flow state; this is the first 
   * packet of connection flowId.
   * Note that there is no need to reset 
   * strike and qlen fields as they are already 0.
   * (Also, note that we assume that a flow exists 
   * (i.e., it is present) only as long as it has packets.) 
   */
  if (!fs_[flowId].present) {  // FRED 
    fs_[flowId].present = 1;   // FRED 
    nactive++;                 // FRED 
  }                            // FRED 
  
  /*
   * 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
   */
  
  if (idle_) {
    /* To account for the period when the queue was empty.  */
    idle_ = 0;
    m = int(edp_.ptc * (now - idletime_));
  }
  
  /*
   * If queues was empty FRED computes the average queue length
   * here. 
   * To account for the current packet arrival the estimator is again
   * invoked at the end of this method; this is done only if the
   * packet is _not_ dropped (see pseudocode in the FRED
   * paper at SIGCOMM'97)
   *
   * Here the estimator is run with the scaled version (m) above 
   * [scaled due to idle time] (bcount_ maintains the byte 
   * count in the underlying queue)
   *
   * Note that the last argument is "m" instead of "m+1" as in the red.cc
   * code. This is because, in this case run_estimator is called
   * again to account for the new arrival at the end of this method.
   */
  if (m)                                              // FRED 
    run_estimator(qib_ ? bcount_ : q_->length(), m);  // FRED  
  

  if (!many_flows_) {                 // FRED
    /* this is block A in FRED pseudocode (see SIGCOMM'97 paper) */
    maxq =  int(edp_.th_min);        // FRED
    if (edv_.v_ave >=  edp_.th_max)  // FRED 
      maxq = MINQ;                   // FRED 
  }                                  // FRED

  /*
   * count and count_bytes keeps a tally of arriving traffic
   * that has not been dropped
   */
  ++edv_.count;
  edv_.count_bytes += ch->size();
  
  // see if we drop early
  
  register double qavg = edv_.v_ave;
  int qlen = qib_ ? bcount_ : q_->length();
  int qlim = qib_ ?  (qlim_ * edp_.mean_pktsize) : qlim_;
  double avgcq;

  /*
   * Compute per flow average queue length
   */  
  if (nactive)               // FRED
    avgcq = qavg/nactive;    // FRED
  else                       // FRED
    avgcq = qavg;            // FRED
  avgcq = max(avgcq, 1);     // FRED


  /* identify and manage non-adaptive flows */
  if (fs_[flowId].qlen >= maxq || (!many_flows_ &&                       // FRED
      /* the next two lines represent line B in the FRED pseudocode
       * (See SIGCOMM'97 paper) 
       */
      ((qavg >= edp_.th_max && fs_[flowId].qlen > 2*avgcq) ||            // FRED 
      ((double)(fs_[flowId].qlen) >= avgcq && fs_[flowId].strike > 1)))){// FRED 
    ++fs_[flowId].strike;                                                // FRED
    droptype = DTYPE_FORCED;                                             // FRED 
    droplog(flowId, 1);                                                  // FRED

  } else {
    /* operate in random drop mode */
    if (qavg >= edp_.th_min && qlen > 1) {
      if (qavg >= edp_.th_max) { 
        // drop-tail mode; the following is block C in the FRED pseudocde
	if (many_flows_) {
	  if (fs_[flowId].qlen >= MINQ) {
	    droptype = DTYPE_FORCED;
	    droplog(flowId, 2);
	  }
	} else { 
	  droptype = DTYPE_FORCED;
	  droplog(flowId, 2);
	}
      } else if (edv_.old == 0) {
	edv_.count = 1;
	edv_.count_bytes = ch->size();
	edv_.old = 1;
      } else {
	/*
         * (edp_.th_min <= qavg < edp_.th_max) && (qlen > 1) && (edv_.old == 1)
         *  Note: the last two clauses are inherited from RED and they shouldn't
         *  affect FRED. (qlen represents the current queue size, while 
         *  edv_.old avoids dropping when the average queue length exceeds
         *  first threshold first time  
         */ 
        if (drop_early(pkt)) { 
          /* drop from robust flows only (see drop_early()) */
	  droplog(flowId, 3);
	  droptype = DTYPE_UNFORCED;
        }
      }
    } else {
      edv_.v_prob = 0.0;
      edv_.old = 0;
    }
  }
	  
  if (qlen >= qlim) {
    droplog(flowId, 4);
    droptype = DTYPE_FORCED;
  }
  
  if (droptype != DTYPE_UNFORCED) {
    // enqueue packet
    q_->enque(pkt);
    bcount_ += ch->size();
    qlen = qib_ ? bcount_ : q_->length();
    ++fs_[flowId].qlen;          // FRED 
  }
  if (droptype == DTYPE_FORCED) {
    /* drop random victim or last one */
    pkt = pickPacketToDrop();
    q_->remove(pkt);
    bcount_ -= (hdr_cmn::access(pkt))->size();
    /* update flow's queue length */
    {
      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
      --fs_[flowId].qlen;                           // FRED 
      reset_flow_state(flowId);
    }                   
  } else if (droptype == DTYPE_UNFORCED && de_drop_ != NULL) {
    de_drop_->recv(pkt);
    reset_flow_state(flowId);   // FRED
    return;
  }

  if (droptype == DTYPE_FORCED || droptype == DTYPE_UNFORCED) {
    drop(pkt);
  }
  reset_flow_state(flowId); // Just to be sure; probably this is not needed here

  /* 
   * If the packet was not dropped compute the average queue length.
   * Note that in RED this is done at the beginning of the method 
   * by calling run_estimator with the last parameter "m+1" instead of "m+1"
   * (Thus unlike RED, FRED to not update the average when the packet is 
   *  dropped.)
   */ 
  if (droptype != DTYPE_FORCED && droptype != DTYPE_UNFORCED) // FRED
    run_estimator(q_->length(), 1);                           // FRED
  
  return;
}

int FREDQueue::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);
    }
  } else if (argc == 3) {
    if (strcmp(argv[1], "link") == 0) {
      LinkDelay* del = (LinkDelay*)TclObject::lookup(argv[2]);
      if (del == 0) {
	tcl.resultf("FRED: no LinkDelay object %s",
		    argv[2]);
	return(TCL_ERROR);
      }
      // set ptc now
      link_ = del;
      edp_.ptc = link_->bandwidth() /
	(8. * edp_.mean_pktsize);
      
      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], "packetqueue-attach")) {
      delete q_;
      if (!(q_ = (PacketQueue*) TclObject::lookup(argv[2])))
	return (TCL_ERROR);
      else
	return (TCL_OK);
    }
  }
  return (Queue::command(argc, argv));
}


void FREDQueue::reset_flow_state(int flowId) 
{
  if (fs_[flowId].qlen == 0 && fs_[flowId].present) { 
    fs_[flowId].present = 0;                          
    fs_[flowId].strike  = 0;                          
    --nactive;                                        
  }                                                   
}

/* for debugging help */
void FREDQueue::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_inv: %f, qw: %f, ptc: %f\n",
	 edp_.max_p_inv, edp_.q_w, edp_.ptc);
  printf("qlim: %d, idletime: %f\n", qlim_, idletime_);
  printf("=========\n");
}

void FREDQueue::print_edv()
{
  printf("v_a: %f, v_b: %f\n", edv_.v_a, edv_.v_b);
}


/* check state consistency for all flows */
void FREDQueue::check()
{
  int qlen = 0;
  static flowState* adr = NULL;

  for (int i = 0; i < MAXFLOWS; i++) {
  
    if (fs_[i].present) {
      if (!adr) adr = (flowState *)&fs_;
      qlen += fs_[i].qlen;
    } else {
      if (fs_[i].qlen) {
        printf("Error: invalid qlen: flow %d, qlen %d \n", i, fs_[i].qlen);
        exit(-1);
      }     
      if (fs_[i].strike) {
        printf("Error: invalid strike: flow %d, qlen %d \n", i, fs_[i].strike);
        exit(-1);
      }     
    }
  }
  
  if (qlen != q_->length()) {        
    printf("Error: invalid length: length %d, qlen %d \n", q_->length(), 
	   qlen);
    exit(-1);
  }     
}

#ifdef SRCID
/* get identifier from source address */
int FREDQueue::getId(int src) 
{
  int i = src % MAXFLOWS;
 
  if (!hashid_[i]) { 
    /* first packet of this flow */
    hashid_[i] = src; 
  } else 
    if (hashid_[i] != src)
      panic1("Source addresses colision!\n");

  return i;
}
#endif


/* FRED function */
void droplog(int flowId, int type)
{
#ifdef FRED_LOG
  printf("d%d %f 1 t%d\n", flowId, Scheduler::instance().clock(), 
     type);
#else
  ;
#endif
}