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 (127 KB)

Source

Journal of the ACM (JACM) archive
Volume 44 , Issue 5 (September 1997) table of contents

Pages: 726 - 741

Year of Publication: 1997

ISSN:0004-5411

Authors

Allan Borodin	Univ. of Toronto, Toronto, Ont., Canada
Prabhakar Raghavan	IBM Almaden Research Center, San Jose, CA
Baruch Schieber	IBM T.J. Watson Research Center
Eli Upfal	IBM Almaden Research Center San Jose, CA; and Weizmann Institute, Rehovot, Israel

Publisher

ACM New York, NY, USA

Bibliometrics

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

Additional Information:

abstract 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/265910.265922 What is a DOI?

ABSTRACT

We study the extent to which complex hardware can speed up routing. Specifically, we consider the following questions. How much does adaptive routing improve over oblivious routing? How much does randomness help? How does it help if each node can have a large number of neighbors? What benefit is available if a node can send packets to several neighbors within a single time step? Some of these features require complex networking hardware, and it is thus important to investigate whether the performance justifies the investment. By varying these hardware parameters, we obtain a hierarchy of time bounds for worst-case permutation routing.

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	AIELLO, B., LEIGHTON, F. T., MAGGS, B., AND NEWMAN, M. 1991. Fast algorithms for bit-serial routing on a hypercube. Math. Syst. Theory 29, 253-271.
	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	Allan Borodin , Prabhakar Raghavan , Baruch Scheiber , Eli Upfal, How much can hardware help routing?, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.573-582, May 16-18, 1993, San Diego, California, United States [doi>10.1145/167088.167237]
	6	Sergio Felperin , Prabhakar Raghavan , Eli Upfal, A Theory of Wormhole Routing in Parallel Computers, IEEE Transactions on Computers, v.45 n.6, p.704-713, June 1996 [doi>10.1109/12.506426]
	7	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]
	8	HOEFFDING, W. 1958. On the distribution of the number of successes in independent trials. Ann. Math. Stat. 27, 713-721.
	9	KAKLAMANIS, C., KRIZANC, D., AND TSANTILAS, f. 1991. Tight bounds for oblivious routing in the hypercube. Math. Syst. Theory 24, 223-232.
	10	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]
	11	LEIGHTON, F. T., AND MAGGS, B. 1989. Expanders might be practical: Fast algorithms for routing around faults in multibutterflies. In Proceedings of the 30th Annual Symposium on Foundations of Computer Science. IEEE, New York, pp. 384-389.
	12	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]
	13	RAMASWAMI, R. 1993. Multiwavelength lightwave networks for computer communications. IEEE Commun. Mag. 31, 2 (Feb.), 78-88.
	14	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]
	15	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]
	16	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]
	17	YAO, A. C-C. 1977. Probabilistic computations: Towards a unified measure of complexity. In Proceedings of the 17th Annual Symposium on Foundations of Computer Science. IEEE, New York, pp. 222-227.

CITED BY 2

	Chris Harrelson , Kirsten Hildrum , Satish Rao, A polynomial-time tree decomposition to minimize congestion, Proceedings of the fifteenth annual ACM symposium on Parallel algorithms and architectures, June 07-09, 2003, San Diego, California, USA
	Alessandro Mei , Romeo Rizzi, Online Permutation Routing in Partitioned Optical Passive Star Networks, IEEE Transactions on Computers, v.55 n.12, p.1557-1571, December 2006