2 This file is part of GNUnet
3 Copyright (C) 2008--2013 GNUnet e.V.
5 GNUnet is free software; you can redistribute it and/or modify
6 it under the terms of the GNU General Public License as published
7 by the Free Software Foundation; either version 3, or (at your
8 option) any later version.
10 GNUnet is distributed in the hope that it will be useful, but
11 WITHOUT ANY WARRANTY; without even the implied warranty of
12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
13 General Public License for more details.
15 You should have received a copy of the GNU General Public License
16 along with GNUnet; see the file COPYING. If not, write to the
17 Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
18 Boston, MA 02110-1301, USA.
22 * @file testbed/testbed_api_topology.c
23 * @brief topology-generation functions
24 * @author Christian Grothoff
27 #include "gnunet_testbed_service.h"
28 #include "testbed_api.h"
29 #include "testbed_api_peers.h"
30 #include "testbed_api_operations.h"
31 #include "testbed_api_topology.h"
34 * Generic loggins shorthand
36 #define LOG(kind,...) \
37 GNUNET_log_from (kind, "testbed-api-topology", __VA_ARGS__)
41 * Default number of retires
43 #define DEFAULT_RETRY_CNT 3
47 * Context information for topology operations
49 struct TopologyContext;
53 * Representation of an overlay link
59 * An operation corresponding to this link
61 struct GNUNET_TESTBED_Operation *op;
64 * The topology context this link is a part of
66 struct TopologyContext *tc;
69 * position of peer A's handle in peers array
74 * position of peer B's handle in peers array
82 * Representation of an underlay link
87 * position of peer A's handle in peers array
92 * position of peer B's handle in peers array
97 * Bandwidth of the link in bytes per second
102 * Latency of the link in milliseconds
107 * Loss in the link in percentage of message dropped
113 struct RetryListEntry
116 * the next pointer for the DLL
118 struct RetryListEntry *next;
121 * the prev pointer for the DLL
123 struct RetryListEntry *prev;
126 * The link to be retired
128 struct OverlayLink *link;
133 * Context information for overlay topologies
135 struct TopologyContextOverlay
140 struct GNUNET_TESTBED_Peer **peers;
143 * An array of links; this array is of size link_array_size
145 struct OverlayLink *link_array;
148 * The operation closure
153 * topology generation completion callback
155 GNUNET_TESTBED_TopologyCompletionCallback comp_cb;
158 * The closure for the above callback
163 * DLL head for retry list
165 struct RetryListEntry *rl_head;
168 * DLL tail for retry list
170 struct RetryListEntry *rl_tail;
173 * How many retries to do before we give up
175 unsigned int retry_cnt;
178 * Number of links to try
183 * How many links have been completed
185 unsigned int ncompleted;
188 * Total successfully established overlay connections
190 unsigned int nsuccess;
193 * Total failed overlay connections
195 unsigned int nfailures;
200 * Topology context information for underlay topologies
202 struct TopologyContextUnderlay
207 struct UnderlayLink *link_array;
212 * Context information for topology operations
214 struct TopologyContext
217 * The type of this context
222 * Type for underlay topology
224 TOPOLOGYCONTEXT_TYPE_UNDERLAY = 0,
227 * Type for overlay topology
229 TOPOLOGYCONTEXT_TYPE_OVERLAY
236 * Topology context information for overlay topology
238 struct TopologyContextOverlay overlay;
241 * Topology context information for underlay topology
243 struct TopologyContextUnderlay underlay;
247 * The number of peers
249 unsigned int num_peers;
252 * The size of the link array
254 unsigned int link_array_size;
260 * A array of names representing topologies. Should be in sync with enum
261 * GNUNET_TESTBED_TopologyOption
263 static const char *topology_strings[] = {
266 * A clique (everyone connected to everyone else). No options. If there are N
267 * peers this topology results in (N * (N -1)) connections.
272 * Small-world network (2d torus plus random links). Followed
273 * by the number of random links to add (unsigned int).
278 * Small-world network (ring plus random links). Followed
279 * by the number of random links to add (unsigned int).
284 * Ring topology. No options.
289 * Star topology. No options.
294 * 2-d torus. No options.
299 * Random graph. Followed by the number of random links to be established
302 "RANDOM", // GNUNET_TESTBED_TOPOLOGY_ERDOS_RENYI
305 * Certain percentage of peers are unable to communicate directly
306 * replicating NAT conditions. Followed by the fraction of
307 * NAT'ed peers (float).
312 * Scale free topology. Followed by the maximum number of links a node can
313 * have (unsigned int); and the number of links a new node should have when
314 * it is added to the network (unsigned int)
319 * Straight line topology. No options.
324 * Read a topology from a given file. Followed by the name of the file (const char *).
329 * All peers are disconnected. No options.
341 * Callback to be called when an overlay_link operation complete
343 * @param cls element of the link_op array which points to the corresponding operation
344 * @param op the operation that has been finished
345 * @param emsg error message in case the operation has failed; will be NULL if
346 * operation has executed successfully.
349 overlay_link_completed (void *cls,
350 struct GNUNET_TESTBED_Operation *op,
353 struct OverlayLink *link = cls;
354 struct TopologyContext *tc;
355 struct TopologyContextOverlay *overlay;
356 struct RetryListEntry *retry_entry;
358 GNUNET_assert (op == link->op);
359 GNUNET_TESTBED_operation_done (op);
362 GNUNET_assert (TOPOLOGYCONTEXT_TYPE_OVERLAY == tc->type);
363 overlay = &tc->u.overlay;
366 overlay->nfailures++;
367 if (0 != overlay->retry_cnt)
369 LOG (GNUNET_ERROR_TYPE_WARNING,
370 "Error while establishing a link: %s -- Retrying\n",
372 retry_entry = GNUNET_new (struct RetryListEntry);
373 retry_entry->link = link;
374 GNUNET_CONTAINER_DLL_insert_tail (overlay->rl_head,
381 overlay->ncompleted++;
382 if (overlay->ncompleted < overlay->nlinks)
384 if ((0 != overlay->retry_cnt) && (NULL != overlay->rl_head))
386 overlay->retry_cnt--;
387 overlay->ncompleted = 0;
389 while (NULL != (retry_entry = overlay->rl_head))
391 link = retry_entry->link;
393 GNUNET_TESTBED_overlay_connect (overlay->op_cls,
394 &overlay_link_completed,
396 overlay->peers[link->A],
397 overlay->peers[link->B]);
399 GNUNET_CONTAINER_DLL_remove (overlay->rl_head,
402 GNUNET_free (retry_entry);
406 if (NULL != overlay->comp_cb)
408 overlay->comp_cb (overlay->comp_cb_cls,
417 * Function called when a overlay connect operation is ready
419 * @param cls the Topology context
422 opstart_overlay_configure_topology (void *cls)
424 struct TopologyContext *tc = cls;
425 struct TopologyContextOverlay *overlay;
428 GNUNET_assert (TOPOLOGYCONTEXT_TYPE_OVERLAY == tc->type);
429 overlay = &tc->u.overlay;
430 overlay->nlinks = tc->link_array_size;
431 for (p = 0; p < tc->link_array_size; p++)
433 overlay->link_array[p].op =
434 GNUNET_TESTBED_overlay_connect (overlay->op_cls,
435 &overlay_link_completed,
436 &overlay->link_array[p],
437 overlay->peers[overlay->link_array[p].A],
438 overlay->peers[overlay->link_array[p].B]);
444 * Callback which will be called when overlay connect operation is released
446 * @param cls the Topology context
449 oprelease_overlay_configure_topology (void *cls)
451 struct TopologyContext *tc = cls;
452 struct TopologyContextOverlay *overlay;
453 struct RetryListEntry *retry_entry;
456 GNUNET_assert (TOPOLOGYCONTEXT_TYPE_OVERLAY == tc->type);
457 overlay = &tc->u.overlay;
458 while (NULL != (retry_entry = overlay->rl_head))
460 GNUNET_CONTAINER_DLL_remove (overlay->rl_head, overlay->rl_tail, retry_entry);
461 GNUNET_free (retry_entry);
463 if (NULL != overlay->link_array)
465 for (p = 0; p < tc->link_array_size; p++)
466 if (NULL != overlay->link_array[p].op)
467 GNUNET_TESTBED_operation_done (overlay->link_array[p].op);
468 GNUNET_free (overlay->link_array);
475 * Populates the OverlayLink structure.
477 * @param offset the offset of the link array to use
478 * @param A the peer A. Should be different from B
479 * @param B the peer B. Should be different from A
480 * @param tc the TopologyContext
484 make_link (unsigned int offset,
487 struct TopologyContext *tc)
489 GNUNET_assert (A != B);
492 case TOPOLOGYCONTEXT_TYPE_OVERLAY:
494 struct TopologyContextOverlay *overlay;
495 struct OverlayLink *olink;
497 overlay = &tc->u.overlay;
498 GNUNET_assert (offset < tc->link_array_size);
499 olink = &overlay->link_array[offset];
500 LOG (GNUNET_ERROR_TYPE_DEBUG, "Connecting peer %u to %u\n", B, A);
507 case TOPOLOGYCONTEXT_TYPE_UNDERLAY:
509 struct TopologyContextUnderlay *underlay;
510 struct UnderlayLink *ulink;
512 underlay = &tc->u.underlay;
513 GNUNET_assert (offset < tc->link_array_size);
514 ulink = &underlay->link_array[offset];
524 * Generates line topology
526 * @param tc the topology context
529 gen_topo_line (struct TopologyContext *tc)
533 tc->link_array_size = tc->num_peers - 1;
536 case TOPOLOGYCONTEXT_TYPE_OVERLAY:
538 struct TopologyContextOverlay *overlay;
540 overlay = &tc->u.overlay;
541 overlay->link_array =
542 GNUNET_new_array (tc->link_array_size,
546 case TOPOLOGYCONTEXT_TYPE_UNDERLAY:
548 struct TopologyContextUnderlay *underlay;
550 underlay = &tc->u.underlay;
551 underlay->link_array =
552 GNUNET_new_array (tc->link_array_size,
553 struct UnderlayLink);
557 for (cnt = 0; cnt < (tc->link_array_size); cnt++)
558 make_link (cnt, cnt, cnt + 1, tc);
563 * Generates star topology
565 * @param tc the topology context
568 gen_topo_star (struct TopologyContext *tc)
572 tc->link_array_size = tc->num_peers - 1;
575 case TOPOLOGYCONTEXT_TYPE_OVERLAY:
577 struct TopologyContextOverlay *overlay;
579 overlay = &tc->u.overlay;
580 overlay->link_array =
581 GNUNET_new_array (tc->link_array_size,
585 case TOPOLOGYCONTEXT_TYPE_UNDERLAY:
587 struct TopologyContextUnderlay *underlay;
589 underlay = &tc->u.underlay;
590 underlay->link_array =
591 GNUNET_new_array (tc->link_array_size,
592 struct UnderlayLink);
596 for (cnt = tc->link_array_size; cnt; cnt--)
605 * Generates ring topology
607 * @param tc the topology context
610 gen_topo_ring (struct TopologyContext *tc)
613 tc->link_array_size++;
616 case TOPOLOGYCONTEXT_TYPE_OVERLAY:
618 struct TopologyContextOverlay *overlay;
620 overlay = &tc->u.overlay;
621 overlay->link_array =
622 GNUNET_realloc (overlay->link_array, sizeof (struct OverlayLink) *
623 tc->link_array_size);
626 case TOPOLOGYCONTEXT_TYPE_UNDERLAY:
628 struct TopologyContextUnderlay *underlay;
630 underlay = &tc->u.underlay;
631 underlay->link_array =
632 GNUNET_realloc (underlay->link_array, sizeof (struct UnderlayLink) *
633 tc->link_array_size);
637 make_link (tc->link_array_size - 1, tc->num_peers - 1, 0, tc);
642 * Returns the number of links that are required to generate a 2d torus for the
643 * given number of peers. Also returns the arrangment (number of rows and the
644 * length of each row)
646 * @param num_peers number of peers
647 * @param rows number of rows in the 2d torus. Can be NULL
648 * @param rows_len the length of each row. This array will be allocated
649 * fresh. The caller should free it. Can be NULL
650 * @return the number of links that are required to generate a 2d torus for the
651 * given number of peers
654 GNUNET_TESTBED_2dtorus_calc_links (unsigned int num_peers, unsigned int *rows,
655 unsigned int **rows_len)
658 unsigned int sq_floor;
660 unsigned int *_rows_len;
663 unsigned int _num_peers;
666 sq = sqrt (num_peers);
668 sq_floor = (unsigned int) sq;
669 _rows = (sq_floor + 1);
670 _rows_len = GNUNET_malloc (sizeof (unsigned int) * _rows);
671 for (y = 0; y < _rows - 1; y++)
672 _rows_len[y] = sq_floor;
673 _num_peers = sq_floor * sq_floor;
674 cnt = (_num_peers < 2) ? _num_peers : 2 * _num_peers;
677 while (_num_peers < num_peers)
680 _rows_len[_rows - 1] = ++x;
685 cnt += (x < 2) ? x : 2 * x;
686 cnt += (y < 2) ? y : 2 * y;
687 if (0 == _rows_len[_rows - 1])
691 if (NULL != rows_len)
692 *rows_len = _rows_len;
694 GNUNET_free (_rows_len);
700 * Generates ring topology
702 * @param tc the topology context
705 gen_topo_2dtorus (struct TopologyContext *tc)
708 unsigned int *rows_len;
714 tc->link_array_size =
715 GNUNET_TESTBED_2dtorus_calc_links (tc->num_peers, &rows, &rows_len);
718 case TOPOLOGYCONTEXT_TYPE_OVERLAY:
720 struct TopologyContextOverlay *overlay;
722 overlay = &tc->u.overlay;
723 overlay->link_array =
724 GNUNET_malloc (sizeof (struct OverlayLink) * tc->link_array_size);
727 case TOPOLOGYCONTEXT_TYPE_UNDERLAY:
729 struct TopologyContextUnderlay *underlay;
731 underlay = &tc->u.underlay;
732 underlay->link_array =
733 GNUNET_malloc (sizeof (struct UnderlayLink) * tc->link_array_size);
739 for (y = 0; y < rows; y++)
741 for (x = 0; x < rows_len[y] - 1; x++)
743 make_link (cnt, offset + x, offset + x + 1, tc);
748 make_link (cnt, offset + x, offset, tc);
750 offset += rows_len[y];
752 for (x = 0; x < rows_len[0]; x++)
755 for (y = 0; y < rows - 1; y++)
757 if (x >= rows_len[y + 1])
759 GNUNET_assert (x < rows_len[y + 1]);
760 make_link (cnt, offset + x, offset + rows_len[y] + x, tc);
761 offset += rows_len[y];
766 make_link (cnt, offset + x, x, tc);
769 GNUNET_assert (cnt == tc->link_array_size);
770 GNUNET_free (rows_len);
775 * Generates ring topology
777 * @param tc the topology context
778 * @param links the number of random links to establish
779 * @param append #GNUNET_YES to add links to existing link array; #GNUNET_NO to
780 * create a new link array
783 gen_topo_random (struct TopologyContext *tc,
792 if (1 == tc->num_peers)
794 if (GNUNET_YES == append)
796 index = tc->link_array_size;
797 tc->link_array_size += links;
802 tc->link_array_size = links;
806 case TOPOLOGYCONTEXT_TYPE_OVERLAY:
808 struct TopologyContextOverlay *overlay;
810 overlay = &tc->u.overlay;
811 if (GNUNET_YES != append)
813 GNUNET_assert (NULL == overlay->link_array);
814 overlay->link_array =
815 GNUNET_malloc (sizeof (struct OverlayLink) * tc->link_array_size);
818 GNUNET_assert ((0 < tc->link_array_size) && (NULL != overlay->link_array));
819 overlay->link_array =
820 GNUNET_realloc (overlay->link_array,
821 sizeof (struct OverlayLink) * tc->link_array_size);
824 case TOPOLOGYCONTEXT_TYPE_UNDERLAY:
826 struct TopologyContextUnderlay *underlay;
828 underlay = &tc->u.underlay;
829 if (GNUNET_YES != append)
831 GNUNET_assert (NULL == underlay->link_array);
832 underlay->link_array =
833 GNUNET_malloc (sizeof (struct UnderlayLink) * tc->link_array_size);
836 GNUNET_assert ((0 < tc->link_array_size) && (NULL != underlay->link_array));
837 underlay->link_array =
838 GNUNET_realloc (underlay->link_array,
839 sizeof (struct UnderlayLink) * tc->link_array_size);
843 for (cnt = 0; cnt < links; cnt++)
848 GNUNET_CRYPTO_random_u32 (GNUNET_CRYPTO_QUALITY_WEAK, tc->num_peers);
850 GNUNET_CRYPTO_random_u32 (GNUNET_CRYPTO_QUALITY_WEAK, tc->num_peers);
852 while (A_rand == B_rand);
853 make_link (index+cnt, A_rand, B_rand, tc);
859 * Generates scale free network. Its construction is described in:
861 * "Emergence of Scaling in Random Networks." Science 286, 509-512, 1999.
863 * @param tc the topology context
864 * @param cap maximum allowed node degree
865 * @param m number of edges to establish for a new node when it is added to the
869 gen_topo_scale_free (struct TopologyContext *tc,
876 unsigned int etaboff;
880 unsigned int random_peer;
883 unsigned int redo_threshold;
886 tc->link_array_size = tc->num_peers * m;
889 case TOPOLOGYCONTEXT_TYPE_OVERLAY:
891 struct TopologyContextOverlay *overlay;
893 overlay = &tc->u.overlay;
894 overlay->link_array = GNUNET_malloc_large (sizeof (struct OverlayLink) *
895 tc->link_array_size);
898 case TOPOLOGYCONTEXT_TYPE_UNDERLAY:
900 struct TopologyContextUnderlay *underlay;
902 underlay = &tc->u.underlay;
903 underlay->link_array = GNUNET_malloc_large (sizeof (struct UnderlayLink) *
904 tc->link_array_size);
908 etab = GNUNET_malloc_large (sizeof (unsigned int) * 2 * tc->link_array_size);
909 deg = GNUNET_malloc (sizeof (unsigned int) * tc->num_peers);
910 used = GNUNET_malloc (sizeof (unsigned int) * m);
911 /* start by connecting peer 1 to peer 0 */
912 make_link (0, 0, 1, tc);
918 for (peer = 2; peer < tc->num_peers; peer++)
922 for (cnt = 0; cnt < GNUNET_MIN (peer, m); cnt++)
926 off = GNUNET_CRYPTO_random_u64 (GNUNET_CRYPTO_QUALITY_WEAK, etaboff);
927 random_peer = etab[off];
928 if (cap < deg[random_peer])
930 if (++redo_threshold > GNUNET_MAX (1, cap / 2))
934 for (cnt2 = 0; cnt2 < etaboff; cnt2++)
936 if (random_peer == etab[cnt2])
941 etab[cnt2 - off] = etab[cnt2];
947 for (cnt2 = 0; cnt2 < cnt; cnt2++)
948 if (random_peer == used[cnt2])
950 make_link (links + cnt, random_peer, peer, tc);
953 used[cnt] = random_peer;
955 for (cnt = 0; cnt < GNUNET_MIN (peer, m); cnt++)
957 etab[etaboff++] = used[cnt];
958 etab[etaboff++] = peer;
960 links += GNUNET_MIN (peer, m);
965 GNUNET_assert (links <= tc->link_array_size);
966 tc->link_array_size = links;
969 case TOPOLOGYCONTEXT_TYPE_OVERLAY:
971 struct TopologyContextOverlay *overlay;
973 overlay = &tc->u.overlay;
974 overlay->link_array =
975 GNUNET_realloc (overlay->link_array, sizeof (struct OverlayLink) * tc->link_array_size);
978 case TOPOLOGYCONTEXT_TYPE_UNDERLAY:
980 struct TopologyContextUnderlay *underlay;
982 underlay = &tc->u.underlay;
983 underlay->link_array =
984 GNUNET_realloc (underlay->link_array, sizeof (struct UnderlayLink) * tc->link_array_size);
992 * Generates topology from the given file
994 * @param tc the topology context
995 * @param filename the filename of the file containing topology data
998 gen_topo_from_file (struct TopologyContext *tc,
999 const char *filename)
1006 unsigned long int peer_id;
1007 unsigned long int other_peer_id;
1012 * We read the peer index
1017 * We read the other peer indices
1024 status = GNUNET_SYSERR;
1025 if (GNUNET_YES != GNUNET_DISK_file_test (filename))
1027 LOG (GNUNET_ERROR_TYPE_ERROR,
1028 _("Topology file %s not found\n"),
1033 GNUNET_DISK_file_size (filename, &fs, GNUNET_YES, GNUNET_YES))
1035 LOG (GNUNET_ERROR_TYPE_ERROR,
1036 _("Topology file %s has no data\n"),
1040 data = GNUNET_malloc (fs);
1041 if (fs != GNUNET_DISK_fn_read (filename, data, fs))
1043 LOG (GNUNET_ERROR_TYPE_ERROR,
1044 _("Topology file %s cannot be read\n"),
1054 if (0 != isspace (data[offset]))
1062 buf = strchr (&data[offset], ':');
1065 LOG (GNUNET_ERROR_TYPE_ERROR,
1066 _("Failed to read peer index from toology file: %s"), filename);
1071 peer_id = (unsigned int) strtoul (&data[offset], &end, 10);
1074 LOG (GNUNET_ERROR_TYPE_ERROR,
1075 _("Value in given topology file: %s out of range\n"), filename);
1078 if (&data[offset] == end)
1080 LOG (GNUNET_ERROR_TYPE_ERROR,
1081 _("Failed to read peer index from topology file: %s"), filename);
1084 if (tc->num_peers <= peer_id)
1086 LOG (GNUNET_ERROR_TYPE_ERROR,
1087 _("Topology file needs more peers than given ones\n"), filename);
1090 state = OTHER_PEER_INDEX;
1091 offset += ((unsigned int) (buf - &data[offset])) + 1;
1093 case OTHER_PEER_INDEX:
1095 other_peer_id = (unsigned int) strtoul (&data[offset], &end, 10);
1098 LOG (GNUNET_ERROR_TYPE_ERROR,
1099 _("Value in given topology file: %s out of range\n"), filename);
1102 if (&data[offset] == end)
1104 LOG (GNUNET_ERROR_TYPE_ERROR,
1105 _("Failed to read peer index from topology file: %s"), filename);
1108 if (tc->num_peers <= other_peer_id)
1110 LOG (GNUNET_ERROR_TYPE_ERROR,
1111 _("Topology file needs more peers than given ones\n"), filename);
1114 if (peer_id != other_peer_id)
1116 tc->link_array_size++;
1119 case TOPOLOGYCONTEXT_TYPE_OVERLAY:
1121 struct TopologyContextOverlay *overlay;
1123 overlay = &tc->u.overlay;
1124 overlay->link_array =
1125 GNUNET_realloc (overlay->link_array,
1126 sizeof (struct OverlayLink) * tc->link_array_size);
1129 case TOPOLOGYCONTEXT_TYPE_UNDERLAY:
1131 struct TopologyContextUnderlay *underlay;
1133 underlay = &tc->u.underlay;
1134 underlay->link_array =
1135 GNUNET_realloc (underlay->link_array,
1136 sizeof (struct UnderlayLink) * tc->link_array_size);
1140 offset += end - &data[offset];
1141 make_link (tc->link_array_size - 1, peer_id, other_peer_id, tc);
1144 LOG (GNUNET_ERROR_TYPE_WARNING,
1145 _("Ignoring to connect peer %u to peer %u\n"),
1148 while (('\n' != data[offset]) && ('|' != data[offset]) && (offset < fs))
1150 if ( (offset < fs) &&
1151 ('\n' == data[offset]) )
1153 else if ( (offset < fs) &&
1154 ('|' == data[offset]) )
1156 state = OTHER_PEER_INDEX;
1166 if (GNUNET_OK != status)
1168 LOG (GNUNET_ERROR_TYPE_WARNING,
1169 "Removing link data read from the file\n");
1170 tc->link_array_size = 0;
1173 case TOPOLOGYCONTEXT_TYPE_OVERLAY:
1175 struct TopologyContextOverlay *overlay;
1177 overlay = &tc->u.overlay;
1178 GNUNET_free_non_null (overlay->link_array);
1179 overlay->link_array = NULL;
1182 case TOPOLOGYCONTEXT_TYPE_UNDERLAY:
1184 struct TopologyContextUnderlay *underlay;
1186 underlay = &tc->u.underlay;
1187 GNUNET_free_non_null (underlay->link_array);
1188 underlay->link_array = NULL;
1197 * Generates clique topology
1199 * @param tc the topology context
1202 gen_topo_clique (struct TopologyContext *tc)
1205 unsigned int offset;
1206 unsigned int neighbour;
1208 tc->link_array_size = tc->num_peers * (tc->num_peers - 1);
1211 case TOPOLOGYCONTEXT_TYPE_OVERLAY:
1213 struct TopologyContextOverlay *overlay;
1215 overlay = &tc->u.overlay;
1216 overlay->link_array = GNUNET_new_array (tc->link_array_size,
1217 struct OverlayLink);
1220 case TOPOLOGYCONTEXT_TYPE_UNDERLAY:
1222 struct TopologyContextUnderlay *underlay;
1224 underlay = &tc->u.underlay;
1225 underlay->link_array = GNUNET_new_array (tc->link_array_size,
1226 struct UnderlayLink);
1230 for (cnt = 0; cnt < tc->num_peers; cnt++)
1232 for (neighbour = 0; neighbour < tc->num_peers; neighbour++)
1234 if (neighbour == cnt)
1236 make_link (offset, cnt, neighbour, tc);
1244 * Configure overall network topology to have a particular shape.
1246 * @param op_cls closure argument to give with the operation event
1247 * @param num_peers number of peers in @a peers
1248 * @param peers array of @a num_peers with the peers to configure
1249 * @param topo desired underlay topology to use
1250 * @param ap topology-specific options
1251 * @return handle to the operation, NULL if configuring the topology
1252 * is not allowed at this time
1254 struct GNUNET_TESTBED_Operation *
1255 GNUNET_TESTBED_underlay_configure_topology_va (void *op_cls,
1256 unsigned int num_peers,
1257 struct GNUNET_TESTBED_Peer
1260 GNUNET_TESTBED_TopologyOption
1269 * Configure overall network topology to have a particular shape.
1271 * @param op_cls closure argument to give with the operation event
1272 * @param num_peers number of peers in @a peers
1273 * @param peers array of @a num_peers with the peers to configure
1274 * @param topo desired underlay topology to use
1275 * @param ... topology-specific options
1276 * @return handle to the operation, NULL if configuring the topology
1277 * is not allowed at this time
1279 struct GNUNET_TESTBED_Operation *
1280 GNUNET_TESTBED_underlay_configure_topology (void *op_cls,
1281 unsigned int num_peers,
1282 struct GNUNET_TESTBED_Peer **peers,
1283 enum GNUNET_TESTBED_TopologyOption
1292 * All peers must have been started before calling this function.
1293 * This function then connects the given peers in the P2P overlay
1294 * using the given topology.
1296 * @param op_cls closure argument to give with the peer connect operation events
1297 * generated through this function
1298 * @param num_peers number of peers in @a peers
1299 * @param peers array of @a num_peers with the peers to configure
1300 * @param max_connections the maximums number of overlay connections that will
1301 * be made to achieve the given topology
1302 * @param comp_cb the completion callback to call when the topology generation
1304 * @param comp_cb_cls closure for the above completion callback
1305 * @param topo desired underlay topology to use
1306 * @param va topology-specific options
1307 * @return handle to the operation, NULL if connecting these
1308 * peers is fundamentally not possible at this time (peers
1309 * not running or underlay disallows) or if num_peers is less than 2
1311 struct GNUNET_TESTBED_Operation *
1312 GNUNET_TESTBED_overlay_configure_topology_va (void *op_cls,
1313 unsigned int num_peers,
1314 struct GNUNET_TESTBED_Peer **peers,
1315 unsigned int *max_connections,
1316 GNUNET_TESTBED_TopologyCompletionCallback
1319 enum GNUNET_TESTBED_TopologyOption topo,
1322 struct TopologyContext *tc;
1323 struct TopologyContextOverlay *overlay;
1324 struct GNUNET_TESTBED_Operation *op;
1325 struct GNUNET_TESTBED_Controller *c;
1326 enum GNUNET_TESTBED_TopologyOption secondary_option;
1330 c = peers[0]->controller;
1331 tc = GNUNET_new (struct TopologyContext);
1332 tc->type = TOPOLOGYCONTEXT_TYPE_OVERLAY;
1333 overlay = &tc->u.overlay;
1334 overlay->peers = peers;
1335 tc->num_peers = num_peers;
1336 overlay->op_cls = op_cls;
1337 overlay->retry_cnt = DEFAULT_RETRY_CNT;
1338 overlay->comp_cb = comp_cb;
1339 overlay->comp_cb_cls = comp_cb_cls;
1342 case GNUNET_TESTBED_TOPOLOGY_LINE:
1345 case GNUNET_TESTBED_TOPOLOGY_STAR:
1348 case GNUNET_TESTBED_TOPOLOGY_RING:
1351 case GNUNET_TESTBED_TOPOLOGY_ERDOS_RENYI:
1352 gen_topo_random (tc, va_arg (va, unsigned int), GNUNET_NO);
1354 case GNUNET_TESTBED_TOPOLOGY_SMALL_WORLD_RING:
1356 gen_topo_random (tc, va_arg (va, unsigned int), GNUNET_YES);
1358 case GNUNET_TESTBED_TOPOLOGY_CLIQUE:
1359 gen_topo_clique (tc);
1361 case GNUNET_TESTBED_TOPOLOGY_2D_TORUS:
1362 gen_topo_2dtorus (tc);
1364 case GNUNET_TESTBED_TOPOLOGY_SMALL_WORLD:
1365 gen_topo_2dtorus (tc);
1366 gen_topo_random (tc, va_arg (va, unsigned int), GNUNET_YES);
1369 case GNUNET_TESTBED_TOPOLOGY_SCALE_FREE:
1374 cap = (uint16_t) va_arg (va, unsigned int);
1375 m = (uint8_t) va_arg (va, unsigned int);
1376 gen_topo_scale_free (tc, cap, m);
1379 case GNUNET_TESTBED_TOPOLOGY_FROM_FILE:
1381 const char *filename;
1383 filename = va_arg (va, const char *);
1385 GNUNET_assert (NULL != filename);
1386 gen_topo_from_file (tc, filename);
1396 secondary_option = va_arg (va, enum GNUNET_TESTBED_TopologyOption);
1398 switch (secondary_option)
1400 case GNUNET_TESTBED_TOPOLOGY_RETRY_CNT:
1401 overlay->retry_cnt = va_arg (va, unsigned int);
1403 case GNUNET_TESTBED_TOPOLOGY_OPTION_END:
1406 GNUNET_break (0); /* Should not use any other option apart from
1407 * the ones handled here */
1408 GNUNET_free_non_null (overlay->link_array);
1413 while (GNUNET_TESTBED_TOPOLOGY_OPTION_END != secondary_option);
1414 op = GNUNET_TESTBED_operation_create_ (tc,
1415 &opstart_overlay_configure_topology,
1416 &oprelease_overlay_configure_topology);
1417 GNUNET_TESTBED_operation_queue_insert_
1418 (c->opq_parallel_topology_config_operations, op);
1419 GNUNET_TESTBED_operation_begin_wait_ (op);
1420 LOG (GNUNET_ERROR_TYPE_DEBUG,
1421 "Generated %u connections\n",
1422 tc->link_array_size);
1423 if (NULL != max_connections)
1424 *max_connections = tc->link_array_size;
1430 * All peers must have been started before calling this function.
1431 * This function then connects the given peers in the P2P overlay
1432 * using the given topology.
1434 * @param op_cls closure argument to give with the peer connect operation events
1435 * generated through this function
1436 * @param num_peers number of peers in 'peers'
1437 * @param peers array of 'num_peers' with the peers to configure
1438 * @param max_connections the maximums number of overlay connections that will
1439 * be made to achieve the given topology
1440 * @param comp_cb the completion callback to call when the topology generation
1442 * @param comp_cb_cls closure for the above completion callback
1443 * @param topo desired underlay topology to use
1444 * @param ... topology-specific options
1445 * @return handle to the operation, NULL if connecting these
1446 * peers is fundamentally not possible at this time (peers
1447 * not running or underlay disallows) or if num_peers is less than 2
1449 struct GNUNET_TESTBED_Operation *
1450 GNUNET_TESTBED_overlay_configure_topology (void *op_cls,
1451 unsigned int num_peers,
1452 struct GNUNET_TESTBED_Peer **peers,
1453 unsigned int *max_connections,
1454 GNUNET_TESTBED_TopologyCompletionCallback
1457 enum GNUNET_TESTBED_TopologyOption topo,
1460 struct GNUNET_TESTBED_Operation *op;
1463 GNUNET_assert (topo < GNUNET_TESTBED_TOPOLOGY_OPTION_END);
1464 va_start (vargs, topo);
1465 op = GNUNET_TESTBED_overlay_configure_topology_va (op_cls, num_peers, peers,
1467 comp_cb, comp_cb_cls,
1476 * Get a topology from a string input.
1478 * @param topology where to write the retrieved topology
1479 * @param topology_string The string to attempt to
1480 * get a configuration value from
1481 * @return #GNUNET_YES if topology string matched a
1482 * known topology, #GNUNET_NO if not
1485 GNUNET_TESTBED_topology_get_ (enum GNUNET_TESTBED_TopologyOption *topology,
1486 const char *topology_string)
1490 for (cnt = 0; NULL != topology_strings[cnt]; cnt++)
1492 if (0 == strcasecmp (topology_string, topology_strings[cnt]))
1494 if (NULL != topology)
1495 *topology = (enum GNUNET_TESTBED_TopologyOption) cnt;
1496 GNUNET_assert (GNUNET_TESTBED_TOPOLOGY_OPTION_END != (enum GNUNET_TESTBED_TopologyOption) cnt);
1505 * Returns the string corresponding to the given topology
1507 * @param topology the topology
1508 * @return the string (freshly allocated) of given topology; NULL if topology cannot be
1509 * expressed as a string
1512 GNUNET_TESTBED_topology_to_str_ (enum GNUNET_TESTBED_TopologyOption topology)
1514 if (GNUNET_TESTBED_TOPOLOGY_OPTION_END <= topology)
1516 return GNUNET_strdup (topology_strings[topology]);
1521 * Function to construct an underlay topology
1523 * @param num_peers the number of peers for which the topology should be
1525 * @param proc the underlay link processor callback. Will be called for each
1526 * underlay link generated unless a previous call to this callback
1527 * returned #GNUNET_SYSERR. Cannot be NULL.
1528 * @param cls closure for @a proc
1529 * @param ... variable arguments denoting the topology and its parameters. They
1530 * should start with the type of topology to generate followed by their
1532 * @return #GNUNET_OK if underlay link generation is successful; #GNUNET_SYSERR
1533 * upon error in generating the underlay or if any calls to the
1534 * underlay link processor returned #GNUNET_SYSERR
1537 GNUNET_TESTBED_underlay_construct_ (int num_peers,
1538 underlay_link_processor proc,
1542 struct TopologyContext tc;
1543 struct TopologyContextUnderlay *underlay;
1544 struct UnderlayLink *ulink;
1546 enum GNUNET_TESTBED_TopologyOption topology;
1550 GNUNET_assert (NULL != proc);
1552 memset (&tc, 0, sizeof (tc));
1553 tc.num_peers = num_peers;
1554 tc.type = TOPOLOGYCONTEXT_TYPE_UNDERLAY;
1555 underlay = &tc.u.underlay;
1556 va_start (vargs, cls);
1557 topology = va_arg (vargs, enum GNUNET_TESTBED_TopologyOption);
1560 case GNUNET_TESTBED_TOPOLOGY_LINE:
1561 gen_topo_line (&tc);
1563 case GNUNET_TESTBED_TOPOLOGY_STAR:
1564 gen_topo_star (&tc);
1566 case GNUNET_TESTBED_TOPOLOGY_RING:
1567 gen_topo_ring (&tc);
1569 case GNUNET_TESTBED_TOPOLOGY_CLIQUE:
1570 gen_topo_clique (&tc);
1572 case GNUNET_TESTBED_TOPOLOGY_2D_TORUS:
1573 gen_topo_2dtorus (&tc);
1575 case GNUNET_TESTBED_TOPOLOGY_ERDOS_RENYI:
1576 gen_topo_random (&tc, va_arg (vargs, unsigned int), GNUNET_NO);
1578 case GNUNET_TESTBED_TOPOLOGY_SMALL_WORLD_RING:
1579 gen_topo_ring (&tc);
1580 gen_topo_random (&tc, va_arg (vargs, unsigned int), GNUNET_YES);
1582 case GNUNET_TESTBED_TOPOLOGY_SMALL_WORLD:
1583 gen_topo_2dtorus (&tc);
1584 gen_topo_random (&tc, va_arg (vargs, unsigned int), GNUNET_YES);
1586 case GNUNET_TESTBED_TOPOLOGY_FROM_FILE:
1588 const char *filename;
1589 filename = va_arg (vargs, char *);
1590 GNUNET_assert (NULL != filename);
1591 gen_topo_from_file (&tc, filename);
1594 case GNUNET_TESTBED_TOPOLOGY_SCALE_FREE:
1598 cap = (uint16_t) va_arg (vargs, unsigned int);
1599 m = (uint8_t) va_arg (vargs, unsigned int);
1600 gen_topo_scale_free (&tc, cap, m);
1607 for (cnt = 0; cnt < tc.link_array_size; cnt++)
1609 ulink = &underlay->link_array[cnt];
1610 if (GNUNET_SYSERR == proc (cls,
1617 ret = GNUNET_SYSERR;
1621 GNUNET_free_non_null (underlay->link_array);
1625 /* end of testbed_api_topology.c */