jobs.cc

Go to the documentation of this file.

/*
 * Copyright (c) 2000-2002, by the Rector and Board of Visitors of the 
 * University of Virginia.
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, 
 * with or without modification, are permitted provided 
 * that the following conditions are met:
 *
 * Redistributions of source code must retain the above 
 * copyright notice, this list of conditions and the following 
 * disclaimer. 
 *
 * 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. 
 *
 * Neither the name of the University of Virginia nor the names 
 * of its contributors may be used to endorse or promote products 
 * derived from this software without specific prior written 
 * permission. 
 *
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS 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.
 */
/*
 *                                                                     
 * JoBS - ns-2 prototype implementation                                
 *                                                                     
 * Author: Nicolas Christin <nicolas@cs.virginia.edu>, 2000-2002       
 *                                                                    
 * JoBS algorithms originally devised and proposed by                 
 * Nicolas Christin and Jorg Liebeherr                                 
 * Grateful acknowledgments to Tarek Abdelzaher for his help and       
 * comments.                                                           
 *                                                                     
 * $Id: jobs.cc,v 1.2 2003/02/04 20:45:55 xuanc Exp $                   
 *                                                                    
 */

#include "jobs.h"

static class JoBSClass : public TclClass {
public:
  JoBSClass() : TclClass("Queue/JoBS") {}
  TclObject* create(int, const char*const*) {
    return (new JoBS);
  }
} class_jobs;

JoBS::JoBS() : link_(NULL) {
        for (int i=1; i<=NO_CLASSES; i++) 
                cls_[i] = new PacketQueue;

        bind_bool("drop_front_", &drop_front_);
        bind_bool("trace_hop_", &trace_hop_);
        bind("mean_pkt_size_", &mean_pkt_size_);  // avg pkt size
        bind("adc_resolution_type_", &adc_resolution_type_);
        bind_bool("shared_buffer_", &shared_buffer_);
        total_backlog_Pkts_     = 0;
        total_backlog_Bits_     = 0;
        pkt_count_ = 0;
        idle_ = 1;
        ABS_present_ = FALSE;
        monitoring_window_ = 0;
        last_arrival_ = 0;
        last_monitor_update_ = 0;
        sliding_arv_pkts_=0;
        util_ = 0;

        for (int i=1; i<=NO_CLASSES; i++) {
                RDC_[i] = (double)i; 
                RLC_[i] = (double)i;
                ADC_[i] = INFINITY;
                ALC_[i] = INFINITY;
                sliding_serviced_pkts_[i] = 0;
                sliding_serviced_bits_[i] = 0;
                sliding_arv_pkts_c[i] = 0;
                sliding_class_delay_[i] = 0;
                sliding_class_service_rate_[i] = 0;
                last_xmit_[i] = 0;
                
                avg_elapsed_[i] = 0.0;
                excess_drops_[i] = 0.0;
                Rout_last_up_[i] = 0.0;
                min_drop_[i] = 0.0;
                max_drop_[i] = 1.0;
                error_[i] = 0.0;
                min_rate_[i] = 0.0;
                backlog_Pkts_[i] = 0;
                backlog_Bits_[i] = 0;
                service_rate_[i] = 0;
                current_loss_[i] = 0;
                Rout_[i] = 0;
                Rin_[i] = 0;
                Rout_th_[i] = 0;
                last_rate_update_[i] = 0;
        }  
}

