testbed_api_topology.c File Reference

topology-generation functions More...

#include "platform.h"
#include "gnunet_testbed_service.h"
#include "testbed_api.h"
#include "testbed_api_peers.h"
#include "testbed_api_operations.h"
#include "testbed_api_topology.h"

Include dependency graph for testbed_api_topology.c:

Go to the source code of this file.

Data Structures
struct	OverlayLink
	Representation of an overlay link. More...
struct	UnderlayLink
	Representation of an underlay link. More...
struct	RetryListEntry
struct	TopologyContextOverlay
	Context information for overlay topologies. More...
struct	TopologyContextUnderlay
	Topology context information for underlay topologies. More...
struct	TopologyContext
	Context information for topology operations. More...

Macros
#define	LOG(kind, ...)    GNUNET_log_from (kind, "testbed-api-topology", __VA_ARGS__)
	Generic loggins shorthand. More...
#define	DEFAULT_RETRY_CNT   3
	Default number of retires. More...

Functions
static void	overlay_link_completed (void *cls, struct GNUNET_TESTBED_Operation *op, const char *emsg)
	Callback to be called when an overlay_link operation complete. More...
static void	opstart_overlay_configure_topology (void *cls)
	Function called when a overlay connect operation is ready. More...
static void	oprelease_overlay_configure_topology (void *cls)
	Callback which will be called when overlay connect operation is released. More...
static void	make_link (unsigned int offset, uint32_t A, uint32_t B, struct TopologyContext *tc)
	Populates the OverlayLink structure. More...
static void	gen_topo_line (struct TopologyContext *tc)
	Generates line topology. More...
static void	gen_topo_star (struct TopologyContext *tc)
	Generates star topology. More...
static void	gen_topo_ring (struct TopologyContext *tc)
	Generates ring topology. More...
unsigned int	GNUNET_TESTBED_2dtorus_calc_links (unsigned int num_peers, unsigned int *rows, unsigned int **rows_len)
	Returns the number of links that are required to generate a 2d torus for the given number of peers. More...
static void	gen_topo_2dtorus (struct TopologyContext *tc)
	Generates ring topology. More...
static void	gen_topo_random (struct TopologyContext *tc, unsigned int links, int append)
	Generates ring topology. More...
static void	gen_topo_scale_free (struct TopologyContext *tc, uint16_t cap, uint8_t m)
	Generates scale free network. More...
static void	gen_topo_from_file (struct TopologyContext *tc, const char *filename)
	Generates topology from the given file. More...
static void	gen_topo_clique (struct TopologyContext *tc)
	Generates clique topology. More...
struct GNUNET_TESTBED_Operation *	GNUNET_TESTBED_underlay_configure_topology_va (void *op_cls, unsigned int num_peers, struct GNUNET_TESTBED_Peer **peers, enum GNUNET_TESTBED_TopologyOption topo, va_list ap)
	Configure overall network topology to have a particular shape. More...
struct GNUNET_TESTBED_Operation *	GNUNET_TESTBED_underlay_configure_topology (void *op_cls, unsigned int num_peers, struct GNUNET_TESTBED_Peer **peers, enum GNUNET_TESTBED_TopologyOption topo,...)
	Configure overall network topology to have a particular shape. More...
struct GNUNET_TESTBED_Operation *	GNUNET_TESTBED_overlay_configure_topology_va (void *op_cls, unsigned int num_peers, struct GNUNET_TESTBED_Peer **peers, unsigned int *max_connections, GNUNET_TESTBED_TopologyCompletionCallback comp_cb, void *comp_cb_cls, enum GNUNET_TESTBED_TopologyOption topo, va_list va)
	All peers must have been started before calling this function. More...
struct GNUNET_TESTBED_Operation *	GNUNET_TESTBED_overlay_configure_topology (void *op_cls, unsigned int num_peers, struct GNUNET_TESTBED_Peer **peers, unsigned int *max_connections, GNUNET_TESTBED_TopologyCompletionCallback comp_cb, void *comp_cb_cls, enum GNUNET_TESTBED_TopologyOption topo,...)
	All peers must have been started before calling this function. More...
int	GNUNET_TESTBED_topology_get_ (enum GNUNET_TESTBED_TopologyOption *topology, const char *topology_string)
	Get a topology from a string input. More...
char *	GNUNET_TESTBED_topology_to_str_ (enum GNUNET_TESTBED_TopologyOption topology)
	Returns the string corresponding to the given topology. More...
int	GNUNET_TESTBED_underlay_construct_ (int num_peers, underlay_link_processor proc, void *cls,...)
	Function to construct an underlay topology. More...

Variables
static const char *	topology_strings []
	A array of names representing topologies. More...

Detailed Description

topology-generation functions

Author

Christian Grothoff

Definition in file testbed_api_topology.c.

Macro Definition Documentation

LOG

#define LOG	(		kind,
			...
	)		GNUNET_log_from (kind, "testbed-api-topology", __VA_ARGS__)

Generic loggins shorthand.

Definition at line 36 of file testbed_api_topology.c.

DEFAULT_RETRY_CNT

#define DEFAULT_RETRY_CNT   3

Default number of retires.

Definition at line 43 of file testbed_api_topology.c.

Function Documentation

overlay_link_completed()

static void overlay_link_completed ( void *  cls, struct GNUNET_TESTBED_Operation *  op, const char *  emsg  )

static

Callback to be called when an overlay_link operation complete.

Parameters

cls	element of the link_op array which points to the corresponding operation
op	the operation that has been finished
emsg	error message in case the operation has failed; will be NULL if operation has executed successfully.

Definition at line 344 of file testbed_api_topology.c.

