A unified theory of interconnection network structure (Q1088405)

The relationship between the topology of interconnection networks and their functional properties is examined. Graph-theoretical characterizations are derived for delta networks, which have a simple routing scheme, and for bidelta networks, which have the delta property in both directions. Delta networks are shown to have a recursive structure. Bidelta networks are shown to have a unique topology. The definition of bidelta network is used to derive in a uniform manner the labelling schemes that define the omega networks, indirect binary cube networks, flip networks, baseline networks, modified data manipulators and two new networks; these schemes are generalized to arbitrary radices. The labelling schemes are used to characterize networks with simple routing. In another paper [Current advances in distributed computing and communications, 91-113 (1987; Zbl 0604.68036)], we characterize the networks with optimal performance/cost ratio. Only the multistage shuffle-exchange networks have both optimal performance/cost ratio and simple routing. This helps explain why few fundamentally different geometries have been proposed.