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 #include "platform.h"
  28 #include <float.h>
  29 #include "gnunet_ats_service.h"
  30 #include "gnunet-service-ats_addresses.h"
  31 #include "gnunet-service-ats_normalization.h"
  32 #include "gnunet-service-ats_plugins.h"
  33
  34 #define LOG(kind,...) GNUNET_log_from (kind, "ats-normalization",__VA_ARGS__)
  35
  36
  37 /**
  38  * Range information for normalization of quality properties.
  39  */
  40 struct PropertyRange
  41 {
  42   /**
  43    * Minimum value we see for this property across all addresses.
  44    */
  45   struct GNUNET_ATS_Properties min;
  46
  47   /**
  48    * Maximum value we see for this property across all addresses.
  49    */
  50   struct GNUNET_ATS_Properties max;
  51 };
  52
  53
  54 /**
  55  * Range information for all quality properties we see.
  56  */
  57 static struct PropertyRange property_range;
  58
  59
  60 /**
  61  * Add the value from @a atsi to the running average of the
  62  * given @a ni quality property.
  63  *
  64  * @param current_val the updated value
  65  * @param ni normalization information to update
  66  */
  67 static void
  68 update_avg (uint64_t current_val,
  69             struct GAS_NormalizationInfo *ni)
  70 {
  71   double sum;
  72   uint32_t count;
  73   unsigned int c1;
  74
  75   ni->atsi_abs[ni->avg_queue_index++] = current_val;
  76   if (GAS_normalization_queue_length == ni->avg_queue_index)
  77     ni->avg_queue_index = 0;
  78   count = 0;
  79   sum = 0.0;
  80   for (c1 = 0; c1 < GAS_normalization_queue_length; c1++)
  81   {
  82     if (UINT64_MAX != ni->atsi_abs[c1])
  83     {
  84       count++;
  85       sum += (double) ni->atsi_abs[c1];
  86     }
  87   }
  88   GNUNET_assert (0 != count);
  89   ni->avg = sum / count;
  90 }
  91
  92
  93 /**
  94  * Function called for all addresses and peers to find the minimum and
  95  * maximum (averaged) values for a given quality property.  Given
  96  * those, we can then calculate the normalized score.
  97  *
  98  * @param cls the `struct PropertyRange`
  99  * @param h which peer are we looking at (ignored)
 100  * @param k the address for that peer
 101  * @return #GNUNET_OK (continue to iterate)
 102  */
 103 static int
 104 find_min_max_it (void *cls,
 105                  const struct GNUNET_PeerIdentity *h,
 106                  void *k)
 107 {
 108   struct PropertyRange *pr = cls;
 109   const struct ATS_Address *a = k;
 110
 111   pr->max.utilization_out = GNUNET_MAX (pr->max.utilization_out,
 112                                         a->properties.utilization_out);
 113   pr->max.utilization_in = GNUNET_MAX (pr->max.utilization_in,
 114                                        a->properties.utilization_in);
 115   pr->max.distance = GNUNET_MAX (pr->max.distance,
 116                                  a->properties.distance);
 117   pr->max.delay = GNUNET_TIME_relative_max (pr->max.delay,
 118                                             a->properties.delay);
 119   pr->min.utilization_out = GNUNET_MIN (pr->min.utilization_out,
 120                                         a->properties.utilization_out);
 121   pr->min.utilization_in = GNUNET_MIN (pr->min.utilization_in,
 122                                        a->properties.utilization_in);
 123   pr->min.distance = GNUNET_MIN (pr->min.distance,
 124                                  a->properties.distance);
 125   pr->min.delay = GNUNET_TIME_relative_min (pr->min.delay,
 126                                             a->properties.delay);
 127   return GNUNET_OK;
 128 }
 129
 130
 131 /**
 132  * Compute the normalized value from the given @a ni range
 133  * data and the average value.
 134  *
 135  * @param min minimum value
 136  * @param max maximum value
 137  * @param ni normalization information to update
 138  */
 139 static void
 140 update_norm (uint64_t min,
 141              uint64_t max,
 142              struct GAS_NormalizationInfo *ni)
 143 {
 144   /* max - 2 * min + avg_value / (max - min) */
 145   if (min < max)
 146     ni->norm = DEFAULT_REL_QUALITY + (ni->avg - min) / (double) (max - min);
 147   else
 148     ni->norm = DEFAULT_REL_QUALITY;
 149 }
 150
 151
 152 /**
 153  * Normalize the property value for a given address based
 154  * on the range we know that property values have globally.
 155  *
 156  * @param cls NULL
 157  * @param key which peer are we looking at (ignored)
 158  * @param value the address for that peer, from where we get
 159  *            the original value and where we write the
 160  *            normalized value
 161  * @return #GNUNET_OK (continue to iterate)
 162  */
 163 static int
 164 normalize_address (void *cls,
 165                    const struct GNUNET_PeerIdentity *key,
 166                    void *value)
 167 {
 168   struct ATS_Address *address = value;
 169
 170   update_norm (property_range.min.delay.rel_value_us,
 171                property_range.max.delay.rel_value_us,
 172                &address->norm_delay);
 173   update_norm (property_range.min.distance,
 174                property_range.max.distance,
 175                &address->norm_distance);
 176   update_norm (property_range.min.utilization_in,
 177                property_range.max.utilization_in,
 178                &address->norm_utilization_in);
 179   update_norm (property_range.min.utilization_out,
 180                property_range.max.utilization_out,
 181                &address->norm_utilization_out);
 182   return GNUNET_OK;
 183 }
 184
 185
 186 /**
 187  * Notify about change in normalized property.
 188  *
 189  * @param cls NULL
 190  * @param key which peer are we looking at (ignored)
 191  * @param value the address for that peer
 192  * @return #GNUNET_OK (continue to iterate)
 193  */
 194 static int
 195 notify_change (void *cls,
 196                const struct GNUNET_PeerIdentity *key,
 197                void *value)
 198 {
 199   struct ATS_Address *address = value;
 200
 201   GAS_plugin_notify_property_changed (address);
 202   return GNUNET_OK;
 203 }
 204
 205
 206 /**
 207  * Initialize property range to the values corresponding
 208  * to an empty set.
 209  *
 210  * @param pr range to initialize
 211  */
 212 static void
 213 init_range (struct PropertyRange *pr)
 214 {
 215   memset (pr, 0, sizeof (struct PropertyRange));
 216   pr->min.utilization_out = UINT32_MAX;
 217   pr->min.utilization_in = UINT32_MAX;
 218   pr->min.distance = UINT32_MAX;
 219   pr->min.delay = GNUNET_TIME_UNIT_FOREVER_REL;
 220 }
 221
 222
 223 /**
 224  * Update and normalize atsi performance information
 225  *
 226  * @param address the address to update
 227  */
 228 void
 229 GAS_normalization_update_property (struct ATS_Address *address)
 230 {
 231   const struct GNUNET_ATS_Properties *prop = &address->properties;
 232   struct PropertyRange range;
 233   int range_changed;
 234
 235   LOG (GNUNET_ERROR_TYPE_DEBUG,
 236        "Updating properties for peer `%s'\n",
 237        GNUNET_i2s (&address->peer));
 238   GAS_plugin_solver_lock ();
 239   update_avg (prop->delay.rel_value_us,
 240               &address->norm_delay);
 241   update_avg (prop->distance,
 242               &address->norm_distance);
 243   update_avg (prop->utilization_in,
 244               &address->norm_utilization_in);
 245   update_avg (prop->utilization_in,
 246               &address->norm_utilization_out);
 247
 248   init_range (&range);
 249   GNUNET_CONTAINER_multipeermap_iterate (GSA_addresses,
 250                                          &find_min_max_it,
 251                                          &range);
 252   if (0 != memcmp (&range,
 253                    &property_range,
 254                    sizeof (struct PropertyRange)))
 255   {
 256     /* limits changed, (re)normalize all addresses */
 257     property_range = range;
 258     range_changed = GNUNET_YES;
 259   }
 260   if (GNUNET_YES == range_changed)
 261     GNUNET_CONTAINER_multipeermap_iterate (GSA_addresses,
 262                                            &normalize_address,
 263                                            NULL);
 264   else
 265     normalize_address (NULL,
 266                        &address->peer,
 267                        address);
 268   /* after all peers have been updated, notify about changes */
 269   if (GNUNET_YES == range_changed)
 270     GNUNET_CONTAINER_multipeermap_iterate (GSA_addresses,
 271                                            &notify_change,
 272                                            NULL);
 273   else
 274     notify_change (NULL,
 275                    &address->peer,
 276                    address);
 277   GAS_plugin_solver_unlock ();
 278 }
 279
 280
 281 /**
 282  * Start the normalization component
 283  */
 284 void
 285 GAS_normalization_start ()
 286 {
 287   init_range (&property_range);
 288 }
 289
 290
 291 /**
 292  * Stop the normalization component and free all items
 293  */
 294 void
 295 GAS_normalization_stop ()
 296 {
 297   /* nothing to do */
 298 }
 299
 300
 301 /* end of gnunet-service-ats_normalization.c */