Optimal, and reliable communication in hypercubes using extended safety vectors

doi:10.1106/TR.2005.853439

CORC > 计算技术研究所 > 中国科学院计算技术研究所 > 中国科学院计算技术研究所期刊论文 > 英文

	Optimal, and reliable communication in hypercubes using extended safety vectors
	Wu, J ; Gao, F ; Li, ZC ; Min, YH
刊名	IEEE TRANSACTIONS ON RELIABILITY
	2005-09-01
卷号	54 期号:3 页码:402-411
关键词	fault-tolerant routing generalized hypercubes multicomputers reliable communication safety vectors
ISSN号	0018-9529
DOI	10.1106/TR.2005.853439
英文摘要	We propose a new coding method of limited global fault information in an n-cube. First, each node collects precise fault information within distance-d, and then fault information about nodes that are more than distance-d away is coded in a special way. Specifically, in our approach, each node in a cube-based multicomputer of dimension n is associated with an extended safety vector of n bits. In the extended safety vector model, each node knows fault information within distance-2; fault information outside distance-2 is coded in a special way based on the coded information of its neighbors. The extended safety vector of each node can be easily calculated through n - 1 rounds of information exchanges among neighboring nodes. Therefore, each extended safety vector is an approximated measure of the number & distribution of faults in the neighborhood. Optimal unicasting between two nodes is guaranteed if the kth bit of the safety vector of the source node is one, where k is the Hamming distance between the source & destination nodes. In addition, the extended safety vector can be used as a navigation tool to direct a message to its destination through a minimal path. A simulation study has been conducted based on different selections of d, and results have shown a significant improvement under the proposed model over the safety vector model in handling link faults, even for a small value of d as in the extended safety vector model where d = 2.
WOS研究方向	Computer Science ; Engineering
语种	英语
出版者	IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC
WOS记录号	WOS:000231693400006
内容类型	期刊论文
源URL	[http://119.78.100.204/handle/2XEOYT63/10014]
专题	中国科学院计算技术研究所期刊论文_英文
通讯作者	Wu, J
作者单位	1.Chinese Acad Sci, Inst Comp Technol, CAD Lab, Beijing, Peoples R China 2.Florida Atlantic Univ, Dept Comp Sci & Engn, Boca Raton, FL 33431 USA 3.Univ Michigan, Adv Comp Architecture Lab, Ann Arbor, MI 48105 USA
推荐引用方式 GB/T 7714	Wu, J,Gao, F,Li, ZC,et al. Optimal, and reliable communication in hypercubes using extended safety vectors[J]. IEEE TRANSACTIONS ON RELIABILITY,2005,54(3):402-411.
APA	Wu, J,Gao, F,Li, ZC,&Min, YH.(2005).Optimal, and reliable communication in hypercubes using extended safety vectors.IEEE TRANSACTIONS ON RELIABILITY,54(3),402-411.
MLA	Wu, J,et al."Optimal, and reliable communication in hypercubes using extended safety vectors".IEEE TRANSACTIONS ON RELIABILITY 54.3(2005):402-411.