gnunet/src/ats/gnunet-service-ats_normalization.c

/*
   This file is part of GNUnet.
   Copyright (C) 2011-2015 GNUnet e.V.

   GNUnet is free software: you can redistribute it and/or modify it
   under the terms of the GNU Affero General Public License as published
   by the Free Software Foundation, either version 3 of the License,
   or (at your option) any later version.

   GNUnet is distributed in the hope that it will be useful, but
   WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
   Affero General Public License for more details.

   You should have received a copy of the GNU Affero General Public License
   along with this program.  If not, see <http://www.gnu.org/licenses/>.

     SPDX-License-Identifier: AGPL3.0-or-later
 */

/**
 * @file ats/gnunet-service-ats_normalization.c
 * @brief ats service address: management of ATS properties and preferences normalization
 * @author Matthias Wachs
 * @author Christian Grothoff
 */
#include "platform.h"
#include <float.h>
#include "gnunet_ats_service.h"
#include "gnunet-service-ats_addresses.h"
#include "gnunet-service-ats_normalization.h"
#include "gnunet-service-ats_plugins.h"

#define LOG(kind, ...) GNUNET_log_from(kind, "ats-normalization", __VA_ARGS__)


/**
 * Range information for normalization of quality properties.
 */
struct PropertyRange {
  /**
   * Minimum value we see for this property across all addresses.
   */
  struct GNUNET_ATS_Properties min;

  /**
   * Maximum value we see for this property across all addresses.
   */
  struct GNUNET_ATS_Properties max;
};


/**
 * Range information for all quality properties we see.
 */
static struct PropertyRange property_range;


/**
 * Add the value from @a atsi to the running average of the
 * given @a ni quality property.
 *
 * @param current_val the updated value
 * @param ni normalization information to update
 */
static void
update_avg(uint64_t current_val,
           struct GAS_NormalizationInfo *ni)
{
  double sum;
  uint32_t count;
  unsigned int c1;

  ni->atsi_abs[ni->avg_queue_index++] = current_val;
  if (GAS_normalization_queue_length == ni->avg_queue_index)
    ni->avg_queue_index = 0;
  count = 0;
  sum = 0.0;
  for (c1 = 0; c1 < GAS_normalization_queue_length; c1++)
    {
      if (UINT64_MAX != ni->atsi_abs[c1])
        {
          count++;
          sum += (double)ni->atsi_abs[c1];
        }
    }
  if (0 == count)
    ni->avg = current_val; /* must be UINT64_MAX */
  else
    ni->avg = sum / count;
}


/**
 * Function called for all addresses and peers to find the minimum and
 * maximum (averaged) values for a given quality property.  Given
 * those, we can then calculate the normalized score.
 *
 * @param cls the `struct PropertyRange`
 * @param h which peer are we looking at (ignored)
 * @param k the address for that peer
 * @return #GNUNET_OK (continue to iterate)
 */
static int
find_min_max_it(void *cls,
                const struct GNUNET_PeerIdentity *h,
                void *k)
{
  struct PropertyRange *pr = cls;
  const struct ATS_Address *a = k;

  pr->max.utilization_out = GNUNET_MAX(pr->max.utilization_out,
                                       a->properties.utilization_out);
  pr->max.utilization_in = GNUNET_MAX(pr->max.utilization_in,
                                      a->properties.utilization_in);
  pr->max.distance = GNUNET_MAX(pr->max.distance,
                                a->properties.distance);
  pr->max.delay = GNUNET_TIME_relative_max(pr->max.delay,
                                           a->properties.delay);
  pr->min.utilization_out = GNUNET_MIN(pr->min.utilization_out,
                                       a->properties.utilization_out);
  pr->min.utilization_in = GNUNET_MIN(pr->min.utilization_in,
                                      a->properties.utilization_in);
  pr->min.distance = GNUNET_MIN(pr->min.distance,
                                a->properties.distance);
  pr->min.delay = GNUNET_TIME_relative_min(pr->min.delay,
                                           a->properties.delay);
  return GNUNET_OK;
}


/**
 * Compute the normalized value from the given @a ni range
 * data and the average value.
 *
 * @param min minimum value
 * @param max maximum value
 * @param ni normalization information to update
 */
