A new decomposition algorithm for rearrangeable clos interconnection networks

Hyun Yeop Lee, Frank K. Hwang, John D. Carpinelli

Research output: Contribution to journalArticlepeer-review

32 Scopus citations

Abstract

We give a new decomposition algorithm to route a rearrangeable three-stage Clos network in O(nr2) time, which is faster than all existing decomposition algorithms. By performing a row-wise matrix decomposition, this algorithm routes all possible permutations, thus overcoming the limitation on realizable permutations exhibited by many other routing algorithms. This algorithm is extended to the fault tolerant Clos network which has extra switches in each stage, where it provides fault tolerance under faulty conditions and reduces routing time under submaximal fault conditions.

Original languageEnglish (US)
Pages (from-to)1572-1578
Number of pages7
JournalIEEE Transactions on Communications
Volume44
Issue number11
DOIs
StatePublished - Dec 1 1996
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Electrical and Electronic Engineering

Keywords

  • Fault tolerance
  • Interconnection networks
  • Multiprocessor systems
  • Routing algorithm

Fingerprint

Dive into the research topics of 'A new decomposition algorithm for rearrangeable clos interconnection networks'. Together they form a unique fingerprint.

Cite this