implementing small world ring topology

5 files changed, 239 insertions, 67 deletions

diff --git a/src/testbed/Makefile.am b/src/testbed/Makefile.am
index 9eee7cf4e..a48fd138f 100644
--- a/src/testbed/Makefile.am
+++ b/src/testbed/Makefile.am
@@ -94,7 +94,8 @@ check_PROGRAMS = \
  test_testbed_api_testbed_run_topologyrandom \
  test_testbed_api_testbed_run_topologyline \
  test_testbed_api_testbed_run_topologyclique \
- test_testbed_api_testbed_run_topologyring
+ test_testbed_api_testbed_run_topologyring \
+ test_testbed_api_testbed_run_topologysmallworldring
 
 if ENABLE_TEST_RUN
  TESTS = \
@@ -112,7 +113,8 @@ if ENABLE_TEST_RUN
  test_testbed_api_testbed_run_topologyrandom \
  test_testbed_api_testbed_run_topologyline \
  test_testbed_api_testbed_run_topologyclique \
- test_testbed_api_testbed_run_topologyring
+ test_testbed_api_testbed_run_topologyring \
+ test_testbed_api_testbed_run_topologysmallworldring
 endif
 
 test_testbed_api_hosts_SOURCES = \
@@ -210,10 +212,17 @@ test_testbed_api_testbed_run_topologyring_LDADD = \
  $(top_builddir)/src/util/libgnunetutil.la \
  libgnunettestbed.la
 
+test_testbed_api_testbed_run_topologysmallworldring_SOURCES = \
+ test_testbed_api_testbed_run.c
+test_testbed_api_testbed_run_topologysmallworldring_LDADD = \
+ $(top_builddir)/src/util/libgnunetutil.la \
+ libgnunettestbed.la
+
 EXTRA_DIST = \
   test_testbed_api.conf \
   test_testbed_api_testbed_run_topologyring.conf \
   test_testbed_api_testbed_run_topologyclique.conf \
   test_testbed_api_testbed_run_topologyline.conf \
   test_testbed_api_testbed_run_topologyrandom.conf \
+  test_testbed_api_testbed_run_topologysmallworldring.conf \
   sample_hosts.txt
\ No newline at end of file
diff --git a/src/testbed/test_testbed_api_testbed_run_topologyrandom.conf b/src/testbed/test_testbed_api_testbed_run_topologyrandom.conf
index 84f338c3e..cd2913832 100644
--- a/src/testbed/test_testbed_api_testbed_run_topologyrandom.conf
+++ b/src/testbed/test_testbed_api_testbed_run_topologyrandom.conf
@@ -3,7 +3,6 @@ AUTOSTART = NO
 PORT = 12113
 ACCEPT_FROM = 127.0.0.1;
 HOSTNAME = localhost
-NEIGHBOUR_LIMIT = 100
 MAX_PARALLEL_OVERLAY_CONNECT_OPERATIONS = 10
 OVERLAY_TOPOLOGY = RANDOM
 OVERLAY_RANDOM_LINKS = 5
diff --git a/src/testbed/test_testbed_api_testbed_run_topologysmallworldring.conf b/src/testbed/test_testbed_api_testbed_run_topologysmallworldring.conf
new file mode 100644
index 000000000..e16c30832
--- /dev/null
+++ b/src/testbed/test_testbed_api_testbed_run_topologysmallworldring.conf
@@ -0,0 +1,80 @@
+[testbed]
+AUTOSTART = NO
+PORT = 12113
+ACCEPT_FROM = 127.0.0.1;
+HOSTNAME = localhost
+MAX_PARALLEL_OVERLAY_CONNECT_OPERATIONS = 10
+OVERLAY_TOPOLOGY = SMALL_WORLD_RING
+OVERLAY_RANDOM_LINKS = 5
+#PREFIX = xterm -geometry 100x85 -T peer1 -e libtool --mode=execute gdb --args
+
+[fs]
+AUTOSTART = NO
+
+[resolver]
+AUTOSTART = NO
+
+[mesh]
+AUTOSTART = NO
+
+[dht]
+AUTOSTART = NO
+
+[block]
+plugins = dht test
+
+[dhtcache]
+QUOTA = 1 MB
+DATABASE = sqlite
+
+[transport]
+PLUGINS = tcp
+ACCEPT_FROM6 = ::1;
+ACCEPT_FROM = 127.0.0.1;
+NEIGHBOUR_LIMIT = 50
+PORT = 12365
+
+[ats]
+WAN_QUOTA_OUT = 3932160
+WAN_QUOTA_IN = 3932160
+
+[core]
+PORT = 12092
+AUTOSTART = YES
+
+[arm]
+DEFAULTSERVICES = core transport
+PORT = 12366
+
+[transport-tcp]
+TIMEOUT = 300 s
+PORT = 12368
+
+[TESTING]
+NUM_PEERS = 5
+WEAKRANDOM = YES
+HOSTKEYSFILE = ../../contrib/testing_hostkeys.dat
+MAX_CONCURRENT_SSH = 10
+USE_PROGRESSBARS = YES
+PEERGROUP_TIMEOUT = 2400 s
+
+[gnunetd]
+HOSTKEY = $SERVICEHOME/.hostkey
+
+[PATHS]
+SERVICEHOME = /tmp/test-testbed/
+
+[dns]
+AUTOSTART = NO
+
+[nse]
+AUTOSTART = NO
+
+[vpn]
+AUTOSTART = NO
+
+[nat]
+RETURN_LOCAL_ADDRESSES = YES
+
+[gns-helper-service-w32]
+AUTOSTART = NO
\ No newline at end of file
diff --git a/src/testbed/testbed_api_testbed.c b/src/testbed/testbed_api_testbed.c
index 6da0b1075..d597d47a6 100644
--- a/src/testbed/testbed_api_testbed.c
+++ b/src/testbed/testbed_api_testbed.c
@@ -423,15 +423,19 @@ call_cc:
   if (rc->peer_count < rc->num_peers)
     return;
   LOG (GNUNET_ERROR_TYPE_DEBUG, "Peers started successfully\n");
