/*
This file is part of GNUnet
- (C) 2008--2012 Christian Grothoff (and other contributing authors)
+ Copyright (C) 2008--2013 GNUnet e.V.
GNUnet is free software; you can redistribute it and/or modify
it under the terms of the GNU General Public License as published
You should have received a copy of the GNU General Public License
along with GNUnet; see the file COPYING. If not, write to the
- Free Software Foundation, Inc., 59 Temple Place - Suite 330,
- Boston, MA 02111-1307, USA.
+ Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
+ Boston, MA 02110-1301, USA.
*/
/**
GNUNET_log_from (kind, "testbed-api-topology", __VA_ARGS__)
+/**
+ * Default number of retires
+ */
+#define DEFAULT_RETRY_CNT 3
+
+
/**
* Context information for topology operations
*/
/**
* The topology context this link is a part of
- */
+ */
struct TopologyContext *tc;
/**
/**
- * Context information for topology operations
+ * Representation of an underlay link
*/
-struct TopologyContext
+struct UnderlayLink
+{
+ /**
+ * position of peer A's handle in peers array
+ */
+ uint32_t A;
+
+ /**
+ * position of peer B's handle in peers array
+ */
+ uint32_t B;
+
+ /**
+ * Bandwidth of the link in bytes per second
+ */
+ uint32_t bandwidth;
+
+ /**
+ * Latency of the link in milliseconds
+ */
+ uint32_t latency;
+
+ /**
+ * Loss in the link in percentage of message dropped
+ */
+ uint32_t loss;
+};
+
+
+struct RetryListEntry
+{
+ /**
+ * the next pointer for the DLL
+ */
+ struct RetryListEntry *next;
+
+ /**
+ * the prev pointer for the DLL
+ */
+ struct RetryListEntry *prev;
+
+ /**
+ * The link to be retired
+ */
+ struct OverlayLink *link;
+};
+
+
+/**
+ * Context information for overlay topologies
+ */
+struct TopologyContextOverlay
{
/**
* The array of peers
*/
void *op_cls;
+ /**
+ * topology generation completion callback
+ */
+ GNUNET_TESTBED_TopologyCompletionCallback comp_cb;
+
+ /**
+ * The closure for the above callback
+ */
+ void *comp_cb_cls;
+
+ /**
+ * DLL head for retry list
+ */
+ struct RetryListEntry *rl_head;
+
+ /**
+ * DLL tail for retry list
+ */
+ struct RetryListEntry *rl_tail;
+
+ /**
+ * How many retries to do before we give up
+ */
+ unsigned int retry_cnt;
+
+ /**
+ * Number of links to try
+ */
+ unsigned int nlinks;
+
+ /**
+ * How many links have been completed
+ */
+ unsigned int ncompleted;
+
+ /**
+ * Total successfully established overlay connections
+ */
+ unsigned int nsuccess;
+
+ /**
+ * Total failed overlay connections
+ */
+ unsigned int nfailures;
+};
+
+
+/**
+ * Topology context information for underlay topologies
+ */
+struct TopologyContextUnderlay
+{
+ /**
+ * The link array
+ */
+ struct UnderlayLink *link_array;
+};
+
+
+/**
+ * Context information for topology operations
+ */
+struct TopologyContext
+{
+ /**
+ * The type of this context
+ */
+ enum {
+
+ /**
+ * Type for underlay topology
+ */
+ TOPOLOGYCONTEXT_TYPE_UNDERLAY = 0,
+
+ /**
+ * Type for overlay topology
+ */
+ TOPOLOGYCONTEXT_TYPE_OVERLAY
+
+ } type;
+
+ union {
+
+ /**
+ * Topology context information for overlay topology
+ */
+ struct TopologyContextOverlay overlay;
+
+ /**
+ * Topology context information for underlay topology
+ */
+ struct TopologyContextUnderlay underlay;
+ } u;
+
/**
* The number of peers
*/
*/
unsigned int link_array_size;
- /**
- * should the automatic retry be disabled
- */
- int disable_retry;
-
};
* A array of names representing topologies. Should be in sync with enum
* GNUNET_TESTBED_TopologyOption
*/
-const char * topology_strings[] = {
-
+const char *topology_strings[] = {
+
/**
* A clique (everyone connected to everyone else). No options. If there are N
* peers this topology results in (N * (N -1)) connections.
*/
- "CLIQUE",
+ "CLIQUE",
/**
* Small-world network (2d torus plus random links). Followed
* by the number of random links to add (unsigned int).
*/
- "SMALL_WORLD",
+ "SMALL_WORLD",
/**
* Small-world network (ring plus random links). Followed
* by the number of random links to add (unsigned int).
*/
- "SMALL_WORLD_RING",
+ "SMALL_WORLD_RING",
/**
* Ring topology. No options.
*/
- "RING",
+ "RING",
/**
* 2-d torus. No options.
*/
- "2D_TORUS",
+ "2D_TORUS",
/**
* Random graph. Followed by the number of random links to be established
* (unsigned int)
*/
- "RANDOM", // GNUNET_TESTBED_TOPOLOGY_ERDOS_RENYI
+ "RANDOM", // GNUNET_TESTBED_TOPOLOGY_ERDOS_RENYI
/**
* Certain percentage of peers are unable to communicate directly
* replicating NAT conditions. Followed by the fraction of
* NAT'ed peers (float).
*/
- "INTERNAT",
+ "INTERNAT",
/**
- * Scale free topology. FIXME: options?
+ * Scale free topology. Followed by the maximum number of links a node can
+ * have (unsigned int); and the number of links a new node should have when
+ * it is added to the network (unsigned int)
*/
- "SCALE_FREE",
+ "SCALE_FREE",
/**
* Straight line topology. No options.
*/
- "LINE",
+ "LINE",
/**
* Read a topology from a given file. Followed by the name of the file (const char *).
*/
- "FROM_FILE",
+ "FROM_FILE",
/**
* All peers are disconnected. No options.
*/
- "NONE",
-
+ "NONE",
+
/**
* End of strings
*/
- NULL
-
- };
+ NULL
+};
/**
* @param emsg error message in case the operation has failed; will be NULL if
* operation has executed successfully.
*/
-static void
-overlay_link_completed (void *cls,
- struct GNUNET_TESTBED_Operation *op,
- const char *emsg)
+static void
+overlay_link_completed (void *cls, struct GNUNET_TESTBED_Operation *op,
+ const char *emsg)
{
struct OverlayLink *link = cls;
struct TopologyContext *tc;
+ struct TopologyContextOverlay *overlay;
+ struct RetryListEntry *retry_entry;
GNUNET_assert (op == link->op);
GNUNET_TESTBED_operation_done (op);
link->op = NULL;
tc = link->tc;
- if ((NULL != emsg) && (GNUNET_NO == tc->disable_retry))
+ GNUNET_assert (TOPOLOGYCONTEXT_TYPE_OVERLAY == tc->type);
+ overlay = &tc->u.overlay;
+ if (NULL != emsg)
{
- LOG (GNUNET_ERROR_TYPE_WARNING,
- "Error while establishing a link: %s -- Retrying\n", emsg);
- link->op =
- GNUNET_TESTBED_overlay_connect (tc->op_cls,
- &overlay_link_completed,
- link,
- tc->peers[link->A],
- tc->peers[link->B]);
+ overlay->nfailures++;
+ if (0 != overlay->retry_cnt)
+ {
+ LOG (GNUNET_ERROR_TYPE_WARNING,
+ "Error while establishing a link: %s -- Retrying\n", emsg);
+ retry_entry = GNUNET_new (struct RetryListEntry);
+ retry_entry->link = link;
+ GNUNET_CONTAINER_DLL_insert_tail (overlay->rl_head, overlay->rl_tail, retry_entry);
+ }
+ }
+ else
+ overlay->nsuccess++;
+ overlay->ncompleted++;
+ if (overlay->ncompleted < overlay->nlinks)
+ return;
+ if ((0 != overlay->retry_cnt) && (NULL != overlay->rl_head))
+ {
+ overlay->retry_cnt--;
+ overlay->ncompleted = 0;
+ overlay->nlinks = 0;
+ while (NULL != (retry_entry = overlay->rl_head))
+ {
+ link = retry_entry->link;
+ link->op =
+ GNUNET_TESTBED_overlay_connect (overlay->op_cls, &overlay_link_completed,
+ link, overlay->peers[link->A],
+ overlay->peers[link->B]);
+ overlay->nlinks++;
+ GNUNET_CONTAINER_DLL_remove (overlay->rl_head, overlay->rl_tail, retry_entry);
+ GNUNET_free (retry_entry);
+ }
return;
}
+ if (NULL != overlay->comp_cb)
+ {
+ overlay->comp_cb (overlay->comp_cb_cls, overlay->nsuccess, overlay->nfailures);
+ }
}
opstart_overlay_configure_topology (void *cls)
{
struct TopologyContext *tc = cls;
+ struct TopologyContextOverlay *overlay;
unsigned int p;
-
+
+ GNUNET_assert (TOPOLOGYCONTEXT_TYPE_OVERLAY == tc->type);
+ overlay = &tc->u.overlay;
+ overlay->nlinks = tc->link_array_size;
for (p = 0; p < tc->link_array_size; p++)
{
- tc->link_array[p].op =
- GNUNET_TESTBED_overlay_connect (tc->op_cls, &overlay_link_completed,
- &tc->link_array[p],
- tc->peers[tc->link_array[p].A],
- tc->peers[tc->link_array[p].B]);
+ overlay->link_array[p].op =
+ GNUNET_TESTBED_overlay_connect (overlay->op_cls, &overlay_link_completed,
+ &overlay->link_array[p],
+ overlay->peers[overlay->link_array[p].A],
+ overlay->peers[overlay->link_array[p].B]);
}
}
oprelease_overlay_configure_topology (void *cls)
{
struct TopologyContext *tc = cls;
+ struct TopologyContextOverlay *overlay;
+ struct RetryListEntry *retry_entry;
unsigned int p;
-
- if (NULL != tc->link_array)
+
+ GNUNET_assert (TOPOLOGYCONTEXT_TYPE_OVERLAY == tc->type);
+ overlay = &tc->u.overlay;
+ while (NULL != (retry_entry = overlay->rl_head))
+ {
+ GNUNET_CONTAINER_DLL_remove (overlay->rl_head, overlay->rl_tail, retry_entry);
+ GNUNET_free (retry_entry);
+ }
+ if (NULL != overlay->link_array)
{
for (p = 0; p < tc->link_array_size; p++)
- if (NULL != tc->link_array[p].op)
- GNUNET_TESTBED_operation_done (tc->link_array[p].op);
- GNUNET_free (tc->link_array);
+ if (NULL != overlay->link_array[p].op)
+ GNUNET_TESTBED_operation_done (overlay->link_array[p].op);
+ GNUNET_free (overlay->link_array);
}
GNUNET_free (tc);
}
/**
- * Populates the OverlayLink structure
+ * Populates the OverlayLink structure.
*
- * @param link the OverlayLink
- * @param A the peer A
- * @param B the peer B
+ * @param offset the offset of the link array to use
+ * @param A the peer A. Should be different from B
+ * @param B the peer B. Should be different from A
* @param tc the TopologyContext
- * @return
+ * @return
*/
static void
-make_link (struct OverlayLink *link,
- uint32_t A,
- uint32_t B,
+make_link (unsigned int offset, uint32_t A, uint32_t B,
struct TopologyContext *tc)
{
- link->A = A;
- link->B = B;
- link->op = NULL;
- link->tc = tc;
+ GNUNET_assert (A != B);
+ switch (tc->type)
+ {
+ case TOPOLOGYCONTEXT_TYPE_OVERLAY:
+ {
+ struct TopologyContextOverlay *overlay;
+ struct OverlayLink *olink;
+
+ overlay = &tc->u.overlay;
+ GNUNET_assert (offset < tc->link_array_size);
+ olink = &overlay->link_array[offset];
+ LOG (GNUNET_ERROR_TYPE_DEBUG, "Connecting peer %u to %u\n", B, A);
+ olink->A = A;
+ olink->B = B;
+ olink->op = NULL;
+ olink->tc = tc;
+ }
+ break;
+ case TOPOLOGYCONTEXT_TYPE_UNDERLAY:
+ {
+ struct TopologyContextUnderlay *underlay;
+ struct UnderlayLink *ulink;
+
+ underlay = &tc->u.underlay;
+ GNUNET_assert (offset < tc->link_array_size);
+ ulink = &underlay->link_array[offset];
+ ulink->A = A;
+ ulink->B = B;
+ }
+ break;
+ }
}
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++)
- make_link (&tc->link_array[cnt], cnt, cnt + 1, tc);
+ switch (tc->type)
+ {
+ case TOPOLOGYCONTEXT_TYPE_OVERLAY:
+ {
+ struct TopologyContextOverlay *overlay;
+
+ overlay = &tc->u.overlay;
+ overlay->link_array =
+ GNUNET_malloc (sizeof (struct OverlayLink) * tc->link_array_size);
+ }
+ break;
+ case TOPOLOGYCONTEXT_TYPE_UNDERLAY:
+ {
+ struct TopologyContextUnderlay *underlay;
+
+ underlay = &tc->u.underlay;
+ underlay->link_array =
+ GNUNET_malloc (sizeof (struct UnderlayLink) * tc->link_array_size);
+ }
+ break;
+ }
+ for (cnt = 0; cnt < (tc->link_array_size); cnt++)
+ make_link (cnt, cnt, cnt + 1, tc);
}
{
gen_topo_line (tc);
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],
- tc->num_peers - 1,
- 0,
- tc);
+ switch (tc->type)
+ {
+ case TOPOLOGYCONTEXT_TYPE_OVERLAY:
+ {
+ struct TopologyContextOverlay *overlay;
+
+ overlay = &tc->u.overlay;
+ overlay->link_array =
+ GNUNET_realloc (overlay->link_array, sizeof (struct OverlayLink) *
+ tc->link_array_size);
+ }
+ break;
+ case TOPOLOGYCONTEXT_TYPE_UNDERLAY:
+ {
+ struct TopologyContextUnderlay *underlay;
+
+ underlay = &tc->u.underlay;
+ underlay->link_array =
+ GNUNET_realloc (underlay->link_array, sizeof (struct UnderlayLink) *
+ tc->link_array_size);
+ }
+ break;
+ }
+ make_link (tc->link_array_size - 1, tc->num_peers - 1, 0, tc);
}
* @param rows number of rows in the 2d torus. Can be NULL
* @param rows_len the length of each row. This array will be allocated
* fresh. The caller should free it. Can be NULL
+ * @return the number of links that are required to generate a 2d torus for the
+ * given number of peers
*/
unsigned int
-GNUNET_TESTBED_2dtorus_calc_links (unsigned int num_peers,
- unsigned int *rows,
+GNUNET_TESTBED_2dtorus_calc_links (unsigned int num_peers, unsigned int *rows,
unsigned int **rows_len)
{
double sq;
unsigned int y;
unsigned int _num_peers;
unsigned int cnt;
-
+
sq = sqrt (num_peers);
sq = floor (sq);
sq_floor = (unsigned int) sq;
_rows = (sq_floor + 1);
- _rows_len = GNUNET_malloc (sizeof (unsigned int) * _rows);
+ _rows_len = GNUNET_malloc (sizeof (unsigned int) * _rows);
for (y = 0; y < _rows - 1; y++)
_rows_len[y] = sq_floor;
_num_peers = sq_floor * sq_floor;
- cnt = 2 * _num_peers;
+ cnt = (_num_peers < 2) ? _num_peers : 2 * _num_peers;
x = 0;
y = 0;
while (_num_peers < num_peers)
unsigned int cnt;
unsigned int offset;
- tc->link_array_size = GNUNET_TESTBED_2dtorus_calc_links (tc->num_peers, &rows,
- &rows_len);
- tc->link_array = GNUNET_malloc (sizeof (struct OverlayLink) *
- tc->link_array_size);
+ tc->link_array_size =
+ GNUNET_TESTBED_2dtorus_calc_links (tc->num_peers, &rows, &rows_len);
+ switch (tc->type)
+ {
+ case TOPOLOGYCONTEXT_TYPE_OVERLAY:
+ {
+ struct TopologyContextOverlay *overlay;
+
+ overlay = &tc->u.overlay;
+ overlay->link_array =
+ GNUNET_malloc (sizeof (struct OverlayLink) * tc->link_array_size);
+ }
+ break;
+ case TOPOLOGYCONTEXT_TYPE_UNDERLAY:
+ {
+ struct TopologyContextUnderlay *underlay;
+
+ underlay = &tc->u.underlay;
+ underlay->link_array =
+ GNUNET_malloc (sizeof (struct UnderlayLink) * tc->link_array_size);
+ break;
+ }
+ }
cnt = 0;
offset = 0;
for (y = 0; y < rows; y++)
{
for (x = 0; x < rows_len[y] - 1; x++)
{
- make_link (&tc->link_array[cnt],
- offset + x,
- offset + x + 1,
- tc);
+ make_link (cnt, offset + x, offset + x + 1, tc);
cnt++;
}
if (0 == x)
break;
- make_link (&tc->link_array[cnt],
- offset + x,
- offset,
- tc);
+ make_link (cnt, offset + x, offset, tc);
cnt++;
offset += rows_len[y];
}
offset = 0;
for (y = 0; y < rows - 1; y++)
{
- if (x == rows_len[y+1])
+ if (x >= rows_len[y + 1])
break;
- GNUNET_assert (x < rows_len[y+1]);
- make_link (&tc->link_array[cnt],
- offset + x,
- offset + rows_len[y] + x,
- tc);
+ GNUNET_assert (x < rows_len[y + 1]);
+ make_link (cnt, offset + x, offset + rows_len[y] + x, tc);
offset += rows_len[y];
cnt++;
}
if (0 == offset)
break;
- make_link (&tc->link_array[cnt],
- offset + x,
- x,
- tc);
+ make_link (cnt, offset + x, x, tc);
cnt++;
}
GNUNET_assert (cnt == tc->link_array_size);
*
* @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
+ * @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)
+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 (1 == tc->num_peers)
+ return;
if (GNUNET_YES == append)
{
- GNUNET_assert ((0 < tc->link_array_size) && (NULL != tc->link_array));
- index = tc->link_array_size;
+ 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;
+ index = 0;
tc->link_array_size = links;
- tc->link_array = GNUNET_malloc (sizeof (struct OverlayLink) *
- tc->link_array_size);
+ }
+ switch (tc->type)
+ {
+ case TOPOLOGYCONTEXT_TYPE_OVERLAY:
+ {
+ struct TopologyContextOverlay *overlay;
+
+ overlay = &tc->u.overlay;
+ if (GNUNET_YES != append)
+ {
+ GNUNET_assert (NULL == overlay->link_array);
+ overlay->link_array =
+ GNUNET_malloc (sizeof (struct OverlayLink) * tc->link_array_size);
+ break;
+ }
+ GNUNET_assert ((0 < tc->link_array_size) && (NULL != overlay->link_array));
+ overlay->link_array =
+ GNUNET_realloc (overlay->link_array,
+ sizeof (struct OverlayLink) * tc->link_array_size);
+ break;
+ }
+ case TOPOLOGYCONTEXT_TYPE_UNDERLAY:
+ {
+ struct TopologyContextUnderlay *underlay;
+
+ underlay = &tc->u.underlay;
+ if (GNUNET_YES != append)
+ {
+ GNUNET_assert (NULL == underlay->link_array);
+ underlay->link_array =
+ GNUNET_malloc (sizeof (struct UnderlayLink) * tc->link_array_size);
+ break;
+ }
+ GNUNET_assert ((0 < tc->link_array_size) && (NULL != underlay->link_array));
+ underlay->link_array =
+ GNUNET_realloc (underlay->link_array,
+ sizeof (struct UnderlayLink) * tc->link_array_size);
+ break;
+ }
}
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);
- make_link (&tc->link_array[index + cnt], A_rand, B_rand, tc);
+ 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);
+ make_link (index+cnt, A_rand, B_rand, tc);
}
}
* "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_topo_scale_free (struct TopologyContext *tc,
+ uint16_t cap,
+ uint8_t m)
{
- double random;
- double probability;
+ unsigned int *deg;
+ unsigned int *etab;
+ unsigned int *used;
+ unsigned int etaboff;
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)
+ unsigned int cnt2;
+ unsigned int peer;
+ unsigned int random_peer;
+ unsigned int links;
+ unsigned int off;
+ unsigned int redo_threshold;
+
+ etaboff = 0;
+ tc->link_array_size = tc->num_peers * m;
+ switch (tc->type)
+ {
+ case TOPOLOGYCONTEXT_TYPE_OVERLAY:
+ {
+ struct TopologyContextOverlay *overlay;
+
+ overlay = &tc->u.overlay;
+ overlay->link_array = GNUNET_malloc_large (sizeof (struct OverlayLink) *
+ tc->link_array_size);
+ }
+ break;
+ case TOPOLOGYCONTEXT_TYPE_UNDERLAY:
+ {
+ struct TopologyContextUnderlay *underlay;
+
+ underlay = &tc->u.underlay;
+ underlay->link_array = GNUNET_malloc_large (sizeof (struct UnderlayLink) *
+ tc->link_array_size);
+ }
+ break;
+ }
+ etab = GNUNET_malloc_large (sizeof (unsigned int) * 2 * tc->link_array_size);
+ deg = GNUNET_malloc (sizeof (unsigned int) * tc->num_peers);
+ used = GNUNET_malloc (sizeof (unsigned int) * m);
+ /* start by connecting peer 1 to peer 0 */
+ make_link (0, 0, 1, tc);
+ deg[0]++;
+ deg[1]++;
+ etab[etaboff++] = 0;
+ etab[etaboff++] = 1;
+ links = 1;
+ for (peer = 2; peer < tc->num_peers; peer++)
+ {
+ if (cap < deg[peer])
+ continue;
+ for (cnt = 0; cnt < GNUNET_MIN (peer, m); cnt++)
+ {
+ redo_threshold = 0;
+ redo:
+ off = GNUNET_CRYPTO_random_u64 (GNUNET_CRYPTO_QUALITY_WEAK, etaboff);
+ random_peer = etab[off];
+ if (cap < deg[random_peer])
{
- 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]++;
+ if (++redo_threshold > GNUNET_MAX (1, cap / 2))
+ {
+ redo_threshold = 0;
+ off = 0;
+ for (cnt2 = 0; cnt2 < etaboff; cnt2++)
+ {
+ if (random_peer == etab[cnt2])
+ {
+ off++;
+ continue;
+ }
+ etab[cnt2 - off] = etab[cnt2];
+ }
+ etaboff -= off;
+ }
+ goto redo;
}
+ for (cnt2 = 0; cnt2 < cnt; cnt2++)
+ if (random_peer == used[cnt2])
+ goto redo;
+ make_link (links + cnt, random_peer, peer, tc);
+ deg[random_peer]++;
+ deg[peer]++;
+ used[cnt] = random_peer;
}
+ for (cnt = 0; cnt < GNUNET_MIN (peer, m); cnt++)
+ {
+ etab[etaboff++] = used[cnt];
+ etab[etaboff++] = peer;
+ }
+ links += GNUNET_MIN (peer, m);
+ }
+ GNUNET_free (etab);
+ GNUNET_free (used);
+ GNUNET_free (deg);
+ GNUNET_assert (links <= tc->link_array_size);
+ tc->link_array_size = links;
+ switch (tc->type)
+ {
+ case TOPOLOGYCONTEXT_TYPE_OVERLAY:
+ {
+ struct TopologyContextOverlay *overlay;
+
+ overlay = &tc->u.overlay;
+ overlay->link_array =
+ GNUNET_realloc (overlay->link_array, sizeof (struct OverlayLink) * tc->link_array_size);
+ }
+ break;
+ case TOPOLOGYCONTEXT_TYPE_UNDERLAY:
+ {
+ struct TopologyContextUnderlay *underlay;
+
+ underlay = &tc->u.underlay;
+ underlay->link_array =
+ GNUNET_realloc (underlay->link_array, sizeof (struct UnderlayLink) * tc->link_array_size);
+ }
+ break;
}
- GNUNET_free (popularity);
}
* @param filename the filename of the file containing topology data
*/
static void
-gen_topo_from_file (struct TopologyContext *tc, const char *filename)
+gen_topo_from_file (struct TopologyContext *tc,
+ const char *filename)
{
char *data;
char *end;
uint64_t offset;
unsigned long int peer_id;
unsigned long int other_peer_id;
- enum ParseState {
-
+ enum ParseState
+ {
+
/**
* We read the peer index
*/
status = GNUNET_SYSERR;
if (GNUNET_YES != GNUNET_DISK_file_test (filename))
{
- LOG (GNUNET_ERROR_TYPE_ERROR, _("Topology file %s not found\n"), filename);
+ LOG (GNUNET_ERROR_TYPE_ERROR,
+ _("Topology file %s not found\n"),
+ filename);
return;
}
if (GNUNET_OK !=
GNUNET_DISK_file_size (filename, &fs, GNUNET_YES, GNUNET_YES))
{
- LOG (GNUNET_ERROR_TYPE_ERROR, _("Topology file %s has no data\n"), filename);
+ LOG (GNUNET_ERROR_TYPE_ERROR,
+ _("Topology file %s has no data\n"),
+ filename);
return;
}
data = GNUNET_malloc (fs);
if (fs != GNUNET_DISK_fn_read (filename, data, fs))
{
- LOG (GNUNET_ERROR_TYPE_ERROR, _("Topology file %s cannot be read\n"),
+ LOG (GNUNET_ERROR_TYPE_ERROR,
+ _("Topology file %s cannot be read\n"),
filename);
goto _exit;
}
offset = 0;
peer_id = 0;
state = PEER_INDEX;
- buf = data;
while (offset < fs)
{
if (0 != isspace (data[offset]))
if (tc->num_peers <= peer_id)
{
LOG (GNUNET_ERROR_TYPE_ERROR,
- _("Topology file need more peers than the given ones\n"),
- filename);
+ _("Topology file needs more peers than given ones\n"), filename);
goto _exit;
}
state = OTHER_PEER_INDEX;
break;
case OTHER_PEER_INDEX:
errno = 0;
- other_peer_id = (unsigned int) strtoul (&data[offset], &end, 10);
+ other_peer_id = (unsigned int) strtoul (&data[offset], &end, 10);
if (0 != errno)
{
LOG (GNUNET_ERROR_TYPE_ERROR,
if (tc->num_peers <= other_peer_id)
{
LOG (GNUNET_ERROR_TYPE_ERROR,
- _("Topology file need more peers than the given ones\n"),
- filename);
+ _("Topology file needs more peers than given ones\n"), filename);
goto _exit;
}
- tc->link_array_size++;
- tc->link_array = GNUNET_realloc (tc->link_array,
- sizeof (struct OverlayLink) *
- tc->link_array_size);
- offset += end - &data[offset];
- make_link (&tc->link_array[tc->link_array_size - 1], peer_id,
- other_peer_id, tc);
- while (('\n' != data[offset]) && ('|' != data[offset])
- && (offset < fs))
+ if (peer_id != other_peer_id)
+ {
+ tc->link_array_size++;
+ switch (tc->type)
+ {
+ case TOPOLOGYCONTEXT_TYPE_OVERLAY:
+ {
+ struct TopologyContextOverlay *overlay;
+
+ overlay = &tc->u.overlay;
+ overlay->link_array =
+ GNUNET_realloc (overlay->link_array,
+ sizeof (struct OverlayLink) * tc->link_array_size);
+ }
+ break;
+ case TOPOLOGYCONTEXT_TYPE_UNDERLAY:
+ {
+ struct TopologyContextUnderlay *underlay;
+
+ underlay = &tc->u.underlay;
+ underlay->link_array =
+ GNUNET_realloc (underlay->link_array,
+ sizeof (struct UnderlayLink) * tc->link_array_size);
+ }
+ break;
+ }
+ offset += end - &data[offset];
+ make_link (tc->link_array_size - 1, peer_id, other_peer_id, tc);
+ }
+ else
+ LOG (GNUNET_ERROR_TYPE_WARNING,
+ _("Ignoring to connect peer %u to peer %u\n"),
+ peer_id,
+ other_peer_id);
+ while (('\n' != data[offset]) && ('|' != data[offset]) && (offset < fs))
offset++;
if ('\n' == data[offset])
state = PEER_INDEX;
}
}
status = GNUNET_OK;
-
- _exit:
+
+_exit:
GNUNET_free (data);
if (GNUNET_OK != status)
{
LOG (GNUNET_ERROR_TYPE_WARNING,
- "Removing and link data read from the file\n");
+ "Removing link data read from the file\n");
tc->link_array_size = 0;
- GNUNET_free_non_null (tc->link_array);
- tc->link_array = NULL;
+ switch (tc->type)
+ {
+ case TOPOLOGYCONTEXT_TYPE_OVERLAY:
+ {
+ struct TopologyContextOverlay *overlay;
+
+ overlay = &tc->u.overlay;
+ GNUNET_free_non_null (overlay->link_array);
+ overlay->link_array = NULL;
+ }
+ break;
+ case TOPOLOGYCONTEXT_TYPE_UNDERLAY:
+ {
+ struct TopologyContextUnderlay *underlay;
+
+ underlay = &tc->u.underlay;
+ GNUNET_free_non_null (underlay->link_array);
+ underlay->link_array = NULL;
+ }
+ break;
+ }
+ }
+}
+
+
+/**
+ * Generates clique topology
+ *
+ * @param tc the topology context
+ */
+static void
+gen_topo_clique (struct TopologyContext *tc)
+{
+ unsigned int cnt;
+ unsigned int offset;
+ unsigned int neighbour;
+
+ tc->link_array_size = tc->num_peers * (tc->num_peers - 1);
+ switch (tc->type)
+ {
+ case TOPOLOGYCONTEXT_TYPE_OVERLAY:
+ {
+ struct TopologyContextOverlay *overlay;
+
+ overlay = &tc->u.overlay;
+ overlay->link_array = GNUNET_new_array (tc->link_array_size,
+ struct OverlayLink);
+ }
+ break;
+ case TOPOLOGYCONTEXT_TYPE_UNDERLAY:
+ {
+ struct TopologyContextUnderlay *underlay;
+
+ underlay = &tc->u.underlay;
+ underlay->link_array = GNUNET_new_array (tc->link_array_size,
+ struct UnderlayLink);
+ }
+ }
+ offset = 0;
+ for (cnt = 0; cnt < tc->num_peers; cnt++)
+ {
+ for (neighbour = 0; neighbour < tc->num_peers; neighbour++)
+ {
+ if (neighbour == cnt)
+ continue;
+ make_link (offset, cnt, neighbour, tc);
+ offset++;
+ }
}
}
* Configure overall network topology to have a particular shape.
*
* @param op_cls closure argument to give with the operation event
- * @param num_peers number of peers in 'peers'
- * @param peers array of 'num_peers' with the peers to configure
+ * @param num_peers number of peers in @a peers
+ * @param peers array of @a num_peers with the peers to configure
* @param topo desired underlay topology to use
* @param ap topology-specific options
* @return handle to the operation, NULL if configuring the topology
* Configure overall network topology to have a particular shape.
*
* @param op_cls closure argument to give with the operation event
- * @param num_peers number of peers in 'peers'
- * @param peers array of 'num_peers' with the peers to configure
+ * @param num_peers number of peers in @a peers
+ * @param peers array of @a num_peers with the peers to configure
* @param topo desired underlay topology to use
* @param ... topology-specific options
* @return handle to the operation, NULL if configuring the topology
* This function then connects the given peers in the P2P overlay
* using the given topology.
*
- * @param op_cls closure argument to give with the operation event
- * @param num_peers number of peers in 'peers'
- * @param peers array of 'num_peers' with the peers to configure
+ * @param op_cls closure argument to give with the peer connect operation events
+ * generated through this function
+ * @param num_peers number of peers in @a peers
+ * @param peers array of @a num_peers with the peers to configure
* @param max_connections the maximums number of overlay connections that will
* be made to achieve the given topology
+ * @param comp_cb the completion callback to call when the topology generation
+ * is completed
+ * @param comp_cb_cls closure for the above completion callback
* @param topo desired underlay topology to use
* @param va topology-specific options
* @return handle to the operation, NULL if connecting these
unsigned int num_peers,
struct GNUNET_TESTBED_Peer **peers,
unsigned int *max_connections,
- enum GNUNET_TESTBED_TopologyOption
- topo, va_list va)
+ GNUNET_TESTBED_TopologyCompletionCallback
+ comp_cb,
+ void *comp_cb_cls,
+ enum GNUNET_TESTBED_TopologyOption topo,
+ va_list va)
{
struct TopologyContext *tc;
+ struct TopologyContextOverlay *overlay;
struct GNUNET_TESTBED_Operation *op;
struct GNUNET_TESTBED_Controller *c;
enum GNUNET_TESTBED_TopologyOption secondary_option;
- unsigned int cnt;
if (num_peers < 2)
return NULL;
c = peers[0]->controller;
- tc = GNUNET_malloc (sizeof (struct TopologyContext));
- tc->peers = peers;
+ tc = GNUNET_new (struct TopologyContext);
+ tc->type = TOPOLOGYCONTEXT_TYPE_OVERLAY;
+ overlay = &tc->u.overlay;
+ overlay->peers = peers;
tc->num_peers = num_peers;
- tc->op_cls = op_cls;
+ overlay->op_cls = op_cls;
+ overlay->retry_cnt = DEFAULT_RETRY_CNT;
+ overlay->comp_cb = comp_cb;
+ overlay->comp_cb_cls = comp_cb_cls;
switch (topo)
{
case GNUNET_TESTBED_TOPOLOGY_LINE:
gen_topo_ring (tc);
break;
case GNUNET_TESTBED_TOPOLOGY_ERDOS_RENYI:
- gen_topo_random (tc,
- va_arg (va, unsigned int),
- GNUNET_NO);
+ 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);
+ 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);
- tc->link_array = GNUNET_malloc (sizeof (struct OverlayLink) *
- tc->link_array_size);
- {
- unsigned int offset;
-
- offset = 0;
- for (cnt=0; cnt < num_peers; cnt++)
- {
- unsigned int neighbour;
-
- for (neighbour=0; neighbour < num_peers; neighbour++)
- {
- if (neighbour == cnt)
- continue;
- tc->link_array[offset].A = cnt;
- tc->link_array[offset].B = neighbour;
- tc->link_array[offset].tc = tc;
- offset++;
- }
- }
- }
+ gen_topo_clique (tc);
break;
case GNUNET_TESTBED_TOPOLOGY_2D_TORUS:
gen_topo_2dtorus (tc);
break;
case GNUNET_TESTBED_TOPOLOGY_SMALL_WORLD:
gen_topo_2dtorus (tc);
- gen_topo_random (tc,
- va_arg (va, unsigned int),
- GNUNET_YES);
+ gen_topo_random (tc, va_arg (va, unsigned int), GNUNET_YES);
+
break;
case GNUNET_TESTBED_TOPOLOGY_SCALE_FREE:
- gen_scale_free (tc);
- break;
- case GNUNET_TESTBED_TOPOLOGY_FROM_FILE:
{
- const char *filename;
-
- filename = va_arg (va, const char *);
- GNUNET_assert (NULL != filename);
- gen_topo_from_file (tc, filename);
+ uint16_t cap;
+ uint8_t m;
+
+ cap = (uint16_t) va_arg (va, unsigned int);
+ m = (uint8_t) va_arg (va, unsigned int);
+ gen_topo_scale_free (tc, cap, m);
}
break;
+ case GNUNET_TESTBED_TOPOLOGY_FROM_FILE:
+ {
+ const char *filename;
+
+ filename = va_arg (va, const char *);
+
+ GNUNET_assert (NULL != filename);
+ gen_topo_from_file (tc, filename);
+ }
+ break;
default:
GNUNET_break (0);
GNUNET_free (tc);
do
{
secondary_option = va_arg (va, enum GNUNET_TESTBED_TopologyOption);
+
switch (secondary_option)
{
- case GNUNET_TESTBED_TOPOLOGY_DISABLE_AUTO_RETRY:
- tc->disable_retry = GNUNET_YES;
+ case GNUNET_TESTBED_TOPOLOGY_RETRY_CNT:
+ overlay->retry_cnt = va_arg (va, unsigned int);
break;
case GNUNET_TESTBED_TOPOLOGY_OPTION_END:
break;
default:
GNUNET_break (0); /* Should not use any other option apart from
- the ones handled here */
- GNUNET_free_non_null (tc->link_array);
+ * the ones handled here */
+ GNUNET_free_non_null (overlay->link_array);
GNUNET_free (tc);
return NULL;
}
- } while (GNUNET_TESTBED_TOPOLOGY_OPTION_END != secondary_option);
+ }
+ while (GNUNET_TESTBED_TOPOLOGY_OPTION_END != secondary_option);
op = GNUNET_TESTBED_operation_create_ (tc,
- &opstart_overlay_configure_topology,
- &oprelease_overlay_configure_topology);
+ &opstart_overlay_configure_topology,
+ &oprelease_overlay_configure_topology);
GNUNET_TESTBED_operation_queue_insert_
(c->opq_parallel_topology_config_operations, op);
GNUNET_TESTBED_operation_begin_wait_ (op);
LOG (GNUNET_ERROR_TYPE_DEBUG,
- "Generated %u connections\n", tc->link_array_size);
+ "Generated %u connections\n",
+ tc->link_array_size);
if (NULL != max_connections)
*max_connections = tc->link_array_size;
return op;
* This function then connects the given peers in the P2P overlay
* using the given topology.
*
- * @param op_cls closure argument to give with the operation event
+ * @param op_cls closure argument to give with the peer connect operation events
+ * generated through this function
* @param num_peers number of peers in 'peers'
* @param peers array of 'num_peers' with the peers to configure
* @param max_connections the maximums number of overlay connections that will
* be made to achieve the given topology
+ * @param comp_cb the completion callback to call when the topology generation
+ * is completed
+ * @param comp_cb_cls closure for the above completion callback
* @param topo desired underlay topology to use
* @param ... topology-specific options
* @return handle to the operation, NULL if connecting these
* not running or underlay disallows) or if num_peers is less than 2
*/
struct GNUNET_TESTBED_Operation *
-GNUNET_TESTBED_overlay_configure_topology (void *op_cls, unsigned int num_peers,
+GNUNET_TESTBED_overlay_configure_topology (void *op_cls,
+ unsigned int num_peers,
struct GNUNET_TESTBED_Peer **peers,
unsigned int *max_connections,
- enum GNUNET_TESTBED_TopologyOption
- topo, ...)
+ GNUNET_TESTBED_TopologyCompletionCallback
+ comp_cb,
+ void *comp_cb_cls,
+ enum GNUNET_TESTBED_TopologyOption topo,
+ ...)
{
struct GNUNET_TESTBED_Operation *op;
va_list vargs;
GNUNET_assert (topo < GNUNET_TESTBED_TOPOLOGY_OPTION_END);
va_start (vargs, topo);
op = GNUNET_TESTBED_overlay_configure_topology_va (op_cls, num_peers, peers,
- max_connections,
- topo, vargs);
+ max_connections,
+ comp_cb, comp_cb_cls,
+ topo,
+ vargs);
va_end (vargs);
return op;
}
* @param topology where to write the retrieved topology
* @param topology_string The string to attempt to
* get a configuration value from
- * @return GNUNET_YES if topology string matched a
- * known topology, GNUNET_NO if not
+ * @return #GNUNET_YES if topology string matched a
+ * known topology, #GNUNET_NO if not
*/
int
GNUNET_TESTBED_topology_get_ (enum GNUNET_TESTBED_TopologyOption *topology,
const char *topology_string)
-{
+{
unsigned int cnt;
for (cnt = 0; NULL != topology_strings[cnt]; cnt++)
return GNUNET_strdup (topology_strings[topology]);
}
+
+/**
+ * Function to construct an underlay topology
+ *
+ * @param num_peers the number of peers for which the topology should be
+ * generated
+ * @param proc the underlay link processor callback. Will be called for each
+ * underlay link generated unless a previous call to this callback
+ * returned #GNUNET_SYSERR. Cannot be NULL.
+ * @param cls closure for @a proc
+ * @param ... variable arguments denoting the topology and its parameters. They
+ * should start with the type of topology to generate followed by their
+ * options.
+ * @return #GNUNET_OK if underlay link generation is successful; #GNUNET_SYSERR
+ * upon error in generating the underlay or if any calls to the
+ * underlay link processor returned #GNUNET_SYSERR
+ */
+int
+GNUNET_TESTBED_underlay_construct_ (int num_peers,
+ underlay_link_processor proc,
+ void *cls,
+ ...)
+{
+ struct TopologyContext tc;
+ struct TopologyContextUnderlay *underlay;
+ struct UnderlayLink *ulink;
+ va_list vargs;
+ enum GNUNET_TESTBED_TopologyOption topology;
+ unsigned int cnt;
+ int ret;
+
+ GNUNET_assert (NULL != proc);
+ ret = GNUNET_OK;
+ memset (&tc, 0, sizeof (tc));
+ tc.num_peers = num_peers;
+ tc.type = TOPOLOGYCONTEXT_TYPE_UNDERLAY;
+ underlay = &tc.u.underlay;
+ va_start (vargs, cls);
+ topology = va_arg (vargs, enum GNUNET_TESTBED_TopologyOption);
+ switch (topology)
+ {
+ case GNUNET_TESTBED_TOPOLOGY_LINE:
+ gen_topo_line (&tc);
+ break;
+ case GNUNET_TESTBED_TOPOLOGY_RING:
+ gen_topo_ring (&tc);
+ break;
+ case GNUNET_TESTBED_TOPOLOGY_CLIQUE:
+ gen_topo_clique (&tc);
+ break;
+ case GNUNET_TESTBED_TOPOLOGY_2D_TORUS:
+ gen_topo_2dtorus (&tc);
+ break;
+ case GNUNET_TESTBED_TOPOLOGY_ERDOS_RENYI:
+ gen_topo_random (&tc, va_arg (vargs, unsigned int), GNUNET_NO);
+ break;
+ case GNUNET_TESTBED_TOPOLOGY_SMALL_WORLD_RING:
+ gen_topo_ring (&tc);
+ gen_topo_random (&tc, va_arg (vargs, unsigned int), GNUNET_YES);
+ break;
+ case GNUNET_TESTBED_TOPOLOGY_SMALL_WORLD:
+ gen_topo_2dtorus (&tc);
+ gen_topo_random (&tc, va_arg (vargs, unsigned int), GNUNET_YES);
+ break;
+ case GNUNET_TESTBED_TOPOLOGY_FROM_FILE:
+ {
+ const char *filename;
+ filename = va_arg (vargs, char *);
+ GNUNET_assert (NULL != filename);
+ gen_topo_from_file (&tc, filename);
+ }
+ break;
+ case GNUNET_TESTBED_TOPOLOGY_SCALE_FREE:
+ {
+ uint16_t cap;
+ uint8_t m;
+ cap = (uint16_t) va_arg (vargs, unsigned int);
+ m = (uint8_t) va_arg (vargs, unsigned int);
+ gen_topo_scale_free (&tc, cap, m);
+ }
+ break;
+ default:
+ GNUNET_assert (0);
+ }
+ va_end (vargs);
+ for (cnt = 0; cnt < tc.link_array_size; cnt++)
+ {
+ ulink = &underlay->link_array[cnt];
+ if (GNUNET_SYSERR == proc (cls,
+ ulink->A,
+ ulink->B,
+ ulink->bandwidth,
+ ulink->latency,
+ ulink->loss))
+ {
+ ret = GNUNET_SYSERR;
+ break;
+ }
+ }
+ GNUNET_free_non_null (underlay->link_array);
+ return ret;
+}
+
/* end of testbed_api_topology.c */
projects / oweals / gnunet.git / blobdiff