2 This file is part of GNUnet.
3 (C) 2011 Christian Grothoff (and other contributing authors)
5 GNUnet is free software; you can redistribute it and/or modify
6 it under the terms of the GNU General Public License as published
7 by the Free Software Foundation; either version 3, or (at your
8 option) any later version.
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 General Public License for more details.
15 You should have received a copy of the GNU General Public License
16 along with GNUnet; see the file COPYING. If not, write to the
17 Free Software Foundation, Inc., 59 Temple Place - Suite 330,
18 Boston, MA 02111-1307, USA.
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
28 #include "gnunet_ats_service.h"
29 #include "gnunet-service-ats_addresses.h"
30 #include "gnunet-service-ats_normalization.h"
32 #define LOG(kind,...) GNUNET_log_from (kind, "ats-normalization",__VA_ARGS__)
38 struct PreferenceClient
43 struct PreferenceClient *prev;
49 struct PreferenceClient *next;
57 * Total preference for this peer
59 double f_abs_sum[GNUNET_ATS_PreferenceCount];
62 * List of peer preferences for this client
68 struct PreferencePeer *p_head;
73 struct PreferencePeer *p_tail;
85 struct PreferencePeer *next;
90 struct PreferencePeer *prev;
95 struct PreferenceClient *client;
100 struct GNUNET_PeerIdentity id;
103 * Absolute preference values
105 double f_abs[GNUNET_ATS_PreferenceCount];
108 * Relative preference values
110 double f_rel[GNUNET_ATS_PreferenceCount];
115 GNUNET_SCHEDULER_TaskIdentifier aging_task;
119 * Relative preferences for a peer
124 * Relative preference values
126 double f_rel[GNUNET_ATS_PreferenceCount];
131 struct GNUNET_PeerIdentity id;
136 * Callback to call on changing preference values
138 static GAS_Normalization_preference_changed_cb pref_changed_cb;
142 * Closure for callback to call on changing preference values
144 static void *pref_changed_cb_cls;
148 * Callback to call on changing property values
150 GAS_Normalization_property_changed_cb prop_ch_cb;
153 * Closure for callback to call on changing property values
155 void *prop_ch_cb_cls;
159 * Hashmap to store peer information for preference normalization
161 static struct GNUNET_CONTAINER_MultiHashMap *preference_peers;
166 * Hashmap to store peer information for property normalization
168 static struct GNUNET_CONTAINER_MultiHashMap *property_peers;
173 * Clients in DLL: head
175 static struct PreferenceClient *pc_head;
179 * Clients in DLL: tail
181 static struct PreferenceClient *pc_tail;
187 static struct PeerRelative defvalues;
190 * Application Preference Normalization
197 * @param kind the kind
198 * @return the new relative preference
201 update_peers (struct GNUNET_PeerIdentity *id,
202 enum GNUNET_ATS_PreferenceKind kind)
204 struct PreferenceClient *c_cur;
205 struct PreferencePeer *p_cur;
206 struct PeerRelative *rp;
214 /* For all clients */
215 for (c_cur = pc_head; NULL != c_cur; c_cur = c_cur->next)
217 /* Find peer with id */
218 for (p_cur = c_cur->p_head; NULL != p_cur; p_cur = p_cur->next)
220 if (0 == memcmp (id, &p_cur->id, sizeof (struct GNUNET_PeerIdentity)))
225 /* Found peer with id */
226 f_rel_total += p_cur->f_rel[kind];
232 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
233 "%u clients have a total relative preference for peer `%s''s `%s' of %.3f\n",
236 GNUNET_ATS_print_preference_type (kind),
238 if (NULL != (rp = GNUNET_CONTAINER_multihashmap_get (preference_peers, &id->hashPubKey)))
240 backup = rp->f_rel[kind];
243 rp->f_rel[kind] = f_rel_total / count;
247 rp->f_rel[kind] = DEFAULT_REL_PREFERENCE;
252 return DEFAULT_REL_PREFERENCE;
255 if ((backup != rp->f_rel[kind]) && (NULL != pref_changed_cb))
257 pref_changed_cb (pref_changed_cb_cls, &rp->id, kind, rp->f_rel[kind]);
260 return rp->f_rel[kind];
265 * Recalculate preference for a specific ATS property
267 * @param c the preference client
269 * @param kind the preference kind
273 recalculate_rel_preferences (struct PreferenceClient *c,
274 struct PreferencePeer *p,
275 enum GNUNET_ATS_PreferenceKind kind)
277 struct PreferencePeer *p_cur;
278 struct PeerRelative *rp;
283 /* For this client: sum preferences to total preference */
284 c->f_abs_sum[kind] = 0;
285 for (p_cur = c->p_head; NULL != p_cur; p_cur = p_cur->next)
286 c->f_abs_sum[kind] += p_cur->f_abs[kind];
287 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
288 "Client %p has total preference for %s of %.3f\n",
290 GNUNET_ATS_print_preference_type (kind),
293 ret = DEFAULT_REL_PREFERENCE;
294 /* For all peers: calculate relative preference */
295 for (p_cur = c->p_head; NULL != p_cur; p_cur = p_cur->next)
297 /* Calculate relative preference for specific kind */
298 backup = p_cur->f_rel[kind];
299 if (DEFAULT_ABS_PREFERENCE == c->f_abs_sum[kind])
300 /* No peer has a preference for this property,
301 * so set default preference */
302 p_cur->f_rel[kind] = DEFAULT_REL_PREFERENCE;
304 p_cur->f_rel[kind] = (c->f_abs_sum[kind] + p_cur->f_abs[kind]) /
307 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
308 "Client %p: peer `%s' has relative preference for %s of %.3f\n",
310 GNUNET_i2s (&p_cur->id),
311 GNUNET_ATS_print_preference_type (kind),
315 if (p_cur->f_rel[kind] != backup)
317 /* Value changed, recalculate */
318 res = update_peers (&p_cur->id,kind);
319 if (0 == memcmp (&p->id, &p_cur->id, sizeof (struct GNUNET_PeerIdentity)))
324 /* Value did not chang, return old value*/
325 GNUNET_assert (NULL != (rp = GNUNET_CONTAINER_multihashmap_get (preference_peers,
326 &p->id.hashPubKey)));
327 ret = rp->f_rel[kind];
335 * Update the absolute preference value for a peer
336 * @param c the client
338 * @param kind the preference kind
339 * @param score_abs the absolute value
340 * @return the new relative preference value
343 update_preference (struct PreferenceClient *c,
344 struct PreferencePeer *p,
345 enum GNUNET_ATS_PreferenceKind kind,
348 double score = score_abs;
350 /* Update preference value according to type */
352 case GNUNET_ATS_PREFERENCE_BANDWIDTH:
353 case GNUNET_ATS_PREFERENCE_LATENCY:
354 p->f_abs[kind] = (p->f_abs[kind] + score) / 2;
356 case GNUNET_ATS_PREFERENCE_END:
361 return recalculate_rel_preferences (c, p, kind);
366 * Reduce absolute preferences since they got old
368 * @param cls the PreferencePeer
372 preference_aging (void *cls, const struct GNUNET_SCHEDULER_TaskContext *tc)
376 struct PreferencePeer *p = cls;
377 GNUNET_assert (NULL != p);
379 p->aging_task = GNUNET_SCHEDULER_NO_TASK;
381 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Aging preferences for peer `%s'\n",
382 GNUNET_i2s (&p->id));
384 /* Aging absolute values: */
385 for (i = 0; i < GNUNET_ATS_PreferenceCount; i++)
387 backup = p->f_abs[i];
388 if (p->f_abs[i] > DEFAULT_ABS_PREFERENCE)
389 p->f_abs[i] *= PREF_AGING_FACTOR;
390 if (backup != p->f_abs[i])
392 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Aged preference for peer `%s' from %.3f to %.3f\n",
393 GNUNET_i2s (&p->id), backup, p->f_abs[i]);
394 recalculate_rel_preferences (p->client, p, i);
397 p->aging_task = GNUNET_SCHEDULER_add_delayed (PREF_AGING_INTERVAL,
398 &preference_aging, p);
403 * Normalize an updated preference value
405 * @param src the client with this preference
406 * @param peer the peer to change the preference for
407 * @param kind the kind to change the preference
408 * @param score_abs the normalized score
411 GAS_normalization_normalize_preference (void *src,
412 const struct GNUNET_PeerIdentity *peer,
413 enum GNUNET_ATS_PreferenceKind kind,
416 struct PreferenceClient *c_cur;
417 struct PreferencePeer *p_cur;
418 struct PeerRelative *r_cur;
422 GNUNET_assert (NULL != src);
423 GNUNET_assert (NULL != peer);
425 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
426 "Client %p changes preference for peer `%s' for `%s' to %.2f\n",
429 GNUNET_ATS_print_preference_type (kind),
432 if (kind >= GNUNET_ATS_PreferenceCount)
438 /* Find preference client */
439 for (c_cur = pc_head; NULL != c_cur; c_cur = c_cur->next)
441 if (src == c_cur->client)
444 /* Not found: create new preference client */
447 c_cur = GNUNET_malloc (sizeof (struct PreferenceClient));
449 GNUNET_CONTAINER_DLL_insert (pc_head, pc_tail, c_cur);
452 /* Find entry for peer */
453 for (p_cur = c_cur->p_head; NULL != p_cur; p_cur = p_cur->next)
454 if (0 == memcmp (&p_cur->id, peer, sizeof (p_cur->id)))
457 /* Not found: create new peer entry */
460 p_cur = GNUNET_malloc (sizeof (struct PreferencePeer));
461 p_cur->client = c_cur;
463 for (i = 0; i < GNUNET_ATS_PreferenceCount; i++)
465 /* Default value per peer absolut preference for a quality:
466 * No value set, so absolute preference 0 */
467 p_cur->f_abs[i] = DEFAULT_ABS_PREFERENCE;
468 /* Default value per peer relative preference for a quality: 1.0 */
469 p_cur->f_rel[i] = DEFAULT_REL_PREFERENCE;
471 p_cur->aging_task = GNUNET_SCHEDULER_add_delayed (PREF_AGING_INTERVAL,
472 &preference_aging, p_cur);
473 GNUNET_CONTAINER_DLL_insert (c_cur->p_head, c_cur->p_tail, p_cur);
476 if (NULL == GNUNET_CONTAINER_multihashmap_get (preference_peers,
479 r_cur = GNUNET_malloc (sizeof (struct PeerRelative));
481 for (i = 0; i < GNUNET_ATS_PreferenceCount; i++)
482 r_cur->f_rel[i] = DEFAULT_REL_PREFERENCE;
483 GNUNET_CONTAINER_multihashmap_put (preference_peers, &r_cur->id.hashPubKey,
484 r_cur, GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY);
486 update_preference (c_cur, p_cur, kind, score_abs);
491 * Get the normalized preference values for a specific peer or
492 * the default values if
495 * @return pointer to the values, can be indexed with GNUNET_ATS_PreferenceKind,
496 * default preferences if peer does not exist
499 GAS_normalization_get_preferences (const struct GNUNET_PeerIdentity *id)
501 GNUNET_assert (NULL != preference_peers);
502 GNUNET_assert (NULL != id);
504 struct PeerRelative *rp;
505 if (NULL == (rp = GNUNET_CONTAINER_multihashmap_get (preference_peers, &id->hashPubKey)))
507 return defvalues.f_rel;
514 * Get the normalized properties values for a specific peer or
515 * the default values if
517 * @param address the address
518 * @return pointer to the values, can be indexed with GNUNET_ATS_PreferenceKind,
519 * default preferences if peer does not exist
522 GAS_normalization_get_properties (struct ATS_Address *address)
524 static double norm_values[GNUNET_ATS_QualityPropertiesCount];
527 GNUNET_assert (NULL != address);
529 for (i = 0; i < GNUNET_ATS_QualityPropertiesCount; i++)
531 if ((address->atsin[i].norm >= 1.0) &&
532 (address->atsin[i].norm <= 2.0))
533 norm_values[i] = address->atsin[i].norm;
535 norm_values[i] = DEFAULT_REL_QUALITY;
543 * Quality Normalization
554 struct Property properties[GNUNET_ATS_QualityPropertiesCount];
557 * Normalize a specific ATS type with the values in queue
558 * @param address the address
559 * @param atsi the ats information
560 * @return the new average or GNUNET_ATS_VALUE_UNDEFINED
564 property_average (struct ATS_Address *address,
565 const struct GNUNET_ATS_Information *atsi)
567 struct GAS_NormalizationInfo *ni;
568 uint32_t current_type;
569 uint32_t current_val;
575 unsigned int props[] = GNUNET_ATS_QualityProperties;
577 /* Average the values of this property */
578 current_type = ntohl (atsi->type);
579 current_val = ntohl (atsi->value);
581 for (c1 = 0; c1 < GNUNET_ATS_QualityPropertiesCount; c1++)
583 if (current_type == props[c1])
586 if (c1 == GNUNET_ATS_QualityPropertiesCount)
589 return GNUNET_ATS_VALUE_UNDEFINED;
593 ni = &address->atsin[index];
594 ni->atsi_abs[ni->avg_queue_index] = current_val;
595 ni->avg_queue_index ++;
596 if (GAS_normalization_queue_length == ni->avg_queue_index)
597 ni->avg_queue_index = 0;
601 for (c1 = 0; c1 < GAS_normalization_queue_length; c1++)
603 if (GNUNET_ATS_VALUE_UNDEFINED != ni->atsi_abs[c1])
606 if (GNUNET_ATS_VALUE_UNDEFINED > (sum + ni->atsi_abs[c1]))
607 sum += ni->atsi_abs[c1];
610 sum = GNUNET_ATS_VALUE_UNDEFINED - 1;
615 GNUNET_assert (0 != count);
617 LOG (GNUNET_ERROR_TYPE_DEBUG, "New average of `%s' created by adding %u from %u elements: %u\n",
618 GNUNET_ATS_print_property_type(current_type),
619 current_val, count, res , sum);
633 find_min_max_it (void *cls, const struct GNUNET_HashCode *h, void *k)
635 struct ATS_Address *a = (struct ATS_Address *) k;
636 struct FindMinMaxCtx *find_res = cls;
638 if (a->atsin[find_res->p->prop_type].avg > find_res->max)
639 find_res->max = a->atsin[find_res->p->prop_type].avg;
641 if (a->atsin[find_res->p->prop_type].avg < find_res->min)
642 find_res->min = a->atsin[find_res->p->prop_type].avg;
649 normalize_address (void *cls, const struct GNUNET_HashCode *h, void *k)
651 struct Property *p = cls;
652 struct ATS_Address *address = (struct ATS_Address *) k;
655 uint32_t avg_value = address->atsin[p->prop_type].avg;
657 delta = p->max - p->min;
658 address->atsin[p->prop_type].norm = (delta + (avg_value - p->min)) / (delta);
660 LOG (GNUNET_ERROR_TYPE_DEBUG, "Normalize `%s' address %p's '%s' with value %u to range [%u..%u] = %.3f\n",
661 GNUNET_i2s (&address->peer),
663 GNUNET_ATS_print_property_type (p->atsi_type),
664 address->atsin[p->prop_type].avg,
666 address->atsin[p->prop_type].norm );
668 if (NULL != prop_ch_cb)
669 prop_ch_cb (prop_ch_cb_cls, address, p->atsi_type,
670 address->atsin[p->prop_type].norm);
678 * Normalize avg_value to a range of values between [1.0, 2.0]
679 * based on min max values currently known.
681 * @param addresses the address hashmap
682 * @param p the property
683 * @param address the address
684 * @param avg_value the value to normalize
688 property_normalize (struct GNUNET_CONTAINER_MultiHashMap *addresses,
690 struct ATS_Address *address,
693 struct FindMinMaxCtx find_ctx;
699 find_ctx.min = UINT32_MAX;
700 addr_count = GNUNET_CONTAINER_multihashmap_iterate(addresses, &find_min_max_it, &find_ctx);
708 limits_changed = GNUNET_NO;
709 if (find_ctx.max != p->max)
711 LOG (GNUNET_ERROR_TYPE_DEBUG, "Normalizing %s: new maximum %u -> recalculate all values\n",
712 GNUNET_ATS_print_property_type (p->atsi_type),
714 p->max = find_ctx.max;
715 limits_changed = GNUNET_YES;
718 if ((find_ctx.min != p->min) && (find_ctx.min < p->max))
720 LOG (GNUNET_ERROR_TYPE_DEBUG, "Normalizing %s: new minimum %u -> recalculate all values\n",
721 GNUNET_ATS_print_property_type (p->atsi_type),
722 find_ctx.min, find_ctx.max);
723 p->min = find_ctx.min;
724 limits_changed = GNUNET_YES;
726 else if (find_ctx.min == p->max)
728 /* Only one value, so minimum has to be 0 */
732 /* Normalize the values of this property */
733 if (GNUNET_NO == limits_changed)
735 /* normalize just this address */
736 normalize_address (p, &address->peer.hashPubKey, address);
741 /* limits changed, normalize all addresses */
742 GNUNET_CONTAINER_multihashmap_iterate(addresses, &normalize_address, p);
749 * Update and normalize a atsi performance information
751 * @param addresses hashmap containing all addresses
752 * @param address the address to update
753 * @param atsi the array of performance information
754 * @param atsi_count the number of atsi information in the array
757 GAS_normalization_normalize_property (struct GNUNET_CONTAINER_MultiHashMap *addresses,
758 struct ATS_Address *address,
759 const struct GNUNET_ATS_Information *atsi,
762 struct Property *cur_prop;
765 uint32_t current_type;
766 uint32_t current_val;
767 unsigned int existing_properties[] = GNUNET_ATS_QualityProperties;
769 GNUNET_assert (NULL != address);
770 GNUNET_assert (NULL != atsi);
772 LOG (GNUNET_ERROR_TYPE_DEBUG, "Updating %u elements for peer `%s'\n",
773 atsi_count, GNUNET_i2s (&address->peer));
775 for (c1 = 0; c1 < atsi_count; c1++)
777 current_type = ntohl (atsi[c1].type);
778 current_val = ntohl (atsi[c1].value);
779 for (c2 = 0; c2 < GNUNET_ATS_QualityPropertiesCount; c2++)
781 /* Check if type is valid */
782 if (current_type == existing_properties[c2])
785 if (GNUNET_ATS_QualityPropertiesCount == c2)
787 /* Invalid property, continue with next element */
791 current_val = property_average (address, &atsi[c1]);
792 if (GNUNET_ATS_VALUE_UNDEFINED == current_val)
800 cur_prop = &properties[c2];
801 property_normalize (addresses, cur_prop, address, current_val);
807 * Start the normalization component
809 * @param pref_ch_cb callback to call on relative preference changing
810 * @param pref_ch_cb_cls cls for the preference callback
811 * @param property_ch_cb callback to call on relative property changing
812 * @param property_ch_cb_cls cls for the property callback
815 GAS_normalization_start (GAS_Normalization_preference_changed_cb pref_ch_cb,
816 void *pref_ch_cb_cls,
817 GAS_Normalization_property_changed_cb property_ch_cb,
818 void *property_ch_cb_cls)
822 preference_peers = GNUNET_CONTAINER_multihashmap_create(10, GNUNET_NO);
823 property_peers = GNUNET_CONTAINER_multihashmap_create(10, GNUNET_NO);
824 unsigned int existing_properties[] = GNUNET_ATS_QualityProperties;
826 for (c1 = 0; c1 < GNUNET_ATS_QualityPropertiesCount; c1++)
828 properties[c1].prop_type = c1;
829 properties[c1].atsi_type = existing_properties[c1];
830 properties[c1].min = 0;
831 properties[c1].max = 0;
834 pref_changed_cb = pref_ch_cb;
835 pref_changed_cb_cls = pref_ch_cb_cls;
836 prop_ch_cb = property_ch_cb;
837 prop_ch_cb_cls = pref_ch_cb_cls;
839 for (i = 0; i < GNUNET_ATS_PreferenceCount; i++)
840 defvalues.f_rel[i] = DEFAULT_REL_PREFERENCE;
850 * @param value RelativePeer
851 * @return GNUNET_OK to continue
854 free_peer (void *cls,
855 const struct GNUNET_HashCode * key,
858 struct PeerRelative *rp = value;
859 if (GNUNET_YES == GNUNET_CONTAINER_multihashmap_remove (preference_peers, key, value))
868 * Stop the normalization component and free all items
871 GAS_normalization_stop ()
873 struct PreferenceClient *pc;
874 struct PreferenceClient *next_pc;
875 struct PreferencePeer *p;
876 struct PreferencePeer *next_p;
879 while (NULL != (pc = next_pc))
882 GNUNET_CONTAINER_DLL_remove (pc_head, pc_tail, pc);
884 while (NULL != (p = next_p))
887 if (GNUNET_SCHEDULER_NO_TASK != p->aging_task)
889 GNUNET_SCHEDULER_cancel(p->aging_task);
890 p->aging_task = GNUNET_SCHEDULER_NO_TASK;
892 GNUNET_CONTAINER_DLL_remove (pc->p_head, pc->p_tail, p);
897 GNUNET_CONTAINER_multihashmap_iterate (preference_peers, &free_peer, NULL);
898 GNUNET_CONTAINER_multihashmap_destroy (preference_peers);
899 GNUNET_CONTAINER_multihashmap_destroy (property_peers);
903 /* end of gnunet-service-ats_normalization.c */