The Complexity Theory of Switching Networks.
MASSACHUSETTS INST OF TECH CAMBRIDGE RESEARCH LAB OF ELECTRONICS
Pagination or Media Count:
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
- Computer Systems
- Non-Radio Communications