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

/*
 * Based on PI controller described in:
 * C. Hollot, V. Misra, D. Towsley and W. Gong. 
 * On Designing Improved Controllers for AQM Routers
 * Supporting TCP Flows, 
 * INFOCOMM 2001. 
 */

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

static class PIClass : public TclClass {
public:
    PIClass() : TclClass("Queue/PI") {}
    TclObject* create(int argc, const char*const* argv) {
        if (argc==5) 
            return (new PIQueue(argv[4]));
        else
            return (new PIQueue("Drop"));
    }
} class_pi;


PIQueue::PIQueue(const char * trace) : CalcTimer(this), link_(NULL), q_(NULL),
    qib_(0), de_drop_(NULL), EDTrace(NULL), tchan_(0), curq_(0),
    edp_(), edv_(), first_reset_(1)
{
    if (strlen(trace) >=20) {
        printf("trace type too long - allocate more space to traceType in pi.h and recompile\n");
        exit(0);
    }
    strcpy(traceType, trace);

    bind_bool("bytes_", &edp_.bytes);       // boolean: use bytes?
    bind_bool("queue_in_bytes_", &qib_);        // boolean: q in bytes?
    bind("a_", &edp_.a);        
    bind("b_", &edp_.b);       
    bind("w_", &edp_.w);          
    bind("qref_", &edp_.qref);        
    bind("mean_pktsize_", &edp_.mean_pktsize);  // avg pkt size
    bind_bool("setbit_", &edp_.setbit);     // mark instead of drop
    bind("prob_", &edv_.v_prob);            // dropping probability
    bind("curq_", &curq_);              // current queue size
    q_ = new PacketQueue();             // underlying queue
    pq_ = q_;
    reset();
}

void PIQueue::reset()
{
    //double now = Scheduler::instance().clock();
    /*
    if (qib_ && first_reset_ == 1) {
        edp_.qref = edp_.qref*edp_.mean_pktsize;
    }
    */
    edv_.count = 0;
    edv_.count_bytes = 0;
    edv_.v_prob = 0;
    edv_.qold = 0;
    curq_ = 0;
    calculate_p();
    Queue::reset();
}


void PIQueue::enque(Packet* pkt)
{
    //double now = Scheduler::instance().clock();
    hdr_cmn* ch = hdr_cmn::access(pkt);
    ++edv_.count;
    edv_.count_bytes += ch->size();

    int droptype = DTYPE_NONE;

    int qlen = qib_ ? q_->byteLength() : q_->length();
    curq_ = qlen;   // helps to trace queue during arrival, if enabled

    int qlim = qib_ ? (qlim_ * edp_.mean_pktsize) : qlim_;

    if (qlen >= qlim) {
        droptype = DTYPE_FORCED;
    }
    else {
        if (drop_early(pkt, qlen)) {
            droptype = DTYPE_UNFORCED;
        }
    }

    if (droptype == DTYPE_UNFORCED) {
        Packet *pkt_to_drop = pickPacketForECN(pkt);
        if (pkt_to_drop != pkt) {
            q_->enque(pkt);
            q_->remove(pkt_to_drop);
            pkt = pkt_to_drop; /* XXX okay because pkt is not needed anymore */
        }

        if (de_drop_ != NULL) {
            if (EDTrace != NULL) 
                ((Trace *)EDTrace)->recvOnly(pkt);
            de_drop_->recv(pkt);
        }
        else {
            drop(pkt);
        }
    } else {
        q_->enque(pkt);
        if (droptype == DTYPE_FORCED) {
            pkt = pickPacketToDrop();
            q_->remove(pkt);
            drop(pkt);
            edv_.count = 0;
            edv_.count_bytes = 0;
        }
    }
    return;
}

