Hypercube Networks, Butterfly Network, Shuffle Exchanges and Fault Tolerant Designs

05 Mar

Hypercube Networks

A network control system in a hyper cube type network having 2n nodes (n>0, integer), each of the nodes being arranged on an apex of a cube and having n sets of links for interconnecting other nodes so as to form an n-dimensional hyper cube type network; a plurality of processors, each processor being connected to each node by input/output links, thereby providing communication paths between processors through the nodes and links; each of the nodes comprising: a device for setting 2n different connection patterns corresponding to 2n phase signals, and a switching device for interconnecting between the links and between the input/output links in accordance with the connection patterns synchronized with the phase signals.

Butterfly Network

In the butterfly network, there are two sources (at the top of the picture), each having knowledge of some value A and B. There are two destination nodes (at the bottom), which each want to know both A and B. Each edge can carry only a single value (we can think of an edge transmitting a bit in each time slot).

If we only used routing, then the central line would be able to carry A or B, but not both. Suppose we send A through the center; then the left destination would receive A twice and not know B at all. Sending B poses a similar problem for the right destination. We say that routing is insufficient because no routing scheme can transmit both A and B simultaneously to both destinations.

Shuffle Exchanges

The adjacency in orthogonal and hypercubic topologies is based on incrementing and/or inverting coordinates. In shuffle topologies, the adjacency is based on shifting the whole strings, typical operation is left shift and left rotation by one position, which enforces orientation on edges. Since most of notions and results apply equally to both directed and undirected versions of these topologies and digraphs are regular in contrast to undirected graphs, we will concentrate on digraphs only. Shuffle-based topologies have very rich, but also rather complicated structure. In general, they are more difficult to understand compared to previous topologies. They have the following properties:

  • Logarithmic diameter and constant vertex degree.
  • Optimal or nearly optimal connectivity.
  • Fault diameter nearly the same as non faulty one, similarly for fault average distances.
  • Large bisection width of order N/log N.
  • Simple shortest-path routing.
  • They are neither symmetric nor hierarchically recursive.
  • They are rich of cycles of various lengths, since the rotation induces equivalence classes of vertices called necklaces.
  • At the same time, they are rich of subtrees and spanning trees, since the general shift operation induces subtrees.

The shuffle-based family includes three main topologies, shuffle exchange, de Bruijn, and Kautz, and their variations. We will describe only the first two main ones.

Fault Tolerant Designs

Fault tolerant design provides a means to achieve a balanced project risk where the cost of failure protection is commensurate with the program resources and the mission criticality of the equipment. By providing compensation for potential hardware failures, a fault tolerant design approach may achieve reliability objectives without recourse to non-optimized redundancy or overdesign.

Go to Exercise # 2

Leave a comment

Posted by on March 5, 2011 in Topic 4


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: