From e5a04492ab3e988a391f88d87f3bf7fcdf80d66b Mon Sep 17 00:00:00 2001 From: Matthias Wachs Date: Fri, 18 Jan 2013 16:52:13 +0000 Subject: preference aging + improved quota recalculation due to pref change --- src/ats/gnunet-service-ats_addresses_simplistic.c | 286 +++++++++++++--------- 1 file changed, 169 insertions(+), 117 deletions(-) (limited to 'src/ats/gnunet-service-ats_addresses_simplistic.c') diff --git a/src/ats/gnunet-service-ats_addresses_simplistic.c b/src/ats/gnunet-service-ats_addresses_simplistic.c index b5df2a1f6..7b95eed2d 100644 --- a/src/ats/gnunet-service-ats_addresses_simplistic.c +++ b/src/ats/gnunet-service-ats_addresses_simplistic.c @@ -55,7 +55,7 @@ * */ -#define PREF_AGING_INTERVAL GNUNET_TIME_relative_multiply (GNUNET_TIME_UNIT_SECONDS, 1) +#define PREF_AGING_INTERVAL GNUNET_TIME_relative_multiply (GNUNET_TIME_UNIT_SECONDS, 10) #define PREF_AGING_FACTOR 0.95 #define DEFAULT_PREFERENCE 1.0 @@ -165,19 +165,6 @@ struct AddressWrapper }; -struct PreferencePeer -{ - struct PreferencePeer *next; - struct PreferencePeer *prev; - struct GNUNET_PeerIdentity id; - - double f[GNUNET_ATS_PreferenceCount]; - double f_rel[GNUNET_ATS_PreferenceCount]; - double f_rel_total; - - GNUNET_SCHEDULER_TaskIdentifier aging_task; -}; - struct PreferenceClient { struct PreferenceClient *prev; @@ -191,6 +178,21 @@ struct PreferenceClient }; +struct PreferencePeer +{ + struct PreferencePeer *next; + struct PreferencePeer *prev; + struct PreferenceClient *client; + struct GAS_SIMPLISTIC_Handle *s; + struct GNUNET_PeerIdentity id; + + double f[GNUNET_ATS_PreferenceCount]; + double f_rel[GNUNET_ATS_PreferenceCount]; + double f_rel_total; + + GNUNET_SCHEDULER_TaskIdentifier aging_task; +}; + /** * Get the prefered address for a specific peer * @@ -399,6 +401,7 @@ bw_available_in_network (struct Network *net) return GNUNET_NO; } + /** * Update the quotas for a network type * @@ -535,6 +538,15 @@ update_quota_per_network (struct GAS_SIMPLISTIC_Handle *s, } } +static void +update_all_networks (struct GAS_SIMPLISTIC_Handle *s) +{ + int i; + for (i = 0; i < s->networks; i++) + update_quota_per_network (s, &s->network_entries[i], NULL); + +} + static void addresse_increment (struct GAS_SIMPLISTIC_Handle *s, struct Network *net, @@ -1076,72 +1088,99 @@ GAS_simplistic_get_preferred_address (void *solver, } static void -update_preference (struct GAS_SIMPLISTIC_Handle *s, - struct PreferenceClient *cur, - struct PreferencePeer *p, - enum GNUNET_ATS_PreferenceKind kind, - float score_f) +recalculate_preferences (struct PreferencePeer *p) { - double p_rel_global; + struct GAS_SIMPLISTIC_Handle *s = p->s; + struct PreferencePeer *p_cur; + struct PreferenceClient *c_cur = p->client; + double p_rel_global; double *dest; - double score = score_f; - struct PreferencePeer *p_cur; - int i; + int kind; + int rkind; int clients; - /* Update preference value according to type */ - switch (kind) { - case GNUNET_ATS_PREFERENCE_BANDWIDTH: - case GNUNET_ATS_PREFERENCE_LATENCY: - p->f[kind] = (p->f[kind] + score) / 2; - break; - case GNUNET_ATS_PREFERENCE_END: - break; - default: - break; - } - - /* Recalcalculate total preference for this quality kind over all peers*/ - cur->f_total[kind] = 0; - for (p_cur = cur->p_head; NULL != p_cur; p_cur = p_cur->next) - cur->f_total[kind] += p_cur->f[kind]; - - LOG (GNUNET_ERROR_TYPE_DEBUG, "Client %p has total preference for %s of %.3f\n", - cur->client, - GNUNET_ATS_print_preference_type (kind), - cur->f_total[kind]); + /** + * Idea: + * + * We have: + * Set of clients c + * Set of peers p_i in P + * Set of preference kinds k + * A preference value f_k_p_i with an unknown range + * + * We get: + * A client specific relative preference f_p_i_rel [1..2] for all peers + * + * For every client c + * { + * For every preference kind k: + * { + * We remember for the preference f_p_i for each peer p_i. + * We have a default preference value f_p_i = 0 + * We have a sum of all preferences f_t = sum (f_p_i) + * So we can calculate a relative preference value fr_p_i: + * + * f_k_p_i_rel = (f_t + f_p_i) / f_t + * f_k_p_i_rel = [1..2], default 1.0 + * } + * f_p_i_rel = sum (f_k_p_i_rel) / #k + * } + * + **/ - /* Recalcalculate relative preference for all peers */ - for (p_cur = cur->p_head; NULL != p_cur; p_cur = p_cur->next) + /* For this client: for all preferences, except TERMINATOR */ + for (kind = GNUNET_ATS_PREFERENCE_END + 1 ; kind < GNUNET_ATS_PreferenceCount; kind ++) { - /* Calculate relative preference for specific kind */ - p_cur->f_rel[kind] = (cur->f_total[kind] + p_cur->f[kind]) / cur->f_total[kind]; - LOG (GNUNET_ERROR_TYPE_DEBUG, "Client %p: peer `%s' has relative preference for %s of %.3f\n", - cur->client, - GNUNET_i2s (&p_cur->id), - GNUNET_ATS_print_preference_type (kind), - p_cur->f_rel[kind]); - - /* Calculate peer relative preference - * Start with i = 1 to exclude terminator */ - p_cur->f_rel_total = 0; - for (i = 1; i < GNUNET_ATS_PreferenceCount; i ++) - { - p_cur->f_rel_total += p_cur->f_rel[i]; - } - p_cur->f_rel_total /= (GNUNET_ATS_PreferenceCount - 1.0); /* -1 due to terminator */ - LOG (GNUNET_ERROR_TYPE_DEBUG, "Client %p: peer `%s' has total relative preference of %.3f\n", - cur->client, - GNUNET_i2s (&p_cur->id), - p_cur->f_rel_total); + /* Recalcalculate total preference for this quality kind over all peers*/ + c_cur->f_total[kind] = 0; + for (p_cur = c_cur->p_head; NULL != p_cur; p_cur = p_cur->next) + c_cur->f_total[kind] += p_cur->f[kind]; + + LOG (GNUNET_ERROR_TYPE_DEBUG, "Client %p has total preference for %s of %.3f\n", + c_cur->client, + GNUNET_ATS_print_preference_type (kind), + c_cur->f_total[kind]); + + /* Recalcalculate relative preference for all peers */ + for (p_cur = c_cur->p_head; NULL != p_cur; p_cur = p_cur->next) + { + /* Calculate relative preference for specific kind */ + if (0.0 == c_cur->f_total[kind]) + { + /* No one has preference, so set default preference */ + p_cur->f_rel[kind] = DEFAULT_PREFERENCE; + } + else + { + p_cur->f_rel[kind] = (c_cur->f_total[kind] + p_cur->f[kind]) / c_cur->f_total[kind]; + } + LOG (GNUNET_ERROR_TYPE_DEBUG, "Client %p: peer `%s' has relative preference for %s of %.3f\n", + c_cur->client, + GNUNET_i2s (&p_cur->id), + GNUNET_ATS_print_preference_type (kind), + p_cur->f_rel[kind]); + + /* Calculate peer relative preference */ + /* Start with kind = 1 to exclude terminator */ + p_cur->f_rel_total = 0; + for (rkind = GNUNET_ATS_PREFERENCE_END + 1; rkind < GNUNET_ATS_PreferenceCount; rkind ++) + { + p_cur->f_rel_total += p_cur->f_rel[rkind]; + } + p_cur->f_rel_total /= (GNUNET_ATS_PreferenceCount - 1.0); /* -1 due to terminator */ + LOG (GNUNET_ERROR_TYPE_DEBUG, "Client %p: peer `%s' has total relative preference of %.3f\n", + c_cur->client, + GNUNET_i2s (&p_cur->id), + p_cur->f_rel_total); + } } /* Calculcate global total relative peer preference over all clients */ p_rel_global = 0.0; clients = 0; - for (cur = s->pc_head; NULL != cur; cur = cur->next) + for (c_cur = s->pc_head; NULL != c_cur; c_cur = c_cur->next) { - for (p_cur = cur->p_head; NULL != p_cur; p_cur = p_cur->next) + for (p_cur = c_cur->p_head; NULL != p_cur; p_cur = p_cur->next) if (0 == memcmp (&p_cur->id, &p->id, sizeof (p_cur->id))) break; if (NULL != p_cur) @@ -1169,16 +1208,56 @@ update_preference (struct GAS_SIMPLISTIC_Handle *s, } } +static void +update_preference (struct PreferencePeer *p, + enum GNUNET_ATS_PreferenceKind kind, + float score_f) +{ + double score = score_f; + + /* Update preference value according to type */ + switch (kind) { + case GNUNET_ATS_PREFERENCE_BANDWIDTH: + case GNUNET_ATS_PREFERENCE_LATENCY: + p->f[kind] = (p->f[kind] + score) / 2; + break; + case GNUNET_ATS_PREFERENCE_END: + break; + default: + break; + } + recalculate_preferences(p); + update_all_networks (p->s); +} + static void preference_aging (void *cls, const struct GNUNET_SCHEDULER_TaskContext *tc) { + int i; + double backup; struct PreferencePeer *p = cls; GNUNET_assert (NULL != p); + + p->aging_task = GNUNET_SCHEDULER_NO_TASK; -/* LOG (GNUNET_ERROR_TYPE_ERROR, "Aging preferences for peer `%s'\n", - GNUNET_i2s (&p->id));*/ + LOG (GNUNET_ERROR_TYPE_ERROR, "Aging preferences for peer `%s'\n", + GNUNET_i2s (&p->id)); + + for (i = 0; i < GNUNET_ATS_PreferenceCount; i++) + { + if (p->f[1] > 1.0) + { + backup = p->f[i]; + p->f[i] *= PREF_AGING_FACTOR; + LOG (GNUNET_ERROR_TYPE_ERROR, "Aged preference for peer `%s' from %.3f to %.3f\n", + GNUNET_i2s (&p->id), backup, p->f[i]); + } + } + + recalculate_preferences (p); + update_all_networks (p->s); p->aging_task = GNUNET_SCHEDULER_add_delayed (PREF_AGING_INTERVAL, &preference_aging, p); @@ -1203,8 +1282,8 @@ GAS_simplistic_address_change_preference (void *solver, { static struct GNUNET_TIME_Absolute next_update; struct GAS_SIMPLISTIC_Handle *s = solver; - struct PreferenceClient *cur; - struct PreferencePeer *p; + struct PreferenceClient *c_cur; + struct PreferencePeer *p_cur; int i; GNUNET_assert (NULL != solver); @@ -1223,72 +1302,45 @@ GAS_simplistic_address_change_preference (void *solver, return; } - /** - * Idea: - * - * We have: - * Set of clients c - * Set of peers p_i in P - * Set of preference kinds k - * A preference value f_k_p_i with an unknown range - * - * We get: - * A client specific relative preference f_p_i_rel [1..2] for all peers - * - * For every client c - * { - * For every preference kind k: - * { - * We remember for the preference f_p_i for each peer p_i. - * We have a default preference value f_p_i = 0 - * We have a sum of all preferences f_t = sum (f_p_i) - * So we can calculate a relative preference value fr_p_i: - * - * f_k_p_i_rel = (f_t + f_p_i) / f_t - * f_k_p_i_rel = [1..2], default 1.0 - * } - * f_p_i_rel = sum (f_k_p_i_rel) / #k - * } - * - **/ - /* Find preference client */ - for (cur = s->pc_head; NULL != cur; cur = cur->next) + for (c_cur = s->pc_head; NULL != c_cur; c_cur = c_cur->next) { - if (client == cur->client) + if (client == c_cur->client) break; } /* Not found: create new preference client */ - if (NULL == cur) + if (NULL == c_cur) { - cur = GNUNET_malloc (sizeof (struct PreferenceClient)); - cur->client = client; - GNUNET_CONTAINER_DLL_insert (s->pc_head, s->pc_tail, cur); + c_cur = GNUNET_malloc (sizeof (struct PreferenceClient)); + c_cur->client = client; + GNUNET_CONTAINER_DLL_insert (s->pc_head, s->pc_tail, c_cur); } /* Find entry for peer */ - for (p = cur->p_head; NULL != p; p = p->next) - if (0 == memcmp (&p->id, peer, sizeof (p->id))) + for (p_cur = c_cur->p_head; NULL != p_cur; p_cur = p_cur->next) + if (0 == memcmp (&p_cur->id, peer, sizeof (p_cur->id))) break; /* Not found: create new peer entry */ - if (NULL == p) + if (NULL == p_cur) { - p = GNUNET_malloc (sizeof (struct PreferencePeer)); - p->id = (*peer); + p_cur = GNUNET_malloc (sizeof (struct PreferencePeer)); + p_cur->s = s; + p_cur->client = c_cur; + p_cur->id = (*peer); for (i = 0; i < GNUNET_ATS_PreferenceCount; i++) { /* Default value per peer absolut preference for a quality: * No value set, so absolute preference 0 */ - p->f[i] = 0.0; + p_cur->f[i] = 0.0; /* Default value per peer relative preference for a quality: 1.0 */ - p->f_rel[i] = DEFAULT_PREFERENCE; + p_cur->f_rel[i] = DEFAULT_PREFERENCE; } - p->aging_task = GNUNET_SCHEDULER_add_delayed (PREF_AGING_INTERVAL, &preference_aging, p); - GNUNET_CONTAINER_DLL_insert (cur->p_head, cur->p_tail, p); + p_cur->aging_task = GNUNET_SCHEDULER_add_delayed (PREF_AGING_INTERVAL, &preference_aging, p_cur); + GNUNET_CONTAINER_DLL_insert (c_cur->p_head, c_cur->p_tail, p_cur); } - update_preference (s, cur, p, kind, score_f); + update_preference (p_cur, kind, score_f); /* FIXME: We should update quotas if UPDATE_INTERVAL is reached */ if (GNUNET_TIME_absolute_get().abs_value > next_update.abs_value) -- cgit v1.2.3