next up previous
Next: 2.2 Splitter networks Up: 2 Butterflies and Multibutterflies Previous: 2 Butterflies and Multibutterflies

2.1 Dilated butterflies

Because message congestion is a common occurrence in real networks, the wires in butterfly networks are typically dilated, so that each wire is replaced by a channel consisting of 2 or more wires. In a d-dilated butterfly, each channel consists of d wires. Because it is harder to congest a channel than it is to congest a single wire in a butterfly, dilated butterflies are better routing networks than simple butterflies [3, 4, 10, 11].

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