The research is concerned with the discovery and development of adaptive routing protocols for massively parallel architectures using Hypercube Interconnection Networks (HINs). This class includes the well known binary n-cube, k-ary n- cube, and multidimensional arrays. A taxonomy of routing protocols is developed and used to focus attention on distinct classes. Two new concepts will be developed and explored in this study. First, the properties of conservatism and optimism of these protocols will be rigorously characterized. The effect of these properties on message latency, network bandwidth, and network topology will be studied. Second, the class of multi-phase protocols will be introduced and developed. These are protocols whose behavior is a function of the distance of a message from the destination. The proposed router architectures will be modeled and evaluated via simulation. Particular attention will be focused on the evaluation of performance in the presence of implementation constraints such as wiring complexity, pin count, and link layer protocols.