{
  struct OverlayLink *link = cls;
  struct TopologyContext *tc;
  struct TopologyContextOverlay *overlay;
  struct RetryListEntry *retry_entry;
 
  GNUNET_assert (op == link->op);
  GNUNET_TESTBED_operation_done (op);
  link->op = NULL;
  tc = link->tc;
  GNUNET_assert (TOPOLOGYCONTEXT_TYPE_OVERLAY == tc->type);
  overlay = &tc->u.overlay;
  if (NULL != emsg)
  {
    overlay->nfailures++;
    if (0 != overlay->retry_cnt)
    {
      LOG (GNUNET_ERROR_TYPE_WARNING,
           "Error while establishing a link: %s -- Retrying\n",
           emsg);
      retry_entry = GNUNET_new (struct RetryListEntry);
      retry_entry->link = link;
      GNUNET_CONTAINER_DLL_insert_tail (overlay->rl_head,
                                        overlay->rl_tail,
                                        retry_entry);
    }
  }
  else
    overlay->nsuccess++;
  overlay->ncompleted++;
  if (overlay->ncompleted < overlay->nlinks)
    return;
  if ((0 != overlay->retry_cnt) && (NULL != overlay->rl_head))
  {
    overlay->retry_cnt--;
    overlay->ncompleted = 0;
    overlay->nlinks = 0;
    while (NULL != (retry_entry = overlay->rl_head))
    {
      link = retry_entry->link;
      link->op =
        GNUNET_TESTBED_overlay_connect (overlay->op_cls,
                                        &overlay_link_completed,
                                        link,
                                        overlay->peers[link->A],
                                        overlay->peers[link->B]);
      overlay->nlinks++;
      GNUNET_CONTAINER_DLL_remove (overlay->rl_head,
                                   overlay->rl_tail,
                                   retry_entry);
      GNUNET_free (retry_entry);
    }
    return;
  }
  if (NULL != overlay->comp_cb)
  {
    overlay->comp_cb (overlay->comp_cb_cls,
                      overlay->nsuccess,
                      overlay->nfailures);
  }
}

References OverlayLink::A, OverlayLink::B, TopologyContextOverlay::comp_cb, TopologyContextOverlay::comp_cb_cls, GNUNET_assert, GNUNET_CONTAINER_DLL_insert_tail, GNUNET_CONTAINER_DLL_remove, GNUNET_ERROR_TYPE_WARNING, GNUNET_free, GNUNET_new, GNUNET_TESTBED_operation_done(), GNUNET_TESTBED_overlay_connect(), RetryListEntry::link, LOG, TopologyContextOverlay::ncompleted, TopologyContextOverlay::nfailures, TopologyContextOverlay::nlinks, TopologyContextOverlay::nsuccess, op, OverlayLink::op, TopologyContextOverlay::op_cls, TopologyContextOverlay::peers, TopologyContextOverlay::retry_cnt, retry_entry(), TopologyContextOverlay::rl_head, TopologyContextOverlay::rl_tail, OverlayLink::tc, and tc.

Referenced by opstart_overlay_configure_topology().

Here is the call graph for this function:

Here is the caller graph for this function:

opstart_overlay_configure_topology()

static void opstart_overlay_configure_topology ( void *  cls )

static

Function called when a overlay connect operation is ready.

Parameters

cls	the Topology context

Definition at line 416 of file testbed_api_topology.c.

{
  struct TopologyContext *tc = cls;
  struct TopologyContextOverlay *overlay;
  unsigned int p;
 
  GNUNET_assert (TOPOLOGYCONTEXT_TYPE_OVERLAY == tc->type);
  overlay = &tc->u.overlay;
  overlay->nlinks = tc->link_array_size;
  for (p = 0; p < tc->link_array_size; p++)
  {
    overlay->link_array[p].op =
      GNUNET_TESTBED_overlay_connect (overlay->op_cls,
                                      &overlay_link_completed,
                                      &overlay->link_array[p],
                                      overlay->peers[overlay->link_array[p].A],
                                      overlay->peers[overlay->link_array[p].B]);
  }
}

References OverlayLink::A, OverlayLink::B, GNUNET_assert, GNUNET_TESTBED_overlay_connect(), TopologyContextOverlay::link_array, TopologyContextOverlay::nlinks, OverlayLink::op, TopologyContextOverlay::op_cls, overlay_link_completed(), p, TopologyContextOverlay::peers, and tc.

Referenced by GNUNET_TESTBED_overlay_configure_topology_va().

Here is the call graph for this function:

Here is the caller graph for this function:

oprelease_overlay_configure_topology()

static void oprelease_overlay_configure_topology ( void *  cls )

static

Callback which will be called when overlay connect operation is released.

Parameters

cls	the Topology context

Definition at line 443 of file testbed_api_topology.c.

{
  struct TopologyContext *tc = cls;
  struct TopologyContextOverlay *overlay;
  struct RetryListEntry *retry_entry;
  unsigned int p;
 
  GNUNET_assert (TOPOLOGYCONTEXT_TYPE_OVERLAY == tc->type);
  overlay = &tc->u.overlay;
  while (NULL != (retry_entry = overlay->rl_head))
  {
    GNUNET_CONTAINER_DLL_remove (overlay->rl_head, overlay->rl_tail,
                                 retry_entry);
    GNUNET_free (retry_entry);
  }
  if (NULL != overlay->link_array)
  {
    for (p = 0; p < tc->link_array_size; p++)
      if (NULL != overlay->link_array[p].op)
        GNUNET_TESTBED_operation_done (overlay->link_array[p].op);
    GNUNET_free (overlay->link_array);
  }
  GNUNET_free (tc);
}

References GNUNET_assert, GNUNET_CONTAINER_DLL_remove, GNUNET_free, GNUNET_TESTBED_operation_done(), TopologyContextOverlay::link_array, OverlayLink::op, p, retry_entry(), TopologyContextOverlay::rl_head, TopologyContextOverlay::rl_tail, and tc.

Referenced by GNUNET_TESTBED_overlay_configure_topology_va().

Here is the call graph for this function:

