//===================================================== file = ALR_dual.c ===== //= A CSIM simulation of an adaptive service time M/M/1 queue = //= - Implements ALR dual-threshold policy = //= - This program verified against analytical model for = //= - packet based buffers and Poisson arrivals = //============================================================================= //= Notes: = //= 1. Can either generate Poisson arrivals or read arrivals from trace = //= 2. Buffer size can be set in either packets or bytes = //= 3. The following parameters are given in the command line = //= - Time to switch data rates (in seconds) = //= - Target utilization for GEN_TYPE == POISSON. This input is = //= required but ignored when GEN_TYPE == FILE. = //= - Trace file with arrivals (only for GEN_TYPE == FILE ) = //= = //= To use generated Poisson arrivals = //= 1. Set GEN_TYPE == POISSON = //= 2. Arrival (lambda) and low service rate (mu) are set in main() = //= 3. High service rate is mu * MAX_RATE (the rate multiplier) = //= = //= To use arrivals read-in from traces = //= 1. Set GEN_TYPE == FILE = //= 2. Set FILE_FORMAT to appropriate file format = //= 3. If trace does not have packet sizes, set PKT_SIZE to required value = //= 4. Set DATA_RATE to the required value (in bits per second) = //= = //= To use packet based buffers: = //= 1. Uncomment #define BUFFER_PKT = //= 2. Set THRESH_MIN_PKT and THRESH_MAX_PKT = //= = //= To use byte based buffers: = //= 1. Comment out #define BUFFER_PKT = //= 2. Set BUFFER_SIZE to maximum buffer size (in bytes) = //= 3. Set THRESH_MIN_KBYTE and THRESH_MAX_KBYTE (in kilo bytes) = //= = //=---------------------------------------------------------------------------= //= Example input: = //= Packet based buffers: THRESH_MIN_PKT = 1, THRESH_MAX_PKT = 30 = //= GEN_TYPE == POISSON = //= T_switch = 0.0, Target_Util = 0.40 (40% utilization) = //= mu = 8333.3333 (assuming mean 1500 byte packet size) = //=---------------------------------------------------------------------------= //= Example execution: = //= === BEGIN SIMULATION === = //= ============================================ ALR_dual.c ======= = //= == *** CSIM simulation of an adaptive service time queue *** == = //= =============================================================== = //= = >>> Poisson = //= = lambda = 33333.333200 cust/sec = //= = mu = 8333.333300 cust/sec = //= = Target_Util = 40.0000 % = //= = T_switch = 0.000000 sec = //= = DATA_RATE = 100.000000 Mb/s = //= = MAX_RATE = 10 = //= = Thresh_max = 30 pkts = //= = Thresh_min = 1 pkts = //= = P_FIX = 0.000000 Watts = //= = P_LOW = 1.500000 Watts = //= = P_HIGH = 4.000000 Watts = //= =============================================================== = //= = Total CPU time = 29.093000 sec = //= = Total sim time = 300.137620 sec = //= = Total completions = 9999988 cust = //= =-------------------------------------------------------------- = //= = Server utilization = 98.022326 % = //= = Mean num in system = 17.239956 cust = //= = Mean response time = 0.000517 sec 0.517437 ms = //= = Mean service time = 0.000029 sec 0.029420 ms = //= = Mean throughput = 33318.009228 cust/sec = //= = Max queue length = 83 pkts = //= = Total service time = 294.201874 sec = //= = Ideal low time = 300.137620 sec = //= =-------------------------------------------------------------- = //= = Time in low rate = 199.48 sec 66.46 % = //= = Time in high rate = 100.66 sec 33.54 % = //= = Num rate switches = 296072 = //= =-------------------------------------------------------------- = //= = alpha metric = 1.710540 = //= = gamma metric = 1.710540 = //= =============================================================== = //= = //=---------------------------------------------------------------------------= //= Build: bcc32 -w-pro ALR_dual.c csim19.obj csim19.lib = //=---------------------------------------------------------------------------= //= Execute: ALR_dual T_switch Target_Util < in.dat = //= T_switch - time to switch data rates (in seconds) = //= Target_Util - target utilization - range is (0,1) = //= - (used in GEN_TYPE == POISSON ) = //= in.dat - input trace file (used in GEN_TYPE == FILE ) = //=---------------------------------------------------------------------------= //= Author: Chamara Gunaratne = //= University of South Florida = //= Email: pgunarat@csee.usf.edu = //=---------------------------------------------------------------------------= //= History: KJC (06/14/05) - Genesis (from adaptive5.c) = //= Aug 25, 2005 - Modified from adaptive5.c = //= Sep 26, 2005 - Modified from adaptive6.c = //= Sep 26, 2005 - Added byte based buffers = //= Oct 18, 2005 - Changed variable names = //= Dec 11, 2005 - Modified from adaptive7.c = //= Dec 11, 2005 - Added low threshold as well as high = //= Mar 18, 2006 - Removed a lot of junk and cleaned up code = //= Dec 25, 2006 - Renamed ALR_dual.c = //= Jan 13, 2007 - Some minor modifications = //============================================================================= //----- Includes -------------------------------------------------------------- #include // Needed for printf() #include // needed for atof() #include // needed for atof() #include // Needed for assert() macro #include "csim.h" // Needed for CSIM18 stuff //----- Defines --------------------------------------------------------------- #define FALSE 0 // Boolean false #define TRUE 1 // Boolean true #define POISSON 0 // Poisson generator #define FILE 1 // Read in from trace file #define USF 0 // Delta time in seconds, packet size in bytes #define PSU 1 // Delat time in microseconds, packet size zero #define TIME_ONLY 2 // Delta time in seconds, no packet size #define FILE_FORMAT USF // data file format //#define FILE_FORMAT PSU // data file format //#define FILE_FORMAT TIME_ONLY // data file format //#define GEN_TYPE POISSON // Generator type #define GEN_TYPE FILE // Generator type #define BUFFER_PKT // Switch buffer to packet mode from byte mode #define SIM_TIME 10.0e3 // Total simulation time in seconds #define MAX_ARRIVALS 10.0e6 // Maximum number of arrivals (for Poisson) #define PKT_SIZE 1518 // pkt size for traces without pkt size #define DATA_RATE 10e6 // low service rate of queue in bits/s #define MAX_RATE 10 // Rate multiplier #define BUFFER_SIZE 32768 // buffer size in bytes - 32KB #define THRESH_MIN_PKT 15 // Min threshold (k1) in packets (must be > 0) #define THRESH_MAX_PKT 30 // Max threshold (k2) in packets #define THRESH_MIN_KBYTE 0 // Min threshold (k1) in kilo bytes #define THRESH_MAX_KBYTE 32 // Max threshold (k2) in kilo bytes #define RATE_SAMPLE_TIME 0.200 // rate sampling interval for printing rate #define U_THRESH 0.05 // Low utilization threshold #define P_FIX 0.0 // Power consumption fixed #define P_LOW 1.5 // Power consumption low data rate #define P_HIGH 4.0 // Power consumption high data rate //----- Globals --------------------------------------------------------------- FACILITY Server; // CSIM facility for server EVENT Done; // CSIM event for trace is done TABLE Table_rate1; // CSIM table for time in low rate TABLE Table_rateMax; // CSIM table for time in high rate TABLE Table_delay; // CSIM table for response times long int Rate_switch_count; // Rate switch counter int Rate_index; // Rate index double Rate_switch_time; // Time of last rate switch int Util_switch_flag; // Utilization switch flag long int Max_queue_length; // Maximum recorded queue length double Total_serv_time; // Total time spent servicing arrivals long int Buffer_size; // Current buffer size - in bytes double Ideal_low_time; // Ideal low time with no delay impact long int Thresh_min; // Minimum threshold level (byte or pkt) long int Thresh_max; // Maximum threshold level (byte or pkt) // these variables are accepted from the command line double T_switch; // Time to switch between rates (sec) double Target_Util; // Targeted utilization level (Poisson only) //----- Prototypes ------------------------------------------------------------ void gen_poisson(double lambda, double mu); // Generator void gen_file(); // Generator void queue1(double service_time, double pkt_size, double start_time); // Queue void print_rate(void); // periodically sample and print the data rate //============================================================================= //== Main program == //============================================================================= void sim(int argc, char *argv[]) { double lambda; // Mean arrival rate (cust/sec) double mu; // Mean service rate (cust/sec) double e_norm; // Energy used if only high data rate double e_save; // Energy used in savings mode double alpha_metric; // Singh energy metric (E/Es) double gamma_metric; // Green energy metric (E/Es)(D/Ds) // sanity check assert(argc == 3); // update T_switch and other parameters from command line T_switch = (double)atof(argv[1]); Target_Util = (double)atof(argv[2]); // debug //printf("T_switch: %f D_BOUND: %f Target_Util: %f \n", \ T_switch, D_BOUND, Target_Util); // Set the maximum and minimum buffer thresholds #ifdef BUFFER_PKT // if counting buffer in packets // Set the minimum threshold Thresh_min = THRESH_MIN_PKT; // Set the maximum threshold Thresh_max = THRESH_MAX_PKT; #else // if counting buffer in bytes // Set the minimum threshold Thresh_min = (int)((double)THRESH_MIN_KBYTE * 1024.0); // Set the maximum threshold Thresh_max = (int)((double)THRESH_MAX_KBYTE * 1024.0); // sanity check assert(Thresh_max <= BUFFER_SIZE); #endif // sanity check - check that max is < min assert(Thresh_min < Thresh_max); // debug //printf("Thresh_min: %d Thresh_max: %d THRESH_DYNA: %d \n", \ (int)Thresh_min, (int)Thresh_max, (int)THRESH_DYNA); // Create the simulation create("sim"); // CSIM and variable initializations Server = facility("Server for single-server queue"); Table_rate1 = table("Rate index 1 time table"); Table_rateMax = table("Rate index RATE_MAX time table"); Table_delay = table("Response time delays"); Done = event("Done"); max_processes((long)100000 ); Rate_index = 1; // start in low rate - problems with high util traces Rate_switch_count = 0; Rate_switch_time = 0.0; Max_queue_length = 0; Total_serv_time = 0.0; Buffer_size = 0; Ideal_low_time = 0.0; // Parameter initializaitons - for Poisson mu = 8333.3333; // lambda as a percentage of mu lambda = (double)mu * (double)MAX_RATE * (double)Target_Util; // lambda as a percentage of 1 Gb/s data rate with 1500 byte pkts - no mu //lambda = (double)83333.3333 * (double)Target_Util; // Output begin-of-simulation banner printf("=== BEGIN SIMULATION === \n"); // Initiate the rate printing process (for graphing data only) //print_rate(); // Initiate appropriate generate function if (GEN_TYPE == POISSON) gen_poisson(lambda, mu); else if (GEN_TYPE == FILE) gen_file(); // Wait for the end of the simulation if (GEN_TYPE == POISSON) wait(Done); else if (GEN_TYPE == FILE) wait(Done); // Make last update to rate tables if (Rate_index == 1) record((clock - Rate_switch_time), Table_rate1); else if (Rate_index == MAX_RATE) record((clock - Rate_switch_time), Table_rateMax); // Compute Singh energy metric e_norm = clock * (P_FIX + P_HIGH); e_save = clock * P_FIX; e_save = e_save + (table_sum(Table_rate1) * P_LOW); e_save = e_save + (table_sum(Table_rateMax) * P_HIGH); alpha_metric = e_norm / e_save; // Compute Green energy metric - not used in this program gamma_metric = alpha_metric; /*if (resp(Server) <= D_BOUND) gamma_metric = alpha_metric; else gamma_metric = alpha_metric * (D_BOUND / resp(Server));*/ // Output results printf("============================================ ALR_dual.c ======= \n"); printf("== *** CSIM simulation of an adaptive service time queue *** == \n"); printf("=============================================================== \n"); printf("= >>> NO ADAPTIVE THRESHOLD \n"); if (GEN_TYPE == POISSON) { printf("= >>> Poisson \n"); printf("= lambda = %f cust/sec \n", lambda); printf("= mu = %f cust/sec \n", mu); printf("= Target_Util = %.2f %% \n", ((double)Target_Util * 100) ); } else if (GEN_TYPE == FILE) { printf("= >>> FILE \n"); } printf("= T_switch = %f sec \n", T_switch); printf("= DATA_RATE = %f Mb/s \n", (double)DATA_RATE/1e6); printf("= MAX_RATE = %d \n", MAX_RATE); #ifdef BUFFER_PKT printf("= Thresh_max = %d pkts \n", Thresh_max); printf("= Thresh_min = %d pkts \n", Thresh_min); #else printf("= BUFFER_SIZE = %d KB \n", (BUFFER_SIZE/1024) ); printf("= Thresh_max = %d KB \n", (Thresh_max/1024) ); printf("= Thresh_min = %d KB \n", (Thresh_min/1024) ); #endif printf("= P_FIX = %f Watts \n", P_FIX); printf("= P_LOW = %f Watts \n", P_LOW); printf("= P_HIGH = %f Watts \n", P_HIGH); printf("=============================================================== \n"); printf("= Total CPU time = %f sec \n", cputime()); printf("= Total sim time = %f sec \n", clock); printf("= Total completions = %d cust \n", completions(Server)); printf("=-------------------------------------------------------------- \n"); printf("= Server utilization = %f %% \n", 100.0 * util(Server)); printf("= Mean num in system = %f cust \n", qlen(Server)); printf("= Mean response time = %f sec %f ms \n", resp(Server), resp(Server) * 1000); printf("= Mean service time = %f sec %f ms \n", serv(Server), serv(Server) * 1000); printf("= Mean throughput = %f cust/sec \n", tput(Server)); #ifdef BUFFER_PKT printf("= Max queue length = %d pkts \n", Max_queue_length); #else printf("= Max queue length = %d bytes \n", Max_queue_length); #endif printf("= Total service time = %f sec \n", Total_serv_time); printf("= Ideal low time = %f sec \n", Ideal_low_time); printf("=-------------------------------------------------------------- \n"); printf("= Time in low rate = %.2f sec\t %.2f %% \n", table_sum(Table_rate1), (table_sum(Table_rate1) * 100.0 / clock)); printf("= Time in high rate = %.2f sec\t %.2f %% \n", table_sum(Table_rateMax), (table_sum(Table_rateMax) * 100.0 / clock)); printf("= Num rate switches = %d \n", Rate_switch_count); printf("=-------------------------------------------------------------- \n"); printf("= alpha metric = %f \n", alpha_metric); printf("= gamma metric = %f \n", gamma_metric); printf("=============================================================== \n"); } //============================================================================= //== Process to generate Poisson customers == //============================================================================= void gen_poisson(double lambda, double mu) { int out_id; // To (destination) outport number double z; // Random number between 0.0 and 1.0 double inter_arrival_time; // Inter arrival time double service_time; // Service time for this customer double pkt_size = 0; // pkt size double trace_time = 0.0; // total time in trace double temp1; unsigned long int counter = 0; // count up to exit create("gen_poisson"); // Packet generation loop while(TRUE) { // Hold for interarrival time inter_arrival_time = expntl(1.0 / lambda); hold(inter_arrival_time); // Compute ideal low time temp1 = inter_arrival_time - ((double)T_switch * 2.0); if (temp1 > 0) Ideal_low_time = Ideal_low_time + temp1; // increment the running trace time value trace_time = trace_time + inter_arrival_time; // service time is exponentially distributed service_time = exponential(1.0 / mu); // if generating service times using average packet sizes //pkt_size = expntl((double)1500.00); //service_time = (pkt_size * 8) / DATA_RATE; // increment the input buffer size Buffer_size = Buffer_size + (long int)pkt_size; // enqueue packet queue1(service_time, pkt_size, (double)clock); // debug //printf("clock: %f trace_time: %f pkt_size: %.1f service_time: %f\n", \ clock, trace_time, pkt_size, service_time); counter = counter + 1; if ((double)counter > (double)MAX_ARRIVALS) break; } set(Done); } //============================================================================= //== Process to read trace file and generate customers == //============================================================================= void gen_file() { char seps[] = " \t,"; // possible token separators char *token; // temporary token holder char instring[1000]; // for reading in data from stdin double service_time; // Service time for this customer double inter_arrival_time; // pkt arrival time double pkt_size; // pkt size double trace_time = 0.0; // total time in trace double temp1; // Temporary variable create("gen_file"); // Loop forever to create customers while(1) { // read in the data line gets(instring); // if end-of-file exit loop if (feof(stdin)) break; // check for comments if ((instring[0] == '#') || (instring[0] == '&')) continue; // for traces with arrival time in seconds and pkt size in bytes if (FILE_FORMAT == USF) { token = (char *)strtok(instring, seps); inter_arrival_time = (double)atof(token); token = (char *)strtok(NULL, seps); pkt_size = (double)atof(token); } // For Singh's traces - arrival time is in us, no pkt size else if (FILE_FORMAT == PSU) { token = (char *)strtok(instring, seps); inter_arrival_time = (double)atof(token) / 1e6; pkt_size = (double)PKT_SIZE; } // For traces with arrival time only is seconds, no pkt size else if (FILE_FORMAT == TIME_ONLY) { token = (char *)strtok(instring, seps); inter_arrival_time = (double)atof(token); pkt_size = (double)PKT_SIZE; } // sanity check - sometimes negative numbers exist in delta times if (inter_arrival_time < 0) inter_arrival_time = 0.0; // Compute ideal low time temp1 = inter_arrival_time - ((double)T_switch * 2.0); if (temp1 > 0) Ideal_low_time = Ideal_low_time + temp1; // increment the running trace time value trace_time = trace_time + inter_arrival_time; // calculate the service time for packet at 'low' data rate service_time = (pkt_size * 8) / DATA_RATE; // hold for arrival time hold(inter_arrival_time); // increment the input buffer size Buffer_size = Buffer_size + (long int)pkt_size; // enqueue packet queue1(service_time, pkt_size, (double)clock); // debug //printf("clock: %.3f trace_time: %.3f arrival_time: %.6f pkt_size: %.1f service_time: %.10f\n", \ clock, trace_time, arrival_time, pkt_size, service_time); } set(Done); } //============================================================================= //== Process for single server queue with adaptive rate change == //============================================================================= void queue1(double service_time, double pkt_size, double start_time) { double t_queue; // for computing queueing time double t_response; // for computing response time static double t_last_depart = 0.0; // for computing inter-departure CoV create("queue1"); // update max queue length #ifdef BUFFER_PKT if (qlength(Server) > Max_queue_length) Max_queue_length = qlength(Server); #else if (Buffer_size > Max_queue_length) Max_queue_length = Buffer_size; #endif // debug //printf("clock: %f enqueuing packet. pkt_size: %d Buffer_size: %d \n", clock,\ (int)pkt_size, (int)qlength(Server) ); // Reserve the server reserve(Server); // Increase the rate if queue length is at threshold (>=) #ifdef BUFFER_PKT if ( (qlength(Server) >= (Thresh_max - 1) ) && (Rate_index == 1)) #else if ( (Buffer_size >= Thresh_max) && (Rate_index == 1)) #endif { // debug //printf("clock: %f - changed to higher data rate. Buffer_size: %d Low rate time: %.10f \n", \ clock, (int)qlength(Server), (clock - Rate_switch_time) ); // hack - this assert triggers on equal!! - it should trigger on < only if (clock > T_switch) assert((clock - Rate_switch_time) >= (T_switch * 0.999999) ); record((clock - Rate_switch_time), Table_rate1); Rate_index = MAX_RATE; Rate_switch_time = clock; Rate_switch_count++; hold(T_switch); } // compute the queueing time t_queue = (double)clock - start_time; // Service the customer hold(service_time / Rate_index); // compute the response time (queueing time + processing time) t_response = (double)clock - start_time; // record the delay time in table for intermediate calculations tabulate(Table_delay, t_response); // print the data for calculating 99% delay and CoV //printf("t_queue: %.10f t_response: %.10f \n", t_queue, t_response); //printf("t_inter_packet: %.10f \n", (clock - t_last_depart) ); // update last departure time t_last_depart = clock; // decrement the input buffer and sanity check Buffer_size = Buffer_size - (int)pkt_size; assert(Buffer_size >= 0); // debug //printf("clock: %f service_time: %f Rate_index: %d \n", clock, \ service_time, Rate_index); //printf("clock: %f dequeueed packet. pkt_size: %d Buffer_size: %d \n", \ clock, (int)pkt_size, (int)Buffer_size); // compute total service time Total_serv_time = Total_serv_time + (service_time / Rate_index); /* NOTE: CSIM qlength() gives the number in *queue* while Markov thresholds are based on number of jobs in *system*. at this point this job is still considered to be in the system. */ // Decrease the rate if queue length is less than Thresh_min (=<) #ifdef BUFFER_PKT if ( (qlength(Server) < (Thresh_min) ) && (Rate_index == MAX_RATE)) #else if ( (Buffer_size <= Thresh_min) && (Rate_index == MAX_RATE)) #endif { //debug //printf("clock: %f - changed to lower rate - Buffer_size: %d High rate time: %.10f \n", \ clock, (int)qlength(Server), (clock - Rate_switch_time)); record((clock - Rate_switch_time), Table_rateMax); Rate_index = 1; Rate_switch_time = clock; Rate_switch_count++; hold(T_switch); } // Release the server release(Server); } //============================================================================= //== Process for printing the data rate (for graphing purposes) == //============================================================================= void print_rate(void) { create("print_rate"); // rate printing loop while(1) { // Hold for a RATE_SAMPLE_TIME hold(RATE_SAMPLE_TIME); if (Rate_index == MAX_RATE) printf("%f %f %f print_rate\n", clock, (double)0, (double)1.0); else if (Rate_index == 1) printf("%f %f %f print_rate\n", clock, (double)1.0, (double)0); } }