The Complexity Theory of Switching Networks.
Abstract
The author considers switching networks of the type used for line switching in communication networks or for reconfiguration of modular computer systems, and examines the complexity (number of switch contacts) of such networks and the complexity (number of arithmetic operations) of algorithms for controlling them. Three network applications are studied: partial concentration, connection, and distribution, and for each application, three modes of operation: rearrangeably nonblocking, incrementally nonblocking, and incrementally epsilon-blocking. For all three problems it is shown that rearrangeably nonblocking networks can be built with a number of contacts that has the same order of growth as the information-theoretic lower bound. For incrementally nonblocking networks it is shown that although connection networks can be built with this order of growth, partial concentration networks cannot, and for distribution networks the question remains open. (Modified author abstract)
Document Details
- Document Type
- Technical Report
- Publication Date
- Dec 19, 1973
- Accession Number
- AD0772937
Entities
People
- Nicholas Pippenger
Organizations
- Massachusetts Institute of Technology