On-line algorithms for path selection in a nonblocking network

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

On-line algorithms for path selection in a nonblocking network

Full text

Pdf (1.01 MB)

Source

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

Baltimore, Maryland, United States

Pages: 149 - 158

Year of Publication: 1990

ISBN:0-89791-361-2

Authors

S. Arora	Mathematics Department and Laboratory for Computer Science, Massachusetts Institute of Technology, Cambridge, MA
T. Leighton	Mathematics Department and Laboratory for Computer Science, Massachusetts Institute of Technology, Cambridge, MA
B. Maggs	Laboratory for Computer Science, Massachusetts Institute of Technology, Cambridge, MA

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

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

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/100216.100232 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	W. Aiello, T. Leighton, B. Maggs, and M. Newman. Fast algorithms for bit-serial routing on a hypercube. Unpublished manuscript.
	2	M. Ajtai , J. Komlós , E. Szemerédi, An 0(n log n) sorting network, Proceedings of the fifteenth annual ACM symposium on Theory of computing, p.1-9, December 1983 [doi>10.1145/800061.808726]
	3	L. A. Bassalygo and M. S. Pinsker. Complexity of optimum nonblocking switching network without reconnections. Problems of Information Transmission, 9:64-66, 1974.
	4	L. A. Bassalygo and M. S. Pinsker. Asymptotically optimal networks for generalized rearrangeable switching and generalized switching without rearrangement. Problemy Peredachi Informatsii, 16:94-98, 1980.
	5	V. E. Benes. Optimal rearrangeable multistage connecting networks. Bell System Technical Journal, 43:1641-1656, July 1964.
	6	D. G. Cantor. On non-blocking switching networks. Networks, 1:367-377, 1971.
	7	Danny Dolev , Cynthia Dwork , Nicholas Pippenger , Avi Wigderson, Superconcentrators, generalizers and generalized connectors with limited depth, Proceedings of the fifteenth annual ACM symposium on Theory of computing, p.42-51, December 1983 [doi>10.1145/800061.808731]
	8	P Feldman , J Friedman , N Pippenger, Non-blocking networks, Proceedings of the eighteenth annual ACM symposium on Theory of computing, p.247-254, May 28-30, 1986, Berkeley, California, United States [doi>10.1145/12130.12155]
	9	Paul Feldman , Joel Friedman , Nicholas Pippengers, Wide-sense nonblocking networks, SIAM Journal on Discrete Mathematics, v.1 n.2, p.158-173, May 1988 [doi>10.1137/0401018]
	10	J. Friedman. A lower bound on strictly nonblocking networks. Combinatorica, 8(2):185-188, 1988.
	11	C. P. Kruskal , M. Snir, A Unified theory of interconnection network structure, Theoretical Computer Science, v.48 n.1, p.75-94, Dec., 1986
	12	F. T. Leighton. Parallel computation using meshes of trees. In 1983 Workshop on Graph-Theoretic Concepts in Computer Science, pages 200-218, Linz, 1984. Trauner Verlag.
	13	T. Leighton and B. Maggs. Expanders might be practical: fast algorithms for routing around faults in multibutterflies. In Proceedings of the 30th Annual Symposium on Foundations of Computer Science, pages 384-389. IEEE, October 1989.
	14	Charles E. Leiserson, Fat-trees: universal networks for hardware-efficient supercomputing, IEEE Transactions on Computers, v.34 n.10, p.892-901, Oct. 1985
	15	G. A. Margulis. Explicit constructions of concentrators. Problems of Information Transmission, 9:325-332, 1973.
	16	G. M. Masson and B. W. Jordan, Jr. Generalized multi-stage connection networks. Networks, 2:191- 209, 1972.
	17	David Nassimi , Sartaj Sahni, Parallel permutation and sorting algorithms and a new generalized connection network, Journal of the ACM (JACM), v.29 n.3, p.642-667, July 1982 [doi>10.1145/322326.322329]
	18	Yu. P. Ofman. A universal automaton. Transactions of the Moscow Mathematical Society, 14:186- 199, 1965.
	19	N. Pippenger. Personal communication.
	20	N. Pippenger. The complexity theory of switching networks. PhD thesis, Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology, Cambridge, MA, 1973.
	21	N. Pippenger. On rearrangeable and nonblocking switching networks. Journal of Computer and System Sciences, 17:145-162, 1978.
	22	N. Pippenger. Telephone switching networks. In Proceedings of Symposia in Applied Mathematics, volume 26, pages 101-133, 1982.
	23	Nicholas Pippenger , Leslie G. Valiant, Shifting Graphs and Their Applications, Journal of the ACM (JACM), v.23 n.3, p.423-432, July 1976 [doi>10.1145/321958.321962]
	24	N. Pippenger and A. C.-C. Yao. Rearrangeable networks with limited depth. SIAM Journal of Algebraic and Discrete Methods, 3:411-417, 1982.
	25	C. E. Shannon. Memory requirements in a telephone exchange. Bell System Technical Journal, 29:343-349, 1950.
	26	J. S. Turner. Practical wide-sense nonblocking generalized connectors. Technical Report WUCS-88- 29, Department of Computer Science, Washington University, St. Louis, MO, 1989.
	27	E. Upfal, An O(logN) deterministic packet routing scheme, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.241-249, May 14-17, 1989, Seattle, Washington, United States [doi>10.1145/73007.73030]

