A unified theory of interconnection network structure

Clyde P. Kruskal, Marc Snir

Research output: Contribution to journalArticlepeer-review


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 languageEnglish (US)
Pages (from-to)75-94
Number of pages20
JournalTheoretical Computer Science
Issue numberC
StatePublished - 1986
Externally publishedYes


  • 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)


Dive into the research topics of 'A unified theory of interconnection network structure'. Together they form a unique fingerprint.

Cite this