A Caltech Library Service

A framework for adaptive routing in multicomputer networks

Ngai, John Y. and Seitz, Charles L. (1991) A framework for adaptive routing in multicomputer networks. ACM SIGARCH Computer Architecture News, 19 (1). pp. 6-14. ISSN 0163-5964. doi:10.1145/121956.121957.

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 Caltech Cosmic Cube [1] 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:Article
Related URLs:
URLURL TypeDescription ItemTechnical Report
Additional Information:© 1991 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
Issue or Number:1
Record Number:CaltechAUTHORS:20161206-171156073
Persistent URL:
Official Citation:John Y. Ngai and Charles L. Seitz. 1991. A framework for adaptive routing in multicomputer networks. SIGARCH Comput. Archit. News 19, 1 (March 1991), 6-14. DOI=
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:72614
Deposited By: Kristin Buxton
Deposited On:07 Dec 2016 17:26
Last Modified:11 Nov 2021 05:04

Repository Staff Only: item control page