From d27d2a9ba2026c1cc4f137490d6bf40073026a05 Mon Sep 17 00:00:00 2001 From: Sree Harsha Totakura Date: Wed, 11 Sep 2013 15:17:47 +0000 Subject: - implement scale free topology correctly and introduce argument to cap the number of connections to a peer in the generated topology --- src/include/gnunet_testbed_service.h | 9 +- ..._testbed_api_testbed_run_topologyscalefree.conf | 4 +- src/testbed/testbed_api_testbed.c | 123 +++++++++++++++++---- src/testbed/testbed_api_topology.c | 87 +++++++++------ 4 files changed, 166 insertions(+), 57 deletions(-) (limited to 'src') diff --git a/src/include/gnunet_testbed_service.h b/src/include/gnunet_testbed_service.h index 48d3440ab..33cf464dc 100644 --- a/src/include/gnunet_testbed_service.h +++ b/src/include/gnunet_testbed_service.h @@ -992,7 +992,14 @@ enum GNUNET_TESTBED_TopologyOption GNUNET_TESTBED_TOPOLOGY_INTERNAT, /** - * Scale free topology. No options. + * Scale free topology. It is generated according to the method described in + * "Emergence of Scaling in Random Networks." Science 286, 509-512, 1999. + * + * This options takes two arguments in the following order: an uint16_t to + * determine the maximum number of edges a peer is permitted to have while + * generating scale free topology, a good value for this argument is 70; and + * an uint8_t to determine the number of edges to be established when adding a + * new node to the scale free network, a good value for this argument is 4. */ GNUNET_TESTBED_TOPOLOGY_SCALE_FREE, diff --git a/src/testbed/test_testbed_api_testbed_run_topologyscalefree.conf b/src/testbed/test_testbed_api_testbed_run_topologyscalefree.conf index b6a1e285a..cdd89f293 100644 --- a/src/testbed/test_testbed_api_testbed_run_topologyscalefree.conf +++ b/src/testbed/test_testbed_api_testbed_run_topologyscalefree.conf @@ -4,7 +4,9 @@ PORT = 12113 ACCEPT_FROM = 127.0.0.1; HOSTNAME = localhost NEIGHBOUR_LIMIT = 100 -OVERLAY_TOPOLOGY = RING +OVERLAY_TOPOLOGY = SCALE_FREE +SCALE_FREE_TOPOLOGY_CAP = 70 +SCALE_FREE_TOPOLOGY_M = 5 #PREFIX = xterm -geometry 100x85 -T peer1 -e libtool --mode=execute gdb --args [fs] diff --git a/src/testbed/testbed_api_testbed.c b/src/testbed/testbed_api_testbed.c index 25054bf1d..2f5fc70e8 100644 --- a/src/testbed/testbed_api_testbed.c +++ b/src/testbed/testbed_api_testbed.c @@ -51,6 +51,23 @@ #define DEFAULT_SETUP_TIMEOUT 300 +/** + * Configuration section for testbed + */ +#define TESTBED_CONFIG_SECTION "testbed" + +/** + * Option string for the maximum number of edges a peer is permitted to have + * while generating scale free topology + */ +#define SCALE_FREE_CAP "SCALE_FREE_TOPOLOGY_CAP" + +/** + * Option string for the number of edges to be established when adding a new + * node to the scale free network + */ +#define SCALE_FREE_M "SCALE_FREE_TOPOLOGY_M" + /** * Context information for the operation we start */ @@ -869,10 +886,13 @@ call_cc: DEBUG ("%u peers started in %s\n", rc->num_peers, prof_time (rc)); if (GNUNET_TESTBED_TOPOLOGY_NONE != rc->topology) { - if ((GNUNET_TESTBED_TOPOLOGY_ERDOS_RENYI == rc->topology) || - (GNUNET_TESTBED_TOPOLOGY_SMALL_WORLD_RING == rc->topology) || - (GNUNET_TESTBED_TOPOLOGY_SMALL_WORLD == rc->topology)) + switch (rc->topology) { + case GNUNET_TESTBED_TOPOLOGY_NONE: + GNUNET_assert (0); + case GNUNET_TESTBED_TOPOLOGY_ERDOS_RENYI: + case GNUNET_TESTBED_TOPOLOGY_SMALL_WORLD_RING: + case GNUNET_TESTBED_TOPOLOGY_SMALL_WORLD: rc->topology_operation = GNUNET_TESTBED_overlay_configure_topology (NULL, rc->num_peers, rc->peers, &rc->num_oc, @@ -881,9 +901,8 @@ call_cc: rc->topology, rc->random_links, GNUNET_TESTBED_TOPOLOGY_OPTION_END); - } - else if (GNUNET_TESTBED_TOPOLOGY_FROM_FILE == rc->topology) - { + break; + case GNUNET_TESTBED_TOPOLOGY_FROM_FILE: GNUNET_assert (NULL != rc->topo_file); rc->topology_operation = GNUNET_TESTBED_overlay_configure_topology (NULL, rc->num_peers, @@ -893,8 +912,32 @@ call_cc: rc->topology, rc->topo_file, GNUNET_TESTBED_TOPOLOGY_OPTION_END); - } - else + break; + case GNUNET_TESTBED_TOPOLOGY_SCALE_FREE: + { + unsigned long long number; + unsigned int cap; + GNUNET_assert (GNUNET_OK == + GNUNET_CONFIGURATION_get_value_number (rc->cfg, TESTBED_CONFIG_SECTION, + SCALE_FREE_CAP, + &number)); + cap = (unsigned int) number; + GNUNET_assert (GNUNET_OK == + GNUNET_CONFIGURATION_get_value_number (rc->cfg, TESTBED_CONFIG_SECTION, + SCALE_FREE_M, + &number)); + rc->topology_operation = + GNUNET_TESTBED_overlay_configure_topology (NULL, rc->num_peers, + rc->peers, &rc->num_oc, + &topology_completion_callback, + rc, + rc->topology, + cap, /* uint16_t */ + (unsigned int) number, /* uint8_t */ + GNUNET_TESTBED_TOPOLOGY_OPTION_END); + } + break; + default: rc->topology_operation = GNUNET_TESTBED_overlay_configure_topology (NULL, rc->num_peers, rc->peers, &rc->num_oc, @@ -902,9 +945,10 @@ call_cc: rc, rc->topology, GNUNET_TESTBED_TOPOLOGY_OPTION_END); + } if (NULL == rc->topology_operation) LOG (GNUNET_ERROR_TYPE_WARNING, - "Not generating topology. Check number of peers\n"); + "Not generating a topology. Check number of peers\n"); else { DEBUG ("Creating overlay topology\n"); @@ -1204,7 +1248,7 @@ GNUNET_TESTBED_run (const char *host_filename, char *topology; struct CompatibilityCheckContext *hc; struct GNUNET_TIME_Relative timeout; - unsigned long long random_links; + unsigned long long number; unsigned int hid; unsigned int nhost; @@ -1245,12 +1289,12 @@ GNUNET_TESTBED_run (const char *host_filename, rc->state = RC_INIT; rc->topology = GNUNET_TESTBED_TOPOLOGY_NONE; if (GNUNET_OK == - GNUNET_CONFIGURATION_get_value_string (rc->cfg, "testbed", + GNUNET_CONFIGURATION_get_value_string (rc->cfg, TESTBED_CONFIG_SECTION, "OVERLAY_TOPOLOGY", &topology)) { if (GNUNET_NO == GNUNET_TESTBED_topology_get_ (&rc->topology, topology)) { - GNUNET_log_config_invalid (GNUNET_ERROR_TYPE_ERROR, "testbed", + GNUNET_log_config_invalid (GNUNET_ERROR_TYPE_ERROR, TESTBED_CONFIG_SECTION, "OVERLAY_TOPLOGY", _ ("Specified topology must be supported by testbed")); @@ -1263,38 +1307,73 @@ GNUNET_TESTBED_run (const char *host_filename, case GNUNET_TESTBED_TOPOLOGY_SMALL_WORLD_RING: case GNUNET_TESTBED_TOPOLOGY_SMALL_WORLD: if (GNUNET_OK != - GNUNET_CONFIGURATION_get_value_number (rc->cfg, "testbed", + GNUNET_CONFIGURATION_get_value_number (rc->cfg, TESTBED_CONFIG_SECTION, "OVERLAY_RANDOM_LINKS", - &random_links)) + &number)) { /* OVERLAY option RANDOM & SMALL_WORLD_RING requires OVERLAY_RANDOM_LINKS * option to be set to the number of random links to be established */ - GNUNET_log_config_missing (GNUNET_ERROR_TYPE_ERROR, "testbed", + GNUNET_log_config_missing (GNUNET_ERROR_TYPE_ERROR, TESTBED_CONFIG_SECTION, "OVERLAY_RANDOM_LINKS"); goto error_cleanup; } - if (random_links > UINT32_MAX) + if (number > UINT32_MAX) { GNUNET_break (0); /* Too big number */ goto error_cleanup; } - rc->random_links = (unsigned int) random_links; + rc->random_links = (unsigned int) number; break; case GNUNET_TESTBED_TOPOLOGY_FROM_FILE: if (GNUNET_OK != - GNUNET_CONFIGURATION_get_value_string (rc->cfg, "testbed", + GNUNET_CONFIGURATION_get_value_string (rc->cfg, TESTBED_CONFIG_SECTION, "OVERLAY_TOPOLOGY_FILE", &rc->topo_file)) { - GNUNET_log_config_missing (GNUNET_ERROR_TYPE_ERROR, "testbed", + GNUNET_log_config_missing (GNUNET_ERROR_TYPE_ERROR, TESTBED_CONFIG_SECTION, "OVERLAY_TOPOLOGY_FILE"); goto error_cleanup; } - break; + goto warn_ignore; + case GNUNET_TESTBED_TOPOLOGY_SCALE_FREE: + if (GNUNET_OK != + GNUNET_CONFIGURATION_get_value_number (rc->cfg, TESTBED_CONFIG_SECTION, + SCALE_FREE_CAP, &number)) + { + GNUNET_log_config_missing (GNUNET_ERROR_TYPE_ERROR, TESTBED_CONFIG_SECTION, + SCALE_FREE_CAP); + goto error_cleanup; + } + if (UINT16_MAX < number) + { + LOG (GNUNET_ERROR_TYPE_ERROR, + _("Maximum number of edges a peer can have in a scale free topology" + " cannot be more than %u. Given `%s = %llu'"), UINT16_MAX, + SCALE_FREE_CAP, number); + goto error_cleanup; + } + if (GNUNET_OK != + GNUNET_CONFIGURATION_get_value_number (rc->cfg, TESTBED_CONFIG_SECTION, + SCALE_FREE_M, &number)) + { + GNUNET_log_config_missing (GNUNET_ERROR_TYPE_ERROR, TESTBED_CONFIG_SECTION, + SCALE_FREE_M); + goto error_cleanup; + } + if (UINT8_MAX < number) + { + LOG (GNUNET_ERROR_TYPE_ERROR, + _("The number of edges that can established when adding a new node" + " to scale free topology cannot be more than %u. Given `%s = %llu'"), + UINT8_MAX, SCALE_FREE_M, number); + goto error_cleanup; + } + goto warn_ignore; default: + warn_ignore: /* Warn if OVERLAY_RANDOM_LINKS is present that it will be ignored */ if (GNUNET_YES == - GNUNET_CONFIGURATION_have_value (rc->cfg, "testbed", + GNUNET_CONFIGURATION_have_value (rc->cfg, TESTBED_CONFIG_SECTION, "OVERLAY_RANDOM_LINKS")) LOG (GNUNET_ERROR_TYPE_WARNING, "Ignoring value of `OVERLAY_RANDOM_LINKS' in given configuration\n"); @@ -1330,7 +1409,7 @@ GNUNET_TESTBED_run (const char *host_filename, rc->cproc = GNUNET_TESTBED_controller_start ("127.0.0.1", rc->h, &controller_status_cb, rc); - if (GNUNET_OK != GNUNET_CONFIGURATION_get_value_time (cfg, "TESTBED", + if (GNUNET_OK != GNUNET_CONFIGURATION_get_value_time (cfg, TESTBED_CONFIG_SECTION, "SETUP_TIMEOUT", &timeout)) { diff --git a/src/testbed/testbed_api_topology.c b/src/testbed/testbed_api_topology.c index defaad2a1..374e42ad4 100644 --- a/src/testbed/testbed_api_topology.c +++ b/src/testbed/testbed_api_topology.c @@ -589,46 +589,60 @@ gen_topo_random (struct TopologyContext *tc, unsigned int links, int append) * "Emergence of Scaling in Random Networks." Science 286, 509-512, 1999. * * @param tc the topology context + * @param cap maximum allowed node degree + * @param m number of edges to establish for a new node when it is added to the + * network */ static void -gen_scale_free (struct TopologyContext *tc) +gen_scale_free (struct TopologyContext *tc, uint16_t cap, uint8_t m) { - double random; - double probability; unsigned int cnt; - unsigned int previous_connections; - unsigned int i; - uint16_t *popularity; - - popularity = GNUNET_malloc (sizeof (uint16_t) * tc->num_peers); - /* Initially connect peer 1 to peer 0 */ - tc->link_array_size = 1; - tc->link_array = GNUNET_malloc (sizeof (struct OverlayLink)); - make_link (&tc->link_array[0], 0, 1, tc); - popularity[0]++; /* increase popularity of 0 as 1 connected to it */ - for (cnt = 2; cnt < tc->num_peers; cnt++) + unsigned int cnt2; + unsigned int peer; + unsigned int *etab; + unsigned int *used; + unsigned int links; + unsigned int random; + + links = 0; + tc->link_array_size = tc->num_peers * m; + tc->link_array = GNUNET_malloc_large (sizeof (struct OverlayLink) * + tc->link_array_size); + etab = GNUNET_malloc_large (sizeof (unsigned int) * 2 * tc->link_array_size); + + used = GNUNET_malloc (sizeof (unsigned int) * m); + + make_link (&tc->link_array[0], 0, 1, tc); /* Initially connect peer 1 to peer 0 */ + etab[2 * links] = 0; + etab[(2 * links) + 1] = 1; + links = 1; + for (peer = 2; peer < tc->num_peers; peer++) { - previous_connections = tc->link_array_size; - for (i = 0; i < cnt; i++) + for (cnt = 0; cnt < GNUNET_MIN (peer, m); cnt++) { - probability = ((double) popularity[i]) / ((double) previous_connections); - random = - ((double) - GNUNET_CRYPTO_random_u64 (GNUNET_CRYPTO_QUALITY_WEAK, - UINT64_MAX)) / ((double) UINT64_MAX); - if (random < probability) - { - tc->link_array_size++; - tc->link_array = - GNUNET_realloc (tc->link_array, - (sizeof (struct OverlayLink) * - tc->link_array_size)); - make_link (&tc->link_array[tc->link_array_size - 1], i, cnt, tc); - popularity[i]++; - } + redo: + random = GNUNET_CRYPTO_random_u64 (GNUNET_CRYPTO_QUALITY_WEAK, (2 * links) + + cnt); + for (cnt2 = 0; cnt2 < cnt; cnt2++) + if (etab[random] == used[cnt2]) + goto redo; + make_link (&tc->link_array[links + cnt], etab[random], peer, tc); + etab[(2 * links) + cnt] = etab[random]; + used[cnt] = etab[random]; } + for (cnt = 0; cnt < GNUNET_MIN (peer, m); cnt++) + { + etab[(2 * links) + cnt + 1] = peer; + } + links += GNUNET_MIN (peer, m); } - GNUNET_free (popularity); + GNUNET_free (etab); + GNUNET_free (used); + GNUNET_assert (links <= tc->link_array_size); + tc->link_array_size = links; + tc->link_array = + GNUNET_realloc (tc->link_array, + sizeof (struct OverlayLink) * tc->link_array_size); } @@ -933,7 +947,14 @@ GNUNET_TESTBED_overlay_configure_topology_va (void *op_cls, break; case GNUNET_TESTBED_TOPOLOGY_SCALE_FREE: - gen_scale_free (tc); + { + uint16_t cap; + uint8_t m; + + cap = (uint16_t) va_arg (va, unsigned int); + m = (uint8_t) va_arg (va, unsigned int); + gen_scale_free (tc, cap, m); + } break; case GNUNET_TESTBED_TOPOLOGY_FROM_FILE: { -- cgit v1.2.3