#include <REDQueue.h>

Inheritance diagram for REDQueue:

Protected Member Functions
virtual void	initialize ()
virtual void	finish ()
virtual bool	enqueue (cMessage *msg)
virtual cMessage *	dequeue ()
virtual void	sendOut (cMessage *msg)
Protected Attributes
double	wq
double	minth
double	maxth
double	maxp
double	pkrate
cQueue	queue
double	avg
simtime_t	q_time
int	count
cGate *	outGate
cOutVector	avgQlenVec
cOutVector	qlenVec
cOutVector	dropVec
long	numEarlyDrops

Detailed Description

RED queue. See NED for more info.

Definition at line 28 of file REDQueue.h.

Member Function Documentation

cMessage * REDQueue::dequeue ( ) [protected, virtual]

Redefined from PassiveQueueBase.

Implements PassiveQueueBase.

Definition at line 137 of file REDQueue.cc.

{
    if (queue.empty())
        return NULL;

    //"
    // when queue becomes empty
    //    q_time <- time
    //"
    cMessage *pk = (cMessage *)queue.pop();
    if (queue.length()==0)
        q_time = simTime();

    // statistics
    qlenVec.record(queue.length());

    return pk;
}

bool REDQueue::enqueue ( cMessage * msg ) [protected, virtual]

Redefined from PassiveQueueBase.

Implements PassiveQueueBase.

Definition at line 55 of file REDQueue.cc.

{
    //"
    // for each packet arrival
    //    calculate the new average queue size avg:
    //        if the queue is nonempty
    //            avg <- (1-wq)*avg + wq*q
    //        else
    //            m <- f(time-q_time)
    //            avg <- (1-wq)^m * avg
    //"
    if (!queue.empty())
    {
        avg = (1-wq)*avg + wq*queue.length();
    }
    else
    {
        // Note: f() is supposed to estimate the number of packets
        // that could have arrived during the idle interval (see Section 11
        // of the paper). We use pkrate for this purpose.
        double m = SIMTIME_DBL(simTime()-q_time) * pkrate;
        avg = pow(1-wq, m) * avg;
    }

    // statistics
    avgQlenVec.record(avg);

    //"
    //    if minth <= avg < maxth
    //        increment count
    //        calculate probability pa:
    //            pb <- maxp*(avg-minth) / (maxth-minth)
    //            pa <- pb / (1-count*pb)
    //        with probability pa:
    //            mark the arriving packet
    //            count <- 0
    //    else if maxth <= avg
    //        mark the arriving packet
    //        count <- 0
    //    else count <- -1
    //"

    bool mark = false;
    if (minth<=avg && avg<maxth)
    {
        count++;
        double pb = maxp*(avg-minth) / (maxth-minth);
        double pa = pb / (1-count*pb);
        if (dblrand() < pa)
        {
            EV << "Random early packet drop (avg queue len=" << avg << ", pa=" << pa << ")\n";
            mark = true;
            count = 0;
            numEarlyDrops++;
        }
    }
    else if (maxth <= avg)
    {
        EV << "Avg queue len " << avg << " >= maxth, dropping packet.\n";
        mark = true;
        count = 0;
    }
    else
    {
        count = -1;
    }

    // carry out decision
    if (mark || queue.length()>=maxth) // maxth is also the "hard" limit
    {
        delete msg;
        dropVec.record(1);
        return true;
    }
    else
    {
        queue.insert(msg);
        qlenVec.record(queue.length());
        return false;
    }
}

void REDQueue::finish ( ) [protected, virtual]

Reimplemented from PassiveQueueBase.

Definition at line 161 of file REDQueue.cc.

{
    PassiveQueueBase::finish();
    recordScalar("packets dropped early by RED", numEarlyDrops);
}

void REDQueue::initialize ( ) [protected, virtual]

Reimplemented from PassiveQueueBase.

Definition at line 25 of file REDQueue.cc.

{
    PassiveQueueBase::initialize();
    queue.setName("l2queue");

    avgQlenVec.setName("avg queue length");
    qlenVec.setName("queue length");
    dropVec.setName("drops");

    // configuration
    wq = par("wq");
    minth = par("minth");
    maxth = par("maxth");
    maxp = par("maxp");
    pkrate = par("pkrate");

    outGate = gate("out");

    // state
    avg = 0;
    q_time = 0;
    count = -1;
    numEarlyDrops = 0;

    WATCH(avg);
    WATCH(q_time);
    WATCH(count);
    WATCH(numEarlyDrops);
}