2 This file is part of GNUnet.
3 (C) 2010 Christian Grothoff (and other contributing authors)
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.
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.
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.
23 * @brief functions related to load calculations
24 * @author Christian Grothoff
27 #include "gnunet_load_lib.h"
29 #define DEBUG_LOAD GNUNET_EXTRA_LOGGING
31 #define LOG(kind,...) GNUNET_log_from (kind, "util", __VA_ARGS__)
34 * Values we track for load calculations.
36 struct GNUNET_LOAD_Value
40 * How fast should the load decline if no values are added?
42 struct GNUNET_TIME_Relative autodecline;
45 * Last time this load value was updated by an event.
47 struct GNUNET_TIME_Absolute last_update;
50 * Sum of all datastore delays ever observed (in ms). Note that
51 * delays above 64k ms are excluded (to avoid overflow within
52 * first 4 billion requests).
54 uint64_t cummulative_delay;
57 * Sum of squares of all datastore delays ever observed (in ms). Note that
58 * delays above 64k ms are excluded (to avoid overflow within
59 * first 4 billion requests).
61 uint64_t cummulative_squared_delay;
64 * Total number of requests included in the cummulative datastore delay values.
66 uint64_t cummulative_request_count;
69 * Current running average datastore delay. Its relation to the
70 * average datastore delay and it std. dev. (as calcualted from the
71 * cummulative values) tells us our current load.
76 * How high is the load? 0 for below average, otherwise
77 * the number of std. devs we are above average, or 100 if the
78 * load is so high that we currently cannot calculate it.
86 internal_update (struct GNUNET_LOAD_Value *load)
88 struct GNUNET_TIME_Relative delta;
91 if (load->autodecline.rel_value == GNUNET_TIME_UNIT_FOREVER_REL.rel_value)
93 delta = GNUNET_TIME_absolute_get_duration (load->last_update);
94 if (delta.rel_value < load->autodecline.rel_value)
96 if (load->autodecline.rel_value == 0)
98 load->runavg_delay = 0.0;
102 n = delta.rel_value / load->autodecline.rel_value;
105 load->runavg_delay = 0.0;
112 load->runavg_delay = (load->runavg_delay * 7.0) / 8.0;
118 * Create a new load value.
120 * @param autodecline speed at which this value should automatically
121 * decline in the absence of external events; at the given
122 * frequency, 0-load values will be added to the load
123 * @return the new load value
125 struct GNUNET_LOAD_Value *
126 GNUNET_LOAD_value_init (struct GNUNET_TIME_Relative autodecline)
128 struct GNUNET_LOAD_Value *ret;
130 ret = GNUNET_malloc (sizeof (struct GNUNET_LOAD_Value));
131 ret->autodecline = autodecline;
132 ret->last_update = GNUNET_TIME_absolute_get ();
138 * Change the value by which the load automatically declines.
140 * @param load load to update
141 * @param autodecline frequency of load decline
144 GNUNET_LOAD_value_set_decline (struct GNUNET_LOAD_Value *load,
145 struct GNUNET_TIME_Relative autodecline)
147 internal_update (load);
148 load->autodecline = autodecline;
153 * Recalculate our load value.
155 * @param load load to update
158 calculate_load (struct GNUNET_LOAD_Value *load)
166 if (load->cummulative_request_count <= 1)
168 /* calcuate std dev of latency; we have for n values of "i" that:
170 * avg = (sum val_i) / n
171 * stddev = (sum (val_i - avg)^2) / (n-1)
172 * = (sum (val_i^2 - 2 avg val_i + avg^2) / (n-1)
173 * = (sum (val_i^2) - 2 avg sum (val_i) + n * avg^2) / (n-1)
175 sum_val_i = (double) load->cummulative_delay;
176 n = ((double) load->cummulative_request_count);
178 avgdel = sum_val_i / n;
180 (((double) load->cummulative_squared_delay) - 2.0 * avgdel * sum_val_i +
181 n * avgdel * avgdel) / nm1;
183 stddev = 0.01; /* must have been rounding error or zero; prevent division by zero */
184 /* now calculate load based on how far out we are from
185 * std dev; or if we are below average, simply assume load zero */
186 if (load->runavg_delay < avgdel)
189 load->load = (load->runavg_delay - avgdel) / stddev;
194 * Get the current load.
196 * @param load load handle
197 * @return zero for below-average load, otherwise
198 * number of std. devs we are above average;
199 * 100 if the latest updates were so large
200 * that we could not do proper calculations
203 GNUNET_LOAD_get_load (struct GNUNET_LOAD_Value *load)
205 internal_update (load);
206 calculate_load (load);
212 * Get the average value given to update so far.
214 * @param load load handle
215 * @return zero if update was never called
218 GNUNET_LOAD_get_average (struct GNUNET_LOAD_Value *load)
223 internal_update (load);
224 if (load->cummulative_request_count == 0)
226 n = ((double) load->cummulative_request_count);
227 sum_val_i = (double) load->cummulative_delay;
228 return sum_val_i / n;
233 * Update the current load.
235 * @param load to update
236 * @param data latest measurement value (for example, delay)
239 GNUNET_LOAD_update (struct GNUNET_LOAD_Value *load, uint64_t data)
243 internal_update (load);
244 load->last_update = GNUNET_TIME_absolute_get ();
245 if (data > 64 * 1024)
251 dv = (uint32_t) data;
252 load->cummulative_delay += dv;
253 load->cummulative_squared_delay += dv * dv;
254 load->cummulative_request_count++;
255 load->runavg_delay = ((load->runavg_delay * 7.0) + dv) / 8.0;