From d6b20377017f334596ea030852fb006960e4b0fe Mon Sep 17 00:00:00 2001 From: Matthias Wachs Date: Thu, 20 Dec 2012 14:50:25 +0000 Subject: [PATCH] preference value calculation --- .../gnunet-service-ats_addresses_simplistic.c | 130 +++++++++----- .../test_ats_simplistic_change_preference.c | 159 +++++++----------- 2 files changed, 155 insertions(+), 134 deletions(-) diff --git a/src/ats/gnunet-service-ats_addresses_simplistic.c b/src/ats/gnunet-service-ats_addresses_simplistic.c index 93d091553..573aa8388 100644 --- a/src/ats/gnunet-service-ats_addresses_simplistic.c +++ b/src/ats/gnunet-service-ats_addresses_simplistic.c @@ -160,9 +160,13 @@ struct AddressWrapper struct PreferencePeer { + struct PreferencePeer *next; + struct PreferencePeer *prev; struct GNUNET_PeerIdentity id; - float prefs[GNUNET_ATS_PreferenceCount]; + float f[GNUNET_ATS_PreferenceCount]; + float f_rel[GNUNET_ATS_PreferenceCount]; + float f_rel_total; }; struct PreferenceClient @@ -171,9 +175,10 @@ struct PreferenceClient struct PreferenceClient *next; void *client; - float prefs[GNUNET_ATS_PreferenceCount]; + float f_total[GNUNET_ATS_PreferenceCount]; - struct GNUNET_CONTAINER_MultiHashMap *peers; + struct PreferencePeer *p_head; + struct PreferencePeer *p_tail; }; @@ -252,19 +257,6 @@ GAS_simplistic_init (const struct GNUNET_CONFIGURATION_Handle *cfg, return s; } - -static int -delete_peers (void *cls, - const struct GNUNET_HashCode * key, - void *value) -{ - struct GNUNET_CONTAINER_MultiHashMap *m = cls; - struct PreferencePeer *p = (struct PreferencePeer *) value; - GNUNET_CONTAINER_multihashmap_remove (m, &p->id.hashPubKey, p); - GNUNET_free (p); - return GNUNET_OK; -} - /** * Shutdown the simplistic problem solving component * @@ -276,6 +268,8 @@ GAS_simplistic_done (void *solver) struct GAS_SIMPLISTIC_Handle *s = solver; struct PreferenceClient *pc; struct PreferenceClient *next_pc; + struct PreferencePeer *p; + struct PreferencePeer *next_p; struct AddressWrapper *cur; struct AddressWrapper *next; int c; @@ -334,8 +328,13 @@ GAS_simplistic_done (void *solver) { next_pc = pc->next; GNUNET_CONTAINER_DLL_remove (s->pc_head, s->pc_tail, pc); - GNUNET_CONTAINER_multihashmap_iterate (pc->peers, &delete_peers, pc->peers); - GNUNET_CONTAINER_multihashmap_destroy (pc->peers); + next_p = pc->p_head; + while (NULL != (p = next_p)) + { + next_p = p->next; + GNUNET_CONTAINER_DLL_remove (pc->p_head, pc->p_tail, p); + GNUNET_free (p); + } GNUNET_free (pc); } GNUNET_free (s); @@ -965,18 +964,6 @@ GAS_simplistic_get_preferred_address (void *solver, return cur; } - -static double -update_pref_value (struct PreferenceClient *cur, int kind, float score) -{ - float res = (cur->prefs[kind] + score) / 2; /* change update algorithm here */; - LOG (GNUNET_ERROR_TYPE_DEBUG, "Client %p changes preference for peer type %s from %f to %f\n", - cur->client, - GNUNET_ATS_print_preference_type (kind), - cur->prefs[kind], res); - return res; -} - /** * Changes the preferences for a peer in the problem * @@ -1002,6 +989,35 @@ GAS_simplistic_address_change_preference (void *solver, GNUNET_assert (NULL != client); GNUNET_assert (NULL != peer); + /** + * 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] + * } + * f_p_i_rel = sum (f_k_p_i_rel) / #k + * } + * + **/ + LOG (GNUNET_ERROR_TYPE_DEBUG, "Client %p changes preference for peer `%s' %s %f\n", client, GNUNET_i2s (peer), @@ -1023,34 +1039,70 @@ GAS_simplistic_address_change_preference (void *solver, { cur = GNUNET_malloc (sizeof (struct PreferenceClient)); cur->client = client; - cur->peers = GNUNET_CONTAINER_multihashmap_create (10, GNUNET_NO); GNUNET_CONTAINER_DLL_insert (s->pc_head, s->pc_tail, cur); } - p = GNUNET_CONTAINER_multihashmap_get (cur->peers, &peer->hashPubKey); + for (p = cur->p_head; NULL != p; p = p->next) + if (0 == memcmp (&p->id, peer, sizeof (p->id))) + break; + if (NULL == p) { + /* Add a new peer entry */ p = GNUNET_malloc (sizeof (struct PreferencePeer)); p->id = (*peer); for (i = 0; i < GNUNET_ATS_PreferenceCount; i++) - p->prefs[i] = 1; - GNUNET_CONTAINER_multihashmap_put (cur->peers, - &peer->hashPubKey, - p, - GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_FAST); + { + p->f[i] = 0.0; + p->f_rel[i] = 1.0; + } + GNUNET_CONTAINER_DLL_insert (cur->p_head, cur->p_tail, p); } switch (kind) { case GNUNET_ATS_PREFERENCE_BANDWIDTH: case GNUNET_ATS_PREFERENCE_LATENCY: - p->prefs[kind] = update_pref_value (cur, kind, score); + p->f[kind] = (p->f[kind] + score) / 2; break; case GNUNET_ATS_PREFERENCE_END: break; default: break; } - + /* Recalcalculate total preference for kind*/ + cur->f_total[kind] = 0; + for (p = cur->p_head; NULL != p; p = p->next) + cur->f_total[kind] += p->f[kind]; + + LOG (GNUNET_ERROR_TYPE_DEBUG, "Client %p has total preference for %s of %f\n", + cur, + GNUNET_ATS_print_preference_type (kind), + cur->f_total[kind]); + + /* Recalcalculate relative preference */ + for (p = cur->p_head; NULL != p; p = p->next) + { + /* Calculate relative preference for specific kind */ + p->f_rel[kind] = (cur->f_total[kind] + p->f[kind]) / cur->f_total[kind]; + LOG (GNUNET_ERROR_TYPE_DEBUG, "Client %p: peer `%s' has relative preference for %s of %f\n", + cur, + GNUNET_i2s (&p->id), + GNUNET_ATS_print_preference_type (kind), + p->f_rel[kind]); + + /* Calculate peer relative preference + * Start with i = 1 to exclude terminator */ + p->f_rel_total = 0; + for (i = 1; i < GNUNET_ATS_PreferenceCount; i ++) + { + p->f_rel_total += p->f_rel[i]; + } + p->f_rel_total /= GNUNET_ATS_PreferenceCount - 1.0; + LOG (GNUNET_ERROR_TYPE_DEBUG, "Client %p: peer `%s' has total relative preference of %3f\n", + cur, + GNUNET_i2s (&p->id), + p->f_rel_total); + } } /* end of gnunet-service-ats_addresses_simplistic.c */ diff --git a/src/ats/test_ats_simplistic_change_preference.c b/src/ats/test_ats_simplistic_change_preference.c index 8dc7d1ccb..e8f430ce1 100644 --- a/src/ats/test_ats_simplistic_change_preference.c +++ b/src/ats/test_ats_simplistic_change_preference.c @@ -59,23 +59,23 @@ static int ret; /** * Test address */ -static struct Test_Address test_addr; +static struct Test_Address test_addr[2]; /** * Test peer */ -static struct PeerContext p; +static struct PeerContext p[2]; /** * HELLO address */ -struct GNUNET_HELLO_Address test_hello_address; +struct GNUNET_HELLO_Address test_hello_address[2]; /** * Session */ -static void *test_session; +static void *test_session[2]; /** * Test ats info @@ -107,7 +107,7 @@ end_badly (void *cls, const struct GNUNET_SCHEDULER_TaskContext *tc) GNUNET_ATS_scheduling_done (sched_ats); if (perf_ats != NULL) GNUNET_ATS_performance_done (perf_ats); - free_test_address (&test_addr); + free_test_address (&test_addr[0]); ret = GNUNET_SYSERR; } @@ -125,7 +125,7 @@ end () perf_ats = NULL; GNUNET_ATS_scheduling_done (sched_ats); sched_ats = NULL; - free_test_address (&test_addr); + free_test_address (&test_addr[0]); } @@ -142,7 +142,7 @@ address_suggest_cb (void *cls, const struct GNUNET_HELLO_Address *address, unsigned int bw_out = ntohl(bandwidth_out.value__); if (0 == stage) { - if (GNUNET_OK == compare_addresses (address, session, &test_hello_address, test_session)) + if (GNUNET_OK == compare_addresses (address, session, &test_hello_address[0], test_session[0])) { GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Stage 0: Callback with correct address `%s'\n", GNUNET_i2s (&address->peer)); @@ -183,90 +183,17 @@ address_suggest_cb (void *cls, const struct GNUNET_HELLO_Address *address, if (1 == ret) { - GNUNET_ATS_suggest_address_cancel (sched_ats, &p.id); + GNUNET_ATS_suggest_address_cancel (sched_ats, &p[0].id); GNUNET_SCHEDULER_add_now (&end, NULL); return; } stage ++; - /* Change preference */ - GNUNET_ATS_change_preference (perf_ats, - &p.id, - GNUNET_ATS_PREFERENCE_BANDWIDTH,(double) 1000, GNUNET_ATS_PREFERENCE_END); - - /* Request address */ - GNUNET_ATS_reset_backoff (sched_ats, &p.id); - GNUNET_ATS_suggest_address (sched_ats, &p.id); + GNUNET_ATS_suggest_address_cancel (sched_ats, &p[0].id); + GNUNET_SCHEDULER_add_now (&end, NULL); return; } - if (1 == stage) - { - /* Expecting callback for address with updated quota and no callback for address[1]*/ - if (GNUNET_OK == compare_addresses (address, session, &test_hello_address, test_session)) - { - GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Stage 1: Callback with correct address `%s'\n", - GNUNET_i2s (&address->peer)); - ret = 0; - } - else - { - GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Stage 1: Callback with invalid address `%s'\n", - GNUNET_i2s (&address->peer)); - ret = 1; - } - - if (GNUNET_OK != compare_ats(atsi, ats_count, test_ats_info, test_ats_count)) - { - GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "Stage 1: Callback with incorrect ats info \n"); - ret = 1; - } - - if (bw_in > wan_quota_in) - { - GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "Suggested WAN inbound quota %u bigger than allowed quota %llu \n", - bw_in, wan_quota_in); - ret = 1; - } - else if (p.bw_in_assigned > bw_in) - { - GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "Suggested WAN inbound quota %u bigger than last quota %llu \n", - bw_in, p.bw_in_assigned); - ret = 1; - } - else - GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Suggested WAN inbound quota %u, allowed quota %llu \n", - bw_in, wan_quota_in); - - if (bw_out > wan_quota_out) - { - GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "Suggested WAN outbound quota %u bigger than allowed quota %llu \n", - bw_out, wan_quota_out); - ret = 1; - } - else if (p.bw_out_assigned > bw_out) - { - GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "Suggested WAN inbound quota %u bigger than last quota %llu \n", - bw_out, p.bw_out_assigned); - ret = 1; - } - else - GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Suggested WAN outbound quota %u, allowed quota %llu \n", - bw_out, wan_quota_out); - - if (1 == ret) - { - GNUNET_ATS_suggest_address_cancel (sched_ats, &p.id); - GNUNET_SCHEDULER_add_now (&end, NULL); - return; - } - stage ++; - - GNUNET_ATS_suggest_address_cancel (sched_ats, &p.id); - GNUNET_SCHEDULER_add_now (&end, NULL); - return; - } - } static void @@ -333,7 +260,7 @@ run (void *cls, } /* Set up peer 0 */ - if (GNUNET_SYSERR == GNUNET_CRYPTO_hash_from_string(PEERID0, &p.id.hashPubKey)) + if (GNUNET_SYSERR == GNUNET_CRYPTO_hash_from_string(PEERID0, &p[0].id.hashPubKey)) { GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "Could not setup peer!\n"); ret = GNUNET_SYSERR; @@ -341,11 +268,25 @@ run (void *cls, return; } - GNUNET_assert (0 == strcmp (PEERID0, GNUNET_i2s_full (&p.id))); + GNUNET_assert (0 == strcmp (PEERID0, GNUNET_i2s_full (&p[0].id))); GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Created peer `%s'\n", - GNUNET_i2s(&p.id)); + GNUNET_i2s(&p[0].id)); + + /* Set up peer 0 */ + if (GNUNET_SYSERR == GNUNET_CRYPTO_hash_from_string(PEERID1, &p[1].id.hashPubKey)) + { + GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "Could not setup peer!\n"); + ret = GNUNET_SYSERR; + end (); + return; + } + + GNUNET_assert (0 == strcmp (PEERID1, GNUNET_i2s_full (&p[1].id))); + + GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Created peer `%s'\n", + GNUNET_i2s(&p[1].id)); /* Prepare ATS Information */ test_ats_info[0].type = htonl (GNUNET_ATS_NETWORK_TYPE); @@ -355,15 +296,43 @@ run (void *cls, test_ats_count = 2; /* Adding address with session */ - test_session = &test_addr; - create_test_address (&test_addr, "test0", test_session, "test0", strlen ("test0") + 1); - test_hello_address.peer = p.id; - test_hello_address.transport_name = test_addr.plugin; - test_hello_address.address = test_addr.addr; - test_hello_address.address_length = test_addr.addr_len; - GNUNET_ATS_address_add (sched_ats, &test_hello_address, test_session, test_ats_info, test_ats_count); - - GNUNET_ATS_suggest_address (sched_ats, &p.id); + test_session[0] = &test_addr[0]; + create_test_address (&test_addr[0], "test0", test_session[0], "test0", strlen ("test0") + 1); + test_hello_address[0].peer = p[0].id; + test_hello_address[0].transport_name = test_addr[0].plugin; + test_hello_address[0].address = test_addr[0].addr; + test_hello_address[0].address_length = test_addr[0].addr_len; + GNUNET_ATS_address_add (sched_ats, &test_hello_address[0], test_session[0], test_ats_info, test_ats_count); + + + /* Adding address with session */ + test_session[1] = &test_addr[1]; + create_test_address (&test_addr[1], "test1", test_session[1], "test1", strlen ("test1") + 1); + test_hello_address[1].peer = p[1].id; + test_hello_address[1].transport_name = test_addr[0].plugin; + test_hello_address[1].address = test_addr[0].addr; + test_hello_address[1].address_length = test_addr[0].addr_len; + GNUNET_ATS_address_add (sched_ats, &test_hello_address[1], test_session[1], test_ats_info, test_ats_count); + + + /* Change bandwidth preference */ + GNUNET_ATS_change_preference (perf_ats, + &p[0].id, + GNUNET_ATS_PREFERENCE_BANDWIDTH,(double) 1000, GNUNET_ATS_PREFERENCE_END); + GNUNET_ATS_change_preference (perf_ats, + &p[1].id, + GNUNET_ATS_PREFERENCE_BANDWIDTH,(double) 1000, GNUNET_ATS_PREFERENCE_END); + + + /* Change latency preference */ + + GNUNET_ATS_change_preference (perf_ats, + &p[0].id, + GNUNET_ATS_PREFERENCE_LATENCY,(double) 10, GNUNET_ATS_PREFERENCE_END); + GNUNET_ATS_change_preference (perf_ats, + &p[1].id, + GNUNET_ATS_PREFERENCE_LATENCY,(double) 100, GNUNET_ATS_PREFERENCE_END); + GNUNET_ATS_suggest_address (sched_ats, &p[0].id); } -- 2.25.1