CITED BY 22

	P. J. Bernhard , D. J. Rosenkrantz, Using the Dual Path Property of Omega Networks to Obtain Conflict-Free Message Routing, IEEE Transactions on Parallel and Distributed Systems, v.2 n.4, p.503-507, October 1991
	Pierre Kelsen, Fast parallel matching in expander graphs, Proceedings of the fifth annual ACM symposium on Parallel algorithms and architectures, p.293-299, June 30-July 02, 1993, Velen, Germany
	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
	Nicholas Pippenger, Self-routing superconcentrators, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.355-361, May 16-18, 1993, San Diego, California, United States
	Nabil Kahale, Eigenvalues and expansion of regular graphs, Journal of the ACM (JACM), v.42 n.5, p.1091-1106, Sept. 1995
	Rajesh K. Pankaj, Wavelength requirements for multicasting in all-optical networks, IEEE/ACM Transactions on Networking (TON), v.7 n.3, p.414-424, June 1999
	Nicholas Pippenger , Geng Lin, Fault-tolerant circuit-switching networks, Proceedings of the fourth annual ACM symposium on Parallel algorithms and architectures, p.229-235, June 29-July 01, 1992, San Diego, California, United States
	Eric A. Brewer , Frederic T. Chong , Tom Leighton, Scalable expanders: exploiting hierarchical random wiring, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.144-152, May 23-25, 1994, Montreal, Quebec, Canada
	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
	Frederic T. Chong , Thomas F. Knight, Jr., Design and performance of multipath MIN architectures, Proceedings of the fourth annual ACM symposium on Parallel algorithms and architectures, p.286-295, June 29-July 01, 1992, San Diego, California, United States
	Ori Gerstel , Galen Sasaki , Shay Kutten , Rajiv Ramaswami, Worst-case analysis of dynamic wavelength allocation in optical networks, IEEE/ACM Transactions on Networking (TON), v.7 n.6, p.833-846, Dec. 1999
	Geng Lin , Nicholas Pippenger, Parallel algorithms for routing in non-blocking networks, Proceedings of the third annual ACM symposium on Parallel algorithms and architectures, p.272-277, July 21-24, 1991, Hilton Head, South Carolina, 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
	Gerald M. Masson , Yuanyuan Yang, Broadcast Ring Sandwich Networks, IEEE Transactions on Computers, v.44 n.10, p.1169-1180, October 1995
	Tim J. Harris, A survey of PRAM simulation techniques, ACM Computing Surveys (CSUR), v.26 n.2, p.187-206, June 1994
	Tom Leighton, Methods for message routing in parallel machines, Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.77-96, May 04-06, 1992, Victoria, British Columbia, Canada
	Ted H. Szymanski, Design Principles for Practical Self-Routing Nonblocking Switching Networks with O(N · log N) Bit-Complexity, IEEE Transactions on Computers, v.46 n.10, p.1057-1069, October 1997
	P. J. Bernhard , D. J. Rosenkrantz, Partitioning Message Patterns for Bundled Omega Networks, IEEE Transactions on Parallel and Distributed Systems, v.5 n.4, p.353-363, April 1994
	F. Thomson Leighton , Bruce M. Maggs, Fast Algorithms for Routing Around Faults in Multibutterflies and Randomly-Wired Splitter Networks, IEEE Transactions on Computers, v.41 n.5, p.578-587, May 1992
	Jiangtao Li , Ninghui Li, Policy-hiding access control in open environment, Proceedings of the twenty-fourth annual ACM symposium on Principles of distributed computing, July 17-20, 2005, Las Vegas, NV, USA
	Ching Yuh Jan , A. Yavuz Oruç, Fast Self-Routing Permutation Switching on an Asymptotically Minimum Cost Network, IEEE Transactions on Computers, v.42 n.12, p.1469-1479, December 1993
	Fong-Chih Shao , A. Yavuz Oruç, Efficient Nonblocking Switching Networks for Interprocessor Communications in Multiprocessor Systems, IEEE Transactions on Parallel and Distributed Systems, v.6 n.2, p.132-141, February 1995