int JoBS::command(int argc, const char*const* argv) {
        Tcl& tcl = Tcl::instance();
        double tmp[NO_CLASSES+1];

        if (argc >= NO_CLASSES+2) { /* input RDCs/RLCs/ADCs/ALCs */
                if (strcmp(argv[1], "init-rdcs") == 0) {
                        RDC_[0] = -1;
                        for (int i=1; i<=NO_CLASSES; i++) {
                                RDC_[i] = atof(argv[i+1]);
                                if (RDC_[i] == -1)
                                        concerned_RDC_[i] = FALSE;
                                else
                                  concerned_RDC_[i] = TRUE;
                        }
                        for (int i=1; i<=NO_CLASSES;i++) {
                                tmp[i] = 1.0;
                                for (int j = 1; j <= i-1; j++) 
                                  if (concerned_RDC_[j]) tmp[i] *= RDC_[j];
                        }

                        for (int i=1; i<=NO_CLASSES; i++) {
                                prod_others_[i] = 1.0;
                                for (int j = 1; j <= NO_CLASSES; j++) 
                                        if ((j != i)&&(concerned_RDC_[j]))
                                          prod_others_[i] *= tmp[j];
                        }
                        if (argc == NO_CLASSES+2) {
                                fprintf(stdout, "\nConfigured RDC, with:\n");
                                for (int i=1; i<=NO_CLASSES; i++) {
                                        fprintf(stdout, "\tClass %d: ",i);
                                        if (concerned_RDC_[i]) 
                                                fprintf(stdout, "\t%f\t(%f)\n", (double)RDC_[i], (double) prod_others_[i]);
                                        else 
                                                fprintf(stdout, "\tNot concerned\n");
                                }
                        }
                        return (TCL_OK);
                }

                if (strcmp(argv[1], "init-rlcs") == 0) {
                        RLC_[0] = -1;
                        for (int i=1; i<=NO_CLASSES; i++) {
                                RLC_[i] = atof(argv[i+1]);
                                if (RLC_[i] == -1)
                                        concerned_RLC_[i] = FALSE;
                                else
                                        concerned_RLC_[i] = TRUE;
                        }

                        for (int i=1; i<=NO_CLASSES;i++) {
                                tmp[i] = 1.0;
                                for (int j = 1; j <= i-1; j++) 
                                        if (concerned_RLC_[j]) 
                                                tmp[i] *= RLC_[j];
                        }

                        for (int i=1; i<=NO_CLASSES; i++) {
                                loss_prod_others_[i] = 1.0;
                                for (int j = 1; j <= NO_CLASSES; j++) 
                                        if ((j != i)&&(concerned_RLC_[j]))
                                                loss_prod_others_[i] *= tmp[j];
                        }
                        if (argc == NO_CLASSES+2) {
                                fprintf(stdout, "\nConfigured RLC, with:\n");
                                for (int i=1; i<=NO_CLASSES; i++) {
                                        fprintf(stdout, "\tClass %d: ",i);
                                        if (concerned_RLC_[i]) 
                                                fprintf(stdout, "\t%f\t(%f)\n", (double)RLC_[i], (double)loss_prod_others_[i]);
                                        else 
                                                fprintf(stdout, "\tNot concerned\n");
                                }
                        }
                        
                        return (TCL_OK);
                }
                if (strcmp(argv[1], "init-adcs") == 0) {
                        ADC_[0] = -1;
                        for (int i=1; i<=NO_CLASSES; i++) {
                                ADC_[i] = atof(argv[i+1]);
                                if (ADC_[i] == -1) {
                                        concerned_ADC_[i] = FALSE;
                                        ADC_[i] = INFINITY;
                                } else {
                                        concerned_ADC_[i] = TRUE;
                                        ABS_present_ = TRUE;
                                }
                        }
                        if (argc == NO_CLASSES+2) {
                                fprintf(stdout, "\nConfigured ADC, with:\n");
                                for (int i=1; i<=NO_CLASSES; i++) {
                                        fprintf(stdout, "\tClass %d: ", i);
                                        if (concerned_ADC_[i]) 
                                                fprintf(stdout, "\t%f secs\n", (double)ADC_[i]);
                                        else 
                                                fprintf(stdout, "\tNot concerned\n");
                                }
                        }

                        return (TCL_OK);
                }
                if (strcmp(argv[1], "init-alcs") == 0) {
                        ALC_[0] = -1;
                        for (int i=1; i<=NO_CLASSES; i++) {
                                ALC_[i] = atof(argv[i+1]);
                                if (ALC_[i] == -1) {
                                        concerned_ALC_[i] = FALSE;
                                        ALC_[i] = INFINITY;
                                } else
                                        concerned_ALC_[i] = TRUE;
                        }
                        if (argc == NO_CLASSES+2) {
                                fprintf(stdout, "\nConfigured ALC, with:\n");
                                for (int i=1; i<=NO_CLASSES; i++) {
                                        fprintf(stdout, "\tClass %d: ",i);
                                        if (concerned_ALC_[i])  
                                                fprintf(stdout, "\t%f\n", (double)ALC_[i]);
                                        else 
                                                fprintf(stdout, "\tNot concerned\n");   
                                }
                        }
                        return (TCL_OK);
                }
                if (strcmp(argv[1], "init-arcs") == 0) {
                        ARC_[0] = -1;
                        for (int i=1; i<=NO_CLASSES; i++) {
                                ARC_[i] = atof(argv[i+1]);
                                if (ARC_[i] == -1) {
                                        concerned_ARC_[i] = FALSE;
                                        ARC_[i] = 0;
                                } else {
                                        concerned_ARC_[i] = TRUE;
                                        ABS_present_ = TRUE;
                                }
                        }
                        if (argc == NO_CLASSES+2) {
                                fprintf(stdout, "\nConfigured ARC, with:\n");
                                for (int i=1; i<=NO_CLASSES; i++) {
                                        fprintf(stdout, "\tClass %d: ",i);
                                        if (concerned_ARC_[i])  
                                                fprintf(stdout, "\t%f\n", (double)ARC_[i]);
                                        else 
                                                fprintf(stdout, "\tNot concerned\n");   
                                }
                        }
                        return (TCL_OK);
                }
        } else if (argc == 3) {
                if (strcmp(argv[1], "link") == 0) {
                        LinkDelay* del = (LinkDelay*)TclObject::lookup(argv[2]);
                        if (del == 0) {
                                tcl.resultf("JoBS: no LinkDelay object %s",
                                            argv[2]);
                                return(TCL_ERROR);
                        }
                        link_ = del;
                        for (int i=1; i <= NO_CLASSES; i++)
                                service_rate_[i] = 0;
                        return (TCL_OK);
                }
                if (strcmp(argv[1], "sampling-period") == 0) {
                        sampling_period_ = atoi(argv[2]);
                        if (sampling_period_ < 0) {
                                fprintf(stderr, "JoBS: sampling period must be positive!!\n");
                                abort();
                                return (TCL_ERROR); // __NOT REACHED__
                        } else 
                                return (TCL_OK);      
                }
                if (strcmp(argv[1], "id") == 0) {
                        link_id_ = (int)atof(argv[2]);
                        return (TCL_OK);
                }
                if (strcmp(argv[1], "trace-file") == 0) {
                        file_name_ = new(char[500]);
                        strcpy(file_name_, argv[2]);
                        if (strcmp(file_name_, "null")) {
                                trace_hop_ = true;
                        } else {
                                trace_hop_ = false;
                        }
                        return (TCL_OK);
                }
        } else if (argc == 2) {
                if (strcmp(argv[1], "initialize") == 0) {
                        double myMaxPi=0;
                        for (int i = 1; i <= NO_CLASSES; i++) 
                                if (prod_others_[i] > myMaxPi) 
                                        myMaxPi = prod_others_[i];

                        Kp_static_ = -2/(double)(myMaxPi*mean_pkt_size_*sampling_period_);

      // Open files
                        if (trace_hop_) {
                                if ((hop_trace_ = fopen(file_name_, "w"))==NULL) {
                                        fprintf(stderr, "Problem with opening the per-hop trace file: %s\n", file_name_);
                                        abort();          
                                }
                        }    
                        return (TCL_OK);
                }
                if (strcmp(argv[1], "copyright-info") == 0) {
                        fprintf(stdout, "\n----------------------------------------------------------\n\n");
                        fprintf(stdout, "JoBS scheduler/dropper [prototype ns-2 implementation]\n");
                        fprintf(stdout, "Version 1.0 (CVS Revision: $Id: jobs.cc,v 1.2 2003/02/04 20:45:55 xuanc Exp $)\n\n");
                        fprintf(stdout, "ns-2 implementation by Nicolas Christin <nicolas@cs.virginia.edu>\n");
                        fprintf(stdout, "JoBS algorithms proposed by Nicolas Christin and Jorg Liebeherr.\n");
                        fprintf(stdout, "Grateful acknowledgments to Tarek Abdelzaher for his help and comments.\n");
                        fprintf(stdout, "Visit http://qosbox.cs.virginia.edu for more\n");
                        fprintf(stdout, "information.\n\n");
                        fprintf(stdout, "Copyright (c) 2000-2002 by the Rector and Board of Visitors of the\n");
                        fprintf(stdout, "University of Virginia.\n");
                        fprintf(stdout, "All Rights Reserved.\n");
                        fprintf(stdout, "----------------------------------------------------------\n\n");
                        return (TCL_OK);
                }
        }
        return (Queue::command(argc, argv));
}