static void
update_norm(uint64_t min,
            uint64_t max,
            struct GAS_NormalizationInfo *ni)
{
  /* max - 2 * min + avg_value / (max - min) */
  if (min < max)
    ni->norm = DEFAULT_REL_QUALITY + (ni->avg - min) / (double)(max - min);
  else
    ni->norm = DEFAULT_REL_QUALITY;
}


/**
 * Normalize the property value for a given address based
 * on the range we know that property values have globally.
 *
 * @param cls NULL
 * @param key which peer are we looking at (ignored)
 * @param value the address for that peer, from where we get
 *            the original value and where we write the
 *            normalized value
 * @return #GNUNET_OK (continue to iterate)
 */
static int
normalize_address(void *cls,
                  const struct GNUNET_PeerIdentity *key,
                  void *value)
{
  struct ATS_Address *address = value;

  update_norm(property_range.min.delay.rel_value_us,
              property_range.max.delay.rel_value_us,
              &address->norm_delay);
  update_norm(property_range.min.distance,
              property_range.max.distance,
              &address->norm_distance);
  update_norm(property_range.min.utilization_in,
              property_range.max.utilization_in,
              &address->norm_utilization_in);
  update_norm(property_range.min.utilization_out,
              property_range.max.utilization_out,
              &address->norm_utilization_out);
  return GNUNET_OK;
}


/**
 * Notify about change in normalized property.
 *
 * @param cls NULL
 * @param key which peer are we looking at (ignored)
 * @param value the address for that peer
 * @return #GNUNET_OK (continue to iterate)
 */
static int
notify_change(void *cls,
              const struct GNUNET_PeerIdentity *key,
              void *value)
{
  struct ATS_Address *address = value;

  GAS_plugin_notify_property_changed(address);
  return GNUNET_OK;
}


/**
 * Initialize property range to the values corresponding
 * to an empty set.
 *
 * @param pr range to initialize
 */
static void
init_range(struct PropertyRange *pr)
{
  memset(pr, 0, sizeof(struct PropertyRange));
  pr->min.utilization_out = UINT32_MAX;
  pr->min.utilization_in = UINT32_MAX;
  pr->min.distance = UINT32_MAX;
  pr->min.delay = GNUNET_TIME_UNIT_FOREVER_REL;
}


/**
 * Update and normalize atsi performance information
 *
 * @param address the address to update
 */
void
GAS_normalization_update_property(struct ATS_Address *address)
{
  const struct GNUNET_ATS_Properties *prop = &address->properties;
  struct PropertyRange range;

  LOG(GNUNET_ERROR_TYPE_DEBUG,
      "Updating properties for peer `%s'\n",
      GNUNET_i2s(&address->peer));
  GAS_plugin_solver_lock();
  update_avg(prop->delay.rel_value_us,
             &address->norm_delay);
  update_avg(prop->distance,
             &address->norm_distance);
  update_avg(prop->utilization_in,
             &address->norm_utilization_in);
  update_avg(prop->utilization_in,
             &address->norm_utilization_out);

  init_range(&range);
  GNUNET_CONTAINER_multipeermap_iterate(GSA_addresses,
                                        &find_min_max_it,
                                        &range);
  if (0 != GNUNET_memcmp(&range,
                         &property_range))
    {
      /* limits changed, (re)normalize all addresses */
      property_range = range;
      GNUNET_CONTAINER_multipeermap_iterate(GSA_addresses,
                                            &normalize_address,
                                            NULL);
      GNUNET_CONTAINER_multipeermap_iterate(GSA_addresses,
                                            &notify_change,
                                            NULL);
    }
  else
    {
      /* renormalize just this one address */
      normalize_address(NULL,
                        &address->peer,
                        address);
      notify_change(NULL,
                    &address->peer,
                    address);
    }
  GAS_plugin_solver_unlock();
}


/**
 * Start the normalization component
 */
void
GAS_normalization_start()
{
  init_range(&property_range);
}


/**
 * Stop the normalization component and free all items
 */
void
GAS_normalization_stop()
{
  /* nothing to do */
}


/* end of gnunet-service-ats_normalization.c */