EPrints@IIT Delhi >
Faculty Research Publicatons  >
Electrical Engineering >

Please use this identifier to cite or link to this item: http://eprint.iitd.ac.in/handle/2074/310

Title: Adaptive routing in k-ary n-cubes using incomplete diagnostic information
Authors: Ravikumar, C P
Panda, C S
Keywords: Fault-tolerant routing
Interconnection networks
Fault Diagnosis
Massively Parallel Computers
Issue Date: 1997
Citation: Microprocessors and microsystems, 20(6), 351-360
Abstract: In this paper, we present a fault-tolerant routing algorithm for k-ary n-cube interconnection networks which have become increasingly popular for the construction of massively parallel computers. The k-ary n-cube is a generalization of 2-ary hypercube network, and can model several interesting topologies such as the 2-d torus, 3-d torus, and the binary n-cube. In our routing algorithm, we assume that each node has static knowledge of the fault status of its immediate neighbours. Using this information,the network execute a distributed diagnosis procedure whereby each node i learns the fault status of all other nodes that are reachable from i within k hops, k/> 1. We refer to k as the diagnostic radius. Our simulation results indicate that a diagnostic radius larger than l can improve the performance of the routing algorithm. Our routing algorithm is a significant improvement over a similar algorithm due to Blough and Najand in that our algorithm does not place overheads on each message. The Blough-Najand algorithm requires each message to store the entire path from the source to destination, which can be quite large for a massively parallel multiprocessor. We compare the relative merits and demerits of our algorithm with those in the literature.
URI: http://eprint.iitd.ac.in/dspace/handle/2074/310
Appears in Collections:Electrical Engineering

Files in This Item:

File Description SizeFormat
ravikumarada97.pdf385.96 kBAdobe PDFView/Open
View Statistics

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.


Valid XHTML 1.0! DSpace Software Copyright © 2002-2010  Duraspace - Feedback