Award Date
1-1-2004
Degree Type
Thesis
Degree Name
Master of Science (MS)
Department
Computer Science
First Committee Member
Ajoy K. Datta
Second Committee Member
Sebastien Tixeuil
Number of Pages
60
Abstract
Wormhole routing is an efficient technique used to communicate message packets between processors when they are not completely connected. To the best of our knowledge, this is the first attempt at designing a self-stabilizing wormhole routing algorithm for hypercubes. Our first algorithm handles all types of faults except for node/link failures. This algorithm achieves optimality in terms of routing path length by following only the preferred dimensions. In an n-dimensional hypercube, those dimensions in which source and destination address bits differ are called preferred dimensions. Our second algorithm handles topological changes. We propose an efficient scheme of rerouting flits in case of node/link failures. Similar to the first algorithm, this algorithm also tries to follow preferred dimensions if they are nonfaulty at the time of transmitting the flits. However, due to topological faults it is necessary to take non-preferred dimensions resulting in suboptimality of path selection. Formal proof of correctness for both solutions is given. (Abstract shortened by UMI.).
Keywords
Hypercubes; Routing; Self; Stabilizing; Wormhole
Controlled Subject
Computer science
File Format
File Size
1730.56 KB
Degree Grantor
University of Nevada, Las Vegas
Language
English
Permissions
If you are the rightful copyright holder of this dissertation or thesis and wish to have the full text removed from Digital Scholarship@UNLV, please submit a request to digitalscholarship@unlv.edu and include clear identification of the work, preferably with URL.
Repository Citation
Marichamy, Isai Arasu, "Self-stabilizing wormhole routing in hypercubes" (2004). UNLV Retrospective Theses & Dissertations. 1670.
http://dx.doi.org/10.25669/20gg-3ly2
Rights
IN COPYRIGHT. For more information about this rights statement, please visit http://rightsstatements.org/vocab/InC/1.0/
