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 "float.h"
  29 #include "gnunet_util_lib.h"
  30 #include "gnunet-service-ats_addresses.h"
  31 #include "gnunet_statistics_service.h"
  32
  33 #define RIL_DEFAULT_STEP_TIME GNUNET_TIME_relative_multiply (GNUNET_TIME_UNIT_MILLISECONDS, 3000)
  34 #define RIL_DEFAULT_ALGORITHM RIL_ALGO_Q
  35 #define RIL_DEFAULT_DISCOUNT_FACTOR 0.5
  36 #define RIL_DEFAULT_GRADIENT_STEP_SIZE 0.4
  37 #define RIL_DEFAULT_TRACE_DECAY 0.6
  38 #define RIL_EXPLORE_RATIO 0.1
  39
  40 /**
  41  * ATS reinforcement learning solver
  42  *
  43  * General description
  44  */
  45
  46 enum RIL_Action_Type
  47 {
  48   RIL_ACTION_BW_IN_DBL = 0,
  49   RIL_ACTION_BW_OUT_DBL = 1,
  50   RIL_ACTION_BW_IN_HLV = 2,
  51   RIL_ACTION_BW_OUT_HLV = 3,
  52   RIL_ACTION_TYPE_NUM = 4
  53 };
  54 //TODO! add the rest of the actions
  55
  56 enum RIL_Algorithm
  57 {
  58   RIL_ALGO_SARSA = 0,
  59   RIL_ALGO_Q = 1
  60 };
  61
  62 enum RIL_E_Modification
  63 {
  64   RIL_E_SET, RIL_E_ZERO, RIL_E_ACCUMULATE, RIL_E_REPLACE
  65 };
  66
  67 /**
  68  * Global learning parameters
  69  */
  70 struct RIL_Learning_Parameters
  71 {
  72   /**
  73    * The TD-algorithm to use
  74    */
  75   enum RIL_Algorithm algorithm;
  76
  77   /**
  78    * Learning discount factor in the TD-update
  79    */
  80   float gamma;
  81
  82   /**
  83    * Gradient-descent step-size
  84    */
  85   float alpha;
  86
  87   /**
  88    * Trace-decay factor for eligibility traces
  89    */
  90   float lambda;
  91 };
  92
  93 struct RIL_Peer_Agent
  94 {
  95   /**
  96    * Next agent in solver's linked list
  97    */
  98   struct RIL_Peer_Agent *next;
  99
 100   /**
 101    * Previous agent in solver's linked list
 102    */
 103   struct RIL_Peer_Agent *prev;
 104
 105   /**
 106    * Environment handle
 107    */
 108   struct GAS_RIL_Handle *envi;
 109
 110   /**
 111    * Peer ID
 112    */
 113   struct GNUNET_PeerIdentity peer;
 114
 115   /**
 116    * Whether the agent is active or not
 117    */
 118   int active;
 119
 120   /**
 121    * Number of performed time-steps
 122    */
 123   unsigned long long step_count;
 124
 125   /**
 126    * Experience matrix W
 127    */
 128   double ** W;
 129
 130   /**
 131    * Number of rows of W / Number of state-vector features
 132    */
 133   int m;
 134
 135   /**
 136    * Number of columns of W / Number of actions
 137    */
 138   int n;
 139
 140   /**
 141    * Last perceived state feature vector
 142    */
 143   double * s_old;
 144
 145   /**
 146    * Last chosen action
 147    */
 148   int a_old;
 149
 150   /**
 151    * Eligibility trace vector
 152    */
 153   double * e;
 154
 155   /**
 156    * Address in use
 157    */
 158   struct ATS_Address * address;
 159
 160   /**
 161    * Inbound bandwidth assigned by the agent
 162    */
 163   unsigned long long bw_in;
 164
 165   /**
 166    * Outbound bandwidth assigned by the agent
 167    */
 168   unsigned long long bw_out;
 169 };
 170
 171 struct RIL_Network
 172 {
 173   /**
 174    * ATS network type
 175    */
 176   enum GNUNET_ATS_Network_Type type;
 177
 178   /**
 179    * Total available inbound bandwidth
 180    */
 181   unsigned long long bw_in_available;
 182
 183   /**
 184    * Total assigned outbound bandwidth
 185    */
 186   unsigned long long bw_in_assigned;
 187
 188   /**
 189    * Total available outbound bandwidth
 190    */
 191   unsigned long long bw_out_available;
 192
 193   /**
 194    * Total assigned outbound bandwidth
 195    */
 196   unsigned long long bw_out_assigned;
 197 };
 198
 199 struct RIL_Callbacks
 200 {
 201   /**
 202    * Bandwidth changed callback
 203    */
 204   GAS_bandwidth_changed_cb bw_changed;
 205
 206   /**
 207    * Bandwidth changed callback cls
 208    */
 209   void *bw_changed_cls;
 210
 211   /**
 212    * ATS function to get preferences
 213    */
 214   GAS_get_preferences get_preferences;
 215
 216   /**
 217    * Closure for ATS function to get preferences
 218    */
 219   void *get_preferences_cls;
 220
 221   /**
 222    * ATS function to get properties
 223    */
 224   GAS_get_properties get_properties;
 225
 226   /**
 227    * Closure for ATS function to get properties
 228    */
 229   void *get_properties_cls;
 230 };
 231
 232 /**
 233  * A handle for the reinforcement learning solver
 234  */
 235 struct GAS_RIL_Handle
 236 {
 237   /**
 238    * Statistics handle
 239    */
 240   struct GNUNET_STATISTICS_Handle *stats;
 241
 242   /**
 243    * Hashmap containing all valid addresses
 244    */
 245   const struct GNUNET_CONTAINER_MultiHashMap *addresses;
 246
 247   /**
 248    * Callbacks for the solver
 249    */
 250   struct RIL_Callbacks *callbacks;
 251
 252   /**
 253    * Bulk lock
 254    */
 255   int bulk_lock;
 256
 257   /**
 258    * Number of changes while solver was locked
 259    */
 260   int bulk_requests;
 261
 262   /**
 263    * Number of performed time-steps
 264    */
 265   unsigned long long step_count;
 266
 267   /**
 268    * Interval time between steps in milliseconds //TODO? put in agent
 269    */
 270   struct GNUNET_TIME_Relative step_time;
 271
 272   /**
 273    * Task identifier of the next time-step to be executed //TODO? put in agent
 274    */
 275   GNUNET_SCHEDULER_TaskIdentifier next_step;
 276
 277   /**
 278    * Learning parameters
 279    */
 280   struct RIL_Learning_Parameters parameters;
 281
 282   /**
 283    * Array of networks with global assignment state
 284    */
 285   struct RIL_Network * network_entries;
 286
 287   /**
 288    * Networks count
 289    */
 290   unsigned int networks_count;
 291
 292   /**
 293    * List of active peer-agents
 294    */
 295   struct RIL_Peer_Agent * agents_head;
 296   struct RIL_Peer_Agent * agents_tail;
 297 };
 298
 299 /**
 300  *  Private functions
 301  *  ---------------------------
 302  */
 303
 304 /**
 305  * Estimate the current action-value for state s and action a
 306  * @param agent agent performing the estimation
 307  * @param state s
 308  * @param action a
 309  * @return estimation value
 310  */
 311 static double
 312 agent_estimate_q (struct RIL_Peer_Agent *agent, double *state, int action)
 313 {
 314   int i;
 315   double result = 0;
 316
 317   for (i = 0; i < agent->m; i++)
 318   {
 319     result += state[i] * agent->W[action][i];
 320   }
 321
 322   return result;
 323 }
 324
 325 /**
 326  * Decide whether to do exploration (i.e. taking a new action) or exploitation (i.e. taking the
 327  * currently estimated best action) in the current step
 328  * @param agent agent performing the step
 329  * @return yes, if exploring
 330  */
 331 static int
 332 agent_decide_exploration (struct RIL_Peer_Agent *agent)
 333 {
 334   double r = (double) GNUNET_CRYPTO_random_u32 (GNUNET_CRYPTO_QUALITY_WEAK,
 335       UINT32_MAX) / (double) UINT32_MAX;
 336
 337   if (r < RIL_EXPLORE_RATIO)
 338   {
 339     return GNUNET_YES;
 340   }
 341   return GNUNET_NO;
 342 }
 343
 344 /**
 345  * Gets the action, with the maximal estimated Q-value (i.e. the one currently estimated to bring the
 346  * most reward in the future)
 347  * @param agent agent performing the calculation
 348  * @param state the state from which to take the action
 349  * @return the action promising most future reward
 350  */
 351 static int
 352 agent_get_action_best (struct RIL_Peer_Agent *agent, double *state)
 353 {
 354   int i;
 355   int max_i = -1;
 356   double cur_q;
 357   double max_q = -DBL_MAX;
 358
 359   for (i = 0; i < agent->n; i++)
 360   {
 361     cur_q = agent_estimate_q (agent, state, i);
 362     if (cur_q > max_q)
 363     {
 364       max_q = cur_q;
 365       max_i = i;
 366     }
 367   }
 368
 369   GNUNET_assert(-1 != max_i);
 370
 371   return max_i;
 372 }
 373
 374 /**
 375  * Gets any action, to explore the action space from that state
 376  * @param agent agent performing the calculation
 377  * @param state the state from which to take the action
 378  * @return any action
 379  */
 380 static int
 381 agent_get_action_explore (struct RIL_Peer_Agent *agent, double *state)
 382 {
 383   return GNUNET_CRYPTO_random_u32 (GNUNET_CRYPTO_QUALITY_WEAK, agent->n);
 384 }
 385
 386 /**
 387  * Updates the weights (i.e. coefficients) of the weight vector in matrix W for action a
 388  * @param agent the agent performing the update
 389  * @param reward the reward received for the last action
 390  * @param s_next the new state, the last step got the agent into
 391  * @param a_prime the new
 392  */
 393 static void
 394 agent_update_weights (struct RIL_Peer_Agent *agent,
 395     double reward,
 396     double *s_next,
 397     int a_prime)
 398 {
 399   int i;
 400   double delta;
 401   double *theta = agent->W[agent->a_old];
 402
 403   delta = reward + agent_estimate_q (agent, s_next, a_prime)
 404       - agent_estimate_q (agent, agent->s_old, agent->a_old);
 405   for (i = 0; i < agent->m; i++)
 406   {
 407     theta[i] += agent->envi->parameters.alpha * delta * (agent->e)[i];
 408   }
 409 }
 410
 411 /**
 412  * Changes the eligibility trace vector e in various manners:
 413  * RIL_E_ACCUMULATE - adds 1 to each component as in accumulating eligibility traces
 414  * RIL_E_REPLACE - resets each component to 1 as in replacing traces
 415  * RIL_E_SET - multiplies e with gamma and lambda as in the update rule
 416  * RIL_E_ZERO - sets e to 0 as in Watkin's Q-learning algorithm when exploring and when initializing
 417  * @param agent
 418  * @param mod
 419  */
 420 static void
 421 agent_modify_eligibility (struct RIL_Peer_Agent *agent,
 422     enum RIL_E_Modification mod)
 423 {
 424   int i;
 425   double *e = agent->e;
 426   double gamma = agent->envi->parameters.gamma;
 427   double lambda = agent->envi->parameters.lambda;
 428
 429   for (i = 0; i < agent->m; i++)
 430   {
 431     switch (mod)
 432     {
 433     case RIL_E_ACCUMULATE:
 434       e[i] += 1;
 435       break;
 436     case RIL_E_REPLACE:
 437       e[i] = 1;
 438       break;
 439     case RIL_E_SET:
 440       e[i] = gamma * lambda;
 441       break;
 442     case RIL_E_ZERO:
 443       e[i] = 0;
 444       break;
 445     }
 446   }
 447 }
 448
 449 static void
 450 envi_change_active_address (struct GAS_RIL_Handle *solver,
 451     struct RIL_Peer_Agent *agent,
 452     struct ATS_Address *new_address,
 453     unsigned long long new_bw_in,
 454     unsigned long long new_bw_out)
 455 {
 456   int notify = GNUNET_NO;
 457
 458   if (agent->address != new_address)
 459   {
 460     agent->address->active = GNUNET_NO;
 461     agent->address = new_address;
 462     agent->address->active = GNUNET_YES;
 463     agent->address->assigned_bw_in.value__ = htonl (agent->bw_in);
 464     agent->address->assigned_bw_out.value__ = htonl (agent->bw_out);
 465     notify |= GNUNET_YES;
 466   }
 467   if (agent->bw_in != new_bw_in)
 468   {
 469     agent->bw_in = new_bw_in;
 470     agent->address->assigned_bw_in.value__ = htonl (new_bw_out);
 471     notify |= GNUNET_YES;
 472   }
 473   if (agent->bw_out != new_bw_out)
 474   {
 475     agent->bw_out = new_bw_out;
 476     agent->address->assigned_bw_out.value__ = htonl (new_bw_out);
 477     notify |= GNUNET_YES;
 478   }
 479
 480
 481   if (notify)
 482   {
 483     solver->callbacks->bw_changed (solver->callbacks->bw_changed_cls,
 484             agent->address);
 485   }
 486 }
 487
 488 /**
 489  * Allocates a state vector and fills it with the features present
 490  * @param solver the solver handle
 491  * @return pointer to the state vector
 492  */
 493 static double *
 494 envi_get_state (struct GAS_RIL_Handle *solver)
 495 {
 496   int i;
 497   struct RIL_Network *net;
 498   double *state = GNUNET_malloc (sizeof (double) * solver->networks_count * 4);
 499
 500   for (i = 0; i < solver->networks_count; i++)
 501   {
 502     net = &solver->network_entries[i];
 503     state[i*4 + 0] = (double) net->bw_in_assigned;
 504     state[i*4 + 1] = (double) net->bw_in_available;
 505     state[i*4 + 2] = (double) net->bw_out_assigned;
 506     state[i*4 + 3] = (double) net->bw_out_available;
 507   }
 508
 509   return state;
 510 }
 511
 512 /**
 513  * Gets the reward of the last performed step
 514  * @param solver solver handle
 515  * @return the reward
 516  */
 517 static double
 518 envi_get_reward (struct GAS_RIL_Handle *solver, struct RIL_Peer_Agent *agent)
 519 {
 520   //TODO! implement reward calculation
 521
 522   return (double) GNUNET_CRYPTO_random_u32 (GNUNET_CRYPTO_QUALITY_WEAK,
 523       UINT32_MAX) / (double) UINT32_MAX;
 524 }
 525
 526 static void
 527 envi_action_bw_double (struct GAS_RIL_Handle *solver,
 528     struct RIL_Peer_Agent *agent,
 529     int direction_in)
 530 {
 531   if (direction_in)
 532   {
 533     envi_change_active_address(solver, agent, agent->address, agent->bw_in * 2, agent->bw_out);
 534   }
 535   else
 536   {
 537     envi_change_active_address(solver, agent, agent->address, agent->bw_in, agent->bw_out * 2);
 538   }
 539 }
 540
 541 static void
 542 envi_action_bw_halven (struct GAS_RIL_Handle *solver,
 543     struct RIL_Peer_Agent *agent,
 544     int direction_in)
 545 {
 546   uint32_t min_bw = ntohl (GNUNET_CONSTANTS_DEFAULT_BW_IN_OUT.value__);
 547   unsigned long long new_bw;
 548
 549   if (direction_in)
 550   {
 551     new_bw = agent->bw_in / 2;
 552     if (new_bw < min_bw)
 553       new_bw = min_bw;
 554     envi_change_active_address(solver, agent, agent->address, new_bw, agent->bw_out);
 555   }
 556   else
 557   {
 558     new_bw = agent->bw_out / 2;
 559     if (new_bw < min_bw)
 560       new_bw = min_bw;
 561     envi_change_active_address(solver, agent, agent->address, agent->bw_in, new_bw);
 562   }
 563 }
 564
 565 /**
 566  * Puts the action into effect
 567  * @param solver solver handle
 568  * @param action action to perform by the solver
 569  */
 570 static void
 571 envi_do_action (struct GAS_RIL_Handle *solver,
 572     struct RIL_Peer_Agent *agent,
 573     int action)
 574 {
 575   switch (action)
 576   {
 577   case RIL_ACTION_BW_IN_DBL:
 578     envi_action_bw_double (solver, agent, GNUNET_YES);
 579     break;
 580   case RIL_ACTION_BW_IN_HLV:
 581     envi_action_bw_halven (solver, agent, GNUNET_YES);
 582     break;
 583   case RIL_ACTION_BW_OUT_DBL:
 584     envi_action_bw_double (solver, agent, GNUNET_NO);
 585     break;
 586   case RIL_ACTION_BW_OUT_HLV:
 587     envi_action_bw_halven (solver, agent, GNUNET_NO);
 588     break;
 589   }
 590 }
 591
 592 /**
 593  * Performs one step of the Markov Decision Process. Other than in the literature the step starts
 594  * after having done the last action a_old. It observes the new state s_next and the reward
 595  * received. Then the coefficient update is done according to the SARSA or Q-learning method. The
 596  * next action is put into effect.
 597  * @param agent the agent performing the step
 598  */
 599 static void
 600 agent_step (struct RIL_Peer_Agent *agent)
 601 {
 602   int a_next = -1;
 603   double *s_next;
 604   double reward;
 605
 606   s_next = envi_get_state (agent->envi);
 607   reward = envi_get_reward (agent->envi, agent);
 608
 609   GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "agent_step() with algorithm %s\n",
 610       agent->envi->parameters.algorithm ? "Q" : "SARSA");
 611
 612   switch (agent->envi->parameters.algorithm)
 613   {
 614   case RIL_ALGO_SARSA:
 615     agent_modify_eligibility (agent, RIL_E_SET);
 616     if (agent_decide_exploration (agent))
 617     {
 618       a_next = agent_get_action_explore (agent, s_next);
 619     }
 620     else
 621     {
 622       a_next = agent_get_action_best (agent, s_next);
 623     }
 624     //updates weights with selected action (on-policy), if not first step
 625     if (-1 != agent->a_old)
 626       agent_update_weights (agent, reward, s_next, a_next);
 627     break;
 628
 629   case RIL_ALGO_Q:
 630     //updates weights with best action, disregarding actually selected action (off-policy), if not first step
 631     a_next = agent_get_action_best (agent, s_next);
 632     if (-1 != agent->a_old)
 633       agent_update_weights (agent, reward, s_next, a_next);
 634     if (agent_decide_exploration (agent))
 635     {
 636       a_next = agent_get_action_explore (agent, s_next);
 637       agent_modify_eligibility (agent, RIL_E_ZERO);
 638     }
 639     else
 640     {
 641       a_next = agent_get_action_best (agent, s_next);
 642       agent_modify_eligibility (agent, RIL_E_SET);
 643     }
 644     break;
 645   }
 646
 647   GNUNET_assert(-1 != a_next);
 648
 649   agent_modify_eligibility (agent, RIL_E_ACCUMULATE);
 650
 651   envi_do_action (agent->envi, agent, a_next);
 652
 653   GNUNET_free(agent->s_old);
 654   agent->s_old = s_next;
 655   agent->a_old = a_next;
 656
 657   agent->step_count += 1;
 658 }
 659
 660 /**
 661  * Cycles through all agents and lets the active ones do a step. Schedules the next step.
 662  * @param solver the solver handle
 663  * @param tc task context for the scheduler
 664  */
 665 static void
 666 ril_periodic_step (void *cls, const struct GNUNET_SCHEDULER_TaskContext *tc)
 667 {
 668   struct GAS_RIL_Handle *solver = cls;
 669   struct RIL_Peer_Agent *cur;
 670
 671   GNUNET_log(GNUNET_ERROR_TYPE_DEBUG, "RIL step number %d\n",
 672       solver->step_count);
 673
 674   for (cur = solver->agents_head; NULL != cur; cur = cur->next)
 675   {
 676     if (cur->active)
 677     {
 678       agent_step (cur);
 679     }
 680   }
 681
 682   solver->step_count += 1;
 683   solver->next_step = GNUNET_SCHEDULER_add_delayed (solver->step_time,
 684       &ril_periodic_step, solver);
 685 }
 686
 687 /**
 688  * Initialize an agent without addresses and its knowledge base
 689  * @param s ril solver
 690  * @param peer the one in question
 691  * @return handle to the new agent
 692  */
 693 static struct RIL_Peer_Agent *
 694 agent_init (void *s, const struct GNUNET_PeerIdentity *peer)
 695 {
 696   int i;
 697   struct GAS_RIL_Handle * solver = s;
 698   struct RIL_Peer_Agent * agent = GNUNET_malloc (sizeof (struct RIL_Peer_Agent));
 699
 700   agent->envi = solver;
 701   agent->peer = *peer;
 702   agent->step_count = 0;
 703   agent->active = GNUNET_NO;
 704   agent->s_old = envi_get_state (solver);
 705   agent->n = RIL_ACTION_TYPE_NUM;
 706   agent->m = solver->networks_count * 4;
 707   agent->W = (double **) GNUNET_malloc (sizeof (double) * agent->n);
 708   for (i = 0; i < agent->n; i++)
 709   {
 710     agent->W[i] = (double *) GNUNET_malloc (sizeof (double) * agent->m);
 711   }
 712   agent->a_old = -1;
 713   agent->e = (double *) GNUNET_malloc (sizeof (double) * agent->m);
 714   agent_modify_eligibility (agent, RIL_E_ZERO);
 715
 716   GNUNET_CONTAINER_DLL_insert_tail(solver->agents_head, solver->agents_tail,
 717       agent);
 718
 719   return agent;
 720 }
 721
 722 /**
 723  * Deallocate agent
 724  * @param s solver handle
 725  * @param agent the agent to retire
 726  */
 727 static void
 728 agent_die (struct GAS_RIL_Handle *solver, struct RIL_Peer_Agent *agent)
 729 {
 730   int i;
 731
 732   for (i = 0; i < agent->n; i++)
 733   {
 734     GNUNET_free(agent->W[i]);
 735   }
 736   GNUNET_free(agent->W);
 737   GNUNET_free(agent->e);
 738   GNUNET_free(agent->s_old);
 739 }
 740
 741 static void
 742 ril_remove_agent (struct GAS_RIL_Handle *s, struct RIL_Peer_Agent *agent)
 743 {
 744   struct RIL_Peer_Agent *cur_agent;
 745   struct RIL_Peer_Agent *next_agent;
 746
 747   cur_agent = s->agents_head;
 748   while (NULL != cur_agent)
 749   {
 750     next_agent = cur_agent->next;
 751
 752     if (agent == cur_agent)
 753     {
 754       GNUNET_CONTAINER_DLL_remove(s->agents_head, s->agents_tail, cur_agent);
 755       agent_die (s, cur_agent);
 756     }
 757
 758     cur_agent = next_agent;
 759   }
 760 }
 761
 762 /**
 763  * Counts the (active) agents
 764  * @param solver solver handle
 765  * @param active_only whether only active agents should be counted
 766  * @return number of agents
 767  */
 768 static int
 769 ril_count_agents (struct GAS_RIL_Handle *solver, int active_only)
 770 {
 771   int c;
 772   struct RIL_Peer_Agent *cur;
 773
 774   c = 0;
 775   for (cur = solver->agents_head; NULL != cur; cur = cur->next)
 776   {
 777     if ((!active_only) || (active_only && cur->active))
 778     {
 779       c += 1;
 780     }
 781   }
 782   return c;
 783 }
 784
 785
 786
 787 /**
 788  * Returns the agent for a peer
 789  * @param s solver handle
 790  * @param peer identity of the peer
 791  * @param create whether to create an agent if none is allocated yet
 792  * @return agent
 793  */
 794 static struct RIL_Peer_Agent *
 795 ril_get_agent (struct GAS_RIL_Handle *solver,
 796     const struct GNUNET_PeerIdentity *peer,
 797     int create)
 798 {
 799   struct RIL_Peer_Agent *cur;
 800
 801   for (cur = solver->agents_head; NULL != cur; cur = cur->next)
 802   {
 803     if (0 == GNUNET_CRYPTO_hash_cmp (&peer->hashPubKey, &cur->peer.hashPubKey))
 804     {
 805       return cur;
 806     }
 807   }
 808
 809   if (create)
 810     return agent_init (solver, peer);
 811   return NULL;
 812 }
 813
 814 static int
 815 ril_network_is_active (struct RIL_Network *network)
 816 {
 817   uint32_t min_bw = ntohl (GNUNET_CONSTANTS_DEFAULT_BW_IN_OUT.value__);
 818
 819   if (network->bw_out_available < min_bw)
 820     return GNUNET_NO;
 821   return GNUNET_YES;
 822 }
 823
 824 /**
 825  * Iterator, which allocates one agent per peer
 826  *
 827  * @param cls solver
 828  * @param key peer identity
 829  * @param value address
 830  * @return whether iterator should continue
 831  */
 832 static int
 833 ril_init_agents_it (void *cls, const struct GNUNET_HashCode *key, void *value)
 834 {
 835   struct GAS_RIL_Handle *solver = cls;
 836   struct ATS_Address *address = value;
 837   struct RIL_Peer_Agent *agent = NULL;
 838   uint32_t min_bw = ntohl (GNUNET_CONSTANTS_DEFAULT_BW_IN_OUT.value__);
 839
 840   if (ril_network_is_active(address->solver_information))
 841   {
 842     agent = ril_get_agent (solver, &address->peer, GNUNET_YES);
 843
 844     GNUNET_assert(NULL != agent);
 845
 846     if (NULL == agent->address)
 847     {
 848       agent->address = address;
 849       agent->address->active = GNUNET_YES;
 850       agent->bw_in = min_bw;
 851       agent->address->assigned_bw_in.value__ = htonl (min_bw);
 852       agent->bw_out = min_bw;
 853       agent->address->assigned_bw_out.value__ = htonl (min_bw);
 854     }
 855   }
 856   return GNUNET_YES;
 857 }
 858
 859 static void
 860 ril_get_new_address_or_delete (struct GAS_RIL_Handle *solver, struct RIL_Peer_Agent *agent)
 861 {
 862   uint32_t min_bw = ntohl (GNUNET_CONSTANTS_DEFAULT_BW_IN_OUT.value__);
 863   //get new address for agent or delete agent
 864
 865   agent->address = NULL; //forget current address
 866   GNUNET_CONTAINER_multihashmap_iterate (solver->addresses, &ril_init_agents_it,
 867       solver); //put another address
 868
 869   if (NULL == agent->address) //no other address available
 870   {
 871     agent->active = GNUNET_NO;
 872     ril_remove_agent(solver, agent);
 873   }
 874   else
 875   {
 876     envi_change_active_address(solver, agent, agent->address, min_bw, min_bw);
 877   }
 878 }
 879
 880 /**
 881  * Lookup network struct by type
 882  *
 883  * @param s the solver handle
 884  * @param type the network type
 885  * @return the network struct
 886  */
 887 static struct RIL_Network *
 888 ril_get_network (struct GAS_RIL_Handle *s, uint32_t type)
 889 {
 890   int i;
 891
 892   for (i = 0; i < s->networks_count; i++)
 893   {
 894     if (s->network_entries[i].type == type) {
 895       return &s->network_entries[i];
 896     }
 897   }
 898   return NULL;
 899 }
 900
 901 /**
 902  *  Solver API functions
 903  *  ---------------------------
 904  */
 905
 906 /**
 907  * Changes the preferences for a peer in the problem
 908  *
 909  * @param solver the solver handle
 910  * @param peer the peer to change the preference for
 911  * @param kind the kind to change the preference
 912  * @param pref_rel the normalized preference value for this kind over all clients
 913  */
 914 void
 915 GAS_ril_address_change_preference (void *s,
 916     const struct GNUNET_PeerIdentity *peer,
 917     enum GNUNET_ATS_PreferenceKind kind,
 918     double pref_rel)
 919 {
 920   GNUNET_log(GNUNET_ERROR_TYPE_DEBUG,
 921       "API_address_change_preference() Preference '%s' for peer '%s' changed to %.2f \n",
 922       GNUNET_ATS_print_preference_type (kind), GNUNET_i2s (peer), pref_rel);
 923   /*
 924    * Nothing to do here. Preferences are considered during reward calculation.
 925    */
 926 }
 927
 928 /**
 929  * Init the reinforcement learning problem solver
 930  *
 931  * Quotas:
 932  * network[i] contains the network type as type GNUNET_ATS_NetworkType[i]
 933  * out_quota[i] contains outbound quota for network type i
 934  * in_quota[i] contains inbound quota for network type i
 935  *
 936  * Example
 937  * network = {GNUNET_ATS_NET_UNSPECIFIED, GNUNET_ATS_NET_LOOPBACK, GNUNET_ATS_NET_LAN, GNUNET_ATS_NET_WAN, GNUNET_ATS_NET_WLAN}
 938  * network[2]   == GNUNET_ATS_NET_LAN
 939  * out_quota[2] == 65353
 940  * in_quota[2]  == 65353
 941  *
 942  * @param cfg configuration handle
 943  * @param stats the GNUNET_STATISTICS handle
 944  * @param network array of GNUNET_ATS_NetworkType with length dest_length
 945  * @param addresses hashmap containing all addresses
 946  * @param out_quota array of outbound quotas
 947  * @param in_quota array of outbound quota
 948  * @param dest_length array length for quota arrays
 949  * @param bw_changed_cb callback for changed bandwidth amounts
 950  * @param bw_changed_cb_cls cls for callback
 951  * @param get_preference callback to get relative preferences for a peer
 952  * @param get_preference_cls cls for callback to get relative preferences
 953  * @param get_properties_cls for callback to get relative properties
 954  * @param get_properties_cls cls for callback to get relative properties
 955  * @return handle for the solver on success, NULL on fail
 956  */
 957 void *
 958 GAS_ril_init (const struct GNUNET_CONFIGURATION_Handle *cfg,
 959     const struct GNUNET_STATISTICS_Handle *stats,
 960     const struct GNUNET_CONTAINER_MultiHashMap *addresses,
 961     int *network,
 962     unsigned long long *out_quota,
 963     unsigned long long *in_quota,
 964     int dest_length,
 965     GAS_bandwidth_changed_cb bw_changed_cb,
 966     void *bw_changed_cb_cls,
 967     GAS_get_preferences get_preference,
 968     void *get_preference_cls,
 969     GAS_get_properties get_properties,
 970     void *get_properties_cls)
 971 {
 972   int c;
 973   unsigned long long tmp;
 974   char *string;
 975   struct RIL_Network * cur;
 976   struct GAS_RIL_Handle *solver = GNUNET_malloc (sizeof (struct GAS_RIL_Handle));
 977
 978   GNUNET_log(GNUNET_ERROR_TYPE_DEBUG, "API_init() Initializing RIL solver\n");
 979
 980   GNUNET_assert(NULL != cfg);
 981   GNUNET_assert(NULL != stats);
 982   GNUNET_assert(NULL != network);
 983   GNUNET_assert(NULL != bw_changed_cb);
 984   GNUNET_assert(NULL != get_preference);
 985   GNUNET_assert(NULL != get_properties);
 986
 987   if (GNUNET_OK
 988       != GNUNET_CONFIGURATION_get_value_time (cfg, "ats", "RIL_STEP_TIME",
 989           &solver->step_time))
 990   {
 991     solver->step_time = RIL_DEFAULT_STEP_TIME;
 992   }
 993   if (GNUNET_OK
 994       == GNUNET_CONFIGURATION_get_value_string (cfg, "ats", "RIL_ALGORITHM",
 995           &string) && NULL != string && 0 == strcmp (string, "SARSA"))
 996   {
 997     solver->parameters.algorithm = RIL_ALGO_SARSA;
 998   }
 999   else
1000   {
1001     solver->parameters.algorithm = RIL_DEFAULT_ALGORITHM;
1002   }
1003   if (GNUNET_OK
1004       == GNUNET_CONFIGURATION_get_value_size (cfg, "ats", "RIL_DISCOUNT_FACTOR",
1005           &tmp))
1006   {
1007     solver->parameters.gamma = (double) tmp / 100;
1008   }
1009   else
1010   {
1011     solver->parameters.gamma = RIL_DEFAULT_DISCOUNT_FACTOR;
1012   }
1013   if (GNUNET_OK
1014       == GNUNET_CONFIGURATION_get_value_size (cfg, "ats",
1015           "RIL_GRADIENT_STEP_SIZE", &tmp))
1016   {
1017     solver->parameters.alpha = (double) tmp / 100;
1018   }
1019   else
1020   {
1021     solver->parameters.alpha = RIL_DEFAULT_GRADIENT_STEP_SIZE;
1022   }
1023   if (GNUNET_OK
1024       == GNUNET_CONFIGURATION_get_value_size (cfg, "ats", "RIL_TRACE_DECAY",
1025           &tmp))
1026   {
1027     solver->parameters.lambda = (double) tmp / 100;
1028   }
1029   else
1030   {
1031     solver->parameters.lambda = RIL_DEFAULT_TRACE_DECAY;
1032   }
1033
1034   solver->stats = (struct GNUNET_STATISTICS_Handle *) stats;
1035   solver->callbacks = GNUNET_malloc (sizeof (struct RIL_Callbacks));
1036   solver->callbacks->bw_changed = bw_changed_cb;
1037   solver->callbacks->bw_changed_cls = bw_changed_cb_cls;
1038   solver->callbacks->get_preferences = get_preference;
1039   solver->callbacks->get_preferences_cls = get_preference_cls;
1040   solver->callbacks->get_properties = get_properties;
1041   solver->callbacks->get_properties_cls = get_properties_cls;
1042   solver->networks_count = dest_length;
1043   solver->network_entries =
1044       GNUNET_malloc (dest_length * sizeof (struct RIL_Network));
1045   solver->bulk_lock = GNUNET_NO;
1046   solver->addresses = addresses;
1047   solver->step_count = 0;
1048
1049   for (c = 0; c < dest_length; c++)
1050   {
1051     cur = &solver->network_entries[c];
1052     cur->type = network[c];
1053     cur->bw_in_available = in_quota[c];
1054     cur->bw_in_assigned = 0;
1055     cur->bw_out_available = out_quota[c];
1056     cur->bw_out_assigned = 0;
1057   }
1058
1059   solver->next_step = GNUNET_SCHEDULER_add_delayed (
1060       GNUNET_TIME_relative_multiply (GNUNET_TIME_relative_get_millisecond_ (),
1061           1000), &ril_periodic_step, solver);
1062
1063   return solver;
1064 }
1065
1066 /**
1067  * Shutdown the reinforcement learning problem solver
1068  *
1069  * @param solver the respective handle to shutdown
1070  */
1071 void
1072 GAS_ril_done (void * solver)
1073 {
1074   struct GAS_RIL_Handle *s = solver;
1075   struct RIL_Peer_Agent *cur_agent;
1076   struct RIL_Peer_Agent *next_agent;
1077
1078   GNUNET_log(GNUNET_ERROR_TYPE_DEBUG, "API_done() Shutting down RIL solver\n");
1079
1080   cur_agent = s->agents_head;
1081   while (NULL != cur_agent)
1082   {
1083     next_agent = cur_agent->next;
1084     GNUNET_CONTAINER_DLL_remove(s->agents_head, s->agents_tail, cur_agent);
1085     agent_die (s, cur_agent);
1086     cur_agent = next_agent;
1087   }
1088
1089   GNUNET_SCHEDULER_cancel (s->next_step);
1090   GNUNET_free(s->callbacks);
1091   GNUNET_free(s->network_entries);
1092   GNUNET_free(s);
1093 }
1094
1095 /**
1096  * Add a single address within a network to the solver
1097  *
1098  * @param solver the solver Handle
1099  * @param address the address to add
1100  * @param network network type of this address
1101  */
1102 void
1103 GAS_ril_address_add (void *solver,
1104     struct ATS_Address *address,
1105     uint32_t network)
1106 {
1107   struct GAS_RIL_Handle *s = solver;
1108   //TODO! implement solver address add
1109   /*
1110    * if (new peer)
1111    *     initialize new agent
1112    * Add address
1113    * increase state vector
1114    * knowledge matrix
1115    * and action vector
1116    */
1117
1118   address->solver_information = ril_get_network(s, network);
1119
1120   /*
1121    * reiterate all addresses, create new agent if necessary and give the agent the address
1122    */
1123   GNUNET_CONTAINER_multihashmap_iterate (s->addresses, &ril_init_agents_it,
1124       solver);
1125
1126   GNUNET_log(GNUNET_ERROR_TYPE_DEBUG,
1127       "API_address_add() Added %s address for peer '%s'\n", address->plugin,
1128       GNUNET_i2s (&address->peer));
1129 }
1130
1131 /**
1132  * Remove an address from the solver
1133  *
1134  * @param solver the solver handle
1135  * @param address the address to remove
1136  * @param session_only delete only session not whole address
1137  */
1138 void
1139 GAS_ril_address_delete (void *solver,
1140     struct ATS_Address *address,
1141     int session_only)
1142 {
1143   //TODO! implement solver address delete
1144   //TODO! delete session only
1145   /*
1146    * remove address
1147    * if (last address of peer)
1148    *     remove agent
1149    * else
1150    *     decrease state vector
1151    *     decrease knowledge matrix
1152    *     decrease action vector
1153    */
1154   struct GAS_RIL_Handle *s = solver;
1155   struct RIL_Peer_Agent *agent;
1156
1157   GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "API_address_delete() deleting %s address %p for peer '%s'\n",
1158       address->active ? "active" : "inactive",
1159       address,
1160       GNUNET_i2s(&address->peer));
1161
1162   agent = ril_get_agent (s, &address->peer, GNUNET_NO);
1163
1164   if (NULL == agent)
1165   {
1166     GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "API_address_delete() deleting address for unallocated agent\n");
1167     return;
1168   }
1169
1170   if (address == agent->address) //if used address deleted
1171   {
1172     address->active = GNUNET_NO;
1173     ril_get_new_address_or_delete(s, agent);
1174   }
1175
1176   GNUNET_log(GNUNET_ERROR_TYPE_DEBUG,
1177       "API_address_delete() Deleted %s%s address for peer '%s'\n",
1178       session_only ? "session for " : "", address->plugin,
1179       GNUNET_i2s (&address->peer));
1180 }
1181
1182 /**
1183  * Transport properties for this address have changed
1184  *
1185  * @param solver solver handle
1186  * @param address the address
1187  * @param type the ATSI type in HBO
1188  * @param abs_value the absolute value of the property
1189  * @param rel_value the normalized value
1190  */
1191 void
1192 GAS_ril_address_property_changed (void *solver,
1193     struct ATS_Address *address,
1194     uint32_t type,
1195     uint32_t abs_value,
1196     double rel_value)
1197 {
1198   GNUNET_log(GNUNET_ERROR_TYPE_DEBUG,
1199       "API_address_property_changed() Property '%s' for peer '%s' address %p changed "
1200           "to %.2f \n", GNUNET_ATS_print_property_type (type),
1201       GNUNET_i2s (&address->peer), address, rel_value);
1202   /*
1203    * Nothing to do here, properties are considered in every reward calculation
1204    */
1205 }
1206
1207 /**
1208  * Transport session for this address has changed
1209  *
1210  * NOTE: values in addresses are already updated
1211  *
1212  * @param solver solver handle
1213  * @param address the address
1214  * @param cur_session the current session
1215  * @param new_session the new session
1216  */
1217 void
1218 GAS_ril_address_session_changed (void *solver,
1219     struct ATS_Address *address,
1220     uint32_t cur_session,
1221     uint32_t new_session)
1222 {
1223   //TODO? consider session changed in solver behaviour
1224   /*
1225    * Potentially add session activity as a feature in state vector
1226    */
1227   GNUNET_log(GNUNET_ERROR_TYPE_DEBUG, "API_address_session_changed()\n");
1228 }
1229
1230 /**
1231  * Usage for this address has changed
1232  *
1233  * NOTE: values in addresses are already updated
1234  *
1235  * @param solver solver handle
1236  * @param address the address
1237  * @param in_use usage state
1238  */
1239 void
1240 GAS_ril_address_inuse_changed (void *solver,
1241     struct ATS_Address *address,
1242     int in_use)
1243 {
1244   //TODO! consider address_inuse_changed according to matthias' email
1245   /**
1246    * See matthias' email
1247    */
1248   GNUNET_log(GNUNET_ERROR_TYPE_DEBUG,
1249       "API_address_inuse_changed() Usage for %s address of peer '%s' changed to %s\n",
1250       address->plugin, GNUNET_i2s (&address->peer),
1251       (GNUNET_YES == in_use) ? "USED" : "UNUSED");
1252 }
1253
1254 /**
1255  * Network scope for this address has changed
1256  *
1257  * NOTE: values in addresses are already updated
1258  *
1259  * @param solver solver handle
1260  * @param address the address
1261  * @param current_network the current network
1262  * @param new_network the new network
1263  */
1264 void
1265 GAS_ril_address_change_network (void *solver,
1266     struct ATS_Address *address,
1267     uint32_t current_network,
1268     uint32_t new_network)
1269 {
1270   struct GAS_RIL_Handle *s = solver;
1271   struct RIL_Peer_Agent *agent;
1272   struct RIL_Network *net;
1273
1274   GNUNET_log(GNUNET_ERROR_TYPE_DEBUG,
1275       "API_address_change_network() Network type changed, moving "
1276           "%s address of peer %s from '%s' to '%s'\n",
1277       (GNUNET_YES == address->active) ? "active" : "inactive",
1278       GNUNET_i2s (&address->peer),
1279       GNUNET_ATS_print_network_type (current_network),
1280       GNUNET_ATS_print_network_type (new_network));
1281
1282   address->solver_information = ril_get_network(solver, new_network);
1283
1284   if (address->active)
1285   {
1286     agent = ril_get_agent(solver, &address->peer, GNUNET_NO);
1287
1288     //remove from old network
1289     net = ril_get_network (s, current_network);
1290     net->bw_in_assigned -= agent->bw_in;
1291     net->bw_out_assigned -= agent->bw_out;
1292
1293     if (ril_network_is_active(ril_get_network(s, new_network)))
1294     {
1295       GNUNET_log(GNUNET_ERROR_TYPE_DEBUG, "New network is active\n");
1296       //add to new network
1297       net = ril_get_network (s, new_network);
1298       net->bw_in_assigned += agent->bw_in;
1299       net->bw_out_assigned += agent->bw_out;
1300
1301       GNUNET_log(GNUNET_ERROR_TYPE_DEBUG,
1302           "API_address_change_network() Moved %d inbound and %d "
1303               "outbound\n", agent->bw_in, agent->bw_out);
1304     }
1305     else //new network for this address is not active => address must not be considered
1306     {
1307       GNUNET_log(GNUNET_ERROR_TYPE_DEBUG, "New network is not active\n");
1308
1309       net = agent->address->solver_information;
1310       GNUNET_log(GNUNET_ERROR_TYPE_DEBUG, "Before: active address %p is %s\n", agent->address, GNUNET_ATS_print_network_type(net->type));
1311
1312       address->active = GNUNET_NO;
1313       ril_get_new_address_or_delete(s, agent);
1314
1315       net = agent->address->solver_information;
1316       GNUNET_log(GNUNET_ERROR_TYPE_DEBUG, "After: active address %p is %s\n", agent->address, GNUNET_ATS_print_network_type(net->type));
1317     }
1318   }
1319 }
1320
1321 /**
1322  * Get application feedback for a peer
1323  *
1324  * @param solver the solver handle
1325  * @param application the application
1326  * @param peer the peer to change the preference for
1327  * @param scope the time interval for this feedback: [now - scope .. now]
1328  * @param kind the kind to change the preference
1329  * @param score the score
1330  */
1331 void
1332 GAS_ril_address_preference_feedback (void *solver,
1333     void *application,
1334     const struct GNUNET_PeerIdentity *peer,
1335     const struct GNUNET_TIME_Relative scope,
1336     enum GNUNET_ATS_PreferenceKind kind,
1337     double score)
1338 {
1339   //TODO! collect reward until next reward calculation
1340   GNUNET_log(GNUNET_ERROR_TYPE_DEBUG,
1341       "API_address_preference_feedback() Peer '%s' got a feedback of %+.3f from application %s for "
1342           "preference %s for %d seconds\n", GNUNET_i2s (peer), "UNKNOWN",
1343       GNUNET_ATS_print_preference_type (kind), scope.rel_value_us / 1000000);
1344 }
1345
1346 /**
1347  * Start a bulk operation
1348  *
1349  * @param solver the solver
1350  */
1351 void
1352 GAS_ril_bulk_start (void *solver)
1353 {
1354   //TODO? consideration: keep bulk counter and stop agents during bulk
1355   /*
1356    * bulk counter up, but not really relevant, because there is no complete calculation of the
1357    * bandwidth assignment triggered anyway. Therefore, changes to addresses can come and go as
1358    * they want. Consideration: Step-pause during bulk-start-stop period...
1359    */
1360
1361   //GNUNET_log(GNUNET_ERROR_TYPE_DEBUG, "API_bulk_start()\n");
1362 }
1363
1364 /**
1365  * Bulk operation done
1366  */
1367 void
1368 GAS_ril_bulk_stop (void *solver)
1369 {
1370   //TODO? consideration: keep bulk counter and stop agents during bulk
1371   /*
1372    * bulk counter down, see bulk_start()
1373    */
1374
1375   //GNUNET_log(GNUNET_ERROR_TYPE_DEBUG, "API_bulk_stop()\n");
1376 }
1377
1378 /**
1379  * Get the preferred address for a specific peer
1380  *
1381  * @param solver the solver handle
1382  * @param peer the identity of the peer
1383  */
1384 const struct ATS_Address *
1385 GAS_ril_get_preferred_address (void *solver,
1386     const struct GNUNET_PeerIdentity *peer)
1387 {
1388   /*
1389    * activate agent, return currently chosen address
1390    */
1391   struct GAS_RIL_Handle *s = solver;
1392   struct RIL_Peer_Agent *agent;
1393
1394   agent = ril_get_agent (s, peer, GNUNET_NO);
1395
1396   if (NULL == agent)
1397   {
1398     GNUNET_log(GNUNET_ERROR_TYPE_DEBUG,
1399           "API_get_preferred_address() No agent for peer '%s' do not suggest address\n",
1400           GNUNET_i2s (peer));
1401     return NULL;
1402   }
1403
1404   agent->active = GNUNET_YES;
1405
1406   GNUNET_assert(NULL != agent->address);
1407
1408   GNUNET_log(GNUNET_ERROR_TYPE_DEBUG,
1409       "API_get_preferred_address() Activated agent for peer '%s' with %s address\n",
1410       GNUNET_i2s (peer), agent->address->plugin);
1411
1412   return agent->address;
1413 }
1414
1415 /**
1416  * Stop notifying about address and bandwidth changes for this peer
1417  *
1418  * @param solver the solver handle
1419  * @param peer the peer
1420  */
1421 void
1422 GAS_ril_stop_get_preferred_address (void *solver,
1423     const struct GNUNET_PeerIdentity *peer)
1424 {
1425   struct GAS_RIL_Handle *s = solver;
1426   struct RIL_Peer_Agent *agent;
1427
1428   agent = ril_get_agent (s, peer, GNUNET_NO);
1429   agent->active = GNUNET_NO;
1430
1431   GNUNET_log(GNUNET_ERROR_TYPE_DEBUG,
1432       "API_stop_get_preferred_address() Paused agent for peer '%s' with %s address\n",
1433       GNUNET_i2s (peer), agent->address->plugin);
1434 }
1435
1436 /* end of gnunet-service-ats-solver_ril.c */