next up previous
Next: 1.4 Our results Up: 1 Introduction Previous: 1.2 Splitter networks

1.3 Randomly-wired splitter networks and multibutterflies

In this paper, we are primarily concerned with randomly-wired splitter networks. A randomly-wired splitter network 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 is incident to d up and d down edges, and each splitter output is incident to 2d incoming edges.

The crucial property that randomly-wired splitter networks are likely to possess is known as expansion. In particular, an M-input splitter is said to have tex2html_wrap_inline1313 -expansion if every set of tex2html_wrap_inline1315 inputs is connected to at least tex2html_wrap_inline1317 up outputs and tex2html_wrap_inline1319 down outputs, where tex2html_wrap_inline1321 and tex2html_wrap_inline1323 are fixed constants. For example, see Figure 4.

A splitter network is said to have tex2html_wrap_inline1325 -expansion if all of its splitters have tex2html_wrap_inline1327 -expansion. More simply, a splitter or a splitter network is said to have expansion if it has tex2html_wrap_inline1329 -expansion for some constants tex2html_wrap_inline1331 and tex2html_wrap_inline1333 . A splitter network with expansion is more commonly known as a multibutterfly [29], and a multibutterfly with tex2html_wrap_inline1335 -expansion and multiplicity d consists of splitters in which each splitter input is incident to d up and d down edges and for which any tex2html_wrap_inline1343 splitter inputs are adjacent to tex2html_wrap_inline1345 splitter outputs.

Splitters with expansion are known to exist for any tex2html_wrap_inline1347 , and they can be constructed deterministically in polynomial time [11, 23, 29], but randomized wirings typically provide the best possible expansion. In fact, the expansion of a randomly-wired splitter will be close to d-1 with probability close to 1, provided that tex2html_wrap_inline1353 is a sufficiently small constant. (For a discussion of the tradeoffs between tex2html_wrap_inline1355 and tex2html_wrap_inline1357 in randomly-wired splitters, see [20, 29].)

A multibutterfly with tex2html_wrap_inline1359 -expansion is good at routing because one must block tex2html_wrap_inline1361 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_inline1369 switches l levels back, whereas in a multibutterfly, it takes tex2html_wrap_inline1373 faults to block a single switch l levels back.

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

In 1989, Upfal showed that any N-input multibutterfly can route any one-to-one problem in tex2html_wrap_inline1383 steps using a simple greedy algorithm [29], and that, by using pipelining, any N-input multibutterfly can route tex2html_wrap_inline1387 one-to-one problems in tex2html_wrap_inline1389 steps. Although the proof is complicated and the constants hidden by the Big Oh notation are large, the result is important because the only previously known deterministic on-line linear-hardware tex2html_wrap_inline1391 -step packet routing algorithm [18] requires the use of the AKS sorting circuit [1] (which is even more complicated and has even larger constant factors).

next up previous
Next: 1.4 Our results Up: 1 Introduction Previous: 1.2 Splitter networks

Bruce Maggs
Mon Jul 22 18:45:42 EDT 1996