summaryrefslogtreecommitdiff
path: root/src
diff options
context:
space:
mode:
Diffstat (limited to 'src')
-rw-r--r--src/include/gnunet_testbed_service.h9
-rw-r--r--src/testbed/test_testbed_api_testbed_run_topologyscalefree.conf4
-rw-r--r--src/testbed/testbed_api_testbed.c123
-rw-r--r--src/testbed/testbed_api_topology.c87
4 files changed, 166 insertions, 57 deletions
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
@@ -52,6 +52,23 @@
/**
+ * 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
*/
struct RunContextOperation
@@ -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:
{