csfq.cc

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

/*
 * Copyright (c) 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 MASH Research
 * 	Group at the University of California Berkeley.
 * 4. Neither the name of the University nor of the Research Group 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.
 */

#ifndef lint
static char rcsid[] =
"@(#) $Header: /afs/cs/project/cmcl-ns2/NetBSD1.2.1/ns-allinone/ns-2/RCS/csfq.cc,v 1.7 1998/09/12 19:39:27 istoica Exp istoica $ (ANS)";
#endif

#include <stdlib.h>
#include <string.h>
#include "random.h"
#include "queue.h"

#define MAXFLOWS 200

#ifndef TRUE
#define TRUE 1
#define FALSE 0
#endif

#define KALPHA 29 // 0.99^29 = 0.75

//#define CSFQ_LOG 
//#define PENALTY_BOX  /* use penalty box in conjucntion with CSFQ */

#ifdef PENALTY_BOX
#define MONITOR_TABLE_SIZE 10
#define PUNISH_TABLE_SIZE  10
#define DROPPED_ARRAY_SIZE 100
#define PUNISH_THRESH  1.3  /* 
			     * when the flow's rate exceeds 
			     * PUNISH_THRESH times the fair rate 
			     * the flow is punished
			     */
#define GOOD_THRESH     0.7  /* 
			      * when the punished flow's rate is  
			      * GOOD_THRESH times smaller than the 
			      * link's fair rate the flow 
			      * is no longer punished
			      */
#define BETA 0.98            /* 
			      * (1 - BETA) = precentage by which 
			      * link's fair rate is decreased when a
			      * forced drop occurs
                              */


typedef struct identHash {
  int    valid_;
  double prevTime_;
  double estNormRate_;
} IdentHashTable;

#endif

//#define SRCID       /* identify flow bassed of source id rather than flow id */
//#define CSFQ_RLMEX  /* used for RLM experiments only */


/* the following three functions are in util.cc */
void  initRand(unsigned seed);
float funifRand(float a, float b);
void  panic(char *s);

double min(double x, double y)
{
  return (x < y ? x : y);
}

class CSFQ : public Queue {
public: 
  CSFQ();
  virtual int command(int argc, const char*const* argv);
  Packet *deque(void);
  void   enque(Packet *pkt);

protected:
  double estRate(int flowid, int pktSize, double arvTime);
  void estAlpha(int pktSize, double pktLabel, double arvTime, int enqueue);
  
  void logArvPacket(int flowId, double ctime, int pktSize);
  void logDptPacket(int flowId, double ctime, int pktSize);
  void logDroppedPacket(int flowId, double ctime);
  void logDroppedPacket1(int flowId, double ctime);
  void logEstAlpha(double ctime);
  void logEstLabel(int flowId, double ctime, double label);

#ifdef SRCID
        int getId(int src);
#endif 

#ifdef PENALTY_BOX
  int isInHash(int idx, IdentHashTable *hashTable, int size); 
  int insertInHash(int idx, double flowRate, 
			 IdentHashTable *hashTable, int size);
  void deleteFromHash(int idx, IdentHashTable *hashTable, int size); 
  double updateNormRate(int idx, double pktLabel,
			IdentHashTable *hashTable, int size); 
  int  recordDroppedPacket(int flowId);
  void choseToMonitor();
  void punishFlow(int flowId);
#endif

  struct flowState {
    double weight_;   /* the weight of the flow */
    double k_;        /* averaging interval for rate estimation */
    double estRate_;  /* current flow's estimated rate */
    double prevTime_;
    /* internal statistics */ 
    int size_;      /* keep track of packets that arrive
		       at the same time */
    int numArv_;    /* number of arrival packets */
    int numDpt_;    /* number of dropped packets */
    int numDroped_; /* number of droped packets */
    
  } fs_[MAXFLOWS];

