as_waksman_routing_algorithm.hpp File Reference

#include <cstddef>
#include <libff/common/utils.hpp>
#include <libsnark/common/data_structures/integer_permutation.hpp>
#include <map>
#include <vector>

Include dependency graph for as_waksman_routing_algorithm.hpp:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Namespaces
	libsnark

Typedefs
typedef std::vector< std::vector< std::pair< size_t, size_t > > >	libsnark::as_waksman_topology
typedef std::vector< std::map< size_t, bool > >	libsnark::as_waksman_routing

Functions
size_t	libsnark::as_waksman_num_columns (const size_t num_packets)
as_waksman_topology	libsnark::generate_as_waksman_topology (const size_t num_packets)
as_waksman_routing	libsnark::get_as_waksman_routing (const integer_permutation &permutation)
bool	libsnark::valid_as_waksman_routing (const integer_permutation &permutation, const as_waksman_routing &routing)

Detailed Description

Declaration of interfaces for functionality for routing on an arbitrary-size (AS) Waksman network.

AS-Waksman networks were introduced in [BD02]. An AS-Waksman network for N packets is recursively defined as follows: place a column of floor(N/2) switches on the left, and a column of floor(N/2) switches on the right; then place two AS-Waksman sub-networks, for floor(N/2) and ceil(N/2) packets respectively, in the middle.

Note that unlike for Beneš networks where each switch handles routing of one packet to one of its two possible destinations, AS-Waksman network employs switches with two input ports and two output ports and operate either in "straight" or "cross mode".

Routing is performed in a way that is similar to routing on Benes networks: one first computes the switch settings for the left and right columns, and then one recursively computes routings for the top and bottom sub-networks. More precisely, as in [BD02], we treat the problem of determining the switch settings of the left and right columns as a 2-coloring problem on a certain bipartite graph. The coloring is found by performing a depth-first search on the graph and alternating the color at every step. For performance reasons the graph in our implementation is implicitly represented.

References:

[BD02]: "On arbitrary size {W}aksman networks and their vulnerability", Bruno Beauquier, Eric Darrot, Parallel Processing Letters 2002

Author

This file is part of libsnark, developed by SCIPR Lab and contributors (see AUTHORS).

Copyright

MIT license (see LICENSE file)

Definition in file as_waksman_routing_algorithm.hpp.