// *******************************************************************
// JoBS: Simplified Packetization of the Fluid Flow Model.
// *******************************************************************

Packet* JoBS::deque() { // Lower classes are better. 
        double  cur_time  = Scheduler::instance().clock(); 
        double  error;
        double  maxError;
        int     svc_class = 0;
  
        error = 0;

        // Fast translation of service rates into packet forwarding decisions

        maxError = -INFINITY;
        for (int i=1; i<=NO_CLASSES; i++) {
                if (cls_[i]->head()) {
                        error = (double)Rout_th_[i] - Rout_[i];
                        if (error > maxError) {
                                maxError = error;
                                svc_class = i;
                        }
                }
        }

        if (svc_class == 0) {
                idle_ = 1;
                if (&Scheduler::instance() != NULL)
                        idletime_ = cur_time;
                else
                        idletime_ = 0.0;
                return NULL; /* Idle system */
        } else {
                idle_ = 0;
                Packet* p = cls_[svc_class]->deque();
                hdr_cmn* cm_h = hdr_cmn::access(p);
    
                total_backlog_Pkts_--;
                total_backlog_Bits_ -= 8*cm_h->size();
                backlog_Pkts_[svc_class]--;
                backlog_Bits_[svc_class] -= 8*cm_h->size();
                Rout_[svc_class] += 8*cm_h->size();
                Rout_last_up_[svc_class] = cur_time;
                
                sliding_serviced_pkts_[svc_class] ++;
                sliding_serviced_bits_[svc_class] += 8*cm_h->size();
                sliding_class_delay_[svc_class] 
                  = ((sliding_serviced_pkts_[svc_class]-1)*(sliding_class_delay_[svc_class])
                     +(cur_time-cm_h->ts_))/(sliding_serviced_pkts_[svc_class]);
                last_xmit_[svc_class] = cur_time+(8.*cm_h->size()/(double)link_->bandwidth());
                return(p);
        }
}

// *******************************************************************
// JoBS: Enqueue packet 
// *******************************************************************

void JoBS::enque(Packet* pkt) {
        double* DeltaR;
        int i;
        hdr_ip*  ip_h = hdr_ip::access(pkt);
        hdr_cmn* cm_h = hdr_cmn::access(pkt);
        
        int prio = ip_h->prio_;
        if ((prio < 1) || (prio > NO_CLASSES)) {
                printf("Bad priority value\n");
                abort();
        }
  
        double cur_time = Scheduler::instance().clock(); 
        cm_h->ts_ = cur_time; // timestamp the packet
        cls_[prio]->enque(pkt);
        
        monitoring_window_ -= cur_time-last_monitor_update_;
        last_monitor_update_ = cur_time;
        if (monitoring_window_ <= 0) {
                updateStats(pkt, RESET_STATS);
                monitoring_window_ = MON_WINDOW_SIZE;
        } else {
                updateStats(pkt, UPDATE_STATS);
        }
        
        // Reset arrival, input, and service curves if the scheduler is 
        // not busy

        if (idle_) {
                for (i=1; i<= NO_CLASSES; i++) {
                  Arrival_[i]=0.0;
                  Rin_[i]=0.0;
                  Rout_[i]=0.0;
                  Rout_th_[i]=0.0;
                  last_rate_update_[i] = 0;
                  Rout_last_up_[i] = cur_time;
                  idle_ = 0;
                }
        }
        
        arvAccounting(pkt);
        
        /* Is the buffer full? */  
        if (!shared_buffer_ && backlog_Pkts_[prio] > qlim_/NO_CLASSES) {
                /* separate buffers: no guarantees on packet drops 
                 * can be offered
                 * thus we drop the incoming packet
                 */
                if (drop_front_)
                        dropFront(prio, WITH_UPDATE);
                else
                        dropTail(prio, WITH_UPDATE);    
        } else {
          /* shared buffer */
                if (total_backlog_Pkts_ > qlim_) {
                        if (!concerned_RLC_[prio]) {
                                if (!concerned_ALC_[prio]) {
                                        // No ALC, no RLC on that class. Drop the incoming packet.
                                        if (drop_front_)
                                                dropFront(prio, WITH_UPDATE);
                                        else
                                                dropTail(prio, WITH_UPDATE);
                                } else {
                                        // No RLC on that class. Drop the incoming packet if you can...
                                        if (current_loss_[prio]+(double)8*cm_h -> size()/(double)Arrival_[prio] <= ALC_[prio]) {
                                                if (drop_front_)
                                                        dropFront(prio, WITH_UPDATE);
                                                else        
                                                        dropTail(prio, WITH_UPDATE);
                                        } else {
                                                // If it doesn't work, pick another class
                                                if (drop_front_)
                                                        dropFront(pickDroppedRLC(RESOLVE_OVERFLOW), WITH_UPDATE);
                                                else        
                                                        dropTail(pickDroppedRLC(RESOLVE_OVERFLOW), WITH_UPDATE);
                                        }
                                }
                        } else {
                                // RLC on that class (w/ or w/o ALC), pick a class according to the RLC
                          if (drop_front_)
                                dropFront(pickDroppedRLC(RESOLVE_OVERFLOW), WITH_UPDATE);
                          else      
                                dropTail(pickDroppedRLC(RESOLVE_OVERFLOW), WITH_UPDATE);
                        }
                }
        }
        pkt_count_ ++;
        enforceWC(); // Change rates if some classes have entered/left the system
        // since the last update

        if ((ABS_present_)&&(!minRatesNeeded(ip_h -> prio()))) {
                DeltaR = assignRateDropsADC();   

                if (DeltaR != NULL) {
                        for (i = 1; i <= NO_CLASSES; i++) 
                                service_rate_[i] += DeltaR[i];
                        delete []DeltaR; 
                }

                DeltaR = adjustRatesRDC();
                
                if (DeltaR) {
                        for (i = 1; i <= NO_CLASSES; i++) 
                                service_rate_[i] += DeltaR[i];
                        delete []DeltaR;   
                }

                pkt_count_ = 0;

        } else if (pkt_count_ >= sampling_period_) {
                /* Is it time for a new evaluation of the system? */
                DeltaR = adjustRatesRDC();
                if (DeltaR != NULL) {
                        for (i = 1; i <= NO_CLASSES; i++)
                                service_rate_[i] += DeltaR[i];
                        delete []DeltaR;
                } 
                pkt_count_ = 0;
        }
        return;
}