Here is the caller graph for this function:

make_link()

static void make_link ( unsigned int  offset, uint32_t  A, uint32_t  B, struct TopologyContext *  tc  )

static

Populates the OverlayLink structure.

Parameters

offset	the offset of the link array to use
A	the peer A. Should be different from B
B	the peer B. Should be different from A
tc	the TopologyContext

Returns

Definition at line 479 of file testbed_api_topology.c.

{
  GNUNET_assert (A != B);
  switch (tc->type)
  {
  case TOPOLOGYCONTEXT_TYPE_OVERLAY:
    {
      struct TopologyContextOverlay *overlay;
      struct OverlayLink *olink;
 
      overlay = &tc->u.overlay;
      GNUNET_assert (offset < tc->link_array_size);
      olink = &overlay->link_array[offset];
      LOG (GNUNET_ERROR_TYPE_DEBUG, "Connecting peer %u to %u\n", B, A);
      olink->A = A;
      olink->B = B;
      olink->op = NULL;
      olink->tc = tc;
    }
    break;
 
  case TOPOLOGYCONTEXT_TYPE_UNDERLAY:
    {
      struct TopologyContextUnderlay *underlay;
      struct UnderlayLink *ulink;
 
      underlay = &tc->u.underlay;
      GNUNET_assert (offset < tc->link_array_size);
      ulink = &underlay->link_array[offset];
      ulink->A = A;
      ulink->B = B;
    }
    break;
  }
}

References OverlayLink::A, UnderlayLink::A, OverlayLink::B, UnderlayLink::B, GNUNET_assert, GNUNET_ERROR_TYPE_DEBUG, TopologyContextOverlay::link_array, TopologyContextUnderlay::link_array, LOG, OverlayLink::op, OverlayLink::tc, and tc.

Referenced by gen_topo_2dtorus(), gen_topo_clique(), gen_topo_from_file(), gen_topo_line(), gen_topo_random(), gen_topo_ring(), gen_topo_scale_free(), and gen_topo_star().

Here is the caller graph for this function:

gen_topo_line()

static void gen_topo_line ( struct TopologyContext *  tc )

static

Generates line topology.

Parameters

tc	the topology context

Definition at line 525 of file testbed_api_topology.c.

{
  unsigned int cnt;
 
  tc->link_array_size = tc->num_peers - 1;
  switch (tc->type)
  {
  case TOPOLOGYCONTEXT_TYPE_OVERLAY:
    {
      struct TopologyContextOverlay *overlay;
 
      overlay = &tc->u.overlay;
      overlay->link_array =
        GNUNET_new_array (tc->link_array_size,
                          struct OverlayLink);
    }
    break;
 
  case TOPOLOGYCONTEXT_TYPE_UNDERLAY:
    {
      struct TopologyContextUnderlay *underlay;
 
      underlay = &tc->u.underlay;
      underlay->link_array =
        GNUNET_new_array (tc->link_array_size,
                          struct UnderlayLink);
    }
    break;
  }
  for (cnt = 0; cnt < (tc->link_array_size); cnt++)
    make_link (cnt, cnt, cnt + 1, tc);
}

References GNUNET_new_array, TopologyContextOverlay::link_array, TopologyContextUnderlay::link_array, make_link(), and tc.

Referenced by gen_topo_ring(), GNUNET_TESTBED_overlay_configure_topology_va(), and GNUNET_TESTBED_underlay_construct_().

Here is the call graph for this function:

Here is the caller graph for this function:

gen_topo_star()

static void gen_topo_star ( struct TopologyContext *  tc )

static

Generates star topology.

Parameters

tc	the topology context

Definition at line 565 of file testbed_api_topology.c.

{
  unsigned int cnt;
 
  tc->link_array_size = tc->num_peers - 1;
  switch (tc->type)
  {
  case TOPOLOGYCONTEXT_TYPE_OVERLAY:
    {
      struct TopologyContextOverlay *overlay;
 
      overlay = &tc->u.overlay;
      overlay->link_array =
        GNUNET_new_array (tc->link_array_size,
                          struct OverlayLink);
    }
    break;
 
  case TOPOLOGYCONTEXT_TYPE_UNDERLAY:
    {
      struct TopologyContextUnderlay *underlay;
 
      underlay = &tc->u.underlay;
      underlay->link_array =
        GNUNET_new_array (tc->link_array_size,
                          struct UnderlayLink);
    }
    break;
  }
  for (cnt = tc->link_array_size; cnt; cnt--)
    make_link (cnt - 1,
               0,
               cnt,
               tc);
}

References GNUNET_new_array, TopologyContextOverlay::link_array, TopologyContextUnderlay::link_array, make_link(), and tc.

Referenced by GNUNET_TESTBED_overlay_configure_topology_va(), and GNUNET_TESTBED_underlay_construct_().

Here is the call graph for this function:

Here is the caller graph for this function:

gen_topo_ring()

static void gen_topo_ring ( struct TopologyContext *  tc )

static

Generates ring topology.

Parameters

tc	the topology context

Definition at line 608 of file testbed_api_topology.c.

{
  gen_topo_line (tc);
  tc->link_array_size++;
  switch (tc->type)
  {
  case TOPOLOGYCONTEXT_TYPE_OVERLAY:
    {
      struct TopologyContextOverlay *overlay;
 
      overlay = &tc->u.overlay;
      overlay->link_array =
        GNUNET_realloc (overlay->link_array, sizeof(struct OverlayLink)
                        * tc->link_array_size);
    }
    break;
 
  case TOPOLOGYCONTEXT_TYPE_UNDERLAY:
    {
      struct TopologyContextUnderlay *underlay;
 
      underlay = &tc->u.underlay;
      underlay->link_array =
        GNUNET_realloc (underlay->link_array, sizeof(struct UnderlayLink)
                        * tc->link_array_size);
    }
    break;
  }
  make_link (tc->link_array_size - 1, tc->num_peers - 1, 0, tc);
}

