## Abstract

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 (Kruskal/Snir, 1984), 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.

Original language | English (US) |
---|---|

Pages (from-to) | 75-94 |

Number of pages | 20 |

Journal | Theoretical Computer Science |

Volume | 48 |

Issue number | C |

DOIs | |

State | Published - 1986 |

Externally published | Yes |

## Keywords

- Banyan network
- baseline network
- bidelta network
- capacity
- delay
- delta network
- flip network
- indirect binary cube network
- interconnection network
- isomorphism
- multistage network
- omega network
- packet-switching network
- routing
- topological equivalence

## ASJC Scopus subject areas

- Theoretical Computer Science
- Computer Science(all)