QuManager.cpp

/*
Implementation Notes
We maintain two heaps defined on the links. The active heap
contains links for which packets are currently queued. The
vactive heap contains links that are "virtually active", meaning
that they recently sent their last packet, but they are not
yet allowed to send their next, given the limit on their bit
rate and packet rate. If a packet arrives for a virtually active
link, it is moved to the active heap with a deadline inherited
from the vactive heap.

It's important that links be moved off the vactive heap when
they become eligible to send new packets. This is done in the
nextReady routine, which is expected to be called frequently
(e.g. once on each iteration of the router's main loop).

In addition to the active and vactive heaps, there is a HeapSet
data structure that contains a heap for each link. These heaps
contain queues and the key of a queue in its heap, is the
virtual finish time of the queue in a Self-Clocked Fair Queueing
packet scheduler.
*/

#include "QuManager.h"

namespace forest {


// Constructor for QuManager, allocates space and initializes everything.
QuManager::QuManager(int nL1, int nP1, int nQ1, int maxppl1,
                                     PacketStore *ps1, StatsModule *sm1)
                                    : nL(nL1), nP(nP1), nQ(nQ1),
                                      maxppl(maxppl1), ps(ps1), sm(sm1) {
                queues = new ListSet(nP,nQ);
                active = new Dheap<uint64_t>(nL);  
                vactive = new Dheap<uint64_t>(nL);
                quInfo = new QuInfo[nQ+1];
                lnkInfo = new LinkInfo[nL+1]; 
                hset = new DheapSet<uint64_t>(nQ,nL);

                RateSpec rs(Forest::MINBITRATE,Forest::MINBITRATE,
                                    Forest::MINPKTRATE,Forest::MINPKTRATE);
                for (int lnk = 1; lnk <= nL; lnk++) {
                                lnkInfo[lnk].vt = 0; setLinkRates(lnk, rs);
                }

                // build free list of queues using lnk field
                for (int qid = 1; qid < nQ; qid++) {
                                quInfo[qid].lnk = qid+1;
                                quInfo[qid].pktLim = -1; // used to identify unassigned queues
                                quInfo[qid].vft = 0;
                }
                quInfo[nQ].lnk = 0; free = 1;
                qCnt = 0;
}
                                
QuManager::~QuManager() {
                delete queues; delete active; delete vactive;
                delete [] quInfo; delete [] lnkInfo; delete hset;
}

int QuManager::allocQ(int lnk) {
                unique_lock lck(mtx);
                if (free == 0) return 0;
                int qid = free; free = quInfo[qid].lnk;
                quInfo[qid].lnk = lnk;
                quInfo[qid].pktLim = 0; // non-negative value for assigned queues
                qCnt++;
                return qid;
}

void QuManager::freeQ(int qid) {
                unique_lock lck(mtx);
                if (qid == 0) return;
                if (queues->empty(qid)) {
                                quInfo[qid].lnk = free; free = qid; qCnt--;
                } 
                quInfo[qid].pktLim = -1; // negative value for free queues
}

bool QuManager::enq(int px, int qid, uint64_t now) {
                unique_lock lck(mtx);
                int pleng = Forest::truPktLeng((ps->getPacket(px)).length);
                QuInfo& q = quInfo[qid]; int lnk = q.lnk;

                // don't queue it if too many packets for link
                // or if queue is past its limits
                if (sm->getLinkQlen(lnk) >= maxppl ||
                    sm->getQlen(qid) >= q.pktLim ||
                    sm->getQbytes(qid) + pleng > q.byteLim) {
                                return false;
                }

                if (queues->empty(qid)) {
                                // make link active if need be
                                if (!active->member(lnk)) {
                                                uint64_t d;
                                                if (vactive->member(lnk)) {
                                                                d = vactive->key(lnk);
                                                                if (now >= d) d = now;
                                                                vactive->remove(lnk);
                                                } else {
                                                                d = now;
                                                                lnkInfo[lnk].avgPktTime = lnkInfo[lnk].minDelta;
                                                }
                                                active->insert(lnk,d);
                                }
                                // set virtual finish time of queue
                                uint64_t d = q.nsPerByte; d *= pleng;
                                if (q.minDelta > d) d = q.minDelta;
                                q.vft = max(q.vft, lnkInfo[lnk].vt) + d;

                                // add queue to scheduling heap for link
                                if (!hset->insert(qid,q.vft,lnk)) {
                                                cerr << "enq attempt to insert in hset failed qid="
                                                     << qid << " lnk=" << lnk << " hset="
                                                     << hset->toString(lnk);
                                }
                } 

                // add packet to queue
                queues->addLast(px,qid);
                sm->incQlen(qid,lnk,pleng);
                return true;
}

int QuManager::deq(int& lnk, uint64_t now) {
                unique_lock lck(mtx);
                // first process virtually active links that should now be idle
                //
                int vl = vactive->findmin(); uint64_t d = vactive->key(vl);
                while (vl != 0 && now >= d) {
                                vactive->remove(vl);
                                vl = vactive->findmin(); d = vactive->key(vl);
                }
                // determine next active link that is ready to send
                if (active->empty()) return 0;
                lnk = active->findmin(); d = active->key(lnk);
                if (now < d) return 0;

                // dequeue packet and update statistics
                int qid = hset->findMin(lnk);
                pktx px = queues->removeFirst(qid);
                int pleng = Forest::truPktLeng(ps->getPacket(px).length);
                sm->decQlen(qid,lnk,pleng);

                // and update scheduling heap and virtual time of lnk
                QuInfo& q = quInfo[qid];
                lnkInfo[lnk].vt = q.vft;
                if (queues->empty(qid)) {
                                hset->deleteMin(lnk);
                                if (q.pktLim < 0) {
                                                // move queue to the free list
                                                q.lnk = free; free = qid; qCnt--;
                                }
                } else {
                                int npx = queues->first(qid);
                                Packet& np = ps->getPacket(npx);
                                int npleng = Forest::truPktLeng(np.length);
                                uint64_t d = q.nsPerByte; d *= npleng;
                                if (q.minDelta > d) d = q.minDelta;
                                q.vft += d;
                                hset->changeKeyMin(q.vft, lnk);
                }

                // update the time when lnk can send its next packet
                uint64_t t = lnkInfo[lnk].nsPerByte; t *= pleng;
                lnkInfo[lnk].avgPktTime = (t/16) + (15*(lnkInfo[lnk].avgPktTime/16));
                if (lnkInfo[lnk].avgPktTime < lnkInfo[lnk].minDelta &&
                    t < lnkInfo[lnk].minDelta)
                                t = lnkInfo[lnk].minDelta;
                t += active->key(lnk);

                if (hset->empty(lnk)) {
                                active->remove(lnk);
                                vactive->insert(lnk,t);
                } else {
                                active->changekey(lnk,t);
                }
                
                return px;
}

} // ends namespace