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