A framework for adaptive routing in multicomputer networks

Abstract

Message-passing concurrent computers, also known as multicomputers, such as the Calteeh Cosmic Cube [I] and its commercial descendents, consist of many computing nodes that interact with each other by sending and receiving messages over communication channels between the nodes [2]. The communication networks of the second-generation machines, such as the Symult Series 2010 and the Intel iPSC2, employ an oblivious wormhole routing technique [3,4] that guarantees deadlock freedom. The network performance of this highly evolved oblivious technique has reached a limit of being capable of delivering, under random traffic, a stable maximum sustained throughput of ~45 to 50% of the limit set by the network bisection bandwidth. Further improvements on these networks will require an adaptive utilization of available network bandwidth to diffuse local congestions. in an adaptive multipath routing scheme, message routes are no longer deterministic, but are continuously perturbed by local message loading. It is expected that such an adaptive control can increase the throughput capability towards the bisection bandwidth limit, while maintaining a reasonable network latency. While the potential gain in throughput is at most only a factor of 2 under random traffic, the adaptive approach offers additional advantages, such as the ability to diffuse local congestions in unbalanced traffic, and the potential to exploit inherent path redundancy in richly connected networks to perform fault-tolerant routing. The rest of this paper consists of an examination of the various feasibility issues and results concerning the adaptive approach studied by the authors. A much more detailed exposition including results on performance modeling and fault-tolerant routing, can be found in [5].