/* -*-	Mode:C++; c-basic-offset:8; tab-width:8; indent-tabs-mode:t -*- */
/*
 * 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
 * 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.
 *
 *
 * Here is one set of parameters from one of Sally's simulations
 * (this is from tcpsim, the older simulator):
 * 
 * ed [ q_weight=0.002 thresh=5 linterm=30 maxthresh=15
 *         mean_pktsize=500 dropmech=random-drop queue-size=60
 *         plot-file=none bytes=false doubleq=false dqthresh=50 
 *	   wait=true ]
 * 
 * 1/"linterm" is the max probability of dropping a packet. 
 * There are different options that make the code
 * more messy that it would otherwise be.  For example,
 * "doubleq" and "dqthresh" are for a queue that gives priority to
 *   small (control) packets, 
 * "bytes" indicates whether the queue should be measured in bytes 
 *   or in packets, 
 * "dropmech" indicates whether the drop function should be random-drop 
 *   or drop-tail when/if the queue overflows, and 
 *   the commented-out Holt-Winters method for computing the average queue 
 *   size can be ignored.
 * "wait" indicates whether the gateway should wait between dropping
 *   packets.
 */

/*
 * SRED
 * Author: Srinivas R. Avasarala (Computer Science, Purdue University)
 *
 * Note that this code is written based on the paper, T. J. Ott, T. V. Lakshman,
 * and L. H. Wong, "SRED: Stabilized RED," in Proceedings of IEEE INFOCOM, March 1999.
 */


#ifndef lint
static const char rcsid[] =
    "@(#) $Header: /nfs/jade/vint/CVSROOT/ns-2/red.cc,v 1.54 2000/10/05 21:25:34 sfloyd Exp $ (LBL)";
#endif

#include <math.h>
#include <sys/types.h>
#include "config.h"
#include "template.h"
#include "random.h"
#include "flags.h"
#include "delay.h"
#include "sred.h"

static class SREDClass : public TclClass {
public:
	SREDClass() : TclClass("Queue/SRED") {}
	TclObject* create(int argc, const char*const* argv) {
		//printf("creating SRED Queue. argc = %d\n", argc);
		//modified to enable RED to take arguments
		if (argc==5) 
			return (new SREDQueue(argv[4]));
		else
			return (new SREDQueue("Drop"));
	}
} class_sred;

/*
 * modified to enable instantiation with special Trace objects - ratul
 */
SREDQueue::SREDQueue(const char * trace) : link_(NULL), bcount_(0), drop_tgt_(NULL), drop_trace_(NULL), tchan_(0)
{
	//	printf("Making trace type %s\n", trace);
	if (strlen(trace) >=20) {
		printf("trace type too long - allocate more space to \
				  traceType in red.h and recompile\n");
		exit(0);
	}
	bind("which_", &which_);
	strcpy(traceType, trace);
	bind_bool("full_SRED_", &full_sred_);	// boolean: full or simple SRED?
	bind("prob_overwrite_", &p_overwrite_);// double: prob of overwrite a zombie
	bind("prob_maximum_", &p_max_);			// double: max drop probability
	bind_bool("queue_in_bytes_", &qib_);		// boolean: q in bytes?
	bind("curq_", &curq_);			 			   // current queue size
	
	listsize_ = 0;
	p_t_ = 0;
	alpha_ = p_overwrite_/M;

	q_ = new PacketQueue();			    			// underlying queue
	pq_ = q_;

	reset();
}

void SREDQueue::reset()
{
	listsize_ = 0;
	p_t_ = 0;
	alpha_ = p_overwrite_/M;

	Queue::reset();

	bcount_ = 0;
}

/*
 * Return the next packet in the queue for transmission.
 */
Packet* SREDQueue::deque()
{
	Packet *p;
	p = q_->deque();
	if (p != 0) {
		bcount_ -= hdr_cmn::access(p)->size();
		// helps to trace queue during arrival, if enabled
		curq_ = qib_ ? bcount_ : q_->length();
	}
	return (p);
}

double SREDQueue::calc_psred()
{
	int len, lim, lim_3, lim_6;

	len = curq_*536;
	lim = qlim_*536; lim_3 = lim/3; lim_6 = lim/6;

	if ((len >= lim_3) && (len < lim)) {
		return p_max_;
	} else if ((len >= lim_6) && (len < lim_3)) {
		return (p_max_/4);
	} else if ((len >= 0) && (len < lim_6)) {
		return 0;
	}
}

double SREDQueue::calc_simple_pzap(double prob_sred)
{
	double factor;

	factor = 256 * p_t_;
	factor *= factor;
	factor = 1/factor;
	if (factor > 1)
		factor = 1;
// printf("%f ", 1/((p_t_)*(p_t_)));
// fflush(stdout);
	return (prob_sred * factor);
}

double SREDQueue::calc_full_pzap(double prob_sred, int hit)
{
	double prob_zap = calc_simple_pzap(prob_sred);
	prob_zap *= (1 + (hit/p_t_));
	return prob_zap;
}