References gen_topo_line(), GNUNET_realloc, TopologyContextOverlay::link_array, TopologyContextUnderlay::link_array, make_link(), and tc.

Referenced by GNUNET_TESTBED_overlay_configure_topology_va(), and GNUNET_TESTBED_underlay_construct_().

Here is the call graph for this function:

Here is the caller graph for this function:

GNUNET_TESTBED_2dtorus_calc_links()

unsigned int GNUNET_TESTBED_2dtorus_calc_links	(	unsigned int	num_peers,
		unsigned int *	rows,
		unsigned int **	rows_len
	)

Returns the number of links that are required to generate a 2d torus for the given number of peers.

Also returns the arrangement (number of rows and the length of each row)

Parameters

num_peers	number of peers
rows	number of rows in the 2d torus. Can be NULL.
rows_len	the length of each row. This array will be allocated fresh. The caller should free it. Can be NULL.

Returns

the number of links that are required to generate a 2d torus for the given number of peers

Definition at line 641 of file testbed_api_topology.c.

{
  double sq;
  unsigned int sq_floor;
  unsigned int _rows;
  unsigned int *_rows_len;
  unsigned int x;
  unsigned int y;
  unsigned int _num_peers;
  unsigned int cnt;
 
  sq = sqrt (num_peers);
  sq = floor (sq);
  sq_floor = (unsigned int) sq;
  _rows = (sq_floor + 1);
  _rows_len = GNUNET_malloc (sizeof(unsigned int) * _rows);
  for (y = 0; y < _rows - 1; y++)
    _rows_len[y] = sq_floor;
  _num_peers = sq_floor * sq_floor;
  cnt = (_num_peers < 2) ? _num_peers : 2 * _num_peers;
  x = 0;
  y = 0;
  while (_num_peers < num_peers)
  {
    if (x < y)
      _rows_len[_rows - 1] = ++x;
    else
      _rows_len[y++]++;
    _num_peers++;
  }
  cnt += (x < 2) ? x : 2 * x;
  cnt += (y < 2) ? y : 2 * y;
  if (0 == _rows_len[_rows - 1])
    _rows--;
  if (NULL != rows)
    *rows = _rows;
  if (NULL != rows_len)
    *rows_len = _rows_len;
  else
    GNUNET_free (_rows_len);
  return cnt;
}

References GNUNET_free, GNUNET_malloc, consensus-simulation::int, and num_peers.

Referenced by gen_topo_2dtorus().

Here is the caller graph for this function:

gen_topo_2dtorus()

static void gen_topo_2dtorus ( struct TopologyContext *  tc )

static

Generates ring topology.

Parameters

tc	the topology context

Definition at line 692 of file testbed_api_topology.c.

{
  unsigned int rows;
  unsigned int *rows_len;
  unsigned int x;
  unsigned int y;
  unsigned int cnt;
  unsigned int offset;
 
  tc->link_array_size =
    GNUNET_TESTBED_2dtorus_calc_links (tc->num_peers, &rows, &rows_len);
  switch (tc->type)
  {
  case TOPOLOGYCONTEXT_TYPE_OVERLAY:
    {
      struct TopologyContextOverlay *overlay;
 
      overlay = &tc->u.overlay;
      overlay->link_array =
        GNUNET_malloc (sizeof(struct OverlayLink) * tc->link_array_size);
    }
    break;
 
  case TOPOLOGYCONTEXT_TYPE_UNDERLAY:
    {
      struct TopologyContextUnderlay *underlay;
 
      underlay = &tc->u.underlay;
      underlay->link_array =
        GNUNET_malloc (sizeof(struct UnderlayLink) * tc->link_array_size);
      break;
    }
  }
  cnt = 0;
  offset = 0;
  for (y = 0; y < rows; y++)
  {
    for (x = 0; x < rows_len[y] - 1; x++)
    {
      make_link (cnt, offset + x, offset + x + 1, tc);
      cnt++;
    }
    if (0 == x)
      break;
    make_link (cnt, offset + x, offset, tc);
    cnt++;
    offset += rows_len[y];
  }
  for (x = 0; x < rows_len[0]; x++)
  {
    offset = 0;
    for (y = 0; y < rows - 1; y++)
    {
      if (x >= rows_len[y + 1])
        break;
      GNUNET_assert (x < rows_len[y + 1]);
      make_link (cnt, offset + x, offset + rows_len[y] + x, tc);
      offset += rows_len[y];
      cnt++;
    }
    if (0 == offset)
      break;
    make_link (cnt, offset + x, x, tc);
    cnt++;
  }
  GNUNET_assert (cnt == tc->link_array_size);
  GNUNET_free (rows_len);
}

References GNUNET_assert, GNUNET_free, GNUNET_malloc, GNUNET_TESTBED_2dtorus_calc_links(), TopologyContextOverlay::link_array, TopologyContextUnderlay::link_array, make_link(), and tc.

Referenced by GNUNET_TESTBED_overlay_configure_topology_va(), and GNUNET_TESTBED_underlay_construct_().

Here is the call graph for this function:

Here is the caller graph for this function:

gen_topo_random()

static void gen_topo_random ( struct TopologyContext *  tc, unsigned int  links, int  append  )

static

Generates ring topology.

Parameters

tc	the topology context
links	the number of random links to establish
append	GNUNET_YES to add links to existing link array; GNUNET_NO to create a new link array

Definition at line 771 of file testbed_api_topology.c.

