src/ats/gnunet-service-ats_normalization.c

   1 /*
   2  This file is part of GNUnet.
   3  Copyright (C) 2011-2015 GNUnet e.V.
   4
   5  GNUnet is free software: you can redistribute it and/or modify it
   6  under the terms of the GNU Affero General Public License as published
   7  by the Free Software Foundation, either version 3 of the License,
   8  or (at your 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  Affero General Public License for more details.
  14
  15  You should have received a copy of the GNU Affero General Public License
  16  along with this program.  If not, see <http://www.gnu.org/licenses/>.
  17
  18      SPDX-License-Identifier: AGPL3.0-or-later
  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   if (0 == count)
  89     ni->avg = current_val; /* must be UINT64_MAX */
  90   else
  91     ni->avg = sum / count;
  92 }
  93
  94
  95 /**
  96  * Function called for all addresses and peers to find the minimum and
  97  * maximum (averaged) values for a given quality property.  Given
  98  * those, we can then calculate the normalized score.
  99  *
 100  * @param cls the `struct PropertyRange`
 101  * @param h which peer are we looking at (ignored)
 102  * @param k the address for that peer
 103  * @return #GNUNET_OK (continue to iterate)
 104  */
 105 static int
 106 find_min_max_it (void *cls,
 107                  const struct GNUNET_PeerIdentity *h,
 108                  void *k)
 109 {
 110   struct PropertyRange *pr = cls;
 111   const struct ATS_Address *a = k;
 112
 113   pr->max.utilization_out = GNUNET_MAX (pr->max.utilization_out,
 114                                         a->properties.utilization_out);
 115   pr->max.utilization_in = GNUNET_MAX (pr->max.utilization_in,
 116                                        a->properties.utilization_in);
 117   pr->max.distance = GNUNET_MAX (pr->max.distance,
 118                                  a->properties.distance);
 119   pr->max.delay = GNUNET_TIME_relative_max (pr->max.delay,
 120                                             a->properties.delay);
 121   pr->min.utilization_out = GNUNET_MIN (pr->min.utilization_out,
 122                                         a->properties.utilization_out);
 123   pr->min.utilization_in = GNUNET_MIN (pr->min.utilization_in,
 124                                        a->properties.utilization_in);
 125   pr->min.distance = GNUNET_MIN (pr->min.distance,
 126                                  a->properties.distance);
 127   pr->min.delay = GNUNET_TIME_relative_min (pr->min.delay,
 128                                             a->properties.delay);
 129   return GNUNET_OK;
 130 }
 131
 132
 133 /**
 134  * Compute the normalized value from the given @a ni range
 135  * data and the average value.
 136  *
 137  * @param min minimum value
 138  * @param max maximum value
 139  * @param ni normalization information to update
 140  */
 141 static void
 142 update_norm (uint64_t min,
 143              uint64_t max,
 144              struct GAS_NormalizationInfo *ni)
 145 {
 146   /* max - 2 * min + avg_value / (max - min) */
 147   if (min < max)
 148     ni->norm = DEFAULT_REL_QUALITY + (ni->avg - min) / (double) (max - min);
 149   else
 150     ni->norm = DEFAULT_REL_QUALITY;
 151 }
 152
 153
 154 /**
 155  * Normalize the property value for a given address based
 156  * on the range we know that property values have globally.
 157  *
 158  * @param cls NULL
 159  * @param key which peer are we looking at (ignored)
 160  * @param value the address for that peer, from where we get
 161  *            the original value and where we write the
 162  *            normalized value
 163  * @return #GNUNET_OK (continue to iterate)
 164  */
 165 static int
 166 normalize_address (void *cls,
 167                    const struct GNUNET_PeerIdentity *key,
 168                    void *value)
 169 {
 170   struct ATS_Address *address = value;
 171
 172   update_norm (property_range.min.delay.rel_value_us,
 173                property_range.max.delay.rel_value_us,
 174                &address->norm_delay);
 175   update_norm (property_range.min.distance,
 176                property_range.max.distance,
 177                &address->norm_distance);
 178   update_norm (property_range.min.utilization_in,
 179                property_range.max.utilization_in,
 180                &address->norm_utilization_in);
 181   update_norm (property_range.min.utilization_out,
 182                property_range.max.utilization_out,
 183                &address->norm_utilization_out);
 184   return GNUNET_OK;
 185 }
 186
 187
 188 /**
 189  * Notify about change in normalized property.
 190  *
 191  * @param cls NULL
 192  * @param key which peer are we looking at (ignored)
 193  * @param value the address for that peer
 194  * @return #GNUNET_OK (continue to iterate)
 195  */
 196 static int
 197 notify_change (void *cls,
 198                const struct GNUNET_PeerIdentity *key,
 199                void *value)
 200 {
 201   struct ATS_Address *address = value;
 202
 203   GAS_plugin_notify_property_changed (address);
 204   return GNUNET_OK;
 205 }
 206
 207
 208 /**
 209  * Initialize property range to the values corresponding
 210  * to an empty set.
 211  *
 212  * @param pr range to initialize
 213  */
 214 static void
 215 init_range (struct PropertyRange *pr)
 216 {
 217   memset (pr, 0, sizeof (struct PropertyRange));
 218   pr->min.utilization_out = UINT32_MAX;
 219   pr->min.utilization_in = UINT32_MAX;
 220   pr->min.distance = UINT32_MAX;
 221   pr->min.delay = GNUNET_TIME_UNIT_FOREVER_REL;
 222 }
 223
 224
 225 /**
 226  * Update and normalize atsi performance information
 227  *
 228  * @param address the address to update
 229  */
 230 void
 231 GAS_normalization_update_property (struct ATS_Address *address)
 232 {
 233   const struct GNUNET_ATS_Properties *prop = &address->properties;
 234   struct PropertyRange range;
 235
 236   LOG (GNUNET_ERROR_TYPE_DEBUG,
 237        "Updating properties for peer `%s'\n",
 238        GNUNET_i2s (&address->peer));
 239   GAS_plugin_solver_lock ();
 240   update_avg (prop->delay.rel_value_us,
 241               &address->norm_delay);
 242   update_avg (prop->distance,
 243               &address->norm_distance);
 244   update_avg (prop->utilization_in,
 245               &address->norm_utilization_in);
 246   update_avg (prop->utilization_in,
 247               &address->norm_utilization_out);
 248
 249   init_range (&range);
 250   GNUNET_CONTAINER_multipeermap_iterate (GSA_addresses,
 251                                          &find_min_max_it,
 252                                          &range);
 253   if (0 != memcmp (&range,
 254                    &property_range,
 255                    sizeof (struct PropertyRange)))
 256   {
 257     /* limits changed, (re)normalize all addresses */
 258     property_range = range;
 259     GNUNET_CONTAINER_multipeermap_iterate (GSA_addresses,
 260                                            &normalize_address,
 261                                            NULL);
 262     GNUNET_CONTAINER_multipeermap_iterate (GSA_addresses,
 263                                            &notify_change,
 264                                            NULL);
 265   }
 266   else
 267   {
 268     /* renormalize just this one address */
 269     normalize_address (NULL,
 270                        &address->peer,
 271                        address);
 272     notify_change (NULL,
 273                    &address->peer,
 274                    address);
 275   }
 276   GAS_plugin_solver_unlock ();
 277 }
 278
 279
 280 /**
 281  * Start the normalization component
 282  */
 283 void
 284 GAS_normalization_start ()
 285 {
 286   init_range (&property_range);
 287 }
 288
 289
 290 /**
 291  * Stop the normalization component and free all items
 292  */
 293 void
 294 GAS_normalization_stop ()
 295 {
 296   /* nothing to do */
 297 }
 298
 299
 300 /* end of gnunet-service-ats_normalization.c */