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
 133 struct GNUNET_CONTAINER_MultiHashMap *peers;
 134 struct PreferenceClient *pc_head;
 135 struct PreferenceClient *pc_tail;
 136 struct PeerRelative defvalues;
 137
 138
 139 static double
 140 update_peers (struct GNUNET_PeerIdentity *id,
 141                                                         enum GNUNET_ATS_PreferenceKind kind)
 142 {
 143         struct PreferenceClient *c_cur;
 144         struct PreferencePeer *p_cur;
 145         struct PeerRelative *rp;
 146         double f_rel_total;
 147         unsigned int count;
 148
 149         f_rel_total = 0.0;
 150         count = 0;
 151
 152         /* For all clients */
 153         for (c_cur = pc_head; NULL != c_cur; c_cur = c_cur->next)
 154         {
 155                 /* Find peer with id */
 156                 for (p_cur = c_cur->p_head; NULL != p_cur; p_cur = p_cur->next)
 157                 {
 158                         if (0 == memcmp (id, &p_cur->id, sizeof (struct GNUNET_PeerIdentity)))
 159                                 break;
 160                 }
 161                 if (NULL != p_cur)
 162                 {
 163                         /* Found peer with id */
 164                         f_rel_total +=  p_cur->f_rel[kind];
 165                         count ++;
 166                 }
 167         }
 168
 169         if (0 < count)
 170         {
 171                 /* Find a client */
 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",
 174                                 count,
 175                                 GNUNET_i2s (id),
 176                                 GNUNET_ATS_print_preference_type (kind),
 177                                 f_rel_total);
 178                 if (NULL != (rp = GNUNET_CONTAINER_multihashmap_get (peers, &id->hashPubKey)))
 179                 {
 180                         rp->f_rel[kind] = f_rel_total;
 181                 }
 182                 return f_rel_total;
 183         }
 184         else
 185         {
 186                 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "No clients have a total relative preference for peer `%s''s%s\n",
 187                                 count,
 188                                 GNUNET_i2s (id),
 189                                 GNUNET_ATS_print_preference_type (kind));
 190                 if (NULL != (rp = GNUNET_CONTAINER_multihashmap_get (peers, &id->hashPubKey)))
 191                 {
 192                         rp->f_rel[kind] = DEFAULT_REL_PREFERENCE;
 193                 }
 194                 return DEFAULT_REL_PREFERENCE;
 195         }
 196 }
 197
 198 /**
 199  * Recalculate preference for a specific ATS property
 200  *
 201  * @param p the peer
 202  * @param kind the preference kind
 203  */
 204 static double
 205 recalculate_rel_preferences (struct PreferenceClient *c,
 206                                                                                                  struct PreferencePeer *p,
 207                                                                                                  enum GNUNET_ATS_PreferenceKind kind)
 208 {
 209         struct PreferencePeer *p_cur;
 210         struct PeerRelative *rp;
 211         double backup;
 212         double res;
 213         double ret;
 214
 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",
 220                         c->client,
 221                         GNUNET_ATS_print_preference_type (kind),
 222                         c->f_abs_sum[kind]);
 223
 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)
 227         {
 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;
 233                 else
 234                                 p_cur->f_rel[kind] = (c->f_abs_sum[kind] + p_cur->f_abs[kind]) / c->f_abs_sum[kind];
 235
 236                 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Client %p: peer `%s' has relative preference for %s of %.3f\n",
 237                                 c->client,
 238                                 GNUNET_i2s (&p_cur->id),
 239                                 GNUNET_ATS_print_preference_type (kind),
 240                                 p_cur->f_rel[kind]);
 241
 242                 res = 0.0;
 243                 if (p_cur->f_rel[kind] != backup)
 244                 {
 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)))
 248                                 ret = res;
 249                 }
 250                 else
 251           {
 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];
 255           }
 256         }
 257         return ret;
 258 }
 259
 260 static double
 261 update_preference (struct PreferenceClient *c,
 262                                                                          struct PreferencePeer *p,
 263                                                                          enum GNUNET_ATS_PreferenceKind kind,
 264                                                          float score_abs)
 265 {
 266         double score = score_abs;
 267
 268   /* Update preference value according to type */
 269   switch (kind) {
 270     case GNUNET_ATS_PREFERENCE_BANDWIDTH:
 271     case GNUNET_ATS_PREFERENCE_LATENCY:
 272       p->f_abs[kind] = (p->f_abs[kind] + score) / 2;
 273       break;
 274     case GNUNET_ATS_PREFERENCE_END:
 275       break;
 276     default:
 277       break;
 278   }
 279   return recalculate_rel_preferences (c, p, kind);
 280 }
 281
 282 static void
 283 preference_aging (void *cls, const struct GNUNET_SCHEDULER_TaskContext *tc)
 284 {
 285         int i;
 286         //double *t = NULL;
 287         double backup;
 288         struct PreferencePeer *p = cls;
 289         GNUNET_assert (NULL != p);
 290
 291         p->aging_task = GNUNET_SCHEDULER_NO_TASK;
 292
 293         GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Aging preferences for peer `%s'\n",
 294                 GNUNET_i2s (&p->id));
 295
 296   /* Issue for aging :
 297    *
 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.
 301    *
 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
 306    *
 307    */
 308   /* Aging absolute values: */
 309   for (i = 0; i < GNUNET_ATS_PreferenceCount; i++)
 310   {
 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])
 315                 {
 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);
 319                 }
 320   }
 321   p->aging_task = GNUNET_SCHEDULER_add_delayed (PREF_AGING_INTERVAL,
 322                 &preference_aging, p);
 323 }
 324
 325 /**
 326  * Changes the preferences for a peer in the problem
 327  *
 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
 333  */
 334 float
 335 GAS_normalization_change_preference (void *src,
 336                                          const struct GNUNET_PeerIdentity *peer,
 337                                          enum GNUNET_ATS_PreferenceKind kind,
 338                                          float score_abs)
 339 {
 340         float score_rel;
 341   struct PreferenceClient *c_cur;
 342   struct PreferencePeer *p_cur;
 343   struct PeerRelative *r_cur;
 344   int i;
 345
 346
 347   GNUNET_assert (NULL != src);
 348   GNUNET_assert (NULL != peer);
 349
 350   GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Client %p changes preference for peer `%s' for `%s' to %.2f\n",
 351                                 src,
 352                                 GNUNET_i2s (peer),
 353                                 GNUNET_ATS_print_preference_type (kind),
 354                                 score_abs);
 355
 356   if (kind >= GNUNET_ATS_PreferenceCount)
 357   {
 358       GNUNET_break (0);
 359       return 0.0;
 360   }
 361
 362   /* Find preference client */
 363   for (c_cur = pc_head; NULL != c_cur; c_cur = c_cur->next)
 364   {
 365       if (src == c_cur->client)
 366         break;
 367   }
 368   /* Not found: create new preference client */
 369   if (NULL == c_cur)
 370   {
 371     c_cur = GNUNET_malloc (sizeof (struct PreferenceClient));
 372     c_cur->client = src;
 373     GNUNET_CONTAINER_DLL_insert (pc_head, pc_tail, c_cur);
 374   }
 375
 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)))
 379         break;
 380
 381   /* Not found: create new peer entry */
 382   if (NULL == p_cur)
 383   {
 384       p_cur = GNUNET_malloc (sizeof (struct PreferencePeer));
 385       p_cur->client = c_cur;
 386       p_cur->id = (*peer);
 387       for (i = 0; i < GNUNET_ATS_PreferenceCount; i++)
 388       {
 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;
 394       }
 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);
 397   }
 398
 399   if (NULL == (r_cur = GNUNET_CONTAINER_multihashmap_get (peers, &peer->hashPubKey)))
 400   {
 401         r_cur = GNUNET_malloc (sizeof (struct PeerRelative));
 402         r_cur->id = (*peer);
 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);
 406   }
 407
 408   score_rel = update_preference (c_cur, p_cur, kind, score_abs);
 409   return score_rel;
 410 }
 411
 412 /**
 413  * Get the normalized preference values for a specific peer
 414  *
 415  * @param id the peer
 416  * @return pointer to the values, can be indexed with GNUNET_ATS_PreferenceKind, default preferences if peer does not exist
 417  */
 418 const double *
 419 GAS_normalization_get_preferences (struct GNUNET_PeerIdentity *id)
 420 {
 421         struct PeerRelative *rp;
 422         if (NULL == (rp = GNUNET_CONTAINER_multihashmap_get (peers, &id->hashPubKey)))
 423         {
 424                 return defvalues.f_rel;
 425         }
 426         return rp->f_rel;
 427 }
 428
 429 void
 430 GAS_normalization_start ()
 431 {
 432         int i;
 433         peers = GNUNET_CONTAINER_multihashmap_create(10, GNUNET_NO);
 434
 435         for (i = 0; i < GNUNET_ATS_PreferenceCount; i++)
 436                 defvalues.f_rel[i] = DEFAULT_REL_PREFERENCE;
 437         return;
 438 }
 439
 440 static int
 441 free_peer (void *cls,
 442                          const struct GNUNET_HashCode * key,
 443                          void *value)
 444 {
 445         struct PeerRelative *rp = value;
 446         GNUNET_CONTAINER_multihashmap_remove (peers, key, value);
 447         GNUNET_free (rp);
 448         return GNUNET_OK;
 449 }
 450
 451 void
 452 GAS_normalization_stop ()
 453 {
 454   struct PreferenceClient *pc;
 455   struct PreferenceClient *next_pc;
 456   struct PreferencePeer *p;
 457   struct PreferencePeer *next_p;
 458
 459   next_pc = pc_head;
 460   while (NULL != (pc = next_pc))
 461   {
 462       next_pc = pc->next;
 463       GNUNET_CONTAINER_DLL_remove (pc_head, pc_tail, pc);
 464       next_p = pc->p_head;
 465       while (NULL != (p = next_p))
 466       {
 467           next_p = p->next;
 468           if (GNUNET_SCHEDULER_NO_TASK != p->aging_task)
 469           {
 470                 GNUNET_SCHEDULER_cancel(p->aging_task);
 471                 p->aging_task = GNUNET_SCHEDULER_NO_TASK;
 472           }
 473           GNUNET_CONTAINER_DLL_remove (pc->p_head, pc->p_tail, p);
 474           GNUNET_free (p);
 475       }
 476       GNUNET_free (pc);
 477   }
 478   GNUNET_CONTAINER_multihashmap_iterate (peers, &free_peer, NULL);
 479   GNUNET_CONTAINER_multihashmap_destroy (peers);
 480         return;
 481 }
 482
 483 /* end of gnunet-service-ats_normalization.c */