Some directed graph theorems for testing the dynamic full access property of multistage interconnection networks

Tsern-Huei Lee*, Jin Jye Chou

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contribution

5 Scopus citations

Abstract

Fault tolerance of multistage interconnection networks (MINs) has been an important issue for many years. Multiple-pass routing is a technique to make an MIN fault tolerant without adding redundant circuits. The basic idea of multiple-pass routing is to route a packet through a faulty MIN several times, if necessary, until it is delivered to its proper destination. In order to utilize multiple-pass routing schemes, a faulty MIN must possess the dynamic full access (DFA) property. In this paper, we present a simple procedure for testing the DFA property of a faulty MIN based on a theorem from graph theory. The testing procedure can be applied to find all the subsystems possessing DFA property. Besides, we also introduce the concept of possessing the DFA property within k passes. The shortest path algorithms are applied to check whether or not a faulty MIN possesses the DFA property within k passes.

Original languageEnglish
Title of host publicationProceedings of the 10th IEEE Region Conference on Computer, Communication, Control and Power Engineering
PublisherPubl by IEEE
Pages217-220
Number of pages4
ISBN (Print)0780312333
DOIs
StatePublished - 1 Dec 1993
EventProceedings of the 1993 IEEE Region 10 Conference on Computer, Communication, Control and Power Engineering (TENCON '93). Part 1 (of 5) - Beijing, China
Duration: 19 Oct 199321 Oct 1993

Publication series

NameProceedings of the 10th IEEE Region Conference on Computer, Communication, Control and Power Engineering

Conference

ConferenceProceedings of the 1993 IEEE Region 10 Conference on Computer, Communication, Control and Power Engineering (TENCON '93). Part 1 (of 5)
CityBeijing, China
Period19/10/9321/10/93

Fingerprint Dive into the research topics of 'Some directed graph theorems for testing the dynamic full access property of multistage interconnection networks'. Together they form a unique fingerprint.

  • Cite this

    Lee, T-H., & Chou, J. J. (1993). Some directed graph theorems for testing the dynamic full access property of multistage interconnection networks. In Proceedings of the 10th IEEE Region Conference on Computer, Communication, Control and Power Engineering (pp. 217-220). (Proceedings of the 10th IEEE Region Conference on Computer, Communication, Control and Power Engineering). Publ by IEEE. https://doi.org/10.1109/TENCON.1993.319967