{
  unsigned int cnt;
  unsigned int index;
  uint32_t A_rand;
  uint32_t B_rand;
 
  if (1 == tc->num_peers)
    return;
  if (GNUNET_YES == append)
  {
    index = tc->link_array_size;
    tc->link_array_size += links;
  }
  else
  {
    index = 0;
    tc->link_array_size = links;
  }
  switch (tc->type)
  {
  case TOPOLOGYCONTEXT_TYPE_OVERLAY:
    {
      struct TopologyContextOverlay *overlay;
 
      overlay = &tc->u.overlay;
      if (GNUNET_YES != append)
      {
        GNUNET_assert (NULL == overlay->link_array);
        overlay->link_array =
          GNUNET_malloc (sizeof(struct OverlayLink) * tc->link_array_size);
        break;
      }
      GNUNET_assert ((0 < tc->link_array_size) && (NULL !=
                                                   overlay->link_array));
      overlay->link_array =
        GNUNET_realloc (overlay->link_array,
                        sizeof(struct OverlayLink) * tc->link_array_size);
      break;
    }
 
  case TOPOLOGYCONTEXT_TYPE_UNDERLAY:
    {
      struct TopologyContextUnderlay *underlay;
 
      underlay = &tc->u.underlay;
      if (GNUNET_YES != append)
      {
        GNUNET_assert (NULL == underlay->link_array);
        underlay->link_array =
          GNUNET_malloc (sizeof(struct UnderlayLink) * tc->link_array_size);
        break;
      }
      GNUNET_assert ((0 < tc->link_array_size) && (NULL !=
                                                   underlay->link_array));
      underlay->link_array =
        GNUNET_realloc (underlay->link_array,
                        sizeof(struct UnderlayLink) * tc->link_array_size);
      break;
    }
  }
  for (cnt = 0; cnt < links; cnt++)
  {
    do
    {
      A_rand =
        GNUNET_CRYPTO_random_u32 (GNUNET_CRYPTO_QUALITY_WEAK, tc->num_peers);
      B_rand =
        GNUNET_CRYPTO_random_u32 (GNUNET_CRYPTO_QUALITY_WEAK, tc->num_peers);
    }
    while (A_rand == B_rand);
    make_link (index + cnt, A_rand, B_rand, tc);
  }
}

References GNUNET_assert, GNUNET_CRYPTO_QUALITY_WEAK, GNUNET_CRYPTO_random_u32(), GNUNET_malloc, GNUNET_realloc, GNUNET_YES, TopologyContextOverlay::link_array, TopologyContextUnderlay::link_array, links, make_link(), and tc.

Referenced by GNUNET_TESTBED_overlay_configure_topology_va(), and GNUNET_TESTBED_underlay_construct_().

Here is the call graph for this function:

Here is the caller graph for this function:

gen_topo_scale_free()

static void gen_topo_scale_free ( struct TopologyContext *  tc, uint16_t  cap, uint8_t  m  )

static

Generates scale free network.

Its construction is described in:

"Emergence of Scaling in Random Networks." Science 286, 509-512, 1999.

Parameters

tc	the topology context
cap	maximum allowed node degree
m	number of edges to establish for a new node when it is added to the network

Definition at line 860 of file testbed_api_topology.c.

{
  unsigned int *deg;
  unsigned int *etab;
  unsigned int *used;
  unsigned int etaboff;
  unsigned int cnt;
  unsigned int cnt2;
  unsigned int peer;
  unsigned int random_peer;
  unsigned int links;
  unsigned int off;
  unsigned int redo_threshold;
 
  etaboff = 0;
  tc->link_array_size = tc->num_peers * m;
  switch (tc->type)
  {
  case TOPOLOGYCONTEXT_TYPE_OVERLAY:
    {
      struct TopologyContextOverlay *overlay;
 
      overlay = &tc->u.overlay;
      overlay->link_array = GNUNET_malloc_large (sizeof(struct OverlayLink)
                                                 * tc->link_array_size);
    }
    break;
 
  case TOPOLOGYCONTEXT_TYPE_UNDERLAY:
    {
      struct TopologyContextUnderlay *underlay;
 
      underlay = &tc->u.underlay;
      underlay->link_array = GNUNET_malloc_large (sizeof(struct UnderlayLink)
                                                  * tc->link_array_size);
    }
    break;
  }
  etab = GNUNET_malloc_large (sizeof(unsigned int) * 2 * tc->link_array_size);
  deg = GNUNET_malloc (sizeof(unsigned int) * tc->num_peers);
  used = GNUNET_malloc (sizeof(unsigned int) * m);
  /* start by connecting peer 1 to peer 0 */
  make_link (0, 0, 1, tc);
  deg[0]++;
  deg[1]++;
  etab[etaboff++] = 0;
  etab[etaboff++] = 1;
  links = 1;
  for (peer = 2; peer < tc->num_peers; peer++)
  {
    if (cap < deg[peer])
      continue;
    for (cnt = 0; cnt < GNUNET_MIN (peer, m); cnt++)
    {
      redo_threshold = 0;
redo:
      off = GNUNET_CRYPTO_random_u64 (GNUNET_CRYPTO_QUALITY_WEAK, etaboff);
      random_peer = etab[off];
      if (cap < deg[random_peer])
      {
        if (++redo_threshold > GNUNET_MAX (1, cap / 2))
        {
          redo_threshold = 0;
          off = 0;
          for (cnt2 = 0; cnt2 < etaboff; cnt2++)
          {
            if (random_peer == etab[cnt2])
            {
              off++;
              continue;
            }
            etab[cnt2 - off] = etab[cnt2];
          }
          etaboff -= off;
        }
        goto redo;
      }
      for (cnt2 = 0; cnt2 < cnt; cnt2++)
        if (random_peer == used[cnt2])
          goto redo;
      make_link (links + cnt, random_peer, peer, tc);
      deg[random_peer]++;
      deg[peer]++;
      used[cnt] = random_peer;
    }
    for (cnt = 0; cnt < GNUNET_MIN (peer, m); cnt++)
    {
      etab[etaboff++] = used[cnt];
      etab[etaboff++] = peer;
    }
    links += GNUNET_MIN (peer, m);
  }
  GNUNET_free (etab);
  GNUNET_free (used);
  GNUNET_free (deg);
  GNUNET_assert (links <= tc->link_array_size);
  tc->link_array_size = links;
  switch (tc->type)
  {
  case TOPOLOGYCONTEXT_TYPE_OVERLAY:
    {
      struct TopologyContextOverlay *overlay;
 
      overlay = &tc->u.overlay;
      overlay->link_array =
        GNUNET_realloc (overlay->link_array, sizeof(struct OverlayLink)
                        * tc->link_array_size);
    }
    break;
 
  case TOPOLOGYCONTEXT_TYPE_UNDERLAY:
    {
      struct TopologyContextUnderlay *underlay;
 
      underlay = &tc->u.underlay;
      underlay->link_array =
        GNUNET_realloc (underlay->link_array, sizeof(struct UnderlayLink)
                        * tc->link_array_size);
    }
    break;
  }
}

