2 This file is part of GNUnet.
3 (C) 2011 Christian Grothoff (and other contributing authors)
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.
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.
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.
22 * @file ats/gnunet-service-ats-solver_ril.c
23 * @brief ATS reinforcement learning solver
24 * @author Fabian Oehlmann
25 * @author Matthias Wachs
28 #include "gnunet_util_lib.h"
29 #include "gnunet-service-ats_addresses.h"
30 #include "gnunet_statistics_service.h"
32 #define RIL_DEFAULT_STEP_TIME GNUNET_TIME_relative_multiply (GNUNET_TIME_UNIT_MILLISECONDS, 3000)
33 #define RIL_DEFAULT_DISCOUNT_FACTOR 0.5
34 #define RIL_DEFAULT_GRADIENT_STEP_SIZE 0.4
35 #define RIL_DEFAULT_TRACE_DECAY 0.6
38 * ATS reinforcement learning solver
44 * Global learning parameters
46 struct RIL_Learning_Parameters
49 * Learning discount factor in the TD-update
54 * Gradient-descent step-size
59 * Trace-decay factor for eligibility traces
67 * Next agent in solver's linked list
69 struct RIL_Peer_Agent *next;
72 * Previous agent in solver's linked list
74 struct RIL_Peer_Agent *prev;
79 struct GNUNET_PeerIdentity peer;
87 * Last perceived state feature vector
97 * Last eligibility trace vector
110 * Network description
115 * Total available inbound bandwidth
117 unsigned long long bw_in_available;
120 * Total assigned outbound bandwidth
122 unsigned long long bw_in_assigned;
125 * Total available outbound bandwidth
127 unsigned long long bw_out_available;
130 * Total assigned outbound bandwidth
132 unsigned long long bw_out_assigned;
138 * Bandwidth changed callback
140 GAS_bandwidth_changed_cb bw_changed;
143 * Bandwidth changed callback cls
145 void *bw_changed_cls;
148 * ATS function to get preferences
150 GAS_get_preferences get_preferences;
153 * Closure for ATS function to get preferences
155 void *get_preferences_cls;
158 * ATS function to get properties
160 GAS_get_properties get_properties;
163 * Closure for ATS function to get properties
165 void *get_properties_cls;
169 * A handle for the reinforcement learning solver
171 struct GAS_RIL_Handle
176 struct GNUNET_STATISTICS_Handle *stats;
179 * Hashmap containing all valid addresses
181 const struct GNUNET_CONTAINER_MultiHashMap *addresses;
184 * Callbacks for the solver
186 struct RIL_Callbacks callbacks;
194 * Number of changes while solver was locked
199 * Number of performed time-steps
201 unsigned long long step_count;
204 * Interval time between steps in milliseconds //TODO put in agent
206 struct GNUNET_TIME_Relative step_time;
209 * Task identifier of the next time-step to be executed //TODO put in agent
211 GNUNET_SCHEDULER_TaskIdentifier next_step;
214 * Learning parameters
216 struct RIL_Learning_Parameters parameters;
219 * Array of networks with global assignment state
221 struct RIL_Network * network_entries;
226 unsigned int networks_count;
229 * List of active peer-agents
231 struct RIL_Peer_Agent * agents_active_head;
232 struct RIL_Peer_Agent * agents_active_tail;
235 * List of paused peer-agents
237 struct RIL_Peer_Agent * agents_paused_head;
238 struct RIL_Peer_Agent * agents_paused_tail;
247 //TODO add the rest of the actions
251 * ---------------------------
255 agent_periodic_step (void *solver,
256 const struct GNUNET_SCHEDULER_TaskContext *tc)
259 * iterate over active agents and do a time step
261 struct GAS_RIL_Handle *s = solver;
263 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "RIL step number %d\n", s->step_count);
266 s->next_step = GNUNET_SCHEDULER_add_delayed (
268 &agent_periodic_step,
273 * Whether a peer already has an agent in a list
274 * @param head of list
275 * @param peer in question
278 list_contains_agent (struct RIL_Peer_Agent * head,
279 struct GNUNET_PeerIdentity * peer)
281 struct RIL_Peer_Agent * cur;
283 for (cur = head; NULL != cur; cur = cur->next)
285 if (!memcmp (&(cur->peer.hashPubKey), &peer->hashPubKey, sizeof(struct GNUNET_HashCode)))
294 * Iterator, which allocates one agent per peer
297 * @param key peer identity
298 * @param value address
299 * @return whether iterator should continue
302 init_agents_it (void *cls,
303 const struct GNUNET_HashCode *key,
306 struct GAS_RIL_Handle *solver = cls;
307 struct ATS_Address *address = value;
308 struct RIL_Peer_Agent *agent;
310 if (!list_contains_agent (solver->agents_paused_head, &address->peer))
312 agent = GNUNET_malloc (sizeof (struct RIL_Peer_Agent));
313 agent->peer = address->peer;
314 GNUNET_CONTAINER_DLL_insert (solver->agents_paused_head, solver->agents_paused_tail, agent);
317 //TODO add address to agent
324 * Solver API functions
325 * ---------------------------
329 * Changes the preferences for a peer in the problem
331 * @param solver the solver handle
332 * @param peer the peer to change the preference for
333 * @param kind the kind to change the preference
334 * @param pref_rel the normalized preference value for this kind over all clients
337 GAS_ril_address_change_preference (void *solver,
338 const struct GNUNET_PeerIdentity *peer,
339 enum GNUNET_ATS_PreferenceKind kind,
345 * Probably nothing to do here. The preference is looked up during reward calculation and does
346 * not trigger anything
348 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "ril_address_change_preference() has been called\n");
353 * Init the reinforcement learning problem solver
356 * network[i] contains the network type as type GNUNET_ATS_NetworkType[i]
357 * out_quota[i] contains outbound quota for network type i
358 * in_quota[i] contains inbound quota for network type i
361 * network = {GNUNET_ATS_NET_UNSPECIFIED, GNUNET_ATS_NET_LOOPBACK, GNUNET_ATS_NET_LAN, GNUNET_ATS_NET_WAN, GNUNET_ATS_NET_WLAN}
362 * network[2] == GNUNET_ATS_NET_LAN
363 * out_quota[2] == 65353
364 * in_quota[2] == 65353
366 * @param cfg configuration handle
367 * @param stats the GNUNET_STATISTICS handle
368 * @param network array of GNUNET_ATS_NetworkType with length dest_length
369 * @param addresses hashmap containing all addresses
370 * @param out_quota array of outbound quotas
371 * @param in_quota array of outbound quota
372 * @param dest_length array length for quota arrays
373 * @param bw_changed_cb callback for changed bandwidth amounts
374 * @param bw_changed_cb_cls cls for callback
375 * @param get_preference callback to get relative preferences for a peer
376 * @param get_preference_cls cls for callback to get relative preferences
377 * @param get_properties_cls for callback to get relative properties
378 * @param get_properties_cls cls for callback to get relative properties
379 * @return handle for the solver on success, NULL on fail
382 GAS_ril_init (const struct GNUNET_CONFIGURATION_Handle *cfg,
383 const struct GNUNET_STATISTICS_Handle *stats,
384 const struct GNUNET_CONTAINER_MultiHashMap *addresses,
386 unsigned long long *out_quota,
387 unsigned long long *in_quota,
389 GAS_bandwidth_changed_cb bw_changed_cb,
390 void *bw_changed_cb_cls,
391 GAS_get_preferences get_preference,
392 void *get_preference_cls,
393 GAS_get_properties get_properties,
394 void *get_properties_cls)
398 unsigned long long tmp;
399 struct RIL_Network * cur;
400 struct GAS_RIL_Handle *solver = GNUNET_malloc (sizeof (struct GAS_RIL_Handle));
401 char * net_str[GNUNET_ATS_NetworkTypeCount] = GNUNET_ATS_NetworkTypeString;
403 GNUNET_assert (NULL != cfg);
404 GNUNET_assert (NULL != stats);
405 GNUNET_assert (NULL != network);
406 GNUNET_assert (NULL != bw_changed_cb);
407 GNUNET_assert (NULL != get_preference);
408 GNUNET_assert (NULL != get_properties);
410 if (GNUNET_OK != GNUNET_CONFIGURATION_get_value_time(cfg, "ats", "RIL_STEP_TIME", &solver->step_time))
412 solver->step_time = RIL_DEFAULT_STEP_TIME;
414 if (GNUNET_OK == GNUNET_CONFIGURATION_get_value_size(cfg, "ats", "RIL_DISCOUNT_FACTOR", &tmp))
416 solver->parameters.gamma = (double) tmp / 100;;
420 solver->parameters.gamma = RIL_DEFAULT_DISCOUNT_FACTOR;
422 if (GNUNET_OK == GNUNET_CONFIGURATION_get_value_size(cfg, "ats", "RIL_GRADIENT_STEP_SIZE", &tmp))
424 solver->parameters.alpha = (double) tmp / 100;;
428 solver->parameters.alpha = RIL_DEFAULT_GRADIENT_STEP_SIZE;
430 if (GNUNET_OK == GNUNET_CONFIGURATION_get_value_size(cfg, "ats", "RIL_TRACE_DECAY", &tmp))
432 solver->parameters.lambda = (double) tmp / 100;;
436 solver->parameters.lambda = RIL_DEFAULT_TRACE_DECAY;
439 solver->stats = (struct GNUNET_STATISTICS_Handle *) stats;
440 solver->callbacks.bw_changed = bw_changed_cb;
441 solver->callbacks.bw_changed_cls = bw_changed_cb_cls;
442 solver->callbacks.get_preferences = get_preference;
443 solver->callbacks.get_preferences_cls = get_preference_cls;
444 solver->callbacks.get_properties = get_properties;
445 solver->callbacks.get_properties_cls = get_properties_cls;
446 solver->networks_count = dest_length;
447 solver->network_entries = GNUNET_malloc (dest_length * sizeof (struct RIL_Network));
448 solver->bulk_lock = GNUNET_NO;
449 solver->addresses = addresses;
450 solver->step_count = 0;
452 for (c = 0; c < dest_length; c++)
454 cur = &solver->network_entries[c];
455 cur->type = network[c];
456 cur->bw_in_available = in_quota[c];
457 cur->bw_in_assigned = 0;
458 cur->bw_out_available = out_quota[c];
459 cur->bw_out_assigned = 0;
460 cur->desc = net_str[c];
463 c = GNUNET_CONTAINER_multihashmap_iterate (addresses, &init_agents_it, solver);
465 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "ril_init() has been called\n");
466 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "RIL number of addresses: %d\n", c);
468 solver->next_step = GNUNET_SCHEDULER_add_delayed (
469 GNUNET_TIME_relative_multiply (GNUNET_TIME_relative_get_millisecond_ (), 1000),
470 &agent_periodic_step,
477 * Shutdown the reinforcement learning problem solver
479 * @param solver the respective handle to shutdown
482 GAS_ril_done (void * solver)
485 struct GAS_RIL_Handle *s = solver;
487 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "ril_done() has been called\n");
489 GNUNET_SCHEDULER_cancel (s->next_step);
490 GNUNET_free (s->network_entries);
496 * Add a single address within a network to the solver
498 * @param solver the solver Handle
499 * @param address the address to add
500 * @param network network type of this address
503 GAS_ril_address_add (void *solver,
504 struct ATS_Address *address,
510 * initialize new agent
512 * increase state vector
516 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "ril_address_add() has been called\n");
520 * Remove an address from the solver
522 * @param solver the solver handle
523 * @param address the address to remove
524 * @param session_only delete only session not whole address
527 GAS_ril_address_delete (void *solver,
528 struct ATS_Address *address, int session_only)
533 * if (last address of peer)
536 * decrease state vector
537 * decrease knowledge matrix
538 * decrease action vector
540 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "ril_address_delete() has been called\n");
544 * Transport properties for this address have changed
546 * @param solver solver handle
547 * @param address the address
548 * @param type the ATSI type in HBO
549 * @param abs_value the absolute value of the property
550 * @param rel_value the normalized value
553 GAS_ril_address_property_changed (void *solver,
554 struct ATS_Address *address,
561 * Like change_preference() not really interesting, since lookup happens anyway during reward
564 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "ril_address_property_changed() has been called\n");
569 * Transport session for this address has changed
571 * NOTE: values in addresses are already updated
573 * @param solver solver handle
574 * @param address the address
575 * @param cur_session the current session
576 * @param new_session the new session
579 GAS_ril_address_session_changed (void *solver,
580 struct ATS_Address *address,
581 uint32_t cur_session,
582 uint32_t new_session)
586 * Potentially add session activity as a feature in state vector
588 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "ril_address_session_changed() has been called\n");
593 * Usage for this address has changed
595 * NOTE: values in addresses are already updated
597 * @param solver solver handle
598 * @param address the address
599 * @param in_use usage state
602 GAS_ril_address_inuse_changed (void *solver,
603 struct ATS_Address *address,
608 * See matthias' email
610 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "ril_address_inuse_changed() has been called\n");
614 * Network scope for this address has changed
616 * NOTE: values in addresses are already updated
618 * @param solver solver handle
619 * @param address the address
620 * @param current_network the current network
621 * @param new_network the new network
624 GAS_ril_address_change_network (void *solver,
625 struct ATS_Address *address,
626 uint32_t current_network,
627 uint32_t new_network)
633 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "ril_address_change_network() has been called\n");
637 * Get application feedback for a peer
639 * @param solver the solver handle
640 * @param application the application
641 * @param peer the peer to change the preference for
642 * @param scope the time interval for this feedback: [now - scope .. now]
643 * @param kind the kind to change the preference
644 * @param score the score
647 GAS_ril_address_preference_feedback (void *solver,
649 const struct GNUNET_PeerIdentity *peer,
650 const struct GNUNET_TIME_Relative scope,
651 enum GNUNET_ATS_PreferenceKind kind,
655 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "ril_address_preference_feedback() has been called\n");
659 * Start a bulk operation
661 * @param solver the solver
664 GAS_ril_bulk_start (void *solver)
668 * bulk counter up, but not really relevant, because there is no complete calculation of the
669 * bandwidth assignment triggered anyway. Therefore, changes to addresses can come and go as
670 * they want. Consideration: Step-pause during bulk-start-stop period...
672 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "ril_bulk_start() has been called\n");
677 * Bulk operation done
680 GAS_ril_bulk_stop (void *solver)
684 * bulk counter down, see bulk_start()
686 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "ril_bulk_stop() has been called\n");
690 * Get the preferred address for a specific peer
692 * @param solver the solver handle
693 * @param peer the identity of the peer
695 const struct ATS_Address *
696 GAS_ril_get_preferred_address (void *solver,
697 const struct GNUNET_PeerIdentity *peer)
701 * connect-only for requested peers, move agent to active list
703 struct GAS_RIL_Handle *s = solver;
705 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "ril_get_preferred_address() has been called\n");
707 if (0 == GNUNET_CONTAINER_multihashmap_contains(s->addresses, &peer->hashPubKey))
709 return GNUNET_CONTAINER_multihashmap_get(s->addresses, &peer->hashPubKey);
712 GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "No address for peer in addresses\n");
717 * Stop notifying about address and bandwidth changes for this peer
719 * @param solver the solver handle
720 * @param peer the peer
723 GAS_ril_stop_get_preferred_address (void *solver,
724 const struct GNUNET_PeerIdentity *peer)
728 * connect-only for requested peers, move agent to paused list
730 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "ril_stop_get_preferred_address() has been called\n");
733 /* end of gnunet-service-ats-solver_reinf.c */