double PIQueue::calculate_p()
{
    //double now = Scheduler::instance().clock();
    double p;
    int qlen = qib_ ? q_->byteLength() : q_->length();
    
    if (qib_) {
        p=edp_.a*(qlen*1.0/edp_.mean_pktsize-edp_.qref)-
            edp_.b*(edv_.qold*1.0/edp_.mean_pktsize-edp_.qref)+
            edv_.v_prob;
    }
    else {
        p=edp_.a*(qlen-edp_.qref)-edp_.b*(edv_.qold-edp_.qref)+edv_.v_prob;
    }
        
    if (p < 0) p = 0;
    if (p > 1) p = 1;
    
    edv_.v_prob = p;
    edv_.qold = qlen;

    CalcTimer.resched(1.0/edp_.w);
    return p;
}

int PIQueue::drop_early(Packet* pkt, int qlen)
{
    //double now = Scheduler::instance().clock();
    hdr_cmn* ch = hdr_cmn::access(pkt);
    double p = edv_.v_prob; 

    if (edp_.bytes) {
        p = p*ch->size()/edp_.mean_pktsize;
        if (p > 1) p = 1; 
    }

    double u = Random::uniform();
    if (u <= p) {
        edv_.count = 0;
        edv_.count_bytes = 0;
        hdr_flags* hf = hdr_flags::access(pickPacketForECN(pkt));
        if (edp_.setbit && hf->ect()) {
            hf->ce() = 1;   // mark Congestion Experienced bit
            return (0); // no drop
        } else {
            return (1); // drop
        }
    }
    return (0);         // no DROP/mark
}

Packet* PIQueue::pickPacketForECN(Packet* pkt)
{
    return pkt; /* pick the packet that just arrived */
}

Packet* PIQueue::pickPacketToDrop() 
{
    int victim;
    victim = q_->length() - 1;
    return(q_->lookup(victim)); 
}

Packet* PIQueue::deque()
{
    Packet *p;
    p = q_->deque();
    curq_ = qib_ ? q_->byteLength() : q_->length(); // helps to trace queue during arrival, if enabled
    return (p);
}

int PIQueue::command(int argc, const char*const* argv)
{
    Tcl& tcl = Tcl::instance();
    if (argc == 2) {
        if (strcmp(argv[1], "reset") == 0) {
            reset();
            return (TCL_OK);
        }
        if (strcmp(argv[1], "early-drop-target") == 0) {
            if (de_drop_ != NULL)
                tcl.resultf("%s", de_drop_->name());
            return (TCL_OK);
        }
        if (strcmp(argv[1], "edrop-trace") == 0) {
            if (EDTrace != NULL) {
                tcl.resultf("%s", EDTrace->name());
            }
            else {
                tcl.resultf("0");
            }
            return (TCL_OK);
        }
        if (strcmp(argv[1], "trace-type") == 0) {
            tcl.resultf("%s", traceType);
            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("PI: trace: can't attach %s for writing", id);
                return (TCL_ERROR);
            }
            return (TCL_OK);
        }
        // tell PI about link stats
        if (strcmp(argv[1], "link") == 0) {
            LinkDelay* del = (LinkDelay*)TclObject::lookup(argv[2]);
            if (del == 0) {
                tcl.resultf("PI: no LinkDelay object %s", argv[2]);
                return(TCL_ERROR);
            }
            link_ = del;
            return (TCL_OK);
        }
        if (strcmp(argv[1], "early-drop-target") == 0) {
            NsObject* p = (NsObject*)TclObject::lookup(argv[2]);
            if (p == 0) {
                tcl.resultf("no object %s", argv[2]);
                return (TCL_ERROR);
            }
            de_drop_ = p;
            return (TCL_OK);
        }
        if (strcmp(argv[1], "edrop-trace") == 0) {
            NsObject * t  = (NsObject *)TclObject::lookup(argv[2]);
            if (t == 0) {
                tcl.resultf("no object %s", argv[2]);
                return (TCL_ERROR);
            }
            EDTrace = t;
            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));
}

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

    if (((p = strstr(v->name(), "prob")) == NULL) &&
        ((p = strstr(v->name(), "curq")) == NULL)) {
        fprintf(stderr, "PI:unknown trace var %s\n", v->name());
        return;
    }
    if (tchan_) {
        int n;
        double t = Scheduler::instance().clock();
        // XXX: be compatible with nsv1 PI trace entries
        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; 
}

void PICalcTimer::expire(Event *)
{
    a_->calculate_p();
}

---