/*
 * 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 (istoica@cs.cmu.edu) 
 */

#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();
  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
}