Fault-Tolerant Circuit-Switching Networks
From The Circuits and Biology Lab at UMN
Authors: Nicholas Pippenger and Geng Lin
Department of Computer Science, The University of British Columbia
Abstract: Circuit-switching networks are used to support simultaneous (data, voice and image) communications across multiprocessor parallel systems, distributed computer systems, and telecommunication systems. Circuit-switching networks accomplish simultaneous communications by means of disjoint paths of electrical links and switches. In this paper, we shall consider fault-tolerant circuit-switching networks under a random switch failure model. Three circuit-switching net works of theoretical importance, non-blocking networks, rearrange able networks and superconcent raters, are studied. We prove lower bounds for the size (the number of switches) and depth (the largest number of switches on a communication path) of such fault-tolerant networks. And we explicitly construct such networks with optimal sizes and depths.
Publication: SPAA, pp. 229–235, 1992.
