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
  19 /**
  20  * @file ats/gnunet-service-ats_normalization.c
  21  * @brief ats service address: management of ATS properties and preferences normalization
  22  * @author Matthias Wachs
  23  * @author Christian Grothoff
  24  */
  25 #include "platform.h"
  26 #include <float.h>
  27 #include "gnunet_ats_service.h"
  28 #include "gnunet-service-ats_addresses.h"
  29 #include "gnunet-service-ats_normalization.h"
  30 #include "gnunet-service-ats_plugins.h"
  31
  32 #define LOG(kind,...) GNUNET_log_from (kind, "ats-normalization",__VA_ARGS__)
  33
  34
  35 /**
  36  * Range information for normalization of quality properties.
  37  */
  38 struct PropertyRange
  39 {
  40   /**
  41    * Minimum value we see for this property across all addresses.
  42    */
  43   struct GNUNET_ATS_Properties min;
  44
  45   /**
  46    * Maximum value we see for this property across all addresses.
  47    */
  48   struct GNUNET_ATS_Properties max;
  49 };
  50
  51
  52 /**
  53  * Range information for all quality properties we see.
  54  */
  55 static struct PropertyRange property_range;
  56
  57
  58 /**
  59  * Add the value from @a atsi to the running average of the
  60  * given @a ni quality property.
  61  *
  62  * @param current_val the updated value
  63  * @param ni normalization information to update
  64  */
  65 static void
  66 update_avg (uint64_t current_val,
  67             struct GAS_NormalizationInfo *ni)
  68 {
  69   double sum;
  70   uint32_t count;
  71   unsigned int c1;
  72
  73   ni->atsi_abs[ni->avg_queue_index++] = current_val;
  74   if (GAS_normalization_queue_length == ni->avg_queue_index)
  75     ni->avg_queue_index = 0;
  76   count = 0;
  77   sum = 0.0;
  78   for (c1 = 0; c1 < GAS_normalization_queue_length; c1++)
  79   {
  80     if (UINT64_MAX != ni->atsi_abs[c1])
  81     {
  82       count++;
  83       sum += (double) ni->atsi_abs[c1];
  84     }
  85   }
  86   if (0 == count)
  87     ni->avg = current_val; /* must be UINT64_MAX */
  88   else
  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
 234   LOG (GNUNET_ERROR_TYPE_DEBUG,
 235        "Updating properties for peer `%s'\n",
 236        GNUNET_i2s (&address->peer));
 237   GAS_plugin_solver_lock ();
 238   update_avg (prop->delay.rel_value_us,
 239               &address->norm_delay);
 240   update_avg (prop->distance,
 241               &address->norm_distance);
 242   update_avg (prop->utilization_in,
 243               &address->norm_utilization_in);
 244   update_avg (prop->utilization_in,
 245               &address->norm_utilization_out);
 246
 247   init_range (&range);
 248   GNUNET_CONTAINER_multipeermap_iterate (GSA_addresses,
 249                                          &find_min_max_it,
 250                                          &range);
 251   if (0 != memcmp (&range,
 252                    &property_range,
 253                    sizeof (struct PropertyRange)))
 254   {
 255     /* limits changed, (re)normalize all addresses */
 256     property_range = range;
 257     GNUNET_CONTAINER_multipeermap_iterate (GSA_addresses,
 258                                            &normalize_address,
 259                                            NULL);
 260     GNUNET_CONTAINER_multipeermap_iterate (GSA_addresses,
 261                                            &notify_change,
 262                                            NULL);
 263   }
 264   else
 265   {
 266     /* renormalize just this one address */
 267     normalize_address (NULL,
 268                        &address->peer,
 269                        address);
 270     notify_change (NULL,
 271                    &address->peer,
 272                    address);
 273   }
 274   GAS_plugin_solver_unlock ();
 275 }
 276
 277
 278 /**
 279  * Start the normalization component
 280  */
 281 void
 282 GAS_normalization_start ()
 283 {
 284   init_range (&property_range);
 285 }
 286
 287
 288 /**
 289  * Stop the normalization component and free all items
 290  */
 291 void
 292 GAS_normalization_stop ()
 293 {
 294   /* nothing to do */
 295 }
 296
 297
 298 /* end of gnunet-service-ats_normalization.c */