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 it
6 under the terms of the GNU Affero General Public License as published
7 by the Free Software Foundation, either version 3 of the License,
8 or (at your 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 Affero General Public License for more details.
15 You should have received a copy of the GNU Affero General Public License
16 along with this program. If not, see <http://www.gnu.org/licenses/>.
18 SPDX-License-Identifier: AGPL3.0-or-later
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
58 * An operation corresponding to this link
60 struct GNUNET_TESTBED_Operation *op;
63 * The topology context this link is a part of
65 struct TopologyContext *tc;
68 * position of peer A's handle in peers array
73 * position of peer B's handle in peers array
80 * Representation of an underlay link
85 * position of peer A's handle in peers array
90 * position of peer B's handle in peers array
95 * Bandwidth of the link in bytes per second
100 * Latency of the link in milliseconds
105 * Loss in the link in percentage of message dropped
111 struct RetryListEntry
114 * the next pointer for the DLL
116 struct RetryListEntry *next;
119 * the prev pointer for the DLL
121 struct RetryListEntry *prev;
124 * The link to be retired
126 struct OverlayLink *link;
131 * Context information for overlay topologies
133 struct TopologyContextOverlay
138 struct GNUNET_TESTBED_Peer **peers;
141 * An array of links; this array is of size link_array_size
143 struct OverlayLink *link_array;
146 * The operation closure
151 * topology generation completion callback
153 GNUNET_TESTBED_TopologyCompletionCallback comp_cb;
156 * The closure for the above callback
161 * DLL head for retry list
163 struct RetryListEntry *rl_head;
166 * DLL tail for retry list
168 struct RetryListEntry *rl_tail;
171 * How many retries to do before we give up
173 unsigned int retry_cnt;
176 * Number of links to try
181 * How many links have been completed
183 unsigned int ncompleted;
186 * Total successfully established overlay connections
188 unsigned int nsuccess;
191 * Total failed overlay connections
193 unsigned int nfailures;
198 * Topology context information for underlay topologies
200 struct TopologyContextUnderlay
205 struct UnderlayLink *link_array;
210 * Context information for topology operations
212 struct TopologyContext
215 * The type of this context
220 * Type for underlay topology
222 TOPOLOGYCONTEXT_TYPE_UNDERLAY = 0,
225 * Type for overlay topology
227 TOPOLOGYCONTEXT_TYPE_OVERLAY
233 * Topology context information for overlay topology
235 struct TopologyContextOverlay overlay;
238 * Topology context information for underlay topology
240 struct TopologyContextUnderlay underlay;
244 * The number of peers
246 unsigned int num_peers;
249 * The size of the link array
251 unsigned int link_array_size;
256 * A array of names representing topologies. Should be in sync with enum
257 * GNUNET_TESTBED_TopologyOption
259 static const char *topology_strings[] = {
261 * A clique (everyone connected to everyone else). No options. If there are N
262 * peers this topology results in (N * (N -1)) connections.
267 * Small-world network (2d torus plus random links). Followed
268 * by the number of random links to add (unsigned int).
273 * Small-world network (ring plus random links). Followed
274 * by the number of random links to add (unsigned int).
279 * Ring topology. No options.
284 * Star 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,
345 struct GNUNET_TESTBED_Operation *op,
348 struct OverlayLink *link = cls;
349 struct TopologyContext *tc;
350 struct TopologyContextOverlay *overlay;
351 struct RetryListEntry *retry_entry;
353 GNUNET_assert (op == link->op);
354 GNUNET_TESTBED_operation_done (op);
357 GNUNET_assert (TOPOLOGYCONTEXT_TYPE_OVERLAY == tc->type);
358 overlay = &tc->u.overlay;
361 overlay->nfailures++;
362 if (0 != overlay->retry_cnt)
364 LOG (GNUNET_ERROR_TYPE_WARNING,
365 "Error while establishing a link: %s -- Retrying\n",
367 retry_entry = GNUNET_new (struct RetryListEntry);
368 retry_entry->link = link;
369 GNUNET_CONTAINER_DLL_insert_tail (overlay->rl_head,
376 overlay->ncompleted++;
377 if (overlay->ncompleted < overlay->nlinks)
379 if ((0 != overlay->retry_cnt) && (NULL != overlay->rl_head))
381 overlay->retry_cnt--;
382 overlay->ncompleted = 0;
384 while (NULL != (retry_entry = overlay->rl_head))
386 link = retry_entry->link;
388 GNUNET_TESTBED_overlay_connect (overlay->op_cls,
389 &overlay_link_completed,
391 overlay->peers[link->A],
392 overlay->peers[link->B]);
394 GNUNET_CONTAINER_DLL_remove (overlay->rl_head,
397 GNUNET_free (retry_entry);
401 if (NULL != overlay->comp_cb)
403 overlay->comp_cb (overlay->comp_cb_cls,
411 * Function called when a overlay connect operation is ready
413 * @param cls the Topology context
416 opstart_overlay_configure_topology (void *cls)
418 struct TopologyContext *tc = cls;
419 struct TopologyContextOverlay *overlay;
422 GNUNET_assert (TOPOLOGYCONTEXT_TYPE_OVERLAY == tc->type);
423 overlay = &tc->u.overlay;
424 overlay->nlinks = tc->link_array_size;
425 for (p = 0; p < tc->link_array_size; p++)
427 overlay->link_array[p].op =
428 GNUNET_TESTBED_overlay_connect (overlay->op_cls,
429 &overlay_link_completed,
430 &overlay->link_array[p],
431 overlay->peers[overlay->link_array[p].A],
432 overlay->peers[overlay->link_array[p].B]);
438 * Callback which will be called when overlay connect operation is released
440 * @param cls the Topology context
443 oprelease_overlay_configure_topology (void *cls)
445 struct TopologyContext *tc = cls;
446 struct TopologyContextOverlay *overlay;
447 struct RetryListEntry *retry_entry;
450 GNUNET_assert (TOPOLOGYCONTEXT_TYPE_OVERLAY == tc->type);
451 overlay = &tc->u.overlay;
452 while (NULL != (retry_entry = overlay->rl_head))
454 GNUNET_CONTAINER_DLL_remove (overlay->rl_head, overlay->rl_tail,
456 GNUNET_free (retry_entry);
458 if (NULL != overlay->link_array)
460 for (p = 0; p < tc->link_array_size; p++)
461 if (NULL != overlay->link_array[p].op)
462 GNUNET_TESTBED_operation_done (overlay->link_array[p].op);
463 GNUNET_free (overlay->link_array);
470 * Populates the OverlayLink structure.
472 * @param offset the offset of the link array to use
473 * @param A the peer A. Should be different from B
474 * @param B the peer B. Should be different from A
475 * @param tc the TopologyContext
479 make_link (unsigned int offset,
482 struct TopologyContext *tc)
484 GNUNET_assert (A != B);
487 case TOPOLOGYCONTEXT_TYPE_OVERLAY:
489 struct TopologyContextOverlay *overlay;
490 struct OverlayLink *olink;
492 overlay = &tc->u.overlay;
493 GNUNET_assert (offset < tc->link_array_size);
494 olink = &overlay->link_array[offset];
495 LOG (GNUNET_ERROR_TYPE_DEBUG, "Connecting peer %u to %u\n", B, A);
503 case TOPOLOGYCONTEXT_TYPE_UNDERLAY:
505 struct TopologyContextUnderlay *underlay;
506 struct UnderlayLink *ulink;
508 underlay = &tc->u.underlay;
509 GNUNET_assert (offset < tc->link_array_size);
510 ulink = &underlay->link_array[offset];
520 * Generates line topology
522 * @param tc the topology context
525 gen_topo_line (struct TopologyContext *tc)
529 tc->link_array_size = tc->num_peers - 1;
532 case TOPOLOGYCONTEXT_TYPE_OVERLAY:
534 struct TopologyContextOverlay *overlay;
536 overlay = &tc->u.overlay;
537 overlay->link_array =
538 GNUNET_new_array (tc->link_array_size,
543 case TOPOLOGYCONTEXT_TYPE_UNDERLAY:
545 struct TopologyContextUnderlay *underlay;
547 underlay = &tc->u.underlay;
548 underlay->link_array =
549 GNUNET_new_array (tc->link_array_size,
550 struct UnderlayLink);
554 for (cnt = 0; cnt < (tc->link_array_size); cnt++)
555 make_link (cnt, cnt, cnt + 1, tc);
560 * Generates star topology
562 * @param tc the topology context
565 gen_topo_star (struct TopologyContext *tc)
569 tc->link_array_size = tc->num_peers - 1;
572 case TOPOLOGYCONTEXT_TYPE_OVERLAY:
574 struct TopologyContextOverlay *overlay;
576 overlay = &tc->u.overlay;
577 overlay->link_array =
578 GNUNET_new_array (tc->link_array_size,
583 case TOPOLOGYCONTEXT_TYPE_UNDERLAY:
585 struct TopologyContextUnderlay *underlay;
587 underlay = &tc->u.underlay;
588 underlay->link_array =
589 GNUNET_new_array (tc->link_array_size,
590 struct UnderlayLink);
594 for (cnt = tc->link_array_size; cnt; cnt--)
603 * Generates ring topology
605 * @param tc the topology context
608 gen_topo_ring (struct TopologyContext *tc)
611 tc->link_array_size++;
614 case TOPOLOGYCONTEXT_TYPE_OVERLAY:
616 struct TopologyContextOverlay *overlay;
618 overlay = &tc->u.overlay;
619 overlay->link_array =
620 GNUNET_realloc (overlay->link_array, sizeof(struct OverlayLink)
621 * tc->link_array_size);
625 case TOPOLOGYCONTEXT_TYPE_UNDERLAY:
627 struct TopologyContextUnderlay *underlay;
629 underlay = &tc->u.underlay;
630 underlay->link_array =
631 GNUNET_realloc (underlay->link_array, sizeof(struct UnderlayLink)
632 * tc->link_array_size);
636 make_link (tc->link_array_size - 1, tc->num_peers - 1, 0, tc);
641 * Returns the number of links that are required to generate a 2d torus for the
642 * given number of peers. Also returns the arrangment (number of rows and the
643 * length of each row)
645 * @param num_peers number of peers
646 * @param rows number of rows in the 2d torus. Can be NULL
647 * @param rows_len the length of each row. This array will be allocated
648 * fresh. The caller should free it. Can be NULL
649 * @return the number of links that are required to generate a 2d torus for the
650 * given number of peers
653 GNUNET_TESTBED_2dtorus_calc_links (unsigned int num_peers, unsigned int *rows,
654 unsigned int **rows_len)
657 unsigned int sq_floor;
659 unsigned int *_rows_len;
662 unsigned int _num_peers;
665 sq = sqrt (num_peers);
667 sq_floor = (unsigned int) sq;
668 _rows = (sq_floor + 1);
669 _rows_len = GNUNET_malloc (sizeof(unsigned int) * _rows);
670 for (y = 0; y < _rows - 1; y++)
671 _rows_len[y] = sq_floor;
672 _num_peers = sq_floor * sq_floor;
673 cnt = (_num_peers < 2) ? _num_peers : 2 * _num_peers;
676 while (_num_peers < num_peers)
679 _rows_len[_rows - 1] = ++x;
684 cnt += (x < 2) ? x : 2 * x;
685 cnt += (y < 2) ? y : 2 * y;
686 if (0 == _rows_len[_rows - 1])
690 if (NULL != rows_len)
691 *rows_len = _rows_len;
693 GNUNET_free (_rows_len);
699 * Generates ring topology
701 * @param tc the topology context
704 gen_topo_2dtorus (struct TopologyContext *tc)
707 unsigned int *rows_len;
713 tc->link_array_size =
714 GNUNET_TESTBED_2dtorus_calc_links (tc->num_peers, &rows, &rows_len);
717 case TOPOLOGYCONTEXT_TYPE_OVERLAY:
719 struct TopologyContextOverlay *overlay;
721 overlay = &tc->u.overlay;
722 overlay->link_array =
723 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 !=
819 overlay->link_array));
820 overlay->link_array =
821 GNUNET_realloc (overlay->link_array,
822 sizeof(struct OverlayLink) * tc->link_array_size);
826 case TOPOLOGYCONTEXT_TYPE_UNDERLAY:
828 struct TopologyContextUnderlay *underlay;
830 underlay = &tc->u.underlay;
831 if (GNUNET_YES != append)
833 GNUNET_assert (NULL == underlay->link_array);
834 underlay->link_array =
835 GNUNET_malloc (sizeof(struct UnderlayLink) * tc->link_array_size);
838 GNUNET_assert ((0 < tc->link_array_size) && (NULL !=
839 underlay->link_array));
840 underlay->link_array =
841 GNUNET_realloc (underlay->link_array,
842 sizeof(struct UnderlayLink) * tc->link_array_size);
846 for (cnt = 0; cnt < links; cnt++)
851 GNUNET_CRYPTO_random_u32 (GNUNET_CRYPTO_QUALITY_WEAK, tc->num_peers);
853 GNUNET_CRYPTO_random_u32 (GNUNET_CRYPTO_QUALITY_WEAK, tc->num_peers);
855 while (A_rand == B_rand);
856 make_link (index + cnt, A_rand, B_rand, tc);
862 * Generates scale free network. Its construction is described in:
864 * "Emergence of Scaling in Random Networks." Science 286, 509-512, 1999.
866 * @param tc the topology context
867 * @param cap maximum allowed node degree
868 * @param m number of edges to establish for a new node when it is added to the
872 gen_topo_scale_free (struct TopologyContext *tc,
879 unsigned int etaboff;
883 unsigned int random_peer;
886 unsigned int redo_threshold;
889 tc->link_array_size = tc->num_peers * m;
892 case TOPOLOGYCONTEXT_TYPE_OVERLAY:
894 struct TopologyContextOverlay *overlay;
896 overlay = &tc->u.overlay;
897 overlay->link_array = GNUNET_malloc_large (sizeof(struct OverlayLink)
898 * tc->link_array_size);
902 case TOPOLOGYCONTEXT_TYPE_UNDERLAY:
904 struct TopologyContextUnderlay *underlay;
906 underlay = &tc->u.underlay;
907 underlay->link_array = GNUNET_malloc_large (sizeof(struct UnderlayLink)
908 * tc->link_array_size);
912 etab = GNUNET_malloc_large (sizeof(unsigned int) * 2 * tc->link_array_size);
913 deg = GNUNET_malloc (sizeof(unsigned int) * tc->num_peers);
914 used = GNUNET_malloc (sizeof(unsigned int) * m);
915 /* start by connecting peer 1 to peer 0 */
916 make_link (0, 0, 1, tc);
922 for (peer = 2; peer < tc->num_peers; peer++)
926 for (cnt = 0; cnt < GNUNET_MIN (peer, m); cnt++)
930 off = GNUNET_CRYPTO_random_u64 (GNUNET_CRYPTO_QUALITY_WEAK, etaboff);
931 random_peer = etab[off];
932 if (cap < deg[random_peer])
934 if (++redo_threshold > GNUNET_MAX (1, cap / 2))
938 for (cnt2 = 0; cnt2 < etaboff; cnt2++)
940 if (random_peer == etab[cnt2])
945 etab[cnt2 - off] = etab[cnt2];
951 for (cnt2 = 0; cnt2 < cnt; cnt2++)
952 if (random_peer == used[cnt2])
954 make_link (links + cnt, random_peer, peer, tc);
957 used[cnt] = random_peer;
959 for (cnt = 0; cnt < GNUNET_MIN (peer, m); cnt++)
961 etab[etaboff++] = used[cnt];
962 etab[etaboff++] = peer;
964 links += GNUNET_MIN (peer, m);
969 GNUNET_assert (links <= tc->link_array_size);
970 tc->link_array_size = links;
973 case TOPOLOGYCONTEXT_TYPE_OVERLAY:
975 struct TopologyContextOverlay *overlay;
977 overlay = &tc->u.overlay;
978 overlay->link_array =
979 GNUNET_realloc (overlay->link_array, sizeof(struct OverlayLink)
980 * tc->link_array_size);
984 case TOPOLOGYCONTEXT_TYPE_UNDERLAY:
986 struct TopologyContextUnderlay *underlay;
988 underlay = &tc->u.underlay;
989 underlay->link_array =
990 GNUNET_realloc (underlay->link_array, sizeof(struct UnderlayLink)
991 * tc->link_array_size);
999 * Generates topology from the given file
1001 * @param tc the topology context
1002 * @param filename the filename of the file containing topology data
1005 gen_topo_from_file (struct TopologyContext *tc,
1006 const char *filename)
1013 unsigned long int peer_id;
1014 unsigned long int other_peer_id;
1018 * We read the peer index
1023 * We read the other peer indices
1029 status = GNUNET_SYSERR;
1030 if (GNUNET_YES != GNUNET_DISK_file_test (filename))
1032 LOG (GNUNET_ERROR_TYPE_ERROR,
1033 _ ("Topology file %s not found\n"),
1038 GNUNET_DISK_file_size (filename, &fs, GNUNET_YES, GNUNET_YES))
1040 LOG (GNUNET_ERROR_TYPE_ERROR,
1041 _ ("Topology file %s has no data\n"),
1045 data = GNUNET_malloc (fs);
1046 if (fs != GNUNET_DISK_fn_read (filename, data, fs))
1048 LOG (GNUNET_ERROR_TYPE_ERROR,
1049 _ ("Topology file %s cannot be read\n"),
1059 if (0 != isspace ((unsigned char) data[offset]))
1067 buf = strchr (&data[offset], ':');
1070 LOG (GNUNET_ERROR_TYPE_ERROR,
1071 _ ("Failed to read peer index from toology file: %s"), filename);
1076 peer_id = (unsigned int) strtoul (&data[offset], &end, 10);
1079 LOG (GNUNET_ERROR_TYPE_ERROR,
1080 _ ("Value in given topology file: %s out of range\n"), filename);
1083 if (&data[offset] == end)
1085 LOG (GNUNET_ERROR_TYPE_ERROR,
1086 _ ("Failed to read peer index from topology file: %s"), filename);
1089 if (tc->num_peers <= peer_id)
1091 LOG (GNUNET_ERROR_TYPE_ERROR,
1092 _ ("Topology file needs more peers than given ones\n"), filename);
1095 state = OTHER_PEER_INDEX;
1096 offset += ((unsigned int) (buf - &data[offset])) + 1;
1099 case OTHER_PEER_INDEX:
1101 other_peer_id = (unsigned int) strtoul (&data[offset], &end, 10);
1104 LOG (GNUNET_ERROR_TYPE_ERROR,
1105 _ ("Value in given topology file: %s out of range\n"), filename);
1108 if (&data[offset] == end)
1110 LOG (GNUNET_ERROR_TYPE_ERROR,
1111 _ ("Failed to read peer index from topology file: %s"), filename);
1114 if (tc->num_peers <= other_peer_id)
1116 LOG (GNUNET_ERROR_TYPE_ERROR,
1117 _ ("Topology file needs more peers than given ones\n"), filename);
1120 if (peer_id != other_peer_id)
1122 tc->link_array_size++;
1125 case TOPOLOGYCONTEXT_TYPE_OVERLAY:
1127 struct TopologyContextOverlay *overlay;
1129 overlay = &tc->u.overlay;
1130 overlay->link_array =
1131 GNUNET_realloc (overlay->link_array,
1132 sizeof(struct OverlayLink) * tc->link_array_size);
1136 case TOPOLOGYCONTEXT_TYPE_UNDERLAY:
1138 struct TopologyContextUnderlay *underlay;
1140 underlay = &tc->u.underlay;
1141 underlay->link_array =
1142 GNUNET_realloc (underlay->link_array,
1143 sizeof(struct UnderlayLink)
1144 * tc->link_array_size);
1148 offset += end - &data[offset];
1149 make_link (tc->link_array_size - 1, peer_id, other_peer_id, tc);
1152 LOG (GNUNET_ERROR_TYPE_WARNING,
1153 _ ("Ignoring to connect peer %u to peer %u\n"),
1156 while (('\n' != data[offset]) && ('|' != data[offset]) && (offset < fs))
1158 if ((offset < fs) &&
1159 ('\n' == data[offset]))
1161 else if ((offset < fs) &&
1162 ('|' == data[offset]))
1164 state = OTHER_PEER_INDEX;
1174 if (GNUNET_OK != status)
1176 LOG (GNUNET_ERROR_TYPE_WARNING,
1177 "Removing link data read from the file\n");
1178 tc->link_array_size = 0;
1181 case TOPOLOGYCONTEXT_TYPE_OVERLAY:
1183 struct TopologyContextOverlay *overlay;
1185 overlay = &tc->u.overlay;
1186 GNUNET_free_non_null (overlay->link_array);
1187 overlay->link_array = NULL;
1191 case TOPOLOGYCONTEXT_TYPE_UNDERLAY:
1193 struct TopologyContextUnderlay *underlay;
1195 underlay = &tc->u.underlay;
1196 GNUNET_free_non_null (underlay->link_array);
1197 underlay->link_array = NULL;
1206 * Generates clique topology
1208 * @param tc the topology context
1211 gen_topo_clique (struct TopologyContext *tc)
1214 unsigned int offset;
1215 unsigned int neighbour;
1217 tc->link_array_size = tc->num_peers * (tc->num_peers - 1);
1220 case TOPOLOGYCONTEXT_TYPE_OVERLAY:
1222 struct TopologyContextOverlay *overlay;
1224 overlay = &tc->u.overlay;
1225 overlay->link_array = GNUNET_new_array (tc->link_array_size,
1226 struct OverlayLink);
1230 case TOPOLOGYCONTEXT_TYPE_UNDERLAY:
1232 struct TopologyContextUnderlay *underlay;
1234 underlay = &tc->u.underlay;
1235 underlay->link_array = GNUNET_new_array (tc->link_array_size,
1236 struct UnderlayLink);
1240 for (cnt = 0; cnt < tc->num_peers; cnt++)
1242 for (neighbour = 0; neighbour < tc->num_peers; neighbour++)
1244 if (neighbour == cnt)
1246 make_link (offset, cnt, neighbour, tc);
1254 * Configure overall network topology to have a particular shape.
1256 * @param op_cls closure argument to give with the operation event
1257 * @param num_peers number of peers in @a peers
1258 * @param peers array of @a num_peers with the peers to configure
1259 * @param topo desired underlay topology to use
1260 * @param ap topology-specific options
1261 * @return handle to the operation, NULL if configuring the topology
1262 * is not allowed at this time
1264 struct GNUNET_TESTBED_Operation *
1265 GNUNET_TESTBED_underlay_configure_topology_va (void *op_cls,
1266 unsigned int num_peers,
1267 struct GNUNET_TESTBED_Peer
1270 GNUNET_TESTBED_TopologyOption
1279 * Configure overall network topology to have a particular shape.
1281 * @param op_cls closure argument to give with the operation event
1282 * @param num_peers number of peers in @a peers
1283 * @param peers array of @a num_peers with the peers to configure
1284 * @param topo desired underlay topology to use
1285 * @param ... topology-specific options
1286 * @return handle to the operation, NULL if configuring the topology
1287 * is not allowed at this time
1289 struct GNUNET_TESTBED_Operation *
1290 GNUNET_TESTBED_underlay_configure_topology (void *op_cls,
1291 unsigned int num_peers,
1292 struct GNUNET_TESTBED_Peer **peers,
1293 enum GNUNET_TESTBED_TopologyOption
1302 * All peers must have been started before calling this function.
1303 * This function then connects the given peers in the P2P overlay
1304 * using the given topology.
1306 * @param op_cls closure argument to give with the peer connect operation events
1307 * generated through this function
1308 * @param num_peers number of peers in @a peers
1309 * @param peers array of @a num_peers with the peers to configure
1310 * @param max_connections the maximums number of overlay connections that will
1311 * be made to achieve the given topology
1312 * @param comp_cb the completion callback to call when the topology generation
1314 * @param comp_cb_cls closure for the above completion callback
1315 * @param topo desired underlay topology to use
1316 * @param va topology-specific options
1317 * @return handle to the operation, NULL if connecting these
1318 * peers is fundamentally not possible at this time (peers
1319 * not running or underlay disallows) or if num_peers is less than 2
1321 struct GNUNET_TESTBED_Operation *
1322 GNUNET_TESTBED_overlay_configure_topology_va (void *op_cls,
1323 unsigned int num_peers,
1324 struct GNUNET_TESTBED_Peer **peers,
1325 unsigned int *max_connections,
1326 GNUNET_TESTBED_TopologyCompletionCallback
1329 enum GNUNET_TESTBED_TopologyOption
1333 struct TopologyContext *tc;
1334 struct TopologyContextOverlay *overlay;
1335 struct GNUNET_TESTBED_Operation *op;
1336 struct GNUNET_TESTBED_Controller *c;
1337 enum GNUNET_TESTBED_TopologyOption secondary_option;
1341 c = peers[0]->controller;
1342 tc = GNUNET_new (struct TopologyContext);
1343 tc->type = TOPOLOGYCONTEXT_TYPE_OVERLAY;
1344 overlay = &tc->u.overlay;
1345 overlay->peers = peers;
1346 tc->num_peers = num_peers;
1347 overlay->op_cls = op_cls;
1348 overlay->retry_cnt = DEFAULT_RETRY_CNT;
1349 overlay->comp_cb = comp_cb;
1350 overlay->comp_cb_cls = comp_cb_cls;
1353 case GNUNET_TESTBED_TOPOLOGY_LINE:
1357 case GNUNET_TESTBED_TOPOLOGY_STAR:
1361 case GNUNET_TESTBED_TOPOLOGY_RING:
1365 case GNUNET_TESTBED_TOPOLOGY_ERDOS_RENYI:
1366 gen_topo_random (tc, va_arg (va, unsigned int), GNUNET_NO);
1369 case GNUNET_TESTBED_TOPOLOGY_SMALL_WORLD_RING:
1371 gen_topo_random (tc, va_arg (va, unsigned int), GNUNET_YES);
1374 case GNUNET_TESTBED_TOPOLOGY_CLIQUE:
1375 gen_topo_clique (tc);
1378 case GNUNET_TESTBED_TOPOLOGY_2D_TORUS:
1379 gen_topo_2dtorus (tc);
1382 case GNUNET_TESTBED_TOPOLOGY_SMALL_WORLD:
1383 gen_topo_2dtorus (tc);
1384 gen_topo_random (tc, va_arg (va, unsigned int), GNUNET_YES);
1388 case GNUNET_TESTBED_TOPOLOGY_SCALE_FREE:
1393 cap = (uint16_t) va_arg (va, unsigned int);
1394 m = (uint8_t) va_arg (va, unsigned int);
1395 gen_topo_scale_free (tc, cap, m);
1399 case GNUNET_TESTBED_TOPOLOGY_FROM_FILE:
1401 const char *filename;
1403 filename = va_arg (va, const char *);
1405 GNUNET_assert (NULL != filename);
1406 gen_topo_from_file (tc, filename);
1417 secondary_option = GNUNET_VA_ARG_ENUM (va, GNUNET_TESTBED_TopologyOption);
1419 switch (secondary_option)
1421 case GNUNET_TESTBED_TOPOLOGY_RETRY_CNT:
1422 overlay->retry_cnt = va_arg (va, unsigned int);
1425 case GNUNET_TESTBED_TOPOLOGY_OPTION_END:
1429 GNUNET_break (0); /* Should not use any other option apart from
1430 * the ones handled here */
1431 GNUNET_free_non_null (overlay->link_array);
1436 while (GNUNET_TESTBED_TOPOLOGY_OPTION_END != secondary_option);
1437 op = GNUNET_TESTBED_operation_create_ (tc,
1438 &opstart_overlay_configure_topology,
1439 &oprelease_overlay_configure_topology);
1440 GNUNET_TESTBED_operation_queue_insert_
1441 (c->opq_parallel_topology_config_operations, op);
1442 GNUNET_TESTBED_operation_begin_wait_ (op);
1443 LOG (GNUNET_ERROR_TYPE_DEBUG,
1444 "Generated %u connections\n",
1445 tc->link_array_size);
1446 if (NULL != max_connections)
1447 *max_connections = tc->link_array_size;
1453 * All peers must have been started before calling this function.
1454 * This function then connects the given peers in the P2P overlay
1455 * using the given topology.
1457 * @param op_cls closure argument to give with the peer connect operation events
1458 * generated through this function
1459 * @param num_peers number of peers in 'peers'
1460 * @param peers array of 'num_peers' with the peers to configure
1461 * @param max_connections the maximums number of overlay connections that will
1462 * be made to achieve the given topology
1463 * @param comp_cb the completion callback to call when the topology generation
1465 * @param comp_cb_cls closure for the above completion callback
1466 * @param topo desired underlay topology to use
1467 * @param ... topology-specific options
1468 * @return handle to the operation, NULL if connecting these
1469 * peers is fundamentally not possible at this time (peers
1470 * not running or underlay disallows) or if num_peers is less than 2
1472 struct GNUNET_TESTBED_Operation *
1473 GNUNET_TESTBED_overlay_configure_topology (void *op_cls,
1474 unsigned int num_peers,
1475 struct GNUNET_TESTBED_Peer **peers,
1476 unsigned int *max_connections,
1477 GNUNET_TESTBED_TopologyCompletionCallback
1480 enum GNUNET_TESTBED_TopologyOption
1484 struct GNUNET_TESTBED_Operation *op;
1487 GNUNET_assert (topo < GNUNET_TESTBED_TOPOLOGY_OPTION_END);
1488 va_start (vargs, topo);
1489 op = GNUNET_TESTBED_overlay_configure_topology_va (op_cls, num_peers, peers,
1491 comp_cb, comp_cb_cls,
1500 * Get a topology from a string input.
1502 * @param topology where to write the retrieved topology
1503 * @param topology_string The string to attempt to
1504 * get a configuration value from
1505 * @return #GNUNET_YES if topology string matched a
1506 * known topology, #GNUNET_NO if not
1509 GNUNET_TESTBED_topology_get_ (enum GNUNET_TESTBED_TopologyOption *topology,
1510 const char *topology_string)
1514 for (cnt = 0; NULL != topology_strings[cnt]; cnt++)
1516 if (0 == strcasecmp (topology_string, topology_strings[cnt]))
1518 if (NULL != topology)
1519 *topology = (enum GNUNET_TESTBED_TopologyOption) cnt;
1520 GNUNET_assert (GNUNET_TESTBED_TOPOLOGY_OPTION_END !=
1521 (enum GNUNET_TESTBED_TopologyOption) cnt);
1530 * Returns the string corresponding to the given topology
1532 * @param topology the topology
1533 * @return the string (freshly allocated) of given topology; NULL if topology cannot be
1534 * expressed as a string
1537 GNUNET_TESTBED_topology_to_str_ (enum GNUNET_TESTBED_TopologyOption topology)
1539 if (GNUNET_TESTBED_TOPOLOGY_OPTION_END <= topology)
1541 return GNUNET_strdup (topology_strings[topology]);
1546 * Function to construct an underlay topology
1548 * @param num_peers the number of peers for which the topology should be
1550 * @param proc the underlay link processor callback. Will be called for each
1551 * underlay link generated unless a previous call to this callback
1552 * returned #GNUNET_SYSERR. Cannot be NULL.
1553 * @param cls closure for @a proc
1554 * @param ... variable arguments denoting the topology and its parameters. They
1555 * should start with the type of topology to generate followed by their
1557 * @return #GNUNET_OK if underlay link generation is successful; #GNUNET_SYSERR
1558 * upon error in generating the underlay or if any calls to the
1559 * underlay link processor returned #GNUNET_SYSERR
1562 GNUNET_TESTBED_underlay_construct_ (int num_peers,
1563 underlay_link_processor proc,
1567 struct TopologyContext tc;
1568 struct TopologyContextUnderlay *underlay;
1569 struct UnderlayLink *ulink;
1571 enum GNUNET_TESTBED_TopologyOption topology;
1575 GNUNET_assert (NULL != proc);
1577 memset (&tc, 0, sizeof(tc));
1578 tc.num_peers = num_peers;
1579 tc.type = TOPOLOGYCONTEXT_TYPE_UNDERLAY;
1580 underlay = &tc.u.underlay;
1581 va_start (vargs, cls);
1582 topology = GNUNET_VA_ARG_ENUM (vargs, GNUNET_TESTBED_TopologyOption);
1585 case GNUNET_TESTBED_TOPOLOGY_LINE:
1586 gen_topo_line (&tc);
1589 case GNUNET_TESTBED_TOPOLOGY_STAR:
1590 gen_topo_star (&tc);
1593 case GNUNET_TESTBED_TOPOLOGY_RING:
1594 gen_topo_ring (&tc);
1597 case GNUNET_TESTBED_TOPOLOGY_CLIQUE:
1598 gen_topo_clique (&tc);
1601 case GNUNET_TESTBED_TOPOLOGY_2D_TORUS:
1602 gen_topo_2dtorus (&tc);
1605 case GNUNET_TESTBED_TOPOLOGY_ERDOS_RENYI:
1606 gen_topo_random (&tc, va_arg (vargs, unsigned int), GNUNET_NO);
1609 case GNUNET_TESTBED_TOPOLOGY_SMALL_WORLD_RING:
1610 gen_topo_ring (&tc);
1611 gen_topo_random (&tc, va_arg (vargs, unsigned int), GNUNET_YES);
1614 case GNUNET_TESTBED_TOPOLOGY_SMALL_WORLD:
1615 gen_topo_2dtorus (&tc);
1616 gen_topo_random (&tc, va_arg (vargs, unsigned int), GNUNET_YES);
1619 case GNUNET_TESTBED_TOPOLOGY_FROM_FILE:
1621 const char *filename;
1622 filename = va_arg (vargs, char *);
1623 GNUNET_assert (NULL != filename);
1624 gen_topo_from_file (&tc, filename);
1628 case GNUNET_TESTBED_TOPOLOGY_SCALE_FREE:
1632 cap = (uint16_t) va_arg (vargs, unsigned int);
1633 m = (uint8_t) va_arg (vargs, unsigned int);
1634 gen_topo_scale_free (&tc, cap, m);
1642 for (cnt = 0; cnt < tc.link_array_size; cnt++)
1644 ulink = &underlay->link_array[cnt];
1645 if (GNUNET_SYSERR == proc (cls,
1652 ret = GNUNET_SYSERR;
1656 GNUNET_free_non_null (underlay->link_array);
1661 /* end of testbed_api_topology.c */