void SREDQueue::enque(Packet* pkt)
{
	hdr_ip* hdr;
	int fid; 
	int hit;

	hdr = hdr_ip::access(pkt);
	fid = hdr->flowid();

	if (listsize_ < M) {
		zombielist[listsize_].fid = fid;
		zombielist[listsize_].count = 0;
		zombielist[listsize_].timestamp = Scheduler::instance().clock();
		++listsize_;

		// enque if curq_ < qlim_, else drop
		// so discard results for first M pkts
		if (curq_ < qlim_) {
			q_->enque(pkt);
			bcount_ += hdr_cmn::access(pkt)->size();
			curq_ = qib_ ? bcount_ : q_->length();
		} else {
			// no drop trace reqd here, as this is just the start up of the run
			drop(pkt);
		}
		return;
	} else {
		int index = Random::integer(M);
		if (zombielist[index].fid == fid) {
			/* HIT */
			hit = 1;
			zombielist[index].count++;
			zombielist[index].timestamp = Scheduler::instance().clock();
		} else {
			/* MISS */
			hit = 0;
			double u2 = Random::uniform();
			if (u2 < p_overwrite_) {
				/* overwrite with random probability */
				zombielist[index].fid = fid;
				zombielist[index].count = 0;
				zombielist[index].timestamp = Scheduler::instance().clock();
			}
		}

		/* update hit frequency */
		p_t_ = (1-alpha_)*p_t_ + alpha_*hit;
	}

	/* calculate p_sred */
	double p_sred = calc_psred();

	/* calculate p_zap */
	double p_zap;
	if (full_sred_)
		p_zap = calc_full_pzap(p_sred, hit);
	else
		p_zap = calc_simple_pzap(p_sred);

	double u1 = Random::uniform();
	if (u1 <= p_zap) {
//printf("* ");
//fflush(stdout);
		/* drop the packet */
		// deliver to special "drop" target, if defined
		if (drop_tgt_ != NULL) {
			// trace first if asked
			if (drop_trace_ != NULL)
				((Trace *)drop_trace_)->recvOnly(pkt);
			drop_tgt_->recv(pkt);
		} else {
			drop(pkt);
		}
	} else {
		/* enque the packet */
		if (curq_ >= qlim_) {
//printf("@ ");
//fflush(stdout);
			// drop
			// deliver to special "drop" target, if defined
			if (drop_tgt_ != NULL) {
				// trace first if asked
				if (drop_trace_ != NULL)
					((Trace *)drop_trace_)->recvOnly(pkt);
				drop_tgt_->recv(pkt);
			} else {
				drop(pkt);
			}
		} else {
			// enque
			q_->enque(pkt);
			bcount_ += hdr_cmn::access(pkt)->size();
			curq_ = qib_ ? bcount_ : q_->length();
		}
	}
	return;
}

int SREDQueue::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], "drop-target") == 0) {
			if (drop_tgt_ != NULL)
				tcl.resultf("%s", drop_tgt_->name());
			return (TCL_OK);
		}
		if (strcmp(argv[1], "drop-trace") == 0) {
			if (drop_trace_ != NULL) {
				tcl.resultf("%s", drop_trace_->name());
				if (debug_) 
					printf("drop trace exists according to RED\n");
			}
			else {
				if (debug_)
					printf("drop trace doesn't exist according to RED\n");
				tcl.resultf("0");
			}
			return (TCL_OK);
		}
		if (strcmp(argv[1], "trace-type") == 0) {
			tcl.resultf("%s", traceType);
			return (TCL_OK);
		}
	} 
	else if (argc == 3) {
		// attach a file for variable tracing
		if (strcmp(argv[1], "attach") == 0) {
			int mode;
			const char* id = argv[2];
			tchan_ = Tcl_GetChannel(tcl.interp(), (char*)id, &mode);
			if (tchan_ == 0) {
				tcl.resultf("RED: trace: can't attach %s for writing", id);
				return (TCL_ERROR);
			}
			return (TCL_OK);
		}
                // tell RED about link stats
		if (strcmp(argv[1], "link") == 0) {
			LinkDelay* del = (LinkDelay*)TclObject::lookup(argv[2]);
			if (del == 0) {
				tcl.resultf("RED: 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], "drop-target") == 0) {
			NsObject* p = (NsObject*)TclObject::lookup(argv[2]);
			if (p == 0) {
				tcl.resultf("no object %s", argv[2]);
				return (TCL_ERROR);
			}
			drop_tgt_ = p;
			return (TCL_OK);
		}
		if (strcmp(argv[1], "drop-trace") == 0) {
			if (debug_) 
				printf("Ok, Here\n");
			NsObject * t  = (NsObject *)TclObject::lookup(argv[2]);
			if (debug_)  
				printf("Ok, Here too\n");
			if (t == 0) {
				tcl.resultf("no object %s", argv[2]);
				return (TCL_ERROR);
			}
			drop_trace_ = t;
			if (debug_)  
				printf("Ok, Here too too too %d\n", ((Trace *)drop_trace_)->type_);
			return (TCL_OK);
		}
		if (!strcmp(argv[1], "packetqueue-attach")) {
			delete q_;
			if (!(q_ = (PacketQueue*) TclObject::lookup(argv[2])))
				return (TCL_ERROR);
			else {
				pq_ = q_;
				return (TCL_OK);
			}
		}
	}
	return (Queue::command(argc, argv));
}

/*
 * Routine called by TracedVar facility when variables change values.
 * Currently used to trace values of avg queue size, drop probability,
 * and the instantaneous queue size seen by arriving packets.
 * Note that the tracing of each var must be enabled in tcl to work.
 */

void
SREDQueue::trace(TracedVar* v)
{
	char wrk[500], *p;

	if (((p = strstr(v->name(), "curq")) == NULL) &&
	    ((p = strstr(v->name(), "curq")) == NULL)) {
		fprintf(stderr, "SRED:unknown trace var %s\n", v->name());
		return;
	}

	if (tchan_) {
		int n;
		double t = Scheduler::instance().clock();
		// XXX: be compatible with nsv1 RED trace entries
		if (*p == 'c') {
			sprintf(wrk, "Q %g %d", t, int(*((TracedInt*) v)));
		} else {
			sprintf(wrk, "%c %g %g", *p, t,
				double(*((TracedDouble*) v)));
		}
		n = strlen(wrk);
		wrk[n] = '\n'; 
		wrk[n+1] = 0;
		(void)Tcl_Write(tchan_, wrk, n+1);
	}
	return; 
}