next up previous
Next: 3 Routing around faults Up: 2 Butterflies and Multibutterflies Previous: 2.2 Splitter networks

2.3 Randomly-wired splitter networks and multibutterflies

In this paper, we are primarily concerned with randomly-wired splitter networks. A randomly-wired splitter network with multiplicity d is a splitter network where the up and down edges within each splitter are chosen at random subject to the constraint that each splitter input has d up and d down edges, and each splitter output has 2d incoming edges.

The crucial property that randomly-wired splitter networks are likely to possess [7, 12] is known as expansion. In particular, an M-input splitter is said to have tex2html_wrap_inline737 -expansion if every set of tex2html_wrap_inline739 inputs is connected to at least tex2html_wrap_inline741 up outputs and tex2html_wrap_inline743 down outputs, where tex2html_wrap_inline745 and tex2html_wrap_inline747 are fixed constants. For example, see Figure 4.

A splitter network is said to have tex2html_wrap_inline749 -expansion if all of its splitters have tex2html_wrap_inline751 -expansion. More simply, a splitter or a splitter network is said to have expansion if it has tex2html_wrap_inline753 -expansion for some constants tex2html_wrap_inline755 and tex2html_wrap_inline757 . A splitter network with expansion is more commonly known as a multibutterfly [12].

Splitters with expansion are known to exist for any tex2html_wrap_inline759 , and they can be constructed deterministically in polynomial time [2, 9, 12], but randomized wirings typically provide better expansion. A discussion of the tradeoffs between tex2html_wrap_inline761 and tex2html_wrap_inline763 in randomly-wired splitters, can be found in [7] and [12]. For the purposes of this paper, two facts are needed. First, for fixed d and sufficiently small tex2html_wrap_inline767 , the expansion, tex2html_wrap_inline769 , of a randomly-wired splitter will be close to d-1 with probability close to 1. Second, for fixed tex2html_wrap_inline775 and sufficiently large d, tex2html_wrap_inline779 will be close tex2html_wrap_inline781 (the best possible) with probability close to 1. It is not known if it is possible for tex2html_wrap_inline785 to be close to d-1 and for tex2html_wrap_inline789 to be close to tex2html_wrap_inline791 simultaneously.

A multibutterfly with tex2html_wrap_inline793 -expansion is good at routing because one must block tex2html_wrap_inline795 splitter outputs in order to block k splitter inputs. In classical networks such as the butterfly, the reverse is true: it is possible to block 2k inputs by blocking only k outputs. When this effect is compounded over several levels, the effect is dramatic. In a butterfly, a single fault can block tex2html_wrap_inline803 switches l levels back, whereas in a multibutterfly, it takes tex2html_wrap_inline807 faults to block a single switch l levels back.

Figure 4: An M-input splitter with tex2html_wrap_inline813 -expansion.

next up previous
Next: 3 Routing around faults Up: 2 Butterflies and Multibutterflies Previous: 2.2 Splitter networks

Bruce Maggs
Mon Jul 22 19:56:03 EDT 1996