/* -*-	Mode:C++; c-basic-offset:8; tab-width:8; indent-tabs-mode:t -*- */
/*
 * Copyright (c) 1996-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.
 */

#ifndef lint
static const char rcsid[] =
    "@(#) $Header: /nfs/jade/vint/CVSROOT/ns-2/common/ivs.cc,v 1.16 2000/09/01 03:04:05 haoboy Exp $ (LBL)";
#endif

#include <stdlib.h>
#include <math.h>
#include "message.h"
#include "trace.h"
#include "agent.h"

/* ivs data packet; ctrl packets are sent back as "messages" */
struct hdr_ivs {
	double ts_;			/* timestamp sent at source */
	u_int8_t S_;
	u_int8_t R_;
	u_int8_t state_;
	u_int8_t rshft_;
	u_int8_t kshft_;
	u_int16_t key_;
	double maxrtt_;
	int seqno_;

	static int offset_;
	inline static int& offset() { return offset_; }
	inline static hdr_ivs* access(Packet* p) {
		return (hdr_ivs*) p->access(offset_);
	}

	/* per-field member functions */
	double& ts() { return (ts_); }
	u_int8_t& S() { return (S_); }
	u_int8_t& R() { return (R_); }
	u_int8_t& state() { return (state_); }
	u_int8_t& rshft() { return (rshft_); }
	u_int8_t& kshft() { return (kshft_); }
	u_int16_t& key() { return (key_); }
	double& maxrtt() { return (maxrtt_); }
	int& seqno() { return (seqno_); }
};

int hdr_ivs::offset_;

static class IvsHeaderClass : public PacketHeaderClass {
public:
	IvsHeaderClass() : PacketHeaderClass("PacketHeader/IVS",
					     sizeof(hdr_ivs)) {
		bind_offset(&hdr_ivs::offset_);
	}
} class_ivshdr;

class IvsSource : public Agent {
public:
	IvsSource();
protected:
	void reset();
	void recv(Packet *pkt, Handler*);
	void sendpkt();

	int S_;
	int R_;
	int state_;
#define ST_U 0
#define ST_L 1
#define ST_C 2
	int rttShift_;
	int keyShift_;
	int key_;
	double maxrtt_;
};

struct Mc_Hole {
	int start;
	int end;
	double time;
	Mc_Hole* next;
};

class IvsReceiver : public Agent {
public:
	IvsReceiver();
	int command(int argc, const char*const* argv);
protected:
	void recv(Packet *pkt, Handler*);
	void update_ipg(double now);
	int lossMeter(double timeDiff, u_int32_t seq, double maxrtt);
	void upcall_respond(double ts, int matchS);
	void upcall_rtt_solicit(double ts, int rshift);

	int state_;
	u_int32_t nextSeq_;

	double timeMean_;
	double timeVar_;
	double ipg_;		/* interpkt gap (estimator) */
	Mc_Hole* head_;
	Mc_Hole* tail_;
	double lastPktTime_;
	int ignoreR_;
	double lastTime_;	/* last time a resp pkt sent */
	int key_;
};

static class IvsSourceClass : public TclClass {
public:
	IvsSourceClass() : TclClass("Agent/IVS/Source") {}
	TclObject* create(int, const char*const*) {
		return (new IvsSource());
	}
} class_ivs_source;

static class IvsReceiverClass : public TclClass {
public:
	IvsReceiverClass() : TclClass("Agent/IVS/Receiver") {}
	TclObject* create(int, const char*const*) {
		return (new IvsReceiver());
	}
} class_ivs_receiver;

IvsSource::IvsSource() : Agent(PT_MESSAGE), S_(0), R_(0), state_(ST_U),
	rttShift_(0), keyShift_(0), key_(0), maxrtt_(0)
{
	bind("S_", &S_);
	bind("R_", &R_);
	bind("state_", &state_);
	bind("rttShift_", &rttShift_);
	bind("keyShift_", &keyShift_);
	bind("key_", &key_);
	bind("maxrtt_", &maxrtt_);
}

void IvsSource::reset()
{
}

/*
 * main reception path - should only see acks, otherwise the
 * network connections are misconfigured
 */
void IvsSource::recv(Packet* pkt, Handler*)
{
	char wrk[128];/*XXX*/
	Tcl& tcl = Tcl::instance();
	hdr_msg *q = hdr_msg::access(pkt);
	sprintf(wrk, "%s handle {%s}", name(), q->msg());
	tcl.eval(wrk);
	Packet::free(pkt);
}

