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 LOG(kind,...) GNUNET_log_from (kind, "ats-ril",__VA_ARGS__)
  34
  35 #define RIL_ACTION_INVALID -1
  36 #define RIL_FEATURES_ADDRESS_COUNT (3 + GNUNET_ATS_QualityPropertiesCount)
  37 #define RIL_FEATURES_NETWORK_COUNT 4
  38
  39 #define RIL_DEFAULT_STEP_TIME GNUNET_TIME_relative_multiply (GNUNET_TIME_UNIT_MILLISECONDS, 3000)
  40 #define RIL_DEFAULT_ALGORITHM RIL_ALGO_Q
  41 #define RIL_DEFAULT_DISCOUNT_FACTOR 0.5
  42 #define RIL_DEFAULT_GRADIENT_STEP_SIZE 0.4
  43 #define RIL_DEFAULT_TRACE_DECAY 0.6
  44 #define RIL_EXPLORE_RATIO 0.1
  45
  46 /**
  47  * ATS reinforcement learning solver
  48  *
  49  * General description
  50  */
  51
  52 enum RIL_Action_Type
  53 {
  54   RIL_ACTION_NOTHING = 0,
  55   RIL_ACTION_BW_IN_DBL = 1,
  56   RIL_ACTION_BW_IN_HLV = 2,
  57   RIL_ACTION_BW_IN_INC = 3,
  58   RIL_ACTION_BW_IN_DEC = 4,
  59   RIL_ACTION_BW_OUT_DBL = 5,
  60   RIL_ACTION_BW_OUT_HLV = 6,
  61   RIL_ACTION_BW_OUT_INC = 7,
  62   RIL_ACTION_BW_OUT_DEC = 8,
  63   RIL_ACTION_TYPE_NUM = 9
  64 };
  65
  66 enum RIL_Algorithm
  67 {
  68   RIL_ALGO_SARSA = 0,
  69   RIL_ALGO_Q = 1
  70 };
  71
  72 enum RIL_E_Modification
  73 {
  74   RIL_E_SET,
  75   RIL_E_ZERO,
  76   RIL_E_ACCUMULATE,
  77   RIL_E_REPLACE
  78 };
  79
  80 /**
  81  * Global learning parameters
  82  */
  83 struct RIL_Learning_Parameters
  84 {
  85   /**
  86    * The TD-algorithm to use
  87    */
  88   enum RIL_Algorithm algorithm;
  89
  90   /**
  91    * Learning discount factor in the TD-update
  92    */
  93   float gamma;
  94
  95   /**
  96    * Gradient-descent step-size
  97    */
  98   float alpha;
  99
 100   /**
 101    * Trace-decay factor for eligibility traces
 102    */
 103   float lambda;
 104 };
 105
 106 /**
 107  * Wrapper for addresses to store them in agent's linked list
 108  */
 109 struct RIL_Address_Wrapped
 110 {
 111   /**
 112    * Next in DLL
 113    */
 114   struct RIL_Address_Wrapped *next;
 115
 116   /**
 117    * Previous in DLL
 118    */
 119   struct RIL_Address_Wrapped *prev;
 120
 121   /**
 122    * The address
 123    */
 124   struct ATS_Address *address_naked;
 125 };
 126
 127 struct RIL_Peer_Agent
 128 {
 129   /**
 130    * Next agent in solver's linked list
 131    */
 132   struct RIL_Peer_Agent *next;
 133
 134   /**
 135    * Previous agent in solver's linked list
 136    */
 137   struct RIL_Peer_Agent *prev;
 138
 139   /**
 140    * Environment handle
 141    */
 142   struct GAS_RIL_Handle *envi;
 143
 144   /**
 145    * Peer ID
 146    */
 147   struct GNUNET_PeerIdentity peer;
 148
 149   /**
 150    * Whether the agent is active or not
 151    */
 152   int active; //TODO? rename into "requested", since it rather depicts whether there is a request pending for it
 153
 154   /**
 155    * Number of performed time-steps
 156    */
 157   unsigned long long step_count;
 158
 159   /**
 160    * Experience matrix W
 161    */
 162   double ** W;
 163
 164   /**
 165    * Number of rows of W / Number of state-vector features
 166    */
 167   unsigned int m;
 168
 169   /**
 170    * Number of columns of W / Number of actions
 171    */
 172   unsigned int n;
 173
 174   /**
 175    * Last perceived state feature vector
 176    */
 177   double * s_old;
 178
 179   /**
 180    * Last chosen action
 181    */
 182   int a_old;
 183
 184   /**
 185    * Eligibility trace vector
 186    */
 187   double * e;
 188
 189   /**
 190    * Address in use
 191    */
 192   struct ATS_Address * address_inuse;
 193
 194   /**
 195    * Head of addresses DLL
 196    */
 197   struct RIL_Address_Wrapped * addresses_head;
 198
 199   /**
 200    * Tail of addresses DLL
 201    */
 202   struct RIL_Address_Wrapped * addresses_tail;
 203
 204   /**
 205    * Inbound bandwidth assigned by the agent
 206    */
 207   unsigned long long bw_in;
 208
 209   /**
 210    * Outbound bandwidth assigned by the agent
 211    */
 212   unsigned long long bw_out;
 213 };
 214
 215 struct RIL_Network
 216 {
 217   /**
 218    * ATS network type
 219    */
 220   enum GNUNET_ATS_Network_Type type;
 221
 222   /**
 223    * Total available inbound bandwidth
 224    */
 225   unsigned long long bw_in_available;
 226
 227   /**
 228    * Total assigned outbound bandwidth
 229    */
 230   unsigned long long bw_in_assigned;
 231
 232   /**
 233    * Total available outbound bandwidth
 234    */
 235   unsigned long long bw_out_available;
 236
 237   /**
 238    * Total assigned outbound bandwidth
 239    */
 240   unsigned long long bw_out_assigned;
 241 };
 242
 243 struct RIL_Callbacks
 244 {
 245   /**
 246    * Bandwidth changed callback
 247    */
 248   GAS_bandwidth_changed_cb bw_changed;
 249
 250   /**
 251    * Bandwidth changed callback cls
 252    */
 253   void *bw_changed_cls;
 254
 255   /**
 256    * ATS function to get preferences for a peer
 257    */
 258   GAS_get_preferences get_preferences;
 259
 260   /**
 261    * Closure for ATS function to get preferences
 262    */
 263   void *get_preferences_cls;
 264
 265   /**
 266    * ATS function to get properties of an address
 267    */
 268   GAS_get_properties get_properties;
 269
 270   /**
 271    * Closure for ATS function to get properties
 272    */
 273   void *get_properties_cls;
 274 };
 275
 276 /**
 277  * A handle for the reinforcement learning solver
 278  */
 279 struct GAS_RIL_Handle
 280 {
 281   /**
 282    * Statistics handle
 283    */
 284   struct GNUNET_STATISTICS_Handle *stats;
 285
 286   /**
 287    * Hashmap containing all valid addresses
 288    */
 289   const struct GNUNET_CONTAINER_MultiPeerMap *addresses;
 290
 291   /**
 292    * Callbacks for the solver
 293    */
 294   struct RIL_Callbacks *callbacks;
 295
 296   /**
 297    * Bulk lock
 298    */
 299   int bulk_lock;
 300
 301   /**
 302    * Number of changes while solver was locked
 303    */
 304   int bulk_requests;
 305
 306   /**
 307    * Number of performed time-steps
 308    */
 309   unsigned long long step_count;
 310
 311   /**
 312    * Interval time between steps in milliseconds //TODO? put in agent
 313    */
 314   struct GNUNET_TIME_Relative step_time;
 315
 316   /**
 317    * Task identifier of the next time-step to be executed //TODO? put in agent
 318    */
 319   GNUNET_SCHEDULER_TaskIdentifier next_step;
 320
 321   /**
 322    * Learning parameters
 323    */
 324   struct RIL_Learning_Parameters parameters;
 325
 326   /**
 327    * Array of networks with global assignment state
 328    */
 329   struct RIL_Network * network_entries;
 330
 331   /**
 332    * Networks count
 333    */
 334   unsigned int networks_count;
 335
 336   /**
 337    * List of active peer-agents
 338    */
 339   struct RIL_Peer_Agent * agents_head;
 340   struct RIL_Peer_Agent * agents_tail;
 341 };
 342
 343 /*
 344  *  Private functions
 345  *  ---------------------------
 346  */
 347
 348 /**
 349  * Estimate the current action-value for state s and action a
 350  * @param agent agent performing the estimation
 351  * @param state s
 352  * @param action a
 353  * @return estimation value
 354  */
 355 static double
 356 agent_estimate_q (struct RIL_Peer_Agent *agent, double *state, int action)
 357 {
 358   int i;
 359   double result = 0;
 360
 361   for (i = 0; i < agent->m; i++)
 362   {
 363     result += state[i] * agent->W[action][i];
 364   }
 365
 366   return result;
 367 }
 368
 369 /**
 370  * Decide whether to do exploration (i.e. taking a new action) or exploitation (i.e. taking the
 371  * currently estimated best action) in the current step
 372  * @param agent agent performing the step
 373  * @return yes, if exploring
 374  */
 375 static int
 376 agent_decide_exploration (struct RIL_Peer_Agent *agent)
 377 {
 378   double r = (double) GNUNET_CRYPTO_random_u32 (GNUNET_CRYPTO_QUALITY_WEAK,
 379       UINT32_MAX) / (double) UINT32_MAX;
 380
 381 if  (r < RIL_EXPLORE_RATIO)
 382   {
 383     return GNUNET_YES;
 384   }
 385   return GNUNET_NO;
 386 }
 387
 388 /**
 389  * Get the index of the address in the agent's list.
 390  * @param agent agent handle
 391  * @param address address handle
 392  * @return the index, starting with zero
 393  */
 394 static int
 395 agent_address_get_index (struct RIL_Peer_Agent *agent, struct ATS_Address *address)
 396 {
 397   int i;
 398   struct RIL_Address_Wrapped *cur;
 399
 400   i = -1;
 401   for (cur = agent->addresses_head; NULL != cur; cur = cur->next)
 402   {
 403     i++;
 404     if (cur->address_naked == address)
 405     {
 406       return i;
 407     }
 408   }
 409
 410   return i;
 411 }
 412
 413 /**
 414  * Gets the wrapped address from the agent's list
 415  * @param agent agent handle
 416  * @param address address handle
 417  * @return wrapped address
 418  */
 419 static struct RIL_Address_Wrapped *
 420 agent_address_get (struct RIL_Peer_Agent *agent, struct ATS_Address *address)
 421 {
 422   struct RIL_Address_Wrapped *cur;
 423
 424   for (cur = agent->addresses_head; NULL != cur; cur = cur->next)
 425   {
 426     if (cur->address_naked == address)
 427     {
 428       return cur;
 429     }
 430   }
 431
 432   return NULL ;
 433 }
 434
 435 /**
 436  * Gets the action, with the maximal estimated Q-value (i.e. the one currently estimated to bring the
 437  * most reward in the future)
 438  * @param agent agent performing the calculation
 439  * @param state the state from which to take the action
 440  * @return the action promising most future reward
 441  */
 442 static int
 443 agent_get_action_best (struct RIL_Peer_Agent *agent, double *state)
 444 {
 445   int i;
 446   int max_i = RIL_ACTION_INVALID;
 447   double cur_q;
 448   double max_q = -DBL_MAX;
 449
 450   for (i = 0; i < agent->n; i++)
 451   {
 452     cur_q = agent_estimate_q (agent, state, i);
 453     if (cur_q > max_q)
 454     {
 455       max_q = cur_q;
 456       max_i = i;
 457     }
 458   }
 459
 460   GNUNET_assert(RIL_ACTION_INVALID != max_i);
 461
 462   return max_i;
 463 }
 464
 465 /**
 466  * Gets any action, to explore the action space from that state
 467  * @param agent agent performing the calculation
 468  * @param state the state from which to take the action
 469  * @return any action
 470  */
 471 static int
 472 agent_get_action_explore (struct RIL_Peer_Agent *agent, double *state)
 473 {
 474   return GNUNET_CRYPTO_random_u32 (GNUNET_CRYPTO_QUALITY_WEAK, agent->n);
 475 }
 476
 477 /**
 478  * Updates the weights (i.e. coefficients) of the weight vector in matrix W for action a
 479  * @param agent the agent performing the update
 480  * @param reward the reward received for the last action
 481  * @param s_next the new state, the last step got the agent into
 482  * @param a_prime the new
 483  */
 484 static void
 485 agent_update_weights (struct RIL_Peer_Agent *agent, double reward, double *s_next, int a_prime)
 486 {
 487   int i;
 488   double delta;
 489   double *theta = agent->W[agent->a_old];
 490
 491   delta = reward + agent_estimate_q (agent, s_next, a_prime)
 492       - agent_estimate_q (agent, agent->s_old, agent->a_old);
 493   for (i = 0; i < agent->m; i++)
 494   {
 495     theta[i] += agent->envi->parameters.alpha * delta * (agent->e)[i];
 496   }
 497 }
 498
 499 /**
 500  * Changes the eligibility trace vector e in various manners:
 501  * RIL_E_ACCUMULATE - adds 1 to each component as in accumulating eligibility traces
 502  * RIL_E_REPLACE - resets each component to 1 as in replacing traces
 503  * RIL_E_SET - multiplies e with gamma and lambda as in the update rule
 504  * RIL_E_ZERO - sets e to 0 as in Watkin's Q-learning algorithm when exploring and when initializing
 505  * @param agent
 506  * @param mod
 507  */
 508 static void
 509 agent_modify_eligibility (struct RIL_Peer_Agent *agent, enum RIL_E_Modification mod)
 510 {
 511   int i;
 512   double *e = agent->e;
 513   double gamma = agent->envi->parameters.gamma;
 514   double lambda = agent->envi->parameters.lambda;
 515
 516   for (i = 0; i < agent->m; i++)
 517   {
 518     switch (mod)
 519     {
 520     case RIL_E_ACCUMULATE:
 521       e[i] += 1;
 522       break;
 523     case RIL_E_REPLACE:
 524       e[i] = 1;
 525       break;
 526     case RIL_E_SET:
 527       e[i] = gamma * lambda;
 528       break;
 529     case RIL_E_ZERO:
 530       e[i] = 0;
 531       break;
 532     }
 533   }
 534 }
 535
 536 /**
 537  * Changes the active assignment suggestion of the handler and invokes the bw_changed callback to
 538  * notify ATS of its new decision.
 539  * @param solver solver handle
 540  * @param agent agent handle
 541  * @param new_address the address which is to be used
 542  * @param new_bw_in the new amount of inbound bandwidth set for this address
 543  * @param new_bw_out the new amount of outbound bandwidth set for this address
 544  * @param silent disables invocation of the bw_changed callback, if GNUNET_YES
 545  */
 546 static void
 547 envi_set_active_suggestion (struct GAS_RIL_Handle *solver,
 548     struct RIL_Peer_Agent *agent,
 549     struct ATS_Address *new_address,
 550     unsigned long long new_bw_in,
 551     unsigned long long new_bw_out,
 552     int silent)
 553 {
 554   int notify = GNUNET_NO;
 555
 556   LOG (GNUNET_ERROR_TYPE_DEBUG, "set_active_suggestion()\n");
 557
 558   //address change
 559   if (agent->address_inuse != new_address)
 560   {
 561     if (NULL != agent->address_inuse)
 562     {
 563       agent->address_inuse->active = GNUNET_NO;
 564       agent->address_inuse->assigned_bw_in.value__ = htonl (0);
 565       agent->address_inuse->assigned_bw_out.value__ = htonl (0);
 566     }
 567     if (NULL != new_address)
 568     {
 569       LOG (GNUNET_ERROR_TYPE_DEBUG, "set address active: %s\n", agent->active ? "yes" : "no");
 570       new_address->active = agent->active;
 571       new_address->assigned_bw_in.value__ = htonl (agent->bw_in);
 572       new_address->assigned_bw_out.value__ = htonl (agent->bw_out);
 573     }
 574     notify |= GNUNET_YES;
 575   }
 576
 577   if (new_address)
 578   {
 579     //activity change
 580     if (new_address->active != agent->active)
 581     {
 582       new_address->active = agent->active;
 583     }
 584
 585     //bw change
 586     if (agent->bw_in != new_bw_in)
 587     {
 588       agent->bw_in = new_bw_in;
 589       new_address->assigned_bw_in.value__ = htonl (new_bw_out);
 590       notify |= GNUNET_YES;
 591     }
 592     if (agent->bw_out != new_bw_out)
 593     {
 594       agent->bw_out = new_bw_out;
 595       new_address->assigned_bw_out.value__ = htonl (new_bw_out);
 596       notify |= GNUNET_YES;
 597     }
 598   }
 599
 600   if (notify && agent->active && (GNUNET_NO == silent))
 601   {
 602     if (new_address)
 603     {
 604       solver->callbacks->bw_changed (solver->callbacks->bw_changed_cls, new_address);
 605     }
 606     else
 607     {
 608       GNUNET_assert (0 == ntohl(agent->address_inuse->assigned_bw_in.value__));
 609       GNUNET_assert (0 == ntohl(agent->address_inuse->assigned_bw_out.value__));
 610       agent->bw_in = 0;
 611       agent->bw_out = 0;
 612       //disconnect
 613       solver->callbacks->bw_changed (solver->callbacks->bw_changed_cls, agent->address_inuse);
 614     }
 615   }
 616   agent->address_inuse = new_address;
 617 }
 618
 619 /**
 620  * Allocates a state vector and fills it with the features present
 621  * @param solver the solver handle
 622  * @return pointer to the state vector
 623  */
 624 static double *
 625 envi_get_state (struct GAS_RIL_Handle *solver, struct RIL_Peer_Agent *agent)
 626 {
 627   int i;
 628   int k;
 629   struct RIL_Network *net;
 630   double *state = GNUNET_malloc (sizeof (double) * agent->m);
 631   struct RIL_Address_Wrapped *cur_address;
 632   const double *properties;
 633
 634   for (i = 0; i < solver->networks_count; i++)
 635   {
 636     net = &solver->network_entries[i];
 637     state[i * RIL_FEATURES_NETWORK_COUNT + 0] = (double) net->bw_in_assigned;
 638     state[i * RIL_FEATURES_NETWORK_COUNT + 1] = (double) net->bw_in_available;
 639     state[i * RIL_FEATURES_NETWORK_COUNT + 2] = (double) net->bw_out_assigned;
 640     state[i * RIL_FEATURES_NETWORK_COUNT + 3] = (double) net->bw_out_available;
 641   }
 642
 643   i = i * RIL_FEATURES_NETWORK_COUNT; //first address feature
 644
 645   for (cur_address = agent->addresses_head; NULL != cur_address; cur_address = cur_address->next)
 646   {
 647     state[i++] = cur_address->address_naked->active;
 648     state[i++] = cur_address->address_naked->active ? agent->bw_in : 0;
 649     state[i++] = cur_address->address_naked->active ? agent->bw_out : 0;
 650     properties = solver->callbacks->get_properties (solver->callbacks->get_properties_cls, cur_address->address_naked);
 651     for (k = 0; k < GNUNET_ATS_QualityPropertiesCount; k++)
 652     {
 653       state[i++] = properties[k];
 654     }
 655   }
 656
 657   return state;
 658 }
 659
 660 /**
 661  * For all networks a peer has an address in, this gets the maximum bandwidth which could
 662  * theoretically be available in one of the networks. This is used for bandwidth normalization.
 663  * @param solver the solver handle
 664  * @param agent the agent handle
 665  * @param direction_in whether the inbound bandwidth should be considered. Returns the maximum outbound bandwidth if GNUNET_NO
 666  */
 667 static long long unsigned
 668 ril_get_max_bw(struct RIL_Peer_Agent *agent, int direction_in)
 669 {
 670   /*
 671    * get the maximum bandwidth possible for a peer, e.g. among all addresses which addresses'
 672    * network could provide the maximum bandwidth if all that bandwidth was used on that one peer.
 673    */
 674   int max = 0;
 675   struct RIL_Address_Wrapped *cur;
 676   struct RIL_Network *net;
 677
 678   for (cur = agent->addresses_head; NULL != cur; cur = cur->next)
 679   {
 680     net = cur->address_naked->solver_information;
 681     if (direction_in)
 682     {
 683       if (net->bw_in_available > max)
 684       {
 685         max = net->bw_in_available;
 686       }
 687     }
 688     else
 689     {
 690       if (net->bw_out_available > max)
 691       {
 692         max = net->bw_out_available;
 693       }
 694     }
 695   }
 696   return max;
 697 }
 698
 699 /**
 700  * Gets the reward of the last performed step
 701  * @param solver solver handle
 702  * @return the reward
 703  */
 704 static double
 705 envi_get_reward (struct GAS_RIL_Handle *solver, struct RIL_Peer_Agent *agent)
 706 {
 707   /*
 708    * Match the preferences of the peer with the current assignment.
 709    */
 710   const double *preferences;
 711   const double *properties;
 712   double pref_match = 0;
 713   double bw_norm;
 714   struct RIL_Network *net;
 715
 716   preferences = solver->callbacks->get_preferences (solver->callbacks->get_preferences_cls, &agent->peer);
 717   properties = solver->callbacks->get_properties (solver->callbacks->get_properties_cls,
 718       agent->address_inuse);
 719   pref_match += preferences[GNUNET_ATS_PREFERENCE_LATENCY] * properties[GNUNET_ATS_QUALITY_NET_DELAY];
 720   bw_norm = GNUNET_MAX(2, (((
 721       ((double) agent->bw_in / (double) ril_get_max_bw(agent, GNUNET_YES)) +
 722       ((double) agent->bw_out / (double) ril_get_max_bw(agent, GNUNET_NO))
 723       ) / 2
 724       ) + 1));
 725   pref_match += preferences[GNUNET_ATS_PREFERENCE_BANDWIDTH] * bw_norm;
 726
 727   net = agent->address_inuse->solver_information;
 728   if ((net->bw_in_assigned > net->bw_in_available) || net->bw_out_assigned > net->bw_out_available)
 729   {
 730     return -1;
 731   }
 732
 733   return pref_match;
 734 }
 735
 736 /**
 737  * Doubles the bandwidth for the active address
 738  * @param solver solver handle
 739  * @param agent agent handle
 740  * @param direction_in if GNUNET_YES, change inbound bandwidth, otherwise the outbound bandwidth
 741  */
 742 static void
 743 envi_action_bw_double (struct GAS_RIL_Handle *solver,
 744     struct RIL_Peer_Agent *agent,
 745     int direction_in)
 746 {
 747   if (direction_in)
 748   {
 749     envi_set_active_suggestion (solver, agent, agent->address_inuse, agent->bw_in * 2,
 750         agent->bw_out, GNUNET_NO);
 751   }
 752   else
 753   {
 754     envi_set_active_suggestion (solver, agent, agent->address_inuse, agent->bw_in,
 755         agent->bw_out * 2, GNUNET_NO);
 756   }
 757 }
 758
 759 /**
 760  * Cuts the bandwidth for the active address in half. The least amount of bandwidth suggested, is
 761  * the minimum bandwidth for a peer, in order to not invoke a disconnect.
 762  * @param solver solver handle
 763  * @param agent agent handle
 764  * @param direction_in if GNUNET_YES, change inbound bandwidth, otherwise change the outbound
 765  * bandwidth
 766  */
 767 static void
 768 envi_action_bw_halven (struct GAS_RIL_Handle *solver,
 769     struct RIL_Peer_Agent *agent,
 770     int direction_in)
 771 {
 772   uint32_t min_bw = ntohl (GNUNET_CONSTANTS_DEFAULT_BW_IN_OUT.value__);
 773   unsigned long long new_bw;
 774
 775   if (direction_in)
 776   {
 777     new_bw = agent->bw_in / 2;
 778     if (new_bw < min_bw)
 779       new_bw = min_bw;
 780     envi_set_active_suggestion (solver, agent, agent->address_inuse, new_bw, agent->bw_out, GNUNET_NO);
 781   }
 782   else
 783   {
 784     new_bw = agent->bw_out / 2;
 785     if (new_bw < min_bw)
 786       new_bw = min_bw;
 787     envi_set_active_suggestion (solver, agent, agent->address_inuse, agent->bw_in, new_bw, GNUNET_NO);
 788   }
 789 }
 790
 791 /**
 792  * Increases the bandwidth by 5 times the minimum bandwidth for the active address.
 793  * @param solver solver handle
 794  * @param agent agent handle
 795  * @param direction_in if GNUNET_YES, change inbound bandwidth, otherwise change the outbound
 796  * bandwidth
 797  */
 798 static void
 799 envi_action_bw_inc (struct GAS_RIL_Handle *solver, struct RIL_Peer_Agent *agent, int direction_in)
 800 {
 801   uint32_t min_bw = ntohl (GNUNET_CONSTANTS_DEFAULT_BW_IN_OUT.value__);
 802
 803   if (direction_in)
 804   {
 805     envi_set_active_suggestion (solver, agent, agent->address_inuse, agent->bw_in + (5 * min_bw),
 806         agent->bw_out, GNUNET_NO);
 807   }
 808   else
 809   {
 810     envi_set_active_suggestion (solver, agent, agent->address_inuse, agent->bw_in,
 811         agent->bw_out + (5 * min_bw), GNUNET_NO);
 812   }
 813 }
 814
 815 /**
 816  * Decreases the bandwidth by 5 times the minimum bandwidth for the active address. The least amount
 817  * of bandwidth suggested, is the minimum bandwidth for a peer, in order to not invoke a disconnect.
 818  * @param solver solver handle
 819  * @param agent agent handle
 820  * @param direction_in if GNUNET_YES, change inbound bandwidth, otherwise change the outbound
 821  * bandwidth
 822  */
 823 static void
 824 envi_action_bw_dec (struct GAS_RIL_Handle *solver, struct RIL_Peer_Agent *agent, int direction_in)
 825 {
 826   uint32_t min_bw = ntohl (GNUNET_CONSTANTS_DEFAULT_BW_IN_OUT.value__);
 827   unsigned long long new_bw;
 828
 829   if (direction_in)
 830   {
 831     new_bw = agent->bw_in - (5 * min_bw);
 832     if (new_bw < min_bw)
 833       new_bw = min_bw;
 834     envi_set_active_suggestion (solver, agent, agent->address_inuse, new_bw, agent->bw_out, GNUNET_NO);
 835   }
 836   else
 837   {
 838     new_bw = agent->bw_out - (5 * min_bw);
 839     if (new_bw < min_bw)
 840       new_bw = min_bw;
 841     envi_set_active_suggestion (solver, agent, agent->address_inuse, agent->bw_in, new_bw, GNUNET_NO);
 842   }
 843 }
 844
 845 /**
 846  * Switches to the address given by its index
 847  * @param solver solver handle
 848  * @param agent agent handle
 849  * @param address_index index of the address as it is saved in the agent's list, starting with zero
 850  */
 851 static void
 852 envi_action_address_switch (struct GAS_RIL_Handle *solver,
 853     struct RIL_Peer_Agent *agent,
 854     unsigned int address_index)
 855 {
 856   struct RIL_Address_Wrapped *cur;
 857   int i = 0;
 858
 859   for (cur = agent->addresses_head; NULL != cur; cur = cur->next)
 860   {
 861     if (i == address_index)
 862     {
 863       envi_set_active_suggestion (solver, agent, cur->address_naked, agent->bw_in, agent->bw_out, GNUNET_NO);
 864       return;
 865     }
 866
 867     i++;
 868   }
 869
 870   //no address with address_index exists, in this case this action should not be callable
 871   GNUNET_assert(GNUNET_NO);
 872 }
 873
 874 /**
 875  * Puts the action into effect by calling the according function
 876  * @param solver solver handle
 877  * @param action action to perform by the solver
 878  */
 879 static void
 880 envi_do_action (struct GAS_RIL_Handle *solver, struct RIL_Peer_Agent *agent, int action)
 881 {
 882   unsigned int address_index;
 883
 884   switch (action)
 885   {
 886   case RIL_ACTION_NOTHING:
 887     break;
 888   case RIL_ACTION_BW_IN_DBL:
 889     envi_action_bw_double (solver, agent, GNUNET_YES);
 890     break;
 891   case RIL_ACTION_BW_IN_HLV:
 892     envi_action_bw_halven (solver, agent, GNUNET_YES);
 893     break;
 894   case RIL_ACTION_BW_IN_INC:
 895     envi_action_bw_inc (solver, agent, GNUNET_YES);
 896     break;
 897   case RIL_ACTION_BW_IN_DEC:
 898     envi_action_bw_dec (solver, agent, GNUNET_YES);
 899     break;
 900   case RIL_ACTION_BW_OUT_DBL:
 901     envi_action_bw_double (solver, agent, GNUNET_NO);
 902     break;
 903   case RIL_ACTION_BW_OUT_HLV:
 904     envi_action_bw_halven (solver, agent, GNUNET_NO);
 905     break;
 906   case RIL_ACTION_BW_OUT_INC:
 907     envi_action_bw_inc (solver, agent, GNUNET_NO);
 908     break;
 909   case RIL_ACTION_BW_OUT_DEC:
 910     envi_action_bw_dec (solver, agent, GNUNET_NO);
 911     break;
 912   default:
 913     if ((action >= RIL_ACTION_TYPE_NUM) && (action < agent->n)) //switch address action
 914     {
 915       address_index = action - RIL_ACTION_TYPE_NUM;
 916
 917       GNUNET_assert(address_index >= 0);
 918       GNUNET_assert(
 919           address_index <= agent_address_get_index (agent, agent->addresses_tail->address_naked));
 920
 921       envi_action_address_switch (solver, agent, address_index);
 922       break;
 923     }
 924     // error - action does not exist
 925     GNUNET_assert(GNUNET_NO);
 926   }
 927 }
 928
 929 /**
 930  * Performs one step of the Markov Decision Process. Other than in the literature the step starts
 931  * after having done the last action a_old. It observes the new state s_next and the reward
 932  * received. Then the coefficient update is done according to the SARSA or Q-learning method. The
 933  * next action is put into effect.
 934  * @param agent the agent performing the step
 935  */
 936 static void
 937 agent_step (struct RIL_Peer_Agent *agent)
 938 {
 939   int a_next = RIL_ACTION_INVALID;
 940   double *s_next;
 941   double reward;
 942
 943   s_next = envi_get_state (agent->envi, agent);
 944   reward = envi_get_reward (agent->envi, agent);
 945
 946   LOG(GNUNET_ERROR_TYPE_DEBUG, "agent_step() with algorithm %s\n",
 947       agent->envi->parameters.algorithm ? "Q" : "SARSA");
 948
 949   switch (agent->envi->parameters.algorithm)
 950   {
 951   case RIL_ALGO_SARSA:
 952     agent_modify_eligibility (agent, RIL_E_SET);
 953     if (agent_decide_exploration (agent))
 954     {
 955       a_next = agent_get_action_explore (agent, s_next);
 956     }
 957     else
 958     {
 959       a_next = agent_get_action_best (agent, s_next);
 960     }
 961     if (RIL_ACTION_INVALID != agent->a_old)
 962     {
 963       //updates weights with selected action (on-policy), if not first step
 964       agent_update_weights (agent, reward, s_next, a_next);
 965     }
 966     break;
 967
 968   case RIL_ALGO_Q:
 969     a_next = agent_get_action_best (agent, s_next);
 970     if (RIL_ACTION_INVALID != agent->a_old)
 971     {
 972       //updates weights with best action, disregarding actually selected action (off-policy), if not first step
 973       agent_update_weights (agent, reward, s_next, a_next);
 974     }
 975     if (agent_decide_exploration (agent))
 976     {
 977       a_next = agent_get_action_explore (agent, s_next);
 978       agent_modify_eligibility (agent, RIL_E_ZERO);
 979     }
 980     else
 981     {
 982       a_next = agent_get_action_best (agent, s_next);
 983       agent_modify_eligibility (agent, RIL_E_SET);
 984     }
 985     break;
 986   }
 987
 988   GNUNET_assert(RIL_ACTION_INVALID != a_next);
 989
 990   agent_modify_eligibility (agent, RIL_E_ACCUMULATE);
 991
 992   envi_do_action (agent->envi, agent, a_next);
 993
 994   GNUNET_free(agent->s_old);
 995   agent->s_old = s_next;
 996   agent->a_old = a_next;
 997
 998   agent->step_count += 1;
 999 }
