rem.cc

Go to the documentation of this file.

/* -*-  Mode:C++; c-basic-offset:8; tab-width:8; indent-tabs-mode:t -*- */
/*
 * Copyright (c) 1990-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.
 *
 *   
 * ns-2 code written by: Sanjeewa Athuraliya (sanjeewa@caltech.edu)
 *                       Caltech, Pasadena,
 *                       CA 91125
 *                       Victor Li
 *                       University of Melbourne, Parkville
 *                       Vic., Australia.
 *
 * Ref: Active Queue Management (REM), IEEE Network, May/June 2001.
 *      http://netlab.caltech.edu
 */

#include <math.h>
#include <sys/types.h>
#include "config.h"
#include "template.h"
#include "random.h"
#include "flags.h"
#include "delay.h"
#include "rem.h"
#include <iostream>

static class REMClass : public TclClass {
public:
        REMClass() : TclClass("Queue/REM") {}
        TclObject* create(int, const char*const*) {
                return (new REMQueue);
        }
} class_rem;


void REMQueue :: set_update_timer()
{
        rem_timer_.resched(remp_.p_updtime);
}

void REMQueue :: timeout()
{
        //do price update
        run_updaterule();
        set_update_timer();
}


void REMTimer :: expire (Event *e) {
         a_->timeout();
}



REMQueue::REMQueue() : link_(NULL), tchan_(0), rem_timer_(this) 
{
        bind("gamma_", &remp_.p_gamma);
        bind("phi_", &remp_.p_phi);
        bind("inw_", &remp_.p_inw);
        bind("mean_pktsize_", &remp_.p_pktsize); 
        bind("pupdtime_", &remp_.p_updtime); 
        bind("pbo_", &remp_.p_bo); 
        bind("prob_", &remv_.v_prob);               // dropping probability
        bind("curq_", &curq_);                      // current queue size
        bind("pmark_", &pmark_);        //number of packets being marked 
        bind_bool("markpkts_", &markpkts_); /* Whether to mark or drop?  Default is drop */
        bind_bool("qib_", &qib_); /* queue in bytes? */ 

        q_ = new PacketQueue();                     // underlying queue
        pq_ = q_;
        reset();

#ifdef notdef
print_remp();
print_remv();
#endif

}

void REMQueue::reset()
{
        /*
         * Compute the "packet time constant" if we know the
         * link bandwidth.  The ptc is the max number of 
         * pkts per second which can be placed on the link.
         * The link bw is given in bits/sec, so scale psize
         * accordingly.
         */
         
        if (link_)
                remp_.p_ptc = link_->bandwidth() / (8.0 * remp_.p_pktsize);

        remv_.v_pl = 0.0;
        remv_.v_prob = 0.0;
        remv_.v_in = 0.0;
        remv_.v_ave = 0.0;
        remv_.v_count = 0.0;

        remv_.v_pl1 = 0.0;
        remv_.v_pl2 = 0.0;
        remv_.v_in1 = 0.0;
        remv_.v_in2 = 0.0;
        pmark_ = 0.0;
        bcount_ = 0; 
        
        //Queue::reset();
        set_update_timer();
}

/*
 * Compute the average input rate, the price and the marking prob..
 */
void REMQueue::run_updaterule()
{

        double in, in_avg, nqueued, pl, pr;

        // link price, the congestion measure

        pl = remv_.v_pl;

        // in is the number of bytes (if qib_ is true) or packets (otherwise)
        // arriving at the link (input rate) during one update time interval

        in = remv_.v_count;
       
        // in_avg is the low pss filtered input rate
        // which is in bytes if qib_ is true and in packets otherwise.

        in_avg = remv_.v_ave;
  
        in_avg *= (1.0 - remp_.p_inw);
        
        if (qib_) {
                in_avg += remp_.p_inw*in/remp_.p_pktsize; 
                nqueued = bcount_/remp_.p_pktsize; 
        }
        else {
                in_avg += remp_.p_inw*in;
                nqueued = q_ -> length();
        }


        // c measures the maximum number of packets that 
        // could be sent during one update interval.

        double c  = remp_.p_updtime*remp_.p_ptc;

        pl = pl + remp_.p_gamma*( in_avg + 0.1*(nqueued-remp_.p_bo) - c );

        if ( pl < 0.0) {
            pl = 0.0;
        }

        double pow1 = pow (remp_.p_phi, -pl);
        pr = 1.0-pow1;


        remv_.v_count = 0.0;
        remv_.v_ave = in_avg;
        remv_.v_pl = pl;
        remv_.v_prob = pr;
}


/*
 * Return the next packet in the queue for transmission.
 */
