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.3 2005/07/27 01:13:44 tomh 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.3 2005/07/27 01:13:44 tomh 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+1];
    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;
}

---