// *******************************************************************
// Auxiliary functions (helpers) follow
// *******************************************************************

// 1) Scheduling Primitives

// *******************************************************************
// JoBS: Enforce Work-Conserving Property
// *******************************************************************

int JoBS::enforceWC() {
        int i;
        int activeClasses;
        int updated;
        
        updated = FALSE;
        activeClasses = 0;
        
        for (i = 1; i <= NO_CLASSES; i++) {
                if (cls_[i]->head()) 
                        activeClasses++;
                if ((cls_[i] -> head() && service_rate_[i] <= PRECISION_ERROR)
                    ||(cls_[i] -> head() == NULL && service_rate_[i] > 0)) 
                  updated = TRUE;
        }

        if (updated) {
                for (i = 1; i <= NO_CLASSES; i++) {
                        if (cls_[i]->head() == NULL) {
                                service_rate_[i] = 0;
                        } else {
                                if (activeClasses > 0)
                                        service_rate_[i] = link_->bandwidth()/(double)activeClasses;
                                else 
                                        service_rate_[i] = 0 ;
                        }
                }
        }
        
        return (updated);
}

// *******************************************************************
// JoBS: Adjusts the rates for meeting the RDCs
// *******************************************************************

double* JoBS::adjustRatesRDC() {
        int i, j;
        int RDC_Classes, activeClasses;
        double* result;
        double credit, available, lower_bound, upper_bound;
        double bk;
        double cur_time;
        
        cur_time = Scheduler::instance().clock(); 
  
        activeClasses = 0;
        RDC_Classes = 0;

        upper_bound = link_ -> bandwidth();

        for (i = 1; i <= NO_CLASSES; i++)
                if (cls_[i]->head() != NULL) {
                        activeClasses++;
                        if (concerned_RDC_[i]) 
                                RDC_Classes++;
                        else 
                                upper_bound -= service_rate_[i];
                }

        result = new double[NO_CLASSES+1];

        if (result == NULL) 
                return NULL;

        for (i = 0; i <= NO_CLASSES; i++) 
                result[i] = 0;

        if (upper_bound < PRECISION_ERROR || activeClasses == 0) return result;
        
        credit = 0;
        lower_bound = 0;
        
        updateError();
        min_share_ = 1.0;
        bk = 0;
        
        for (i = 1; i <= NO_CLASSES; i++) 
                if (concerned_RDC_[i])
                        bk += Rin_[i];

        for (i = 1; i <= NO_CLASSES; i++) 
                if ((double)Rin_[i]/(double)bk < min_share_)
                        min_share_ = (double)Rin_[i]/(double)bk;
  
        /*
         * note that the formula for Kp is slightly different 
         * from the formula derived in CS-2001-21. 
         * the formula used here provides better results 
         * at the expense of more complicated computations.
         */
        
        Kp_dynamic_ = Kp_static_*pow(upper_bound, 2.)*min_share_*util_*max(util_, 1.0);

        credit = 0;
        for (i = 1; i <= NO_CLASSES; i++) {
                if ((cls_[i]->head() != NULL)&&(concerned_RDC_[i])) {
                        result[i] = Kp_dynamic_*(error_[i]); 
                }
        }

        // saturation 

        for (i = 1; i <= NO_CLASSES; i++) 
                if (cls_[i]->head() != NULL) {
                        if (concerned_RDC_[i]) {
                                lower_bound += max(0, min_rate_[i]);
                        } 
                }

        for (i = 1; i <= NO_CLASSES; i++) {
                if ((concerned_RDC_[i])&&(result[i] + service_rate_[i] > upper_bound)) {
                        for (j = 0; j <= NO_CLASSES; j++) {
                                if (concerned_RDC_[j]) {
                                        if (j == i) 
                                                result[j] = (upper_bound-service_rate_[j])  
                                                    + min_rate_[j] - lower_bound;
                                        else
                                                result[j] = -service_rate_[j]+min_rate_[j];
                                }
                        }
                        return result;
                }
                if (concerned_RDC_[i] && result[i] + service_rate_[i] < min_rate_[i]) {
                        credit += service_rate_[i]+result[i]-min_rate_[i]; 
                        // "credit" is in fact a negative number
                        result[i] = -service_rate_[i]+min_rate_[i];
                }
        }

        for (i = NO_CLASSES; (i > 0)&&(credit < 0); i--) {
                if ((cls_[i]->head() != NULL)&&(concerned_RDC_[i])) {
                        available = result[i] + service_rate_[i]-min_rate_[i];
                        if (available >= -credit) {
                                result[i] += credit;
                                credit = 0;
                        } else {
                                result[i] -= available;
                                credit += available;
                        }      
                }
        }
        return result;
}

