src/ats/plugin_ats_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/plugin_ats_ril.c
  23  * @brief ATS reinforcement learning solver
  24  * @author Fabian Oehlmann
  25  * @author Matthias Wachs
  26  */
  27 #include "plugin_ats_ril.h"
  28
  29 #define LOG(kind,...) GNUNET_log_from (kind, "ats-ril",__VA_ARGS__)
  30
  31 #define MIN_BW ntohl (GNUNET_CONSTANTS_DEFAULT_BW_IN_OUT.value__)
  32
  33 #define RIL_ACTION_INVALID -1
  34 #define RIL_INTERVAL_EXPONENT 10
  35 #define RIL_UTILITY_MAX (double) GNUNET_ATS_MaxBandwidth
  36
  37 #define RIL_DEFAULT_STEP_TIME_MIN       GNUNET_TIME_relative_multiply (GNUNET_TIME_UNIT_MILLISECONDS, 500)
  38 #define RIL_DEFAULT_STEP_TIME_MAX       GNUNET_TIME_relative_multiply (GNUNET_TIME_UNIT_MILLISECONDS, 3000)
  39 #define RIL_DEFAULT_ALGORITHM           RIL_ALGO_SARSA
  40 #define RIL_DEFAULT_SELECT              RIL_SELECT_EGREEDY
  41 #define RIL_DEFAULT_DISCOUNT_BETA       1.0
  42 #define RIL_DEFAULT_DISCOUNT_GAMMA      0.5
  43 #define RIL_DEFAULT_GRADIENT_STEP_SIZE  0.1
  44 #define RIL_DEFAULT_TRACE_DECAY         0.5
  45 #define RIL_DEFAULT_EXPLORE_RATIO       0.1
  46 #define RIL_DEFAULT_RBF_DIVISOR             10
  47 #define RIL_DEFAULT_GLOBAL_REWARD_SHARE 0.5
  48 #define RIL_DEFAULT_TEMPERATURE         1.0
  49
  50 #define RIL_INC_DEC_STEP_SIZE           1
  51
  52 /**
  53  * ATS reinforcement learning solver
  54  *
  55  * General description
  56  */
  57
  58 /**
  59  * The actions, how an agent can manipulate the current assignment. I.e. how the bandwidth can be
  60  * changed for the currently chosen address. Not depicted in the enum are the actions of switching
  61  * to a particular address. The action of switching to address with index i is depicted by the
  62  * number (RIL_ACTION_TYPE_NUM + i).
  63  */
  64 enum RIL_Action_Type
  65 {
  66   RIL_ACTION_NOTHING = -1,
  67   RIL_ACTION_BW_IN_DBL = -2, //TODO! put actions back
  68   RIL_ACTION_BW_IN_HLV = -3,
  69   RIL_ACTION_BW_IN_INC = 0,
  70   RIL_ACTION_BW_IN_DEC = 1,
  71   RIL_ACTION_BW_OUT_DBL = -4,
  72   RIL_ACTION_BW_OUT_HLV = -5,
  73   RIL_ACTION_BW_OUT_INC = -6,
  74   RIL_ACTION_BW_OUT_DEC = -7,
  75   RIL_ACTION_TYPE_NUM = 2
  76 };
  77
  78 enum RIL_Algorithm
  79 {
  80   RIL_ALGO_SARSA = 0,
  81   RIL_ALGO_Q = 1
  82 };
  83
  84 enum RIL_Select
  85 {
  86   RIL_SELECT_EGREEDY,
  87   RIL_SELECT_SOFTMAX
  88 };
  89
  90 enum RIL_E_Modification
  91 {
  92   RIL_E_UPDATE,
  93   RIL_E_ZERO,
  94   RIL_E_ACCUMULATE,
  95   RIL_E_REPLACE
  96 };
  97
  98 /**
  99  * Global learning parameters
 100  */
 101 struct RIL_Learning_Parameters
 102 {
 103   /**
 104    * The TD-algorithm to use
 105    */
 106   enum RIL_Algorithm algorithm;
 107
 108   /**
 109    * Gradient-descent step-size
 110    */
 111   double alpha;
 112
 113   /**
 114    * Learning discount variable in the TD-update for semi-MDPs
 115    */
 116   double beta;
 117
 118   /**
 119    * Learning discount factor in the TD-update for MDPs
 120    */
 121   double gamma;
 122
 123   /**
 124    * Trace-decay factor for eligibility traces
 125    */
 126   double lambda;
 127
 128   /**
 129    * Softmax action-selection temperature
 130    */
 131   double temperature;
 132
 133   /**
 134    * State space divisor
 135    */
 136   unsigned long long int divisor;
 137
 138   /**
 139    * Action selection strategy;
 140    */
 141   enum RIL_Select select;
 142
 143   /**
 144    * Ratio, with what probability an agent should explore in the e-greed policy
 145    */
 146   double explore_ratio;
 147
 148   /**
 149    * How big the share of the global part of the reward signal is
 150    */
 151   double reward_global_share;
 152
 153   /**
 154    * Minimal interval time between steps in milliseconds
 155    */
 156   struct GNUNET_TIME_Relative step_time_min;
 157
 158   /**
 159    * Maximum interval time between steps in milliseconds
 160    */
 161   struct GNUNET_TIME_Relative step_time_max;
 162 };
 163
 164 /**
 165  * Wrapper for addresses to store them in agent's linked list
 166  */
 167 struct RIL_Address_Wrapped
 168 {
 169   /**
 170    * Next in DLL
 171    */
 172   struct RIL_Address_Wrapped *next;
 173
 174   /**
 175    * Previous in DLL
 176    */
 177   struct RIL_Address_Wrapped *prev;
 178
 179   /**
 180    * The address
 181    */
 182   struct ATS_Address *address_naked;
 183 };
 184
 185 struct RIL_Peer_Agent
 186 {
 187   /**
 188    * Next agent in solver's linked list
 189    */
 190   struct RIL_Peer_Agent *next;
 191
 192   /**
 193    * Previous agent in solver's linked list
 194    */
 195   struct RIL_Peer_Agent *prev;
 196
 197   /**
 198    * Environment handle
 199    */
 200   struct GAS_RIL_Handle *envi;
 201
 202   /**
 203    * Peer ID
 204    */
 205   struct GNUNET_PeerIdentity peer;
 206
 207   /**
 208    * Whether the agent is active or not
 209    */
 210   int is_active;
 211
 212   /**
 213    * Number of performed time-steps
 214    */
 215   unsigned long long step_count;
 216
 217   /**
 218    * Experience matrix W
 219    */
 220   double ** W;
 221
 222   /**
 223    * Number of rows of W / Number of state-vector features
 224    */
 225   unsigned int m;
 226
 227   /**
 228    * Number of columns of W / Number of actions
 229    */
 230   unsigned int n;
 231
 232   /**
 233    * Last perceived state feature vector
 234    */
 235   double * s_old;
 236
 237   /**
 238    * Last chosen action
 239    */
 240   int a_old;
 241
 242   /**
 243    * Eligibility traces
 244    */
 245   double ** E;
 246
 247   /**
 248    * Address in use
 249    */
 250   struct ATS_Address * address_inuse;
 251
 252   /**
 253    * Head of addresses DLL
 254    */
 255   struct RIL_Address_Wrapped * addresses_head;
 256
 257   /**
 258    * Tail of addresses DLL
 259    */
 260   struct RIL_Address_Wrapped * addresses_tail;
 261
 262   /**
 263    * Inbound bandwidth assigned by the agent
 264    */
 265   unsigned long long bw_in;
 266
 267   /**
 268    * Outbound bandwidth assigned by the agent
 269    */
 270   unsigned long long bw_out;
 271
 272   /**
 273    * Flag whether a suggestion has to be issued
 274    */
 275   int suggestion_issue;
 276
 277   /**
 278    * The address which has to be issued
 279    */
 280   struct ATS_Address * suggestion_address;
 281 };
 282
 283 struct RIL_Network
 284 {
 285   /**
 286    * ATS network type
 287    */
 288   enum GNUNET_ATS_Network_Type type;
 289
 290   /**
 291    * Total available inbound bandwidth
 292    */
 293   unsigned long long bw_in_available;
 294
 295   /**
 296    * Bandwidth inbound assigned in network after last step
 297    */
 298   unsigned long long bw_in_assigned;
 299
 300   /**
 301    * Total available outbound bandwidth
 302    */
 303   unsigned long long bw_out_available;
 304
 305   /**
 306    * * Bandwidth outbound assigned in network after last step
 307    */
 308   unsigned long long bw_out_assigned;
 309 };
 310
 311 /**
 312  * A handle for the reinforcement learning solver
 313  */
 314 struct GAS_RIL_Handle
 315 {
 316   /**
 317    * The solver-plugin environment of the solver-plugin API
 318    */
 319   struct GNUNET_ATS_PluginEnvironment *plugin_envi;
 320
 321   /**
 322    * Statistics handle
 323    */
 324   struct GNUNET_STATISTICS_Handle *stats;
 325
 326   /**
 327    * Number of performed steps
 328    */
 329   unsigned long long step_count;
 330
 331   /**
 332    * Timestamp for the last time-step
 333    */
 334   struct GNUNET_TIME_Absolute step_time_last;
 335
 336   /**
 337    * Task identifier of the next time-step to be executed
 338    */
 339   GNUNET_SCHEDULER_TaskIdentifier step_next_task_id;
 340
 341   /**
 342    * Variable discount factor, dependent on time between steps
 343    */
 344   double global_discount_variable;
 345
 346   /**
 347    * Integrated variable discount factor, dependent on time between steps
 348    */
 349   double global_discount_integrated;
 350
 351   /**
 352    * Lock for bulk operations
 353    */
 354   int bulk_lock;
 355
 356   /**
 357    * Number of changes during a lock
 358    */
 359   int bulk_changes;
 360
 361   /**
 362    * Learning parameters
 363    */
 364   struct RIL_Learning_Parameters parameters;
 365
 366   /**
 367    * Array of networks with global assignment state
 368    */
 369   struct RIL_Network * network_entries;
 370
 371   /**
 372    * Networks count
 373    */
 374   unsigned int networks_count;
 375
 376   /**
 377    * List of active peer-agents
 378    */
 379   struct RIL_Peer_Agent * agents_head;
 380   struct RIL_Peer_Agent * agents_tail;
 381
 382   /**
 383    * Shutdown
 384    */
 385   int done;
 386
 387   /**
 388    * Simulate steps, i.e. schedule steps immediately
 389    */
 390   unsigned long long simulate;
 391 };
 392
 393 /*
 394  *  Private functions
 395  *  ---------------------------
 396  */
 397
 398 static int
 399 ril_count_agents(struct GAS_RIL_Handle * solver);
 400
 401 static double
 402 agent_get_utility (struct RIL_Peer_Agent *agent)
 403 {
 404   return (double) agent->bw_in;
 405 }
 406
 407 /**
 408  * Estimate the current action-value for state s and action a
 409  *
 410  * @param agent agent performing the estimation
 411  * @param state s
 412  * @param action a
 413  * @return estimation value
 414  */
 415 static double
 416 agent_estimate_q (struct RIL_Peer_Agent *agent, double *state, int action)
 417 {
 418   int i;
 419   double result = 0;
 420
 421   for (i = 0; i < agent->m; i++)
 422   {
 423     result += state[i] * agent->W[action][i];
 424   }
 425
 426   GNUNET_assert(!isnan(result));
 427
 428   if (isinf(result))
 429   {
 430     return isinf(result) * UINT32_MAX; //TODO! prevent crash when learning diverges
 431   }
 432   return result;
 433 }
 434
 435
 436 /**
 437  * Decide whether to do exploration (i.e. taking a new action) or exploitation (i.e. taking the
 438  * currently estimated best action) in the current step
 439  *
 440  * @param agent agent performing the step
 441  * @return yes, if exploring
 442  */
 443 static int
 444 agent_decide_exploration (struct RIL_Peer_Agent *agent)
 445 {
 446   //TODO? Future Work: Improve exploration/exploitation trade-off by different mechanisms than e-greedy
 447   double r = (double) GNUNET_CRYPTO_random_u32 (GNUNET_CRYPTO_QUALITY_WEAK,
 448       UINT32_MAX) / (double) UINT32_MAX;
 449
 450   if (r < agent->envi->parameters.explore_ratio)
 451   {
 452     return GNUNET_YES;
 453   }
 454   return GNUNET_NO;
 455 }
 456
 457
 458 /**
 459  * Get the index of the address in the agent's list.
 460  *
 461  * @param agent agent handle
 462  * @param address address handle
 463  * @return the index, starting with zero
 464  */
 465 static int
 466 agent_address_get_index (struct RIL_Peer_Agent *agent, struct ATS_Address *address)
 467 {
 468   int i;
 469   struct RIL_Address_Wrapped *cur;
 470
 471   i = -1;
 472   for (cur = agent->addresses_head; NULL != cur; cur = cur->next)
 473   {
 474     i++;
 475     if (cur->address_naked == address)
 476       return i;
 477   }
 478   return i;
 479 }
 480
 481
 482 /**
 483  * Gets the wrapped address from the agent's list
 484  *
 485  * @param agent agent handle
 486  * @param address address handle
 487  * @return wrapped address
 488  */
 489 static struct RIL_Address_Wrapped *
 490 agent_address_get (struct RIL_Peer_Agent *agent, struct ATS_Address *address)
 491 {
 492   struct RIL_Address_Wrapped *cur;
 493
 494   for (cur = agent->addresses_head; NULL != cur; cur = cur->next)
 495     if (cur->address_naked == address)
 496       return cur;
 497   return NULL;
 498 }
 499
 500
 501 /**
 502  * Gets the action, with the maximal estimated Q-value (i.e. the one currently estimated to bring the
 503  * most reward in the future)
 504  *
 505  * @param agent agent performing the calculation
 506  * @param state the state from which to take the action
 507  * @return the action promising most future reward
 508  */
 509 static int
 510 agent_get_action_best (struct RIL_Peer_Agent *agent, double *state)
 511 {
 512   int i;
 513   int max_i = RIL_ACTION_INVALID;
 514   double cur_q;
 515   double max_q = -DBL_MAX;
 516
 517   for (i = 0; i < agent->n; i++)
 518   {
 519     cur_q = agent_estimate_q (agent, state, i);
 520     if (cur_q > max_q)
 521     {
 522       max_q = cur_q;
 523       max_i = i;
 524     }
 525   }
 526
 527   GNUNET_assert(RIL_ACTION_INVALID != max_i);
 528
 529   return max_i;
 530 }
 531
 532
 533 /**
 534  * Gets any action, to explore the action space from that state
 535  *
 536  * @param agent agent performing the calculation
 537  * @param state the state from which to take the action
 538  * @return any action
 539  */
 540 static int
 541 agent_get_action_explore (struct RIL_Peer_Agent *agent, double *state)
 542 {
 543   // TODO?: Future Work: Choose the action for exploration, which has been explored the least in this state
 544   return GNUNET_CRYPTO_random_u32 (GNUNET_CRYPTO_QUALITY_WEAK, agent->n);
 545 }
 546
 547
 548 /**
 549  * Updates the weights (i.e. coefficients) of the weight vector in matrix W for action a
 550  *
 551  * @param agent the agent performing the update
 552  * @param reward the reward received for the last action
 553  * @param s_next the new state, the last step got the agent into
 554  * @param a_prime the new
 555  */
 556 static void
 557 agent_update_weights (struct RIL_Peer_Agent *agent, double reward, double *s_next, int a_prime)
 558 {
 559   int i;
 560   double delta;
 561   double *theta = agent->W[agent->a_old];
 562
 563   delta = agent->envi->global_discount_integrated * reward; //reward
 564   delta += agent->envi->global_discount_variable * agent_estimate_q (agent, s_next, a_prime); //discounted future value
 565   delta -= agent_estimate_q (agent, agent->s_old, agent->a_old); //one step
 566
 567 //  LOG(GNUNET_ERROR_TYPE_INFO, "update()   Step# %llu  Q(s,a): %f  a: %f  r: %f  y: %f  Q(s+1,a+1) = %f  delta: %f\n",
 568 //      agent->step_count,
 569 //      agent_estimate_q (agent, agent->s_old, agent->a_old),
 570 //      agent->envi->parameters.alpha,
 571 //      reward,
 572 //      agent->envi->global_discount_variable,
 573 //      agent_estimate_q (agent, s_next, a_prime),
 574 //      delta);
 575
 576   for (i = 0; i < agent->m; i++)
 577   {
 578 //    LOG(GNUNET_ERROR_TYPE_INFO, "alpha = %f   delta = %f   e[%d] = %f\n",
 579 //        agent->envi->parameters.alpha,
 580 //        delta,
 581 //        i,
 582 //        agent->e[i]);
 583     theta[i] += agent->envi->parameters.alpha * delta * agent->s_old[i];// * agent->E[a_prime][i];
 584   }
 585 }
 586
 587
 588 /**
 589  * Changes the eligibility trace vector e in various manners:
 590  * #RIL_E_ACCUMULATE - adds @a feature to each component as in accumulating eligibility traces
 591  * #RIL_E_REPLACE - resets each component to @a feature  as in replacing traces
 592  * #RIL_E_SET - multiplies e with discount factor and lambda as in the update rule
 593  * #RIL_E_ZERO - sets e to 0 as in Watkin's Q-learning algorithm when exploring and when initializing
 594  *
 595  * @param agent the agent handle
 596  * @param mod the kind of modification
 597  * @param feature the feature vector
 598  */
 599 static void
 600 agent_modify_eligibility (struct RIL_Peer_Agent *agent,
 601                           enum RIL_E_Modification mod,
 602                           double *feature,
 603                           int action)
 604 {
 605   int i;
 606   int k;
 607
 608   for (i = 0; i < agent->m; i++)
 609   {
 610     switch (mod)
 611     {
 612     case RIL_E_ACCUMULATE:
 613       agent->E[action][i] += feature[i];
 614       break;
 615     case RIL_E_REPLACE:
 616       agent->E[action][i] =  (agent->envi->global_discount_variable * agent->envi->parameters.lambda * agent->E[action][i]) > feature[i] ? agent->E[action][i] : feature[i]; //TODO make replacing traces available
 617       break;
 618     case RIL_E_UPDATE:
 619       agent->E[action][i] *= agent->envi->global_discount_variable * agent->envi->parameters.lambda;
 620       break;
 621     case RIL_E_ZERO:
 622       for (k = 0; k < agent->n; k++)
 623       {
 624         agent->E[k][i] = 0;
 625       }
 626       break;
 627     }
 628   }
 629 }
 630
 631
 632 static void
 633 ril_inform (struct GAS_RIL_Handle *solver,
 634     enum GAS_Solver_Operation op,
 635     enum GAS_Solver_Status stat)
 636 {
 637   if (NULL != solver->plugin_envi->info_cb)
 638     solver->plugin_envi->info_cb (solver->plugin_envi->info_cb_cls, op, stat, GAS_INFO_NONE);
 639 }
 640
 641
 642 /**
 643  * Changes the active assignment suggestion of the handler and invokes the bw_changed callback to
 644  * notify ATS of its new decision
 645  *
 646  * @param solver solver handle
 647  * @param agent agent handle
 648  * @param new_address the address which is to be used
 649  * @param new_bw_in the new amount of inbound bandwidth set for this address
 650  * @param new_bw_out the new amount of outbound bandwidth set for this address
 651  * @param silent disables invocation of the bw_changed callback, if GNUNET_YES
 652  */
 653 static void
 654 envi_set_active_suggestion (struct GAS_RIL_Handle *solver,
 655     struct RIL_Peer_Agent *agent,
 656     struct ATS_Address *new_address,
 657     unsigned long long new_bw_in,
 658     unsigned long long new_bw_out,
 659     int silent)
 660 {
 661   int notify = GNUNET_NO;
 662
 663   LOG(GNUNET_ERROR_TYPE_DEBUG, "    set_active_suggestion() for peer '%s'\n", GNUNET_i2s (&agent->peer));
 664
 665   //address change
 666   if (agent->address_inuse != new_address)
 667   {
 668     if (NULL != agent->address_inuse)
 669     {
 670       agent->address_inuse->active = GNUNET_NO;
 671       agent->address_inuse->assigned_bw_in.value__ = htonl (0);
 672       agent->address_inuse->assigned_bw_out.value__ = htonl (0);
 673     }
 674     if (NULL != new_address)
 675     {
 676       LOG(GNUNET_ERROR_TYPE_DEBUG, "    set address active: %s\n", agent->is_active ? "yes" : "no");
 677       new_address->active = agent->is_active;
 678       new_address->assigned_bw_in.value__ = htonl (agent->bw_in);
 679       new_address->assigned_bw_out.value__ = htonl (agent->bw_out);
 680     }
 681     notify |= GNUNET_YES;
 682   }
 683
 684   if (new_address)
 685   {
 686     //activity change
 687     if (new_address->active != agent->is_active)
 688     {
 689       new_address->active = agent->is_active;
 690       notify |= GNUNET_YES;
 691     }
 692
 693     //bw change
 694     if (agent->bw_in != new_bw_in)
 695     {
 696       agent->bw_in = new_bw_in;
 697       new_address->assigned_bw_in.value__ = htonl (new_bw_in);
 698       notify |= GNUNET_YES;
 699     }
 700     if (agent->bw_out != new_bw_out)
 701     {
 702       agent->bw_out = new_bw_out;
 703       new_address->assigned_bw_out.value__ = htonl (new_bw_out);
 704       notify |= GNUNET_YES;
 705     }
 706   }
 707
 708   if (notify && agent->is_active && (GNUNET_NO == silent))
 709   {
 710     if (new_address)
 711     {
 712       LOG(GNUNET_ERROR_TYPE_DEBUG, "    envi_set_active_suggestion() notify\n");
 713       agent->suggestion_issue = GNUNET_YES;
 714       agent->suggestion_address = new_address;
 715     }
 716     else if (agent->address_inuse)
 717     {
 718       //disconnect case, no new address
 719       GNUNET_assert(0 == ntohl (agent->address_inuse->assigned_bw_in.value__));
 720       GNUNET_assert(0 == ntohl (agent->address_inuse->assigned_bw_out.value__));
 721       agent->bw_in = 0;
 722       agent->bw_out = 0;
 723
 724       agent->suggestion_issue = GNUNET_YES;
 725       agent->suggestion_address = agent->address_inuse;
 726     }
 727   }
 728   agent->address_inuse = new_address;
 729 }
 730
 731
 732 static unsigned long long
 733 ril_network_get_assigned (struct GAS_RIL_Handle *solver, enum GNUNET_ATS_Network_Type type, int direction_in)
 734 {
 735   struct RIL_Peer_Agent *cur;
 736   struct RIL_Network *net;
 737   unsigned long long sum = 0;
 738
 739   for (cur = solver->agents_head; NULL != cur; cur = cur->next)
 740   {
 741     if (cur->is_active && cur->address_inuse)
 742     {
 743       net = cur->address_inuse->solver_information;
 744       if (net->type == type)
 745       {
 746         if (direction_in)
 747           sum += cur->bw_in;
 748         else
 749           sum += cur->bw_out;
 750       }
 751     }
 752   }
 753
 754   return sum;
 755 }
 756
 757 /**
 758  * Allocates a state vector and fills it with the features present
 759  * @param solver the solver handle
 760  * @param agent the agent handle
 761  * @return pointer to the state vector
 762  */
 763 static double *
 764 envi_get_state (struct GAS_RIL_Handle *solver, struct RIL_Peer_Agent *agent)
 765 {
 766   double *state;
 767   double y[2];
 768   double x[2];
 769   double d[2];
 770   double sigma;
 771   double f;
 772   int m;
 773   int i;
 774   int k;
 775
 776   state = GNUNET_malloc (sizeof(double) * agent->m);
 777
 778   y[0] = (double) agent->bw_out;
 779   y[1] = (double) agent->bw_in;
 780
 781   m = agent_address_get_index (agent, agent->address_inuse) * (solver->parameters.divisor+1) * (solver->parameters.divisor+1);
 782   for (i = 0; i <= solver->parameters.divisor; i++)
 783   {
 784     for (k = 0; k <= solver->parameters.divisor; k++)
 785     {
 786       x[0] = i * GNUNET_ATS_MaxBandwidth / solver->parameters.divisor;
 787       x[1] = k * GNUNET_ATS_MaxBandwidth / solver->parameters.divisor;
 788       d[0] = x[0]-y[0];
 789       d[1] = x[1]-y[1];
 790       sigma = ((double) GNUNET_ATS_MaxBandwidth / 2) * M_SQRT2;
 791       f = exp(-((d[0]*d[0] + d[1]*d[1]) / (2 * sigma * sigma)));
 792       state[m++] = f;
 793     }
 794   }
 795
 796   return state;
 797 }
 798
 799 ///*
 800 // * For all networks a peer has an address in, this gets the maximum bandwidth which could
 801 // * theoretically be available in one of the networks. This is used for bandwidth normalization.
 802 // *
 803 // * @param agent the agent handle
 804 // * @param direction_in whether the inbound bandwidth should be considered. Returns the maximum outbound bandwidth if GNUNET_NO
 805 // */
 806 //static unsigned long long
 807 //ril_get_max_bw (struct RIL_Peer_Agent *agent, int direction_in)
 808 //{
 809 //  /*
 810 //   * get the maximum bandwidth possible for a peer, e.g. among all addresses which addresses'
 811 //   * network could provide the maximum bandwidth if all that bandwidth was used on that one peer.
 812 //   */
 813 //  unsigned long long max = 0;
 814 //  struct RIL_Address_Wrapped *cur;
 815 //  struct RIL_Network *net;
 816 //
 817 //  for (cur = agent->addresses_head; NULL != cur; cur = cur->next)
 818 //  {
 819 //    net = cur->address_naked->solver_information;
 820 //    if (direction_in)
 821 //    {
 822 //      if (net->bw_in_available > max)
 823 //      {
 824 //        max = net->bw_in_available;
 825 //      }
 826 //    }
 827 //    else
 828 //    {
 829 //      if (net->bw_out_available > max)
 830 //      {
 831 //        max = net->bw_out_available;
 832 //      }
 833 //    }
 834 //  }
 835 //  return max;
 836 //}
 837
 838 ///*
 839 // * Get the index of the quality-property in question
 840 // *
 841 // * @param type the quality property type
 842 // * @return the index
 843 // */
 844 //static int
 845 //ril_find_property_index (uint32_t type)
 846 //{
 847 //  int existing_types[] = GNUNET_ATS_QualityProperties;
 848 //  int c;
 849 //  for (c = 0; c < GNUNET_ATS_QualityPropertiesCount; c++)
 850 //    if (existing_types[c] == type)
 851 //      return c;
 852 //  return GNUNET_SYSERR;
 853 //}
 854
 855 //static int
 856 //ril_get_atsi (struct ATS_Address *address, uint32_t type)
 857 //{
 858 //  int c1;
 859 //  GNUNET_assert(NULL != address);
 860 //
 861 //  if ((NULL == address->atsi) || (0 == address->atsi_count))
 862 //    return 0;
 863 //
 864 //  for (c1 = 0; c1 < address->atsi_count; c1++)
 865 //  {
 866 //    if (ntohl (address->atsi[c1].type) == type)
 867 //      return ntohl (address->atsi[c1].value);
 868 //  }
 869 //  return 0;
 870 //}
 871
 872 //static double
 873 //envi_reward_global (struct GAS_RIL_Handle *solver)
 874 //{
 875 //  int i;
 876 //  struct RIL_Network net;
 877 //  unsigned int sum_in_available = 0;
 878 //  unsigned int sum_out_available = 0;
 879 //  unsigned int sum_in_assigned = 0;
 880 //  unsigned int sum_out_assigned = 0;
 881 //  double ratio_in;
 882 //  double ratio_out;
 883 //
 884 //  for (i = 0; i < solver->networks_count; i++)
 885 //  {
 886 //    net = solver->network_entries[i];
 887 //    sum_in_available += net.bw_in_available;
 888 //    sum_in_assigned += net.bw_in_assigned;
 889 //    sum_out_available += net.bw_out_available;
 890 //    sum_out_assigned += net.bw_out_assigned;
 891 //  }
 892 //
 893 //  ratio_in = ((double) sum_in_assigned) / ((double) sum_in_available);
 894 //  ratio_out = ((double) sum_out_assigned) / ((double) sum_out_available);
 895 //
 896 //  // global reward in [1,2]
 897 //  return ratio_in +1;
 898 //  return ((ratio_in + ratio_out) / 2) + 1;
 899 //}
 900
 901 //static double
 902 //envi_reward_local (struct GAS_RIL_Handle *solver, struct RIL_Peer_Agent *agent)
 903 //{
 904 //  const double *preferences;
 905 //  const double *properties;
 906 //  int prop_index;
 907 //  double pref_match = 0;
 908 //  double bw_norm;
 909 //  double dl_norm;
 910 //
 911 //  preferences = solver->plugin_envi->get_preferences (solver->plugin_envi->get_preference_cls,
 912 //      &agent->peer);
 913 //  properties = solver->plugin_envi->get_property (solver->plugin_envi->get_property_cls,
 914 //      agent->address_inuse);
 915 //
 916 //  // delay in [0,1]
 917 //  prop_index = ril_find_property_index (GNUNET_ATS_QUALITY_NET_DELAY);
 918 //  dl_norm = 2 - properties[prop_index]; //invert property as we want to maximize for lower latencies
 919 //
 920 //  // utilization in [0,1]
 921 //  bw_norm = (((double) ril_get_atsi (agent->address_inuse, GNUNET_ATS_UTILIZATION_IN)
 922 //      / (double) ril_get_max_bw (agent, GNUNET_YES))
 923 //      + ((double) ril_get_atsi (agent->address_inuse, GNUNET_ATS_UTILIZATION_OUT)
 924 //          / (double) ril_get_max_bw (agent, GNUNET_NO))) / 2;
 925 //
 926 //  // preference matching in [0,4]
 927 //  pref_match += (preferences[GNUNET_ATS_PREFERENCE_LATENCY] * dl_norm);
 928 //  pref_match += (preferences[GNUNET_ATS_PREFERENCE_BANDWIDTH] * bw_norm);
 929 //
 930 //  // local reward in [1,2]
 931 //  return (pref_match / 4) +1;
 932 //}
 933
 934 static double
 935 envi_get_collective_utility (struct GAS_RIL_Handle *solver)
 936 {
 937   //TODO! add nash product
 938   struct RIL_Peer_Agent *cur;
 939   double result = RIL_UTILITY_MAX;
 940
 941   for (cur = solver->agents_head; NULL != cur; cur = cur->next)
 942   {
 943     if (cur->is_active)
 944     {
 945       if (cur->address_inuse)
 946       {
 947         result = GNUNET_MIN(result, agent_get_utility(cur));
 948       }
 949     }
 950   }
 951
 952   return result;
 953 }
 954
 955 /**
 956  * Gets the reward for the last performed step, which is calculated in equal
 957  * parts from the local (the peer specific) and the global (for all peers
 958  * identical) reward.
 959  *
 960  * @param solver the solver handle
 961  * @param agent the agent handle
 962  * @return the reward
 963  */
 964 static double
 965 envi_get_reward (struct GAS_RIL_Handle *solver, struct RIL_Peer_Agent *agent)
 966 {
 967   struct RIL_Network *net;
 968
 969   unsigned long long objective;
 970
 971   LOG(GNUNET_ERROR_TYPE_INFO, "address: %x\n", agent->address_inuse);
 972   net = agent->address_inuse->solver_information;
 973   if (net->bw_in_assigned > net->bw_in_available)
 974   {
 975     objective = net->bw_in_available - net->bw_in_assigned;
 976   }
 977   else
 978   {
 979     objective = envi_get_collective_utility(solver);
 980   }
 981
 982   return objective;
 983 }
 984
 985 /**
 986  * Doubles the bandwidth for the active address
 987  *
 988  * @param solver solver handle
 989  * @param agent agent handle
 990  * @param direction_in if GNUNET_YES, change inbound bandwidth, otherwise the outbound bandwidth
 991  */
 992 static void
 993 envi_action_bw_double (struct GAS_RIL_Handle *solver,
 994     struct RIL_Peer_Agent *agent,
 995     int direction_in)
 996 {
 997   unsigned long long new_bw;
 998
 999   if (direction_in)
1000   {
1001     new_bw = agent->bw_in * 2;
1002     if (new_bw < agent->bw_in || new_bw > GNUNET_ATS_MaxBandwidth)
1003       new_bw = GNUNET_ATS_MaxBandwidth;
1004     envi_set_active_suggestion (solver, agent, agent->address_inuse, new_bw,
1005         agent->bw_out, GNUNET_NO);
1006   }
1007   else
1008   {
1009     new_bw = agent->bw_out * 2;
1010     if (new_bw < agent->bw_out || new_bw > GNUNET_ATS_MaxBandwidth)
1011       new_bw = GNUNET_ATS_MaxBandwidth;
1012     envi_set_active_suggestion (solver, agent, agent->address_inuse, agent->bw_in,
1013         new_bw, GNUNET_NO);
1014   }
1015 }
1016
1017 /**
1018  * Cuts the bandwidth for the active address in half. The least amount of bandwidth suggested, is
1019  * the minimum bandwidth for a peer, in order to not invoke a disconnect.
1020  *
1021  * @param solver solver handle
1022  * @param agent agent handle
1023  * @param direction_in if GNUNET_YES, change inbound bandwidth, otherwise change the outbound
1024  * bandwidth
1025  */
1026 static void
1027 envi_action_bw_halven (struct GAS_RIL_Handle *solver,
1028     struct RIL_Peer_Agent *agent,
1029     int direction_in)
1030 {
1031   unsigned long long new_bw;
1032
1033   if (direction_in)
1034   {
1035     new_bw = agent->bw_in / 2;
1036     if (new_bw < MIN_BW || new_bw > agent->bw_in)
1037       new_bw = MIN_BW;
1038     envi_set_active_suggestion (solver, agent, agent->address_inuse, new_bw, agent->bw_out,
1039         GNUNET_NO);
1040   }
1041   else
1042   {
1043     new_bw = agent->bw_out / 2;
1044     if (new_bw < MIN_BW || new_bw > agent->bw_out)
1045       new_bw = MIN_BW;
1046     envi_set_active_suggestion (solver, agent, agent->address_inuse, agent->bw_in, new_bw,
1047         GNUNET_NO);
1048   }
1049 }
1050
1051 /**
1052  * Increases the bandwidth by 5 times the minimum bandwidth for the active address.
1053  *
1054  * @param solver solver handle
1055  * @param agent agent handle
1056  * @param direction_in if GNUNET_YES, change inbound bandwidth, otherwise change the outbound
1057  * bandwidth
1058  */
1059 static void
1060 envi_action_bw_inc (struct GAS_RIL_Handle *solver, struct RIL_Peer_Agent *agent, int direction_in)
1061 {
1062   unsigned long long new_bw;
1063
1064   if (direction_in)
1065   {
1066     new_bw = agent->bw_in + (RIL_INC_DEC_STEP_SIZE * MIN_BW);
1067     if (new_bw < agent->bw_in || new_bw > GNUNET_ATS_MaxBandwidth)
1068       new_bw = GNUNET_ATS_MaxBandwidth;
1069     envi_set_active_suggestion (solver, agent, agent->address_inuse, new_bw,
1070         agent->bw_out, GNUNET_NO);
1071   }
1072   else
1073   {
1074     new_bw = agent->bw_out + (RIL_INC_DEC_STEP_SIZE * MIN_BW);
1075     if (new_bw < agent->bw_out || new_bw > GNUNET_ATS_MaxBandwidth)
1076       new_bw = GNUNET_ATS_MaxBandwidth;
1077     envi_set_active_suggestion (solver, agent, agent->address_inuse, agent->bw_in,
1078         new_bw, GNUNET_NO);
1079   }
1080 }
1081
1082 /**
1083  * Decreases the bandwidth by 5 times the minimum bandwidth for the active address. The least amount
1084  * of bandwidth suggested, is the minimum bandwidth for a peer, in order to not invoke a disconnect.
1085  *
1086  * @param solver solver handle
1087  * @param agent agent handle
1088  * @param direction_in if GNUNET_YES, change inbound bandwidth, otherwise change the outbound
1089  * bandwidth
1090  */
1091 static void
1092 envi_action_bw_dec (struct GAS_RIL_Handle *solver, struct RIL_Peer_Agent *agent, int direction_in)
1093 {
1094   unsigned long long new_bw;
1095
1096   if (direction_in)
1097   {
1098     new_bw = agent->bw_in - (RIL_INC_DEC_STEP_SIZE * MIN_BW);
1099     if (new_bw < MIN_BW || new_bw > agent->bw_in)
1100       new_bw = MIN_BW;
1101     envi_set_active_suggestion (solver, agent, agent->address_inuse, new_bw, agent->bw_out,
1102         GNUNET_NO);
1103   }
1104   else
1105   {
1106     new_bw = agent->bw_out - (RIL_INC_DEC_STEP_SIZE * MIN_BW);
1107     if (new_bw < MIN_BW || new_bw > agent->bw_out)
1108       new_bw = MIN_BW;
1109     envi_set_active_suggestion (solver, agent, agent->address_inuse, agent->bw_in, new_bw,
1110         GNUNET_NO);
1111   }
1112 }
1113
1114 /**
1115  * Switches to the address given by its index
1116  *
1117  * @param solver solver handle
1118  * @param agent agent handle
1119  * @param address_index index of the address as it is saved in the agent's list, starting with zero
1120  */
1121 static void
1122 envi_action_address_switch (struct GAS_RIL_Handle *solver,
1123     struct RIL_Peer_Agent *agent,
1124     unsigned int address_index)
1125 {
1126   struct RIL_Address_Wrapped *cur;
1127   int i = 0;
1128
1129   for (cur = agent->addresses_head; NULL != cur; cur = cur->next)
1130   {
1131     if (i == address_index)
1132     {
1133       envi_set_active_suggestion (solver, agent, cur->address_naked, agent->bw_in, agent->bw_out,
1134           GNUNET_NO);
1135       return;
1136     }
1137
1138     i++;
1139   }
1140
1141   //no address with address_index exists, in this case this action should not be callable
1142   GNUNET_assert(GNUNET_NO);
1143 }
1144
1145 /**
1146  * Puts the action into effect by calling the according function
1147  *
1148  * @param solver the solver handle
1149  * @param agent the action handle
1150  * @param action the action to perform by the solver
1151  */
1152 static void
1153 envi_do_action (struct GAS_RIL_Handle *solver, struct RIL_Peer_Agent *agent, int action)
1154 {
1155   int address_index;
1156
1157   switch (action)
1158   {
1159   case RIL_ACTION_NOTHING:
1160     break;
1161   case RIL_ACTION_BW_IN_DBL:
1162     envi_action_bw_double (solver, agent, GNUNET_YES);
1163     break;
1164   case RIL_ACTION_BW_IN_HLV:
1165     envi_action_bw_halven (solver, agent, GNUNET_YES);
1166     break;
1167   case RIL_ACTION_BW_IN_INC:
1168     envi_action_bw_inc (solver, agent, GNUNET_YES);
1169     break;
1170   case RIL_ACTION_BW_IN_DEC:
1171     envi_action_bw_dec (solver, agent, GNUNET_YES);
1172     break;
1173   case RIL_ACTION_BW_OUT_DBL:
1174     envi_action_bw_double (solver, agent, GNUNET_NO);
1175     break;
1176   case RIL_ACTION_BW_OUT_HLV:
1177     envi_action_bw_halven (solver, agent, GNUNET_NO);
1178     break;
1179   case RIL_ACTION_BW_OUT_INC:
1180     envi_action_bw_inc (solver, agent, GNUNET_NO);
1181     break;
1182   case RIL_ACTION_BW_OUT_DEC:
1183     envi_action_bw_dec (solver, agent, GNUNET_NO);
1184     break;
1185   default:
1186     if ((action >= RIL_ACTION_TYPE_NUM) && (action < agent->n)) //switch address action
1187     {
1188       address_index = action - RIL_ACTION_TYPE_NUM;
1189
1190       GNUNET_assert(address_index >= 0);
1191       GNUNET_assert(
1192           address_index <= agent_address_get_index (agent, agent->addresses_tail->address_naked));
1193
1194       envi_action_address_switch (solver, agent, address_index);
1195       break;
1196     }
1197     // error - action does not exist
1198     GNUNET_assert(GNUNET_NO);
1199   }
1200 }
1201
1202 static int
1203 agent_select_egreedy (struct RIL_Peer_Agent *agent, double *state)
1204 {
1205   int action;
1206
1207   if (agent_decide_exploration(agent))
1208   {
1209     action = agent_get_action_explore(agent, state);
1210     if (RIL_ALGO_Q == agent->envi->parameters.algorithm)
1211     {
1212       agent_modify_eligibility(agent, RIL_E_ZERO, NULL, action);
1213     }
1214     return action;
1215   }
1216   else
1217   {
1218     action = agent_get_action_best(agent, state);
1219     if (RIL_ALGO_Q == agent->envi->parameters.algorithm)
1220     {
1221       agent_modify_eligibility(agent, RIL_E_UPDATE, NULL, action);
1222     }
1223     return action;
1224   }
1225 }
1226
1227 /**
1228  * Selects the next action with a probability corresponding to its value. The
1229  * probability is calculated using a Boltzmann distribution with a temperature
1230  * value. The higher the temperature, the more are the action selection
1231  * probabilities the same. With a temperature of 0, the selection is greedy,
1232  * i.e. always the action with the highest value is chosen.
1233  * @param agent
1234  * @param state
1235  * @return
1236  */
1237 static int
1238 agent_select_softmax (struct RIL_Peer_Agent *agent, double *state)
1239 {
1240   int i;
1241   int a_max;
1242   double eqt[agent->n];
1243   double p[agent->n];
1244   double sum = 0;
1245   double r;
1246
1247   a_max = agent_get_action_best(agent, state);
1248
1249   for (i=0; i<agent->n; i++)
1250   {
1251     eqt[i] = exp(agent_estimate_q(agent,state,i) / agent->envi->parameters.temperature);
1252     sum += eqt[i];
1253   }
1254   for (i=0; i<agent->n; i++)
1255   {
1256     p[i] = eqt[i]/sum;
1257   }
1258   r = (double) GNUNET_CRYPTO_random_u32 (GNUNET_CRYPTO_QUALITY_WEAK,
1259       UINT32_MAX) / (double) UINT32_MAX;
1260   sum = 0;
1261   for (i=0; i<agent->n; i++)
1262   {
1263     if (sum + p[i] > r)
1264     {
1265       if (RIL_ALGO_Q == agent->envi->parameters.algorithm)
1266       {
1267         if (i == a_max)
1268           agent_modify_eligibility(agent, RIL_E_UPDATE, NULL, i);
1269         else
1270           agent_modify_eligibility(agent, RIL_E_ZERO, NULL, -1);
1271       }
1272       return i;
1273     }
1274     sum += p[i];
1275   }
1276   GNUNET_assert(GNUNET_NO);
1277 }
1278
1279 static int
1280 agent_select_action (struct RIL_Peer_Agent *agent, double *state)
1281 {
1282   if (agent->envi->parameters.select == RIL_SELECT_EGREEDY)
1283   {
1284     return agent_select_egreedy(agent, state);
1285   }
1286   else
1287   {
1288     return agent_select_softmax(agent, state);
1289   }
1290 }
1291
1292 /**
1293  * Performs one step of the Markov Decision Process. Other than in the literature the step starts
1294  * after having done the last action a_old. It observes the new state s_next and the reward
1295  * received. Then the coefficient update is done according to the SARSA or Q-learning method. The
1296  * next action is put into effect.
1297  *
1298  * @param agent the agent performing the step
1299  */
1300 static void
1301 agent_step (struct RIL_Peer_Agent *agent)
1302 {
1303   int a_next = RIL_ACTION_INVALID;
1304   int a_max;
1305   double *s_next;
1306   double reward;
1307
1308   LOG(GNUNET_ERROR_TYPE_DEBUG, "    agent_step() Peer '%s', algorithm %s\n",
1309       GNUNET_i2s (&agent->peer),
1310       agent->envi->parameters.algorithm ? "Q" : "SARSA");
1311
1312   s_next = envi_get_state (agent->envi, agent);
1313   reward = envi_get_reward (agent->envi, agent);
1314
1315   switch (agent->envi->parameters.algorithm)
1316   {
1317   case RIL_ALGO_SARSA:
1318     a_next = agent_select_action (agent, s_next);
1319     if (RIL_ACTION_INVALID != agent->a_old)
1320     {
1321       //updates weights with selected action (on-policy), if not first step
1322       agent_update_weights (agent, reward, s_next, a_next);
1323     }
1324     agent_modify_eligibility (agent, RIL_E_UPDATE, s_next, a_next);
1325     break;
1326
1327   case RIL_ALGO_Q:
1328     a_max = agent_get_action_best (agent, s_next);
1329     if (RIL_ACTION_INVALID != agent->a_old)
1330     {
1331       //updates weights with best action, disregarding actually selected action (off-policy), if not first step
1332       agent_update_weights (agent, reward, s_next, a_max);
1333     }
1334     a_next = agent_select_action (agent, s_next);
1335     break;
1336   }
1337
1338   GNUNET_assert(RIL_ACTION_INVALID != a_next);
1339
1340   agent_modify_eligibility (agent, RIL_E_ACCUMULATE, s_next, a_next);
1341
1342 //  GNUNET_log (GNUNET_ERROR_TYPE_INFO, "step()  Step# %llu  R: %f  IN %llu  OUT %llu  A: %d\n",
1343 //        agent->step_count,
1344 //        reward,
1345 //        agent->bw_in/1024,
1346 //        agent->bw_out/1024,
1347 //        a_next);
1348
1349   envi_do_action (agent->envi, agent, a_next);
1350
1351   GNUNET_free(agent->s_old);
1352   agent->s_old = s_next;
1353   agent->a_old = a_next;
1354
1355   agent->step_count += 1;
1356 }
1357
1358 static void
1359 ril_step (struct GAS_RIL_Handle *solver);
1360
1361 /**
1362  * Task for the scheduler, which performs one step and lets the solver know that
1363  * no further step is scheduled.
1364  *
1365  * @param cls the solver handle
1366  * @param tc the task context for the scheduler
1367  */
1368 static void
1369 ril_step_scheduler_task (void *cls, const struct GNUNET_SCHEDULER_TaskContext *tc)
1370 {
1371   struct GAS_RIL_Handle *solver = cls;
1372
1373   solver->step_next_task_id = GNUNET_SCHEDULER_NO_TASK;
1374   ril_step (solver);
1375 }
1376
1377 static double
1378 ril_get_used_resource_ratio (struct GAS_RIL_Handle *solver)
1379 {
1380   int i;
1381   struct RIL_Network net;
1382   unsigned long long sum_assigned = 0;
1383   unsigned long long sum_available = 0;
1384   double ratio;
1385
1386   for (i = 0; i < solver->networks_count; i++)
1387   {
1388     net = solver->network_entries[i];
1389     if (net.bw_in_assigned > 0) //only consider scopes where an address is actually active
1390     {
1391       sum_assigned += net.bw_in_assigned;
1392       sum_assigned += net.bw_out_assigned;
1393       sum_available += net.bw_in_available;
1394       sum_available += net.bw_out_available;
1395     }
1396   }
1397   if (sum_available > 0)
1398   {
1399     ratio = ((double) sum_assigned) / ((double) sum_available);
1400   }
1401   else
1402   {
1403     ratio = 0;
1404   }
1405
1406   return ratio > 1 ? 1 : ratio; //overutilization possible, cap at 1
1407 }
1408
1409 /**
1410  * Lookup network struct by type
1411  *
1412  * @param s the solver handle
1413  * @param type the network type
1414  * @return the network struct
1415  */
1416 static struct RIL_Network *
1417 ril_get_network (struct GAS_RIL_Handle *s, uint32_t type)
1418 {
1419   int i;
1420
1421   for (i = 0; i < s->networks_count; i++)
1422   {
1423     if (s->network_entries[i].type == type)
1424     {
1425       return &s->network_entries[i];
1426     }
1427   }
1428   return NULL ;
1429 }
1430
1431 static int
1432 ril_network_is_not_full (struct GAS_RIL_Handle *solver, enum GNUNET_ATS_Network_Type network)
1433 {
1434   struct RIL_Network *net;
1435   struct RIL_Peer_Agent *agent;
1436   unsigned long long address_count = 0;
1437
1438   for (agent = solver->agents_head; NULL != agent; agent = agent->next)
1439   {
1440     if (agent->address_inuse && agent->is_active)
1441     {
1442       net = agent->address_inuse->solver_information;
1443       if (net->type == network)
1444       {
1445         address_count++;
1446       }
1447     }
1448   }
1449
1450   net = ril_get_network (solver, network);
1451   return (net->bw_in_available > MIN_BW * address_count) && (net->bw_out_available > MIN_BW * address_count);
1452 }
1453
1454 static void
1455 ril_try_unblock_agent (struct GAS_RIL_Handle *solver, struct RIL_Peer_Agent *agent, int silent)
1456 {
1457   struct RIL_Address_Wrapped *addr_wrap;
1458   struct RIL_Network *net;
1459
1460   for (addr_wrap = agent->addresses_head; NULL != addr_wrap; addr_wrap = addr_wrap->next)
1461   {
1462     net = addr_wrap->address_naked->solver_information;
1463     if (ril_network_is_not_full(solver, net->type))
1464     {
1465       if (NULL == agent->address_inuse)
1466         envi_set_active_suggestion (solver, agent, addr_wrap->address_naked, MIN_BW, MIN_BW, silent);
1467       return;
1468     }
1469   }
1470   agent->address_inuse = NULL;
1471 }
1472
1473 static void
1474 ril_calculate_discount (struct GAS_RIL_Handle *solver)
1475 {
1476   struct GNUNET_TIME_Absolute time_now;
1477   struct GNUNET_TIME_Relative time_delta;
1478   double tau;
1479
1480   // MDP case - remove when debugged
1481   if (solver->simulate)
1482   {
1483     solver->global_discount_variable = solver->parameters.gamma;
1484     solver->global_discount_integrated = 1;
1485     return;
1486   }
1487
1488   // semi-MDP case
1489
1490   //calculate tau, i.e. how many real valued time units have passed, one time unit is one minimum time step
1491   time_now = GNUNET_TIME_absolute_get ();
1492   time_delta = GNUNET_TIME_absolute_get_difference (solver->step_time_last, time_now);
1493   solver->step_time_last = time_now;
1494   tau = (double) time_delta.rel_value_us
1495       / (double) solver->parameters.step_time_min.rel_value_us;
1496
1497   //calculate reward discounts (once per step for all agents)
1498   solver->global_discount_variable = pow (M_E, ((-1.0) * ((double) solver->parameters.beta) * tau));
1499   solver->global_discount_integrated = (1.0 - solver->global_discount_variable)
1500       / (double) solver->parameters.beta;
1501 }
1502
1503 static void
1504 ril_calculate_assigned_bwnet (struct GAS_RIL_Handle *solver)
1505 {
1506   int c;
1507   struct RIL_Network *net;
1508
1509   for (c = 0; c < solver->networks_count; c++)
1510   {
1511     net = &solver->network_entries[c];
1512     net->bw_in_assigned = ril_network_get_assigned(solver, net->type, GNUNET_YES);
1513     net->bw_out_assigned = ril_network_get_assigned(solver, net->type, GNUNET_NO);
1514   }
1515 }
1516
1517 /**
1518  * Schedules the next global step in an adaptive way. The more resources are
1519  * left, the earlier the next step is scheduled. This serves the reactivity of
1520  * the solver to changed inputs.
1521  *
1522  * @param solver the solver handle
1523  */
1524 static void
1525 ril_step_schedule_next (struct GAS_RIL_Handle *solver)
1526 {
1527   double used_ratio;
1528   double factor;
1529   double y;
1530   double offset;
1531   struct GNUNET_TIME_Relative time_next;
1532
1533   used_ratio = ril_get_used_resource_ratio (solver);
1534
1535   GNUNET_assert(
1536       solver->parameters.step_time_min.rel_value_us
1537           <= solver->parameters.step_time_max.rel_value_us);
1538
1539   factor = (double) GNUNET_TIME_relative_subtract (solver->parameters.step_time_max,
1540       solver->parameters.step_time_min).rel_value_us;
1541   offset = (double) solver->parameters.step_time_min.rel_value_us;
1542   y = factor * pow (used_ratio, RIL_INTERVAL_EXPONENT) + offset;
1543
1544   GNUNET_assert(y <= (double ) solver->parameters.step_time_max.rel_value_us);
1545   GNUNET_assert(y >= (double ) solver->parameters.step_time_min.rel_value_us);
1546
1547   time_next = GNUNET_TIME_relative_multiply (GNUNET_TIME_UNIT_MICROSECONDS, (unsigned long long) y);
1548
1549   if (solver->simulate)
1550   {
1551     time_next = GNUNET_TIME_UNIT_ZERO;
1552   }
1553
1554   if ((GNUNET_SCHEDULER_NO_TASK == solver->step_next_task_id) && (GNUNET_NO == solver->done))
1555   {
1556     solver->step_next_task_id = GNUNET_SCHEDULER_add_delayed (time_next, &ril_step_scheduler_task,
1557           solver);
1558   }
1559 }
1560
1561 /**
1562  * Triggers one step per agent
1563  * @param solver
1564  */
1565 static void
1566 ril_step (struct GAS_RIL_Handle *solver)
1567 {
1568   struct RIL_Peer_Agent *cur;
1569
1570   if (GNUNET_YES == solver->bulk_lock)
1571   {
1572     solver->bulk_changes++;
1573     return;
1574   }
1575
1576   ril_inform (solver, GAS_OP_SOLVE_START, GAS_STAT_SUCCESS);
1577
1578   LOG(GNUNET_ERROR_TYPE_DEBUG, "    RIL step number %d\n", solver->step_count);
1579
1580   if (0 == solver->step_count)
1581   {
1582     solver->step_time_last = GNUNET_TIME_absolute_get ();
1583   }
1584
1585   ril_calculate_discount (solver);
1586   ril_calculate_assigned_bwnet (solver);
1587
1588   //calculate network state vector
1589 //  envi_state_networks(solver);
1590
1591   //trigger one step per active, unblocked agent
1592   for (cur = solver->agents_head; NULL != cur; cur = cur->next)
1593   {
1594     if (cur->is_active)
1595     {
1596       if (NULL == cur->address_inuse)
1597       {
1598         ril_try_unblock_agent(solver, cur, GNUNET_NO);
1599       }
1600       if (cur->address_inuse)
1601       {
1602         agent_step (cur);
1603       }
1604     }
1605   }
1606
1607   ril_calculate_assigned_bwnet (solver);
1608
1609   solver->step_count += 1;
1610   ril_step_schedule_next (solver);
1611
1612   ril_inform (solver, GAS_OP_SOLVE_STOP, GAS_STAT_SUCCESS);
1613
1614   ril_inform (solver, GAS_OP_SOLVE_UPDATE_NOTIFICATION_START, GAS_STAT_SUCCESS);
1615   for (cur = solver->agents_head; NULL != cur; cur = cur->next)
1616   {
1617     if (cur->suggestion_issue) {
1618       solver->plugin_envi->bandwidth_changed_cb(solver->plugin_envi->bw_changed_cb_cls, cur->suggestion_address);
1619       cur->suggestion_issue = GNUNET_NO;
1620     }
1621   }
1622   ril_inform (solver, GAS_OP_SOLVE_UPDATE_NOTIFICATION_STOP, GAS_STAT_SUCCESS);
1623 }
1624
1625 static int
1626 ril_count_agents (struct GAS_RIL_Handle *solver)
1627 {
1628   int c = 0;
1629   struct RIL_Peer_Agent *cur_agent;
1630
1631   for (cur_agent = solver->agents_head; NULL != cur_agent; cur_agent = cur_agent->next)
1632   {
1633     c++;
1634   }
1635   return c;
1636 }
1637
1638 static void
1639 agent_w_start (struct RIL_Peer_Agent *agent)
1640 {
1641   int count;
1642   struct RIL_Peer_Agent *other;
1643   int i;
1644   int k;
1645
1646   count = ril_count_agents(agent->envi);
1647
1648   for (i = 0; i < agent->n; i++)
1649   {
1650     for (k = 0; k < agent->m; k++)
1651     {
1652       if (0 == count) {
1653         agent->W[i][k] = agent->envi->parameters.alpha * (1.0 - 2.0*((double) GNUNET_CRYPTO_random_u32(GNUNET_CRYPTO_QUALITY_WEAK, UINT32_MAX)/(double)UINT32_MAX));
1654       }
1655       else {
1656         for (other = agent->envi->agents_head; NULL != other; other = other->next)
1657         {
1658           agent->W[i][k] += (other->W[i][k] / (double) count);
1659         }
1660       }
1661
1662       GNUNET_assert(!isinf(agent->W[i][k]));
1663     }
1664   }
1665 }
1666
1667 /**
1668  * Initialize an agent without addresses and its knowledge base
1669  *
1670  * @param s ril solver
1671  * @param peer the one in question
1672  * @return handle to the new agent
1673  */
1674 static struct RIL_Peer_Agent *
1675 agent_init (void *s, const struct GNUNET_PeerIdentity *peer)
1676 {
1677   int i;
1678   struct GAS_RIL_Handle * solver = s;
1679   struct RIL_Peer_Agent * agent = GNUNET_new (struct RIL_Peer_Agent);
1680
1681   agent->envi = solver;
1682   agent->peer = *peer;
1683   agent->step_count = 0;
1684   agent->is_active = GNUNET_NO;
1685   agent->bw_in = MIN_BW;
1686   agent->bw_out = MIN_BW;
1687   agent->suggestion_issue = GNUNET_NO;
1688   agent->n = RIL_ACTION_TYPE_NUM;
1689   agent->m = 0;
1690   agent->W = (double **) GNUNET_malloc (sizeof (double *) * agent->n);
1691   agent->E = (double **) GNUNET_malloc (sizeof (double *) * agent->n);
1692   for (i = 0; i < agent->n; i++)
1693   {
1694     agent->W[i] = (double *) GNUNET_malloc (sizeof (double) * agent->m);
1695     agent->E[i] = (double *) GNUNET_malloc (sizeof (double) * agent->m);
1696   }
1697   agent_w_start(agent);
1698   agent->a_old = RIL_ACTION_INVALID;
1699   agent->s_old = GNUNET_malloc (sizeof (double) * agent->m);
1700   agent->address_inuse = NULL;
1701
1702   return agent;
1703 }
1704
1705 /**
1706  * Deallocate agent
1707  *
1708  * @param solver the solver handle
1709  * @param agent the agent to retire
1710  */
1711 static void
1712 agent_die (struct GAS_RIL_Handle *solver, struct RIL_Peer_Agent *agent)
1713 {
1714   int i;
1715
1716   for (i = 0; i < agent->n; i++)
1717   {
1718     GNUNET_free_non_null(agent->W[i]);
1719     GNUNET_free_non_null(agent->E[i]);
1720   }
1721   GNUNET_free_non_null(agent->W);
1722   GNUNET_free_non_null(agent->E);
1723   GNUNET_free_non_null(agent->s_old);
1724   GNUNET_free(agent);
1725 }
1726
1727 /**
1728  * Returns the agent for a peer
1729  *
1730  * @param solver the solver handle
1731  * @param peer the identity of the peer
1732  * @param create whether or not to create an agent, if none is allocated yet
1733  * @return the agent
1734  */
1735 static struct RIL_Peer_Agent *
1736 ril_get_agent (struct GAS_RIL_Handle *solver, const struct GNUNET_PeerIdentity *peer, int create)
1737 {
1738   struct RIL_Peer_Agent *cur;
1739
1740   for (cur = solver->agents_head; NULL != cur; cur = cur->next)
1741   {
1742     if (0 == memcmp (peer, &cur->peer, sizeof(struct GNUNET_PeerIdentity)))
1743     {
1744       return cur;
1745     }
1746   }
1747
1748   if (create)
1749   {
1750     cur = agent_init (solver, peer);
1751     GNUNET_CONTAINER_DLL_insert_tail(solver->agents_head, solver->agents_tail, cur);
1752     return cur;
1753   }
1754   return NULL ;
1755 }
1756
1757 /**
1758  * Determine whether at least the minimum bandwidth is set for the network. Otherwise the network is
1759  * considered inactive and not used. Addresses in an inactive network are ignored.
1760  *
1761  * @param solver solver handle
1762  * @param network the network type
1763  * @return whether or not the network is considered active
1764  */
1765 static int
1766 ril_network_is_active (struct GAS_RIL_Handle *solver, enum GNUNET_ATS_Network_Type network)
1767 {
1768   struct RIL_Network *net;
1769
1770   net = ril_get_network (solver, network);
1771   return net->bw_out_available >= MIN_BW;
1772 }
1773
1774 /**
1775  * Cuts a slice out of a vector of elements. This is used to decrease the size of the matrix storing
1776  * the reward function approximation. It copies the memory, which is not cut, to the new vector,
1777  * frees the memory of the old vector, and redirects the pointer to the new one.
1778  *
1779  * @param old pointer to the pointer to the first element of the vector
1780  * @param element_size byte size of the vector elements
1781  * @param hole_start the first element to cut out
1782  * @param hole_length the number of elements to cut out
1783  * @param old_length the length of the old vector
1784  */
1785 static void
1786 ril_cut_from_vector (void **old,
1787     size_t element_size,
1788     unsigned int hole_start,
1789     unsigned int hole_length,
1790     unsigned int old_length)
1791 {
1792   char *tmpptr;
1793   char *oldptr = (char *) *old;
1794   size_t size;
1795   unsigned int bytes_before;
1796   unsigned int bytes_hole;
1797   unsigned int bytes_after;
1798
1799   GNUNET_assert(old_length >= hole_length);
1800   GNUNET_assert(old_length >= (hole_start + hole_length));
1801
1802   size = element_size * (old_length - hole_length);
1803
1804   bytes_before = element_size * hole_start;
1805   bytes_hole = element_size * hole_length;
1806   bytes_after = element_size * (old_length - hole_start - hole_length);
1807
1808   if (0 == size)
1809   {
1810     tmpptr = NULL;
1811   }
1812   else
1813   {
1814     tmpptr = GNUNET_malloc (size);
1815     memcpy (tmpptr, oldptr, bytes_before);
1816     memcpy (tmpptr + bytes_before, oldptr + (bytes_before + bytes_hole), bytes_after);
1817   }
1818   if (NULL != *old)
1819   {
1820     GNUNET_free(*old);
1821   }
1822   *old = (void *) tmpptr;
1823 }
1824
1825 /*
1826  *  Solver API functions
1827  *  ---------------------------
1828  */
1829
1830 /**
1831  * Change relative preference for quality in solver
1832  *
1833  * @param solver the solver handle
1834  * @param peer the peer to change the preference for
1835  * @param kind the kind to change the preference
1836  * @param pref_rel the normalized preference value for this kind over all clients
1837  */
1838 void
1839 GAS_ril_address_change_preference (void *solver,
1840     const struct GNUNET_PeerIdentity *peer,
1841     enum GNUNET_ATS_PreferenceKind kind,
1842     double pref_rel)
1843 {
1844   LOG(GNUNET_ERROR_TYPE_DEBUG,
1845       "API_address_change_preference() Preference '%s' for peer '%s' changed to %.2f \n",
1846       GNUNET_ATS_print_preference_type (kind), GNUNET_i2s (peer), pref_rel);
1847
1848   ril_step (solver);
1849 }
1850
1851 /**
1852  * Entry point for the plugin
1853  *
1854  * @param cls pointer to the 'struct GNUNET_ATS_PluginEnvironment'
1855  */
1856 void *
1857 libgnunet_plugin_ats_ril_init (void *cls)
1858 {
1859   struct GNUNET_ATS_PluginEnvironment *env = cls;
1860   struct GAS_RIL_Handle *solver = GNUNET_new (struct GAS_RIL_Handle);
1861   struct RIL_Network * cur;
1862   int c;
1863   char *string;
1864
1865   LOG(GNUNET_ERROR_TYPE_DEBUG, "API_init() Initializing RIL solver\n");
1866
1867   GNUNET_assert(NULL != env);
1868   GNUNET_assert(NULL != env->cfg);
1869   GNUNET_assert(NULL != env->stats);
1870   GNUNET_assert(NULL != env->bandwidth_changed_cb);
1871   GNUNET_assert(NULL != env->get_preferences);
1872   GNUNET_assert(NULL != env->get_property);
1873
1874   if (GNUNET_OK != GNUNET_CONFIGURATION_get_value_number(env->cfg, "ats", "RIL_RBF_DIVISOR", &solver->parameters.divisor))
1875   {
1876     solver->parameters.divisor = RIL_DEFAULT_RBF_DIVISOR;
1877   }
1878   if (GNUNET_OK
1879       != GNUNET_CONFIGURATION_get_value_time (env->cfg, "ats", "RIL_STEP_TIME_MIN",
1880           &solver->parameters.step_time_min))
1881   {
1882     solver->parameters.step_time_min = RIL_DEFAULT_STEP_TIME_MIN;
1883   }
1884   if (GNUNET_OK
1885       != GNUNET_CONFIGURATION_get_value_time (env->cfg, "ats", "RIL_STEP_TIME_MAX",
1886           &solver->parameters.step_time_max))
1887   {
1888     solver->parameters.step_time_max = RIL_DEFAULT_STEP_TIME_MAX;
1889   }
1890   if (GNUNET_OK == GNUNET_CONFIGURATION_get_value_string (env->cfg, "ats", "RIL_ALGORITHM", &string))
1891   {
1892     solver->parameters.algorithm = !strcmp (string, "SARSA") ? RIL_ALGO_SARSA : RIL_ALGO_Q;
1893     GNUNET_free (string);
1894   }
1895   else
1896   {
1897     solver->parameters.algorithm = RIL_DEFAULT_ALGORITHM;
1898   }
1899   if (GNUNET_OK == GNUNET_CONFIGURATION_get_value_string (env->cfg, "ats", "RIL_SELECT", &string))
1900   {
1901     solver->parameters.select = !strcmp (string, "EGREEDY") ? RIL_SELECT_EGREEDY : RIL_SELECT_SOFTMAX;
1902     GNUNET_free (string);
1903   }
1904   else
1905   {
1906     solver->parameters.select = RIL_DEFAULT_SELECT;
1907   }
1908   if (GNUNET_OK == GNUNET_CONFIGURATION_get_value_string (env->cfg, "ats", "RIL_DISCOUNT_BETA", &string))
1909   {
1910     solver->parameters.beta = strtod (string, NULL);
1911     GNUNET_free (string);
1912     if (!(solver->parameters.beta > 0))
1913     {
1914       LOG (GNUNET_ERROR_TYPE_WARNING, "RIL_DISCOUNT_BETA not configured as positive number. Set to default value of %f instead.\n", RIL_DEFAULT_DISCOUNT_BETA);
1915       solver->parameters.beta = RIL_DEFAULT_DISCOUNT_BETA;
1916     }
1917   }
1918   else
1919   {
1920     solver->parameters.beta = RIL_DEFAULT_DISCOUNT_BETA;
1921   }
1922   if (GNUNET_OK == GNUNET_CONFIGURATION_get_value_string (env->cfg, "ats", "RIL_DISCOUNT_GAMMA", &string))
1923   {
1924     solver->parameters.gamma = strtod (string, NULL);
1925     GNUNET_free (string);
1926     if (!(solver->parameters.gamma < 1) || (solver->parameters.gamma < 0))
1927     {
1928       LOG (GNUNET_ERROR_TYPE_WARNING, "RIL_DISCOUNT_GAMMA not configured in range [0,1[. Set to default value of %f instead.\n", RIL_DEFAULT_DISCOUNT_GAMMA);
1929       solver->parameters.gamma = RIL_DEFAULT_DISCOUNT_GAMMA;
1930     }
1931   }
1932   else
1933   {
1934     solver->parameters.gamma = RIL_DEFAULT_DISCOUNT_GAMMA;
1935   }
1936   if (GNUNET_OK
1937       == GNUNET_CONFIGURATION_get_value_string (env->cfg, "ats", "RIL_GRADIENT_STEP_SIZE", &string))
1938   {
1939     solver->parameters.alpha = strtod (string, NULL);
1940     GNUNET_free (string);
1941     if (!(solver->parameters.alpha > 0) || solver->parameters.alpha > 1)
1942     {
1943       LOG (GNUNET_ERROR_TYPE_WARNING, "RIL_GRADIENT_STEP_SIZE not configured in range ]0,1]. Set to default value of %f instead.\n", RIL_DEFAULT_GRADIENT_STEP_SIZE);
1944       solver->parameters.alpha = RIL_DEFAULT_GRADIENT_STEP_SIZE;
1945     }
1946   }
1947   else
1948   {
1949     solver->parameters.alpha = RIL_DEFAULT_GRADIENT_STEP_SIZE;
1950   }
1951   if (GNUNET_OK == GNUNET_CONFIGURATION_get_value_string (env->cfg, "ats", "RIL_TRACE_DECAY", &string))
1952   {
1953     solver->parameters.lambda = strtod (string, NULL);
1954     GNUNET_free (string);
1955     if (solver->parameters.lambda < 0 || solver->parameters.lambda > 1)
1956     {
1957       LOG (GNUNET_ERROR_TYPE_WARNING, "RIL_TRACE_DECAY not configured in range [0,1]. Set to default value of %f instead.\n", RIL_DEFAULT_TRACE_DECAY);
1958       solver->parameters.lambda = RIL_DEFAULT_TRACE_DECAY;
1959     }
1960   }
1961   else
1962   {
1963     solver->parameters.lambda = RIL_DEFAULT_TRACE_DECAY;
1964   }
1965   if (GNUNET_OK == GNUNET_CONFIGURATION_get_value_string (env->cfg, "ats", "RIL_EXPLORE_RATIO", &string))
1966   {
1967     solver->parameters.explore_ratio = strtod (string, NULL);
1968     GNUNET_free (string);
1969     if (solver->parameters.explore_ratio < 0 || solver->parameters.explore_ratio > 1)
1970     {
1971       LOG (GNUNET_ERROR_TYPE_WARNING, "RIL_EXPLORE_RATIO not configured in range [0,1]. Set to default value of %f instead.\n", RIL_DEFAULT_EXPLORE_RATIO);
1972       solver->parameters.explore_ratio = RIL_DEFAULT_EXPLORE_RATIO;
1973     }
1974   }
1975   else
1976   {
1977     solver->parameters.explore_ratio = RIL_DEFAULT_EXPLORE_RATIO;
1978   }
1979   if (GNUNET_OK == GNUNET_CONFIGURATION_get_value_string (env->cfg, "ats", "RIL_GLOBAL_REWARD_SHARE", &string))
1980   {
1981     solver->parameters.reward_global_share = strtod (string, NULL);
1982     GNUNET_free (string);
1983     if (solver->parameters.reward_global_share < 0 || solver->parameters.reward_global_share > 1)
1984     {
1985       LOG (GNUNET_ERROR_TYPE_WARNING, "RIL_GLOBAL_REWARD_SHARE not configured in range [0,1]. Set to default value of %f instead.\n", RIL_DEFAULT_GLOBAL_REWARD_SHARE);
1986       solver->parameters.reward_global_share = RIL_DEFAULT_GLOBAL_REWARD_SHARE;
1987     }
1988   }
1989   else
1990   {
1991     solver->parameters.reward_global_share = RIL_DEFAULT_GLOBAL_REWARD_SHARE;
1992   }
1993   if (GNUNET_OK == GNUNET_CONFIGURATION_get_value_string (env->cfg, "ats", "RIL_TEMPERATURE", &string))
1994   {
1995     solver->parameters.temperature = strtod (string, NULL);
1996     GNUNET_free (string);
1997     if (solver->parameters.temperature <= 0)
1998     {
1999       LOG (GNUNET_ERROR_TYPE_WARNING, "RIL_TEMPERATURE not positive. Set to default value of %f instead.\n", RIL_DEFAULT_TEMPERATURE);
2000       solver->parameters.temperature = RIL_DEFAULT_TEMPERATURE;
2001     }
2002   }
2003   else
2004   {
2005     solver->parameters.temperature = RIL_DEFAULT_TEMPERATURE;
2006   }
2007   if (GNUNET_OK != GNUNET_CONFIGURATION_get_value_number (env->cfg, "ats", "RIL_SIMULATE", &solver->simulate))
2008   {
2009     solver->simulate = GNUNET_NO;
2010   }
2011
2012   env->sf.s_add = &GAS_ril_address_add;
2013   env->sf.s_address_update_property = &GAS_ril_address_property_changed;
2014   env->sf.s_address_update_session = &GAS_ril_address_session_changed;
2015   env->sf.s_address_update_inuse = &GAS_ril_address_inuse_changed;
2016   env->sf.s_address_update_network = &GAS_ril_address_change_network;
2017   env->sf.s_get = &GAS_ril_get_preferred_address;
2018   env->sf.s_get_stop = &GAS_ril_stop_get_preferred_address;
2019   env->sf.s_pref = &GAS_ril_address_change_preference;
2020   env->sf.s_feedback = &GAS_ril_address_preference_feedback;
2021   env->sf.s_del = &GAS_ril_address_delete;
2022   env->sf.s_bulk_start = &GAS_ril_bulk_start;
2023   env->sf.s_bulk_stop = &GAS_ril_bulk_stop;
2024
2025   solver->plugin_envi = env;
2026   solver->networks_count = env->network_count;
2027   solver->network_entries = GNUNET_malloc (env->network_count * sizeof (struct RIL_Network));
2028   solver->step_count = 0;
2029   solver->done = GNUNET_NO;
2030
2031   for (c = 0; c < env->network_count; c++)
2032   {
2033     cur = &solver->network_entries[c];
2034     cur->type = env->networks[c];
2035     cur->bw_in_available = env->in_quota[c];
2036     cur->bw_out_available = env->out_quota[c];
2037     LOG(GNUNET_ERROR_TYPE_INFO, "init()  Quotas for %s network:  IN %llu - OUT %llu\n", GNUNET_ATS_print_network_type(cur->type), cur->bw_in_available/1024, cur->bw_out_available/1024);
2038   }
2039
2040   LOG(GNUNET_ERROR_TYPE_INFO, "init()  Parameters:\n");
2041   LOG(GNUNET_ERROR_TYPE_INFO, "init()  Algorithm = %s, alpha = %f, beta = %f, lambda = %f\n",
2042       solver->parameters.algorithm ? "Q" : "SARSA",
2043       solver->parameters.alpha,
2044       solver->parameters.beta,
2045       solver->parameters.lambda);
2046   LOG(GNUNET_ERROR_TYPE_INFO, "init()  explore = %f, global_share = %f\n",
2047       solver->parameters.explore_ratio,
2048       solver->parameters.reward_global_share);
2049
2050   return solver;
2051 }
2052
2053 /**
2054  * Exit point for the plugin
2055  *
2056  * @param cls the solver handle
2057  */
2058 void *
2059 libgnunet_plugin_ats_ril_done (void *cls)
2060 {
2061   struct GAS_RIL_Handle *s = cls;
2062   struct RIL_Peer_Agent *cur_agent;
2063   struct RIL_Peer_Agent *next_agent;
2064
2065   LOG(GNUNET_ERROR_TYPE_DEBUG, "API_done() Shutting down RIL solver\n");
2066
2067   s->done = GNUNET_YES;
2068
2069   cur_agent = s->agents_head;
2070   while (NULL != cur_agent)
2071   {
2072     next_agent = cur_agent->next;
2073     GNUNET_CONTAINER_DLL_remove(s->agents_head, s->agents_tail, cur_agent);
2074     agent_die (s, cur_agent);
2075     cur_agent = next_agent;
2076   }
2077
2078   if (GNUNET_SCHEDULER_NO_TASK != s->step_next_task_id)
2079   {
2080     GNUNET_SCHEDULER_cancel (s->step_next_task_id);
2081   }
2082   GNUNET_free(s->network_entries);
2083   GNUNET_free(s);
2084
2085   return NULL;
2086 }
2087
2088 /**
2089  * Add a new address for a peer to the solver
2090  *
2091  * The address is already contained in the addresses hashmap!
2092  *
2093  * @param solver the solver Handle
2094  * @param address the address to add
2095  * @param network network type of this address
2096  */
2097 void
2098 GAS_ril_address_add (void *solver, struct ATS_Address *address, uint32_t network)
2099 {
2100   struct GAS_RIL_Handle *s = solver;
2101   struct RIL_Peer_Agent *agent;
2102   struct RIL_Address_Wrapped *address_wrapped;
2103   struct RIL_Network *net;
2104   unsigned int m_new;
2105   unsigned int m_old;
2106   unsigned int n_new;
2107   unsigned int n_old;
2108   int i;
2109   unsigned int zero;
2110
2111   LOG (GNUNET_ERROR_TYPE_DEBUG, "API_address_add()\n");
2112
2113   net = ril_get_network (s, network);
2114   address->solver_information = net;
2115
2116   if (!ril_network_is_active (s, network))
2117   {
2118     LOG(GNUNET_ERROR_TYPE_DEBUG,
2119         "API_address_add() Did not add %s address %s for peer '%s', network does not have enough bandwidth\n",
2120         address->plugin, address->addr, GNUNET_i2s (&address->peer));
2121     return;
2122   }
2123
2124   agent = ril_get_agent (s, &address->peer, GNUNET_YES);
2125
2126   //add address
2127   address_wrapped = GNUNET_new (struct RIL_Address_Wrapped);
2128   address_wrapped->address_naked = address;
2129   GNUNET_CONTAINER_DLL_insert_tail(agent->addresses_head, agent->addresses_tail, address_wrapped);
2130
2131   //increase size of W
2132   m_new = agent->m + ((s->parameters.divisor+1) * (s->parameters.divisor+1));
2133   m_old = agent->m;
2134   n_new = agent->n + 1;
2135   n_old = agent->n;
2136
2137   GNUNET_array_grow(agent->W, agent->n, n_new);
2138   agent->n = n_old;
2139   GNUNET_array_grow(agent->E, agent->n, n_new);
2140   for (i = 0; i < n_new; i++)
2141   {
2142     if (i < n_old)
2143     {
2144       agent->m = m_old;
2145       GNUNET_array_grow(agent->W[i], agent->m, m_new);
2146       agent->m = m_old;
2147       GNUNET_array_grow(agent->E[i], agent->m, m_new);
2148     }
2149     else
2150     {
2151       zero = 0;
2152       GNUNET_array_grow(agent->W[i], zero, m_new);
2153       zero = 0;
2154       GNUNET_array_grow(agent->E[i], zero, m_new);
2155     }
2156   }
2157
2158   //increase size of old state vector
2159   agent->m = m_old;
2160   GNUNET_array_grow(agent->s_old, agent->m, m_new);
2161
2162   ril_try_unblock_agent(s, agent, GNUNET_NO);
2163
2164   ril_step (s);
2165
2166   LOG(GNUNET_ERROR_TYPE_DEBUG, "API_address_add() Added %s %s address %s for peer '%s'\n",
2167       address->active ? "active" : "inactive", address->plugin, address->addr,
2168       GNUNET_i2s (&address->peer));
2169 }
2170
2171 /**
2172  * Delete an address in the solver
2173  *
2174  * The address is not contained in the address hashmap anymore!
2175  *
2176  * @param solver the solver handle
2177  * @param address the address to remove
2178  * @param session_only delete only session not whole address
2179  */
2180 void
2181 GAS_ril_address_delete (void *solver, struct ATS_Address *address, int session_only)
2182 {
2183   struct GAS_RIL_Handle *s = solver;
2184   struct RIL_Peer_Agent *agent;
2185   struct RIL_Address_Wrapped *address_wrapped;
2186   int address_was_used = address->active;
2187   int address_index;
2188   unsigned int m_new;
2189   unsigned int n_new;
2190   int i;
2191   struct RIL_Network *net;
2192
2193   LOG(GNUNET_ERROR_TYPE_DEBUG, "API_address_delete() Delete %s%s %s address %s for peer '%s'\n",
2194       session_only ? "session for " : "", address->active ? "active" : "inactive", address->plugin,
2195       address->addr, GNUNET_i2s (&address->peer));
2196
2197   agent = ril_get_agent (s, &address->peer, GNUNET_NO);
2198   if (NULL == agent)
2199   {
2200     net = address->solver_information;
2201     GNUNET_assert(!ril_network_is_active (s, net->type));
2202     LOG(GNUNET_ERROR_TYPE_DEBUG,
2203         "No agent allocated for peer yet, since address was in inactive network\n");
2204     return;
2205   }
2206
2207   address_index = agent_address_get_index (agent, address);
2208   address_wrapped = agent_address_get (agent, address);
2209
2210   if (NULL == address_wrapped)
2211   {
2212     net = address->solver_information;
2213     GNUNET_assert(!ril_network_is_active (s, net->type));
2214     LOG(GNUNET_ERROR_TYPE_DEBUG,
2215         "Address not considered by agent, address was in inactive network\n");
2216     return;
2217   }
2218
2219   GNUNET_CONTAINER_DLL_remove(agent->addresses_head, agent->addresses_tail, address_wrapped);
2220   GNUNET_free(address_wrapped);
2221
2222   //decrease W
2223   m_new = agent->m - ((s->parameters.divisor+1) * (s->parameters.divisor+1));
2224   n_new = agent->n - 1;
2225
2226   for (i = 0; i < agent->n; i++)
2227   {
2228     LOG(GNUNET_ERROR_TYPE_DEBUG, "first\n");
2229     ril_cut_from_vector ((void **) &agent->W[i], sizeof(double),
2230         address_index * ((s->parameters.divisor+1) * (s->parameters.divisor+1)),
2231         ((s->parameters.divisor+1) * (s->parameters.divisor+1)), agent->m);
2232     LOG(GNUNET_ERROR_TYPE_DEBUG, "sec\n");
2233     ril_cut_from_vector ((void **) &agent->E[i], sizeof(double),
2234         address_index * ((s->parameters.divisor+1) * (s->parameters.divisor+1)),
2235         ((s->parameters.divisor+1) * (s->parameters.divisor+1)), agent->m);
2236   }
2237   GNUNET_free_non_null(agent->W[RIL_ACTION_TYPE_NUM + address_index]);
2238   GNUNET_free_non_null(agent->E[RIL_ACTION_TYPE_NUM + address_index]);
2239   LOG(GNUNET_ERROR_TYPE_DEBUG, "third\n");
2240   ril_cut_from_vector ((void **) &agent->W, sizeof(double *), RIL_ACTION_TYPE_NUM + address_index,
2241       1, agent->n);
2242   LOG(GNUNET_ERROR_TYPE_DEBUG, "fourth\n");
2243   ril_cut_from_vector ((void **) &agent->E, sizeof(double *), RIL_ACTION_TYPE_NUM + address_index,
2244       1, agent->n);
2245   //correct last action
2246   if (agent->a_old > (RIL_ACTION_TYPE_NUM + address_index))
2247   {
2248     agent->a_old -= 1;
2249   }
2250   else if (agent->a_old == (RIL_ACTION_TYPE_NUM + address_index))
2251   {
2252     agent->a_old = RIL_ACTION_INVALID;
2253   }
2254   //decrease old state vector
2255   LOG(GNUNET_ERROR_TYPE_DEBUG, "fifth\n");
2256   ril_cut_from_vector ((void **) &agent->s_old, sizeof(double),
2257       address_index * ((s->parameters.divisor+1) * (s->parameters.divisor+1)),
2258       ((s->parameters.divisor+1) * (s->parameters.divisor+1)), agent->m);
2259   agent->m = m_new;
2260   agent->n = n_new;
2261
2262   if (address_was_used)
2263   {
2264     if (NULL != agent->addresses_head) //if peer has an address left, use it
2265     {
2266       envi_set_active_suggestion (s, agent, agent->addresses_head->address_naked, MIN_BW, MIN_BW,
2267           GNUNET_NO);
2268     }
2269     else
2270     {
2271       envi_set_active_suggestion (s, agent, NULL, 0, 0, GNUNET_NO);
2272     }
2273   }
2274
2275   ril_step (solver);
2276 }
2277
2278 /**
2279  * Update the properties of an address in the solver
2280  *
2281  * @param solver solver handle
2282  * @param address the address
2283  * @param type the ATSI type in HBO
2284  * @param abs_value the absolute value of the property
2285  * @param rel_value the normalized value
2286  */
2287 void
2288 GAS_ril_address_property_changed (void *solver,
2289     struct ATS_Address *address,
2290     uint32_t type,
2291     uint32_t abs_value,
2292     double rel_value)
2293 {
2294   LOG(GNUNET_ERROR_TYPE_DEBUG,
2295       "API_address_property_changed() Property '%s' for peer '%s' address %s changed "
2296           "to %.2f \n", GNUNET_ATS_print_property_type (type), GNUNET_i2s (&address->peer),
2297       address->addr, rel_value);
2298
2299   ril_step (solver);
2300 }
2301
2302 /**
2303  * Update the session of an address in the solver
2304  *
2305  * NOTE: values in addresses are already updated
2306  *
2307  * @param solver solver handle
2308  * @param address the address
2309  * @param cur_session the current session
2310  * @param new_session the new session
2311  */
2312 void
2313 GAS_ril_address_session_changed (void *solver,
2314     struct ATS_Address *address,
2315     uint32_t cur_session,
2316     uint32_t new_session)
2317 {
2318   /*
2319    * TODO? Future Work: Potentially add session activity as a feature in state vector
2320    */
2321   LOG(GNUNET_ERROR_TYPE_DEBUG, "API_address_session_changed()\n");
2322 }
2323
2324 /**
2325  * Notify the solver that an address is (not) actively used by transport
2326  * to communicate with a remote peer
2327  *
2328  * NOTE: values in addresses are already updated
2329  *
2330  * @param solver solver handle
2331  * @param address the address
2332  * @param in_use usage state
2333  */
2334 void
2335 GAS_ril_address_inuse_changed (void *solver, struct ATS_Address *address, int in_use)
2336 {
2337   /*
2338    * TODO? Future Work: Potentially add usage variable to state vector
2339    */
2340   LOG(GNUNET_ERROR_TYPE_DEBUG,
2341       "API_address_inuse_changed() Usage for %s address of peer '%s' changed to %s\n",
2342       address->plugin, GNUNET_i2s (&address->peer), (GNUNET_YES == in_use) ? "USED" : "UNUSED");
2343 }
2344
2345 /**
2346  * Notify solver that the network an address is located in has changed
2347  *
2348  * NOTE: values in addresses are already updated
2349  *
2350  * @param solver solver handle
2351  * @param address the address
2352  * @param current_network the current network
2353  * @param new_network the new network
2354  */
2355 void
2356 GAS_ril_address_change_network (void *solver,
2357     struct ATS_Address *address,
2358     uint32_t current_network,
2359     uint32_t new_network)
2360 {
2361   struct GAS_RIL_Handle *s = solver;
2362   struct RIL_Peer_Agent *agent;
2363
2364   LOG(GNUNET_ERROR_TYPE_DEBUG, "API_address_change_network() Network type changed, moving "
2365       "%s address of peer %s from '%s' to '%s'\n",
2366       (GNUNET_YES == address->active) ? "active" : "inactive", GNUNET_i2s (&address->peer),
2367       GNUNET_ATS_print_network_type (current_network), GNUNET_ATS_print_network_type (new_network));
2368
2369   if (address->active && !ril_network_is_active (solver, new_network))
2370   {
2371     GAS_ril_address_delete (solver, address, GNUNET_NO);
2372     return;
2373   }
2374
2375   agent = ril_get_agent (s, &address->peer, GNUNET_NO);
2376   if (NULL == agent)
2377   {
2378     GNUNET_assert(!ril_network_is_active (solver, current_network));
2379
2380     GAS_ril_address_add (s, address, new_network);
2381     return;
2382   }
2383
2384   address->solver_information = ril_get_network(solver, new_network);
2385 }
2386
2387 /**
2388  * Give feedback about the current assignment
2389  *
2390  * @param solver the solver handle
2391  * @param application the application
2392  * @param peer the peer to change the preference for
2393  * @param scope the time interval for this feedback: [now - scope .. now]
2394  * @param kind the kind to change the preference
2395  * @param score the score
2396  */
2397 void
2398 GAS_ril_address_preference_feedback (void *solver,
2399     void *application,
2400     const struct GNUNET_PeerIdentity *peer,
2401     const struct GNUNET_TIME_Relative scope,
2402     enum GNUNET_ATS_PreferenceKind kind,
2403     double score)
2404 {
2405   LOG(GNUNET_ERROR_TYPE_DEBUG,
2406       "API_address_preference_feedback() Peer '%s' got a feedback of %+.3f from application %s for "
2407           "preference %s for %d seconds\n", GNUNET_i2s (peer), "UNKNOWN",
2408       GNUNET_ATS_print_preference_type (kind), scope.rel_value_us / 1000000);
2409 }
2410
2411 /**
2412  * Start a bulk operation
2413  *
2414  * @param solver the solver
2415  */
2416 void
2417 GAS_ril_bulk_start (void *solver)
2418 {
2419   struct GAS_RIL_Handle *s = solver;
2420
2421   LOG(GNUNET_ERROR_TYPE_DEBUG, "API_bulk_start() lock: %d\n", s->bulk_lock+1);
2422
2423   s->bulk_lock++;
2424 }
2425
2426 /**
2427  * Bulk operation done
2428  *
2429  * @param solver the solver handle
2430  */
2431 void
2432 GAS_ril_bulk_stop (void *solver)
2433 {
2434   struct GAS_RIL_Handle *s = solver;
2435
2436   LOG(GNUNET_ERROR_TYPE_DEBUG, "API_bulk_stop() lock: %d\n", s->bulk_lock-1);
2437
2438   if (s->bulk_lock < 1)
2439   {
2440     GNUNET_break(0);
2441     return;
2442   }
2443   s->bulk_lock--;
2444
2445   if (0 < s->bulk_changes)
2446   {
2447     ril_step (solver);
2448     s->bulk_changes = 0;
2449   }
2450 }
2451
2452 /**
2453  * Tell solver to notify ATS if the address to use changes for a specific
2454  * peer using the bandwidth changed callback
2455  *
2456  * The solver must only notify about changes for peers with pending address
2457  * requests!
2458  *
2459  * @param solver the solver handle
2460  * @param peer the identity of the peer
2461  */
2462 const struct ATS_Address *
2463 GAS_ril_get_preferred_address (void *solver, const struct GNUNET_PeerIdentity *peer)
2464 {
2465   /*
2466    * activate agent, return currently chosen address
2467    */
2468   struct GAS_RIL_Handle *s = solver;
2469   struct RIL_Peer_Agent *agent;
2470
2471   LOG(GNUNET_ERROR_TYPE_DEBUG, "API_get_preferred_address()\n");
2472
2473   agent = ril_get_agent (s, peer, GNUNET_YES);
2474
2475   agent->is_active = GNUNET_YES;
2476   envi_set_active_suggestion (solver, agent, agent->address_inuse, agent->bw_in, agent->bw_out, GNUNET_YES);
2477
2478   ril_try_unblock_agent(solver, agent, GNUNET_YES);
2479
2480   if (agent->address_inuse)
2481   {
2482     LOG(GNUNET_ERROR_TYPE_DEBUG,
2483         "API_get_preferred_address() Activated agent for peer '%s' with %s address %s\n",
2484         GNUNET_i2s (peer), agent->address_inuse->plugin, agent->address_inuse->addr);
2485   }
2486   else
2487   {
2488     LOG(GNUNET_ERROR_TYPE_DEBUG,
2489         "API_get_preferred_address() Activated agent for peer '%s', but no address available\n",
2490         GNUNET_i2s (peer));
2491   }
2492
2493   return agent->address_inuse;
2494 }
2495
2496 /**
2497  * Tell solver stop notifying ATS about changes for this peers
2498  *
2499  * The solver must only notify about changes for peers with pending address
2500  * requests!
2501  *
2502  * @param solver the solver handle
2503  * @param peer the peer
2504  */
2505 void
2506 GAS_ril_stop_get_preferred_address (void *solver, const struct GNUNET_PeerIdentity *peer)
2507 {
2508   struct GAS_RIL_Handle *s = solver;
2509   struct RIL_Peer_Agent *agent;
2510
2511   LOG(GNUNET_ERROR_TYPE_DEBUG, "API_stop_get_preferred_address()");
2512
2513   agent = ril_get_agent (s, peer, GNUNET_NO);
2514
2515   if (NULL == agent)
2516   {
2517     GNUNET_break(0);
2518     return;
2519   }
2520   if (GNUNET_NO == agent->is_active)
2521   {
2522     GNUNET_break(0);
2523     return;
2524   }
2525
2526   agent->is_active = GNUNET_NO;
2527
2528   envi_set_active_suggestion (s, agent, agent->address_inuse, agent->bw_in, agent->bw_out,
2529       GNUNET_YES);
2530
2531   ril_step (s);
2532
2533   LOG(GNUNET_ERROR_TYPE_DEBUG,
2534       "API_stop_get_preferred_address() Paused agent for peer '%s' with %s address\n",
2535       GNUNET_i2s (peer), agent->address_inuse->plugin);
2536 }
2537
2538 /* end of plugin_ats_ril.c */