fq.cc

Go to the documentation of this file.

/* -*-  Mode:C++; c-basic-offset:8; tab-width:8; indent-tabs-mode:t -*- */
/*
 * Copyright (c) 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 MASH Research
 *  Group at the University of California Berkeley.
 * 4. Neither the name of the University nor of the Research Group 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: /nfs/jade/vint/CVSROOT/ns-2/queue/fq.cc,v 1.12 2005/08/22 05:08:34 tomh Exp $ (ANS)";
#endif

#include "config.h"
#include <stdlib.h>
#include <float.h>
#include "queue.h"

/*XXX*/
#define MAXFLOW 32

class FQ : public Queue {
public: 
    FQ();
    virtual int command(int argc, const char*const* argv);
    Packet *deque(void);
    void enque(Packet *pkt);
    void recv(Packet* p, Handler* h);
protected:
    int update();
    struct flowState {
        Queue* q_;
        Packet* hol_;   /* head-of-line packet for each flow */
        double finishTime_; /* FQ finish time for hol packet */
        double delta_;
        Handler* handler_;
    } fs_[MAXFLOW];
    inline double finish(const flowState& fs, int nactive)
    {
        return (fs.finishTime_ + fs.delta_ * nactive);
    }
    int maxflow_;
    double secsPerByte_;
};

static class FQClass : public TclClass {
public:
    FQClass() : TclClass("Queue/FQ") {}
    TclObject* create(int, const char*const*) {
        return (new FQ);
    }
} class_fq;

FQ::FQ()
{
    for (int i = 0; i < MAXFLOW; ++i) {
        fs_[i].q_ = 0;
        fs_[i].hol_ = 0;
        fs_[i].finishTime_ = 0.;
    }
    maxflow_ = -1;
    secsPerByte_ = 0.;
    bind("secsPerByte_", &secsPerByte_);
}

int FQ::command(int argc, const char*const* argv)
{
    if (argc == 4) {
        if (strcmp(argv[1], "install") == 0) {
            int flowID = atoi(argv[2]);
            fs_[flowID].q_ = (Queue*)TclObject::lookup(argv[3]);
            if (flowID > maxflow_)
                maxflow_ = flowID;
            /*XXX*/
            if (flowID >= MAXFLOW)
                abort();
            return (TCL_OK);
        }
    }
    return (Queue::command(argc, argv));
}

/*XXX this is quite inefficient.*/
int FQ::update()
{
    int nactive = 0;
    for (int i = 0; i <= maxflow_; ++i) {
        Queue* q = fs_[i].q_;
        if (q != 0) {
            if (fs_[i].hol_ == 0) {
                Packet* p = q->deque();
                if (p != 0) {
                    fs_[i].hol_ = p;
                    ++nactive;
                }
            } else
                ++nactive;
        }
    }
    return (nactive);
}

Packet* FQ::deque()

{
    int nactive = update();
    int target = -1;
    double best = DBL_MAX;
    for (int i = 0; i <= maxflow_; ++i) {
        if (fs_[i].hol_ != 0) {
            if (target < 0) { 
                target = i;
                best = finish(fs_[i], nactive);
            } else {
                double F = finish(fs_[i], nactive);
                if (F < best) {
                    target = i;
                    best = F;
                }
            }
        }
    }
    if (target >= 0) {
        Packet* p = fs_[target].hol_;
        fs_[target].hol_ = 0;
        fs_[target].finishTime_ = best;
        /* let this upstream queue resume */
        Handler* h = fs_[target].handler_;
        /*XXX null event okay because queue doesn't use it*/
        h->handle(0);
        return (p);
    }
    return (0);
}

/*
 * Called when one of our queues is unblocked by us in FQ::deque
 * (or gets its first packet).
 */
void FQ::recv(Packet* p, Handler* handler)
{
    hdr_ip* h = hdr_ip::access(p);
    int flowid = h->flowid();
    /* shouldn't be called when head-of-line is pending */
    if (flowid >= MAXFLOW || fs_[flowid].hol_ != 0)
        abort();

    /*
     * Put this packet at the head-of-line for its queue
     * and set up scheduling state according to the
     * standard fair-queueing "finish time" equation.
     */
    fs_[flowid].hol_ = p;
    double now = Scheduler::instance().clock();
    if (now > fs_[flowid].finishTime_)
        fs_[flowid].finishTime_ = now;
    fs_[flowid].handler_ = handler;
    int size = hdr_cmn::access(p)->size();
    fs_[flowid].delta_ = size * secsPerByte_;

    if (!blocked_) {
        /*
         * We're not blocked.  Get a packet and send it on.
         * We perform an extra check because the queue
         * might drop the packet even if it was
         * previously empty!  (e.g., RED can do this.)
         */
        p = deque();
        if (p != 0) {
            blocked_ = 1;
            target_->recv(p, &qh_);
        }
    }
}

void FQ::enque(Packet*)
{
    /* should never be called because we override recv */
    abort();
}

---