#ifdef notdef
void IvsSource::probe_timeout()
{
	rndStart_ = now;

	if (keyShift_ == 15) {
		if (key_ == 0) {
			if (solicitedResponses_ == 0)
				estReceivers_ = 0;
				/*
				 * Got through a round without being LOADED.
				 * increase send rate.
				 */
			if (state_ == ST_U)
				increase();

				/* Reset keys et al */
			S_ = 1;
			state_ = ST_U;

				/*XXX*/
			setRttSolicit(mcstate);

			solicitedResponses_ = 0;
			keyShift_ = startShift_;
				/*XXX do all this in tcl? */
			setkey();
			
		} else { mcstate->hdr.key = 0; }
	} else {
		if (probeTimeout_ > 0)
			++keyShift_;
	}
	sched(pktTime + 2 * maxrtt_, IVS_TIMER_PROBE);
}
#endif

void IvsSource::sendpkt()
{
	Packet* pkt = allocpkt();
	hdr_ivs *p = hdr_ivs::access(pkt);
	/*fill in ivs fields */
	p->ts() = Scheduler::instance().clock();
	p->S() = S_;
	p->R() = R_;
	p->state() = state_;
	p->rshft() = rttShift_;
	p->kshft() = keyShift_;
	p->key() = key_;
	p->maxrtt() = maxrtt_;

	target_->recv(pkt, (Handler *)0);
}

IvsReceiver::IvsReceiver() : Agent(PT_MESSAGE), state_(ST_U),
	nextSeq_(0),
	timeMean_(0.), timeVar_(0.),/*XXX*/
	ipg_(0.),
	head_(0),
	tail_(0),
	lastPktTime_(0.),
	ignoreR_(0),
	lastTime_(0.),
	key_(0)
{
	bind("ignoreR_", &ignoreR_);
	bind("key_", &key_);
	bind("state_", &state_);
	bind("packetSize_", &size_);
}

inline void IvsReceiver::update_ipg(double v)
{
	/* Update the estimated interpacket gap */
	ipg_ = (15 * ipg_ + v) / 16;
}

/*
 * timestamp comes in milliseconds since start of connection according to
 * remote clock
 * now is milliseconds since start of connection
 * rtt in milliseconds
 * This congestion meter is not terribly good at figuring out when the net is 
 * loaded, since the loss of a packet over a rtt is a transitory event
 * Eventually we ought to have a memory thing, that records state once a 
 * maxrtt, with thresholds to decide current state
 */