References GNUNET_assert, GNUNET_CRYPTO_QUALITY_WEAK, GNUNET_CRYPTO_random_u64(), GNUNET_free, GNUNET_malloc, GNUNET_malloc_large, GNUNET_MAX, GNUNET_MIN, GNUNET_realloc, TopologyContextOverlay::link_array, TopologyContextUnderlay::link_array, links, m, make_link(), peer, and tc.

Referenced by GNUNET_TESTBED_overlay_configure_topology_va(), and GNUNET_TESTBED_underlay_construct_().

Here is the call graph for this function:

Here is the caller graph for this function:

gen_topo_from_file()

static void gen_topo_from_file ( struct TopologyContext *  tc, const char *  filename  )

static

Generates topology from the given file.

Parameters

tc	the topology context
filename	the filename of the file containing topology data

We read the peer index

We read the other peer indices

Definition at line 993 of file testbed_api_topology.c.

{
  char *data;
  char *end;
  char *buf;
  uint64_t fs;
  uint64_t offset;
  unsigned long int peer_id;
  unsigned long int other_peer_id;
  enum ParseState
  {
    PEER_INDEX,
 
    OTHER_PEER_INDEX,
  } state;
  int status;
 
  status = GNUNET_SYSERR;
  if (GNUNET_YES != GNUNET_DISK_file_test (filename))
  {
    LOG (GNUNET_ERROR_TYPE_ERROR,
         _ ("Topology file %s not found\n"),
         filename);
    return;
  }
  if (GNUNET_OK !=
      GNUNET_DISK_file_size (filename, &fs, GNUNET_YES, GNUNET_YES))
  {
    LOG (GNUNET_ERROR_TYPE_ERROR,
         _ ("Topology file %s has no data\n"),
         filename);
    return;
  }
  data = GNUNET_malloc (fs);
  if (fs != GNUNET_DISK_fn_read (filename, data, fs))
  {
    LOG (GNUNET_ERROR_TYPE_ERROR,
         _ ("Topology file %s cannot be read\n"),
         filename);
    goto _exit;
  }
 
  offset = 0;
  peer_id = 0;
  state = PEER_INDEX;
  while (offset < fs)
  {
    if (0 != isspace ((unsigned char) data[offset]))
    {
      offset++;
      continue;
    }
    switch (state)
    {
    case PEER_INDEX:
      buf = strchr (&data[offset], ':');
      if (NULL == buf)
      {
        LOG (GNUNET_ERROR_TYPE_ERROR,
             _ ("Failed to read peer index from toology file: %s"), filename);
        goto _exit;
      }
      *buf = '\0';
      errno = 0;
      peer_id = (unsigned int) strtoul (&data[offset], &end, 10);
      if (0 != errno)
      {
        LOG (GNUNET_ERROR_TYPE_ERROR,
             _ ("Value in given topology file: %s out of range\n"), filename);
        goto _exit;
      }
      if (&data[offset] == end)
      {
        LOG (GNUNET_ERROR_TYPE_ERROR,
             _ ("Failed to read peer index from topology file: %s"), filename);
        goto _exit;
      }
      if (tc->num_peers <= peer_id)
      {
        LOG (GNUNET_ERROR_TYPE_ERROR,
             _ ("Topology file needs more peers than given ones\n"));
        goto _exit;
      }
      state = OTHER_PEER_INDEX;
      offset += ((unsigned int) (buf - &data[offset])) + 1;
      break;
 
    case OTHER_PEER_INDEX:
      errno = 0;
      other_peer_id = (unsigned int) strtoul (&data[offset], &end, 10);
      if (0 != errno)
      {
        LOG (GNUNET_ERROR_TYPE_ERROR,
             _ ("Value in given topology file: %s out of range\n"), filename);
        goto _exit;
      }
      if (&data[offset] == end)
      {
        LOG (GNUNET_ERROR_TYPE_ERROR,
             _ ("Failed to read peer index from topology file: %s"), filename);
        goto _exit;
      }
      if (tc->num_peers <= other_peer_id)
      {
        LOG (GNUNET_ERROR_TYPE_ERROR,
             _ ("Topology file needs more peers than given ones\n"));
        goto _exit;
      }
      if (peer_id != other_peer_id)
      {
        tc->link_array_size++;
        switch (tc->type)
        {
        case TOPOLOGYCONTEXT_TYPE_OVERLAY:
          {
            struct TopologyContextOverlay *overlay;
 
            overlay = &tc->u.overlay;
            overlay->link_array =
              GNUNET_realloc (overlay->link_array,
                              sizeof(struct OverlayLink) * tc->link_array_size);
          }
          break;
 
        case TOPOLOGYCONTEXT_TYPE_UNDERLAY:
          {
            struct TopologyContextUnderlay *underlay;
 
            underlay = &tc->u.underlay;
            underlay->link_array =
              GNUNET_realloc (underlay->link_array,
                              sizeof(struct UnderlayLink)
                              * tc->link_array_size);
          }
          break;
        }
        offset += end - &data[offset];
        make_link (tc->link_array_size - 1, peer_id, other_peer_id, tc);
      }
      else
        LOG (GNUNET_ERROR_TYPE_WARNING,
             _ ("Ignoring to connect peer %lu to peer %lu\n"),
             peer_id,
             other_peer_id);
      while (('\n' != data[offset]) && ('|' != data[offset]) && (offset < fs))
        offset++;
      if ((offset < fs) &&
          ('\n' == data[offset]))
        state = PEER_INDEX;
      else if ((offset < fs) &&
               ('|' == data[offset]))
      {
        state = OTHER_PEER_INDEX;
        offset++;
      }
      break;
    }
  }
  status = GNUNET_OK;
 
_exit:
  GNUNET_free (data);
  if (GNUNET_OK != status)
  {
    LOG (GNUNET_ERROR_TYPE_WARNING,
         "Removing link data read from the file\n");
    tc->link_array_size = 0;
    switch (tc->type)
    {
    case TOPOLOGYCONTEXT_TYPE_OVERLAY:
      {
        struct TopologyContextOverlay *overlay;
 
        overlay = &tc->u.overlay;
        GNUNET_free (overlay->link_array);
        overlay->link_array = NULL;
      }
      break;
 
    case TOPOLOGYCONTEXT_TYPE_UNDERLAY:
      {
        struct TopologyContextUnderlay *underlay;
 
        underlay = &tc->u.underlay;
        GNUNET_free (underlay->link_array);
        underlay->link_array = NULL;
      }
      break;
    }
  }
}

