- implement scale free topology correctly and introduce argument to cap the number of connections to a peer in the generated topology

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:
   {