cbq.cc

CBQ的源代码

/* -*-	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 lint
static 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	16

class 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 classifier

protected:

	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
 */

void
CBQueue::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
 */

void
CBQueue::recv(Packet* p, Handler*)
{

	if (pending_pkt_ != NULL)
		abort();

	blocked_ = 1;
	pending_pkt_ = p;
}

void
CBQueue::reset()
{
	// don't do anything
	// in particular, don't let Queue::reset() call
	// our deque() method
}

int
CBQueue::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
 */

void
CBQueue::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_;
		}
	}
}

void
CBQueue::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
 */
int
CBQueue::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
 */

int
CBQueue::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_);

	/*