aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorSree Harsha Totakura <totakura@in.tum.de>2013-09-11 15:17:47 +0000
committerSree Harsha Totakura <totakura@in.tum.de>2013-09-11 15:17:47 +0000
commitd27d2a9ba2026c1cc4f137490d6bf40073026a05 (patch)
tree1a1cbf6c674e41677af7d5cb435f0223ecf998a3
parentd0af4b660210ffc9b00c17383becaee6178de353 (diff)
downloadgnunet-d27d2a9ba2026c1cc4f137490d6bf40073026a05.tar.gz
gnunet-d27d2a9ba2026c1cc4f137490d6bf40073026a05.zip
- implement scale free topology correctly and introduce argument to cap the number of connections to a peer in the generated topology
-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
992 GNUNET_TESTBED_TOPOLOGY_INTERNAT, 992 GNUNET_TESTBED_TOPOLOGY_INTERNAT,
993 993
994 /** 994 /**
995 * Scale free topology. No options. 995 * Scale free topology. It is generated according to the method described in
996 * "Emergence of Scaling in Random Networks." Science 286, 509-512, 1999.
997 *
998 * This options takes two arguments in the following order: an uint16_t to
999 * determine the maximum number of edges a peer is permitted to have while
1000 * generating scale free topology, a good value for this argument is 70; and
1001 * an uint8_t to determine the number of edges to be established when adding a
1002 * new node to the scale free network, a good value for this argument is 4.
996 */ 1003 */
997 GNUNET_TESTBED_TOPOLOGY_SCALE_FREE, 1004 GNUNET_TESTBED_TOPOLOGY_SCALE_FREE,
998 1005
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
4ACCEPT_FROM = 127.0.0.1; 4ACCEPT_FROM = 127.0.0.1;
5HOSTNAME = localhost 5HOSTNAME = localhost
6NEIGHBOUR_LIMIT = 100 6NEIGHBOUR_LIMIT = 100
7OVERLAY_TOPOLOGY = RING 7OVERLAY_TOPOLOGY = SCALE_FREE
8SCALE_FREE_TOPOLOGY_CAP = 70
9SCALE_FREE_TOPOLOGY_M = 5
8#PREFIX = xterm -geometry 100x85 -T peer1 -e libtool --mode=execute gdb --args 10#PREFIX = xterm -geometry 100x85 -T peer1 -e libtool --mode=execute gdb --args
9 11
10[fs] 12[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 @@
52 52
53 53
54/** 54/**
55 * Configuration section for testbed
56 */
57#define TESTBED_CONFIG_SECTION "testbed"
58
59/**
60 * Option string for the maximum number of edges a peer is permitted to have
61 * while generating scale free topology
62 */
63#define SCALE_FREE_CAP "SCALE_FREE_TOPOLOGY_CAP"
64
65/**
66 * Option string for the number of edges to be established when adding a new
67 * node to the scale free network
68 */
69#define SCALE_FREE_M "SCALE_FREE_TOPOLOGY_M"
70
71/**
55 * Context information for the operation we start 72 * Context information for the operation we start
56 */ 73 */
57struct RunContextOperation 74struct RunContextOperation
@@ -869,10 +886,13 @@ call_cc:
869 DEBUG ("%u peers started in %s\n", rc->num_peers, prof_time (rc)); 886 DEBUG ("%u peers started in %s\n", rc->num_peers, prof_time (rc));
870 if (GNUNET_TESTBED_TOPOLOGY_NONE != rc->topology) 887 if (GNUNET_TESTBED_TOPOLOGY_NONE != rc->topology)
871 { 888 {
872 if ((GNUNET_TESTBED_TOPOLOGY_ERDOS_RENYI == rc->topology) || 889 switch (rc->topology)
873 (GNUNET_TESTBED_TOPOLOGY_SMALL_WORLD_RING == rc->topology) ||
874 (GNUNET_TESTBED_TOPOLOGY_SMALL_WORLD == rc->topology))
875 { 890 {
891 case GNUNET_TESTBED_TOPOLOGY_NONE:
892 GNUNET_assert (0);
893 case GNUNET_TESTBED_TOPOLOGY_ERDOS_RENYI:
894 case GNUNET_TESTBED_TOPOLOGY_SMALL_WORLD_RING:
895 case GNUNET_TESTBED_TOPOLOGY_SMALL_WORLD:
876 rc->topology_operation = 896 rc->topology_operation =
877 GNUNET_TESTBED_overlay_configure_topology (NULL, rc->num_peers, 897 GNUNET_TESTBED_overlay_configure_topology (NULL, rc->num_peers,
878 rc->peers, &rc->num_oc, 898 rc->peers, &rc->num_oc,
@@ -881,9 +901,8 @@ call_cc:
881 rc->topology, 901 rc->topology,
882 rc->random_links, 902 rc->random_links,
883 GNUNET_TESTBED_TOPOLOGY_OPTION_END); 903 GNUNET_TESTBED_TOPOLOGY_OPTION_END);
884 } 904 break;
885 else if (GNUNET_TESTBED_TOPOLOGY_FROM_FILE == rc->topology) 905 case GNUNET_TESTBED_TOPOLOGY_FROM_FILE:
886 {
887 GNUNET_assert (NULL != rc->topo_file); 906 GNUNET_assert (NULL != rc->topo_file);
888 rc->topology_operation = 907 rc->topology_operation =
889 GNUNET_TESTBED_overlay_configure_topology (NULL, rc->num_peers, 908 GNUNET_TESTBED_overlay_configure_topology (NULL, rc->num_peers,
@@ -893,8 +912,32 @@ call_cc:
893 rc->topology, 912 rc->topology,
894 rc->topo_file, 913 rc->topo_file,
895 GNUNET_TESTBED_TOPOLOGY_OPTION_END); 914 GNUNET_TESTBED_TOPOLOGY_OPTION_END);
896 } 915 break;
897 else 916 case GNUNET_TESTBED_TOPOLOGY_SCALE_FREE:
917 {
918 unsigned long long number;
919 unsigned int cap;
920 GNUNET_assert (GNUNET_OK ==
921 GNUNET_CONFIGURATION_get_value_number (rc->cfg, TESTBED_CONFIG_SECTION,
922 SCALE_FREE_CAP,
923 &number));
924 cap = (unsigned int) number;
925 GNUNET_assert (GNUNET_OK ==
926 GNUNET_CONFIGURATION_get_value_number (rc->cfg, TESTBED_CONFIG_SECTION,
927 SCALE_FREE_M,
928 &number));
929 rc->topology_operation =
930 GNUNET_TESTBED_overlay_configure_topology (NULL, rc->num_peers,
931 rc->peers, &rc->num_oc,
932 &topology_completion_callback,
933 rc,
934 rc->topology,
935 cap, /* uint16_t */
936 (unsigned int) number, /* uint8_t */
937 GNUNET_TESTBED_TOPOLOGY_OPTION_END);
938 }
939 break;
940 default:
898 rc->topology_operation = 941 rc->topology_operation =
899 GNUNET_TESTBED_overlay_configure_topology (NULL, rc->num_peers, 942 GNUNET_TESTBED_overlay_configure_topology (NULL, rc->num_peers,
900 rc->peers, &rc->num_oc, 943 rc->peers, &rc->num_oc,
@@ -902,9 +945,10 @@ call_cc:
902 rc, 945 rc,
903 rc->topology, 946 rc->topology,
904 GNUNET_TESTBED_TOPOLOGY_OPTION_END); 947 GNUNET_TESTBED_TOPOLOGY_OPTION_END);
948 }
905 if (NULL == rc->topology_operation) 949 if (NULL == rc->topology_operation)
906 LOG (GNUNET_ERROR_TYPE_WARNING, 950 LOG (GNUNET_ERROR_TYPE_WARNING,
907 "Not generating topology. Check number of peers\n"); 951 "Not generating a topology. Check number of peers\n");
908 else 952 else
909 { 953 {
910 DEBUG ("Creating overlay topology\n"); 954 DEBUG ("Creating overlay topology\n");
@@ -1204,7 +1248,7 @@ GNUNET_TESTBED_run (const char *host_filename,
1204 char *topology; 1248 char *topology;
1205 struct CompatibilityCheckContext *hc; 1249 struct CompatibilityCheckContext *hc;
1206 struct GNUNET_TIME_Relative timeout; 1250 struct GNUNET_TIME_Relative timeout;
1207 unsigned long long random_links; 1251 unsigned long long number;
1208 unsigned int hid; 1252 unsigned int hid;
1209 unsigned int nhost; 1253 unsigned int nhost;
1210 1254
@@ -1245,12 +1289,12 @@ GNUNET_TESTBED_run (const char *host_filename,
1245 rc->state = RC_INIT; 1289 rc->state = RC_INIT;
1246 rc->topology = GNUNET_TESTBED_TOPOLOGY_NONE; 1290 rc->topology = GNUNET_TESTBED_TOPOLOGY_NONE;
1247 if (GNUNET_OK == 1291 if (GNUNET_OK ==
1248 GNUNET_CONFIGURATION_get_value_string (rc->cfg, "testbed", 1292 GNUNET_CONFIGURATION_get_value_string (rc->cfg, TESTBED_CONFIG_SECTION,
1249 "OVERLAY_TOPOLOGY", &topology)) 1293 "OVERLAY_TOPOLOGY", &topology))
1250 { 1294 {
1251 if (GNUNET_NO == GNUNET_TESTBED_topology_get_ (&rc->topology, topology)) 1295 if (GNUNET_NO == GNUNET_TESTBED_topology_get_ (&rc->topology, topology))
1252 { 1296 {
1253 GNUNET_log_config_invalid (GNUNET_ERROR_TYPE_ERROR, "testbed", 1297 GNUNET_log_config_invalid (GNUNET_ERROR_TYPE_ERROR, TESTBED_CONFIG_SECTION,
1254 "OVERLAY_TOPLOGY", 1298 "OVERLAY_TOPLOGY",
1255 _ 1299 _
1256 ("Specified topology must be supported by testbed")); 1300 ("Specified topology must be supported by testbed"));
@@ -1263,38 +1307,73 @@ GNUNET_TESTBED_run (const char *host_filename,
1263 case GNUNET_TESTBED_TOPOLOGY_SMALL_WORLD_RING: 1307 case GNUNET_TESTBED_TOPOLOGY_SMALL_WORLD_RING:
1264 case GNUNET_TESTBED_TOPOLOGY_SMALL_WORLD: 1308 case GNUNET_TESTBED_TOPOLOGY_SMALL_WORLD:
1265 if (GNUNET_OK != 1309 if (GNUNET_OK !=
1266 GNUNET_CONFIGURATION_get_value_number (rc->cfg, "testbed", 1310 GNUNET_CONFIGURATION_get_value_number (rc->cfg, TESTBED_CONFIG_SECTION,
1267 "OVERLAY_RANDOM_LINKS", 1311 "OVERLAY_RANDOM_LINKS",
1268 &random_links)) 1312 &number))
1269 { 1313 {
1270 /* OVERLAY option RANDOM & SMALL_WORLD_RING requires OVERLAY_RANDOM_LINKS 1314 /* OVERLAY option RANDOM & SMALL_WORLD_RING requires OVERLAY_RANDOM_LINKS
1271 * option to be set to the number of random links to be established */ 1315 * option to be set to the number of random links to be established */
1272 GNUNET_log_config_missing (GNUNET_ERROR_TYPE_ERROR, "testbed", 1316 GNUNET_log_config_missing (GNUNET_ERROR_TYPE_ERROR, TESTBED_CONFIG_SECTION,
1273 "OVERLAY_RANDOM_LINKS"); 1317 "OVERLAY_RANDOM_LINKS");
1274 goto error_cleanup; 1318 goto error_cleanup;
1275 } 1319 }
1276 if (random_links > UINT32_MAX) 1320 if (number > UINT32_MAX)
1277 { 1321 {
1278 GNUNET_break (0); /* Too big number */ 1322 GNUNET_break (0); /* Too big number */
1279 goto error_cleanup; 1323 goto error_cleanup;
1280 } 1324 }
1281 rc->random_links = (unsigned int) random_links; 1325 rc->random_links = (unsigned int) number;
1282 break; 1326 break;
1283 case GNUNET_TESTBED_TOPOLOGY_FROM_FILE: 1327 case GNUNET_TESTBED_TOPOLOGY_FROM_FILE:
1284 if (GNUNET_OK != 1328 if (GNUNET_OK !=
1285 GNUNET_CONFIGURATION_get_value_string (rc->cfg, "testbed", 1329 GNUNET_CONFIGURATION_get_value_string (rc->cfg, TESTBED_CONFIG_SECTION,
1286 "OVERLAY_TOPOLOGY_FILE", 1330 "OVERLAY_TOPOLOGY_FILE",
1287 &rc->topo_file)) 1331 &rc->topo_file))
1288 { 1332 {
1289 GNUNET_log_config_missing (GNUNET_ERROR_TYPE_ERROR, "testbed", 1333 GNUNET_log_config_missing (GNUNET_ERROR_TYPE_ERROR, TESTBED_CONFIG_SECTION,
1290 "OVERLAY_TOPOLOGY_FILE"); 1334 "OVERLAY_TOPOLOGY_FILE");
1291 goto error_cleanup; 1335 goto error_cleanup;
1292 } 1336 }
1293 break; 1337 goto warn_ignore;
1338 case GNUNET_TESTBED_TOPOLOGY_SCALE_FREE:
1339 if (GNUNET_OK !=
1340 GNUNET_CONFIGURATION_get_value_number (rc->cfg, TESTBED_CONFIG_SECTION,
1341 SCALE_FREE_CAP, &number))
1342 {
1343 GNUNET_log_config_missing (GNUNET_ERROR_TYPE_ERROR, TESTBED_CONFIG_SECTION,
1344 SCALE_FREE_CAP);
1345 goto error_cleanup;
1346 }
1347 if (UINT16_MAX < number)
1348 {
1349 LOG (GNUNET_ERROR_TYPE_ERROR,
1350 _("Maximum number of edges a peer can have in a scale free topology"
1351 " cannot be more than %u. Given `%s = %llu'"), UINT16_MAX,
1352 SCALE_FREE_CAP, number);
1353 goto error_cleanup;
1354 }
1355 if (GNUNET_OK !=
1356 GNUNET_CONFIGURATION_get_value_number (rc->cfg, TESTBED_CONFIG_SECTION,
1357 SCALE_FREE_M, &number))
1358 {
1359 GNUNET_log_config_missing (GNUNET_ERROR_TYPE_ERROR, TESTBED_CONFIG_SECTION,
1360 SCALE_FREE_M);
1361 goto error_cleanup;
1362 }
1363 if (UINT8_MAX < number)
1364 {
1365 LOG (GNUNET_ERROR_TYPE_ERROR,
1366 _("The number of edges that can established when adding a new node"
1367 " to scale free topology cannot be more than %u. Given `%s = %llu'"),
1368 UINT8_MAX, SCALE_FREE_M, number);
1369 goto error_cleanup;
1370 }
1371 goto warn_ignore;
1294 default: 1372 default:
1373 warn_ignore:
1295 /* Warn if OVERLAY_RANDOM_LINKS is present that it will be ignored */ 1374 /* Warn if OVERLAY_RANDOM_LINKS is present that it will be ignored */
1296 if (GNUNET_YES == 1375 if (GNUNET_YES ==
1297 GNUNET_CONFIGURATION_have_value (rc->cfg, "testbed", 1376 GNUNET_CONFIGURATION_have_value (rc->cfg, TESTBED_CONFIG_SECTION,
1298 "OVERLAY_RANDOM_LINKS")) 1377 "OVERLAY_RANDOM_LINKS"))
1299 LOG (GNUNET_ERROR_TYPE_WARNING, 1378 LOG (GNUNET_ERROR_TYPE_WARNING,
1300 "Ignoring value of `OVERLAY_RANDOM_LINKS' in given configuration\n"); 1379 "Ignoring value of `OVERLAY_RANDOM_LINKS' in given configuration\n");
@@ -1330,7 +1409,7 @@ GNUNET_TESTBED_run (const char *host_filename,
1330 rc->cproc = 1409 rc->cproc =
1331 GNUNET_TESTBED_controller_start ("127.0.0.1", rc->h, 1410 GNUNET_TESTBED_controller_start ("127.0.0.1", rc->h,
1332 &controller_status_cb, rc); 1411 &controller_status_cb, rc);
1333 if (GNUNET_OK != GNUNET_CONFIGURATION_get_value_time (cfg, "TESTBED", 1412 if (GNUNET_OK != GNUNET_CONFIGURATION_get_value_time (cfg, TESTBED_CONFIG_SECTION,
1334 "SETUP_TIMEOUT", 1413 "SETUP_TIMEOUT",
1335 &timeout)) 1414 &timeout))
1336 { 1415 {
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)
589 * "Emergence of Scaling in Random Networks." Science 286, 509-512, 1999. 589 * "Emergence of Scaling in Random Networks." Science 286, 509-512, 1999.
590 * 590 *
591 * @param tc the topology context 591 * @param tc the topology context
592 * @param cap maximum allowed node degree
593 * @param m number of edges to establish for a new node when it is added to the
594 * network
592 */ 595 */
593static void 596static void
594gen_scale_free (struct TopologyContext *tc) 597gen_scale_free (struct TopologyContext *tc, uint16_t cap, uint8_t m)
595{ 598{
596 double random;
597 double probability;
598 unsigned int cnt; 599 unsigned int cnt;
599 unsigned int previous_connections; 600 unsigned int cnt2;
600 unsigned int i; 601 unsigned int peer;
601 uint16_t *popularity; 602 unsigned int *etab;
602 603 unsigned int *used;
603 popularity = GNUNET_malloc (sizeof (uint16_t) * tc->num_peers); 604 unsigned int links;
604 /* Initially connect peer 1 to peer 0 */ 605 unsigned int random;
605 tc->link_array_size = 1; 606
606 tc->link_array = GNUNET_malloc (sizeof (struct OverlayLink)); 607 links = 0;
607 make_link (&tc->link_array[0], 0, 1, tc); 608 tc->link_array_size = tc->num_peers * m;
608 popularity[0]++; /* increase popularity of 0 as 1 connected to it */ 609 tc->link_array = GNUNET_malloc_large (sizeof (struct OverlayLink) *
609 for (cnt = 2; cnt < tc->num_peers; cnt++) 610 tc->link_array_size);
611 etab = GNUNET_malloc_large (sizeof (unsigned int) * 2 * tc->link_array_size);
612
613 used = GNUNET_malloc (sizeof (unsigned int) * m);
614
615 make_link (&tc->link_array[0], 0, 1, tc); /* Initially connect peer 1 to peer 0 */
616 etab[2 * links] = 0;
617 etab[(2 * links) + 1] = 1;
618 links = 1;
619 for (peer = 2; peer < tc->num_peers; peer++)
610 { 620 {
611 previous_connections = tc->link_array_size; 621 for (cnt = 0; cnt < GNUNET_MIN (peer, m); cnt++)
612 for (i = 0; i < cnt; i++)
613 { 622 {
614 probability = ((double) popularity[i]) / ((double) previous_connections); 623 redo:
615 random = 624 random = GNUNET_CRYPTO_random_u64 (GNUNET_CRYPTO_QUALITY_WEAK, (2 * links)
616 ((double) 625 + cnt);
617 GNUNET_CRYPTO_random_u64 (GNUNET_CRYPTO_QUALITY_WEAK, 626 for (cnt2 = 0; cnt2 < cnt; cnt2++)
618 UINT64_MAX)) / ((double) UINT64_MAX); 627 if (etab[random] == used[cnt2])
619 if (random < probability) 628 goto redo;
620 { 629 make_link (&tc->link_array[links + cnt], etab[random], peer, tc);
621 tc->link_array_size++; 630 etab[(2 * links) + cnt] = etab[random];
622 tc->link_array = 631 used[cnt] = etab[random];
623 GNUNET_realloc (tc->link_array,
624 (sizeof (struct OverlayLink) *
625 tc->link_array_size));
626 make_link (&tc->link_array[tc->link_array_size - 1], i, cnt, tc);
627 popularity[i]++;
628 }
629 } 632 }
633 for (cnt = 0; cnt < GNUNET_MIN (peer, m); cnt++)
634 {
635 etab[(2 * links) + cnt + 1] = peer;
636 }
637 links += GNUNET_MIN (peer, m);
630 } 638 }
631 GNUNET_free (popularity); 639 GNUNET_free (etab);
640 GNUNET_free (used);
641 GNUNET_assert (links <= tc->link_array_size);
642 tc->link_array_size = links;
643 tc->link_array =
644 GNUNET_realloc (tc->link_array,
645 sizeof (struct OverlayLink) * tc->link_array_size);
632} 646}
633 647
634 648
@@ -933,7 +947,14 @@ GNUNET_TESTBED_overlay_configure_topology_va (void *op_cls,
933 947
934 break; 948 break;
935 case GNUNET_TESTBED_TOPOLOGY_SCALE_FREE: 949 case GNUNET_TESTBED_TOPOLOGY_SCALE_FREE:
936 gen_scale_free (tc); 950 {
951 uint16_t cap;
952 uint8_t m;
953
954 cap = (uint16_t) va_arg (va, unsigned int);
955 m = (uint8_t) va_arg (va, unsigned int);
956 gen_scale_free (tc, cap, m);
957 }
937 break; 958 break;
938 case GNUNET_TESTBED_TOPOLOGY_FROM_FILE: 959 case GNUNET_TESTBED_TOPOLOGY_FROM_FILE:
939 { 960 {