How much can hardware help routing?

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

How much can hardware help routing?

Full text

Pdf (836 KB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the twenty-fifth annual ACM symposium on Theory of computing table of contents

San Diego, California, United States

Pages: 573 - 582

Year of Publication: 1993

ISBN:0-89791-591-7

Authors

Allan Borodin
Prabhakar Raghavan
Baruch Scheiber
Eli Upfal

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 0, Downloads (12 Months): 6, Citation Count: 7

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/167088.167237 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	B. Aiello , F. T. Leighton , B. Maggs , M. Newman, Fast algorithms for bit-serial routing on a hypercube, Proceedings of the second annual ACM symposium on Parallel algorithms and architectures, p.55-64, July 02-06, 1990, Island of Crete, Greece [doi>10.1145/97444.97459]
	2	M. Ajtai , J. Komlós , E. Szemerédi, Sorting in c log n parallel steps, Combinatorica, v.3 n.1, p.1-19, Jan. 1983 [doi>10.1007/BF02579338]
	3	R. Aleliunas, Randomized parallel communication (Preliminary Version), Proceedings of the first ACM SIGACT-SIGOPS symposium on Principles of distributed computing, p.60-72, August 18-20, 1982, Ottawa, Canada [doi>10.1145/800220.806683]
	4	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]
	5	Paul E. Green, The Future of Fiber-Optic Computer Networks, Computer, v.24 n.9, p.78-87, September 1991 [doi>10.1109/2.84902]
	6	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]
	7	Tom Leighton, Tight bounds on the complexity of parallel sorting, IEEE Transactions on Computers, v.34 n.4, p.344-354, April 1985 [doi>10.1109/TC.1985.5009385]
	8	F.T. Leighton and B. Maggs. Expanders might be practical" Fast algorithms for routing around faults in multibutterflies. In Proc. of #he 30#h Annual Symposium on Foundations of Computer Science, pages 384-389, 1989.
	9	David Peleg , Eli Upfal, The token distribution problem, SIAM Journal on Computing, v.18 n.2, p.229-243, April 1989 [doi>10.1137/0218015]
	10	R. Ramaswami. Multiwavelength lightwave networks for computer communications. IEEE Communications Magazine, 31(2):78-88, February, 1993.
	11	Eli Upfal, Efficient Schemes for Parallel Communication, Journal of the ACM (JACM), v.31 n.3, p.507-517, July 1984 [doi>10.1145/828.1892]
	12	Eli Upfal, An O(log N) deterministic packet-routing scheme, Journal of the ACM (JACM), v.39 n.1, p.55-70, Jan. 1992 [doi>10.1145/147508.147517]
	13	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]
	14	A. C-C. Yao. Probabilistic computations: Towards a unified measure of complexity. In Proc. of the 17th Annual Symposium on Foundations of Computer Science, pages 222-227, 1977.

CITED BY 7

	Kazuo Iwama , Eiji Miyano, An O( N ) oblivious routing algorithm for 2-D meshes of constant queue-size, Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, p.466-475, January 17-19, 1999, Baltimore, Maryland, United States
	Alok Aggarwal , Amotz Bar-Noy , Don Coppersmith , Rajiv Ramaswami , Baruch Schieber , Madhu Sudan, Efficient routing in optical networks, Journal of the ACM (JACM), v.43 n.6, p.973-1001, Nov. 1996
	Alok Aggarwal , Amotz Bar-Noy , Don Coppersmith , Rajiv Ramaswami , Baruch Schieber , Madhu Sudan, Efficient routing and scheduling algorithms for optical networks, Proceedings of the fifth annual ACM-SIAM symposium on Discrete algorithms, p.412-423, January 23-25, 1994, Arlington, Virginia, United States
	Richard J. Cole , Bruce M. Maggs , Ramesh K. Sitaraman, On the benefit of supporting virtual channels in wormhole routers, Proceedings of the eighth annual ACM symposium on Parallel algorithms and architectures, p.131-141, June 24-26, 1996, Padua, Italy
	Donald D. Chinn , Tom Leighton , Martin Tompa, Minimal adaptive routing on the mesh with bounded queue size, Proceedings of the sixth annual ACM symposium on Parallel algorithms and architectures, p.354-363, June 27-29, 1994, Cape May, New Jersey, United States
	Allan Borodin , Prabhakar Raghavan , Baruch Schieber , Eli Upfal, How much can hardware help routing?, Journal of the ACM (JACM), v.44 n.5, p.726-741, Sept. 1997
	F. K. Hwang , Y. C. Yao , B. Dasgupta, Some permutation routing algorithms for low-dimensional hypercubes, Theoretical Computer Science, v.270 n.1-2, p.111-124, January