int IvsReceiver::lossMeter(double timeDiff, u_int32_t seq, double maxrtt)
{
	/*
	 * The congestion signal is calculated here by measuring the loss in a 
	 * given period of packets - if the threshold for lost packets is
	 * passed then signal Congested.  If there are no lost packets,
	 * then we are at UNLOADED, else LOADED
	 */
	/* if sequence number is next, increase expected number */
	
	double now = Scheduler::instance().clock();
	if (nextSeq_ == 0)
		nextSeq_ = seq + 1;
	else if (seq == nextSeq_)
		nextSeq_++;
	else if (seq > nextSeq_) {
#ifdef notdef
		if (trace_ != 0) {
			sprintf(trace_->buffer(), "d %g %d",
				lastPktTime_, seq - nextSeq_);
			trace_->dump();
		}
#endif

		/* This is definitely a hole */
		Mc_Hole* hole = new Mc_Hole;
		hole->time = now;
		hole->start = nextSeq_;
		hole->end = seq - 1;
		hole->next = 0;
		/* Now add it to the list */
		if (head_ == NULL) {
			head_ = hole;
			tail_ = hole;
		} else {
			tail_->next = hole;
			tail_ = hole;
		}
		nextSeq_ = seq + 1;
	} else {
		/* XXX can't happen in current ns simulations */
		fprintf(stderr, "ns: ivs rcvr: seq number went backward\n");
		abort();
	}

	/* update the calculation of the variance in the rtt */
	/* get the time averaged mean of the difference */
	if (timeMean_ == 0)
		timeMean_ = timeDiff;
	else
		timeMean_ = (7 * timeMean_ + timeDiff) / 8;

	timeDiff -= timeMean_;
	if (timeDiff < 0)
		timeDiff = -timeDiff;

	timeVar_ = (7 * timeVar_ + timeDiff) / 8;

	int lostPkts = 0;
	/* 
	 * Check down the list of holes, discarding those that before
	 * now-rttvar-rtt, counting those that fall within
	 * now-rttvar to now-rttvar-rtt
	 */
	if (head_ == 0)
		return (ST_U);

	Mc_Hole *cur = head_, *prev = NULL;

	double validEnd = now - 2 * timeVar_;
	double validStart = validEnd - maxrtt;

	/* for each hole, if it is older than required, dump it */
	/* If it is valid, add the size to the loss count */
	/* Go to the next hole */

	while (cur != NULL) {
		if (cur->time < validStart) {
			if (prev == NULL)
				head_ = cur->next;
			else
				prev->next = cur->next;
			delete cur;
			if (prev == NULL)
				cur = head_;
			else
				cur = prev->next;
		} else {
			if (cur->time < validEnd)
				lostPkts += cur->end - cur->start + 1;
			prev = cur;
			cur = cur->next;
		}
	}

	/*
	 * Update the moving average calculation of the number of holes, if
	 * nowMs is another rtt away
	 */

	double pps = (ipg_ != 0) ? maxrtt / ipg_ : 0.;

/*XXX*/
#ifdef notdef
	if (trace_ != 0) {
		double now = Scheduler::instance().clock();
		sprintf(trace_->buffer(), "%.17g %g", now,
			(double)lostPkts / pps);
		trace_->dump();
	}
#endif

/*XXX*/
#define LOSSCONGTH 15
#define LOSSLOADTH 5
	/* If the rtt is smaller than the ipg, set the thresholds to 0,1,2 */
	if ((pps * LOSSCONGTH) / 100 < 2)
		pps = 200 / LOSSCONGTH;

	if (lostPkts <= (LOSSLOADTH * pps) / 100)
		return (ST_U);
	else if (lostPkts <= (LOSSCONGTH * pps) / 100)
		return (ST_L);
	else
		return (ST_C);
}

void IvsReceiver::recv(Packet* pkt, Handler*)
{
	hdr_ivs *p = hdr_ivs::access(pkt);
	double now = Scheduler::instance().clock();

	if (lastPktTime_ == 0.) {
		lastPktTime_ = now;
		Packet::free(pkt);
		return;
	}
	update_ipg(now - lastPktTime_);
	double ts = p->ts();
	int prevState = state_;
	state_ = lossMeter(now - ts, p->seqno(), p->maxrtt());

	lastPktTime_ = now;

	/* If soliciting rtt */
	if (p->R() && !ignoreR_)
		/* upcall into tcl */
		upcall_rtt_solicit(ts, p->rshft());

	/*
	 * send a response if we're congested and its over an rtt since
	 * we last sent one OR
	 * any response is solicited to estimate size and we match the key OR
	 * we're LOADED and we match the key and its over an rtt since we last
	 * sent a response
	 */

	if (now - lastTime_ < p->maxrtt() && state_ <= prevState) {
		Packet::free(pkt);
		return;
	}

	int shift = p->kshft();
	int match;
	if (p->key() == 0)
		match = 1;
	else
		match = (key_ >> shift) == (p->key() >> shift);

	int matchS = match ? p->S() : 0;

	if (state_ == ST_C || matchS || (match && state_ == ST_L)) {
		upcall_respond(ts, matchS);
		lastTime_ = now;
	}

	Packet::free(pkt);
}

void IvsReceiver::upcall_respond(double ts, int matchS)
{
	Tcl::instance().evalf("%s respond %.17g %d", name(), ts, matchS);
}

void IvsReceiver::upcall_rtt_solicit(double ts, int rshift)
{
	Tcl::instance().evalf("%s solicit-rtt %.17g %d", name(), ts, rshift);
}

int IvsReceiver::command(int argc, const char*const* argv)
{
	Tcl& tcl = Tcl::instance();
	if (argc == 3) {
		if (strcmp(argv[1], "send") == 0) {
			Packet* pkt = allocpkt();
			hdr_msg* p = hdr_msg::access(pkt);
			const char* s = argv[2];
			int n = strlen(s);
			if (n >= p->maxmsg()) {
				tcl.result("message too big");
				Packet::free(pkt);
				return (TCL_ERROR);
			}
			strcpy(p->msg(), s);
			target_->recv(pkt, (Handler*)0);
			return (TCL_OK);
		}
	}
	return (Agent::command(argc, argv));
}