Fault-tolerant message routing in hypercube using local neighborhood information

Research output: Chapters, Conference Papers, Creative and Literary Works (RGC: 12, 32, 41, 45)32_Refereed conference paper (with ISBN/ISSN)peer-review

View graph of relations

Author(s)

Detail(s)

Original languageEnglish
Title of host publicationIEEE Region 10's Annual International Conference, Proceedings
PublisherIEEE
Pages440-444
Volume1
Publication statusPublished - 1995

Publication series

Name
Volume1

Conference

TitleProceedings of the 1994 IEEE Region 10's 9th Annual International Conference (TENCON'94). Part 1 (of 2)
CitySingapore, Singapore
Period22 - 26 August 1994

Abstract

We present fault-tolerant message (packet) routing algorithms for hypercube that make use of the 2-neighborhood information. Our algorithms can tolerate (i) up to n faulty components in any Hamming ball of radius 3, and (ii) up to n-1 faulty components in the Hamming ball of radius 2 centered at the destination node. The path length of the packet is less than or equal to 3k, where k is the Hamming distance from the source to destination. We also show that Ω(k2) faults are required to make a packet to undertake a route of length 3k. Simulation study of the performance of the routing algorithms is presented. The structured buffer pool technique can be incorporated into our routing algorithms to prevent deadlock from occurring.

Citation Format(s)

Fault-tolerant message routing in hypercube using local neighborhood information. / Pao, Derek C W; Chan, Chi Kueng.

IEEE Region 10's Annual International Conference, Proceedings. Vol. 1 IEEE, 1995. p. 440-444.

Research output: Chapters, Conference Papers, Creative and Literary Works (RGC: 12, 32, 41, 45)32_Refereed conference paper (with ISBN/ISSN)peer-review