The chaos router: a practical application of randomization in network routing

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

The chaos router: a practical application of randomization in network routing

Full text

Pdf (1.05 MB)

Source

ACM Symposium on Parallel Algorithms and Architectures archive
Proceedings of the second annual ACM symposium on Parallel algorithms and architectures table of contents

Island of Crete, Greece

Pages: 21 - 30

Year of Publication: 1990

ISBN:0-89791-370-1

Authors

S. Konstantinidou	Dept. of Computer Science and Engineering, University of Washington
L. Snyder	Dept. of Computer Science and Engineering, University of Washington

Sponsors

IEEE-CS : Computer Society
SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
SIGARCH: ACM Special Interest Group on Computer Architecture
CTI : Computer Technology Inst.
EATCS : European Association for Theoretical Computer Science
Computer Tech Inst. : Computer Technology Institute

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 4, Downloads (12 Months): 24, Citation Count: 16

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/97444.97452 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	A. Borodin , J. E. Hopcroft, Routing, merging, and sorting on parallel models of computation, Journal of Computer and System Sciences, v.30 n.1, p.130-145, Feb. 1985 [doi>10.1016/0022-0000(85)90008-X]
	2	J. Y. Ngai , C. L. Setiz, A framework for adaptive routing in multicomputer networks, Proceedings of the first annual ACM symposium on Parallel algorithms and architectures, p.1-9, June 18-21, 1989, Santa Fe, New Mexico, United States [doi>10.1145/72935.72936]
	3	W.J. Daily and P. Saung. Design of a Self- Timed VLSI Multicomputer Communication Controller. Proceedings, International Conference on Computer Design, 1987, pp. 230-234.
	4	C. Kaklamanis , D. Krizanc , T. Tsantilas, Tight bounds for oblivious routing in the hypercube, Proceedings of the second annual ACM symposium on Parallel algorithms and architectures, p.31-36, July 02-06, 1990, Island of Crete, Greece [doi>10.1145/97444.97453]
	5	L. G. Valiant , G. J. Brebner, Universal schemes for parallel communication, Proceedings of the thirteenth annual ACM symposium on Theory of computing, p.263-277, May 11-13, 1981, Milwaukee, Wisconsin, United States [doi>10.1145/800076.802479]
	6	Smaragda Konstantinidou, Adaptive, minimal routing in hypercubes, Proceedings of the sixth MIT conference on Advanced research in VLSI, p.139-153, March 1990, Boston, Massachusetts, United States
	7	W D Hillis, The connection machine, MIT Press, Cambridge, MA, 1985
	8	D.A. Padua, D.J. Kuck and D.H. Lawrie. High-Speed Multiprocessors and Compilation Techniques. IEEE Transactions on Computers, Vol. C-29, pp. 763-776, September 1980.
	9	D. Gelernter. A DAG-based algorithm for prevention of store-and-forward deadlock in packet networks. IEEE Transactions on Computers, vol. C-30, pp. 709-715, Oct. 1981.
	10	Dirk Claus Grunwald , D. Reed, Circuit-switched multicomputers and heuristic load placement, 1989
	11	Pen-Chung Yew, On the design of interconnection networks for parallel and multiprocessor systems, 1981
	12	Pin-Yee Chen, Multiprocessor systems: interconnection networks, memory hierarchy, modeling and simulations, 1982

CITED BY 16

	W. J. Dally , H. Aoki, Deadlock-Free Adaptive Routing in Multicomputer Networks Using Virtual Channels, IEEE Transactions on Parallel and Distributed Systems, v.4 n.4, p.466-475, April 1993
	Robert Cypher , Luis Gravano, Requirements for deadlock-free, adaptive packet routing, Proceedings of the eleventh annual ACM symposium on Principles of distributed computing, p.25-33, August 10-12, 1992, Vancouver, British Columbia, Canada
	C. Izu , A. Arruabarrena, Applying segment routing to k-ary n-cube networks, Proceedings of the 12th international conference on Supercomputing, p.409-416, July 1998, Melbourne, Australia
	Gustavo D. Pifarré , Luis Gravano , Sergio A. Felperin , Jorge L. C. Sanz, Fully-adaptive minimal deadlock-free packet routing in hypercubes, meshes, and other networks, Proceedings of the third annual ACM symposium on Parallel algorithms and architectures, p.278-290, July 21-24, 1991, Hilton Head, South Carolina, United States
	Ambrose K. Laing , Robert Cypher, Deadlock-free routing in arbitrary networks via the flattest common supersequence method, Proceedings of the tenth annual ACM symposium on Parallel algorithms and architectures, p.55-66, June 28-July 02, 1998, Puerto Vallarta, Mexico
	Dimiter Avresky , Natcho Natchev, Dynamic Reconfiguration in Computer Clusters with Irregular Topologies in the Presence of Multiple Node and Link Failures, IEEE Transactions on Computers, v.54 n.5, p.603-615, May 2005
	S. Konstantinidou , L. Snyder, Chaos router: architecture and performance, ACM SIGARCH Computer Architecture News, v.19 n.3, p.212-221, May 1991
	Pablo E. Berman , Luis Gravano , Gustavo D. Pifarré , Jorge L. C. Sanz, Adaptive deadlock- and livelock-free routing with all minimal paths in Torus networks, Proceedings of the fourth annual ACM symposium on Parallel algorithms and architectures, p.3-12, June 29-July 01, 1992, San Diego, California, United States
	G. D. Pifarré , L. Gravano , S. A. Felperin , J. L. C. Sanz, Fully Adaptive Minimal Deadlock-Free Packet Routing in Hypercubes, Meshes, and other Networks: Algorithms and Simulations, IEEE Transactions on Parallel and Distributed Systems, v.5 n.3, p.247-263, March 1994
	Luis Gravano , Gustavo D. Pifarré , Pablo E. Berman , Jorge L. C. Sanz, Adaptive Deadlock- and Livelock-Free Routing with All Minimal Paths in Torus Networks, IEEE Transactions on Parallel and Distributed Systems, v.5 n.12, p.1233-1251, December 1994
	Robert Cypher , Luis Gravano, Storage-Efficient, Deadlock-Free Packet Routing Algorithms for Torus Networks, IEEE Transactions on Computers, v.43 n.12, p.1376-1385, December 1994
	Valentín Puente , José-Ángel Gregorio , Ramón Beivide , Cruz Izu, On the Design of a High-Performance Adaptive Router for CC-NUMA Multiprocessors, IEEE Transactions on Parallel and Distributed Systems, v.14 n.5, p.487-501, May 2003
	Gustavo D. Pifarré , Luis Gravano , Gustavo Denicolay , Jorge L. C. Sanz, Adaptive Deadlock- and Livelock-Free Routing in the Hypercube Network, IEEE Transactions on Parallel and Distributed Systems, v.5 n.11, p.1121-1139, November 1994
	José Duato, A Necessary and Sufficient Condition for Deadlock-Free Routing in Cut-Through and Store-and-Forward Networks, IEEE Transactions on Parallel and Distributed Systems, v.7 n.8, p.841-854, August 1996
	Kevin Bolding , Melanie Fulgham , Lawrence Snyder, The Case for Chaotic Adaptive Routing, IEEE Transactions on Computers, v.46 n.12, p.1281-1292, December 1997
	Cruz Izu, Throughput fairness in k-ary n-cube networks, Proceedings of the 29th Australasian Computer Science Conference, p.137-145, January 16-19, 2006, Hobart, Australia