  int         id_; /* queue & link identifier */
#ifdef SRCID
  int         hashid_[MAXFLOWS];
#endif
  int  CSFQ::monitor(int flowId, double pktLabel);
  void CSFQ::dropPkt(int flowId, Packet *pkt);
#ifdef PENALTY_BOX
  IdentHashTable monitorTable_[MONITOR_TABLE_SIZE];
  IdentHashTable punishTable_[PUNISH_TABLE_SIZE];
  int droppedArray_[DROPPED_ARRAY_SIZE];
  int numDroppedPkts_;
  double kDropped_;
#endif

  PacketQueue q_;           /* packet queue */
  int         qsize_;       /* maximum queue size (in bits) */
  int         qsizeThresh_; /* threshold (in bits); if queue occupancy does 
                             * not exceed qsizeThresh_ the queue is
                             * assumed to be uncongested
                             */
  int         qsizeCrt_;    /* current queue size (in bits) */
  int         maxflow_;     /* maximum number of flows */
  
  int    edge_;      /* queue type: 1 if belongs to an edge node; 0 otherwise*/
  double rate_;      /* link rate (in bps) */
  double lastArv_;   /* the arival time of the last packet (in sec) */
  double kLink_;     /* avg. interval for computing rateTotal (usec)*/ 
  double alpha_;     /* output link fair rate */
  double tmpAlpha_;  /* 
		      * used to compute the largest label of a packet, i.e.,
		      * the largest flow rate seen during an
		      * interval of length kLink_ 
		      */
  int    kalpha_;    /*  maximum number of times the fair rate
		      * (alpha_) can be decreased when the queue
		      * overflows, during a time interval of length kLink_ 
		      */
  double rateAlpha_; /* aggreagte forwarded rate corresponding to crt. alpha_ */
  double rateTotal_; /* aggregate arrival rate */
  double lArv_;      /* used to store the start of an interval of 
		      * length kLink_ 
		      */
  int    congested_; /* specify whether the link is congested or not*/
  int    pktSize_;   /* 
		      * the total number of bits enqueued between
		      * two consecutive rate estimations.
		      * usualy, this represent the size of one packet;
		      * however, if more packets are received at the same time
		      * this will represent the cumulative size of all
		      * pacekets received simulatneously
		      */
  int    pktSizeE_;  /* 
		      * same as above, but for the total number of bytes that
		      * are enqueued between consecutive rate estimations
		      */
};

static class CSFQClass : public TclClass {
public:
	CSFQClass() : TclClass("Queue/CSFQ") {}
	TclObject* create(int argc, const char*const* argv) {
		return (new CSFQ);
	}
} class_csfq;


CSFQ::CSFQ()
{
  for (int i = 0; i < MAXFLOWS; ++i) {
    fs_[i].weight_   = 1.0;
    fs_[i].k_        = 100000.0;
    fs_[i].numArv_   = fs_[i].numDpt_ = fs_[i].numDroped_ = 0;
    fs_[i].prevTime_ = 0.0;
    fs_[i].estRate_  = 0.0;
    fs_[i].size_     = 0;
#ifdef SRCID
    hashid_[i]       = 0;
#endif
  }
  maxflow_     = -1;
  qsizeCrt_    = 0;
  alpha_       = tmpAlpha_ = 0.;
  kalpha_ = KALPHA; 

#ifdef PENALTY_BOX
  for (int i = 0; i < MONITOR_TABLE_SIZE; i++) {
    monitorTable_[i].valid_ = 0;
    monitorTable_[i].prevTime_ = monitorTable_[i].estNormRate_ = 0.;    
  }
  for (int i = 0; i < PUNISH_TABLE_SIZE; i++) {
    punishTable_[i].valid_ = 0;
    punishTable_[i].prevTime_ = monitorTable_[i].estNormRate_ = 0.;    
  }
  numDroppedPkts_ = 0;
#endif  

 
  lastArv_   = rateAlpha_ = rateTotal_ = 0.;
  lArv_      = 0.; 
  pktSize_   = pktSizeE_ = 0; 
  congested_ = 1; 

#ifdef PENALTY_BOX
  bind("kLink_", &kDropped_);
#endif  

  bind("kLink_", &kLink_);
  edge_ = 1;
  bind("edge_", &edge_);

  bind("qsize_", &qsize_);
  bind("qsizeThresh_", &qsizeThresh_);
  bind("rate_", &rate_);
  bind("id_", &id_);
}