-  if (GNUNET_TESTBED_TOPOLOGY_OPTION_END != rc->topology)
+  if (GNUNET_TESTBED_TOPOLOGY_NONE != rc->topology)
   {
-    if (GNUNET_TESTBED_TOPOLOGY_ERDOS_RENYI == rc->topology)
+    if ( (GNUNET_TESTBED_TOPOLOGY_ERDOS_RENYI == rc->topology)
+         || (GNUNET_TESTBED_TOPOLOGY_SMALL_WORLD_RING == rc->topology))
       rc->topology_operation =
           GNUNET_TESTBED_overlay_configure_topology (NULL,
                                                      rc->num_peers,
                                                      rc->peers,
                                                      rc->topology,
-                                                     rc->num_oc,
+                                                     (GNUNET_TESTBED_TOPOLOGY_ERDOS_RENYI
+                                                      == rc->topology) ?
+                                                     rc->num_oc : 
+                                                     (rc->num_oc - rc->num_peers),
                                                      GNUNET_TESTBED_TOPOLOGY_OPTION_END);
     else
       rc->topology_operation =
@@ -479,7 +483,7 @@ controller_status_cb (void *cls, const struct GNUNET_CONFIGURATION_Handle *cfg,
   event_mask = rc->event_mask;
   event_mask |= (1LL << GNUNET_TESTBED_ET_PEER_STOP);
   event_mask |= (1LL << GNUNET_TESTBED_ET_OPERATION_FINISHED);
-  if (rc->topology < GNUNET_TESTBED_TOPOLOGY_OPTION_END)
+  if (rc->topology < GNUNET_TESTBED_TOPOLOGY_NONE)
     event_mask |= GNUNET_TESTBED_ET_CONNECT;
   rc->c =
       GNUNET_TESTBED_controller_connect (cfg, rc->h, event_mask, &event_cb, rc);
@@ -624,33 +628,18 @@ GNUNET_TESTBED_run (const char *host_filename,
   rc->master = master;
   rc->master_cls = master_cls;
   rc->state = RC_INIT;
-  rc->topology = GNUNET_TESTBED_TOPOLOGY_OPTION_END;
+  rc->topology = GNUNET_TESTBED_TOPOLOGY_NONE;
   if (GNUNET_OK == GNUNET_CONFIGURATION_get_value_string (cfg, "testbed",
                                                           "OVERLAY_TOPOLOGY",
                                                           &topology))
   {
     if (0 == strcasecmp (topology, "RANDOM"))
-    {      
-      rc->topology = GNUNET_TESTBED_TOPOLOGY_ERDOS_RENYI;
-      if (GNUNET_OK != GNUNET_CONFIGURATION_get_value_number (cfg, "testbed",
-                                                              "OVERLAY_RANDOM_LINKS",
-                                                              &random_links))
-      {
-       /* OVERLAY option RANDOM requires OVERLAY_RANDOM_LINKS option to */
-       /*     be set to the number of random links to be established  */
-        GNUNET_break (0);
-        GNUNET_free (rc);
-        GNUNET_free (topology);
-        return;
-      }
-      if (random_links > UINT32_MAX)
-      {
-        GNUNET_break (0);       /* Too big number */
-        GNUNET_free (rc);
-        GNUNET_free (topology);
-        return;
-      }
-      rc->num_oc = (unsigned int) random_links;
+    {
+      rc->topology = GNUNET_TESTBED_TOPOLOGY_ERDOS_RENYI;      
+    }
+    else if (0 == strcasecmp (topology, "SMALL_WORLD_RING"))
+    {
+      rc->topology = GNUNET_TESTBED_TOPOLOGY_SMALL_WORLD_RING;
     }
     else if (0 == strcasecmp (topology, "CLIQUE"))
     {
@@ -672,6 +661,29 @@ GNUNET_TESTBED_run (const char *host_filename,
            "Unknown topology %s given in configuration\n", topology);
     GNUNET_free (topology);
   }
+  if ( (GNUNET_TESTBED_TOPOLOGY_ERDOS_RENYI == rc->topology)
+       || (GNUNET_TESTBED_TOPOLOGY_SMALL_WORLD_RING == rc->topology))
+  { 
+    if (GNUNET_OK != GNUNET_CONFIGURATION_get_value_number (cfg, "testbed",
+                                                            "OVERLAY_RANDOM_LINKS",
+                                                            &random_links))
+    {
+      /* OVERLAY option RANDOM & SMALL_WORLD_RING requires OVERLAY_RANDOM_LINKS
+         option to be set to the number of random links to be established  */
+      GNUNET_break (0);
+      GNUNET_free (rc);
+      return;
+    }
+    if (random_links > UINT32_MAX)
+    {
+      GNUNET_break (0);       /* Too big number */
+      GNUNET_free (rc);
+      return;
+    }
+    rc->num_oc = (unsigned int) random_links;
+    if (GNUNET_TESTBED_TOPOLOGY_SMALL_WORLD_RING == rc->topology)
+      rc->num_oc += num_peers;
+  }
   GNUNET_SCHEDULER_add_delayed (GNUNET_TIME_UNIT_FOREVER_REL,
                                 &shutdown_run_task, rc);
 }
@@ -703,7 +715,7 @@ GNUNET_TESTBED_create_va (struct GNUNET_TESTBED_Controller *controller,
                           enum GNUNET_TESTBED_TopologyOption underlay_topology,
                           va_list va)
 {
-  GNUNET_assert (underlay_topology < GNUNET_TESTBED_TOPOLOGY_OPTION_END);
+  GNUNET_assert (underlay_topology < GNUNET_TESTBED_TOPOLOGY_NONE);
   GNUNET_break (0);
   return NULL;
 }
diff --git a/src/testbed/testbed_api_topology.c b/src/testbed/testbed_api_topology.c
index d6575adbb..59d95ef3b 100644
--- a/src/testbed/testbed_api_topology.c
+++ b/src/testbed/testbed_api_topology.c
@@ -92,6 +92,11 @@ struct TopologyContext
   void *op_cls;
 
   /**
+   * The number of peers
+   */
+  unsigned int num_peers;
+
+  /**
    * The size of the link array
    */
   unsigned int link_array_size;
@@ -185,6 +190,97 @@ oprelease_overlay_configure_topology (void *cls)
 
 
 /**
+ * Generates line topology
+ *
+ * @param tc the topology context
+ */
+static void
+gen_topo_line (struct TopologyContext *tc)
+{
+  unsigned int cnt;
+
+  tc->link_array_size = tc->num_peers - 1;
+  tc->link_array = GNUNET_malloc (sizeof (struct OverlayLink) *
+                                  tc->link_array_size);
+  for (cnt=0; cnt < (tc->num_peers - 1); cnt++)
+  {
+    tc->link_array[cnt].A = cnt;
+    tc->link_array[cnt].B = cnt + 1;
+    tc->link_array[cnt].tc = tc;
+  }
+}
+
+
+/**
+ * Generates ring topology
+ *
+ * @param tc the topology context
+ */
+static void
+gen_topo_ring (struct TopologyContext *tc)
+{
+  gen_topo_line (tc);
+  tc->link_array_size++;
+  tc->link_array = GNUNET_realloc (tc->link_array,
+                                   sizeof (struct OverlayLink) *
+                                   tc->link_array_size);
+  tc->link_array[tc->link_array_size - 1].op = NULL;
+  tc->link_array[tc->link_array_size - 1].tc = tc;
+  tc->link_array[tc->link_array_size - 1].A = tc->num_peers - 1;
+  tc->link_array[tc->link_array_size - 1].B = 0;
+}
+
+
+/**
+ * Generates ring topology
+ *
+ * @param tc the topology context
+ * @param links the number of random links to establish
+ * @param append GNUNET_YES to add links to existing link array; GNUNET_NO to
+ *          create a new link array
+ */
+static void
+gen_topo_random (struct TopologyContext *tc, unsigned int links, int append)
+{
+  unsigned int cnt;
+  unsigned int index;
+  uint32_t A_rand;
+  uint32_t B_rand;
+  
+  if (GNUNET_YES == append)
+  {
+    GNUNET_assert ((0 < tc->link_array_size) && (NULL != tc->link_array));
+    index = tc->link_array_size;   
+    tc->link_array_size += links;
+    tc->link_array = GNUNET_realloc (tc->link_array,
+                                   sizeof (struct OverlayLink) *
+                                     tc->link_array_size);
+  }
+  else
+  {
+    GNUNET_assert ((0 == tc->link_array_size) && (NULL == tc->link_array));
+    index = 0;   
+    tc->link_array_size = links;
+    tc->link_array = GNUNET_malloc (sizeof (struct OverlayLink) *
+                                    tc->link_array_size);
+  }
+  for (cnt = 0; cnt < links; cnt++)
+  {
+    do {
+      A_rand = GNUNET_CRYPTO_random_u32 (GNUNET_CRYPTO_QUALITY_WEAK,
+                                         tc->num_peers);
+      B_rand = GNUNET_CRYPTO_random_u32 (GNUNET_CRYPTO_QUALITY_WEAK,
+                                         tc->num_peers);
+    } while (A_rand == B_rand);
+    tc->link_array[index + cnt].op = NULL;
+    tc->link_array[index + cnt].A = A_rand;
+    tc->link_array[index + cnt].B = B_rand;
+    tc->link_array[index + cnt].tc = tc;
+  }
+}
+
+
+/**
  * Configure overall network topology to have a particular shape.
  *
  * @param op_cls closure argument to give with the operation event
@@ -264,50 +360,26 @@ GNUNET_TESTBED_overlay_configure_topology_va (void *op_cls,
   c = peers[0]->controller;
   tc = GNUNET_malloc (sizeof (struct TopologyContext));
   tc->peers = peers;
+  tc->num_peers = num_peers;
   tc->op_cls = op_cls;
   switch (topo)
   {
   case GNUNET_TESTBED_TOPOLOGY_LINE:
+    gen_topo_line (tc);
+    break;
   case GNUNET_TESTBED_TOPOLOGY_RING:
-    tc->link_array_size = 
-        (GNUNET_TESTBED_TOPOLOGY_LINE == topo)
-        ? (num_peers - 1) : num_peers;
-    tc->link_array = GNUNET_malloc (sizeof (struct OverlayLink) *
-                                    tc->link_array_size);
-    for (cnt=0; cnt < (num_peers - 1); cnt++)
-    {
-      tc->link_array[cnt].A = cnt;
-      tc->link_array[cnt].B = cnt + 1;
-      tc->link_array[cnt].tc = tc;
-    }
-    if (GNUNET_TESTBED_TOPOLOGY_RING == topo)
-    {
-      tc->link_array[cnt].A = num_peers - 1;
-      tc->link_array[cnt].B = 0;
-      tc->link_array[cnt].tc = tc;
-      cnt++;
-    }
-    GNUNET_assert (cnt == tc->link_array_size);
+    gen_topo_ring (tc);
     break;
   case GNUNET_TESTBED_TOPOLOGY_ERDOS_RENYI:
-    tc->link_array_size = va_arg (va, unsigned int);
-    tc->link_array = GNUNET_malloc (sizeof (struct OverlayLink) *
-                                    tc->link_array_size);
-    for (cnt = 0; cnt < tc->link_array_size; cnt++)
-    {
-      uint32_t A_rand;
-      uint32_t B_rand;
-      
-      do {
-        A_rand = GNUNET_CRYPTO_random_u32 (GNUNET_CRYPTO_QUALITY_WEAK,
-                                           num_peers);
-        B_rand = GNUNET_CRYPTO_random_u32 (GNUNET_CRYPTO_QUALITY_WEAK,
-                                           num_peers);
-      } while (A_rand == B_rand);      
-      tc->link_array[cnt].A = A_rand;
-      tc->link_array[cnt].B = B_rand;
-      tc->link_array[cnt].tc = tc;
-    }
+    gen_topo_random (tc,
+                     va_arg (va, unsigned int),
+                     GNUNET_NO);
+    break;
+  case GNUNET_TESTBED_TOPOLOGY_SMALL_WORLD_RING:
+    gen_topo_ring (tc);
+    gen_topo_random (tc,
+                     va_arg (va, unsigned int),
+                     GNUNET_YES);
     break;
   case GNUNET_TESTBED_TOPOLOGY_CLIQUE:
     tc->link_array_size = num_peers * (num_peers - 1);