src/ats/gnunet-service-ats_normalization.c

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