Fault-tolerant message routing in hypercube using local neighborhood information

We present fault-tolerant message (packet) routing algorithms for hypercubes 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 th...

Full description

Saved in:
Bibliographic Details
Main Authors: Pao, D.C.W., Chi-Kueng Chan
Format: Conference Proceeding
Language:English
Subjects:
Cities and towns
Fault tolerance
Hamming distance
Heuristic algorithms
Hypercubes
Peer to peer computing
Routing
System recovery
Online Access:Request full text
Tags: Add Tag
No Tags, Be the first to tag this record!
cited_by
cites
container_end_page 444 vol.1
container_issue
container_start_page 440
container_title
container_volume
creator Pao, D.C.W.
Chi-Kueng Chan
description We present fault-tolerant message (packet) routing algorithms for hypercubes 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 /spl Omega/(k/sup 2/) faults are required to make a packet to undertake a route of length 3k. A 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.< >
doi_str_mv 10.1109/TENCON.1994.369262
format conference_proceeding
fullrecord <record><control><sourceid>ieee_6IE</sourceid><recordid>TN_cdi_ieee_primary_369262</recordid><sourceformat>XML</sourceformat><sourcesystem>PC</sourcesystem><ieee_id>369262</ieee_id><sourcerecordid>369262</sourcerecordid><originalsourceid>FETCH-LOGICAL-i104t-7748e8fccb6947b879a4dfd3588909d033a79891dc8b5aa3143631416c3960823</originalsourceid><addsrcrecordid>eNotj0tqwzAYhAWl0DbNBbLSBexKlqzHspikLYQki3QdZPm3rWJbQZIXuX1d0lnMwMcwMAhtKMkpJfrtvD1Ux0NOteY5E7oQxQN6IVIRRpUoyie0jvGHLOIlkZQ9o9POzEPKkh8gmCnhEWI0HeDg5-SmDrsJ97crBDvXgOf4hwZvzYAncF1f-9B73yyt1ofRJOenV_TYmiHC-j9X6Hu3PVef2f748VW97zNHCU-ZlFyBaq2theayVlIb3rQNK5XSRDeEMSO10rSxqi6NYZQzsRgVlmlBVMFWaHPfdQBwuQY3mnC73D-zXwgHTcY</addsrcrecordid><sourcetype>Publisher</sourcetype><iscdi>true</iscdi><recordtype>conference_proceeding</recordtype></control><display><type>conference_proceeding</type><title>Fault-tolerant message routing in hypercube using local neighborhood information</title><source>IEEE Electronic Library (IEL) Conference Proceedings</source><creator>Pao, D.C.W. ; Chi-Kueng Chan</creator><creatorcontrib>Pao, D.C.W. ; Chi-Kueng Chan</creatorcontrib><description>We present fault-tolerant message (packet) routing algorithms for hypercubes 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 /spl Omega/(k/sup 2/) faults are required to make a packet to undertake a route of length 3k. A 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.&lt; &gt;</description><identifier>ISBN: 0780318625</identifier><identifier>ISBN: 9780780318625</identifier><identifier>DOI: 10.1109/TENCON.1994.369262</identifier><language>eng</language><publisher>IEEE</publisher><subject>Cities and towns ; Fault tolerance ; Hamming distance ; Heuristic algorithms ; Hypercubes ; Peer to peer computing ; Routing ; System recovery</subject><ispartof>Proceedings of TENCON'94 - 1994 IEEE Region 10's 9th Annual International Conference on: 'Frontiers of Computer Technology', 1994, p.440-444 vol.1</ispartof><woscitedreferencessubscribed>false</woscitedreferencessubscribed></display><links><openurl>$$Topenurl_article</openurl><openurlfulltext>$$Topenurlfull_article</openurlfulltext><thumbnail>$$Tsyndetics_thumb_exl</thumbnail><linktohtml>$$Uhttps://ieeexplore.ieee.org/document/369262$$EHTML$$P50$$Gieee$$H</linktohtml><link.rule.ids>309,310,780,784,789,790,2058,4050,4051,27925,54920</link.rule.ids><linktorsrc>$$Uhttps://ieeexplore.ieee.org/document/369262$$EView_record_in_IEEE$$FView_record_in_$$GIEEE</linktorsrc></links><search><creatorcontrib>Pao, D.C.W.</creatorcontrib><creatorcontrib>Chi-Kueng Chan</creatorcontrib><title>Fault-tolerant message routing in hypercube using local neighborhood information</title><title>Proceedings of TENCON'94 - 1994 IEEE Region 10's 9th Annual International Conference on: 'Frontiers of Computer Technology'</title><addtitle>TENCON</addtitle><description>We present fault-tolerant message (packet) routing algorithms for hypercubes 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 /spl Omega/(k/sup 2/) faults are required to make a packet to undertake a route of length 3k. A 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.&lt; &gt;</description><subject>Cities and towns</subject><subject>Fault tolerance</subject><subject>Hamming distance</subject><subject>Heuristic algorithms</subject><subject>Hypercubes</subject><subject>Peer to peer computing</subject><subject>Routing</subject><subject>System recovery</subject><isbn>0780318625</isbn><isbn>9780780318625</isbn><fulltext>true</fulltext><rsrctype>conference_proceeding</rsrctype><creationdate>1994</creationdate><recordtype>conference_proceeding</recordtype><sourceid>6IE</sourceid><recordid>eNotj0tqwzAYhAWl0DbNBbLSBexKlqzHspikLYQki3QdZPm3rWJbQZIXuX1d0lnMwMcwMAhtKMkpJfrtvD1Ux0NOteY5E7oQxQN6IVIRRpUoyie0jvGHLOIlkZQ9o9POzEPKkh8gmCnhEWI0HeDg5-SmDrsJ97crBDvXgOf4hwZvzYAncF1f-9B73yyt1ofRJOenV_TYmiHC-j9X6Hu3PVef2f748VW97zNHCU-ZlFyBaq2theayVlIb3rQNK5XSRDeEMSO10rSxqi6NYZQzsRgVlmlBVMFWaHPfdQBwuQY3mnC73D-zXwgHTcY</recordid><startdate>1994</startdate><enddate>1994</enddate><creator>Pao, D.C.W.</creator><creator>Chi-Kueng Chan</creator><general>IEEE</general><scope>6IE</scope><scope>6IL</scope><scope>CBEJK</scope><scope>RIE</scope><scope>RIL</scope></search><sort><creationdate>1994</creationdate><title>Fault-tolerant message routing in hypercube using local neighborhood information</title><author>Pao, D.C.W. ; Chi-Kueng Chan</author></sort><facets><frbrtype>5</frbrtype><frbrgroupid>cdi_FETCH-LOGICAL-i104t-7748e8fccb6947b879a4dfd3588909d033a79891dc8b5aa3143631416c3960823</frbrgroupid><rsrctype>conference_proceedings</rsrctype><prefilter>conference_proceedings</prefilter><language>eng</language><creationdate>1994</creationdate><topic>Cities and towns</topic><topic>Fault tolerance</topic><topic>Hamming distance</topic><topic>Heuristic algorithms</topic><topic>Hypercubes</topic><topic>Peer to peer computing</topic><topic>Routing</topic><topic>System recovery</topic><toplevel>online_resources</toplevel><creatorcontrib>Pao, D.C.W.</creatorcontrib><creatorcontrib>Chi-Kueng Chan</creatorcontrib><collection>IEEE Electronic Library (IEL) Conference Proceedings</collection><collection>IEEE Proceedings Order Plan All Online (POP All Online) 1998-present by volume</collection><collection>IEEE Xplore All Conference Proceedings</collection><collection>IEL</collection><collection>IEEE Proceedings Order Plans (POP All) 1998-Present</collection></facets><delivery><delcategory>Remote Search Resource</delcategory><fulltext>fulltext_linktorsrc</fulltext></delivery><addata><au>Pao, D.C.W.</au><au>Chi-Kueng Chan</au><format>book</format><genre>proceeding</genre><ristype>CONF</ristype><atitle>Fault-tolerant message routing in hypercube using local neighborhood information</atitle><btitle>Proceedings of TENCON'94 - 1994 IEEE Region 10's 9th Annual International Conference on: 'Frontiers of Computer Technology'</btitle><stitle>TENCON</stitle><date>1994</date><risdate>1994</risdate><spage>440</spage><epage>444 vol.1</epage><pages>440-444 vol.1</pages><isbn>0780318625</isbn><isbn>9780780318625</isbn><abstract>We present fault-tolerant message (packet) routing algorithms for hypercubes 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 /spl Omega/(k/sup 2/) faults are required to make a packet to undertake a route of length 3k. A 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.&lt; &gt;</abstract><pub>IEEE</pub><doi>10.1109/TENCON.1994.369262</doi></addata></record>
fulltext fulltext_linktorsrc
identifier ISBN: 0780318625
ispartof Proceedings of TENCON'94 - 1994 IEEE Region 10's 9th Annual International Conference on: 'Frontiers of Computer Technology', 1994, p.440-444 vol.1
issn
language eng
recordid cdi_ieee_primary_369262
source IEEE Electronic Library (IEL) Conference Proceedings
subjects Cities and towns
Fault tolerance
Hamming distance
Heuristic algorithms
Hypercubes
Peer to peer computing
Routing
System recovery
title Fault-tolerant message routing in hypercube using local neighborhood information
url http://sfxeu10.hosted.exlibrisgroup.com/loughborough?ctx_ver=Z39.88-2004&ctx_enc=info:ofi/enc:UTF-8&ctx_tim=2025-01-04T07%3A49%3A52IST&url_ver=Z39.88-2004&url_ctx_fmt=infofi/fmt:kev:mtx:ctx&rfr_id=info:sid/primo.exlibrisgroup.com:primo3-Article-ieee_6IE&rft_val_fmt=info:ofi/fmt:kev:mtx:book&rft.genre=proceeding&rft.atitle=Fault-tolerant%20message%20routing%20in%20hypercube%20using%20local%20neighborhood%20information&rft.btitle=Proceedings%20of%20TENCON'94%20-%201994%20IEEE%20Region%2010's%209th%20Annual%20International%20Conference%20on:%20'Frontiers%20of%20Computer%20Technology'&rft.au=Pao,%20D.C.W.&rft.date=1994&rft.spage=440&rft.epage=444%20vol.1&rft.pages=440-444%20vol.1&rft.isbn=0780318625&rft.isbn_list=9780780318625&rft_id=info:doi/10.1109/TENCON.1994.369262&rft_dat=%3Cieee_6IE%3E369262%3C/ieee_6IE%3E%3Cgrp_id%3Ecdi_FETCH-LOGICAL-i104t-7748e8fccb6947b879a4dfd3588909d033a79891dc8b5aa3143631416c3960823%3C/grp_id%3E%3Coa%3E%3C/oa%3E%3Curl%3E%3C/url%3E&rft_id=info:oai/&rft_id=info:pmid/&rft_ieee_id=369262&rfr_iscdi=true