[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[GNUnet-SVN] r29211 - in gnunet/src: include testbed
|
From: |
gnunet |
|
Subject: |
[GNUnet-SVN] r29211 - in gnunet/src: include testbed |
|
Date: |
Wed, 11 Sep 2013 17:17:47 +0200 |
Author: harsha
Date: 2013-09-11 17:17:47 +0200 (Wed, 11 Sep 2013)
New Revision: 29211
Modified:
gnunet/src/include/gnunet_testbed_service.h
gnunet/src/testbed/test_testbed_api_testbed_run_topologyscalefree.conf
gnunet/src/testbed/testbed_api_testbed.c
gnunet/src/testbed/testbed_api_topology.c
Log:
- implement scale free topology correctly and introduce argument to cap the
number of connections to a peer in the generated topology
Modified: gnunet/src/include/gnunet_testbed_service.h
===================================================================
--- gnunet/src/include/gnunet_testbed_service.h 2013-09-11 15:16:18 UTC (rev
29210)
+++ gnunet/src/include/gnunet_testbed_service.h 2013-09-11 15:17:47 UTC (rev
29211)
@@ -992,7 +992,14 @@
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,
Modified: gnunet/src/testbed/test_testbed_api_testbed_run_topologyscalefree.conf
===================================================================
--- gnunet/src/testbed/test_testbed_api_testbed_run_topologyscalefree.conf
2013-09-11 15:16:18 UTC (rev 29210)
+++ gnunet/src/testbed/test_testbed_api_testbed_run_topologyscalefree.conf
2013-09-11 15:17:47 UTC (rev 29211)
@@ -4,7 +4,9 @@
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]
Modified: gnunet/src/testbed/testbed_api_testbed.c
===================================================================
--- gnunet/src/testbed/testbed_api_testbed.c 2013-09-11 15:16:18 UTC (rev
29210)
+++ gnunet/src/testbed/testbed_api_testbed.c 2013-09-11 15:17:47 UTC (rev
29211)
@@ -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 @@
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 @@
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 @@
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 @@
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 @@
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 @@
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 @@
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 @@
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))
{
Modified: gnunet/src/testbed/testbed_api_topology.c
===================================================================
--- gnunet/src/testbed/testbed_api_topology.c 2013-09-11 15:16:18 UTC (rev
29210)
+++ gnunet/src/testbed/testbed_api_topology.c 2013-09-11 15:17:47 UTC (rev
29211)
@@ -589,46 +589,60 @@
* "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;
+ unsigned int cnt2;
+ unsigned int peer;
+ unsigned int *etab;
+ unsigned int *used;
+ unsigned int links;
+ unsigned int random;
- 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++)
+ 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 @@
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:
{
| [Prev in Thread] |
Current Thread |
[Next in Thread] |
- [GNUnet-SVN] r29211 - in gnunet/src: include testbed,
gnunet <=