An example of an 8-input butterfly network is illustrated in Figure 1. The nodes in this graph represent switches, and the edges represent wires. Each node in the network has a distinct label , where r is the row, and l is the level. In a butterfly with N inputs, the row is a -bit binary number and the level is an integer between 0 and . The nodes on level 0 and are called the inputs and outputs, respectively. For , a node labeled is connected to nodes and , where denotes r with bit l complemented (bit 0 is the most significant, bit the least).
In a butterfly, messages are typically sent from the switches on level 0, called the inputs, to those on level , called the outputs. In a one-to-one routing problem, each input is the origin of at most one message, and each output is the destination of a most one message. One-to-one routing is also called permutation routing.
Figure 1: An 8-input butterfly network.