2 This file is part of GNUnet
3 Copyright (C) 2008--2013 Christian Grothoff (and other contributing authors)
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 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 * 2-d torus. No options.
294 * Random graph. Followed by the number of random links to be established
297 "RANDOM", // GNUNET_TESTBED_TOPOLOGY_ERDOS_RENYI
300 * Certain percentage of peers are unable to communicate directly
301 * replicating NAT conditions. Followed by the fraction of
302 * NAT'ed peers (float).
307 * Scale free topology. Followed by the maximum number of links a node can
308 * have (unsigned int); and the number of links a new node should have when
309 * it is added to the network (unsigned int)
314 * Straight line topology. No options.
319 * Read a topology from a given file. Followed by the name of the file (const char *).
324 * All peers are disconnected. No options.
336 * Callback to be called when an overlay_link operation complete
338 * @param cls element of the link_op array which points to the corresponding operation
339 * @param op the operation that has been finished
340 * @param emsg error message in case the operation has failed; will be NULL if
341 * operation has executed successfully.
344 overlay_link_completed (void *cls, struct GNUNET_TESTBED_Operation *op,
347 struct OverlayLink *link = cls;
348 struct TopologyContext *tc;
349 struct TopologyContextOverlay *overlay;
350 struct RetryListEntry *retry_entry;
352 GNUNET_assert (op == link->op);
353 GNUNET_TESTBED_operation_done (op);
356 GNUNET_assert (TOPOLOGYCONTEXT_TYPE_OVERLAY == tc->type);
357 overlay = &tc->u.overlay;
360 overlay->nfailures++;
361 if (0 != overlay->retry_cnt)
363 LOG (GNUNET_ERROR_TYPE_WARNING,
364 "Error while establishing a link: %s -- Retrying\n", emsg);
365 retry_entry = GNUNET_new (struct RetryListEntry);
366 retry_entry->link = link;
367 GNUNET_CONTAINER_DLL_insert_tail (overlay->rl_head, overlay->rl_tail, retry_entry);
372 overlay->ncompleted++;
373 if (overlay->ncompleted < overlay->nlinks)
375 if ((0 != overlay->retry_cnt) && (NULL != overlay->rl_head))
377 overlay->retry_cnt--;
378 overlay->ncompleted = 0;
380 while (NULL != (retry_entry = overlay->rl_head))
382 link = retry_entry->link;
384 GNUNET_TESTBED_overlay_connect (overlay->op_cls, &overlay_link_completed,
385 link, overlay->peers[link->A],
386 overlay->peers[link->B]);
388 GNUNET_CONTAINER_DLL_remove (overlay->rl_head, overlay->rl_tail, retry_entry);
389 GNUNET_free (retry_entry);
393 if (NULL != overlay->comp_cb)
395 overlay->comp_cb (overlay->comp_cb_cls, overlay->nsuccess, overlay->nfailures);
402 * Function called when a overlay connect operation is ready
404 * @param cls the Topology context
407 opstart_overlay_configure_topology (void *cls)
409 struct TopologyContext *tc = cls;
410 struct TopologyContextOverlay *overlay;
413 GNUNET_assert (TOPOLOGYCONTEXT_TYPE_OVERLAY == tc->type);
414 overlay = &tc->u.overlay;
415 overlay->nlinks = tc->link_array_size;
416 for (p = 0; p < tc->link_array_size; p++)
418 overlay->link_array[p].op =
419 GNUNET_TESTBED_overlay_connect (overlay->op_cls, &overlay_link_completed,
420 &overlay->link_array[p],
421 overlay->peers[overlay->link_array[p].A],
422 overlay->peers[overlay->link_array[p].B]);
428 * Callback which will be called when overlay connect operation is released
430 * @param cls the Topology context
433 oprelease_overlay_configure_topology (void *cls)
435 struct TopologyContext *tc = cls;
436 struct TopologyContextOverlay *overlay;
437 struct RetryListEntry *retry_entry;
440 GNUNET_assert (TOPOLOGYCONTEXT_TYPE_OVERLAY == tc->type);
441 overlay = &tc->u.overlay;
442 while (NULL != (retry_entry = overlay->rl_head))
444 GNUNET_CONTAINER_DLL_remove (overlay->rl_head, overlay->rl_tail, retry_entry);
445 GNUNET_free (retry_entry);
447 if (NULL != overlay->link_array)
449 for (p = 0; p < tc->link_array_size; p++)
450 if (NULL != overlay->link_array[p].op)
451 GNUNET_TESTBED_operation_done (overlay->link_array[p].op);
452 GNUNET_free (overlay->link_array);
459 * Populates the OverlayLink structure.
461 * @param offset the offset of the link array to use
462 * @param A the peer A. Should be different from B
463 * @param B the peer B. Should be different from A
464 * @param tc the TopologyContext
468 make_link (unsigned int offset, uint32_t A, uint32_t B,
469 struct TopologyContext *tc)
471 GNUNET_assert (A != B);
474 case TOPOLOGYCONTEXT_TYPE_OVERLAY:
476 struct TopologyContextOverlay *overlay;
477 struct OverlayLink *olink;
479 overlay = &tc->u.overlay;
480 GNUNET_assert (offset < tc->link_array_size);
481 olink = &overlay->link_array[offset];
482 LOG (GNUNET_ERROR_TYPE_DEBUG, "Connecting peer %u to %u\n", B, A);
489 case TOPOLOGYCONTEXT_TYPE_UNDERLAY:
491 struct TopologyContextUnderlay *underlay;
492 struct UnderlayLink *ulink;
494 underlay = &tc->u.underlay;
495 GNUNET_assert (offset < tc->link_array_size);
496 ulink = &underlay->link_array[offset];
506 * Generates line topology
508 * @param tc the topology context
511 gen_topo_line (struct TopologyContext *tc)
515 tc->link_array_size = tc->num_peers - 1;
518 case TOPOLOGYCONTEXT_TYPE_OVERLAY:
520 struct TopologyContextOverlay *overlay;
522 overlay = &tc->u.overlay;
523 overlay->link_array =
524 GNUNET_malloc (sizeof (struct OverlayLink) * tc->link_array_size);
527 case TOPOLOGYCONTEXT_TYPE_UNDERLAY:
529 struct TopologyContextUnderlay *underlay;
531 underlay = &tc->u.underlay;
532 underlay->link_array =
533 GNUNET_malloc (sizeof (struct UnderlayLink) * tc->link_array_size);
537 for (cnt = 0; cnt < (tc->link_array_size); cnt++)
538 make_link (cnt, cnt, cnt + 1, tc);
543 * Generates ring topology
545 * @param tc the topology context
548 gen_topo_ring (struct TopologyContext *tc)
551 tc->link_array_size++;
554 case TOPOLOGYCONTEXT_TYPE_OVERLAY:
556 struct TopologyContextOverlay *overlay;
558 overlay = &tc->u.overlay;
559 overlay->link_array =
560 GNUNET_realloc (overlay->link_array, sizeof (struct OverlayLink) *
561 tc->link_array_size);
564 case TOPOLOGYCONTEXT_TYPE_UNDERLAY:
566 struct TopologyContextUnderlay *underlay;
568 underlay = &tc->u.underlay;
569 underlay->link_array =
570 GNUNET_realloc (underlay->link_array, sizeof (struct UnderlayLink) *
571 tc->link_array_size);
575 make_link (tc->link_array_size - 1, tc->num_peers - 1, 0, tc);
580 * Returns the number of links that are required to generate a 2d torus for the
581 * given number of peers. Also returns the arrangment (number of rows and the
582 * length of each row)
584 * @param num_peers number of peers
585 * @param rows number of rows in the 2d torus. Can be NULL
586 * @param rows_len the length of each row. This array will be allocated
587 * fresh. The caller should free it. Can be NULL
588 * @return the number of links that are required to generate a 2d torus for the
589 * given number of peers
592 GNUNET_TESTBED_2dtorus_calc_links (unsigned int num_peers, unsigned int *rows,
593 unsigned int **rows_len)
596 unsigned int sq_floor;
598 unsigned int *_rows_len;
601 unsigned int _num_peers;
604 sq = sqrt (num_peers);
606 sq_floor = (unsigned int) sq;
607 _rows = (sq_floor + 1);
608 _rows_len = GNUNET_malloc (sizeof (unsigned int) * _rows);
609 for (y = 0; y < _rows - 1; y++)
610 _rows_len[y] = sq_floor;
611 _num_peers = sq_floor * sq_floor;
612 cnt = (_num_peers < 2) ? _num_peers : 2 * _num_peers;
615 while (_num_peers < num_peers)
618 _rows_len[_rows - 1] = ++x;
623 cnt += (x < 2) ? x : 2 * x;
624 cnt += (y < 2) ? y : 2 * y;
625 if (0 == _rows_len[_rows - 1])
629 if (NULL != rows_len)
630 *rows_len = _rows_len;
632 GNUNET_free (_rows_len);
638 * Generates ring topology
640 * @param tc the topology context
643 gen_topo_2dtorus (struct TopologyContext *tc)
646 unsigned int *rows_len;
652 tc->link_array_size =
653 GNUNET_TESTBED_2dtorus_calc_links (tc->num_peers, &rows, &rows_len);
656 case TOPOLOGYCONTEXT_TYPE_OVERLAY:
658 struct TopologyContextOverlay *overlay;
660 overlay = &tc->u.overlay;
661 overlay->link_array =
662 GNUNET_malloc (sizeof (struct OverlayLink) * tc->link_array_size);
665 case TOPOLOGYCONTEXT_TYPE_UNDERLAY:
667 struct TopologyContextUnderlay *underlay;
669 underlay = &tc->u.underlay;
670 underlay->link_array =
671 GNUNET_malloc (sizeof (struct UnderlayLink) * tc->link_array_size);
677 for (y = 0; y < rows; y++)
679 for (x = 0; x < rows_len[y] - 1; x++)
681 make_link (cnt, offset + x, offset + x + 1, tc);
686 make_link (cnt, offset + x, offset, tc);
688 offset += rows_len[y];
690 for (x = 0; x < rows_len[0]; x++)
693 for (y = 0; y < rows - 1; y++)
695 if (x >= rows_len[y + 1])
697 GNUNET_assert (x < rows_len[y + 1]);
698 make_link (cnt, offset + x, offset + rows_len[y] + x, tc);
699 offset += rows_len[y];
704 make_link (cnt, offset + x, x, tc);
707 GNUNET_assert (cnt == tc->link_array_size);
708 GNUNET_free (rows_len);
713 * Generates ring topology
715 * @param tc the topology context
716 * @param links the number of random links to establish
717 * @param append #GNUNET_YES to add links to existing link array; #GNUNET_NO to
718 * create a new link array
721 gen_topo_random (struct TopologyContext *tc,
730 if (1 == tc->num_peers)
732 if (GNUNET_YES == append)
734 index = tc->link_array_size;
735 tc->link_array_size += links;
740 tc->link_array_size = links;
744 case TOPOLOGYCONTEXT_TYPE_OVERLAY:
746 struct TopologyContextOverlay *overlay;
748 overlay = &tc->u.overlay;
749 if (GNUNET_YES != append)
751 GNUNET_assert (NULL == overlay->link_array);
752 overlay->link_array =
753 GNUNET_malloc (sizeof (struct OverlayLink) * tc->link_array_size);
756 GNUNET_assert ((0 < tc->link_array_size) && (NULL != overlay->link_array));
757 overlay->link_array =
758 GNUNET_realloc (overlay->link_array,
759 sizeof (struct OverlayLink) * tc->link_array_size);
762 case TOPOLOGYCONTEXT_TYPE_UNDERLAY:
764 struct TopologyContextUnderlay *underlay;
766 underlay = &tc->u.underlay;
767 if (GNUNET_YES != append)
769 GNUNET_assert (NULL == underlay->link_array);
770 underlay->link_array =
771 GNUNET_malloc (sizeof (struct UnderlayLink) * tc->link_array_size);
774 GNUNET_assert ((0 < tc->link_array_size) && (NULL != underlay->link_array));
775 underlay->link_array =
776 GNUNET_realloc (underlay->link_array,
777 sizeof (struct UnderlayLink) * tc->link_array_size);
781 for (cnt = 0; cnt < links; cnt++)
786 GNUNET_CRYPTO_random_u32 (GNUNET_CRYPTO_QUALITY_WEAK, tc->num_peers);
788 GNUNET_CRYPTO_random_u32 (GNUNET_CRYPTO_QUALITY_WEAK, tc->num_peers);
790 while (A_rand == B_rand);
791 make_link (index+cnt, A_rand, B_rand, tc);
797 * Generates scale free network. Its construction is described in:
799 * "Emergence of Scaling in Random Networks." Science 286, 509-512, 1999.
801 * @param tc the topology context
802 * @param cap maximum allowed node degree
803 * @param m number of edges to establish for a new node when it is added to the
807 gen_topo_scale_free (struct TopologyContext *tc,
814 unsigned int etaboff;
818 unsigned int random_peer;
821 unsigned int redo_threshold;
824 tc->link_array_size = tc->num_peers * m;
827 case TOPOLOGYCONTEXT_TYPE_OVERLAY:
829 struct TopologyContextOverlay *overlay;
831 overlay = &tc->u.overlay;
832 overlay->link_array = GNUNET_malloc_large (sizeof (struct OverlayLink) *
833 tc->link_array_size);
836 case TOPOLOGYCONTEXT_TYPE_UNDERLAY:
838 struct TopologyContextUnderlay *underlay;
840 underlay = &tc->u.underlay;
841 underlay->link_array = GNUNET_malloc_large (sizeof (struct UnderlayLink) *
842 tc->link_array_size);
846 etab = GNUNET_malloc_large (sizeof (unsigned int) * 2 * tc->link_array_size);
847 deg = GNUNET_malloc (sizeof (unsigned int) * tc->num_peers);
848 used = GNUNET_malloc (sizeof (unsigned int) * m);
849 /* start by connecting peer 1 to peer 0 */
850 make_link (0, 0, 1, tc);
856 for (peer = 2; peer < tc->num_peers; peer++)
860 for (cnt = 0; cnt < GNUNET_MIN (peer, m); cnt++)
864 off = GNUNET_CRYPTO_random_u64 (GNUNET_CRYPTO_QUALITY_WEAK, etaboff);
865 random_peer = etab[off];
866 if (cap < deg[random_peer])
868 if (++redo_threshold > GNUNET_MAX (1, cap / 2))
872 for (cnt2 = 0; cnt2 < etaboff; cnt2++)
874 if (random_peer == etab[cnt2])
879 etab[cnt2 - off] = etab[cnt2];
885 for (cnt2 = 0; cnt2 < cnt; cnt2++)
886 if (random_peer == used[cnt2])
888 make_link (links + cnt, random_peer, peer, tc);
891 used[cnt] = random_peer;
893 for (cnt = 0; cnt < GNUNET_MIN (peer, m); cnt++)
895 etab[etaboff++] = used[cnt];
896 etab[etaboff++] = peer;
898 links += GNUNET_MIN (peer, m);
903 GNUNET_assert (links <= tc->link_array_size);
904 tc->link_array_size = links;
907 case TOPOLOGYCONTEXT_TYPE_OVERLAY:
909 struct TopologyContextOverlay *overlay;
911 overlay = &tc->u.overlay;
912 overlay->link_array =
913 GNUNET_realloc (overlay->link_array, sizeof (struct OverlayLink) * tc->link_array_size);
916 case TOPOLOGYCONTEXT_TYPE_UNDERLAY:
918 struct TopologyContextUnderlay *underlay;
920 underlay = &tc->u.underlay;
921 underlay->link_array =
922 GNUNET_realloc (underlay->link_array, sizeof (struct UnderlayLink) * tc->link_array_size);
930 * Generates topology from the given file
932 * @param tc the topology context
933 * @param filename the filename of the file containing topology data
936 gen_topo_from_file (struct TopologyContext *tc,
937 const char *filename)
944 unsigned long int peer_id;
945 unsigned long int other_peer_id;
950 * We read the peer index
955 * We read the other peer indices
962 status = GNUNET_SYSERR;
963 if (GNUNET_YES != GNUNET_DISK_file_test (filename))
965 LOG (GNUNET_ERROR_TYPE_ERROR,
966 _("Topology file %s not found\n"),
971 GNUNET_DISK_file_size (filename, &fs, GNUNET_YES, GNUNET_YES))
973 LOG (GNUNET_ERROR_TYPE_ERROR,
974 _("Topology file %s has no data\n"),
978 data = GNUNET_malloc (fs);
979 if (fs != GNUNET_DISK_fn_read (filename, data, fs))
981 LOG (GNUNET_ERROR_TYPE_ERROR,
982 _("Topology file %s cannot be read\n"),
992 if (0 != isspace (data[offset]))
1000 buf = strchr (&data[offset], ':');
1003 LOG (GNUNET_ERROR_TYPE_ERROR,
1004 _("Failed to read peer index from toology file: %s"), filename);
1009 peer_id = (unsigned int) strtoul (&data[offset], &end, 10);
1012 LOG (GNUNET_ERROR_TYPE_ERROR,
1013 _("Value in given topology file: %s out of range\n"), filename);
1016 if (&data[offset] == end)
1018 LOG (GNUNET_ERROR_TYPE_ERROR,
1019 _("Failed to read peer index from topology file: %s"), filename);
1022 if (tc->num_peers <= peer_id)
1024 LOG (GNUNET_ERROR_TYPE_ERROR,
1025 _("Topology file needs more peers than given ones\n"), filename);
1028 state = OTHER_PEER_INDEX;
1029 offset += ((unsigned int) (buf - &data[offset])) + 1;
1031 case OTHER_PEER_INDEX:
1033 other_peer_id = (unsigned int) strtoul (&data[offset], &end, 10);
1036 LOG (GNUNET_ERROR_TYPE_ERROR,
1037 _("Value in given topology file: %s out of range\n"), filename);
1040 if (&data[offset] == end)
1042 LOG (GNUNET_ERROR_TYPE_ERROR,
1043 _("Failed to read peer index from topology file: %s"), filename);
1046 if (tc->num_peers <= other_peer_id)
1048 LOG (GNUNET_ERROR_TYPE_ERROR,
1049 _("Topology file needs more peers than given ones\n"), filename);
1052 if (peer_id != other_peer_id)
1054 tc->link_array_size++;
1057 case TOPOLOGYCONTEXT_TYPE_OVERLAY:
1059 struct TopologyContextOverlay *overlay;
1061 overlay = &tc->u.overlay;
1062 overlay->link_array =
1063 GNUNET_realloc (overlay->link_array,
1064 sizeof (struct OverlayLink) * tc->link_array_size);
1067 case TOPOLOGYCONTEXT_TYPE_UNDERLAY:
1069 struct TopologyContextUnderlay *underlay;
1071 underlay = &tc->u.underlay;
1072 underlay->link_array =
1073 GNUNET_realloc (underlay->link_array,
1074 sizeof (struct UnderlayLink) * tc->link_array_size);
1078 offset += end - &data[offset];
1079 make_link (tc->link_array_size - 1, peer_id, other_peer_id, tc);
1082 LOG (GNUNET_ERROR_TYPE_WARNING,
1083 _("Ignoring to connect peer %u to peer %u\n"),
1086 while (('\n' != data[offset]) && ('|' != data[offset]) && (offset < fs))
1088 if ('\n' == data[offset])
1090 else if ('|' == data[offset])
1092 state = OTHER_PEER_INDEX;
1102 if (GNUNET_OK != status)
1104 LOG (GNUNET_ERROR_TYPE_WARNING,
1105 "Removing link data read from the file\n");
1106 tc->link_array_size = 0;
1109 case TOPOLOGYCONTEXT_TYPE_OVERLAY:
1111 struct TopologyContextOverlay *overlay;
1113 overlay = &tc->u.overlay;
1114 GNUNET_free_non_null (overlay->link_array);
1115 overlay->link_array = NULL;
1118 case TOPOLOGYCONTEXT_TYPE_UNDERLAY:
1120 struct TopologyContextUnderlay *underlay;
1122 underlay = &tc->u.underlay;
1123 GNUNET_free_non_null (underlay->link_array);
1124 underlay->link_array = NULL;
1133 * Generates clique topology
1135 * @param tc the topology context
1138 gen_topo_clique (struct TopologyContext *tc)
1141 unsigned int offset;
1142 unsigned int neighbour;
1144 tc->link_array_size = tc->num_peers * (tc->num_peers - 1);
1147 case TOPOLOGYCONTEXT_TYPE_OVERLAY:
1149 struct TopologyContextOverlay *overlay;
1151 overlay = &tc->u.overlay;
1152 overlay->link_array = GNUNET_new_array (tc->link_array_size,
1153 struct OverlayLink);
1156 case TOPOLOGYCONTEXT_TYPE_UNDERLAY:
1158 struct TopologyContextUnderlay *underlay;
1160 underlay = &tc->u.underlay;
1161 underlay->link_array = GNUNET_new_array (tc->link_array_size,
1162 struct UnderlayLink);
1166 for (cnt = 0; cnt < tc->num_peers; cnt++)
1168 for (neighbour = 0; neighbour < tc->num_peers; neighbour++)
1170 if (neighbour == cnt)
1172 make_link (offset, cnt, neighbour, tc);
1180 * Configure overall network topology to have a particular shape.
1182 * @param op_cls closure argument to give with the operation event
1183 * @param num_peers number of peers in @a peers
1184 * @param peers array of @a num_peers with the peers to configure
1185 * @param topo desired underlay topology to use
1186 * @param ap topology-specific options
1187 * @return handle to the operation, NULL if configuring the topology
1188 * is not allowed at this time
1190 struct GNUNET_TESTBED_Operation *
1191 GNUNET_TESTBED_underlay_configure_topology_va (void *op_cls,
1192 unsigned int num_peers,
1193 struct GNUNET_TESTBED_Peer
1196 GNUNET_TESTBED_TopologyOption
1205 * Configure overall network topology to have a particular shape.
1207 * @param op_cls closure argument to give with the operation event
1208 * @param num_peers number of peers in @a peers
1209 * @param peers array of @a num_peers with the peers to configure
1210 * @param topo desired underlay topology to use
1211 * @param ... topology-specific options
1212 * @return handle to the operation, NULL if configuring the topology
1213 * is not allowed at this time
1215 struct GNUNET_TESTBED_Operation *
1216 GNUNET_TESTBED_underlay_configure_topology (void *op_cls,
1217 unsigned int num_peers,
1218 struct GNUNET_TESTBED_Peer **peers,
1219 enum GNUNET_TESTBED_TopologyOption
1228 * All peers must have been started before calling this function.
1229 * This function then connects the given peers in the P2P overlay
1230 * using the given topology.
1232 * @param op_cls closure argument to give with the peer connect operation events
1233 * generated through this function
1234 * @param num_peers number of peers in @a peers
1235 * @param peers array of @a num_peers with the peers to configure
1236 * @param max_connections the maximums number of overlay connections that will
1237 * be made to achieve the given topology
1238 * @param comp_cb the completion callback to call when the topology generation
1240 * @param comp_cb_cls closure for the above completion callback
1241 * @param topo desired underlay topology to use
1242 * @param va topology-specific options
1243 * @return handle to the operation, NULL if connecting these
1244 * peers is fundamentally not possible at this time (peers
1245 * not running or underlay disallows) or if num_peers is less than 2
1247 struct GNUNET_TESTBED_Operation *
1248 GNUNET_TESTBED_overlay_configure_topology_va (void *op_cls,
1249 unsigned int num_peers,
1250 struct GNUNET_TESTBED_Peer **peers,
1251 unsigned int *max_connections,
1252 GNUNET_TESTBED_TopologyCompletionCallback
1255 enum GNUNET_TESTBED_TopologyOption topo,
1258 struct TopologyContext *tc;
1259 struct TopologyContextOverlay *overlay;
1260 struct GNUNET_TESTBED_Operation *op;
1261 struct GNUNET_TESTBED_Controller *c;
1262 enum GNUNET_TESTBED_TopologyOption secondary_option;
1266 c = peers[0]->controller;
1267 tc = GNUNET_new (struct TopologyContext);
1268 tc->type = TOPOLOGYCONTEXT_TYPE_OVERLAY;
1269 overlay = &tc->u.overlay;
1270 overlay->peers = peers;
1271 tc->num_peers = num_peers;
1272 overlay->op_cls = op_cls;
1273 overlay->retry_cnt = DEFAULT_RETRY_CNT;
1274 overlay->comp_cb = comp_cb;
1275 overlay->comp_cb_cls = comp_cb_cls;
1278 case GNUNET_TESTBED_TOPOLOGY_LINE:
1281 case GNUNET_TESTBED_TOPOLOGY_RING:
1284 case GNUNET_TESTBED_TOPOLOGY_ERDOS_RENYI:
1285 gen_topo_random (tc, va_arg (va, unsigned int), GNUNET_NO);
1287 case GNUNET_TESTBED_TOPOLOGY_SMALL_WORLD_RING:
1289 gen_topo_random (tc, va_arg (va, unsigned int), GNUNET_YES);
1291 case GNUNET_TESTBED_TOPOLOGY_CLIQUE:
1292 gen_topo_clique (tc);
1294 case GNUNET_TESTBED_TOPOLOGY_2D_TORUS:
1295 gen_topo_2dtorus (tc);
1297 case GNUNET_TESTBED_TOPOLOGY_SMALL_WORLD:
1298 gen_topo_2dtorus (tc);
1299 gen_topo_random (tc, va_arg (va, unsigned int), GNUNET_YES);
1302 case GNUNET_TESTBED_TOPOLOGY_SCALE_FREE:
1307 cap = (uint16_t) va_arg (va, unsigned int);
1308 m = (uint8_t) va_arg (va, unsigned int);
1309 gen_topo_scale_free (tc, cap, m);
1312 case GNUNET_TESTBED_TOPOLOGY_FROM_FILE:
1314 const char *filename;
1316 filename = va_arg (va, const char *);
1318 GNUNET_assert (NULL != filename);
1319 gen_topo_from_file (tc, filename);
1329 secondary_option = va_arg (va, enum GNUNET_TESTBED_TopologyOption);
1331 switch (secondary_option)
1333 case GNUNET_TESTBED_TOPOLOGY_RETRY_CNT:
1334 overlay->retry_cnt = va_arg (va, unsigned int);
1336 case GNUNET_TESTBED_TOPOLOGY_OPTION_END:
1339 GNUNET_break (0); /* Should not use any other option apart from
1340 * the ones handled here */
1341 GNUNET_free_non_null (overlay->link_array);
1346 while (GNUNET_TESTBED_TOPOLOGY_OPTION_END != secondary_option);
1347 op = GNUNET_TESTBED_operation_create_ (tc,
1348 &opstart_overlay_configure_topology,
1349 &oprelease_overlay_configure_topology);
1350 GNUNET_TESTBED_operation_queue_insert_
1351 (c->opq_parallel_topology_config_operations, op);
1352 GNUNET_TESTBED_operation_begin_wait_ (op);
1353 LOG (GNUNET_ERROR_TYPE_DEBUG,
1354 "Generated %u connections\n",
1355 tc->link_array_size);
1356 if (NULL != max_connections)
1357 *max_connections = tc->link_array_size;
1363 * All peers must have been started before calling this function.
1364 * This function then connects the given peers in the P2P overlay
1365 * using the given topology.
1367 * @param op_cls closure argument to give with the peer connect operation events
1368 * generated through this function
1369 * @param num_peers number of peers in 'peers'
1370 * @param peers array of 'num_peers' with the peers to configure
1371 * @param max_connections the maximums number of overlay connections that will
1372 * be made to achieve the given topology
1373 * @param comp_cb the completion callback to call when the topology generation
1375 * @param comp_cb_cls closure for the above completion callback
1376 * @param topo desired underlay topology to use
1377 * @param ... topology-specific options
1378 * @return handle to the operation, NULL if connecting these
1379 * peers is fundamentally not possible at this time (peers
1380 * not running or underlay disallows) or if num_peers is less than 2
1382 struct GNUNET_TESTBED_Operation *
1383 GNUNET_TESTBED_overlay_configure_topology (void *op_cls,
1384 unsigned int num_peers,
1385 struct GNUNET_TESTBED_Peer **peers,
1386 unsigned int *max_connections,
1387 GNUNET_TESTBED_TopologyCompletionCallback
1390 enum GNUNET_TESTBED_TopologyOption topo,
1393 struct GNUNET_TESTBED_Operation *op;
1396 GNUNET_assert (topo < GNUNET_TESTBED_TOPOLOGY_OPTION_END);
1397 va_start (vargs, topo);
1398 op = GNUNET_TESTBED_overlay_configure_topology_va (op_cls, num_peers, peers,
1400 comp_cb, comp_cb_cls,
1409 * Get a topology from a string input.
1411 * @param topology where to write the retrieved topology
1412 * @param topology_string The string to attempt to
1413 * get a configuration value from
1414 * @return #GNUNET_YES if topology string matched a
1415 * known topology, #GNUNET_NO if not
1418 GNUNET_TESTBED_topology_get_ (enum GNUNET_TESTBED_TopologyOption *topology,
1419 const char *topology_string)
1423 for (cnt = 0; NULL != topology_strings[cnt]; cnt++)
1425 if (0 == strcasecmp (topology_string, topology_strings[cnt]))
1427 if (NULL != topology)
1428 *topology = (enum GNUNET_TESTBED_TopologyOption) cnt;
1437 * Returns the string corresponding to the given topology
1439 * @param topology the topology
1440 * @return the string (freshly allocated) of given topology; NULL if topology cannot be
1441 * expressed as a string
1444 GNUNET_TESTBED_topology_to_str_ (enum GNUNET_TESTBED_TopologyOption topology)
1446 if (GNUNET_TESTBED_TOPOLOGY_OPTION_END <= topology)
1448 return GNUNET_strdup (topology_strings[topology]);
1453 * Function to construct an underlay topology
1455 * @param num_peers the number of peers for which the topology should be
1457 * @param proc the underlay link processor callback. Will be called for each
1458 * underlay link generated unless a previous call to this callback
1459 * returned #GNUNET_SYSERR. Cannot be NULL.
1460 * @param cls closure for @a proc
1461 * @param ... variable arguments denoting the topology and its parameters. They
1462 * should start with the type of topology to generate followed by their
1464 * @return #GNUNET_OK if underlay link generation is successful; #GNUNET_SYSERR
1465 * upon error in generating the underlay or if any calls to the
1466 * underlay link processor returned #GNUNET_SYSERR
1469 GNUNET_TESTBED_underlay_construct_ (int num_peers,
1470 underlay_link_processor proc,
1474 struct TopologyContext tc;
1475 struct TopologyContextUnderlay *underlay;
1476 struct UnderlayLink *ulink;
1478 enum GNUNET_TESTBED_TopologyOption topology;
1482 GNUNET_assert (NULL != proc);
1484 memset (&tc, 0, sizeof (tc));
1485 tc.num_peers = num_peers;
1486 tc.type = TOPOLOGYCONTEXT_TYPE_UNDERLAY;
1487 underlay = &tc.u.underlay;
1488 va_start (vargs, cls);
1489 topology = va_arg (vargs, enum GNUNET_TESTBED_TopologyOption);
1492 case GNUNET_TESTBED_TOPOLOGY_LINE:
1493 gen_topo_line (&tc);
1495 case GNUNET_TESTBED_TOPOLOGY_RING:
1496 gen_topo_ring (&tc);
1498 case GNUNET_TESTBED_TOPOLOGY_CLIQUE:
1499 gen_topo_clique (&tc);
1501 case GNUNET_TESTBED_TOPOLOGY_2D_TORUS:
1502 gen_topo_2dtorus (&tc);
1504 case GNUNET_TESTBED_TOPOLOGY_ERDOS_RENYI:
1505 gen_topo_random (&tc, va_arg (vargs, unsigned int), GNUNET_NO);
1507 case GNUNET_TESTBED_TOPOLOGY_SMALL_WORLD_RING:
1508 gen_topo_ring (&tc);
1509 gen_topo_random (&tc, va_arg (vargs, unsigned int), GNUNET_YES);
1511 case GNUNET_TESTBED_TOPOLOGY_SMALL_WORLD:
1512 gen_topo_2dtorus (&tc);
1513 gen_topo_random (&tc, va_arg (vargs, unsigned int), GNUNET_YES);
1515 case GNUNET_TESTBED_TOPOLOGY_FROM_FILE:
1517 const char *filename;
1518 filename = va_arg (vargs, char *);
1519 GNUNET_assert (NULL != filename);
1520 gen_topo_from_file (&tc, filename);
1523 case GNUNET_TESTBED_TOPOLOGY_SCALE_FREE:
1527 cap = (uint16_t) va_arg (vargs, unsigned int);
1528 m = (uint8_t) va_arg (vargs, unsigned int);
1529 gen_topo_scale_free (&tc, cap, m);
1536 for (cnt = 0; cnt < tc.link_array_size; cnt++)
1538 ulink = &underlay->link_array[cnt];
1539 if (GNUNET_SYSERR == proc (cls,
1546 ret = GNUNET_SYSERR;
1550 GNUNET_free_non_null (underlay->link_array);
1554 /* end of testbed_api_topology.c */