A Caltech Library Service

A framework for adaptive routing in multicomputer networks

Ngai, John Y. and Seitz, Charles L. (1989) A framework for adaptive routing in multicomputer networks. In: SPAA '89 Proceedings of the first annual ACM symposium on Parallel algorithms and architectures. ACM , New York, NY, pp. 1-9. ISBN 0-89791-323-X.

Full text is not posted in this repository. Consult Related URLs below.

Use this Persistent URL to link to this item:


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].

Item Type:Book Section
Related URLs:
URLURL TypeDescription ItemTechnical Report
Additional Information:© 1989 ACM. The research described in this paper was sponsored in part by the Defense Advanced Research Projects Agency, DARPA Order number 6202, and monitored by the Office of Naval Research under contract number N00014-87-K-0745; and in part by grants from Intel Scientific Computers and Ametek Computer Research Division.
Funding AgencyGrant Number
Defense Advanced Research Projects Agency (DARPA)6202
Office of Naval Research (ONR)N00014-87-K-0745
Intel Scientific ComputersUNSPECIFIED
Record Number:CaltechAUTHORS:20161206-171851156
Persistent URL:
Official Citation:J. Y. Ngai and C. L. Setiz. 1989. A framework for adaptive routing in multicomputer networks. In Proceedings of the first annual ACM symposium on Parallel algorithms and architectures (SPAA '89), F. T. Leighton (Ed.). ACM, New York, NY, USA, 1-9. DOI=
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:72615
Deposited On:07 Dec 2016 17:27
Last Modified:11 Nov 2021 05:04

Repository Staff Only: item control page