X-Git-Url: https://git.librecmc.org/?a=blobdiff_plain;f=src%2Fats%2Fgnunet-service-ats_normalization.c;h=e70be018e03057f22d2e807f4195224d1dc1d1c3;hb=e871f8368c8a1f0867f68f656875e4c37c26f298;hp=23b7b0cb7a09a25d4e712003d33fcdffe649bced;hpb=6115a1150c65bd4a33ed61c6e96594c4a73d86ac;p=oweals%2Fgnunet.git
diff --git a/src/ats/gnunet-service-ats_normalization.c b/src/ats/gnunet-service-ats_normalization.c
index 23b7b0cb7..e70be018e 100644
--- a/src/ats/gnunet-service-ats_normalization.c
+++ b/src/ats/gnunet-service-ats_normalization.c
@@ -1,21 +1,19 @@
/*
This file is part of GNUnet.
- Copyright (C) 2011-2015 Christian Grothoff (and other contributing authors)
+ 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 General Public License as published
- by the Free Software Foundation; either version 3, or (at your
- option) any later version.
+ 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
- General Public License for more details.
+ Affero General Public License for more details.
- You should have received a copy of the GNU General Public License
- along with GNUnet; see the file COPYING. If not, write to the
- Free Software Foundation, Inc., 59 Temple Place - Suite 330,
- Boston, MA 02111-1307, USA.
+ You should have received a copy of the GNU Affero General Public License
+ along with this program. If not, see .
*/
/**
@@ -23,10 +21,9 @@
* @brief ats service address: management of ATS properties and preferences normalization
* @author Matthias Wachs
* @author Christian Grothoff
- *
- * FIXME: rename to 'properties'!? merge with addresses!?
*/
#include "platform.h"
+#include
#include "gnunet_ats_service.h"
#include "gnunet-service-ats_addresses.h"
#include "gnunet-service-ats_normalization.h"
@@ -36,164 +33,69 @@
/**
- * Quality Normalization
+ * Range information for normalization of quality properties.
*/
-struct Property
+struct PropertyRange
{
- /**
- * Index into the properties array.
- */
- uint32_t prop_type;
-
- /**
- * Corresponding enum value. FIXME: type?
- */
- uint32_t atsi_type;
-
/**
* Minimum value we see for this property across all addresses.
*/
- uint32_t min;
+ struct GNUNET_ATS_Properties min;
/**
* Maximum value we see for this property across all addresses.
*/
- uint32_t max;
+ struct GNUNET_ATS_Properties max;
};
/**
- * Range information for all properties we see.
+ * Range information for all quality properties we see.
*/
-static struct Property properties[GNUNET_ATS_QualityPropertiesCount];
+static struct PropertyRange property_range;
/**
- * Get the normalized properties values for a specific peer or
- * the default values if no normalized values are available.
+ * Add the value from @a atsi to the running average of the
+ * given @a ni quality property.
*
- * @param cls ignored
- * @param address the address
- * @return pointer to the values, can be indexed with GNUNET_ATS_PreferenceKind
+ * @param current_val the updated value
+ * @param ni normalization information to update
*/
-const double *
-GAS_normalization_get_properties (void *cls,
- const struct ATS_Address *address)
-{
- static double norm_values[GNUNET_ATS_QualityPropertiesCount];
- unsigned int i;
-
- for (i = 0; i < GNUNET_ATS_QualityPropertiesCount; i++)
- {
- if ((address->atsin[i].norm >= 1.0) && (address->atsin[i].norm <= 2.0))
- norm_values[i] = address->atsin[i].norm;
- else
- norm_values[i] = DEFAULT_REL_QUALITY;
- }
- return norm_values;
-}
-
-
-/**
- * Normalize a specific ATS type with the values in queue.
- *
- * @param address the address
- * @param atsi the ats information
- * @return the new average or #GNUNET_ATS_VALUE_UNDEFINED
- */
-static uint32_t
-property_average (struct ATS_Address *address,
- const struct GNUNET_ATS_Information *atsi)
+static void
+update_avg (uint64_t current_val,
+ struct GAS_NormalizationInfo *ni)
{
- struct GAS_NormalizationInfo *ni;
- uint32_t current_type;
- uint32_t current_val;
- uint32_t res;
- uint64_t sum;
+ double sum;
uint32_t count;
unsigned int c1;
- unsigned int index;
- unsigned int props[] = GNUNET_ATS_QualityProperties;
-
- /* Average the values of this property */
- current_type = ntohl (atsi->type);
- current_val = ntohl (atsi->value);
- for (c1 = 0; c1 < GNUNET_ATS_QualityPropertiesCount; c1++)
- {
- if (current_type == props[c1])
- break;
- }
- if (c1 == GNUNET_ATS_QualityPropertiesCount)
- {
- GNUNET_break(0);
- return GNUNET_ATS_VALUE_UNDEFINED;
- }
- index = c1;
-
- ni = &address->atsin[index];
- ni->atsi_abs[ni->avg_queue_index] = current_val;
- ni->avg_queue_index++;
+ 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;
+ sum = 0.0;
for (c1 = 0; c1 < GAS_normalization_queue_length; c1++)
{
- if (GNUNET_ATS_VALUE_UNDEFINED != ni->atsi_abs[c1])
+ if (UINT64_MAX != ni->atsi_abs[c1])
{
count++;
- if (GNUNET_ATS_VALUE_UNDEFINED > (sum + ni->atsi_abs[c1]))
- sum += ni->atsi_abs[c1];
- else
- {
- sum = GNUNET_ATS_VALUE_UNDEFINED - 1;
- GNUNET_break(0);
- }
+ sum += (double) ni->atsi_abs[c1];
}
}
- GNUNET_assert(0 != count);
- res = sum / count;
- LOG(GNUNET_ERROR_TYPE_DEBUG,
- "New average of `%s' created by adding %u from %u elements: %u\n",
- GNUNET_ATS_print_property_type (current_type),
- current_val,
- count,
- res,
- sum);
- ni->avg = res;
- return res;
+ if (0 == count)
+ ni->avg = current_val; /* must be UINT64_MAX */
+ else
+ ni->avg = sum / count;
}
/**
- * Closure for #find_min_max_it().
- */
-struct FindMinMaxCtx
-{
- /**
- * Property we are looking for.
- */
- struct Property *p;
-
- /**
- * Set to mimimum value observed.
- */
- uint32_t min;
-
- /**
- * Set to maximum value observed.
- */
- uint32_t max;
-};
-
-
-/**
- * Function called on X to find the minimum and maximum
- * values for a given property.
+ * 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 FindMinMaxCtx`
+ * @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)
@@ -203,139 +105,118 @@ find_min_max_it (void *cls,
const struct GNUNET_PeerIdentity *h,
void *k)
{
- struct FindMinMaxCtx *find_res = cls;
+ struct PropertyRange *pr = cls;
const struct ATS_Address *a = k;
- find_res->max = GNUNET_MAX (find_res->max,
- a->atsin[find_res->p->prop_type].avg);
- find_res->min = GNUNET_MIN (find_res->min,
- a->atsin[find_res->p->prop_type].avg);
+ 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 value has globally.
+ * on the range we know that property values have globally.
*
- * @param cls the `struct Property` with details on the
- * property and its global range
- * @param h which peer are we looking at (ignored)
- * @param k the address for that peer, from where we get
+ * @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 *h,
- void *k)
+ const struct GNUNET_PeerIdentity *key,
+ void *value)
{
- struct Property *p = cls;
- struct ATS_Address *address = k;
- double delta;
- double backup;
- uint32_t avg_value;
-
- backup = address->atsin[p->prop_type].norm;
- avg_value = address->atsin[p->prop_type].avg;
- delta = p->max - p->min;
- /* max - 2 * min + avg_value / max - min */
- if (0 != delta)
- address->atsin[p->prop_type].norm = (delta + (avg_value - p->min)) / (delta);
- else
- address->atsin[p->prop_type].norm = DEFAULT_REL_QUALITY;
-
- if (backup == address->atsin[p->prop_type].norm)
- return GNUNET_OK;
-
- LOG (GNUNET_ERROR_TYPE_DEBUG,
- "Normalize `%s' address %p's '%s' with value %u to range [%u..%u] = %.3f\n",
- GNUNET_i2s (&address->peer),
- address,
- GNUNET_ATS_print_property_type (p->atsi_type),
- address->atsin[p->prop_type].avg,
- p->min,
- p->max,
- address->atsin[p->prop_type].norm);
- GAS_normalized_property_changed (address,
- p->atsi_type,
- address->atsin[p->prop_type].norm);
+ 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;
}
/**
- * Normalize @a avg_value to a range of values between [1.0, 2.0]
- * based on min/max values currently known.
+ * Notify about change in normalized property.
*
- * @param p the property
- * @param address the address
- * @param avg_value the value to normalize
+ * @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 void
-property_normalize (struct Property *p,
- struct ATS_Address *address,
- uint32_t avg_value)
+static int
+notify_change (void *cls,
+ const struct GNUNET_PeerIdentity *key,
+ void *value)
{
- struct FindMinMaxCtx find_ctx;
- int addr_count;
- int limits_changed;
-
- find_ctx.p = p;
- find_ctx.max = 0;
- find_ctx.min = UINT32_MAX;
- addr_count = GNUNET_CONTAINER_multipeermap_iterate (GSA_addresses,
- &find_min_max_it,
- &find_ctx);
- if (0 == addr_count)
- {
- GNUNET_break(0);
- return;
- }
+ struct ATS_Address *address = value;
- limits_changed = GNUNET_NO;
- if (find_ctx.max != p->max)
- {
- LOG (GNUNET_ERROR_TYPE_DEBUG,
- "Normalizing %s: new maximum %u -> recalculate all values\n",
- GNUNET_ATS_print_property_type (p->atsi_type),
- find_ctx.max);
- p->max = find_ctx.max;
- limits_changed = GNUNET_YES;
- }
+ GAS_plugin_notify_property_changed (address);
+ return GNUNET_OK;
+}
- if ((find_ctx.min != p->min) && (find_ctx.min < p->max))
- {
- LOG (GNUNET_ERROR_TYPE_DEBUG,
- "Normalizing %s: new minimum %u -> recalculate all values\n",
- GNUNET_ATS_print_property_type (p->atsi_type),
- find_ctx.min,
- find_ctx.max);
- p->min = find_ctx.min;
- limits_changed = GNUNET_YES;
- }
- else if (find_ctx.min == p->max)
- {
- /* Only one value, so minimum has to be 0 */
- p->min = 0;
- }
- /* Normalize the values of this property */
- if (GNUNET_NO == limits_changed)
- {
- /* normalize just this address */
- normalize_address (p,
- &address->peer,
- address);
- }
- else
- {
- /* limits changed, normalize all addresses */
- GNUNET_CONTAINER_multipeermap_iterate (GSA_addresses,
- &normalize_address,
- p);
- }
+/**
+ * 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;
}
@@ -343,55 +224,52 @@ property_normalize (struct Property *p,
* Update and normalize atsi performance information
*
* @param address the address to update
- * @param atsi the array of performance information
- * @param atsi_count the number of atsi information in the array
*/
void
-GAS_normalization_normalize_property (struct ATS_Address *address,
- const struct GNUNET_ATS_Information *atsi,
- uint32_t atsi_count)
+GAS_normalization_update_property (struct ATS_Address *address)
{
- struct Property *cur_prop;
- unsigned int c1;
- unsigned int c2;
- uint32_t current_type;
- uint32_t current_val;
- unsigned int existing_properties[] = GNUNET_ATS_QualityProperties;
+ const struct GNUNET_ATS_Properties *prop = &address->properties;
+ struct PropertyRange range;
LOG (GNUNET_ERROR_TYPE_DEBUG,
- "Updating %u elements for peer `%s'\n",
- atsi_count,
+ "Updating properties for peer `%s'\n",
GNUNET_i2s (&address->peer));
GAS_plugin_solver_lock ();
- for (c1 = 0; c1 < atsi_count; c1++)
+ 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 != memcmp (&range,
+ &property_range,
+ sizeof (struct PropertyRange)))
{
- current_type = ntohl (atsi[c1].type);
-
- for (c2 = 0; c2 < GNUNET_ATS_QualityPropertiesCount; c2++)
- {
- /* Check if type is valid */
- if (current_type == existing_properties[c2])
- break;
- }
- if (GNUNET_ATS_QualityPropertiesCount == c2)
- {
- /* Invalid property, continue with next element */
- continue;
- }
- /* Averaging */
- current_val = property_average (address, &atsi[c1]);
- if (GNUNET_ATS_VALUE_UNDEFINED == current_val)
- {
- GNUNET_break(0);
- continue;
- }
-
- /* Normalizing */
- /* Check min, max */
- cur_prop = &properties[c2];
- property_normalize (cur_prop,
- address,
- current_val);
+ /* limits changed, (re)normalize all addresses */
+ property_range = range;
+ GNUNET_CONTAINER_multipeermap_iterate (GSA_addresses,
+ &normalize_address,
+ NULL);
+ GNUNET_CONTAINER_multipeermap_iterate (GSA_addresses,
+ ¬ify_change,
+ NULL);
+ }
+ else
+ {
+ /* renormalize just this one address */
+ normalize_address (NULL,
+ &address->peer,
+ address);
+ notify_change (NULL,
+ &address->peer,
+ address);
}
GAS_plugin_solver_unlock ();
}
@@ -403,16 +281,7 @@ GAS_normalization_normalize_property (struct ATS_Address *address,
void
GAS_normalization_start ()
{
- unsigned int c1;
- unsigned int existing_properties[] = GNUNET_ATS_QualityProperties;
-
- for (c1 = 0; c1 < GNUNET_ATS_QualityPropertiesCount; c1++)
- {
- properties[c1].prop_type = c1;
- properties[c1].atsi_type = existing_properties[c1];
- properties[c1].min = UINT32_MAX;
- properties[c1].max = 0;
- }
+ init_range (&property_range);
}