Principles and Practices of Interconnection Networks

CHAPTER 4

Butterfly Networks

While numerous topologies have been proposed over the years, almost all networks

that have actually been constructed use topologies derived from two main families:

butterflies (k-ary n-flies) or tori (k-ary n-cubes). In this chapter, we will define the

family of butterfly networks and explore its properties. Torus networks are examined

in Chapter 5.

A butterfly network is the quintessential indirect network. The butterfly topology

has the minimum diameter for an N node network with switches of degree δ = 2k,

H = log

k

N + 1. Although this optimal diameter is an attractive feature, butterfly

networks have two main drawbacks. First, the ...