src/ats/gnunet-service-ats_normalization.c

   1 /*
   2  This file is part of GNUnet.
   3  (C) 2011-2015 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 3, 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 ats/gnunet-service-ats_normalization.c
  23  * @brief ats service address: management of ATS properties and preferences normalization
  24  * @author Matthias Wachs
  25  * @author Christian Grothoff
  26  *
  27  * FIXME: rename to 'properties'!?
  28  */
  29 #include "platform.h"
  30 #include "gnunet_ats_service.h"
  31 #include "gnunet-service-ats_addresses.h"
  32 #include "gnunet-service-ats_normalization.h"
  33 #include "gnunet-service-ats_plugins.h"
  34
  35 #define LOG(kind,...) GNUNET_log_from (kind, "ats-normalization",__VA_ARGS__)
  36
  37
  38 /**
  39  * Quality Normalization
  40  */
  41 struct Property
  42 {
  43   /**
  44    * Index into the properties array.
  45    */
  46   uint32_t prop_type;
  47
  48   /**
  49    * Corresponding enum value.  FIXME: type?
  50    */
  51   uint32_t atsi_type;
  52
  53   /**
  54    * Minimum value we see for this property across all addresses.
  55    */
  56   uint32_t min;
  57
  58   /**
  59    * Maximum value we see for this property across all addresses.
  60    */
  61   uint32_t max;
  62 };
  63
  64
  65 /**
  66  * Range information for all properties we see.
  67  */
  68 static struct Property properties[GNUNET_ATS_QualityPropertiesCount];
  69
  70
  71 /**
  72  * Get the normalized properties values for a specific peer or
  73  * the default values if no normalized values are available.
  74  *
  75  * @param cls ignored
  76  * @param address the address
  77  * @return pointer to the values, can be indexed with GNUNET_ATS_PreferenceKind,
  78  * default preferences if peer does not exist
  79  */
  80 const double *
  81 GAS_normalization_get_properties (void *cls,
  82                                   const struct ATS_Address *address)
  83 {
  84   static double norm_values[GNUNET_ATS_QualityPropertiesCount];
  85   unsigned int i;
  86
  87   for (i = 0; i < GNUNET_ATS_QualityPropertiesCount; i++)
  88   {
  89     if ((address->atsin[i].norm >= 1.0) && (address->atsin[i].norm <= 2.0))
  90       norm_values[i] = address->atsin[i].norm;
  91     else
  92       norm_values[i] = DEFAULT_REL_QUALITY;
  93   }
  94   return norm_values;
  95 }
  96
  97
  98 /**
  99  * Normalize a specific ATS type with the values in queue.
 100  *
 101  * @param address the address
 102  * @param atsi the ats information
 103  * @return the new average or GNUNET_ATS_VALUE_UNDEFINED
 104  */
 105 static uint32_t
 106 property_average (struct ATS_Address *address,
 107                   const struct GNUNET_ATS_Information *atsi)
 108 {
 109   struct GAS_NormalizationInfo *ni;
 110   uint32_t current_type;
 111   uint32_t current_val;
 112   uint32_t res;
 113   uint64_t sum;
 114   uint32_t count;
 115   unsigned int c1;
 116   unsigned int index;
 117   unsigned int props[] = GNUNET_ATS_QualityProperties;
 118
 119   /* Average the values of this property */
 120   current_type = ntohl (atsi->type);
 121   current_val = ntohl (atsi->value);
 122
 123   for (c1 = 0; c1 < GNUNET_ATS_QualityPropertiesCount; c1++)
 124   {
 125     if (current_type == props[c1])
 126       break;
 127   }
 128   if (c1 == GNUNET_ATS_QualityPropertiesCount)
 129   {
 130     GNUNET_break(0);
 131     return GNUNET_ATS_VALUE_UNDEFINED;
 132   }
 133   index = c1;
 134
 135   ni = &address->atsin[index];
 136   ni->atsi_abs[ni->avg_queue_index] = current_val;
 137   ni->avg_queue_index++;
 138   if (GAS_normalization_queue_length == ni->avg_queue_index)
 139     ni->avg_queue_index = 0;
 140
 141   count = 0;
 142   sum = 0;
 143   for (c1 = 0; c1 < GAS_normalization_queue_length; c1++)
 144   {
 145     if (GNUNET_ATS_VALUE_UNDEFINED != ni->atsi_abs[c1])
 146     {
 147       count++;
 148       if (GNUNET_ATS_VALUE_UNDEFINED > (sum + ni->atsi_abs[c1]))
 149         sum += ni->atsi_abs[c1];
 150       else
 151       {
 152         sum = GNUNET_ATS_VALUE_UNDEFINED - 1;
 153         GNUNET_break(0);
 154       }
 155     }
 156   }
 157   GNUNET_assert(0 != count);
 158   res = sum / count;
 159   LOG(GNUNET_ERROR_TYPE_DEBUG,
 160       "New average of `%s' created by adding %u from %u elements: %u\n",
 161       GNUNET_ATS_print_property_type (current_type),
 162       current_val,
 163       count,
 164       res,
 165       sum);
 166   ni->avg = res;
 167   return res;
 168 }
 169
 170
 171 /**
 172  * Closure for #find_min_max_it().
 173  */
 174 struct FindMinMaxCtx
 175 {
 176   /**
 177    * Property we are looking for.
 178    */
 179   struct Property *p;
 180
 181   /**
 182    * Set to mimimum value observed.
 183    */
 184   uint32_t min;
 185
 186   /**
 187    * Set to maximum value observed.
 188    */
 189   uint32_t max;
 190 };
 191
 192
 193 /**
 194  * Function called on X to find the minimum and maximum
 195  * values for a given property.
 196  *
 197  * @param cls the `struct FindMinMaxCtx`
 198  * @param h which peer are we looking at (ignored)
 199  * @param k the address for that peer
 200  * @return #GNUNET_OK (continue to iterate)
 201  */
 202 static int
 203 find_min_max_it (void *cls,
 204                  const struct GNUNET_PeerIdentity *h,
 205                  void *k)
 206 {
 207   struct FindMinMaxCtx *find_res = cls;
 208   const struct ATS_Address *a = k;
 209
 210   find_res->max = GNUNET_MAX (find_res->max,
 211                               a->atsin[find_res->p->prop_type].avg);
 212   find_res->min = GNUNET_MIN (find_res->min,
 213                               a->atsin[find_res->p->prop_type].avg);
 214   return GNUNET_OK;
 215 }
 216
 217
 218 /**
 219  * Normalize the property value for a given address based
 220  * on the range we know that property value has globally.
 221  *
 222  * @param cls the `struct Property` with details on the
 223  *            property and its global range
 224  * @param h which peer are we looking at (ignored)
 225  * @param k the address for that peer, from where we get
 226  *            the original value and where we write the
 227  *            normalized value
 228  * @return #GNUNET_OK (continue to iterate)
 229  */
 230 static int
 231 normalize_address (void *cls,
 232                    const struct GNUNET_PeerIdentity *h,
 233                    void *k)
 234 {
 235   struct Property *p = cls;
 236   struct ATS_Address *address = k;
 237   double delta;
 238   double backup;
 239   uint32_t avg_value;
 240
 241   backup = address->atsin[p->prop_type].norm;
 242   avg_value = address->atsin[p->prop_type].avg;
 243   delta = p->max - p->min;
 244   /* max - 2 * min + avg_value / max - min */
 245   if (0 != delta)
 246     address->atsin[p->prop_type].norm = (delta + (avg_value - p->min)) / (delta);
 247   else
 248     address->atsin[p->prop_type].norm = DEFAULT_REL_QUALITY;
 249
 250   if (backup == address->atsin[p->prop_type].norm)
 251     return GNUNET_OK;
 252
 253   LOG (GNUNET_ERROR_TYPE_DEBUG,
 254        "Normalize `%s' address %p's '%s' with value %u to range [%u..%u] = %.3f\n",
 255        GNUNET_i2s (&address->peer), address,
 256        GNUNET_ATS_print_property_type (p->atsi_type),
 257        address->atsin[p->prop_type].avg, p->min, p->max,
 258        address->atsin[p->prop_type].norm);
 259   GAS_normalized_property_changed (address,
 260                                    p->atsi_type,
 261                                    address->atsin[p->prop_type].norm);
 262   return GNUNET_OK;
 263 }
 264
 265
 266 /**
 267  * Normalize @a avg_value to a range of values between [1.0, 2.0]
 268  * based on min/max values currently known.
 269  *
 270  * @param p the property
 271  * @param address the address
 272  * @param avg_value the value to normalize
 273  */
 274 static void
 275 property_normalize (struct Property *p,
 276                     struct ATS_Address *address,
 277                     uint32_t avg_value)
 278 {
 279   struct FindMinMaxCtx find_ctx;
 280   int addr_count;
 281   int limits_changed;
 282
 283   find_ctx.p = p;
 284   find_ctx.max = 0;
 285   find_ctx.min = UINT32_MAX;
 286   addr_count = GNUNET_CONTAINER_multipeermap_iterate (GSA_addresses,
 287                                                       &find_min_max_it,
 288                                                       &find_ctx);
 289   if (0 == addr_count)
 290   {
 291     GNUNET_break(0);
 292     return;
 293   }
 294
 295   limits_changed = GNUNET_NO;
 296   if (find_ctx.max != p->max)
 297   {
 298     LOG (GNUNET_ERROR_TYPE_DEBUG,
 299          "Normalizing %s: new maximum %u -> recalculate all values\n",
 300          GNUNET_ATS_print_property_type (p->atsi_type),
 301          find_ctx.max);
 302     p->max = find_ctx.max;
 303     limits_changed = GNUNET_YES;
 304   }
 305
 306   if ((find_ctx.min != p->min) && (find_ctx.min < p->max))
 307   {
 308     LOG (GNUNET_ERROR_TYPE_DEBUG,
 309          "Normalizing %s: new minimum %u -> recalculate all values\n",
 310          GNUNET_ATS_print_property_type (p->atsi_type),
 311          find_ctx.min,
 312          find_ctx.max);
 313     p->min = find_ctx.min;
 314     limits_changed = GNUNET_YES;
 315   }
 316   else if (find_ctx.min == p->max)
 317   {
 318     /* Only one value, so minimum has to be 0 */
 319     p->min = 0;
 320   }
 321
 322   /* Normalize the values of this property */
 323   if (GNUNET_NO == limits_changed)
 324   {
 325     /* normalize just this  address */
 326     normalize_address (p,
 327                        &address->peer,
 328                        address);
 329   }
 330   else
 331   {
 332     /* limits changed, normalize all addresses */
 333     GNUNET_CONTAINER_multipeermap_iterate (GSA_addresses,
 334                                            &normalize_address,
 335                                            p);
 336   }
 337 }
 338
 339
 340 /**
 341  * Update and normalize atsi performance information
 342  *
 343  * @param address the address to update
 344  * @param atsi the array of performance information
 345  * @param atsi_count the number of atsi information in the array
 346  */
 347 void
 348 GAS_normalization_normalize_property (struct ATS_Address *address,
 349                                       const struct GNUNET_ATS_Information *atsi,
 350                                       uint32_t atsi_count)
 351 {
 352   struct Property *cur_prop;
 353   int c1;
 354   int c2;
 355   uint32_t current_type;
 356   uint32_t current_val;
 357   unsigned int existing_properties[] = GNUNET_ATS_QualityProperties;
 358
 359   LOG (GNUNET_ERROR_TYPE_DEBUG,
 360        "Updating %u elements for peer `%s'\n",
 361        atsi_count,
 362        GNUNET_i2s (&address->peer));
 363
 364   for (c1 = 0; c1 < atsi_count; c1++)
 365   {
 366     current_type = ntohl (atsi[c1].type);
 367
 368     for (c2 = 0; c2 < GNUNET_ATS_QualityPropertiesCount; c2++)
 369     {
 370       /* Check if type is valid */
 371       if (current_type == existing_properties[c2])
 372         break;
 373     }
 374     if (GNUNET_ATS_QualityPropertiesCount == c2)
 375     {
 376       /* Invalid property, continue with next element */
 377       continue;
 378     }
 379     /* Averaging */
 380     current_val = property_average (address, &atsi[c1]);
 381     if (GNUNET_ATS_VALUE_UNDEFINED == current_val)
 382     {
 383       GNUNET_break(0);
 384       continue;
 385     }
 386
 387     /* Normalizing */
 388     /* Check min, max */
 389     cur_prop = &properties[c2];
 390     property_normalize (cur_prop,
 391                         address,
 392                         current_val);
 393   }
 394 }
 395
 396
 397 /**
 398  * Start the normalization component
 399  */
 400 void
 401 GAS_normalization_start ()
 402 {
 403   unsigned int c1;
 404   unsigned int existing_properties[] = GNUNET_ATS_QualityProperties;
 405
 406   for (c1 = 0; c1 < GNUNET_ATS_QualityPropertiesCount; c1++)
 407   {
 408     properties[c1].prop_type = c1;
 409     properties[c1].atsi_type = existing_properties[c1];
 410     properties[c1].min = UINT32_MAX;
 411     properties[c1].max = 0;
 412   }
 413 }
 414
 415
 416 /**
 417  * Stop the normalization component and free all items
 418  */
 419 void
 420 GAS_normalization_stop ()
 421 {
 422   /* nothing to do */
 423 }
 424
 425
 426 /* end of gnunet-service-ats_normalization.c */