priqueue.cc

INSIGNIA是专门为无线ad hoc网络设计的qos信令协议

/* -*- c++ -*-
   priqueue.cc
   
   A simple priority queue with a remove packet function
   $Id: priqueue.cc,v 1.19 1999/06/01 17:45:59 ml Exp $
   */

#include <object.h>
#include <packet.h>
#include <cmu/cmu-trace.h>
#include <cmu/priqueue.h>

#define PRIQUEUE_DEBUG 1

PriQueue_List PriQueue::prq_head = { 0 };

static class PriQueueClass : public TclClass {
public:
  PriQueueClass() : TclClass("PriQueue") {}
  TclObject* create(int, const char*const*) {
    return (new PriQueue);
  }
} class_PriQueue;

/* ======================================================================
   Priority Queue Handler
   ====================================================================== */
void PriQueueHandler::handle(Event*)
{
        qh_ifq->prq_resume();
}       

/* ======================================================================
   PriQueue - public routines
   ====================================================================== */
PriQueue::PriQueue() : Connector(), prq_qh(this)
{
	int i;

	for(i = 0; i < IFQ_MAX; i++) {
		prq_snd[i].ifq_head = prq_snd[i].ifq_tail = 0;
		prq_snd[i].ifq_len = 0;
		prq_snd[i].ifq_maxlen = IFQ_MAXLEN;
		prq_snd[i].ifq_drops = 0;
	}
	prq_logtarget = 0;		// no logging target by default
	prq_ipaddr = 0;
	prq_blocked = 0;
	LIST_INSERT_HEAD(&prq_head, this, prq_link);
}

int
PriQueue::command(int argc, const char*const* argv)
{
	if (argc == 2 && strcasecmp(argv[1], "reset") == 0) {
		Terminate();
		//FALL-THROUGH to give parents a chance to reset
	} else if(argc == 3) {
		if(strcmp(argv[1], "logtarget") == 0) {
			prq_logtarget = (Trace*) TclObject::lookup(argv[2]);
			assert(prq_logtarget);
			return (TCL_OK);
		}
		else if(strcmp(argv[1], "ipaddr") == 0) {
			prq_ipaddr = atoi(argv[2]);
			assert(prq_ipaddr > 0);
			return (TCL_OK);
		}
	}
	return Connector::command(argc, argv);
}

void
PriQueue::recv(Packet *p, Handler *)
{
#if PRIQUEUE_DEBUG > 0
	prq_validate();
#endif
	prq_enqueue(p);
#if PRIQUEUE_DEBUG > 0
	prq_validate();
#endif
}

void
PriQueue::prq_resume()
{
	Packet *p;

	assert(prq_blocked);
#if PRIQUEUE_DEBUG > 0
	prq_validate();
#endif
	p = prq_dequeue();
	if (p != 0) {
                target_->recv(p, &prq_qh);
        } else {
		prq_blocked = 0;
        }
}


/*
 * Called at the end of the simulation to purge the IFQ.
 */
void
PriQueue::Terminate()
{
	Packet *p;
	while((p = prq_dequeue())) {
		drop(p, DROP_END_OF_SIMULATION);
	}
}

typedef int (*PacketFilter)(Packet *, void *);
#define FILTER_KEEP   0
#define FILTER_REMOVE 1

void 
PriQueue::prq_purge_filter(PacketFilter filter, void * data)
{
	int q;
	Packet *p;

#if PRIQUEUE_DEBUG > 0
	prq_validate();
#endif
	for(q = 0; q < IFQ_MAX; q++) {
		for(p = prq_snd[q].ifq_head; p; ) {
			Packet *pn = p->next_;

			if(filter(p, data)) {
				IF_DROP(&prq_snd[q]);
				drop(p, DROP_IFQ_FILTER);
			}

			p = pn;
		}
	}
#if PRIQUEUE_DEBUG > 0
	prq_validate();
#endif
}