References _, buf, data, end, filename, fs, GNUNET_DISK_file_size(), GNUNET_DISK_file_test(), GNUNET_DISK_fn_read(), GNUNET_ERROR_TYPE_ERROR, GNUNET_ERROR_TYPE_WARNING, GNUNET_free, GNUNET_malloc, GNUNET_OK, GNUNET_realloc, GNUNET_SYSERR, GNUNET_YES, consensus-simulation::int, TopologyContextOverlay::link_array, TopologyContextUnderlay::link_array, LOG, make_link(), peer_id, state, status, and tc.

Referenced by GNUNET_TESTBED_overlay_configure_topology_va(), and GNUNET_TESTBED_underlay_construct_().

Here is the call graph for this function:

Here is the caller graph for this function:

gen_topo_clique()

static void gen_topo_clique ( struct TopologyContext *  tc )

static

Generates clique topology.

Parameters

tc	the topology context

Definition at line 1199 of file testbed_api_topology.c.

{
  unsigned int cnt;
  unsigned int offset;
  unsigned int neighbour;
 
  tc->link_array_size = tc->num_peers * (tc->num_peers - 1);
  switch (tc->type)
  {
  case TOPOLOGYCONTEXT_TYPE_OVERLAY:
    {
      struct TopologyContextOverlay *overlay;
 
      overlay = &tc->u.overlay;
      overlay->link_array = GNUNET_new_array (tc->link_array_size,
                                              struct OverlayLink);
    }
    break;
 
  case TOPOLOGYCONTEXT_TYPE_UNDERLAY:
    {
      struct TopologyContextUnderlay *underlay;
 
      underlay = &tc->u.underlay;
      underlay->link_array = GNUNET_new_array (tc->link_array_size,
                                               struct UnderlayLink);
    }
  }
  offset = 0;
  for (cnt = 0; cnt < tc->num_peers; cnt++)
  {
    for (neighbour = 0; neighbour < tc->num_peers; neighbour++)
    {
      if (neighbour == cnt)
        continue;
      make_link (offset, cnt, neighbour, tc);
      offset++;
    }
  }
}

References GNUNET_new_array, TopologyContextOverlay::link_array, TopologyContextUnderlay::link_array, make_link(), and tc.

Referenced by GNUNET_TESTBED_overlay_configure_topology_va(), and GNUNET_TESTBED_underlay_construct_().

Here is the call graph for this function:

Here is the caller graph for this function:

GNUNET_TESTBED_topology_get_()

int GNUNET_TESTBED_topology_get_	(	enum GNUNET_TESTBED_TopologyOption *	topology,
		const char *	topology_string
	)

Get a topology from a string input.

Parameters

topology	where to write the retrieved topology
topology_string	The string to attempt to get a configuration value from

Returns

GNUNET_YES if topology string matched a known topology, GNUNET_NO if not

Definition at line 1446 of file testbed_api_topology.c.

{
  unsigned int cnt;
 
  for (cnt = 0; NULL != topology_strings[cnt]; cnt++)
  {
    if (0 == strcasecmp (topology_string, topology_strings[cnt]))
    {
      if (NULL != topology)
        *topology = (enum GNUNET_TESTBED_TopologyOption) cnt;
      GNUNET_assert (GNUNET_TESTBED_TOPOLOGY_OPTION_END !=
                     (enum GNUNET_TESTBED_TopologyOption) cnt);
      return GNUNET_YES;
    }
  }
  return GNUNET_NO;
}

References GNUNET_assert, GNUNET_NO, GNUNET_TESTBED_TOPOLOGY_OPTION_END, GNUNET_YES, topology, and topology_strings.

Referenced by GNUNET_TESTBED_run(), and run().

Here is the caller graph for this function:

GNUNET_TESTBED_topology_to_str_()

char* GNUNET_TESTBED_topology_to_str_

(

enum GNUNET_TESTBED_TopologyOption

topology

)

Returns the string corresponding to the given topology.

Parameters

topology

the topology

Returns

the string (freshly allocated) of given topology; NULL if topology cannot be expressed as a string

Definition at line 1474 of file testbed_api_topology.c.

{
  if (GNUNET_TESTBED_TOPOLOGY_OPTION_END <= topology)
    return NULL;
  return GNUNET_strdup (topology_strings[topology]);
}

