Fault-tolerant gamma interconnection network without backtracking

Ching Wen Chen*, Chung-Ping Chung

*Corresponding author for this work

Research output: Contribution to journalArticle

11 Scopus citations


A no-backtracking gamma interconnection network (NBGIN) is a modified gamma interconnection network (GIN) that can tolerate one switch or link fault without backward packet transmission. Basically, this can be achieved by providing two alternative paths at all intermediate nodes during the progression of routing through carefully designed algorithm. In this work, a destination tag routing named as NB function is designed. With this NB function, a packet can find an alternate path as soon as it encounters a switch or link fault in NBGIN. The major advantage of NBGIN over gamma-induced networks is that there is no rerouting penalty under a fault. In addition, NBGIN processes the characteristics of one-fault tolerance, destination tag routing, and dynamic rerouting. Furthermore, the routing and rerouting path can be simply determined by the destination tag only instead of being computed with the routing tag.

Original languageEnglish
Pages (from-to)23-31
Number of pages9
JournalJournal of Systems and Software
Issue number1
StatePublished - 15 Aug 2001


  • Backtracking
  • Destination tag routing
  • Disjoint paths
  • Distance tag routing
  • Gamma interconnection network

Fingerprint Dive into the research topics of 'Fault-tolerant gamma interconnection network without backtracking'. Together they form a unique fingerprint.

  • Cite this