int CSFQ::command(int argc, const char*const* argv)
{
  if (argc == 5) { /* flowid, weight_, k_ */
    if (strcmp(argv[1], "init-flow") == 0) {
      int flowId     = atoi(argv[2]);
   
      if (flowId >= MAXFLOWS) {
        fprintf(stderr, "CSFQ: Flow id=%d too large; it should be < %d!\n",
          flowId, MAXFLOWS);
        abort();
      }
      fs_[flowId].weight_ = (double)atoi(argv[3]); 
      fs_[flowId].k_      = (double)atoi(argv[4]); 
      return (TCL_OK);
     
    } 
  } else if ((argc == 7) && (strcmp(argv[1], "init-link") == 0)) {
    /* edge_, kLink_, qsize_, qsizeThresh_  */

    edge_  = atoi(argv[2]);
    if (edge_ != 0 && edge_ != 1) {
      fprintf(stderr, "CSFQ: Invalide link type !\n");
      abort();
    }
    kLink_       = (double)atoi(argv[3]); 
#ifdef PENALTY_BOX
    kDropped_    = kLink_; 
#endif
    qsize_       = atoi(argv[4]); 
    qsizeThresh_ = atoi(argv[5]); 
    rate_        = atof(argv[6]);
    return (TCL_OK);
  }
  return (Queue::command(argc, argv));
}


/* Receive a new packet.  The flow rate is estimated, and the link's
 * fair rate (alpha_) is computed. If the packet's label is larger
 * than alpha_ then a 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.  
 */

void CSFQ::enque(Packet* pkt)
{
  double   now  = Scheduler::instance().clock();
  hdr_cmn* hdr  = hdr_cmn::access(pkt); 
  hdr_ip*  hip  = hdr_ip::access(pkt); /* (hdr_ip*)pkt->access(off_ip_); */
  int pktSize   = hdr->size() << 3; /* length of the packet in bits */
  double pktLabel = hdr->label();
#ifdef SRCID
  int    flowId   = getId(hip->src());
#else
  int    flowId   = hip->flowid();
#endif

  /* 
   * if this queue belongs to an edge node, estimate session rate 
   * and label the packet
   */
 
  if (edge_ == 1) {
#ifdef CSFQ_RLMEX
    hdr->setlabel(estRate(1, pktSize, now)/fs_[1].weight_);
#else
    hdr->setlabel(estRate(flowId, pktSize, now)/fs_[flowId].weight_);
#endif
    pktLabel = hdr->label();
  }

#ifdef PENALTY_BOX
  /*  
   * if the flow is monitored and its rate (i.e., the packet label)
   * exceeds PUNISH_THRESH times link's fair rate, then punish the
   * flow if the flow is punished but its rate is no larger than
   * GOOD_THRESH times link's fair rate, then remove flow from penalty
   * box.  
   */
  if (monitor(flowId, pktLabel)) {
    drop(pkt);
    return;
  }
#endif

#ifdef CSFQ_LOG
    logEstLabel(flowId, now, pktLabel);
#endif

#ifdef CSFQ_LOG
  logEstAlpha(now);
  logArvPacket(flowId, now, pktSize);
#endif

  /* 
   * check whether alpha_ has been initialized
   * alpha_ is set to 0. whenever qusizeCrt_ < qsizeThreshold_ 
   * (see estAlpha method)
   */
  if (alpha_ != 0) { 
    if (alpha_/pktLabel < funifRand(0., 1.)) {

      /* drop packet prbabilistically */
      dropPkt(flowId, pkt);
      /* 
       * estimate fair rate (alpha_); call with last parameter 0 as 
       * the packet is probabilistically dropped
       */
      estAlpha(pktSize, pktLabel, now, 0); 
#ifdef CSFQ_LOG
      logDroppedPacket(flowId, now);
#endif
      return;
    }