References GNUNET_strdup, GNUNET_TESTBED_TOPOLOGY_OPTION_END, topology, and topology_strings.

GNUNET_TESTBED_underlay_construct_()

int GNUNET_TESTBED_underlay_construct_	(	int	num_peers,
		underlay_link_processor	proc,
		void *	cls,
			...
	)

Function to construct an underlay topology.

Parameters

num_peers	the number of peers for which the topology should be generated
proc	the underlay link processor callback. Will be called for each underlay link generated unless a previous call to this callback returned GNUNET_SYSERR. Cannot be NULL.
cls	closure for proc
...	variable arguments denoting the topology and its parameters. They should start with the type of topology to generate followed by their options.

Returns

GNUNET_OK if underlay link generation is successful; GNUNET_SYSERR upon error in generating the underlay or if any calls to the underlay link processor returned GNUNET_SYSERR

Definition at line 1499 of file testbed_api_topology.c.

{
  struct TopologyContext tc;
  struct TopologyContextUnderlay *underlay;
  struct UnderlayLink *ulink;
  va_list vargs;
  enum GNUNET_TESTBED_TopologyOption topology;
  unsigned int cnt;
  int ret;
 
  GNUNET_assert (NULL != proc);
  ret = GNUNET_OK;
  memset (&tc, 0, sizeof(tc));
  tc.num_peers = num_peers;
  tc.type = TOPOLOGYCONTEXT_TYPE_UNDERLAY;
  underlay = &tc.u.underlay;
  va_start (vargs, cls);
  topology = GNUNET_VA_ARG_ENUM (vargs, GNUNET_TESTBED_TopologyOption);
  switch (topology)
  {
  case GNUNET_TESTBED_TOPOLOGY_LINE:
    gen_topo_line (&tc);
    break;
 
  case GNUNET_TESTBED_TOPOLOGY_STAR:
    gen_topo_star (&tc);
    break;
 
  case GNUNET_TESTBED_TOPOLOGY_RING:
    gen_topo_ring (&tc);
    break;
 
  case GNUNET_TESTBED_TOPOLOGY_CLIQUE:
    gen_topo_clique (&tc);
    break;
 
  case GNUNET_TESTBED_TOPOLOGY_2D_TORUS:
    gen_topo_2dtorus (&tc);
    break;
 
  case GNUNET_TESTBED_TOPOLOGY_ERDOS_RENYI:
    gen_topo_random (&tc, va_arg (vargs, unsigned int), GNUNET_NO);
    break;
 
  case GNUNET_TESTBED_TOPOLOGY_SMALL_WORLD_RING:
    gen_topo_ring (&tc);
    gen_topo_random (&tc, va_arg (vargs, unsigned int), GNUNET_YES);
    break;
 
  case GNUNET_TESTBED_TOPOLOGY_SMALL_WORLD:
    gen_topo_2dtorus (&tc);
    gen_topo_random (&tc, va_arg (vargs, unsigned int), GNUNET_YES);
    break;
 
  case GNUNET_TESTBED_TOPOLOGY_FROM_FILE:
    {
      const char *filename;
      filename = va_arg (vargs, char *);
      GNUNET_assert (NULL != filename);
      gen_topo_from_file (&tc, filename);
    }
    break;
 
  case GNUNET_TESTBED_TOPOLOGY_SCALE_FREE:
    {
      uint16_t cap;
      uint8_t m;
      cap = (uint16_t) va_arg (vargs, unsigned int);
      m = (uint8_t) va_arg (vargs, unsigned int);
      gen_topo_scale_free (&tc, cap, m);
    }
    break;
 
  default:
    GNUNET_assert (0);
  }
  va_end (vargs);
  for (cnt = 0; cnt < tc.link_array_size; cnt++)
  {
    ulink = &underlay->link_array[cnt];
    if (GNUNET_SYSERR == proc (cls,
                               ulink->A,
                               ulink->B,
                               ulink->bandwidth,
                               ulink->latency,
                               ulink->loss))
    {
      ret = GNUNET_SYSERR;
      break;
    }
  }
  GNUNET_free (underlay->link_array);
  return ret;
}

References UnderlayLink::A, UnderlayLink::B, UnderlayLink::bandwidth, filename, gen_topo_2dtorus(), gen_topo_clique(), gen_topo_from_file(), gen_topo_line(), gen_topo_random(), gen_topo_ring(), gen_topo_scale_free(), gen_topo_star(), GNUNET_assert, GNUNET_free, GNUNET_NO, GNUNET_OK, GNUNET_SYSERR, GNUNET_TESTBED_TOPOLOGY_2D_TORUS, GNUNET_TESTBED_TOPOLOGY_CLIQUE, GNUNET_TESTBED_TOPOLOGY_ERDOS_RENYI, GNUNET_TESTBED_TOPOLOGY_FROM_FILE, GNUNET_TESTBED_TOPOLOGY_LINE, GNUNET_TESTBED_TOPOLOGY_RING, GNUNET_TESTBED_TOPOLOGY_SCALE_FREE, GNUNET_TESTBED_TOPOLOGY_SMALL_WORLD, GNUNET_TESTBED_TOPOLOGY_SMALL_WORLD_RING, GNUNET_TESTBED_TOPOLOGY_STAR, GNUNET_VA_ARG_ENUM, GNUNET_YES, UnderlayLink::latency, TopologyContextUnderlay::link_array, UnderlayLink::loss, m, num_peers, ret, tc, and topology.

Referenced by run().

Here is the call graph for this function:

Here is the caller graph for this function:

Variable Documentation

topology_strings

const char* topology_strings[]

static

A array of names representing topologies.

Should be in sync with enum GNUNET_TESTBED_TopologyOption

Definition at line 259 of file testbed_api_topology.c.

Referenced by GNUNET_TESTBED_topology_get_(), and GNUNET_TESTBED_topology_to_str_().