// *******************************************************************
// JoBS: Assigns the rates (and possibly drops some traffic) 
// needed for meeting the ADCs
// *******************************************************************

double* JoBS::assignRateDropsADC() {
        double* x;
        //double myRatios[NO_CLASSES+1];
        double c[NO_CLASSES+1], n[NO_CLASSES];
        double k[NO_CLASSES+1], target[NO_CLASSES+1];
        double available[NO_CLASSES+1];
        double toDrop;
        int lowest, highest;
        int victim_class, keep_going;
        int i;
        Packet* p; 
        hdr_cmn* cm_h; 
        double cur_time = Scheduler::instance().clock(); 
        
        x = new double[NO_CLASSES+1];
        
        if (x == NULL) return NULL;
        
        for (i = 0;i <= NO_CLASSES; i++) 
                x[i] = 0;
        
        keep_going = TRUE;
        
        for (i = 1; i <= NO_CLASSES; i++) {
                if (cls_[i]->head() != NULL) {
                        p = cls_[i]->head();
                        cm_h = hdr_cmn::access(p);
                        n[i] = (double)service_rate_[i];
                        k[i] = (double)backlog_Bits_[i];
                        available[i] = service_rate_[i];
                        
                        if (concerned_ADC_[i]) { 
                                c[i] = (double)max((double)ADC_[i]-(cur_time-cm_h->ts_),1e-10);
                                target[i] = (double)k[i]/(double)c[i];
                                available[i] = -(target[i] - n[i]); 
                        } 
                        if (concerned_ARC_[i]) { 
                                if (n[i] - ARC_[i] < available[i])
                                        available[i] = n[i] - ARC_[i];
                        }
                } else {
                        available[i] = service_rate_[i];
                        n[i] = 0;
                        k[i] = 0;
                        c[i] = 0;
                }
        }
        
        // Step 1: Adjust rates 
        
        highest = 1;
        lowest  = NO_CLASSES;
        
        while ((highest < NO_CLASSES+1)&&(available[highest] >= 0))
                highest++; // which is the highest class that needs more service? 
        while ((lowest > 0)&&(available[lowest] <= 0))
                lowest--;  // which is the lowest class that needs less service? 
        
        
        while ((highest != NO_CLASSES+1)&&(lowest != 0)) {
                // give the excess service from lowest to highest 
                if (available[lowest]+available[highest] > 0) {
                        // Still some "credit" left 
                        // Give all that is needed by "highest" 
                        n[lowest]  -= -available[highest];
                        n[highest] += -available[highest];
                        
                        available[lowest]  -= -available[highest];
                        available[highest] = 0;
                        
                        while ((highest < NO_CLASSES+1)&&(available[highest] >= 0))
                                highest++;  // which is the highest class that needs more service? 
                        
                } else if (available[lowest]+available[highest] == 0) {
                        // No more credit left but it's fine 
                        n[lowest]  -= -available[highest];
                        n[highest] += -available[highest];
                        
                        available[highest] = 0;
                        available[lowest]  = 0;
                        
                        while ((highest < NO_CLASSES+1)&&(available[highest] >= 0))
                                highest++;  // which is the highest class that needs more service? 
                        while ((lowest > 0)&&(available[lowest] <= 0))
                                lowest--;   // which is the lowest class that needs less service? 

                } else if (available[lowest]+available[highest] < 0) {
                        // No more credit left and we need to switch to another class 
                        n[lowest]  -= available[lowest];
                        n[highest] += available[lowest];

                        available[highest] += available[lowest];
                        available[lowest]  = 0;
                        
                        while ((lowest > 0)&&(available[lowest] <= 0))
                                lowest--;  // which is the lowest class that needs less service? 
                }
        }
        
        for (i = 1; i <= NO_CLASSES; i++) {
                if (cls_[i]->head() != NULL)
                        x[i] = n[i] - (double)service_rate_[i];
                else 
                        x[i] = - (double)service_rate_[i] ;
        }
        
        // Step 2: Adjust drops 
        
        if (highest != NO_CLASSES+1) {
                // Some class still needs additional service 
                if (adc_resolution_type_ == SHARED_PAIN) {
                        // Drop from all classes
                        toDrop = 0;
                        for (i = 1; i <= NO_CLASSES; i++) 
                                if (available[i] < 0 && concerned_ADC_[i] && cls_[i]->head()) 
                                        toDrop += k[i] - c[i]*n[i];
                        
                        while ((toDrop > 0)&&(keep_going)) {
                                victim_class = pickDroppedRLC(RESOLVE_ADC);
                                if (drop_front_) 
                                        p = cls_[victim_class] -> head();
                                else
                                        p = cls_[victim_class] -> tail();
              
                                cm_h = hdr_cmn::access(p);

                                if (current_loss_[victim_class]+(double)8*cm_h -> size()/(double)Arrival_[victim_class] > ALC_[victim_class]) {
                                        keep_going = FALSE;
                                } else {
                                        toDrop -= (double)8*cm_h -> size();

                                        if (drop_front_) 
                                                dropFront(victim_class, WITH_UPDATE);
                                        else
                                                dropTail(victim_class, WITH_UPDATE);
                                }
                        }       
                } else {
                        // Drop solely from the class(es) that need(s) more service
                        for (i = 1; i <= NO_CLASSES; i++) {
                                if (available[i] < 0 && cls_[i] -> head()) {
                                        k[i] = c[i]*n[i];       

                                        while ((backlog_Bits_[i] > k[i])&&(keep_going)) {
                                                if (drop_front_) {
                                                        p = cls_[i] -> head();
                                                        cm_h = hdr_cmn::access(p);
                                                        if (current_loss_[i]+(double)8*cm_h -> size()/(double)Arrival_[i] > ALC_[i]) {
                                                                keep_going = FALSE;
                                                        } else 
                                                                dropFront(i, WITH_UPDATE);
                                                } else {
                                                        p = cls_[i] -> tail();
                                                        cm_h = hdr_cmn::access(p);
                                                        if (current_loss_[i]+(double)8*cm_h -> size()/(double)Arrival_[i] > ALC_[i]) {
                                                                keep_going = FALSE;
                                                        } else 
                                                                dropTail(i, WITH_UPDATE);
                                                }
                                        }
                                        k[i] = backlog_Bits_[i];
                                }
                        }      
                }
        } 

        for (i = 1; i <= NO_CLASSES; i++) 
                if (cls_[i]->head() && concerned_ADC_[i]) {
                        if (c[i] > 0) {
                                if (concerned_ADC_[i] && !concerned_ARC_[i]) {
                                        min_rate_[i] = (double)k[i]/(double)c[i];
                                } else 
                                        min_rate_[i] = (double)n[i];
                        } else {
                                min_rate_[i] = INFINITY;
                        }
                } else  if (cls_[i]->head() && concerned_ARC_[i]) {
                        min_rate_[i] = n[i];
                } else {
                  min_rate_[i] = 0.0;    
                }
        return (x);
}

