On Rearrangeable and Non-Blocking Switching Networks

Authors

Nicholas Pippenger, Harvey Mudd CollegeFollow

Document Type

Article

Department

Mathematics (HMC)

Publication Date

1978

Abstract

Switching networks of the type used in telephone exchanges are studied, with emphasis on a particular class of networks possessing great structural symmetry. This class contains rearrangeable networks carrying N calls with roughly 6N log₃ N contacts, and non-blocking networks with roughly 16N(log₅ N)2 contacts; these results are the best obtainable by the methods used. We also show, by an impractical argument, that there are non-blocking networks with roughly 90N log₃ N contacts.

Rights Information

© 1978 Elsevier Ltd.

Terms of Use & License Information

Terms of Use for work posted in Scholarship@Claremont.

DOI

10.1016/0022-0000(78)90001-6

Recommended Citation

Nicholas Pippenger, On rearrangeable and non-blocking switching networks, Journal of Computer and System Sciences, Volume 17, Issue 2, October 1978, Pages 145-162, ISSN 0022-0000, 10.1016/0022-0000(78)90001-6. (http://www.sciencedirect.com/science/article/pii/0022000078900016)