Standard 2x2-Switch Banyan Networks and Their Graphs

摘要

The standard networks of the paper are the Omega network of Lawrie and itsvarious equivalent counterparts and another network which corresponds to the CC-banyan, or restricted data manipulator, but is also built from 2x2-crossbar switches. The author presents several characterizations of the graphs which determine the linkage of the switches in these networks. For the graph of the Omega network such a characterization has recently been given by Bermond, Fourneau and Jean-Marie and some of the descriptions of the paper are variants of, or inspired by their findings. Apart from the banyan property and conditions on the components of certain subgraphs, use is made of variations of the familiar buddy property. The paper also contains a discussion of some of the basic concepts of networks, switch graphs, banyans, and equivalence and an investigation of the automorphisms of the graphs of the afore-mentioned networks. (Copyright (c) GMD 1990.)