ADAPTIVE ROUTING PROTOCOLS FOR HYPERCUBE INTERCONNECTION NETWORKS

The objective of this article is to provide a basis for comparing and contrasting different approaches to creating robust routing protocols in massively parallel architectures. Communication bottlenecks form a major impediment to the development and application of massively paral lel architectures. Multipath networks using virtual channels and adapt ive routing protocols will be the rule rather than the exception in su ch architectures. In multipath networks, adaptive routing protocols ca n dynamically route messages around network trouble spots such as comp onent failures or communication bottlenecks. Virtual channels provide a mechanism for dealing with deadlock as well as increasing effective through-put via higher link utilization. As a result, these techniques are increasingly important in providing acceptable communication late ncy and bandwidth utilization in large networks. Hypercube interconnec tion networks (HINs) form a large class of flexible and powerful inter connection networks that have been employed or proposed for several co mmercial and research endeavors in large-scale parallel computing. The se networks include the well-known binary n-cube and k-ary n-cubes. Th is article (1) discusses adaptive routing protocols for HINs; (2) intr oduces and examines such important issues as communication mechanisms, the use of virtual channels, deadlock/livelock avoidance in HINs, and the impact of these issues on adaptive routing protocols; (3) delinea tes a taxonomy of adaptive routing protocols that serves as the basis for presentation and discussion, and describes representative protocol s from each class - emphasizing features common to protocols in that c lass; and (4) presents and discusses simulation results of the impleme ntation of representative protocols from each class as well as certain implementation considerations.