diff options
author | Fabian Oehlmann <oehlmann@in.tum.de> | 2014-01-21 19:04:34 +0000 |
---|---|---|
committer | Fabian Oehlmann <oehlmann@in.tum.de> | 2014-01-21 19:04:34 +0000 |
commit | a5c28352b9ceda0c4a0b723e4c03ca58d3f6f570 (patch) | |
tree | 77fef9b282f2800b20f1dceee0ee55c1cfe009f4 /src/ats/plugin_ats_ril.c | |
parent | 7851d98327dbcf0146accfba3684f58feec253dd (diff) | |
download | gnunet-a5c28352b9ceda0c4a0b723e4c03ca58d3f6f570.tar.gz gnunet-a5c28352b9ceda0c4a0b723e4c03ca58d3f6f570.zip |
several fixes and comments
Diffstat (limited to 'src/ats/plugin_ats_ril.c')
-rwxr-xr-x | src/ats/plugin_ats_ril.c | 428 |
1 files changed, 264 insertions, 164 deletions
diff --git a/src/ats/plugin_ats_ril.c b/src/ats/plugin_ats_ril.c index 4d0283195..27628ec70 100755 --- a/src/ats/plugin_ats_ril.c +++ b/src/ats/plugin_ats_ril.c | |||
@@ -28,12 +28,12 @@ | |||
28 | 28 | ||
29 | #define LOG(kind,...) GNUNET_log_from (kind, "ats-ril",__VA_ARGS__) | 29 | #define LOG(kind,...) GNUNET_log_from (kind, "ats-ril",__VA_ARGS__) |
30 | 30 | ||
31 | #define RIL_MIN_BW ntohl (GNUNET_CONSTANTS_DEFAULT_BW_IN_OUT.value__) | 31 | #define RIL_MIN_BW ntohl (GNUNET_CONSTANTS_DEFAULT_BW_IN_OUT.value__) |
32 | #define RIL_MAX_BW 1024 * 250 //TODO return to max | 32 | #define RIL_MAX_BW 1024 * 250 //GNUNET_ATS_MaxBandwidth |
33 | 33 | ||
34 | #define RIL_ACTION_INVALID -1 | 34 | #define RIL_ACTION_INVALID -1 |
35 | #define RIL_INTERVAL_EXPONENT 10 | 35 | #define RIL_INTERVAL_EXPONENT 10 |
36 | #define RIL_UTILITY_MAX (double) RIL_MAX_BW | 36 | #define RIL_UTILITY_DELAY_MAX 100 |
37 | 37 | ||
38 | #define RIL_DEFAULT_STEP_TIME_MIN GNUNET_TIME_relative_multiply (GNUNET_TIME_UNIT_MILLISECONDS, 500) | 38 | #define RIL_DEFAULT_STEP_TIME_MIN GNUNET_TIME_relative_multiply (GNUNET_TIME_UNIT_MILLISECONDS, 500) |
39 | #define RIL_DEFAULT_STEP_TIME_MAX GNUNET_TIME_relative_multiply (GNUNET_TIME_UNIT_MILLISECONDS, 3000) | 39 | #define RIL_DEFAULT_STEP_TIME_MAX GNUNET_TIME_relative_multiply (GNUNET_TIME_UNIT_MILLISECONDS, 3000) |
@@ -264,6 +264,11 @@ struct RIL_Peer_Agent | |||
264 | double ** E; | 264 | double ** E; |
265 | 265 | ||
266 | /** | 266 | /** |
267 | * Whether to reset the eligibility traces to 0 after a Q-exploration step | ||
268 | */ | ||
269 | int eligibility_reset; | ||
270 | |||
271 | /** | ||
267 | * Address in use | 272 | * Address in use |
268 | */ | 273 | */ |
269 | struct ATS_Address * address_inuse; | 274 | struct ATS_Address * address_inuse; |
@@ -327,16 +332,26 @@ struct RIL_Scope | |||
327 | unsigned long long bw_in_assigned; | 332 | unsigned long long bw_in_assigned; |
328 | 333 | ||
329 | /** | 334 | /** |
335 | * Bandwidth inbound actually utilized in the network | ||
336 | */ | ||
337 | unsigned long long bw_in_utilized; | ||
338 | |||
339 | /** | ||
330 | * Total available outbound bandwidth | 340 | * Total available outbound bandwidth |
331 | */ | 341 | */ |
332 | unsigned long long bw_out_available; | 342 | unsigned long long bw_out_available; |
333 | 343 | ||
334 | /** | 344 | /** |
335 | * * Bandwidth outbound assigned in network after last step | 345 | * Bandwidth outbound assigned in network after last step |
336 | */ | 346 | */ |
337 | unsigned long long bw_out_assigned; | 347 | unsigned long long bw_out_assigned; |
338 | 348 | ||
339 | /** | 349 | /** |
350 | * Bandwidth outbound actually utilized in the network | ||
351 | */ | ||
352 | unsigned long long bw_out_utilized; | ||
353 | |||
354 | /** | ||
340 | * Number of active agents in scope | 355 | * Number of active agents in scope |
341 | */ | 356 | */ |
342 | unsigned int agent_count; | 357 | unsigned int agent_count; |
@@ -430,7 +445,7 @@ struct GAS_RIL_Handle | |||
430 | }; | 445 | }; |
431 | 446 | ||
432 | /* | 447 | /* |
433 | * Private functions | 448 | * "Private" functions |
434 | * --------------------------- | 449 | * --------------------------- |
435 | */ | 450 | */ |
436 | 451 | ||
@@ -601,7 +616,12 @@ agent_get_action_max (struct RIL_Peer_Agent *agent, double *state) | |||
601 | return max_i; | 616 | return max_i; |
602 | } | 617 | } |
603 | 618 | ||
604 | 619 | /** | |
620 | * Chooses a random action from the set of possible ones | ||
621 | * | ||
622 | * @param agent the agent performing the action | ||
623 | * @return the action index | ||
624 | */ | ||
605 | static int | 625 | static int |
606 | agent_get_action_random (struct RIL_Peer_Agent *agent) | 626 | agent_get_action_random (struct RIL_Peer_Agent *agent) |
607 | { | 627 | { |
@@ -675,7 +695,7 @@ agent_update (struct RIL_Peer_Agent *agent, double reward, double *s_next, int a | |||
675 | // delta, | 695 | // delta, |
676 | // i, | 696 | // i, |
677 | // agent->e[i]); | 697 | // agent->e[i]); |
678 | theta[i] += agent->envi->parameters.alpha * delta * agent->s_old[i] * agent->E[agent->a_old][i]; | 698 | theta[i] += agent->envi->parameters.alpha * delta * agent->E[agent->a_old][i]; |
679 | } | 699 | } |
680 | } | 700 | } |
681 | 701 | ||
@@ -684,7 +704,7 @@ agent_update (struct RIL_Peer_Agent *agent, double reward, double *s_next, int a | |||
684 | * Changes the eligibility trace vector e in various manners: | 704 | * Changes the eligibility trace vector e in various manners: |
685 | * #RIL_E_ACCUMULATE - adds @a feature to each component as in accumulating eligibility traces | 705 | * #RIL_E_ACCUMULATE - adds @a feature to each component as in accumulating eligibility traces |
686 | * #RIL_E_REPLACE - resets each component to @a feature as in replacing traces | 706 | * #RIL_E_REPLACE - resets each component to @a feature as in replacing traces |
687 | * #RIL_E_SET - multiplies e with discount factor and lambda as in the update rule | 707 | * #RIL_E_DISCOUNT - multiplies e with discount factor and lambda as in the update rule |
688 | * #RIL_E_ZERO - sets e to 0 as in Watkin's Q-learning algorithm when exploring and when initializing | 708 | * #RIL_E_ZERO - sets e to 0 as in Watkin's Q-learning algorithm when exploring and when initializing |
689 | * | 709 | * |
690 | * @param agent the agent handle | 710 | * @param agent the agent handle |
@@ -711,7 +731,10 @@ agent_modify_eligibility (struct RIL_Peer_Agent *agent, | |||
711 | agent->E[action][i] = (agent->envi->global_discount_variable * agent->envi->parameters.lambda * agent->E[action][i]) > feature[i] ? agent->E[action][i] : feature[i]; | 731 | agent->E[action][i] = (agent->envi->global_discount_variable * agent->envi->parameters.lambda * agent->E[action][i]) > feature[i] ? agent->E[action][i] : feature[i]; |
712 | break; | 732 | break; |
713 | case RIL_E_DISCOUNT: | 733 | case RIL_E_DISCOUNT: |
714 | agent->E[action][i] *= agent->envi->global_discount_variable * agent->envi->parameters.lambda; | 734 | for (k = 0; k < agent->n; k++) |
735 | { | ||
736 | agent->E[k][i] *= agent->envi->global_discount_variable * agent->envi->parameters.lambda; | ||
737 | } | ||
715 | break; | 738 | break; |
716 | case RIL_E_ZERO: | 739 | case RIL_E_ZERO: |
717 | for (k = 0; k < agent->n; k++) | 740 | for (k = 0; k < agent->n; k++) |
@@ -723,11 +746,17 @@ agent_modify_eligibility (struct RIL_Peer_Agent *agent, | |||
723 | } | 746 | } |
724 | } | 747 | } |
725 | 748 | ||
726 | 749 | /** | |
750 | * Informs the environment about the status of the solver | ||
751 | * | ||
752 | * @param solver | ||
753 | * @param op | ||
754 | * @param stat | ||
755 | */ | ||
727 | static void | 756 | static void |
728 | ril_inform (struct GAS_RIL_Handle *solver, | 757 | ril_inform (struct GAS_RIL_Handle *solver, |
729 | enum GAS_Solver_Operation op, | 758 | enum GAS_Solver_Operation op, |
730 | enum GAS_Solver_Status stat) | 759 | enum GAS_Solver_Status stat) |
731 | { | 760 | { |
732 | if (NULL != solver->plugin_envi->info_cb) | 761 | if (NULL != solver->plugin_envi->info_cb) |
733 | solver->plugin_envi->info_cb (solver->plugin_envi->info_cb_cls, op, stat, GAS_INFO_NONE); | 762 | solver->plugin_envi->info_cb (solver->plugin_envi->info_cb_cls, op, stat, GAS_INFO_NONE); |
@@ -824,31 +853,6 @@ envi_set_active_suggestion (struct GAS_RIL_Handle *solver, | |||
824 | } | 853 | } |
825 | 854 | ||
826 | 855 | ||
827 | static unsigned long long | ||
828 | ril_network_get_assigned (struct GAS_RIL_Handle *solver, enum GNUNET_ATS_Network_Type type, int direction_in) | ||
829 | { | ||
830 | struct RIL_Peer_Agent *cur; | ||
831 | struct RIL_Scope *net; | ||
832 | unsigned long long sum = 0; | ||
833 | |||
834 | for (cur = solver->agents_head; NULL != cur; cur = cur->next) | ||
835 | { | ||
836 | if (cur->is_active && cur->address_inuse) | ||
837 | { | ||
838 | net = cur->address_inuse->solver_information; | ||
839 | if (net->type == type) | ||
840 | { | ||
841 | if (direction_in) | ||
842 | sum += cur->bw_in; | ||
843 | else | ||
844 | sum += cur->bw_out; | ||
845 | } | ||
846 | } | ||
847 | } | ||
848 | |||
849 | return sum; | ||
850 | } | ||
851 | |||
852 | /** | 856 | /** |
853 | * Allocates a state vector and fills it with the features present | 857 | * Allocates a state vector and fills it with the features present |
854 | * @param solver the solver handle | 858 | * @param solver the solver handle |
@@ -894,120 +898,67 @@ envi_get_state (struct GAS_RIL_Handle *solver, struct RIL_Peer_Agent *agent) | |||
894 | return state; | 898 | return state; |
895 | } | 899 | } |
896 | 900 | ||
897 | ///* | 901 | /** |
898 | // * For all networks a peer has an address in, this gets the maximum bandwidth which could | 902 | * Retrieves an ATS information value of an address |
899 | // * theoretically be available in one of the networks. This is used for bandwidth normalization. | 903 | * |
900 | // * | 904 | * @param address the address in question |
901 | // * @param agent the agent handle | 905 | * @param type the ATS information type |
902 | // * @param direction_in whether the inbound bandwidth should be considered. Returns the maximum outbound bandwidth if GNUNET_NO | 906 | * @return the value |
903 | // */ | 907 | */ |
904 | //static unsigned long long | 908 | static unsigned int |
905 | //ril_get_max_bw (struct RIL_Peer_Agent *agent, int direction_in) | 909 | ril_get_atsi (struct ATS_Address *address, uint32_t type) |
906 | //{ | 910 | { |
907 | // /* | 911 | int c1; |
908 | // * get the maximum bandwidth possible for a peer, e.g. among all addresses which addresses' | 912 | GNUNET_assert(NULL != address); |
909 | // * network could provide the maximum bandwidth if all that bandwidth was used on that one peer. | 913 | |
910 | // */ | 914 | if ((NULL == address->atsi) || (0 == address->atsi_count)) |
911 | // unsigned long long max = 0; | 915 | return GNUNET_ATS_QUALITY_NET_DELAY == type ? UINT32_MAX : 1; |
912 | // struct RIL_Address_Wrapped *cur; | ||
913 | // struct RIL_Scope *net; | ||
914 | // | ||
915 | // for (cur = agent->addresses_head; NULL != cur; cur = cur->next) | ||
916 | // { | ||
917 | // net = cur->address_naked->solver_information; | ||
918 | // if (direction_in) | ||
919 | // { | ||
920 | // if (net->bw_in_available > max) | ||
921 | // { | ||
922 | // max = net->bw_in_available; | ||
923 | // } | ||
924 | // } | ||
925 | // else | ||
926 | // { | ||
927 | // if (net->bw_out_available > max) | ||
928 | // { | ||
929 | // max = net->bw_out_available; | ||
930 | // } | ||
931 | // } | ||
932 | // } | ||
933 | // return max; | ||
934 | //} | ||
935 | // | ||
936 | ///* | ||
937 | // * Get the index of the quality-property in question | ||
938 | // * | ||
939 | // * @param type the quality property type | ||
940 | // * @return the index | ||
941 | // */ | ||
942 | //static int | ||
943 | //ril_find_property_index (uint32_t type) | ||
944 | //{ | ||
945 | // int existing_types[] = GNUNET_ATS_QualityProperties; | ||
946 | // int c; | ||
947 | // for (c = 0; c < GNUNET_ATS_QualityPropertiesCount; c++) | ||
948 | // if (existing_types[c] == type) | ||
949 | // return c; | ||
950 | // return GNUNET_SYSERR; | ||
951 | //} | ||
952 | // | ||
953 | //static int | ||
954 | //ril_get_atsi (struct ATS_Address *address, uint32_t type) | ||
955 | //{ | ||
956 | // int c1; | ||
957 | // GNUNET_assert(NULL != address); | ||
958 | // | ||
959 | // if ((NULL == address->atsi) || (0 == address->atsi_count)) | ||
960 | // return 0; | ||
961 | // | ||
962 | // for (c1 = 0; c1 < address->atsi_count; c1++) | ||
963 | // { | ||
964 | // if (ntohl (address->atsi[c1].type) == type) | ||
965 | // return ntohl (address->atsi[c1].value); | ||
966 | // } | ||
967 | // return 0; | ||
968 | //} | ||
969 | // | ||
970 | // | ||
971 | //static double | ||
972 | //envi_reward_local (struct GAS_RIL_Handle *solver, struct RIL_Peer_Agent *agent) | ||
973 | //{ | ||
974 | // const double *preferences; | ||
975 | // const double *properties; | ||
976 | // int prop_index; | ||
977 | // double pref_match = 0; | ||
978 | // double bw_norm; | ||
979 | // double dl_norm; | ||
980 | // | ||
981 | // preferences = solver->plugin_envi->get_preferences (solver->plugin_envi->get_preference_cls, | ||
982 | // &agent->peer); | ||
983 | // properties = solver->plugin_envi->get_property (solver->plugin_envi->get_property_cls, | ||
984 | // agent->address_inuse); | ||
985 | // | ||
986 | // // delay in [0,1] | ||
987 | // prop_index = ril_find_property_index (GNUNET_ATS_QUALITY_NET_DELAY); | ||
988 | // dl_norm = 2 - properties[prop_index]; //invert property as we want to maximize for lower latencies | ||
989 | // | ||
990 | // // utilization in [0,1] | ||
991 | // bw_norm = (((double) ril_get_atsi (agent->address_inuse, GNUNET_ATS_UTILIZATION_IN) | ||
992 | // / (double) ril_get_max_bw (agent, GNUNET_YES)) | ||
993 | // + ((double) ril_get_atsi (agent->address_inuse, GNUNET_ATS_UTILIZATION_OUT) | ||
994 | // / (double) ril_get_max_bw (agent, GNUNET_NO))) / 2; | ||
995 | // | ||
996 | // // preference matching in [0,4] | ||
997 | // pref_match += (preferences[GNUNET_ATS_PREFERENCE_LATENCY] * dl_norm); | ||
998 | // pref_match += (preferences[GNUNET_ATS_PREFERENCE_BANDWIDTH] * bw_norm); | ||
999 | // | ||
1000 | // // local reward in [1,2] | ||
1001 | // return (pref_match / 4) +1; | ||
1002 | //} | ||
1003 | 916 | ||
917 | for (c1 = 0; c1 < address->atsi_count; c1++) | ||
918 | { | ||
919 | if (ntohl (address->atsi[c1].type) == type) | ||
920 | return ntohl (address->atsi[c1].value); | ||
921 | } | ||
922 | return GNUNET_ATS_QUALITY_NET_DELAY == type ? UINT32_MAX : 1; | ||
923 | } | ||
924 | |||
925 | /** | ||
926 | * Returns the utility value of the connection an agent manages | ||
927 | * | ||
928 | * @param agent the agent in question | ||
929 | * @return the utility value | ||
930 | */ | ||
1004 | static double | 931 | static double |
1005 | agent_get_utility (struct RIL_Peer_Agent *agent) | 932 | agent_get_utility (struct RIL_Peer_Agent *agent) |
1006 | { | 933 | { |
934 | const double *preferences; | ||
935 | double delay_atsi; | ||
936 | double delay_norm; | ||
937 | double pref_match; | ||
938 | |||
939 | preferences = agent->envi->plugin_envi->get_preferences (agent->envi->plugin_envi->get_preference_cls, | ||
940 | &agent->peer); | ||
941 | |||
942 | delay_atsi = (double) ril_get_atsi (agent->address_inuse, GNUNET_ATS_QUALITY_NET_DELAY); | ||
943 | delay_norm = RIL_UTILITY_DELAY_MAX*exp(-delay_atsi*0.00001); | ||
944 | |||
945 | pref_match = (preferences[GNUNET_ATS_PREFERENCE_LATENCY] * delay_norm); | ||
946 | pref_match += (preferences[GNUNET_ATS_PREFERENCE_BANDWIDTH] * (double) (agent->bw_in/RIL_MIN_BW)); | ||
947 | pref_match += (preferences[GNUNET_ATS_PREFERENCE_BANDWIDTH] * (double) (agent->bw_out/RIL_MIN_BW)); | ||
948 | |||
1007 | // return (double) (agent->bw_in/RIL_MIN_BW); | 949 | // return (double) (agent->bw_in/RIL_MIN_BW); |
1008 | return sqrt((double) (agent->bw_in/RIL_MIN_BW) * (double) (agent->bw_out/RIL_MIN_BW)); | 950 | // return sqrt((double) (agent->bw_in/RIL_MIN_BW) * (double) (agent->bw_out/RIL_MIN_BW)); |
951 | return pref_match; | ||
1009 | } | 952 | } |
1010 | 953 | ||
954 | /** | ||
955 | * Calculates the social welfare within a network scope according to what social | ||
956 | * welfare measure is set in the configuration. | ||
957 | * | ||
958 | * @param solver the solver handle | ||
959 | * @param scope the network scope in question | ||
960 | * @return the social welfare value | ||
961 | */ | ||
1011 | static double | 962 | static double |
1012 | ril_network_get_social_welfare (struct GAS_RIL_Handle *solver, struct RIL_Scope *scope) | 963 | ril_network_get_social_welfare (struct GAS_RIL_Handle *solver, struct RIL_Scope *scope) |
1013 | { | 964 | { |
@@ -1017,7 +968,7 @@ ril_network_get_social_welfare (struct GAS_RIL_Handle *solver, struct RIL_Scope | |||
1017 | switch (solver->parameters.social_welfare) | 968 | switch (solver->parameters.social_welfare) |
1018 | { | 969 | { |
1019 | case RIL_WELFARE_EGALITARIAN: | 970 | case RIL_WELFARE_EGALITARIAN: |
1020 | result = RIL_UTILITY_MAX; | 971 | result = DBL_MAX; |
1021 | for (cur = solver->agents_head; NULL != cur; cur = cur->next) | 972 | for (cur = solver->agents_head; NULL != cur; cur = cur->next) |
1022 | { | 973 | { |
1023 | if (cur->is_active && cur->address_inuse && (cur->address_inuse->solver_information == scope)) | 974 | if (cur->is_active && cur->address_inuse && (cur->address_inuse->solver_information == scope)) |
@@ -1064,6 +1015,7 @@ envi_get_reward (struct GAS_RIL_Handle *solver, struct RIL_Peer_Agent *agent) | |||
1064 | 1015 | ||
1065 | net = agent->address_inuse->solver_information; | 1016 | net = agent->address_inuse->solver_information; |
1066 | 1017 | ||
1018 | //TODO make sure in tests to have utilization property updated | ||
1067 | if (net->bw_in_assigned > net->bw_in_available) | 1019 | if (net->bw_in_assigned > net->bw_in_available) |
1068 | over_in = net->bw_in_assigned - net->bw_in_available; | 1020 | over_in = net->bw_in_assigned - net->bw_in_available; |
1069 | if (net->bw_out_assigned > net->bw_out_available) | 1021 | if (net->bw_out_assigned > net->bw_out_available) |
@@ -1074,10 +1026,10 @@ envi_get_reward (struct GAS_RIL_Handle *solver, struct RIL_Peer_Agent *agent) | |||
1074 | delta = objective - agent->objective_old; | 1026 | delta = objective - agent->objective_old; |
1075 | agent->objective_old = objective; | 1027 | agent->objective_old = objective; |
1076 | 1028 | ||
1077 | // if (delta != 0) | 1029 | if (delta != 0) |
1078 | // { | 1030 | { |
1079 | agent->nop_bonus = 0.5; | 1031 | agent->nop_bonus = delta * 0.5; |
1080 | // } | 1032 | } |
1081 | 1033 | ||
1082 | LOG(GNUNET_ERROR_TYPE_DEBUG, "agent->nop_bonus: %f\n", agent->nop_bonus); | 1034 | LOG(GNUNET_ERROR_TYPE_DEBUG, "agent->nop_bonus: %f\n", agent->nop_bonus); |
1083 | 1035 | ||
@@ -1310,6 +1262,17 @@ envi_do_action (struct GAS_RIL_Handle *solver, struct RIL_Peer_Agent *agent, int | |||
1310 | } | 1262 | } |
1311 | } | 1263 | } |
1312 | 1264 | ||
1265 | /** | ||
1266 | * Selects the next action using the e-greedy strategy. I.e. with a probability | ||
1267 | * of (1-e) the action with the maximum expected return will be chosen | ||
1268 | * (=> exploitation) and with probability (e) a random action will be chosen. | ||
1269 | * In case the Q-learning rule is set, the function also resets the eligibility | ||
1270 | * traces in the exploration case (after Watkin's Q-learning). | ||
1271 | * | ||
1272 | * @param agent the agent selecting an action | ||
1273 | * @param state the current state-feature vector | ||
1274 | * @return the action index | ||
1275 | */ | ||
1313 | static int | 1276 | static int |
1314 | agent_select_egreedy (struct RIL_Peer_Agent *agent, double *state) | 1277 | agent_select_egreedy (struct RIL_Peer_Agent *agent, double *state) |
1315 | { | 1278 | { |
@@ -1322,17 +1285,13 @@ agent_select_egreedy (struct RIL_Peer_Agent *agent, double *state) | |||
1322 | action = agent_get_action_random(agent); | 1285 | action = agent_get_action_random(agent); |
1323 | if (RIL_ALGO_Q == agent->envi->parameters.algorithm) | 1286 | if (RIL_ALGO_Q == agent->envi->parameters.algorithm) |
1324 | { | 1287 | { |
1325 | agent_modify_eligibility(agent, RIL_E_ZERO, NULL, action); | 1288 | agent->eligibility_reset = GNUNET_YES; |
1326 | } | 1289 | } |
1327 | return action; | 1290 | return action; |
1328 | } | 1291 | } |
1329 | else //exploit | 1292 | else //exploit |
1330 | { | 1293 | { |
1331 | action = agent_get_action_max(agent, state); | 1294 | action = agent_get_action_max(agent, state); |
1332 | if (RIL_ALGO_Q == agent->envi->parameters.algorithm) | ||
1333 | { | ||
1334 | agent_modify_eligibility(agent, RIL_E_DISCOUNT, NULL, action); | ||
1335 | } | ||
1336 | return action; | 1295 | return action; |
1337 | } | 1296 | } |
1338 | } | 1297 | } |
@@ -1387,10 +1346,8 @@ agent_select_softmax (struct RIL_Peer_Agent *agent, double *state) | |||
1387 | { | 1346 | { |
1388 | if (RIL_ALGO_Q == agent->envi->parameters.algorithm) | 1347 | if (RIL_ALGO_Q == agent->envi->parameters.algorithm) |
1389 | { | 1348 | { |
1390 | if (i == a_max) | 1349 | if (i != a_max) |
1391 | agent_modify_eligibility(agent, RIL_E_DISCOUNT, NULL, i); | 1350 | agent->eligibility_reset = GNUNET_YES; |
1392 | else | ||
1393 | agent_modify_eligibility(agent, RIL_E_ZERO, NULL, -1); | ||
1394 | } | 1351 | } |
1395 | return i; | 1352 | return i; |
1396 | } | 1353 | } |
@@ -1399,6 +1356,14 @@ agent_select_softmax (struct RIL_Peer_Agent *agent, double *state) | |||
1399 | GNUNET_assert(GNUNET_NO); | 1356 | GNUNET_assert(GNUNET_NO); |
1400 | } | 1357 | } |
1401 | 1358 | ||
1359 | /** | ||
1360 | * Select the next action of an agent either according to the e-greedy strategy | ||
1361 | * or the softmax strategy. | ||
1362 | * | ||
1363 | * @param agent the agent in question | ||
1364 | * @param state the current state-feature vector | ||
1365 | * @return the action index | ||
1366 | */ | ||
1402 | static int | 1367 | static int |
1403 | agent_select_action (struct RIL_Peer_Agent *agent, double *state) | 1368 | agent_select_action (struct RIL_Peer_Agent *agent, double *state) |
1404 | { | 1369 | { |
@@ -1435,6 +1400,20 @@ agent_step (struct RIL_Peer_Agent *agent) | |||
1435 | s_next = envi_get_state (agent->envi, agent); | 1400 | s_next = envi_get_state (agent->envi, agent); |
1436 | reward = envi_get_reward (agent->envi, agent); | 1401 | reward = envi_get_reward (agent->envi, agent); |
1437 | 1402 | ||
1403 | if (agent->eligibility_reset) | ||
1404 | { | ||
1405 | agent_modify_eligibility(agent, RIL_E_ZERO, NULL, -1); | ||
1406 | agent->eligibility_reset = GNUNET_NO; | ||
1407 | } | ||
1408 | else | ||
1409 | { | ||
1410 | agent_modify_eligibility (agent, RIL_E_DISCOUNT, NULL, -1); | ||
1411 | } | ||
1412 | if (RIL_ACTION_INVALID != agent->a_old) | ||
1413 | { | ||
1414 | agent_modify_eligibility (agent, agent->envi->parameters.eligibility_trace_mode, agent->s_old, agent->a_old); | ||
1415 | } | ||
1416 | |||
1438 | switch (agent->envi->parameters.algorithm) | 1417 | switch (agent->envi->parameters.algorithm) |
1439 | { | 1418 | { |
1440 | case RIL_ALGO_SARSA: | 1419 | case RIL_ALGO_SARSA: |
@@ -1444,7 +1423,6 @@ agent_step (struct RIL_Peer_Agent *agent) | |||
1444 | //updates weights with selected action (on-policy), if not first step | 1423 | //updates weights with selected action (on-policy), if not first step |
1445 | agent_update (agent, reward, s_next, a_next); | 1424 | agent_update (agent, reward, s_next, a_next); |
1446 | } | 1425 | } |
1447 | agent_modify_eligibility (agent, RIL_E_DISCOUNT, s_next, a_next); | ||
1448 | break; | 1426 | break; |
1449 | 1427 | ||
1450 | case RIL_ALGO_Q: | 1428 | case RIL_ALGO_Q: |
@@ -1460,8 +1438,6 @@ agent_step (struct RIL_Peer_Agent *agent) | |||
1460 | 1438 | ||
1461 | GNUNET_assert(RIL_ACTION_INVALID != a_next); | 1439 | GNUNET_assert(RIL_ACTION_INVALID != a_next); |
1462 | 1440 | ||
1463 | agent_modify_eligibility (agent, agent->envi->parameters.eligibility_trace_mode, s_next, a_next); | ||
1464 | |||
1465 | GNUNET_log (GNUNET_ERROR_TYPE_INFO, "step() Step# %llu R: %f IN %llu OUT %llu A: %d\n", | 1441 | GNUNET_log (GNUNET_ERROR_TYPE_INFO, "step() Step# %llu R: %f IN %llu OUT %llu A: %d\n", |
1466 | agent->step_count, | 1442 | agent->step_count, |
1467 | reward, | 1443 | reward, |
@@ -1478,6 +1454,11 @@ agent_step (struct RIL_Peer_Agent *agent) | |||
1478 | agent->step_count += 1; | 1454 | agent->step_count += 1; |
1479 | } | 1455 | } |
1480 | 1456 | ||
1457 | /** | ||
1458 | * Prototype of the ril_step() procedure | ||
1459 | * | ||
1460 | * @param solver the solver handle | ||
1461 | */ | ||
1481 | static void | 1462 | static void |
1482 | ril_step (struct GAS_RIL_Handle *solver); | 1463 | ril_step (struct GAS_RIL_Handle *solver); |
1483 | 1464 | ||
@@ -1497,6 +1478,14 @@ ril_step_scheduler_task (void *cls, const struct GNUNET_SCHEDULER_TaskContext *t | |||
1497 | ril_step (solver); | 1478 | ril_step (solver); |
1498 | } | 1479 | } |
1499 | 1480 | ||
1481 | /** | ||
1482 | * Determines how much of the available bandwidth is assigned. If more is | ||
1483 | * assigned than available it returns 1. The function is used to determine the | ||
1484 | * step size of the adaptive stepping. | ||
1485 | * | ||
1486 | * @param solver the solver handle | ||
1487 | * @return the ratio | ||
1488 | */ | ||
1500 | static double | 1489 | static double |
1501 | ril_get_used_resource_ratio (struct GAS_RIL_Handle *solver) | 1490 | ril_get_used_resource_ratio (struct GAS_RIL_Handle *solver) |
1502 | { | 1491 | { |
@@ -1526,7 +1515,7 @@ ril_get_used_resource_ratio (struct GAS_RIL_Handle *solver) | |||
1526 | ratio = 0; | 1515 | ratio = 0; |
1527 | } | 1516 | } |
1528 | 1517 | ||
1529 | return ratio > 1 ? 1 : ratio; //overutilization possible, cap at 1 | 1518 | return ratio > 1 ? 1 : ratio; //overassignment is possible, cap at 1 |
1530 | } | 1519 | } |
1531 | 1520 | ||
1532 | /** | 1521 | /** |
@@ -1551,6 +1540,15 @@ ril_get_network (struct GAS_RIL_Handle *s, uint32_t type) | |||
1551 | return NULL ; | 1540 | return NULL ; |
1552 | } | 1541 | } |
1553 | 1542 | ||
1543 | /** | ||
1544 | * Determines whether more connections are allocated in a network scope, than | ||
1545 | * they would theoretically fit. This is used as a heuristic to determine, | ||
1546 | * whether a new connection can be allocated or not. | ||
1547 | * | ||
1548 | * @param solver the solver handle | ||
1549 | * @param network the network scope in question | ||
1550 | * @return GNUNET_YES if there are theoretically enough resources left | ||
1551 | */ | ||
1554 | static int | 1552 | static int |
1555 | ril_network_is_not_full (struct GAS_RIL_Handle *solver, enum GNUNET_ATS_Network_Type network) | 1553 | ril_network_is_not_full (struct GAS_RIL_Handle *solver, enum GNUNET_ATS_Network_Type network) |
1556 | { | 1554 | { |
@@ -1574,6 +1572,16 @@ ril_network_is_not_full (struct GAS_RIL_Handle *solver, enum GNUNET_ATS_Network_ | |||
1574 | return (net->bw_in_available > RIL_MIN_BW * address_count) && (net->bw_out_available > RIL_MIN_BW * address_count); | 1572 | return (net->bw_in_available > RIL_MIN_BW * address_count) && (net->bw_out_available > RIL_MIN_BW * address_count); |
1575 | } | 1573 | } |
1576 | 1574 | ||
1575 | /** | ||
1576 | * Unblocks an agent for which a connection request is there, that could not | ||
1577 | * be satisfied. Iterates over the addresses of the agent, if one of its | ||
1578 | * addresses can now be allocated in its scope the agent is unblocked, | ||
1579 | * otherwise it remains unchanged. | ||
1580 | * | ||
1581 | * @param solver the solver handle | ||
1582 | * @param agent the agent in question | ||
1583 | * @param silent | ||
1584 | */ | ||
1577 | static void | 1585 | static void |
1578 | ril_try_unblock_agent (struct GAS_RIL_Handle *solver, struct RIL_Peer_Agent *agent, int silent) | 1586 | ril_try_unblock_agent (struct GAS_RIL_Handle *solver, struct RIL_Peer_Agent *agent, int silent) |
1579 | { | 1587 | { |
@@ -1593,6 +1601,12 @@ ril_try_unblock_agent (struct GAS_RIL_Handle *solver, struct RIL_Peer_Agent *age | |||
1593 | agent->address_inuse = NULL; | 1601 | agent->address_inuse = NULL; |
1594 | } | 1602 | } |
1595 | 1603 | ||
1604 | /** | ||
1605 | * Determines how much the reward needs to be discounted depending on the amount | ||
1606 | * of time, which has passed since the last time-step. | ||
1607 | * | ||
1608 | * @param solver the solver handle | ||
1609 | */ | ||
1596 | static void | 1610 | static void |
1597 | ril_calculate_discount (struct GAS_RIL_Handle *solver) | 1611 | ril_calculate_discount (struct GAS_RIL_Handle *solver) |
1598 | { | 1612 | { |
@@ -1623,6 +1637,13 @@ ril_calculate_discount (struct GAS_RIL_Handle *solver) | |||
1623 | / (double) solver->parameters.beta; | 1637 | / (double) solver->parameters.beta; |
1624 | } | 1638 | } |
1625 | 1639 | ||
1640 | /** | ||
1641 | * Count the number of active agents/connections in a network scope | ||
1642 | * | ||
1643 | * @param solver the solver handle | ||
1644 | * @param scope the network scope in question | ||
1645 | * @return the number of allocated connections | ||
1646 | */ | ||
1626 | static int | 1647 | static int |
1627 | ril_network_count_active_agents (struct GAS_RIL_Handle *solver, struct RIL_Scope *scope) | 1648 | ril_network_count_active_agents (struct GAS_RIL_Handle *solver, struct RIL_Scope *scope) |
1628 | { | 1649 | { |
@@ -1639,6 +1660,82 @@ ril_network_count_active_agents (struct GAS_RIL_Handle *solver, struct RIL_Scope | |||
1639 | return c; | 1660 | return c; |
1640 | } | 1661 | } |
1641 | 1662 | ||
1663 | /** | ||
1664 | * Calculates how much bandwidth is assigned in sum in a network scope, either | ||
1665 | * in the inbound or in the outbound direction. | ||
1666 | * | ||
1667 | * @param solver the solver handle | ||
1668 | * @param type the type of the network scope in question | ||
1669 | * @param direction_in GNUNET_YES if the inbound direction should be summed up, | ||
1670 | * otherwise the outbound direction will be summed up | ||
1671 | * @return the sum of the assigned bandwidths | ||
1672 | */ | ||
1673 | static unsigned long long | ||
1674 | ril_network_get_assigned (struct GAS_RIL_Handle *solver, enum GNUNET_ATS_Network_Type type, int direction_in) | ||
1675 | { | ||
1676 | struct RIL_Peer_Agent *cur; | ||
1677 | struct RIL_Scope *net; | ||
1678 | unsigned long long sum = 0; | ||
1679 | |||
1680 | for (cur = solver->agents_head; NULL != cur; cur = cur->next) | ||
1681 | { | ||
1682 | if (cur->is_active && cur->address_inuse) | ||
1683 | { | ||
1684 | net = cur->address_inuse->solver_information; | ||
1685 | if (net->type == type) | ||
1686 | { | ||
1687 | if (direction_in) | ||
1688 | sum += cur->bw_in; | ||
1689 | else | ||
1690 | sum += cur->bw_out; | ||
1691 | } | ||
1692 | } | ||
1693 | } | ||
1694 | |||
1695 | return sum; | ||
1696 | } | ||
1697 | |||
1698 | /** | ||
1699 | * Calculates how much bandwidth is actually utilized in sum in a network scope, | ||
1700 | * either in the inbound or in the outbound direction. | ||
1701 | * | ||
1702 | * @param solver the solver handle | ||
1703 | * @param type the type of the network scope in question | ||
1704 | * @param direction_in GNUNET_YES if the inbound direction should be summed up, | ||
1705 | * otherwise the outbound direction will be summed up | ||
1706 | * @return the sum of the utilized bandwidths (in bytes/second) | ||
1707 | */ | ||
1708 | static unsigned long long | ||
1709 | ril_network_get_utilized (struct GAS_RIL_Handle *solver, enum GNUNET_ATS_Network_Type type, int direction_in) | ||
1710 | { | ||
1711 | struct RIL_Peer_Agent *cur; | ||
1712 | struct RIL_Scope *net; | ||
1713 | unsigned long long sum = 0; | ||
1714 | |||
1715 | for (cur = solver->agents_head; NULL != cur; cur = cur->next) | ||
1716 | { | ||
1717 | if (cur->is_active && cur->address_inuse) | ||
1718 | { | ||
1719 | net = cur->address_inuse->solver_information; | ||
1720 | if (net->type == type) | ||
1721 | { | ||
1722 | if (direction_in) | ||
1723 | sum += ril_get_atsi (cur->address_inuse, GNUNET_ATS_UTILIZATION_IN); | ||
1724 | else | ||
1725 | sum += ril_get_atsi (cur->address_inuse, GNUNET_ATS_UTILIZATION_OUT); | ||
1726 | } | ||
1727 | } | ||
1728 | } | ||
1729 | |||
1730 | return sum; | ||
1731 | } | ||
1732 | |||
1733 | /** | ||
1734 | * Retrieves the state of the network scope, so that its attributes are up-to- | ||
1735 | * date. | ||
1736 | * | ||
1737 | * @param solver the solver handle | ||
1738 | */ | ||
1642 | static void | 1739 | static void |
1643 | ril_networks_update_state (struct GAS_RIL_Handle *solver) | 1740 | ril_networks_update_state (struct GAS_RIL_Handle *solver) |
1644 | { | 1741 | { |
@@ -1649,7 +1746,9 @@ ril_networks_update_state (struct GAS_RIL_Handle *solver) | |||
1649 | { | 1746 | { |
1650 | net = &solver->network_entries[c]; | 1747 | net = &solver->network_entries[c]; |
1651 | net->bw_in_assigned = ril_network_get_assigned(solver, net->type, GNUNET_YES); | 1748 | net->bw_in_assigned = ril_network_get_assigned(solver, net->type, GNUNET_YES); |
1749 | net->bw_in_utilized = ril_network_get_utilized(solver, net->type, GNUNET_YES); | ||
1652 | net->bw_out_assigned = ril_network_get_assigned(solver, net->type, GNUNET_NO); | 1750 | net->bw_out_assigned = ril_network_get_assigned(solver, net->type, GNUNET_NO); |
1751 | net->bw_out_utilized = ril_network_get_utilized(solver, net->type, GNUNET_NO); | ||
1653 | net->agent_count = ril_network_count_active_agents(solver, net); | 1752 | net->agent_count = ril_network_count_active_agents(solver, net); |
1654 | net->social_welfare = ril_network_get_social_welfare(solver, net); | 1753 | net->social_welfare = ril_network_get_social_welfare(solver, net); |
1655 | } | 1754 | } |
@@ -1812,6 +1911,7 @@ agent_init (void *s, const struct GNUNET_PeerIdentity *peer) | |||
1812 | agent->E[i] = (double *) GNUNET_malloc (sizeof (double) * agent->m); | 1911 | agent->E[i] = (double *) GNUNET_malloc (sizeof (double) * agent->m); |
1813 | } | 1912 | } |
1814 | agent_w_init(agent); | 1913 | agent_w_init(agent); |
1914 | agent->eligibility_reset = GNUNET_NO; | ||
1815 | agent->a_old = RIL_ACTION_INVALID; | 1915 | agent->a_old = RIL_ACTION_INVALID; |
1816 | agent->s_old = GNUNET_malloc (sizeof (double) * agent->m); | 1916 | agent->s_old = GNUNET_malloc (sizeof (double) * agent->m); |
1817 | agent->address_inuse = NULL; | 1917 | agent->address_inuse = NULL; |