// 1bis) Scheduling Helpers

// *******************************************************************
// JoBS: Update Error - used by the RDC feedback loop controller
// *******************************************************************

void JoBS::updateError() {
        int i;
        int activeClasses, backloggedClasses;
        double meanWeightedDelay;

        meanWeightedDelay = 0;
        activeClasses = 0 ; 
        backloggedClasses = 0;
        
        for (i = 1; i <= NO_CLASSES; i++) 
                if (cls_[i]->head() != NULL) {
                        backloggedClasses++;
                        if (concerned_RDC_[i]) {
                                meanWeightedDelay += prod_others_[i]*projDelay(i);
                                activeClasses ++;
                        }    
                }

        if (activeClasses > 0) 
                meanWeightedDelay /= (double)activeClasses;
        else if (backloggedClasses == 0) {
                fprintf(stderr, "JoBS::updateError() called but there's no backlog!\n");
                abort();
        }
        
        for (i = 1; i <= NO_CLASSES; i++) 
                if ((cls_[i]->head() != NULL)&&(concerned_RDC_[i])) {
                        error_[i] = meanWeightedDelay-prod_others_[i]*projDelay(i);
                } else {
                        error_[i] = 0.0; // either the class isn't concerned, or it's not backlogged
                        // in any case, the rate shouldn't be adjusted.
                }
        return;
}
// *******************************************************************
// JoBS: Derives the rates needed for meeting the ADC.
// Returns true if the sum of the rates needed for meeting the ADC
// is less than the link's bandwidth, false otherwise.
// It's also the place where the "RED" algorithm is triggered.
// Side effect (desired): assigns a value to min_rate_[i]
// *******************************************************************

int JoBS::minRatesNeeded(int priority) {
        int result;
        int i;
        double cur_time;
        Packet* p;
        hdr_cmn* cm_h; 

        cur_time = Scheduler::instance().clock();
        result = TRUE;
  
        for (i = 1; i <= NO_CLASSES; i++) {
                if (cls_[i]->head() != 0 && (concerned_ADC_[i] || concerned_ARC_[i])) {
                        p = cls_[i]->head();
                        cm_h = hdr_cmn::access(p);

                        if (concerned_ADC_[i]) { 
                                if ((ADC_[i] - (cur_time-cm_h->ts_)) > 0 ) {
                                        // min rate needed for ADC
                                        min_rate_[i] = (double)(backlog_Bits_[i])
                                            /(double)(ADC_[i] - (cur_time-cm_h->ts_));
                                        if (concerned_ARC_[i] && ARC_[i] > min_rate_[i]) {
                                                // min rate needed for ADC+ARC
                                                min_rate_[i] = ARC_[i];
                                        }
                                } else 
                                        min_rate_[i] = INFINITY;        
                        } else if (concerned_ARC_[i]) {
                                // no ADC, an ARC
                                min_rate_[i] = ARC_[i];
                        }
                        if (min_rate_[i] > service_rate_[i]) 
                                result = FALSE;
                } else 
                        min_rate_[i] = 0.0;
        }
        return result;
}

// *******************************************************************
// JoBS: Returns the value of the delay metric for class i
// *******************************************************************

double JoBS::projDelay(int i) {
        double cur_time  = Scheduler::instance().clock(); 
        if (cls_[i]->head() != NULL) {
                Packet* p = cls_[i]->head();
                hdr_cmn* cm_h = hdr_cmn::access(p);
                return (cur_time - cm_h -> ts_);
        } else return 0.0; // __NOT REACHED__
}

