Accession Number : AD0772937

Title :   The Complexity Theory of Switching Networks.

Descriptive Note : Technical rept.,

Corporate Author : MASSACHUSETTS INST OF TECH CAMBRIDGE RESEARCH LAB OF ELECTRONICS

Personal Author(s) : Pippenger,Nicholas

Report Date : 19 DEC 1973

Pagination or Media Count : 59

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)

Descriptors :   *Switching circuits, *Networks, *Telecommunication circuits, Logic circuits, Information theory, Graphics, Probability, Theorems, Theses

Subject Categories : Computer Systems
      Non-radio Communications

Distribution Statement : APPROVED FOR PUBLIC RELEASE