Packet* REMQueue::deque() 
{
        Packet *p = q_->deque();
        hdr_cmn* ch; 
        if (p != 0) {
                ch = hdr_cmn::access(p);
                bcount_ -= ch->size();
        }
        if (markpkts_) {
                double u = Random::uniform();
                if (p!=0) {
                        double pro = remv_.v_prob;
                        if (qib_) {
                                pro = remv_.v_prob*ch->size()/remp_.p_pktsize; 
                        }
                if ( u <= pro ) {
                                hdr_flags* hf = hdr_flags::access(p);
                                if(hf->ect() == 1) { 
                                        hf->ce() = 1; 
                                        pmark_++;
                                }
                        }
                }
        }
        double qlen = qib_ ? bcount_ : q_->length();
        curq_ = (int) qlen;
        return (p);
}

/*
 * Receive a new packet arriving at the queue.
 * The packet is dropped if the maximum queue size is exceeded.
 */

void REMQueue::enque(Packet* pkt)
{
        hdr_cmn* ch = hdr_cmn::access(pkt);
        double qlen; 

        if (qib_) {
                remv_.v_count += ch->size();
        }
        else {
                ++remv_.v_count;
        }

        double qlim = qib_ ? (qlim_*remp_.p_pktsize) : qlim_ ;

        q_ -> enque(pkt);
        bcount_ += ch->size();

        qlen = qib_ ? bcount_ : q_->length();

        if (qlen >= qlim) {
                q_->remove(pkt);
                bcount_ -= ch->size();
                drop(pkt);
        }
        else  {
                if (!markpkts_) {
                        double u = Random::uniform(); 
                        double pro = remv_.v_prob;
                        if (qib_) {
                                pro = remv_.v_prob*ch->size()/remp_.p_pktsize; 
                        }
                        if ( u <= pro ) {
                                q_->remove(pkt);
                                bcount_ -= ch->size();
                                drop(pkt);
                        }                   
                }
        }
        qlen = qib_ ? bcount_ : q_->length();
        curq_ = (int) qlen;
}


int REMQueue::command(int argc, const char*const* argv)
{

        Tcl& tcl = Tcl::instance();
        if (argc == 2) {
                if (strcmp(argv[1], "reset") == 0) {
                        reset();
                        return (TCL_OK);
                }
        } else if (argc == 3) {
                // attach a file for variable tracing
                if (strcmp(argv[1], "attach") == 0) {
                        int mode;
                        const char* id = argv[2];
                        tchan_ = Tcl_GetChannel(tcl.interp(), (char*)id, &mode);
                        if (tchan_ == 0) {
                                tcl.resultf("REM: trace: can't attach %s for writing", id);
                                return (TCL_ERROR);
                        }
                        return (TCL_OK);
                }
                // tell REM about link stats
                if (strcmp(argv[1], "link") == 0) {
                        LinkDelay* del = (LinkDelay*)TclObject::lookup(argv[2]);
                        if (del == 0) {
                                tcl.resultf("REM: no LinkDelay object %s",
                                        argv[2]);
                                return(TCL_ERROR);
                        }
                        // set ptc now
                        link_ = del;
                        remp_.p_ptc = link_->bandwidth() /
                                (8. * remp_.p_pktsize);

                        return (TCL_OK);
                }
                if (!strcmp(argv[1], "packetqueue-attach")) {
                        delete q_;
                        if (!(q_ = (PacketQueue*) TclObject::lookup(argv[2])))
                                return (TCL_ERROR);
                        else {
                                pq_ = q_;
                                return (TCL_OK);
                        }
                }
        }
        return (Queue::command(argc, argv));
}

/*
 * Routine called by TracedVar facility when variables change values.
 * Currently used to trace values of avg queue size, drop probability,
 * and the instantaneous queue size seen by arriving packets.
 * Note that the tracing of each var must be enabled in tcl to work.
 */

void
REMQueue::trace(TracedVar* v)
{
        char wrk[500], *p;

        if (((p = strstr(v->name(), "ave")) == NULL) &&
            ((p = strstr(v->name(), "prob")) == NULL) &&
            ((p = strstr(v->name(), "curq")) == NULL)) {
                fprintf(stderr, "REM:unknown trace var %s\n",
                        v->name());
                return;
        }

        if (tchan_) {
                int n;
                double t = Scheduler::instance().clock();
                if (*p == 'c') {
                        sprintf(wrk, "Q %g %d", t, int(*((TracedInt*) v)));
                } else {
                        sprintf(wrk, "%c %g %g", *p, t,
                                double(*((TracedDouble*) v)));
                }
                n = strlen(wrk);
                wrk[n] = '\n'; 
                wrk[n+1] = 0;
                (void)Tcl_Write(tchan_, wrk, n+1);
        }
        return; 
}

/* for debugging help */
void REMQueue::print_remp()
{
        printf("=========\n");
}

void REMQueue::print_remv()
{
        printf("=========\n");
}

---