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
29 #include "gnunet_util_lib.h"
30 #include "gnunet-service-ats_addresses.h"
31 #include "gnunet_statistics_service.h"
33 #define RIL_DEFAULT_STEP_TIME GNUNET_TIME_relative_multiply (GNUNET_TIME_UNIT_MILLISECONDS, 3000)
34 #define RIL_DEFAULT_DISCOUNT_FACTOR 0.5
35 #define RIL_DEFAULT_GRADIENT_STEP_SIZE 0.4
36 #define RIL_DEFAULT_TRACE_DECAY 0.6
37 #define RIL_EXPLORE_RATIO 0.1
40 * ATS reinforcement learning solver
51 //TODO add the rest of the actions
54 * Global learning parameters
56 struct RIL_Learning_Parameters
59 * Learning discount factor in the TD-update
64 * Gradient-descent step-size
69 * Trace-decay factor for eligibility traces
77 * Next agent in solver's linked list
79 struct RIL_Peer_Agent *next;
82 * Previous agent in solver's linked list
84 struct RIL_Peer_Agent *prev;
89 struct GAS_RIL_Handle *envi;
94 struct GNUNET_PeerIdentity peer;
97 * Whether the agent is active or not
102 * Number of performed time-steps
104 unsigned long long step_count;
107 * Experience matrix W
112 * Number of rows of W / Number of state-vector features
117 * Number of columns of W / Number of actions
122 * Last perceived state feature vector
132 * Last eligibility trace vector
139 struct ATS_Address * address;
150 * Network description
155 * Total available inbound bandwidth
157 unsigned long long bw_in_available;
160 * Total assigned outbound bandwidth
162 unsigned long long bw_in_assigned;
165 * Total available outbound bandwidth
167 unsigned long long bw_out_available;
170 * Total assigned outbound bandwidth
172 unsigned long long bw_out_assigned;
178 * Bandwidth changed callback
180 GAS_bandwidth_changed_cb bw_changed;
183 * Bandwidth changed callback cls
185 void *bw_changed_cls;
188 * ATS function to get preferences
190 GAS_get_preferences get_preferences;
193 * Closure for ATS function to get preferences
195 void *get_preferences_cls;
198 * ATS function to get properties
200 GAS_get_properties get_properties;
203 * Closure for ATS function to get properties
205 void *get_properties_cls;
209 * A handle for the reinforcement learning solver
211 struct GAS_RIL_Handle
216 struct GNUNET_STATISTICS_Handle *stats;
219 * Hashmap containing all valid addresses
221 const struct GNUNET_CONTAINER_MultiHashMap *addresses;
224 * Callbacks for the solver
226 struct RIL_Callbacks callbacks;
234 * Number of changes while solver was locked
239 * Number of performed time-steps
241 unsigned long long step_count;
244 * Interval time between steps in milliseconds //TODO put in agent
246 struct GNUNET_TIME_Relative step_time;
249 * Task identifier of the next time-step to be executed //TODO put in agent
251 GNUNET_SCHEDULER_TaskIdentifier next_step;
254 * Learning parameters
256 struct RIL_Learning_Parameters parameters;
259 * Array of networks with global assignment state
261 struct RIL_Network * network_entries;
266 unsigned int networks_count;
269 * List of active peer-agents
271 struct RIL_Peer_Agent * agents_head;
272 struct RIL_Peer_Agent * agents_tail;
280 * ---------------------------
284 * Estimate the current action-value for state s and action a
285 * @param agent agent performing the estimation
288 * @return estimation value
291 agent_estimate_q (struct RIL_Peer_Agent *agent,
298 for (i = 0; i < agent->m; i++)
300 result += state[i] * (agent->W)[agent->m][action];
307 agent_choose_action (struct RIL_Peer_Agent *agent,
314 double max_q = DBL_MIN;
316 r = ((double) GNUNET_CRYPTO_random_u32(GNUNET_CRYPTO_QUALITY_WEAK, UINT32_MAX) / (double) UINT32_MAX);
318 if (r < RIL_EXPLORE_RATIO)
320 return GNUNET_CRYPTO_random_u32(GNUNET_CRYPTO_QUALITY_WEAK, agent->n);
323 for (i = 0; i < agent->m; i++)
325 cur_q = agent_estimate_q (agent, state, i);
333 GNUNET_assert(-1 != max_i);
339 envi_get_state (void *s)
342 struct GAS_RIL_Handle *solver = s;
343 struct RIL_Network *net;
344 double *state = GNUNET_malloc (sizeof (double) * solver->networks_count * 4);
346 for (i = 0; i < solver->networks_count; i += 4)
348 net = (&solver->network_entries)[i];
349 state[i] = (double) net->bw_in_assigned;
350 state[i+1] = (double) net->bw_in_available;
351 state[i+2] = (double) net->bw_out_assigned;
352 state[i+3] = (double) net->bw_out_available;
362 return (double) GNUNET_CRYPTO_random_u32(GNUNET_CRYPTO_QUALITY_WEAK, UINT32_MAX) / (double) UINT32_MAX;
366 agent_step (struct RIL_Peer_Agent *agent)
375 s_next = envi_get_state(agent->envi);
376 reward = envi_get_reward();
378 a_next = agent_choose_action (agent, s_next);
379 q_next = agent_estimate_q(agent, s_next, a_next);
381 if (NULL != agent->s_old)
384 (agent->envi->parameters.gamma * q_next) -
385 agent_estimate_q(agent, agent->s_old, agent->a_old);
388 GNUNET_free(agent->s_old);
389 agent->s_old = s_next;
390 agent->a_old = a_next;
392 agent->step_count += 1;
396 ril_periodic_step (void *s,
397 const struct GNUNET_SCHEDULER_TaskContext *tc)
400 * iterate over active agents and do a time step
402 struct GAS_RIL_Handle *solver = s;
403 struct RIL_Peer_Agent *cur;
405 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "RIL step number %d\n", solver->step_count);
407 for (cur = solver->agents_head; NULL != cur; cur = cur->next)
415 solver->step_count += 1;
416 solver->next_step = GNUNET_SCHEDULER_add_delayed (
423 * Initialize an agent without addresses and its knowledge base
424 * @param s ril solver
425 * @param peer the one in question
426 * @return handle to the new agent
428 struct RIL_Peer_Agent *
430 struct GNUNET_PeerIdentity peer)
433 struct GAS_RIL_Handle * solver = s;
434 struct RIL_Peer_Agent * agent = GNUNET_malloc (sizeof (struct RIL_Peer_Agent));
436 agent->envi = solver;
438 agent->step_count = 0;
439 agent->active = GNUNET_NO;
441 agent->n = solver->networks_count * 4;
442 agent->m = RIL_NUM_ACTIONS;
443 agent->W = (double **) GNUNET_malloc (sizeof (double) * agent->n);
444 for (i = 0; i < agent->n; i++)
446 (agent->W)[i] = (double *) GNUNET_malloc (sizeof (double) * agent->m);
451 GNUNET_CONTAINER_DLL_insert (solver->agents_head, solver->agents_tail, agent);
458 * @param s solver handle
459 * @param agent the agent to retire
463 struct RIL_Peer_Agent * agent)
469 * Returns the agent for a peer
470 * @param s solver handle
471 * @param peer identity of the peer
474 struct RIL_Peer_Agent *
475 ril_get_agent (struct GAS_RIL_Handle * s,
476 struct GNUNET_PeerIdentity peer)
478 struct GAS_RIL_Handle * solver = s;
479 struct RIL_Peer_Agent * cur;
481 for (cur = s->agents_head; NULL != cur; cur = cur->next)
483 if (0 == GNUNET_CRYPTO_hash_cmp (&peer.hashPubKey, &cur->peer.hashPubKey))
489 return agent_init (solver, peer);
493 * Iterator, which allocates one agent per peer
496 * @param key peer identity
497 * @param value address
498 * @return whether iterator should continue
501 init_agents_it (void *cls,
502 const struct GNUNET_HashCode *key,
505 struct GAS_RIL_Handle *solver = cls;
506 struct ATS_Address *address = value;
507 struct RIL_Peer_Agent *agent;
509 agent = ril_get_agent (solver, address->peer);
511 GNUNET_assert (agent != NULL);
513 if (NULL == agent->address)
515 agent->address = address;
524 * Solver API functions
525 * ---------------------------
529 * Changes the preferences for a peer in the problem
531 * @param solver the solver handle
532 * @param peer the peer to change the preference for
533 * @param kind the kind to change the preference
534 * @param pref_rel the normalized preference value for this kind over all clients
537 GAS_ril_address_change_preference (void *solver,
538 const struct GNUNET_PeerIdentity *peer,
539 enum GNUNET_ATS_PreferenceKind kind,
542 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
543 "Preference `%s' for peer `%s' changed to %.2f \n",
544 GNUNET_ATS_print_preference_type (kind),
548 * Nothing to do here. Preferences are considered during reward calculation.
554 * Init the reinforcement learning problem solver
557 * network[i] contains the network type as type GNUNET_ATS_NetworkType[i]
558 * out_quota[i] contains outbound quota for network type i
559 * in_quota[i] contains inbound quota for network type i
562 * network = {GNUNET_ATS_NET_UNSPECIFIED, GNUNET_ATS_NET_LOOPBACK, GNUNET_ATS_NET_LAN, GNUNET_ATS_NET_WAN, GNUNET_ATS_NET_WLAN}
563 * network[2] == GNUNET_ATS_NET_LAN
564 * out_quota[2] == 65353
565 * in_quota[2] == 65353
567 * @param cfg configuration handle
568 * @param stats the GNUNET_STATISTICS handle
569 * @param network array of GNUNET_ATS_NetworkType with length dest_length
570 * @param addresses hashmap containing all addresses
571 * @param out_quota array of outbound quotas
572 * @param in_quota array of outbound quota
573 * @param dest_length array length for quota arrays
574 * @param bw_changed_cb callback for changed bandwidth amounts
575 * @param bw_changed_cb_cls cls for callback
576 * @param get_preference callback to get relative preferences for a peer
577 * @param get_preference_cls cls for callback to get relative preferences
578 * @param get_properties_cls for callback to get relative properties
579 * @param get_properties_cls cls for callback to get relative properties
580 * @return handle for the solver on success, NULL on fail
583 GAS_ril_init (const struct GNUNET_CONFIGURATION_Handle *cfg,
584 const struct GNUNET_STATISTICS_Handle *stats,
585 const struct GNUNET_CONTAINER_MultiHashMap *addresses,
587 unsigned long long *out_quota,
588 unsigned long long *in_quota,
590 GAS_bandwidth_changed_cb bw_changed_cb,
591 void *bw_changed_cb_cls,
592 GAS_get_preferences get_preference,
593 void *get_preference_cls,
594 GAS_get_properties get_properties,
595 void *get_properties_cls)
599 unsigned long long tmp;
600 struct RIL_Network * cur;
601 struct GAS_RIL_Handle *solver = GNUNET_malloc (sizeof (struct GAS_RIL_Handle));
602 char * net_str[GNUNET_ATS_NetworkTypeCount] = GNUNET_ATS_NetworkTypeString;
604 GNUNET_assert (NULL != cfg);
605 GNUNET_assert (NULL != stats);
606 GNUNET_assert (NULL != network);
607 GNUNET_assert (NULL != bw_changed_cb);
608 GNUNET_assert (NULL != get_preference);
609 GNUNET_assert (NULL != get_properties);
611 if (GNUNET_OK != GNUNET_CONFIGURATION_get_value_time(cfg, "ats", "RIL_STEP_TIME", &solver->step_time))
613 solver->step_time = RIL_DEFAULT_STEP_TIME;
615 if (GNUNET_OK == GNUNET_CONFIGURATION_get_value_size(cfg, "ats", "RIL_DISCOUNT_FACTOR", &tmp))
617 solver->parameters.gamma = (double) tmp / 100;;
621 solver->parameters.gamma = RIL_DEFAULT_DISCOUNT_FACTOR;
623 if (GNUNET_OK == GNUNET_CONFIGURATION_get_value_size(cfg, "ats", "RIL_GRADIENT_STEP_SIZE", &tmp))
625 solver->parameters.alpha = (double) tmp / 100;;
629 solver->parameters.alpha = RIL_DEFAULT_GRADIENT_STEP_SIZE;
631 if (GNUNET_OK == GNUNET_CONFIGURATION_get_value_size(cfg, "ats", "RIL_TRACE_DECAY", &tmp))
633 solver->parameters.lambda = (double) tmp / 100;;
637 solver->parameters.lambda = RIL_DEFAULT_TRACE_DECAY;
640 solver->stats = (struct GNUNET_STATISTICS_Handle *) stats;
641 solver->callbacks.bw_changed = bw_changed_cb;
642 solver->callbacks.bw_changed_cls = bw_changed_cb_cls;
643 solver->callbacks.get_preferences = get_preference;
644 solver->callbacks.get_preferences_cls = get_preference_cls;
645 solver->callbacks.get_properties = get_properties;
646 solver->callbacks.get_properties_cls = get_properties_cls;
647 solver->networks_count = dest_length;
648 solver->network_entries = GNUNET_malloc (dest_length * sizeof (struct RIL_Network));
649 solver->bulk_lock = GNUNET_NO;
650 solver->addresses = addresses;
651 solver->step_count = 0;
653 for (c = 0; c < dest_length; c++)
655 cur = &solver->network_entries[c];
656 cur->type = network[c];
657 cur->bw_in_available = in_quota[c];
658 cur->bw_in_assigned = 0;
659 cur->bw_out_available = out_quota[c];
660 cur->bw_out_assigned = 0;
661 cur->desc = net_str[c];
664 c = GNUNET_CONTAINER_multihashmap_iterate (addresses, &init_agents_it, solver);
666 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "ril_init() has been called\n");
667 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "RIL number of addresses: %d\n", c);
669 solver->next_step = GNUNET_SCHEDULER_add_delayed (
670 GNUNET_TIME_relative_multiply (GNUNET_TIME_relative_get_millisecond_ (), 1000),
678 * Shutdown the reinforcement learning problem solver
680 * @param solver the respective handle to shutdown
683 GAS_ril_done (void * solver)
686 struct GAS_RIL_Handle *s = solver;
688 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "ril_done() has been called\n");
690 GNUNET_SCHEDULER_cancel (s->next_step);
691 GNUNET_free (s->network_entries);
697 * Add a single address within a network to the solver
699 * @param solver the solver Handle
700 * @param address the address to add
701 * @param network network type of this address
704 GAS_ril_address_add (void *solver,
705 struct ATS_Address *address,
711 * initialize new agent
713 * increase state vector
717 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "ril_address_add() has been called\n");
721 * Remove an address from the solver
723 * @param solver the solver handle
724 * @param address the address to remove
725 * @param session_only delete only session not whole address
728 GAS_ril_address_delete (void *solver,
729 struct ATS_Address *address,
735 * if (last address of peer)
738 * decrease state vector
739 * decrease knowledge matrix
740 * decrease action vector
742 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "ril_address_delete() has been called\n");
746 * Transport properties for this address have changed
748 * @param solver solver handle
749 * @param address the address
750 * @param type the ATSI type in HBO
751 * @param abs_value the absolute value of the property
752 * @param rel_value the normalized value
755 GAS_ril_address_property_changed (void *solver,
756 struct ATS_Address *address,
761 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
762 "Property `%s' for peer `%s' address %p changed to %.2f \n",
763 GNUNET_ATS_print_property_type (type),
764 GNUNET_i2s (&address->peer),
767 * Nothing to do here, properties are considered in every reward calculation
773 * Transport session for this address has changed
775 * NOTE: values in addresses are already updated
777 * @param solver solver handle
778 * @param address the address
779 * @param cur_session the current session
780 * @param new_session the new session
783 GAS_ril_address_session_changed (void *solver,
784 struct ATS_Address *address,
785 uint32_t cur_session,
786 uint32_t new_session)
790 * Potentially add session activity as a feature in state vector
792 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "ril_address_session_changed() has been called\n");
797 * Usage for this address has changed
799 * NOTE: values in addresses are already updated
801 * @param solver solver handle
802 * @param address the address
803 * @param in_use usage state
806 GAS_ril_address_inuse_changed (void *solver,
807 struct ATS_Address *address,
812 * See matthias' email
814 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "ril_address_inuse_changed() has been called\n");
818 * Network scope for this address has changed
820 * NOTE: values in addresses are already updated
822 * @param solver solver handle
823 * @param address the address
824 * @param current_network the current network
825 * @param new_network the new network
828 GAS_ril_address_change_network (void *solver,
829 struct ATS_Address *address,
830 uint32_t current_network,
831 uint32_t new_network)
837 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "ril_address_change_network() has been called\n");
841 * Get application feedback for a peer
843 * @param solver the solver handle
844 * @param application the application
845 * @param peer the peer to change the preference for
846 * @param scope the time interval for this feedback: [now - scope .. now]
847 * @param kind the kind to change the preference
848 * @param score the score
851 GAS_ril_address_preference_feedback (void *solver,
853 const struct GNUNET_PeerIdentity *peer,
854 const struct GNUNET_TIME_Relative scope,
855 enum GNUNET_ATS_PreferenceKind kind,
859 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "ril_address_preference_feedback() has been called\n");
863 * Start a bulk operation
865 * @param solver the solver
868 GAS_ril_bulk_start (void *solver)
872 * bulk counter up, but not really relevant, because there is no complete calculation of the
873 * bandwidth assignment triggered anyway. Therefore, changes to addresses can come and go as
874 * they want. Consideration: Step-pause during bulk-start-stop period...
876 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "ril_bulk_start() has been called\n");
881 * Bulk operation done
884 GAS_ril_bulk_stop (void *solver)
888 * bulk counter down, see bulk_start()
890 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "ril_bulk_stop() has been called\n");
894 * Get the preferred address for a specific peer
896 * @param solver the solver handle
897 * @param peer the identity of the peer
899 const struct ATS_Address *
900 GAS_ril_get_preferred_address (void *solver,
901 const struct GNUNET_PeerIdentity *peer)
905 * connect-only for requested peers, move agent to active list
907 struct GAS_RIL_Handle *s = solver;
909 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "ril_get_preferred_address() has been called\n");
911 if (0 == GNUNET_CONTAINER_multihashmap_contains(s->addresses, &peer->hashPubKey))
913 return GNUNET_CONTAINER_multihashmap_get(s->addresses, &peer->hashPubKey);
916 GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "No address for peer in addresses\n");
921 * Stop notifying about address and bandwidth changes for this peer
923 * @param solver the solver handle
924 * @param peer the peer
927 GAS_ril_stop_get_preferred_address (void *solver,
928 const struct GNUNET_PeerIdentity *peer)
932 * connect-only for requested peers, move agent to paused list
934 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "ril_stop_get_preferred_address() has been called\n");
937 /* end of gnunet-service-ats-solver_reinf.c */