Abstract
The hypercube architecture has been considered a useful host to simulate many networks. However, when processors on hypercubes become faulty, the simulated topologies may no longer be valid and, thus, the system needs to invoke some reconfiguration algorithm to recover the topology. The efficiency of this reconfiguration depends heavily on the initial embedding method. This paper proposes a general scheme based on the idea of divide and conquer that efficiently embeds even length rings on hypercubes with small expansion and recovery cost. It is shown that the average expansion for the proposed scheme is 1.58, and the average number of recovery steps is 1.3. Moreover, within 3 steps the system applying the proposed embedding scheme is able to recover any single fault. Compared to other embedding schemes that result in either large expansion or great recovery cost, the proposed embedding scheme results in much better performance.
Recommended Citation
Liu, Junlin and McMillin, Bruce M., "A Divide and Conquer Ring Embedding Scheme on Hypercubes with Efficient Recovery Ability" (1992). Computer Science Technical Reports. 132.
https://scholarsmine.mst.edu/comsci_techreports/132
Department(s)
Computer Science
Keywords and Phrases
Embedding, Fault Tolerance, Reconfiguration, Ring, Hypercube.
Report Number
CSc-92-03
Document Type
Technical Report
Document Version
Final Version
File Type
text
Language(s)
English
Rights
© 1992 University of Missouri - Rolla, All rights reserved
Publication Date
10 January, 1992
Comments
The first Author is a Graduate Student,
This work was supported in part by the National Science Foundation under Grant Numbers MIP-8909749 and CDA-8820714, and in part by the AMOCO Faculty Development Program.