Adaptive packet routing in a hypercube

Abstract
All commercial hypercubes use fixed-path routing for packet switching. However, it has long been known that adaptive routing reduces packet delay by sending packets via less congested areas. Moreover, the hypercube topology contains many alternative, equal-length paths, suggesting the desirability of adaptive routing. Noting the importance of a communication system and the efficiency of adaptive routing, we investigate the effect of packet routing on communication latency and message throughput in a hypercube. As a feasibility study of adaptive routing, we selected four representative adaptive routing methods for testing on the Intel IPSC: NRCC routing, shortest queue, delta, and hybrid weighted routing. In NRCC routing, a single node, the network routing control center (NRCC), collects network status information and distributes routing tables to all other nodes. In contrast, shortest queue routing is fully distributed; each node selects the link with the shortest queue of outgoing messages that is the part of a shortest path to the destination node. Delta and hybrid weighted routing are hybrid schemes, combining centralized NRCC routing and distributed shortest queue routing. Extensive simulation studies and implementation confirm the superiority of adaptive routing to the fixed-path routing in commercial hypercubes. This result holds for a variety of traffic models, including high temporal locality and traffic surges.