src/ats/gnunet-service-ats_normalization.c

   1 /*
   2      This file is part of GNUnet.
   3      (C) 2011 Christian Grothoff (and other contributing authors)
   4
   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.
   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      General Public License for more details.
  14
  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.
  19 */
  20
  21 /**
  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
  26  */
  27 #include "platform.h"
  28 #include "gnunet_ats_service.h"
  29 #include "gnunet-service-ats_normalization.h"
  30
  31
  32
  33 /**
  34  * Preference client
  35  */
  36 struct PreferenceClient
  37 {
  38   /**
  39    * Next in DLL
  40    */
  41   struct PreferenceClient *prev;
  42
  43   /**
  44    * Next in DLL
  45    */
  46
  47   struct PreferenceClient *next;
  48
  49   /**
  50    * Client handle
  51    */
  52   void *client;
  53
  54   /**
  55    * Total preference for this peer
  56    */
  57   double f_abs_sum[GNUNET_ATS_PreferenceCount];
  58
  59   /**
  60    * List of peer preferences for this client
  61    */
  62
  63   /**
  64    * Head of peer list
  65    */
  66   struct PreferencePeer *p_head;
  67
  68   /**
  69    * Tail of peer list
  70    */
  71   struct PreferencePeer *p_tail;
  72 };
  73
  74
  75 /**
  76  * Preference peer
  77  */
  78 struct PreferencePeer
  79 {
  80   /**
  81    * Next in DLL
  82    */
  83   struct PreferencePeer *next;
  84
  85   /**
  86    * Previous in DLL
  87    */
  88   struct PreferencePeer *prev;
  89
  90   /**
  91    * Client
  92    */
  93   struct PreferenceClient *client;
  94
  95   /**
  96    * Peer id
  97    */
  98   struct GNUNET_PeerIdentity id;
  99
 100   /**
 101    * Absolute preference values
 102    */
 103   double f_abs[GNUNET_ATS_PreferenceCount];
 104
 105   /**
 106    * Relative preference values
 107    */
 108   double f_rel[GNUNET_ATS_PreferenceCount];
 109
 110   /**
 111    * Aging Task
 112    */
 113   GNUNET_SCHEDULER_TaskIdentifier aging_task;
 114 };
 115
 116 /**
 117  * Relative preferences for a peer
 118  */
 119 struct PeerRelative
 120 {
 121   /**
 122    * Relative preference values
 123    */
 124   double f_rel[GNUNET_ATS_PreferenceCount];
 125
 126   /**
 127    * Peer id
 128    */
 129   struct GNUNET_PeerIdentity id;
 130 };
 131
 132 GAS_Normalization_preference_changed_cb pref_changed_cb;
 133 void *pref_changed_cb_cls;
 134 struct GNUNET_CONTAINER_MultiHashMap *peers;
 135 struct PreferenceClient *pc_head;
 136 struct PreferenceClient *pc_tail;
 137 struct PeerRelative defvalues;
 138
 139
 140 static double
 141 update_peers (struct GNUNET_PeerIdentity *id,
 142                                                         enum GNUNET_ATS_PreferenceKind kind)
 143 {
 144         struct PreferenceClient *c_cur;
 145         struct PreferencePeer *p_cur;
 146         struct PeerRelative *rp;
 147         double f_rel_total;
 148         double backup;
 149         unsigned int count;
 150
 151         f_rel_total = 0.0;
 152         count = 0;
 153
 154         /* For all clients */
 155         for (c_cur = pc_head; NULL != c_cur; c_cur = c_cur->next)
 156         {
 157                 /* Find peer with id */
 158                 for (p_cur = c_cur->p_head; NULL != p_cur; p_cur = p_cur->next)
 159                 {
 160                         if (0 == memcmp (id, &p_cur->id, sizeof (struct GNUNET_PeerIdentity)))
 161                                 break;
 162                 }
 163                 if (NULL != p_cur)
 164                 {
 165                         /* Found peer with id */
 166                         f_rel_total +=  p_cur->f_rel[kind];
 167                         count ++;
 168                 }
 169         }
 170
 171         /* Find a client */
 172         GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "%u clients have a total relative preference for peer `%s''s `%s' of %.3f\n",
 173                         count,
 174                         GNUNET_i2s (id),
 175                         GNUNET_ATS_print_preference_type (kind),
 176                         f_rel_total);
 177         if (NULL != (rp = GNUNET_CONTAINER_multihashmap_get (peers, &id->hashPubKey)))
 178         {
 179                 backup = rp->f_rel[kind];
 180                 if (0 < count)
 181                 {
 182                         rp->f_rel[kind] = f_rel_total / count;
 183                 }
 184                 else
 185                 {
 186                         rp->f_rel[kind] = DEFAULT_REL_PREFERENCE;
 187                 }
 188         }
 189         else
 190         {
 191                 return DEFAULT_REL_PREFERENCE;
 192         }
 193
 194         if ((backup != rp->f_rel[kind]) && (NULL != pref_changed_cb))
 195         {
 196                 pref_changed_cb (pref_changed_cb_cls, &rp->id, kind, rp->f_rel[kind]);
 197         }
 198
 199         return rp->f_rel[kind];
 200 }
 201
 202 /**
 203  * Recalculate preference for a specific ATS property
 204  *
 205  * @param p the peer
 206  * @param kind the preference kind
 207  */
 208 static double
 209 recalculate_rel_preferences (struct PreferenceClient *c,
 210                                                                                                  struct PreferencePeer *p,
 211                                                                                                  enum GNUNET_ATS_PreferenceKind kind)
 212 {
 213         struct PreferencePeer *p_cur;
 214         struct PeerRelative *rp;
 215         double backup;
 216         double res;
 217         double ret;
 218
 219         /* For this client: sum preferences to total preference */
 220         c->f_abs_sum[kind] = 0;
 221         for (p_cur = c->p_head; NULL != p_cur; p_cur = p_cur->next)
 222                 c->f_abs_sum[kind] += p_cur->f_abs[kind];
 223         GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Client %p has total preference for %s of %.3f\n",
 224                         c->client,
 225                         GNUNET_ATS_print_preference_type (kind),
 226                         c->f_abs_sum[kind]);
 227
 228         ret = DEFAULT_REL_PREFERENCE;
 229         /* For all peers: calculate relative preference */
 230         for (p_cur = c->p_head; NULL != p_cur; p_cur = p_cur->next)
 231         {
 232                 /* Calculate relative preference for specific kind */
 233                 backup = p_cur->f_rel[kind];
 234                 if (DEFAULT_ABS_PREFERENCE == c->f_abs_sum[kind])
 235                                 /* No peer has a preference for this property, so set default preference */
 236                                 p_cur->f_rel[kind] = DEFAULT_REL_PREFERENCE;
 237                 else
 238                                 p_cur->f_rel[kind] = (c->f_abs_sum[kind] + p_cur->f_abs[kind]) / c->f_abs_sum[kind];
 239
 240                 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Client %p: peer `%s' has relative preference for %s of %.3f\n",
 241                                 c->client,
 242                                 GNUNET_i2s (&p_cur->id),
 243                                 GNUNET_ATS_print_preference_type (kind),
 244                                 p_cur->f_rel[kind]);
 245
 246                 res = 0.0;
 247                 if (p_cur->f_rel[kind] != backup)
 248                 {
 249                         /* Value changed, recalculate */
 250                         res = update_peers (&p_cur->id,kind);
 251                         if (0 == memcmp (&p->id, &p_cur->id, sizeof (struct GNUNET_PeerIdentity)))
 252                                 ret = res;
 253                 }
 254                 else
 255           {
 256                         /* Value did not chang, return old value*/
 257                         GNUNET_assert (NULL != (rp = GNUNET_CONTAINER_multihashmap_get (peers, &p->id.hashPubKey)));
 258                         ret = rp->f_rel[kind];
 259           }
 260         }
 261         return ret;
 262 }
 263
 264 static double
 265 update_preference (struct PreferenceClient *c,
 266                                                                          struct PreferencePeer *p,
 267                                                                          enum GNUNET_ATS_PreferenceKind kind,
 268                                                          float score_abs)
 269 {
 270         double score = score_abs;
 271
 272   /* Update preference value according to type */
 273   switch (kind) {
 274     case GNUNET_ATS_PREFERENCE_BANDWIDTH:
 275     case GNUNET_ATS_PREFERENCE_LATENCY:
 276       p->f_abs[kind] = (p->f_abs[kind] + score) / 2;
 277       break;
 278     case GNUNET_ATS_PREFERENCE_END:
 279       break;
 280     default:
 281       break;
 282   }
 283   return recalculate_rel_preferences (c, p, kind);
 284 }
 285
 286 static void
 287 preference_aging (void *cls, const struct GNUNET_SCHEDULER_TaskContext *tc)
 288 {
 289         int i;
 290         //double *t = NULL;
 291         double backup;
 292         struct PreferencePeer *p = cls;
 293         GNUNET_assert (NULL != p);
 294
 295         p->aging_task = GNUNET_SCHEDULER_NO_TASK;
 296
 297         GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Aging preferences for peer `%s'\n",
 298                 GNUNET_i2s (&p->id));
 299
 300   /* Issue for aging :
 301    *
 302    * Not for every peer preference values are set by default, so reducing the
 303    * absolute preference value does not help for aging because it does not have
 304    * influence on the relative values.
 305    *
 306    * So we have to reduce the relative value to have an immediate impact on
 307    * quota calculation. In addition we cannot call recalculate_preferences here
 308    * but instead reduce the absolute value to have an aging impact on future
 309    * calls to change_preference where recalculate_preferences is called
 310    *
 311    */
 312   /* Aging absolute values: */
 313   for (i = 0; i < GNUNET_ATS_PreferenceCount; i++)
 314   {
 315                         backup = p->f_abs[i];
 316                 if (p->f_abs[i] > DEFAULT_ABS_PREFERENCE)
 317                         p->f_abs[i] *= PREF_AGING_FACTOR;
 318                 if (backup != p->f_abs[i])
 319                 {
 320                         GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Aged preference for peer `%s' from %.3f to %.3f\n",
 321                         GNUNET_i2s (&p->id), backup, p->f_abs[i]);
 322                         recalculate_rel_preferences (p->client, p, i);
 323                 }
 324   }
 325   p->aging_task = GNUNET_SCHEDULER_add_delayed (PREF_AGING_INTERVAL,
 326                 &preference_aging, p);
 327 }
 328
 329 /**
 330  * Changes the preferences for a peer in the problem
 331  *
 332  * @param solver the solver handle
 333  * @param client the client with this preference
 334  * @param peer the peer to change the preference for
 335  * @param kind the kind to change the preference
 336  * @param score the normalized score
 337  */
 338 float
 339 GAS_normalization_change_preference (void *src,
 340                                          const struct GNUNET_PeerIdentity *peer,
 341                                          enum GNUNET_ATS_PreferenceKind kind,
 342                                          float score_abs)
 343 {
 344         float score_rel;
 345   struct PreferenceClient *c_cur;
 346   struct PreferencePeer *p_cur;
 347   struct PeerRelative *r_cur;
 348   int i;
 349
 350
 351   GNUNET_assert (NULL != src);
 352   GNUNET_assert (NULL != peer);
 353
 354   GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Client %p changes preference for peer `%s' for `%s' to %.2f\n",
 355                                 src,
 356                                 GNUNET_i2s (peer),
 357                                 GNUNET_ATS_print_preference_type (kind),
 358                                 score_abs);
 359
 360   if (kind >= GNUNET_ATS_PreferenceCount)
 361   {
 362       GNUNET_break (0);
 363       return 0.0;
 364   }
 365
 366   /* Find preference client */
 367   for (c_cur = pc_head; NULL != c_cur; c_cur = c_cur->next)
 368   {
 369       if (src == c_cur->client)
 370         break;
 371   }
 372   /* Not found: create new preference client */
 373   if (NULL == c_cur)
 374   {
 375     c_cur = GNUNET_malloc (sizeof (struct PreferenceClient));
 376     c_cur->client = src;
 377     GNUNET_CONTAINER_DLL_insert (pc_head, pc_tail, c_cur);
 378   }
 379
 380   /* Find entry for peer */
 381   for (p_cur = c_cur->p_head; NULL != p_cur; p_cur = p_cur->next)
 382     if (0 == memcmp (&p_cur->id, peer, sizeof (p_cur->id)))
 383         break;
 384
 385   /* Not found: create new peer entry */
 386   if (NULL == p_cur)
 387   {
 388       p_cur = GNUNET_malloc (sizeof (struct PreferencePeer));
 389       p_cur->client = c_cur;
 390       p_cur->id = (*peer);
 391       for (i = 0; i < GNUNET_ATS_PreferenceCount; i++)
 392       {
 393         /* Default value per peer absolut preference for a quality:
 394          * No value set, so absolute preference 0 */
 395         p_cur->f_abs[i] = DEFAULT_ABS_PREFERENCE;
 396         /* Default value per peer relative preference for a quality: 1.0 */
 397         p_cur->f_rel[i] = DEFAULT_REL_PREFERENCE;
 398       }
 399       p_cur->aging_task = GNUNET_SCHEDULER_add_delayed (PREF_AGING_INTERVAL, &preference_aging, p_cur);
 400       GNUNET_CONTAINER_DLL_insert (c_cur->p_head, c_cur->p_tail, p_cur);
 401   }
 402
 403   if (NULL == (r_cur = GNUNET_CONTAINER_multihashmap_get (peers, &peer->hashPubKey)))
 404   {
 405         r_cur = GNUNET_malloc (sizeof (struct PeerRelative));
 406         r_cur->id = (*peer);
 407         for (i = 0; i < GNUNET_ATS_PreferenceCount; i++)
 408                 r_cur->f_rel[i] = DEFAULT_REL_PREFERENCE;
 409         GNUNET_CONTAINER_multihashmap_put (peers, &r_cur->id.hashPubKey, r_cur, GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY);
 410   }
 411
 412   score_rel = update_preference (c_cur, p_cur, kind, score_abs);
 413   return score_rel;
 414 }
 415
 416 /**
 417  * Get the normalized preference values for a specific peer
 418  *
 419  * @param id the peer
 420  * @return pointer to the values, can be indexed with GNUNET_ATS_PreferenceKind, default preferences if peer does not exist
 421  */
 422 const double *
 423 GAS_normalization_get_preferences (struct GNUNET_PeerIdentity *id)
 424 {
 425         GNUNET_assert (NULL != peers);
 426         GNUNET_assert (NULL != id);
 427
 428         struct PeerRelative *rp;
 429         if (NULL == (rp = GNUNET_CONTAINER_multihashmap_get (peers, &id->hashPubKey)))
 430         {
 431                 return defvalues.f_rel;
 432         }
 433         return rp->f_rel;
 434 }
 435
 436
 437 void
 438 GAS_normalization_start (GAS_Normalization_preference_changed_cb pref_ch_cb, void *pref_ch_cb_cls)
 439 {
 440         int i;
 441         peers = GNUNET_CONTAINER_multihashmap_create(10, GNUNET_NO);
 442         pref_changed_cb = pref_ch_cb;
 443         pref_changed_cb_cls = pref_ch_cb_cls;
 444         for (i = 0; i < GNUNET_ATS_PreferenceCount; i++)
 445                 defvalues.f_rel[i] = DEFAULT_REL_PREFERENCE;
 446         return;
 447 }
 448
 449 static int
 450 free_peer (void *cls,
 451                          const struct GNUNET_HashCode * key,
 452                          void *value)
 453 {
 454         struct PeerRelative *rp = value;
 455         GNUNET_CONTAINER_multihashmap_remove (peers, key, value);
 456         GNUNET_free (rp);
 457         return GNUNET_OK;
 458 }
 459
 460 void
 461 GAS_normalization_stop ()
 462 {
 463   struct PreferenceClient *pc;
 464   struct PreferenceClient *next_pc;
 465   struct PreferencePeer *p;
 466   struct PreferencePeer *next_p;
 467
 468   next_pc = pc_head;
 469   while (NULL != (pc = next_pc))
 470   {
 471       next_pc = pc->next;
 472       GNUNET_CONTAINER_DLL_remove (pc_head, pc_tail, pc);
 473       next_p = pc->p_head;
 474       while (NULL != (p = next_p))
 475       {
 476           next_p = p->next;
 477           if (GNUNET_SCHEDULER_NO_TASK != p->aging_task)
 478           {
 479                 GNUNET_SCHEDULER_cancel(p->aging_task);
 480                 p->aging_task = GNUNET_SCHEDULER_NO_TASK;
 481           }
 482           GNUNET_CONTAINER_DLL_remove (pc->p_head, pc->p_tail, p);
 483           GNUNET_free (p);
 484       }
 485       GNUNET_free (pc);
 486   }
 487   GNUNET_CONTAINER_multihashmap_iterate (peers, &free_peer, NULL);
 488   GNUNET_CONTAINER_multihashmap_destroy (peers);
 489         return;
 490 }
 491
 492 /* end of gnunet-service-ats_normalization.c */