src/util/load.c

   1 /*
   2      This file is part of GNUnet.
   3      (C) 2010 Christian Grothoff (and other contributing authors)
   4
   5      GNUnet is free software; you can redistribute it and/or modify
   6      it under the terms of the GNU General Public License as published
   7      by the Free Software Foundation; either version 2, or (at your
   8      option) any later version.
   9
  10      GNUnet is distributed in the hope that it will be useful, but
  11      WITHOUT ANY WARRANTY; without even the implied warranty of
  12      MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  13      General Public License for more details.
  14
  15      You should have received a copy of the GNU General Public License
  16      along with GNUnet; see the file COPYING.  If not, write to the
  17      Free Software Foundation, Inc., 59 Temple Place - Suite 330,
  18      Boston, MA 02111-1307, USA.
  19 */
  20
  21 /**
  22  * @file util/load.c
  23  * @brief functions related to load calculations
  24  * @author Christian Grothoff
  25  */
  26 #include "platform.h"
  27 #include "gnunet_load_lib.h"
  28
  29 #define DEBUG_LOAD GNUNET_NO
  30
  31 /**
  32  * Values we track for load calculations.
  33  */
  34 struct GNUNET_LOAD_Value
  35 {
  36
  37   /**
  38    * Sum of all datastore delays ever observed (in ms).  Note that
  39    * delays above 64k ms are excluded (to avoid overflow within
  40    * first 4 billion requests).
  41    */
  42   uint64_t cummulative_delay;
  43
  44   /**
  45    * Sum of squares of all datastore delays ever observed (in ms).   Note that
  46    * delays above 64k ms are excluded (to avoid overflow within
  47    * first 4 billion requests).
  48    */
  49   uint64_t cummulative_squared_delay;
  50
  51   /**
  52    * Total number of requests included in the cummulative datastore delay values.
  53    */
  54   uint64_t cummulative_request_count;
  55
  56   /**
  57    * Current running average datastore delay.  Its relation to the
  58    * average datastore delay and it std. dev. (as calcualted from the
  59    * cummulative values) tells us our current load.
  60    */
  61   double runavg_delay;
  62
  63   /**
  64    * How high is the load?  0 for below average, otherwise
  65    * the number of std. devs we are above average, or 100 if the
  66    * load is so high that we currently cannot calculate it.
  67    */
  68   double load;
  69
  70 };
  71
  72
  73 /**
  74  * Create a new load value.
  75  *
  76  * @return the new load value
  77  */
  78 struct GNUNET_LOAD_Value *
  79 GNUNET_LOAD_value_init ()
  80 {
  81   return GNUNET_malloc (sizeof (struct GNUNET_LOAD_Value));
  82 }
  83
  84
  85 /**
  86  * Get the current load.
  87  *
  88  * @param load load handle
  89  * @return zero for below-average load, otherwise
  90  *         number of std. devs we are above average;
  91  *         100 if the latest updates were so large
  92  *         that we could not do proper calculations
  93  */
  94 double
  95 GNUNET_LOAD_get_load (const struct GNUNET_LOAD_Value *load)
  96 {
  97   return load->load;
  98 }
  99
 100
 101 /**
 102  * Get the average value given to update so far.
 103  *
 104  * @param load load handle
 105  * @return zero if update was never called
 106  */
 107 double
 108 GNUNET_LOAD_get_average (const struct GNUNET_LOAD_Value *load)
 109 {
 110   double n;
 111   double sum_val_i;
 112
 113   if (load->cummulative_request_count == 0)
 114     return 0.0;
 115   n = ((double) load->cummulative_request_count);
 116   sum_val_i = (double) load->cummulative_delay;
 117   return sum_val_i / n;
 118 }
 119
 120
 121 /**
 122  * Update the current load.
 123  *
 124  * @param load to update
 125  * @param data latest measurement value (for example, delay)
 126  */
 127 void
 128 GNUNET_LOAD_update (struct GNUNET_LOAD_Value *load,
 129                     uint64_t data)
 130 {
 131   uint32_t dv;
 132   double stddev;
 133   double avgdel;
 134   double sum_val_i;
 135   double n;
 136   double nm1;
 137
 138   if (data > 64 * 1024)
 139     {
 140       /* very large */
 141       load->load = 100.0;
 142       return;
 143     }
 144   dv = (uint32_t) data;
 145   load->cummulative_delay += dv;
 146   load->cummulative_squared_delay += dv * dv;
 147   load->cummulative_request_count++;
 148   load->runavg_delay = ((load->runavg_delay * 7.0) + dv) / 8.0;
 149   if (load->cummulative_request_count > 1)
 150     {
 151       /* calcuate std dev of latency; we have for n values of "i" that:
 152
 153          avg = (sum val_i) / n
 154          stddev = (sum (val_i - avg)^2) / (n-1)
 155                 = (sum (val_i^2 - 2 avg val_i + avg^2) / (n-1)
 156                 = (sum (val_i^2) - 2 avg sum (val_i) + n * avg^2) / (n-1)
 157       */
 158       sum_val_i = (double) load->cummulative_delay;
 159       n = ((double) load->cummulative_request_count);
 160       nm1 = n - 1.0;
 161       avgdel = sum_val_i / n;
 162       stddev = (((double) load->cummulative_squared_delay) - 2.0 * avgdel * sum_val_i + n * avgdel * avgdel) / nm1;
 163       if (stddev <= 0)
 164         stddev = 0.01; /* must have been rounding error or zero; prevent division by zero */
 165       /* now calculate load based on how far out we are from
 166          std dev; or if we are below average, simply assume load zero */
 167       if (load->runavg_delay < avgdel)
 168         load->load = 0.0;
 169       else
 170         load->load = (load->runavg_delay - avgdel) / stddev;
 171     }
 172 }
 173
 174
 175 /* end of load.c */