// 2) Dropping Primitives

// *******************************************************************
// JoBS: Choose which class to drop from in case of a buffer overflow
// *******************************************************************

int JoBS::pickDroppedRLC(int mode) {
        double Mean;
        double loss_error[NO_CLASSES+1];
        int i, activeClasses, backloggedClasses;
        int class_dropped;
        double maxError;
        double maxALC;
        double cur_time  = Scheduler::instance().clock(); 

        hdr_cmn* cm_h; 
        
        class_dropped = -1;
        maxError = 0;
        Mean = 0;
        activeClasses = 0;
        backloggedClasses = 0;
        
        for (i = 1; i <= NO_CLASSES; i++) 
                if (cls_[i]->head() != NULL) {
                        backloggedClasses ++;
                        if (concerned_RLC_[i]) {
                                Mean += loss_prod_others_[i]*current_loss_[i];
                                activeClasses ++;
                        }    
                }
        
        if (activeClasses > 0) 
                Mean /= (double)activeClasses;
        else if (backloggedClasses == 0) {
                fprintf(stderr, "JoBS::pickDroppedRLC() called but there's no backlog!\n");
                abort();
        }

        if (activeClasses == 0) 
                class_dropped = NO_CLASSES+1; // no classes are concerned by RLCs (NO_CLASSES+1 means "ignore RLC")
        else {
                for (i = 1; i <= NO_CLASSES; i++) 
                        if ((cls_[i]->head() != NULL)&&(concerned_RLC_[i])) 
                                loss_error[i]=loss_prod_others_[i]*current_loss_[i]-Mean;
                        else 
                                loss_error[i] = INFINITY; 
    
                for (i = 1; i <= NO_CLASSES; i++)
                        if ((cls_[i]->head() != NULL)&&(loss_error[i] <= maxError)) {
                                maxError = loss_error[i]; // Find out which class is the most below the mean
                                class_dropped = i;   // It's the one that needs to be dropped
                                // Ties are broken in favor of the higher priority classes (i.e., if
                                // two classes present the same deviation, the lower priority class 
                                // will get dropped).
                        } 
                
                if (class_dropped != -1) {
                        if (drop_front_)
                                cm_h = hdr_cmn::access(cls_[class_dropped] -> head());
                        else
                                cm_h = hdr_cmn::access(cls_[class_dropped] -> tail());

                        if (current_loss_[class_dropped]+(double)8*cm_h -> size()/(double)Arrival_[class_dropped] > ALC_[class_dropped])
                                class_dropped = NO_CLASSES+1; // the class to drop for meeting the RLC will defeat the ALC: ignore RLC.
                } else 
                        class_dropped = NO_CLASSES+1;
        }

        if (class_dropped != -1) { // this test is here only for "safety purposes" 
                // it should always return true at this point.
                if (class_dropped == NO_CLASSES+1) {
                        maxALC = -INFINITY;
                        for (i = 1; i <= NO_CLASSES; i++) {
                                if (cls_[i] -> tail() != NULL) {
                                        if (ALC_[i]-current_loss_[i] > maxALC);
                                        maxALC = ALC_[i]-current_loss_[i]; // pick the class which is the furthest from its ALC
                                        class_dropped = i;
                                }
                        }
                        if (drop_front_)
                          cm_h = hdr_cmn::access(cls_[class_dropped]->head());
                        else
                          cm_h = hdr_cmn::access(cls_[class_dropped]->tail());
                        if ((mode == RESOLVE_OVERFLOW)
                            &&(current_loss_[class_dropped]+(double)8*cm_h -> size()/(double)Arrival_[class_dropped] > ALC_[class_dropped])) {

                                fprintf(stderr, "*** Warning at time t=%f: ALC violated in class %d on link %d\n(reason: buffer overflow impossible to resolve otherwise)\nPkt size=%d bits\told_loss[%d]=%f\tnew_loss[%d]=%f\tArrival_[%d]=%f\tALC[%d]=%f\n",
                                        cur_time, link_id_,
                                        class_dropped, 8*cm_h -> size(),
                                        class_dropped, current_loss_[class_dropped],
                                        class_dropped, current_loss_[class_dropped]+(double)8*cm_h -> size()/(double)Arrival_[class_dropped],
                                        class_dropped, (double)Arrival_[class_dropped],
                                        class_dropped, ALC_[class_dropped]);
                        }
                }               
        } else {
                fprintf(stderr, "Trying to drop a packet, but there's nothing in any queue!\n");
                abort();
        }
        return class_dropped;
}

// *******************************************************************
// JoBS: Drops traffic from the tail of the specified class, and 
// update the statistics.
// *******************************************************************

void JoBS::dropTail(int prio, int strategy) {
        Packet *p;
        hdr_cmn *cm_h;
        
        p = cls_[prio] -> tail();
        cm_h = hdr_cmn::access(p);
        
        total_backlog_Pkts_ --;
        total_backlog_Bits_ -= 8*cm_h->size();
        backlog_Pkts_[prio] --;
        backlog_Bits_[prio] -= 8*cm_h->size();
        Rin_[prio] -= 8*cm_h->size();
        if (strategy == WITH_UPDATE) {
                for (int i = 1; i <= NO_CLASSES; i++) 
                        current_loss_[i] = min_drop_[i];
                current_loss_[prio] += (double)8*cm_h -> size() 
                    /(double)Arrival_[prio];
        }
        cls_[prio] -> remove(p);
        drop(p);
        return;
}

// *******************************************************************
// JoBS: Drops traffic from the head of the specified class, and 
// update the statistics.
// *******************************************************************

