Embedding paths of variable lengths into hypercubes with conditional link-faults

ASIA unversity > 資訊學院 > 資訊工程學系 > 期刊論文 > Item 310904400/8691

Please use this identifier to cite or link to this item: http://asiair.asia.edu.tw/ir/handle/310904400/8691

Title:	Embedding paths of variable lengths into hypercubes with conditional link-faults
Authors:	Kueng, Tz-Liang;Lin, Cheng-Kuan;Liang, Tyne;Tan, Jimmy J.M.;Hsu, Lih-Hsing
Contributors:	Department of Computer Science and Information Engineering
Keywords:	Array processing;Fault tolerance;Frequency modulation;Geometry;Interconnection networks;Conditional fault;Fault diameter;Fault-tolerant capability;Faulty links;Hardware failures;Hyper-cubes;Hypercube;Linear array;Path embedding;Software errors;Variable length
Date:	2009
Issue Date:	2010-04-07 13:27:24 (UTC+0)
Publisher:	Asia University
Abstract:	Faults in a network may take various forms such as hardware failures while a node or a link stops functioning, software errors, or even missing of transmitted packets. In this paper, we study the link-fault-tolerant capability of an n-dimensional hypercube (n-cube for short) with respect to path embedding of variable lengths in the range from the shortest to the longest. Let F be a set consisting of faulty links in a wounded n-cube Q<inf>n</inf>, in which every node is still incident to at least two fault-free links. Then we show that Q<inf>n</inf> - F has a path of any odd (resp. even) length in the range from the distance to 2<sup>n</sup> - 1 (resp. 2<sup>n</sup> - 2) between two arbitrary nodes even if \| F \| = 2 n - 5. In order to tackle this problem, we also investigate the fault diameter of an n-cube with hybrid node and link faults. © 2009 Elsevier B.V. All rights reserved.
Relation:	Parallel Computing 35(8-9):441-454
Appears in Collections:	[資訊工程學系] 期刊論文

Files in This Item:

File	Description	Size	Format
		0Kb	Unknown	475	View/Open
121.doc		30Kb	Microsoft Word	214	View/Open

Loading...