src/ats/gnunet-service-ats-solver_ril.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-solver_ril.c
  23  * @brief ATS reinforcement learning solver
  24  * @author Fabian Oehlmann
  25  * @author Matthias Wachs
  26  */
  27 #include "platform.h"
  28 #include "gnunet_util_lib.h"
  29 #include "gnunet-service-ats_addresses.h"
  30 #include "gnunet_statistics_service.h"
  31
  32 #define RIL_DEFAULT_STEP_TIME GNUNET_TIME_relative_multiply (GNUNET_TIME_UNIT_MILLISECONDS, 3000)
  33 #define RIL_DEFAULT_DISCOUNT_FACTOR 0.5
  34 #define RIL_DEFAULT_GRADIENT_STEP_SIZE 0.4
  35 #define RIL_DEFAULT_TRACE_DECAY 0.6
  36
  37 /**
  38  * ATS reinforcement learning solver
  39  *
  40  * General description
  41  */
  42
  43 /**
  44  * Global learning parameters
  45  */
  46 struct RIL_Learning_Parameters
  47 {
  48         /**
  49          * Learning discount factor in the TD-update
  50          */
  51         float gamma;
  52
  53         /**
  54          * Gradient-descent step-size
  55          */
  56         float alpha;
  57
  58         /**
  59          * Trace-decay factor for eligibility traces
  60          */
  61         float lambda;
  62 };
  63
  64 struct RIL_Peer_Agent
  65 {
  66         /**
  67          * Next agent in solver's linked list
  68          */
  69         struct RIL_Peer_Agent *next;
  70
  71         /**
  72          * Previous agent in solver's linked list
  73          */
  74         struct RIL_Peer_Agent *prev;
  75
  76         /**
  77          * Peer ID
  78          */
  79         struct GNUNET_PeerIdentity peer;
  80
  81         /**
  82          * Experience matrix W
  83          */
  84         double ** W;
  85
  86         /**
  87          * Last perceived state feature vector
  88          */
  89         double * s_t;
  90
  91         /**
  92          * Last chosen action
  93          */
  94         double * a_t;
  95
  96         /**
  97          * Last eligibility trace vector
  98          */
  99         double * e_t;
 100 };
 101
 102 struct RIL_Network
 103 {
 104           /**
 105            * ATS network type
 106            */
 107           unsigned int type;
 108
 109           /**
 110            * Network description
 111            */
 112           char *desc;
 113
 114           /**
 115            * Total available inbound bandwidth
 116            */
 117           unsigned long long bw_in_available;
 118
 119           /**
 120            * Total assigned outbound bandwidth
 121            */
 122           unsigned long long bw_in_assigned;
 123
 124           /**
 125            * Total available outbound bandwidth
 126            */
 127           unsigned long long bw_out_available;
 128
 129           /**
 130            * Total assigned outbound bandwidth
 131            */
 132           unsigned long long bw_out_assigned;
 133 };
 134
 135 struct RIL_Callbacks
 136 {
 137           /**
 138            * Bandwidth changed callback
 139            */
 140           GAS_bandwidth_changed_cb bw_changed;
 141
 142           /**
 143            * Bandwidth changed callback cls
 144            */
 145           void *bw_changed_cls;
 146
 147           /**
 148            * ATS function to get preferences
 149            */
 150           GAS_get_preferences get_preferences;
 151
 152           /**
 153            * Closure for ATS function to get preferences
 154            */
 155           void *get_preferences_cls;
 156
 157           /**
 158            * ATS function to get properties
 159            */
 160           GAS_get_properties get_properties;
 161
 162           /**
 163            * Closure for ATS function to get properties
 164            */
 165           void *get_properties_cls;
 166 };
 167
 168 /**
 169  * A handle for the reinforcement learning solver
 170  */
 171 struct GAS_RIL_Handle
 172 {
 173         /**
 174         * Statistics handle
 175         */
 176         struct GNUNET_STATISTICS_Handle *stats;
 177
 178         /**
 179         * Hashmap containing all valid addresses
 180         */
 181         const struct GNUNET_CONTAINER_MultiHashMap *addresses;
 182
 183         /**
 184         * Callbacks for the solver
 185         */
 186         struct RIL_Callbacks callbacks;
 187
 188         /**
 189         * Bulk lock
 190         */
 191         int bulk_lock;
 192
 193         /**
 194         * Number of changes while solver was locked
 195         */
 196         int bulk_requests;
 197
 198         /**
 199         * Number of performed time-steps
 200         */
 201         unsigned long long step_count;
 202
 203         /**
 204         * Interval time between steps in milliseconds //TODO put in agent
 205         */
 206         struct GNUNET_TIME_Relative step_time;
 207
 208         /**
 209         * Task identifier of the next time-step to be executed //TODO put in agent
 210         */
 211         GNUNET_SCHEDULER_TaskIdentifier next_step;
 212
 213         /**
 214         * Learning parameters
 215         */
 216         struct RIL_Learning_Parameters parameters;
 217
 218         /**
 219         * Array of networks with global assignment state
 220         */
 221         struct RIL_Network * network_entries;
 222
 223         /**
 224         * Networks count
 225         */
 226         unsigned int networks_count;
 227
 228         /**
 229         * List of active peer-agents
 230         */
 231         struct RIL_Peer_Agent * agents_active_head;
 232         struct RIL_Peer_Agent * agents_active_tail;
 233
 234         /**
 235         * List of paused peer-agents
 236         */
 237         struct RIL_Peer_Agent * agents_paused_head;
 238         struct RIL_Peer_Agent * agents_paused_tail;
 239 };
 240
 241
 242 enum Actions
 243 {
 244         bw_dbl,
 245         bw_hlv
 246 };
 247 //TODO add the rest of the actions
 248
 249 /**
 250  *  Private functions
 251  *  ---------------------------
 252  */
 253
 254 void
 255 agent_periodic_step (void *solver,
 256                                 const struct GNUNET_SCHEDULER_TaskContext *tc)
 257 {
 258         /*
 259          * iterate over active agents and do a time step
 260          */
 261         struct GAS_RIL_Handle *s = solver;
 262
 263         GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "RIL step number %d\n", s->step_count);
 264
 265         s->step_count += 1;
 266         s->next_step = GNUNET_SCHEDULER_add_delayed (
 267                         s->step_time,
 268                         &agent_periodic_step,
 269                         solver);
 270 }
 271
 272 /**
 273  * Whether a peer already has an agent in a list
 274  * @param head of list
 275  * @param peer in question
 276  */
 277 int
 278 list_contains_agent (struct RIL_Peer_Agent * head,
 279                                         struct GNUNET_PeerIdentity * peer)
 280 {
 281         struct RIL_Peer_Agent * cur;
 282
 283         for (cur = head; NULL != cur; cur = cur->next)
 284         {
 285                 if (!memcmp (&(cur->peer.hashPubKey), &peer->hashPubKey, sizeof(struct GNUNET_HashCode)))
 286                 {
 287                         return GNUNET_YES;
 288                 }
 289         }
 290         return GNUNET_NO;
 291 }
 292
 293 /**
 294  * Iterator, which allocates one agent per peer
 295  *
 296  * @param cls solver
 297  * @param key peer identity
 298  * @param value address
 299  * @return whether iterator should continue
 300  */
 301 int
 302 init_agents_it (void *cls,
 303                                 const struct GNUNET_HashCode *key,
 304                                 void *value)
 305 {
 306         struct GAS_RIL_Handle *solver = cls;
 307         struct ATS_Address *address = value;
 308         struct RIL_Peer_Agent *agent;
 309
 310         if (!list_contains_agent (solver->agents_paused_head, &address->peer))
 311         {
 312                 agent = GNUNET_malloc (sizeof (struct RIL_Peer_Agent));
 313                 agent->peer = address->peer;
 314                 GNUNET_CONTAINER_DLL_insert (solver->agents_paused_head, solver->agents_paused_tail, agent);
 315         }
 316
 317         //TODO add address to agent
 318         return GNUNET_YES;
 319 }
 320
 321
 322
 323 /**
 324  *  Solver API functions
 325  *  ---------------------------
 326  */
 327
 328 /**
 329  * Changes the preferences for a peer in the problem
 330  *
 331  * @param solver the solver handle
 332  * @param peer the peer to change the preference for
 333  * @param kind the kind to change the preference
 334  * @param pref_rel the normalized preference value for this kind over all clients
 335  */
 336 void
 337 GAS_ril_address_change_preference (void *solver,
 338                                                                                         const struct GNUNET_PeerIdentity *peer,
 339                                                                                         enum GNUNET_ATS_PreferenceKind kind,
 340                                                                                         double pref_rel)
 341 {
 342         //TODO implement
 343
 344         /*
 345          * Probably nothing to do here. The preference is looked up during reward calculation and does
 346          * not trigger anything
 347          */
 348         GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "ril_address_change_preference() has been called\n");
 349 }
 350
 351
 352 /**
 353  * Init the reinforcement learning problem solver
 354  *
 355  * Quotas:
 356  * network[i] contains the network type as type GNUNET_ATS_NetworkType[i]
 357  * out_quota[i] contains outbound quota for network type i
 358  * in_quota[i] contains inbound quota for network type i
 359  *
 360  * Example
 361  * network = {GNUNET_ATS_NET_UNSPECIFIED, GNUNET_ATS_NET_LOOPBACK, GNUNET_ATS_NET_LAN, GNUNET_ATS_NET_WAN, GNUNET_ATS_NET_WLAN}
 362  * network[2]   == GNUNET_ATS_NET_LAN
 363  * out_quota[2] == 65353
 364  * in_quota[2]  == 65353
 365  *
 366  * @param cfg configuration handle
 367  * @param stats the GNUNET_STATISTICS handle
 368  * @param network array of GNUNET_ATS_NetworkType with length dest_length
 369  * @param addresses hashmap containing all addresses
 370  * @param out_quota array of outbound quotas
 371  * @param in_quota array of outbound quota
 372  * @param dest_length array length for quota arrays
 373  * @param bw_changed_cb callback for changed bandwidth amounts
 374  * @param bw_changed_cb_cls cls for callback
 375  * @param get_preference callback to get relative preferences for a peer
 376  * @param get_preference_cls cls for callback to get relative preferences
 377  * @param get_properties_cls for callback to get relative properties
 378  * @param get_properties_cls cls for callback to get relative properties
 379  * @return handle for the solver on success, NULL on fail
 380  */
 381 void *
 382 GAS_ril_init (const struct GNUNET_CONFIGURATION_Handle *cfg,
 383                                 const struct GNUNET_STATISTICS_Handle *stats,
 384                                 const struct GNUNET_CONTAINER_MultiHashMap *addresses,
 385                                 int *network,
 386                                 unsigned long long *out_quota,
 387                                 unsigned long long *in_quota,
 388                                 int dest_length,
 389                                 GAS_bandwidth_changed_cb bw_changed_cb,
 390                                 void *bw_changed_cb_cls,
 391                                 GAS_get_preferences get_preference,
 392                                 void *get_preference_cls,
 393                                 GAS_get_properties get_properties,
 394                                 void *get_properties_cls)
 395 {
 396         //TODO implement
 397         int c;
 398         unsigned long long tmp;
 399         struct RIL_Network * cur;
 400         struct GAS_RIL_Handle *solver = GNUNET_malloc (sizeof (struct GAS_RIL_Handle));
 401         char * net_str[GNUNET_ATS_NetworkTypeCount] = GNUNET_ATS_NetworkTypeString;
 402
 403         GNUNET_assert (NULL != cfg);
 404         GNUNET_assert (NULL != stats);
 405         GNUNET_assert (NULL != network);
 406         GNUNET_assert (NULL != bw_changed_cb);
 407         GNUNET_assert (NULL != get_preference);
 408         GNUNET_assert (NULL != get_properties);
 409
 410         if (GNUNET_OK != GNUNET_CONFIGURATION_get_value_time(cfg, "ats", "RIL_STEP_TIME", &solver->step_time))
 411         {
 412                 solver->step_time = RIL_DEFAULT_STEP_TIME;
 413         }
 414         if (GNUNET_OK == GNUNET_CONFIGURATION_get_value_size(cfg, "ats", "RIL_DISCOUNT_FACTOR", &tmp))
 415         {
 416                 solver->parameters.gamma = tmp;
 417         }
 418         else
 419         {
 420                 solver->parameters.gamma = RIL_DEFAULT_DISCOUNT_FACTOR;
 421         }
 422         if (GNUNET_OK == GNUNET_CONFIGURATION_get_value_size(cfg, "ats", "RIL_GRADIENT_STEP_SIZE", &tmp))
 423         {
 424                 solver->parameters.alpha = tmp;
 425         }
 426         else
 427         {
 428                 solver->parameters.alpha = RIL_DEFAULT_GRADIENT_STEP_SIZE;
 429         }
 430         if (GNUNET_OK == GNUNET_CONFIGURATION_get_value_size(cfg, "ats", "RIL_TRACE_DECAY", &tmp))
 431         {
 432                 solver->parameters.lambda = tmp;
 433         }
 434         else
 435         {
 436                 solver->parameters.lambda = RIL_DEFAULT_TRACE_DECAY;
 437         }
 438
 439         solver->stats = (struct GNUNET_STATISTICS_Handle *) stats;
 440         solver->callbacks.bw_changed = bw_changed_cb;
 441         solver->callbacks.bw_changed_cls = bw_changed_cb_cls;
 442         solver->callbacks.get_preferences = get_preference;
 443         solver->callbacks.get_preferences_cls = get_preference_cls;
 444         solver->callbacks.get_properties = get_properties;
 445         solver->callbacks.get_properties_cls = get_properties_cls;
 446         solver->networks_count = dest_length;
 447         solver->network_entries = GNUNET_malloc (dest_length * sizeof (struct RIL_Network));
 448         solver->bulk_lock = GNUNET_NO;
 449         solver->addresses = addresses;
 450         solver->step_count = 0;
 451
 452         for (c = 0; c < dest_length; c++)
 453         {
 454                 cur = &solver->network_entries[c];
 455                 cur->type = network[c];
 456                 cur->bw_in_available = in_quota[c];
 457                 cur->bw_in_assigned = 0;
 458                 cur->bw_out_available = out_quota[c];
 459                 cur->bw_out_assigned = 0;
 460                 cur->desc = net_str[c];
 461         }
 462
 463         c = GNUNET_CONTAINER_multihashmap_iterate (addresses, &init_agents_it, solver);
 464
 465         GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "ril_init() has been called\n");
 466         GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "RIL number of addresses: %d\n", c);
 467
 468         solver->next_step = GNUNET_SCHEDULER_add_delayed (
 469                                 GNUNET_TIME_relative_multiply (GNUNET_TIME_relative_get_millisecond_ (), 1000),
 470                                 &agent_periodic_step,
 471                                 solver);
 472
 473         return solver;
 474 }
 475
 476 /**
 477  * Shutdown the reinforcement learning problem solver
 478  *
 479  * @param solver the respective handle to shutdown
 480  */
 481 void
 482 GAS_ril_done (void * solver)
 483 {
 484         //TODO implement
 485         struct GAS_RIL_Handle *s = solver;
 486
 487         GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "ril_done() has been called\n");
 488
 489         GNUNET_SCHEDULER_cancel (s->next_step);
 490         GNUNET_free (s->network_entries);
 491         GNUNET_free (s);
 492 }
 493
 494
 495 /**
 496  * Add a single address within a network to the solver
 497  *
 498  * @param solver the solver Handle
 499  * @param address the address to add
 500  * @param network network type of this address
 501  */
 502 void
 503 GAS_ril_address_add (void *solver,
 504                                                         struct ATS_Address *address,
 505                                                         uint32_t network)
 506 {
 507         //TODO implement
 508         /*
 509          * if (new peer)
 510          *     initialize new agent
 511          * Add address
 512          * increase state vector
 513          * knowledge matrix
 514          * and action vector
 515          */
 516         GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "ril_address_add() has been called\n");
 517 }
 518
 519 /**
 520  * Remove an address from the solver
 521  *
 522  * @param solver the solver handle
 523  * @param address the address to remove
 524  * @param session_only delete only session not whole address
 525  */
 526 void
 527 GAS_ril_address_delete (void *solver,
 528     struct ATS_Address *address, int session_only)
 529 {
 530         //TODO implement
 531         /*
 532          * remove address
 533          * if (last address of peer)
 534          *     remove agent
 535          * else
 536          *     decrease state vector
 537          *     decrease knowledge matrix
 538          *     decrease action vector
 539          */
 540         GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "ril_address_delete() has been called\n");
 541 }
 542
 543 /**
 544  * Transport properties for this address have changed
 545  *
 546  * @param solver solver handle
 547  * @param address the address
 548  * @param type the ATSI type in HBO
 549  * @param abs_value the absolute value of the property
 550  * @param rel_value the normalized value
 551  */
 552 void
 553 GAS_ril_address_property_changed (void *solver,
 554                                                                                                                         struct ATS_Address *address,
 555                                                                                                                         uint32_t type,
 556                                                                                                                         uint32_t abs_value,
 557                                                                                                                         double rel_value)
 558 {
 559         //TODO implement
 560         /*
 561          * Like change_preference() not really interesting, since lookup happens anyway during reward
 562          * calculation
 563          */
 564         GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "ril_address_property_changed() has been called\n");
 565 }
 566
 567
 568 /**
 569  * Transport session for this address has changed
 570  *
 571  * NOTE: values in addresses are already updated
 572  *
 573  * @param solver solver handle
 574  * @param address the address
 575  * @param cur_session the current session
 576  * @param new_session the new session
 577  */
 578 void
 579 GAS_ril_address_session_changed (void *solver,
 580                                                                                                                         struct ATS_Address *address,
 581                                                                                                                         uint32_t cur_session,
 582                                                                                                                         uint32_t new_session)
 583 {
 584         //TODO implement
 585         /*
 586          * Potentially add session activity as a feature in state vector
 587          */
 588         GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "ril_address_session_changed() has been called\n");
 589 }
 590
 591
 592 /**
 593  * Usage for this address has changed
 594  *
 595  * NOTE: values in addresses are already updated
 596  *
 597  * @param solver solver handle
 598  * @param address the address
 599  * @param in_use usage state
 600  */
 601 void
 602 GAS_ril_address_inuse_changed (void *solver,
 603                                                                                                                         struct ATS_Address *address,
 604                                                                                                                         int in_use)
 605 {
 606         //TODO implement
 607         /**
 608          * See matthias' email
 609          */
 610         GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "ril_address_inuse_changed() has been called\n");
 611 }
 612
 613 /**
 614  * Network scope for this address has changed
 615  *
 616  * NOTE: values in addresses are already updated
 617  *
 618  * @param solver solver handle
 619  * @param address the address
 620  * @param current_network the current network
 621  * @param new_network the new network
 622  */
 623 void
 624 GAS_ril_address_change_network (void *solver,
 625                                                                                                                                            struct ATS_Address *address,
 626                                                                                                                                            uint32_t current_network,
 627                                                                                                                                            uint32_t new_network)
 628 {
 629         //TODO implement
 630         /*
 631          * update network
 632          */
 633         GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "ril_address_change_network() has been called\n");
 634 }
 635
 636 /**
 637  * Start a bulk operation
 638  *
 639  * @param solver the solver
 640  */
 641 void
 642 GAS_ril_bulk_start (void *solver)
 643 {
 644         //TODO implement
 645         /*
 646          * bulk counter up, but not really relevant, because there is no complete calculation of the
 647          * bandwidth assignment triggered anyway. Therefore, changes to addresses can come and go as
 648          * they want. Consideration: Step-pause during bulk-start-stop period...
 649          */
 650         GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "ril_bulk_start() has been called\n");
 651 }
 652
 653
 654 /**
 655  * Bulk operation done
 656  */
 657 void
 658 GAS_ril_bulk_stop (void *solver)
 659 {
 660         //TODO implement
 661         /*
 662          * bulk counter down, see bulk_start()
 663          */
 664         GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "ril_bulk_stop() has been called\n");
 665 }
 666
 667 /**
 668  * Get the preferred address for a specific peer
 669  *
 670  * @param solver the solver handle
 671  * @param peer the identity of the peer
 672  */
 673 const struct ATS_Address *
 674 GAS_ril_get_preferred_address (void *solver,
 675                                const struct GNUNET_PeerIdentity *peer)
 676 {
 677         //TODO implement
 678         /*
 679          * connect-only for requested peers, move agent to active list
 680          */
 681         struct GAS_RIL_Handle *s = solver;
 682
 683         GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "ril_get_preferred_address() has been called\n");
 684
 685         if (0 == GNUNET_CONTAINER_multihashmap_contains(s->addresses, &peer->hashPubKey))
 686         {
 687                 return GNUNET_CONTAINER_multihashmap_get(s->addresses, &peer->hashPubKey);
 688         }
 689
 690         GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "No address for peer in addresses\n");
 691         return NULL;
 692 }
 693
 694 /**
 695  * Stop notifying about address and bandwidth changes for this peer
 696  *
 697  * @param solver the solver handle
 698  * @param peer the peer
 699  */
 700 void
 701 GAS_ril_stop_get_preferred_address (void *solver,
 702                                      const struct GNUNET_PeerIdentity *peer)
 703 {
 704         //TODO implement
 705         /*
 706          * connect-only for requested peers, move agent to paused list
 707          */
 708         GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "ril_stop_get_preferred_address() has been called\n");
 709 }
 710
 711 /* end of gnunet-service-ats-solver_reinf.c */