void JoBS::dropFront(int prio, int strategy) {
        Packet *p;
        hdr_cmn *cm_h;
        
        p = cls_[prio] -> head();
        cm_h = hdr_cmn::access(p);
        total_backlog_Pkts_ --;
        total_backlog_Bits_ -= 8*cm_h->size();
        backlog_Pkts_[prio] --;
        backlog_Bits_[prio] -= 8*cm_h->size();
        Rin_[prio] -= 8*cm_h->size();
        if (strategy == WITH_UPDATE) {
                for (int i = 1; i <= NO_CLASSES; i++) 
                        current_loss_[i] = min_drop_[i];
                current_loss_[prio] += (double)8*cm_h -> size() 
                  /(double)Arrival_[prio];
        }
        cls_[prio] -> remove(p);
        drop(p);
        return;
}  


// 3) Other Helpers

// *******************************************************************
// JoBS: Update internal variables upon a packet arrival.
// *******************************************************************

void JoBS::arvAccounting(Packet* thePacket) {
        int i;
        double cur_time;
        hdr_cmn* cm_h;
        hdr_cmn* cm_h1;
        hdr_cmn* cm_h2; 
        hdr_ip*  ip_h; 
        
        cur_time = Scheduler::instance().clock();
        cm_h = hdr_cmn::access(thePacket);
        ip_h = hdr_ip::access(thePacket);
        
        /* Update curves */
        
        Arrival_[ip_h -> prio()]      += 8*cm_h -> size();
        Rin_    [ip_h -> prio()]      += 8*cm_h -> size();
        if (last_rate_update_[ip_h -> prio()] == 0) {
                last_rate_update_[ip_h -> prio()] = cur_time;
        } else {
                Rout_th_ [ip_h -> prio()]      += (cur_time-last_rate_update_[ip_h -> prio()])*service_rate_[ip_h -> prio()];
                last_rate_update_[ip_h -> prio()] = cur_time;
        }
        backlog_Pkts_[ip_h -> prio()] ++;
        backlog_Bits_[ip_h -> prio()] += 8*cm_h -> size();
        total_backlog_Bits_ += 8*cm_h -> size();
        total_backlog_Pkts_ ++;
        
        for (i = 1; i <= NO_CLASSES; i++) {
                if (Arrival_[i] > 0) {
                        current_loss_[i] = (double)(Arrival_[i] - Rin_[i])/(double)(Arrival_[i]);
                        min_drop_[i] = (double)(max(0.0, (1.0-(double)(Rin_[i])/(double)Arrival_[i])));
                        max_drop_[i] = (double)(min(1.0, (1.0-(double)((double)Rout_[i]/(double)Arrival_[i]))));        
                } else {
                        current_loss_[i] = 0;
                        min_drop_[i] = 0.0;
                        max_drop_[i] = 0.0;
                }
                
                if (cls_[i]->head() != NULL) {
                        cm_h1 = hdr_cmn::access(cls_[i]->head());
                        cm_h2 = hdr_cmn::access(cls_[i]->tail());
                        avg_elapsed_[i] = (2*cur_time - cm_h1 -> ts_ - cm_h2 -> ts_)/((backlog_Pkts_[i]>1)? 2.0 :1.0);
                }
        }
        return;
}

// 4) Debugging Tools

void JoBS::updateStats(Packet* p, int action) {
        double cur_time = Scheduler::instance().clock();
        hdr_cmn* cm_h;
        hdr_ip* ip_h;
        
        cm_h = hdr_cmn::access(p);
        ip_h = hdr_ip::access(p);
        if (action == UPDATE_STATS) {
                sliding_arv_pkts_++;
                sliding_arv_pkts_c[ip_h->prio()]++;
                sliding_inter_ = (cur_time - last_arrival_ + sliding_inter_ * (sliding_arv_pkts_-1))
                    /(double)sliding_arv_pkts_;
                sliding_avg_pkt_size_ = (sliding_avg_pkt_size_*(sliding_arv_pkts_ - 1) + 8*cm_h->size())
                    /(double)sliding_arv_pkts_; 
                last_arrival_ = cur_time;
        } else if (action == RESET_STATS) {
                if (trace_hop_) {
                        fprintf(hop_trace_, "%f\t", cur_time);
                        for (int i=1;i<=NO_CLASSES;i++) {
                                fprintf(hop_trace_, "%.8f\t", max(current_loss_[i],0.00000001));
                        }
                        for (int i=1;i<=NO_CLASSES;i++) {
                                fprintf(hop_trace_, "%.8f\t", max(sliding_class_delay_[i],0.00000001));
                        }
                        for (int i=1;i<=NO_CLASSES;i++) {
                                sliding_class_service_rate_[i] = sliding_serviced_bits_[i]/(double)MON_WINDOW_SIZE;
                                fprintf(hop_trace_, "%.0f\t", max(sliding_class_service_rate_[i], 1));
                                sliding_serviced_pkts_[i] = 0;
                                sliding_serviced_bits_[i] = 0;
                                sliding_class_delay_[i] = 0;
                                sliding_class_service_rate_[i] = 0;
                        }
                        for (int i=1;i<=NO_CLASSES;i++) {
                                fprintf(hop_trace_, "%.0f\t", (double)cls_[i]->length());
                        }
                        fprintf(hop_trace_, "\n");
                }
                sliding_arv_pkts_ = 1;
                sliding_arv_pkts_c[ip_h->prio()] = 1;
                sliding_inter_ = cur_time - last_arrival_;
                sliding_avg_pkt_size_ = 8*cm_h->size();
                last_arrival_ = cur_time;
        }
        util_ = sliding_avg_pkt_size_ / (sliding_inter_*link_->bandwidth());
        return;
}

---