/* -*-	Mode:C++; c-basic-offset:8; tab-width:8; indent-tabs-mode:t -*- *//* * Copyright (c) 1997 The 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 Network Research * 	Group at Lawrence Berkeley National 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 lintstatic const char rcsid[] =    "@(#) $Header: /cvsroot/nsnam/ns-2/queue/cbq.cc,v 1.28 2005/07/27 01:13:44 tomh Exp $ (LBL)";#endif//// new version of cbq using the ns-2 fine-grain// objects.  Also, re-orginaize CBQ to look more like how// its description reads in ToN v3n4 and simplify extraneous stuff -KF//// there is a 1-1 relationship between classes and queues, except// that internal nodes in the LS tree don't have queues//// Definitions://	overlimit://		recently used more than allocated link-sharing bandwidth//			(in bytes/sec averaged over specified interval)//	//	level://		all leaves are at level 1//		interior nodes are at a level 1 greater than//		    the highest level number of any of its children////	unsatisfied://		(leaf): underlimit and has demand//		(interior): underlimit and has some descendant w/demand//			[either a leaf or interior descendant]////	formal link-sharing://		class may continue unregulated if either://		1> class is underlimit or at-limit//		2> class has a under(at)-limit ancestor at level i//			and no unsatisfied classes at any levels < i////	ancestors-only link-sharing://		class may continue unregulated if either://		1> class is under/at limit//		2> class has an UNDER-limit ancestor [at-limit not ok]////	top-level link-sharing://		class may continue unregulated if either://		1> class is under/at limit//		2> class has an UNDER-limit ancestor with level//			<= the value of "top-level"#include "queue-monitor.h"#include "queue.h"#include "delay.h"#define	MAXPRIO		10	/* # priorities in scheduler */#define	MAXLEVEL	32	/* max depth of link-share tree(s) */#define	LEAF_LEVEL	1	/* level# for leaves */#define	POWEROFTWO	16class CBQueue;class CBQClass : public Connector {public:	friend class CBQueue;	friend class WRR_CBQueue;	CBQClass();	int	command(int argc, const char*const* argv);	void	recv(Packet*, Handler*);	// from upstream classifierprotected:	void	newallot(double);		// change an allotment	void	update(Packet*, double);	// update when sending pkt	void	delayed(double);		// when overlim/can't borrow	int	satisfied(double);		// satisfied?	int 	demand();			// do I have demand?	int 	leaf();				// am I a leaf class?	int	ancestor(CBQClass*p);		// are we an ancestor of p?	int	desc_with_demand();		// any desc has demand?	CBQueue*	cbq_;			// the CBQueue I'm part of	CBQClass*	peer_;			// peer at same sched prio level	CBQClass*	level_peer_;		// peer at same LS level	CBQClass*	lender_;		// parent I can borrow from	Queue*		q_;			// underlying queue	QueueMonitor*	qmon_;			// monitor for the queue	double		allotment_;		// frac of link bw	double		maxidle_;		// bound on idle time	double		maxrate_;		// bound on bytes/sec rate	double		extradelay_;		// adjustment to delay	double		last_time_;		// last xmit time this class	double		undertime_;		// will become unsat/eligible	double		avgidle_;		// EWMA of idle	int		pri_;			// priority for scheduler	int		level_;			// depth in link-sharing tree	int		delayed_;		// boolean-was I delayed	int		bytes_alloc_;		// for wrr only	int		permit_borrowing_;	// ok to borrow?};class CBQueue : public Queue {public:	CBQueue();	void		reset();	void		enque(Packet*) { abort(); }	void		recv(Packet*, Handler*);	LinkDelay*	link() const { return (link_); }	CBQClass*	level(int n) const { return levels_[n]; }	Packet*		deque();	virtual int	command(int argc, const char*const* argv);	virtual void	addallot(int, double) { }	Packet*	pending_pkt() const { return (pending_pkt_); }	void		sched();	int		toplevel() {	// are we using toplevel?// 		return (eligible_ == &eligible_toplevel);		return (eligible_ == TOPLEVEL);	}	void		toplevel_arrival(CBQClass*, double);protected:	Event		intr_;	int		algorithm(const char *);	virtual int	insert_class(CBQClass*);	int		send_permitted(CBQClass*, double);	CBQClass*	find_lender(CBQClass*, double);	void		toplevel_departure(CBQClass*, double);	CBQClass*	last_lender_;	Packet*		pending_pkt_;		// queued packet	LinkDelay*	link_;			// managed link	CBQClass*	active_[MAXPRIO];	// classes at prio of index	CBQClass*	levels_[MAXLEVEL+1];	// LL of classes per level	int		maxprio_;		// highest prio# seen	int		maxpkt_;		// largest pkt (used by WRR)	int		maxlevel_;		// highest level# seen	int		toplevel_;		// for top-level LS// 	typedef int (CBQueue::*eligible_type_)(CBQClass*, double);// 	eligible_type_ eligible_;		// eligible function	enum eligible_type_ { NONE, FORMAL, ANCESTORS, TOPLEVEL };	eligible_type_ eligible_;	int	eligible_formal(CBQClass*, double);	int	eligible_ancestors(CBQClass*, double) { return (1); }	int	eligible_toplevel(CBQClass* cl, double) {		return(cl->level_ <= toplevel_);	}};static class CBQQueueClass : public TclClass {public:	CBQQueueClass() : TclClass("Queue/CBQ") { }	TclObject* create(int, const char*const*) {		return (new CBQueue);	}} class_cbq;static class CBQClassClass : public TclClass {public:	CBQClassClass() : TclClass("CBQClass") { }	TclObject* create(int, const char*const*) {		return (new CBQClass);	}} class_cbqclass;CBQueue::CBQueue() : last_lender_(NULL), pending_pkt_(NULL), link_(NULL),	maxprio_(-1), maxpkt_(-1), maxlevel_(-1), toplevel_(MAXLEVEL),// 	eligible_((eligible_type_)NULL)	eligible_(NONE){	bind("maxpkt_", &maxpkt_);	memset(active_, '\0', sizeof(active_));	memset(levels_, '\0', sizeof(levels_));}/* * schedule ourselves, used by CBQClass::recv */voidCBQueue::sched(){	Scheduler& s = Scheduler::instance();	blocked_ = 1;	s.schedule(&qh_, &intr_, 0);}/* * invoked by passing a packet from one of our managed queues * basically provides a queue of one packet */voidCBQueue::recv(Packet* p, Handler*){	if (pending_pkt_ != NULL)		abort();	blocked_ = 1;	pending_pkt_ = p;}voidCBQueue::reset(){	// don't do anything	// in particular, don't let Queue::reset() call	// our deque() method}intCBQueue::algorithm(const char *arg){	if (*arg == '0' || (strcmp(arg, "ancestor-only") == 0)) {// 		eligible_ = &eligible_ancestors;		eligible_ = ANCESTORS;		return (1);	} else if (*arg == '1' || (strcmp(arg, "top-level") == 0)) {// 		eligible_ = &eligible_toplevel;		eligible_ = TOPLEVEL;		return (1);	} else if (*arg == '2' || (strcmp(arg, "formal") == 0)) {// 		eligible_ = &eligible_formal;		eligible_ = FORMAL;		return (1);	} else if (*arg == '3' || (strcmp(arg, "old-formal") == 0)) {		fprintf(stderr, "CBQ: old-formal LS not supported\n");		return (-1);	}	return (-1);}/* * * toplevel_arrival:	called only using TL link sharing on arrival * toplevel_departure:	called only using TL link sharing on departure */voidCBQueue::toplevel_departure(CBQClass *cl, double now){	if (toplevel_ >= last_lender_->level_) {		if ((cl->qmon_->pkts() <= 1) ||		    last_lender_->undertime_ > now) {			toplevel_ = MAXLEVEL;		} else {			toplevel_ = last_lender_->level_;		}	}}voidCBQueue::toplevel_arrival(CBQClass *cl, double now){	if (toplevel_ > 1) {		if (cl->undertime_ < now)			toplevel_ = 1;		else if (toplevel_ > 2 && cl->permit_borrowing_ && cl->lender_ != NULL) {			if (cl->lender_->undertime_ < now)				toplevel_ = 2;		}	}}/* * deque: this gets invoked by way of our downstream * (i.e. linkdelay) neighbor doing a 'resume' on us * via our handler (by Queue::resume()), or by our upstream * neighbor when it gives us a packet when we were * idle */Packet *CBQueue::deque(){	Scheduler& s = Scheduler::instance();	double now = s.clock();	CBQClass* first = NULL;	CBQClass* eligible = NULL;	CBQClass* cl;	register int prio;	Packet* rval;	int none_found = 0;	/*	 * prio runs from 0 .. maxprio_	 *	 * round-robin through all the classes at priority 'prio'	 * 	if any class is ok to send, resume it's queue	 * go on to next lowest priority (higher prio nuber) and repeat	 * [lowest priority number is the highest priority]	 */	for (prio = 0; prio <= maxprio_; prio++) {		// see if there is any class at this prio		if ((cl = active_[prio]) == NULL) {			// nobody at this prio level			continue;		}		// look for underlimit peer with something to send		do {			// anything to send?			if (cl->demand()) {				if (first == NULL && cl->permit_borrowing_ && cl->lender_ != NULL)					first = cl;				if (send_permitted(cl, now)) {					// ok to send					eligible = cl;					goto found;				} else {					// not ok right now					cl->delayed(now);				}			}			cl = cl->peer_;	// move to next at same prio		} while (cl != active_[prio]);	}	// did not find anyone so let first go	// eligible will be NULL at this point	if (first != NULL) {		none_found = 1;		eligible = first;	}found:	if (eligible != NULL) {		active_[eligible->pri_] = eligible->peer_;		// eligible->q_->unblock();		eligible->q_->resume();	// fills in pending		if (pending_pkt_ && !none_found) {			eligible->update(pending_pkt_, now);			if (toplevel())				toplevel_departure(eligible, now);		}	}	rval = pending_pkt_;	pending_pkt_ = NULL;	return (rval);}/* * we are permitted to send if either *	1> we are not overlimit (ie we are underlimit or at limit) *	2> one of the varios algorithm-dependent conditions is met * * if we are permitted, who did we borrow from? [could be ourselves * if we were not overlimit] */int CBQueue::send_permitted(CBQClass* cl, double now){	if (cl->undertime_ < now) {		cl->delayed_ = 0;		last_lender_ = cl;		return (1);	} else if (cl->permit_borrowing_ &&		   (((cl = find_lender(cl, now)) != NULL))) {		last_lender_ = cl;		return (1);	}	return (0);}/* * find_lender(class, time) * *	find a lender for the provided class according to the *	various algorithms * */CBQClass*CBQueue::find_lender(CBQClass* cl, double now){	if ((!cl->permit_borrowing_) || ((cl = cl->lender_) == NULL))		return (NULL);		// no ancestor to borrow from	while (cl != NULL) {		// skip past overlimit ancestors		//	if using TL and we're above the TL limit		//	do early out		if (cl->undertime_ > now) {			if (toplevel() && cl->level_ > toplevel_)				return (NULL);			cl = cl->lender_;			continue;		}		// found what may be an eligible		// lender, check using per-algorithm eligibility		// criteria		// XXX we explicitly invoke this indirect method with		// the "this" pointer because MS VC++ can't parse it		// without it...// 		if ((this->*eligible_)(cl, now))// 			return (cl);		switch (eligible_) {		case TOPLEVEL:			if (eligible_toplevel(cl, now))				return (cl);			break;		case ANCESTORS:			if (eligible_ancestors(cl, now))				return (cl);			break;		case FORMAL:			if (eligible_formal(cl, now))				return (cl);			break;		default:			fprintf(stderr, "Wrong eligible_\n");			abort();		}		cl = cl->lender_;	}	return (cl);}/* * rule #2 for formal link-sharing *	class must have no unsatisfied classes below it */intCBQueue::eligible_formal(CBQClass *cl, double now){	int level;	CBQClass *p;	// check from leaf level to (cl->level - 1)	for (level = LEAF_LEVEL; level < cl->level_; level++) {		p = levels_[level];		while (p != NULL) {			if (!p->satisfied(now))				return (0);			p = p->level_peer_;		}	}	return (1);}/* * insert a class into the cbq object */intCBQueue::insert_class(CBQClass *p){	p->cbq_ = this;	/*	 * Add to circularly-linked list "active_"	 *    of peers for the given priority.	 */	if (p->pri_ < 0 || p->pri_ > (MAXPRIO-1)) {		fprintf(stderr, "CBQ class %s has invalid pri %d\n",			p->name(), p->pri_);		return (-1);	}	if (p->q_ != NULL) {		// only leaf nodes (which have associated queues)		// are scheduled		if (active_[p->pri_] != NULL) {			p->peer_ = active_[p->pri_]->peer_;			active_[p->pri_]->peer_ = p;		} else {			p->peer_ = p;			active_[p->pri_] = p;		}		if (p->pri_ > maxprio_)			maxprio_ = p->pri_;	}	/*	 * Compute maxrate from allotment.	 * convert to bytes/sec	 *	and store the highest prio# we've seen	 */	if (p->allotment_ < 0.0 || p->allotment_ > 1.0) {		fprintf(stderr, "CBQ class %s has invalid allot %f\n",			p->name(), p->allotment_);		return (-1);	}	if (link_ == NULL) {		fprintf(stderr, "CBQ obj %s has no link!\n", name());		return (-1);	}	if (link_->bandwidth() <= 0.0) {		fprintf(stderr, "CBQ obj %s has invalid link bw %f on link %s\n",			name(), link_->bandwidth(), link_->name());		return (-1);	}	p->maxrate_ = p->allotment_ * (link_->bandwidth() / 8.0);	addallot(p->pri_, p->allotment_);	/*