[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[GNUnet-SVN] r25063 - gnunet/src/testbed
From: |
gnunet |
Subject: |
[GNUnet-SVN] r25063 - gnunet/src/testbed |
Date: |
Tue, 20 Nov 2012 12:24:06 +0100 |
Author: harsha
Date: 2012-11-20 12:24:05 +0100 (Tue, 20 Nov 2012)
New Revision: 25063
Modified:
gnunet/src/testbed/testbed_api_topology.c
Log:
scale free topology
Modified: gnunet/src/testbed/testbed_api_topology.c
===================================================================
--- gnunet/src/testbed/testbed_api_topology.c 2012-11-20 09:12:46 UTC (rev
25062)
+++ gnunet/src/testbed/testbed_api_topology.c 2012-11-20 11:24:05 UTC (rev
25063)
@@ -191,6 +191,28 @@
/**
+ * Populates the OverlayLink structure
+ *
+ * @param link the OverlayLink
+ * @param A the peer A
+ * @param B the peer B
+ * @param tc the TopologyContext
+ * @return
+ */
+static void
+make_link (struct OverlayLink *link,
+ uint32_t A,
+ uint32_t B,
+ struct TopologyContext *tc)
+{
+ link->A = A;
+ link->B = B;
+ link->op = NULL;
+ link->tc = tc;
+}
+
+
+/**
* Generates line topology
*
* @param tc the topology context
@@ -204,11 +226,7 @@
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;
- }
+ make_link (&tc->link_array[cnt], cnt, cnt + 1, tc);
}
@@ -225,10 +243,10 @@
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;
+ make_link (&tc->link_array[tc->link_array_size - 1],
+ tc->num_peers - 1,
+ 0,
+ tc);
}
@@ -314,16 +332,18 @@
{
for (x = 0; x < rows_len[y] - 1; x++)
{
- tc->link_array[cnt].tc = tc;
- tc->link_array[cnt].A = offset + x;
- tc->link_array[cnt].B = offset + x + 1;
+ make_link (&tc->link_array[cnt],
+ offset + x,
+ offset + x + 1,
+ tc);
cnt++;
}
if (0 == x)
break;
- tc->link_array[cnt].tc = tc;
- tc->link_array[cnt].A = offset + x;
- tc->link_array[cnt].B = offset;
+ make_link (&tc->link_array[cnt],
+ offset + x,
+ offset,
+ tc);
cnt++;
offset += rows_len[y];
}
@@ -335,17 +355,19 @@
if (x == rows_len[y+1])
break;
GNUNET_assert (x < rows_len[y+1]);
- tc->link_array[cnt].tc= tc;
- tc->link_array[cnt].A = offset + x;
+ make_link (&tc->link_array[cnt],
+ offset + x,
+ offset + rows_len[y] + x,
+ tc);
offset += rows_len[y];
- tc->link_array[cnt].B = offset + x;
cnt++;
}
if (0 == offset)
break;
- tc->link_array[cnt].tc = tc;
- tc->link_array[cnt].A = offset + x;
- tc->link_array[cnt].B = x;
+ make_link (&tc->link_array[cnt],
+ offset + x,
+ x,
+ tc);
cnt++;
}
GNUNET_assert (cnt == tc->link_array_size);
@@ -394,15 +416,62 @@
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;
+ make_link (&tc->link_array[index + cnt], A_rand, B_rand, tc);
}
}
/**
+ * Generates scale free network. Its construction is described in:
+ *
+ * "Emergence of Scaling in Random Networks." Science 286, 509-512, 1999.
+ *
+ * @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_scale_free (struct TopologyContext *tc)
+{
+ 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 = 1; cnt < tc->num_peers; cnt++)
+ {
+ previous_connections = tc->link_array_size;
+ for (i = 0; i < cnt; i++)
+ {
+ 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], cnt, i, tc);
+ popularity[cnt]++;
+ }
+ }
+ }
+ GNUNET_free (popularity);
+}
+
+
+/**
* Configure overall network topology to have a particular shape.
*
* @param op_cls closure argument to give with the operation event
@@ -536,6 +605,9 @@
va_arg (va, unsigned int),
GNUNET_YES);
break;
+ case GNUNET_TESTBED_TOPOLOGY_SCALE_FREE:
+ gen_scale_free (tc);
+ break;
default:
GNUNET_break (0);
GNUNET_free (tc);
[Prev in Thread] |
Current Thread |
[Next in Thread] |
- [GNUnet-SVN] r25063 - gnunet/src/testbed,
gnunet <=