1000
1001 /**
1002  * Cycles through all agents and lets the active ones do a step. Schedules the next step.
1003  * @param solver the solver handle
1004  * @param tc task context for the scheduler
1005  */
1006 static void
1007 ril_periodic_step (void *cls, const struct GNUNET_SCHEDULER_TaskContext *tc)
1008 {
1009   struct GAS_RIL_Handle *solver = cls;
1010   struct RIL_Peer_Agent *cur;
1011
1012   LOG(GNUNET_ERROR_TYPE_DEBUG, "RIL step number %d\n", solver->step_count);
1013
1014   for (cur = solver->agents_head; NULL != cur; cur = cur->next)
1015   {
1016     if (cur->active && cur->address_inuse)
1017     {
1018       agent_step (cur);
1019     }
1020   }
1021
1022   solver->step_count += 1;
1023   solver->next_step = GNUNET_SCHEDULER_add_delayed (solver->step_time, &ril_periodic_step, solver);
1024 }
1025
1026 /**
1027  * Initialize an agent without addresses and its knowledge base
1028  * @param s ril solver
1029  * @param peer the one in question
1030  * @return handle to the new agent
1031  */
1032 static struct RIL_Peer_Agent *
1033 agent_init (void *s, const struct GNUNET_PeerIdentity *peer)
1034 {
1035   int i;
1036   struct GAS_RIL_Handle * solver = s;
1037   struct RIL_Peer_Agent * agent = GNUNET_malloc (sizeof (struct RIL_Peer_Agent));
1038
1039   agent->envi = solver;
1040   agent->peer = *peer;
1041   agent->step_count = 0;
1042   agent->active = GNUNET_NO;
1043   agent->n = RIL_ACTION_TYPE_NUM;
1044   agent->m = solver->networks_count * RIL_FEATURES_NETWORK_COUNT;
1045   agent->W = (double **) GNUNET_malloc (sizeof (double) * agent->n);
1046   for (i = 0; i < agent->n; i++)
1047   {
1048     agent->W[i] = (double *) GNUNET_malloc (sizeof (double) * agent->m);
1049   }
1050   agent->a_old = RIL_ACTION_INVALID;
1051   agent->s_old = envi_get_state (solver, agent);
1052   agent->e = (double *) GNUNET_malloc (sizeof (double) * agent->m);
1053   agent_modify_eligibility (agent, RIL_E_ZERO);
1054
1055   GNUNET_CONTAINER_DLL_insert_tail(solver->agents_head, solver->agents_tail, agent);
1056
1057   return agent;
1058 }
1059
1060 /**
1061  * Deallocate agent
1062  * @param s solver handle
1063  * @param agent the agent to retire
1064  */
1065 static void
1066 agent_die (struct GAS_RIL_Handle *solver, struct RIL_Peer_Agent *agent)
1067 {
1068   int i;
1069
1070   for (i = 0; i < agent->n; i++)
1071   {
1072     GNUNET_free(agent->W[i]);
1073   }
1074   GNUNET_free(agent->W);
1075   GNUNET_free(agent->e);
1076   GNUNET_free(agent->s_old);
1077   GNUNET_free(agent);
1078 }
1079
1080 /**
1081  * Returns the agent for a peer
1082  * @param s solver handle
1083  * @param peer identity of the peer
1084  * @param create whether to create an agent if none is allocated yet
1085  * @return agent
1086  */
1087 static struct RIL_Peer_Agent *
1088 ril_get_agent (struct GAS_RIL_Handle *solver, const struct GNUNET_PeerIdentity *peer, int create)
1089 {
1090   struct RIL_Peer_Agent *cur;
1091
1092   for (cur = solver->agents_head; NULL != cur; cur = cur->next)
1093   {
1094     if (0 == memcmp (peer,
1095                      &cur->peer,
1096                      sizeof (struct GNUNET_PeerIdentity)))
1097     {
1098       return cur;
1099     }
1100   }
1101
1102   if (create)
1103   {
1104     return agent_init (solver, peer);
1105   }
1106   return NULL ;
1107 }
1108
1109 /**
1110  * Lookup network struct by type
1111  *
1112  * @param s the solver handle
1113  * @param type the network type
1114  * @return the network struct
1115  */
1116 static struct RIL_Network *
1117 ril_get_network (struct GAS_RIL_Handle *s, uint32_t type)
1118 {
1119   int i;
1120
1121   for (i = 0; i < s->networks_count; i++)
1122   {
1123     if (s->network_entries[i].type == type)
1124     {
1125       return &s->network_entries[i];
1126     }
1127   }
1128   return NULL ;
1129 }
1130
1131 /**
1132  * Determine whether at least the minimum bandwidth is set for the network. Otherwise the network is
1133  * considered inactive and not used. Addresses in an inactive network are ignored.
1134  * @param solver solver handle
1135  * @param network the network type
1136  * @return
1137  */
1138 static int
1139 ril_network_is_active (struct GAS_RIL_Handle *solver, enum GNUNET_ATS_Network_Type network)
1140 {
1141   struct RIL_Network *net;
1142   uint32_t min_bw = ntohl (GNUNET_CONSTANTS_DEFAULT_BW_IN_OUT.value__);
1143
1144   net = ril_get_network (solver, network);
1145   if (net->bw_out_available < min_bw)
1146     return GNUNET_NO;
1147   return GNUNET_YES;
1148 }
1149
1150 /**
1151  * Cuts a slice out of a vector of elements. This is used to decrease the size of the matrix storing
1152  * the reward function approximation. It copies the memory, which is not cut, to the new vector,
1153  * frees the memory of the old vector, and redirects the pointer to the new one.
1154  * @param old pointer to the pointer to the first element of the vector
1155  * @param element_size byte size of the vector elements
1156  * @param hole_start the first element to cut out
1157  * @param hole_length the number of elements to cut out
1158  * @param old_length the length of the old vector
1159  */
1160 static void
1161 ril_cut_from_vector (void **old,
1162     size_t element_size,
1163     unsigned int hole_start,
1164     unsigned int hole_length,
1165     unsigned int old_length)
1166 {
1167   char *tmpptr;
1168   char *oldptr = (char *) *old;
1169   size_t size;
1170   unsigned int bytes_before;
1171   unsigned int bytes_hole;
1172   unsigned int bytes_after;
1173
1174
1175   GNUNET_assert(old_length > hole_length);
1176   GNUNET_assert(old_length >= (hole_start + hole_length));
1177
1178   size = element_size * (old_length - hole_length);
1179
1180   bytes_before = element_size * hole_start;
1181   bytes_hole = element_size * hole_length;
1182   bytes_after = element_size * (old_length - hole_start - hole_length);
1183
1184   if (0 == size)
1185   {
1186     tmpptr = NULL;
1187   }
1188   else
1189   {
1190     tmpptr = GNUNET_malloc (size);
1191     memcpy (tmpptr, oldptr, bytes_before);
1192     memcpy (tmpptr + bytes_before, oldptr + (bytes_before + bytes_hole), bytes_after);
1193   }
1194   if (NULL != *old)
1195   {
1196     GNUNET_free(*old);
1197   }
1198   *old = (void *) tmpptr;
1199 }
1200
1201 /*
1202  *  Solver API functions
1203  *  ---------------------------
1204  */
1205
1206 /**
1207  * Changes the preferences for a peer in the problem
1208  *
1209  * @param solver the solver handle
1210  * @param peer the peer to change the preference for
1211  * @param kind the kind to change the preference
1212  * @param pref_rel the normalized preference value for this kind over all clients
1213  */
1214 void
1215 GAS_ril_address_change_preference (void *s,
1216     const struct GNUNET_PeerIdentity *peer,
1217     enum GNUNET_ATS_PreferenceKind kind,
1218     double pref_rel)
1219 {
1220   LOG(GNUNET_ERROR_TYPE_DEBUG,
1221       "API_address_change_preference() Preference '%s' for peer '%s' changed to %.2f \n",
1222       GNUNET_ATS_print_preference_type (kind), GNUNET_i2s (peer), pref_rel);
1223   /*
1224    * Nothing to do here. Preferences are considered during reward calculation.
1225    */
1226 }
1227
1228 /**
1229  * Init the reinforcement learning problem solver
1230  *
1231  * Quotas:
1232  * network[i] contains the network type as type GNUNET_ATS_NetworkType[i]
1233  * out_quota[i] contains outbound quota for network type i
1234  * in_quota[i] contains inbound quota for network type i
1235  *
1236  * Example
1237  * network = {GNUNET_ATS_NET_UNSPECIFIED, GNUNET_ATS_NET_LOOPBACK, GNUNET_ATS_NET_LAN, GNUNET_ATS_NET_WAN, GNUNET_ATS_NET_WLAN}
1238  * network[2]   == GNUNET_ATS_NET_LAN
1239  * out_quota[2] == 65353
1240  * in_quota[2]  == 65353
1241  *
1242  * @param cfg configuration handle
1243  * @param stats the GNUNET_STATISTICS handle
1244  * @param network array of GNUNET_ATS_NetworkType with length dest_length
1245  * @param addresses hashmap containing all addresses
1246  * @param out_quota array of outbound quotas
1247  * @param in_quota array of outbound quota
1248  * @param dest_length array length for quota arrays
1249  * @param bw_changed_cb callback for changed bandwidth amounts
1250  * @param bw_changed_cb_cls cls for callback
1251  * @param get_preference callback to get relative preferences for a peer
1252  * @param get_preference_cls cls for callback to get relative preferences
1253  * @param get_properties_cls for callback to get relative properties
1254  * @param get_properties_cls cls for callback to get relative properties
1255  * @return handle for the solver on success, NULL on fail
1256  */
1257 void *
1258 GAS_ril_init (const struct GNUNET_CONFIGURATION_Handle *cfg,
1259     const struct GNUNET_STATISTICS_Handle *stats,
1260     const struct GNUNET_CONTAINER_MultiPeerMap *addresses,
1261     int *network,
1262     unsigned long long *out_quota,
1263     unsigned long long *in_quota,
1264     int dest_length,
1265     GAS_bandwidth_changed_cb bw_changed_cb,
1266     void *bw_changed_cb_cls,
1267     GAS_get_preferences get_preference,
1268     void *get_preference_cls,
1269     GAS_get_properties get_properties,
1270     void *get_properties_cls)
1271 {
1272   int c;
1273   unsigned long long tmp;
1274   char *string;
1275   struct RIL_Network * cur;
1276   struct GAS_RIL_Handle *solver = GNUNET_new (struct GAS_RIL_Handle);
1277
1278   LOG(GNUNET_ERROR_TYPE_DEBUG, "API_init() Initializing RIL solver\n");
1279
1280   GNUNET_assert(NULL != cfg);
1281   GNUNET_assert(NULL != stats);
1282   GNUNET_assert(NULL != network);
1283   GNUNET_assert(NULL != bw_changed_cb);
1284   GNUNET_assert(NULL != get_preference);
1285   GNUNET_assert(NULL != get_properties);
1286
1287   if (GNUNET_OK
1288       != GNUNET_CONFIGURATION_get_value_time (cfg, "ats", "RIL_STEP_TIME", &solver->step_time))
1289   {
1290     solver->step_time = RIL_DEFAULT_STEP_TIME;
1291   }
1292   if (GNUNET_OK == GNUNET_CONFIGURATION_get_value_string (cfg, "ats", "RIL_ALGORITHM", &string)
1293       && NULL != string && 0 == strcmp (string, "SARSA"))
1294   {
1295     solver->parameters.algorithm = RIL_ALGO_SARSA;
1296   }
1297   else
1298   {
1299     solver->parameters.algorithm = RIL_DEFAULT_ALGORITHM;
1300   }
1301   if (GNUNET_OK == GNUNET_CONFIGURATION_get_value_size (cfg, "ats", "RIL_DISCOUNT_FACTOR", &tmp))
1302   {
1303     solver->parameters.gamma = (double) tmp / 100;
1304   }
1305   else
1306   {
1307     solver->parameters.gamma = RIL_DEFAULT_DISCOUNT_FACTOR;
1308   }
1309   if (GNUNET_OK == GNUNET_CONFIGURATION_get_value_size (cfg, "ats", "RIL_GRADIENT_STEP_SIZE", &tmp))
1310   {
1311     solver->parameters.alpha = (double) tmp / 100;
1312   }
1313   else
1314   {
1315     solver->parameters.alpha = RIL_DEFAULT_GRADIENT_STEP_SIZE;
1316   }
1317   if (GNUNET_OK == GNUNET_CONFIGURATION_get_value_size (cfg, "ats", "RIL_TRACE_DECAY", &tmp))
1318   {
1319     solver->parameters.lambda = (double) tmp / 100;
1320   }
1321   else
1322   {
1323     solver->parameters.lambda = RIL_DEFAULT_TRACE_DECAY;
1324   }
1325
1326   solver->stats = (struct GNUNET_STATISTICS_Handle *) stats;
1327   solver->callbacks = GNUNET_malloc (sizeof (struct RIL_Callbacks));
1328   solver->callbacks->bw_changed = bw_changed_cb;
1329   solver->callbacks->bw_changed_cls = bw_changed_cb_cls;
1330   solver->callbacks->get_preferences = get_preference;
1331   solver->callbacks->get_preferences_cls = get_preference_cls;
1332   solver->callbacks->get_properties = get_properties;
1333   solver->callbacks->get_properties_cls = get_properties_cls;
1334   solver->networks_count = dest_length;
1335   solver->network_entries = GNUNET_malloc (dest_length * sizeof (struct RIL_Network));
1336   solver->bulk_lock = GNUNET_NO;
1337   solver->addresses = addresses;
1338   solver->step_count = 0;
1339
1340   for (c = 0; c < dest_length; c++)
1341   {
1342     cur = &solver->network_entries[c];
1343     cur->type = network[c];
1344     cur->bw_in_available = in_quota[c];
1345     cur->bw_in_assigned = 0;
1346     cur->bw_out_available = out_quota[c];
1347     cur->bw_out_assigned = 0;
1348   }
1349
1350   solver->next_step = GNUNET_SCHEDULER_add_delayed (
1351       GNUNET_TIME_relative_multiply (GNUNET_TIME_relative_get_millisecond_ (), 1000),
1352       &ril_periodic_step, solver);
1353
1354   return solver;
1355 }
1356
1357 /**
1358  * Shutdown the reinforcement learning problem solver
1359  *
1360  * @param solver the respective handle to shutdown
1361  */
1362 void
1363 GAS_ril_done (void * solver)
1364 {
1365   struct GAS_RIL_Handle *s = solver;
1366   struct RIL_Peer_Agent *cur_agent;
1367   struct RIL_Peer_Agent *next_agent;
1368
1369   LOG(GNUNET_ERROR_TYPE_DEBUG, "API_done() Shutting down RIL solver\n");
1370
1371   cur_agent = s->agents_head;
1372   while (NULL != cur_agent)
1373   {
1374     next_agent = cur_agent->next;
1375     GNUNET_CONTAINER_DLL_remove(s->agents_head, s->agents_tail, cur_agent);
1376     agent_die (s, cur_agent);
1377     cur_agent = next_agent;
1378   }
1379
1380   GNUNET_SCHEDULER_cancel (s->next_step);
1381   GNUNET_free(s->callbacks);
1382   GNUNET_free(s->network_entries);
1383   GNUNET_free(s);
1384 }
1385
1386 /**
1387  * Add a single address within a network to the solver
1388  *
1389  * @param solver the solver Handle
1390  * @param address the address to add
1391  * @param network network type of this address
1392  */
1393 void
1394 GAS_ril_address_add (void *solver, struct ATS_Address *address, uint32_t network)
1395 {
1396   struct GAS_RIL_Handle *s = solver;
1397   struct RIL_Peer_Agent *agent;
1398   struct RIL_Address_Wrapped *address_wrapped;
1399   struct RIL_Network *net;
1400   unsigned int m_new;
1401   unsigned int m_old;
1402   unsigned int n_new;
1403   unsigned int n_old;
1404   int i;
1405   unsigned int zero;
1406   uint32_t min_bw = ntohl (GNUNET_CONSTANTS_DEFAULT_BW_IN_OUT.value__);
1407
1408   net = ril_get_network (s, network);
1409   address->solver_information = net;
1410
1411   if (!ril_network_is_active (s, network))
1412   {
1413     LOG(GNUNET_ERROR_TYPE_DEBUG,
1414         "API_address_add() Did not add %s address %p for peer '%s', network does not have enough bandwidth\n",
1415         address->plugin, address->addr, GNUNET_i2s (&address->peer));
1416     return;
1417   }
1418
1419   agent = ril_get_agent (s, &address->peer, GNUNET_YES);
1420
1421   //add address
1422   address_wrapped = GNUNET_malloc (sizeof (struct RIL_Address_Wrapped));
1423   address_wrapped->address_naked = address;
1424   GNUNET_CONTAINER_DLL_insert_tail(agent->addresses_head, agent->addresses_tail, address_wrapped);
1425
1426   //increase size of W
1427   m_new = agent->m + RIL_FEATURES_ADDRESS_COUNT;
1428   m_old = agent->m;
1429   n_new = agent->n + 1;
1430   n_old = agent->n;
1431
1432   GNUNET_array_grow(agent->W, agent->n, n_new);
1433   for (i = 0; i < n_new; i++)
1434   {
1435     if (i < n_old)
1436     {
1437       agent->m = m_old;
1438       GNUNET_array_grow(agent->W[i], agent->m, m_new);
1439     }
1440     else
1441     {
1442       zero = 0;
1443       GNUNET_array_grow(agent->W[i], zero, m_new);
1444     }
1445   }
1446
1447   //increase size of old state vector
1448   agent->m = m_old;
1449   GNUNET_array_grow(agent->s_old, agent->m, m_new); //TODO initialize new state features?
1450
1451   agent->m = m_old;
1452   GNUNET_array_grow(agent->e, agent->m, m_new);
1453
1454   if (NULL == agent->address_inuse)
1455   {
1456     net->bw_in_assigned += min_bw;
1457     net->bw_out_assigned += min_bw;
1458     envi_set_active_suggestion (s, agent, address, min_bw, min_bw, GNUNET_NO);
1459   }
1460
1461   LOG(GNUNET_ERROR_TYPE_DEBUG, "API_address_add() Added %s %s address %p for peer '%s'\n",
1462       address->active ? "active" : "inactive",
1463       address->plugin, address->addr, GNUNET_i2s (&address->peer));
1464 }
1465
1466 /**
1467  * Remove an address from the solver
1468  *
1469  * @param solver the solver handle
1470  * @param address the address to remove
1471  * @param session_only delete only session not whole address
1472  */
1473 void
1474 GAS_ril_address_delete (void *solver, struct ATS_Address *address, int session_only)
1475 {
1476   //TODO? use session as feature
1477   struct GAS_RIL_Handle *s = solver;
1478   struct RIL_Peer_Agent *agent;
1479   struct RIL_Address_Wrapped *address_wrapped;
1480   int address_was_used = address->active;
1481   int address_index;
1482   unsigned int m_new;
1483   unsigned int n_new;
1484   int i;
1485   struct RIL_Network *net;
1486   uint32_t min_bw = ntohl (GNUNET_CONSTANTS_DEFAULT_BW_IN_OUT.value__);
1487
1488   LOG(GNUNET_ERROR_TYPE_DEBUG, "API_address_delete() Delete %s%s %s address %p for peer '%s'\n",
1489       session_only ? "session for " : "", address->active ? "active" : "inactive", address->plugin,
1490       address->addr, GNUNET_i2s (&address->peer));
1491
1492   agent = ril_get_agent (s, &address->peer, GNUNET_NO);
1493   if (NULL == agent)
1494   {
1495     net = address->solver_information;
1496     GNUNET_assert(!ril_network_is_active (s, net->type));
1497     LOG(GNUNET_ERROR_TYPE_DEBUG,
1498         "No agent allocated for peer yet, since address was in inactive network\n");
1499     return;
1500   }
1501
1502   address_index = agent_address_get_index (agent, address);
1503   address_wrapped = agent_address_get (agent, address);
1504
1505   if (NULL == address_wrapped)
1506   {
1507     net = address->solver_information;
1508     GNUNET_assert(!ril_network_is_active (s, net->type));
1509     LOG(GNUNET_ERROR_TYPE_DEBUG,
1510         "Address not considered by agent, address was in inactive network\n");
1511     return;
1512   }
1513
1514   GNUNET_CONTAINER_DLL_remove(agent->addresses_head, agent->addresses_tail, address_wrapped);
1515   GNUNET_free(address_wrapped);
1516
1517   //decrease W
1518   m_new = agent->m - RIL_FEATURES_ADDRESS_COUNT;
1519   n_new = agent->n - 1;
1520
1521   for (i = 0; i < agent->n; i++)
1522   {
1523     ril_cut_from_vector ((void **) &agent->W[i], sizeof(double),
1524         ((s->networks_count * RIL_FEATURES_NETWORK_COUNT) + (address_index * RIL_FEATURES_ADDRESS_COUNT)), RIL_FEATURES_ADDRESS_COUNT, agent->m);
1525   }
1526   GNUNET_free (agent->W[RIL_ACTION_TYPE_NUM + address_index]);
1527   ril_cut_from_vector ((void **) &agent->W, sizeof(double *), RIL_ACTION_TYPE_NUM + address_index,
1528       1, agent->n);
1529   //correct last action
1530   if (agent->a_old > (RIL_ACTION_TYPE_NUM + address_index))
1531   {
1532     agent->a_old -= 1;
1533   }
1534   else if (agent->a_old == (RIL_ACTION_TYPE_NUM + address_index))
1535   {
1536     agent->a_old = RIL_ACTION_INVALID;
1537   }
1538   //decrease old state vector and eligibility vector
1539   ril_cut_from_vector ((void **) &agent->s_old, sizeof(double),
1540       ((s->networks_count * RIL_FEATURES_NETWORK_COUNT) + (address_index * RIL_FEATURES_ADDRESS_COUNT)), RIL_FEATURES_ADDRESS_COUNT, agent->m);
1541   ril_cut_from_vector ((void **) &agent->e, sizeof(double),
1542       ((s->networks_count * RIL_FEATURES_NETWORK_COUNT) + (address_index * RIL_FEATURES_ADDRESS_COUNT)), RIL_FEATURES_ADDRESS_COUNT, agent->m);
1543   agent->m = m_new;
1544   agent->n = n_new;
1545
1546   LOG (GNUNET_ERROR_TYPE_DEBUG, "address was used: %s\n", address_was_used ? "yes" : "no");
1547
1548   if (address_was_used)
1549   {
1550     net = address->solver_information;
1551     net->bw_in_assigned -= agent->bw_in;
1552     net->bw_out_assigned -= agent->bw_out;
1553
1554     if (NULL != agent->addresses_head) //if peer has an address left, use it
1555     {
1556       LOG (GNUNET_ERROR_TYPE_DEBUG, "address left: %p\n", agent->addresses_head->address_naked->addr);
1557       //TODO? check if network/bandwidth update can be done more clever/elegant at different function
1558       envi_set_active_suggestion (s, agent, agent->addresses_head->address_naked, min_bw, min_bw, GNUNET_NO);
1559       net = agent->addresses_head->address_naked->solver_information;
1560       net->bw_in_assigned -= min_bw;
1561       net->bw_out_assigned -= min_bw;
1562     }
1563     else
1564     {
1565       LOG (GNUNET_ERROR_TYPE_DEBUG, "no address left => disconnect\n");
1566
1567       envi_set_active_suggestion (s, agent, NULL, 0, 0, GNUNET_NO);
1568     }
1569   }
1570
1571   LOG(GNUNET_ERROR_TYPE_DEBUG, "Address deleted\n");
1572 }
1573
1574 /**
1575  * Transport properties for this address have changed
1576  *
1577  * @param solver solver handle
1578  * @param address the address
1579  * @param type the ATSI type in HBO
1580  * @param abs_value the absolute value of the property
1581  * @param rel_value the normalized value
1582  */
1583 void
1584 GAS_ril_address_property_changed (void *solver,
1585     struct ATS_Address *address,
1586     uint32_t type,
1587     uint32_t abs_value,
1588     double rel_value)
1589 {
1590   LOG(GNUNET_ERROR_TYPE_DEBUG,
1591       "API_address_property_changed() Property '%s' for peer '%s' address %p changed "
1592           "to %.2f \n", GNUNET_ATS_print_property_type (type), GNUNET_i2s (&address->peer),
1593       address->addr, rel_value);
1594   /*
1595    * Nothing to do here, properties are considered in every reward calculation
1596    */
1597 }
1598
1599 /**
1600  * Transport session for this address has changed
1601  *
1602  * NOTE: values in addresses are already updated
1603  *
1604  * @param solver solver handle
1605  * @param address the address
1606  * @param cur_session the current session
1607  * @param new_session the new session
1608  */
1609 void
1610 GAS_ril_address_session_changed (void *solver,
1611     struct ATS_Address *address,
1612     uint32_t cur_session,
1613     uint32_t new_session)
1614 {
1615   //TODO? consider session change in solver behaviour
1616   /*
1617    * Potentially add session activity as a feature in state vector
1618    */
1619   LOG(GNUNET_ERROR_TYPE_DEBUG, "API_address_session_changed()\n");
1620 }
1621
1622 /**
1623  * Usage for this address has changed
1624  *
1625  * NOTE: values in addresses are already updated
1626  *
1627  * @param solver solver handle
1628  * @param address the address
1629  * @param in_use usage state
1630  */
1631 void
1632 GAS_ril_address_inuse_changed (void *solver, struct ATS_Address *address, int in_use)
1633 {
1634   /* Nothing to do here */
1635   LOG(GNUNET_ERROR_TYPE_DEBUG,
1636       "API_address_inuse_changed() Usage for %s address of peer '%s' changed to %s\n",
1637       address->plugin, GNUNET_i2s (&address->peer), (GNUNET_YES == in_use) ? "USED" : "UNUSED");
1638 }
1639
1640 /**
1641  * Network scope for this address has changed
1642  *
1643  * NOTE: values in addresses are already updated
1644  *
1645  * @param solver solver handle
1646  * @param address the address
1647  * @param current_network the current network
1648  * @param new_network the new network
1649  */
1650 void
1651 GAS_ril_address_change_network (void *solver,
1652     struct ATS_Address *address,
1653     uint32_t current_network,
1654     uint32_t new_network)
1655 {
1656   struct GAS_RIL_Handle *s = solver;
1657   struct RIL_Peer_Agent *agent;
1658   struct RIL_Network *net;
1659   uint32_t min_bw = ntohl (GNUNET_CONSTANTS_DEFAULT_BW_IN_OUT.value__);
1660
1661   LOG(GNUNET_ERROR_TYPE_DEBUG, "API_address_change_network() Network type changed, moving "
1662       "%s address of peer %s from '%s' to '%s'\n",
1663       (GNUNET_YES == address->active) ? "active" : "inactive", GNUNET_i2s (&address->peer),
1664       GNUNET_ATS_print_network_type (current_network), GNUNET_ATS_print_network_type (new_network));
1665
1666   if (address->active && !ril_network_is_active (solver, new_network))
1667   {
1668     GAS_ril_address_delete (solver, address, GNUNET_NO);
1669     return;
1670   }
1671
1672   agent = ril_get_agent (s, &address->peer, GNUNET_NO);
1673   if (NULL == agent)
1674   {
1675     GNUNET_assert(!ril_network_is_active (solver, current_network));
1676
1677     GAS_ril_address_add (s, address, new_network);
1678     return;
1679   }
1680
1681   net = ril_get_network (s, current_network);
1682   net->bw_in_assigned -= agent->bw_in;
1683   net->bw_out_assigned -= agent->bw_out;
1684
1685   net = ril_get_network (s, new_network);
1686   net->bw_in_assigned -= min_bw;
1687   net->bw_out_assigned -= min_bw;
1688   address->solver_information = net;
1689 }
1690
1691 /**
1692  * Get application feedback for a peer
1693  *
1694  * @param solver the solver handle
1695  * @param application the application
1696  * @param peer the peer to change the preference for
1697  * @param scope the time interval for this feedback: [now - scope .. now]
1698  * @param kind the kind to change the preference
1699  * @param score the score
1700  */
1701 void
1702 GAS_ril_address_preference_feedback (void *solver,
1703     void *application,
1704     const struct GNUNET_PeerIdentity *peer,
1705     const struct GNUNET_TIME_Relative scope,
1706     enum GNUNET_ATS_PreferenceKind kind,
1707     double score)
1708 {
1709   //TODO! talk to Matthias about feedback
1710   LOG(GNUNET_ERROR_TYPE_DEBUG,
1711       "API_address_preference_feedback() Peer '%s' got a feedback of %+.3f from application %s for "
1712           "preference %s for %d seconds\n", GNUNET_i2s (peer), "UNKNOWN",
1713       GNUNET_ATS_print_preference_type (kind), scope.rel_value_us / 1000000);
1714 }
1715
1716 /**
1717  * Start a bulk operation
1718  *
1719  * @param solver the solver
1720  */
1721 void
1722 GAS_ril_bulk_start (void *solver)
1723 {
1724   /*
1725    * Since new calculations of the assignment are not triggered by a change of preferences, as it
1726    * happens in the proportional and the mlp solver, there is no need to block this solver.
1727    */
1728 }
1729
1730 /**
1731  * Bulk operation done
1732  */
1733 void
1734 GAS_ril_bulk_stop (void *solver)
1735 {
1736   /*
1737    * Since new calculations of the assignment are not triggered by a change of preferences, as it
1738    * happens in the proportional and the mlp solver, there is no need to block this solver.
1739    */
1740 }
1741
1742 /**
1743  * Get the preferred address for a specific peer
1744  *
1745  * @param solver the solver handle
1746  * @param peer the identity of the peer
1747  */
1748 const struct ATS_Address *
1749 GAS_ril_get_preferred_address (void *solver, const struct GNUNET_PeerIdentity *peer)
1750 {
1751   /*
1752    * activate agent, return currently chosen address
1753    */
1754   struct GAS_RIL_Handle *s = solver;
1755   struct RIL_Peer_Agent *agent;
1756
1757   agent = ril_get_agent (s, peer, GNUNET_YES);
1758
1759   agent->active = GNUNET_YES;
1760
1761   envi_set_active_suggestion(s, agent, agent->address_inuse, agent->bw_in, agent->bw_out, GNUNET_YES);
1762
1763   if (agent->address_inuse)
1764   {
1765     LOG(GNUNET_ERROR_TYPE_DEBUG,
1766         "API_get_preferred_address() Activated agent for peer '%s' with %s address %p\n",
1767         GNUNET_i2s (peer), agent->address_inuse->plugin, agent->address_inuse->addr);
1768   }
1769   else
1770   {
1771     LOG(GNUNET_ERROR_TYPE_DEBUG,
1772             "API_get_preferred_address() Activated agent for peer '%s', but no address available\n", GNUNET_i2s (peer));
1773   }
1774
1775   return agent->address_inuse;
1776 }
1777
1778 /**
1779  * Stop notifying about address and bandwidth changes for this peer
1780  *
1781  * @param solver the solver handle
1782  * @param peer the peer
1783  */
1784 void
1785 GAS_ril_stop_get_preferred_address (void *solver, const struct GNUNET_PeerIdentity *peer)
1786 {
1787   struct GAS_RIL_Handle *s = solver;
1788   struct RIL_Peer_Agent *agent;
1789
1790   agent = ril_get_agent (s, peer, GNUNET_NO);
1791
1792   if (NULL == agent)
1793   {
1794     GNUNET_break(0);
1795     return;
1796   }
1797   if (GNUNET_NO == agent->active)
1798   {
1799     GNUNET_break(0);
1800     return;
1801   }
1802
1803   agent->active = GNUNET_NO;
1804   envi_set_active_suggestion(s, agent, agent->address_inuse, agent->bw_in, agent->bw_out, GNUNET_YES);
1805
1806   LOG(GNUNET_ERROR_TYPE_DEBUG,
1807       "API_stop_get_preferred_address() Paused agent for peer '%s' with %s address\n",
1808       GNUNET_i2s (peer), agent->address_inuse->plugin);
1809 }
1810
1811 /* end of gnunet-service-ats-solver_ril.c */