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_normalization.h"
36 struct PreferenceClient
41 struct PreferenceClient *prev;
47 struct PreferenceClient *next;
55 * Total preference for this peer
57 double f_abs_sum[GNUNET_ATS_PreferenceCount];
60 * List of peer preferences for this client
66 struct PreferencePeer *p_head;
71 struct PreferencePeer *p_tail;
83 struct PreferencePeer *next;
88 struct PreferencePeer *prev;
93 struct PreferenceClient *client;
98 struct GNUNET_PeerIdentity id;
101 * Absolute preference values
103 double f_abs[GNUNET_ATS_PreferenceCount];
106 * Relative preference values
108 double f_rel[GNUNET_ATS_PreferenceCount];
113 GNUNET_SCHEDULER_TaskIdentifier aging_task;
117 * Relative preferences for a peer
122 * Relative preference values
124 double f_rel[GNUNET_ATS_PreferenceCount];
129 struct GNUNET_PeerIdentity id;
133 struct GNUNET_CONTAINER_MultiHashMap *peers;
134 struct PreferenceClient *pc_head;
135 struct PreferenceClient *pc_tail;
136 struct PeerRelative defvalues;
140 update_peers (struct GNUNET_PeerIdentity *id,
141 enum GNUNET_ATS_PreferenceKind kind)
143 struct PreferenceClient *c_cur;
144 struct PreferencePeer *p_cur;
145 struct PeerRelative *rp;
152 /* For all clients */
153 for (c_cur = pc_head; NULL != c_cur; c_cur = c_cur->next)
155 /* Find peer with id */
156 for (p_cur = c_cur->p_head; NULL != p_cur; p_cur = p_cur->next)
158 if (0 == memcmp (id, &p_cur->id, sizeof (struct GNUNET_PeerIdentity)))
163 /* Found peer with id */
164 f_rel_total += p_cur->f_rel[kind];
172 f_rel_total /= count;
173 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "%u clients have a total relative preference for peer `%s''s%s is %.3f\n",
176 GNUNET_ATS_print_preference_type (kind),
178 if (NULL != (rp = GNUNET_CONTAINER_multihashmap_get (peers, &id->hashPubKey)))
180 rp->f_rel[kind] = f_rel_total;
186 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "No clients have a total relative preference for peer `%s''s%s\n",
189 GNUNET_ATS_print_preference_type (kind));
190 if (NULL != (rp = GNUNET_CONTAINER_multihashmap_get (peers, &id->hashPubKey)))
192 rp->f_rel[kind] = DEFAULT_REL_PREFERENCE;
194 return DEFAULT_REL_PREFERENCE;
199 * Recalculate preference for a specific ATS property
202 * @param kind the preference kind
205 recalculate_rel_preferences (struct PreferenceClient *c,
206 struct PreferencePeer *p,
207 enum GNUNET_ATS_PreferenceKind kind)
209 struct PreferencePeer *p_cur;
210 struct PeerRelative *rp;
215 /* For this client: sum preferences to total preference */
216 c->f_abs_sum[kind] = 0;
217 for (p_cur = c->p_head; NULL != p_cur; p_cur = p_cur->next)
218 c->f_abs_sum[kind] += p_cur->f_abs[kind];
219 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Client %p has total preference for %s of %.3f\n",
221 GNUNET_ATS_print_preference_type (kind),
224 ret = DEFAULT_REL_PREFERENCE;
225 /* For all peers: calculate relative preference */
226 for (p_cur = c->p_head; NULL != p_cur; p_cur = p_cur->next)
228 /* Calculate relative preference for specific kind */
229 backup = p_cur->f_rel[kind];
230 if (DEFAULT_ABS_PREFERENCE == c->f_abs_sum[kind])
231 /* No peer has a preference for this property, so set default preference */
232 p_cur->f_rel[kind] = DEFAULT_REL_PREFERENCE;
234 p_cur->f_rel[kind] = (c->f_abs_sum[kind] + p_cur->f_abs[kind]) / c->f_abs_sum[kind];
236 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Client %p: peer `%s' has relative preference for %s of %.3f\n",
238 GNUNET_i2s (&p_cur->id),
239 GNUNET_ATS_print_preference_type (kind),
243 if (p_cur->f_rel[kind] != backup)
245 /* Value changed, recalculate */
246 res = update_peers (&p_cur->id,kind);
247 if (0 == memcmp (&p->id, &p_cur->id, sizeof (struct GNUNET_PeerIdentity)))
252 /* Value did not chang, return old value*/
253 GNUNET_assert (NULL != (rp = GNUNET_CONTAINER_multihashmap_get (peers, &p->id.hashPubKey)));
254 ret = rp->f_rel[kind];
261 update_preference (struct PreferenceClient *c,
262 struct PreferencePeer *p,
263 enum GNUNET_ATS_PreferenceKind kind,
266 double score = score_abs;
268 /* Update preference value according to type */
270 case GNUNET_ATS_PREFERENCE_BANDWIDTH:
271 case GNUNET_ATS_PREFERENCE_LATENCY:
272 p->f_abs[kind] = (p->f_abs[kind] + score) / 2;
274 case GNUNET_ATS_PREFERENCE_END:
279 return recalculate_rel_preferences (c, p, kind);
283 preference_aging (void *cls, const struct GNUNET_SCHEDULER_TaskContext *tc)
288 struct PreferencePeer *p = cls;
289 GNUNET_assert (NULL != p);
291 p->aging_task = GNUNET_SCHEDULER_NO_TASK;
293 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Aging preferences for peer `%s'\n",
294 GNUNET_i2s (&p->id));
298 * Not for every peer preference values are set by default, so reducing the
299 * absolute preference value does not help for aging because it does not have
300 * influence on the relative values.
302 * So we have to reduce the relative value to have an immediate impact on
303 * quota calculation. In addition we cannot call recalculate_preferences here
304 * but instead reduce the absolute value to have an aging impact on future
305 * calls to change_preference where recalculate_preferences is called
308 /* Aging absolute values: */
309 for (i = 0; i < GNUNET_ATS_PreferenceCount; i++)
311 backup = p->f_abs[i];
312 if (p->f_abs[i] > DEFAULT_ABS_PREFERENCE)
313 p->f_abs[i] *= PREF_AGING_FACTOR;
314 if (backup != p->f_abs[i])
316 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Aged preference for peer `%s' from %.3f to %.3f\n",
317 GNUNET_i2s (&p->id), backup, p->f_abs[i]);
318 recalculate_rel_preferences (p->client, p, i);
321 p->aging_task = GNUNET_SCHEDULER_add_delayed (PREF_AGING_INTERVAL,
322 &preference_aging, p);
326 * Changes the preferences for a peer in the problem
328 * @param solver the solver handle
329 * @param client the client with this preference
330 * @param peer the peer to change the preference for
331 * @param kind the kind to change the preference
332 * @param score the normalized score
335 GAS_normalization_change_preference (void *src,
336 const struct GNUNET_PeerIdentity *peer,
337 enum GNUNET_ATS_PreferenceKind kind,
341 struct PreferenceClient *c_cur;
342 struct PreferencePeer *p_cur;
343 struct PeerRelative *r_cur;
347 GNUNET_assert (NULL != src);
348 GNUNET_assert (NULL != peer);
350 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Client %p changes preference for peer `%s' for `%s' to %.2f\n",
353 GNUNET_ATS_print_preference_type (kind),
356 if (kind >= GNUNET_ATS_PreferenceCount)
362 /* Find preference client */
363 for (c_cur = pc_head; NULL != c_cur; c_cur = c_cur->next)
365 if (src == c_cur->client)
368 /* Not found: create new preference client */
371 c_cur = GNUNET_malloc (sizeof (struct PreferenceClient));
373 GNUNET_CONTAINER_DLL_insert (pc_head, pc_tail, c_cur);
376 /* Find entry for peer */
377 for (p_cur = c_cur->p_head; NULL != p_cur; p_cur = p_cur->next)
378 if (0 == memcmp (&p_cur->id, peer, sizeof (p_cur->id)))
381 /* Not found: create new peer entry */
384 p_cur = GNUNET_malloc (sizeof (struct PreferencePeer));
385 p_cur->client = c_cur;
387 for (i = 0; i < GNUNET_ATS_PreferenceCount; i++)
389 /* Default value per peer absolut preference for a quality:
390 * No value set, so absolute preference 0 */
391 p_cur->f_abs[i] = DEFAULT_ABS_PREFERENCE;
392 /* Default value per peer relative preference for a quality: 1.0 */
393 p_cur->f_rel[i] = DEFAULT_REL_PREFERENCE;
395 p_cur->aging_task = GNUNET_SCHEDULER_add_delayed (PREF_AGING_INTERVAL, &preference_aging, p_cur);
396 GNUNET_CONTAINER_DLL_insert (c_cur->p_head, c_cur->p_tail, p_cur);
399 if (NULL == (r_cur = GNUNET_CONTAINER_multihashmap_get (peers, &peer->hashPubKey)))
401 r_cur = GNUNET_malloc (sizeof (struct PeerRelative));
403 for (i = 0; i < GNUNET_ATS_PreferenceCount; i++)
404 r_cur->f_rel[i] = DEFAULT_REL_PREFERENCE;
405 GNUNET_CONTAINER_multihashmap_put (peers, &r_cur->id.hashPubKey, r_cur, GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY);
408 score_rel = update_preference (c_cur, p_cur, kind, score_abs);
413 * Get the normalized preference values for a specific peer
416 * @return pointer to the values, can be indexed with GNUNET_ATS_PreferenceKind, default preferences if peer does not exist
419 GAS_normalization_get_preferences (struct GNUNET_PeerIdentity *id)
421 struct PeerRelative *rp;
422 if (NULL == (rp = GNUNET_CONTAINER_multihashmap_get (peers, &id->hashPubKey)))
424 return defvalues.f_rel;
430 GAS_normalization_start ()
433 peers = GNUNET_CONTAINER_multihashmap_create(10, GNUNET_NO);
435 for (i = 0; i < GNUNET_ATS_PreferenceCount; i++)
436 defvalues.f_rel[i] = DEFAULT_REL_PREFERENCE;
441 free_peer (void *cls,
442 const struct GNUNET_HashCode * key,
445 struct PeerRelative *rp = value;
446 GNUNET_CONTAINER_multihashmap_remove (peers, key, value);
452 GAS_normalization_stop ()
454 struct PreferenceClient *pc;
455 struct PreferenceClient *next_pc;
456 struct PreferencePeer *p;
457 struct PreferencePeer *next_p;
460 while (NULL != (pc = next_pc))
463 GNUNET_CONTAINER_DLL_remove (pc_head, pc_tail, pc);
465 while (NULL != (p = next_p))
468 if (GNUNET_SCHEDULER_NO_TASK != p->aging_task)
470 GNUNET_SCHEDULER_cancel(p->aging_task);
471 p->aging_task = GNUNET_SCHEDULER_NO_TASK;
473 GNUNET_CONTAINER_DLL_remove (pc->p_head, pc->p_tail, p);
478 GNUNET_CONTAINER_multihashmap_iterate (peers, &free_peer, NULL);
479 GNUNET_CONTAINER_multihashmap_destroy (peers);
483 /* end of gnunet-service-ats_normalization.c */