Fault-tolerant message routing in hypercube using local neighborhood information

Derek C. W. Pao; Chi Kueng Chan

doi:10.1109/TENCON.1994.369262

Fault-tolerant message routing in hypercube using local neighborhood information

Derek C. W. Pao, Chi Kueng Chan

Department of Electrical Engineering

Research output: Chapters, Conference Papers, Creative and Literary Works › RGC 32 - Refereed conference paper (with host publication) › peer-review

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 Ω(k²) 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.

Original language	English
Title of host publication	Proceedings of TENCON'94 - 1994 IEEE Region 10's 9th Annual International Conference on: 'Frontiers of Computer Technology'
Publisher	IEEE
Pages	440-444
Volume	1
ISBN (Print)	0-7803-1862-5
DOIs	https://doi.org/10.1109/TENCON.1994.369262
Publication status	Published - Aug 1995
Event	1994 IEEE Region 10's 9th Annual International Conference (TENCON'94) - , Singapore Duration: 22 Aug 1994 → 26 Aug 1994

Conference

Conference	1994 IEEE Region 10's 9th Annual International Conference (TENCON'94)
Place	Singapore
Period	22/08/94 → 26/08/94

Access Output

10.1109/TENCON.1994.369262

Other Access Options

Check CityUHK Library

Permanent Link

Right click to copy link

Cite this

@inproceedings{d8617d1dfa0445b182ba366f2d91a26b,

title = "Fault-tolerant message routing in hypercube using local neighborhood information",

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.",

author = "Pao, {Derek C. W.} and Chan, {Chi Kueng}",

year = "1995",

month = aug,

doi = "10.1109/TENCON.1994.369262",

language = "English",

isbn = "0-7803-1862-5",

volume = "1",

pages = "440--444",

booktitle = "Proceedings of TENCON'94 - 1994 IEEE Region 10's 9th Annual International Conference on: 'Frontiers of Computer Technology'",

publisher = "IEEE",

address = "United States",

note = "1994 IEEE Region 10's 9th Annual International Conference (TENCON'94) ; Conference date: 22-08-1994 Through 26-08-1994",

}

Pao, DCW & Chan, CK 1995, Fault-tolerant message routing in hypercube using local neighborhood information. in Proceedings of TENCON'94 - 1994 IEEE Region 10's 9th Annual International Conference on: 'Frontiers of Computer Technology'. vol. 1, IEEE, pp. 440-444, 1994 IEEE Region 10's 9th Annual International Conference (TENCON'94), Singapore, 22/08/94. https://doi.org/10.1109/TENCON.1994.369262

Fault-tolerant message routing in hypercube using local neighborhood information. / Pao, Derek C. W.; Chan, Chi Kueng.
Proceedings of TENCON'94 - 1994 IEEE Region 10's 9th Annual International Conference on: 'Frontiers of Computer Technology'. Vol. 1 IEEE, 1995. p. 440-444.

Research output: Chapters, Conference Papers, Creative and Literary Works › RGC 32 - Refereed conference paper (with host publication) › peer-review

TY - GEN

T1 - Fault-tolerant message routing in hypercube using local neighborhood information

AU - Pao, Derek C. W.

AU - Chan, Chi Kueng

PY - 1995/8

Y1 - 1995/8

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=0029219076&partnerID=8YFLogxK

UR - https://www.scopus.com/record/pubmetrics.uri?eid=2-s2.0-0029219076&origin=recordpage

U2 - 10.1109/TENCON.1994.369262

DO - 10.1109/TENCON.1994.369262

M3 - RGC 32 - Refereed conference paper (with host publication)

SN - 0-7803-1862-5

VL - 1

SP - 440

EP - 444

BT - Proceedings of TENCON'94 - 1994 IEEE Region 10's 9th Annual International Conference on: 'Frontiers of Computer Technology'

PB - IEEE

T2 - 1994 IEEE Region 10's 9th Annual International Conference (TENCON'94)

Y2 - 22 August 1994 through 26 August 1994

ER -

Fault-tolerant message routing in hypercube using local neighborhood information

Abstract

Conference

Access Output

Other Access Options

Permanent Link

Other Files and Links

Fingerprint

Cite this