Packet*
PriQueue::prq_get_nexthop(nsaddr_t id)
{
	int q;
	Packet *p, *pprev = 0;
	struct ifqueue *ifq;

#if PRIQUEUE_DEBUG > 0
	prq_validate();
#endif
	for(q = 0; q < IFQ_MAX; q++) {
		ifq = &prq_snd[q];
		pprev = 0;
		for(p = ifq->ifq_head; p; p = p->next_) {
			struct hdr_cmn *ch = HDR_CMN(p);

			if(ch->next_hop() == id)
				break;
			pprev = p;
		}
	}

	if(p) {
		if(p == ifq->ifq_head) {
			assert(pprev == 0);

			IF_DEQUEUE(ifq, p);
			/* don't increment drop counter */
#if PRIQUEUE_DEBUG > 0
			prq_validate();
#endif
			return p;
		} else {
			assert(pprev);
			pprev->next_ = p->next_;
	
			if(p == ifq->ifq_tail)
				ifq->ifq_tail = pprev;
			ifq->ifq_len--;

#if PRIQUEUE_DEBUG > 0
			prq_validate();
#endif
			p->next_ = 0;
			return p;
		}
	}

	return (Packet*) 0;
}

int
PriQueue::prq_length()
{
	int q, tlen = 0;

	for(q = 0; q < IFQ_MAX; q++) {
		tlen += prq_snd[q].ifq_len;
	}

	return tlen;
}

/* INSIGNIA EXTN */
int
PriQueue::prq_class_length(int cl)
{
	int q, tlen = 0;

	for(q = 0; q < IFQ_MAX; q++) {
		tlen += prq_snd[q].ifq_len;
	}

	return tlen;
}

/* ======================================================================
   PriQueue - private routines
   ====================================================================== */
void
PriQueue::prq_enqueue(Packet *p)
{
	int q = prq_assign_queue(p);
	struct ifqueue *ifq = &prq_snd[q];

	if(IF_QFULL(ifq)) {
		IF_DROP(ifq);
		drop(p, DROP_IFQ_QFULL);
		return;
	}
	IF_ENQUEUE(ifq, p);

	/*
	 * Start queue if idle...
	 */
	if(prq_blocked == 0) {
		p = prq_dequeue();
		prq_blocked = 1;
		target_->recv(p, &prq_qh);
	}
}

Packet*
PriQueue::prq_dequeue(void)
{
	Packet *p;
	int q;

	for(q = 0; q < IFQ_MAX; q++) {
		if(prq_snd[q].ifq_len > 0) {
			assert(prq_snd[q].ifq_head);
			IF_DEQUEUE(&prq_snd[q], p);
			return p;
		}
	}
	return (Packet*) 0;
}

int
PriQueue::prq_assign_queue(Packet *p)
{
        struct hdr_cmn *ch = HDR_CMN(p);
	struct hdr_ip *iph = HDR_IP(p);

	switch(ch->ptype()) {
	case PT_AODV:
	case PT_DSR:
	case PT_IMEP:
	case PT_MESSAGE:	/* used by DSDV */
	case PT_TORA:
		return IFQ_RTPROTO;

	case PT_AUDIO:
	case PT_VIDEO:
		return IFQ_REALTIME;

	case PT_ACK:
		return IFQ_LOWDELAY;

	default:
	        if(iph->tos_ == 1) return IFQ_REALTIME; // INSIGNIA EXTN
		if(iph->tos_ == 2) return IFQ_QOSREPO;  // INSIGNIA EXTN
		else return IFQ_NORMAL;
	}
}

void
PriQueue::prq_validate()
{
	int q, qlen;
	Packet *p;
	struct ifqueue *ifq;

	for(q = 0; q < IFQ_MAX; q++) {
		ifq = &prq_snd[q];
		qlen = 0;
			
		if(ifq->ifq_head == 0) {
			assert(ifq->ifq_len == 0);
			assert(ifq->ifq_head == ifq->ifq_tail);
			continue;
		}

		for(p = ifq->ifq_head; p; p = p->next_)
			qlen++;

		assert(qlen == ifq->ifq_len);
		assert(qlen <= ifq->ifq_maxlen);
	}
}