The authors consider fault-tolerant circuit-switching networks under a random switch failure model. Three circuit-switching networks of theoretical importance—nonblocking networks, rearrangeable networks, and superconcentrators—are studied. The authors 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 explicitly construct such networks with optimal size Θ( n (log n)2 ) and depth Θ( log n ).
© 1994 Society for Industrial and Applied Mathematics
Nicholas Pippenger and Geng Lin. "Fault-Tolerant Circuit-Switching Networks", Society for Industrial and Applied Mathematics Journal of Discrete Mathematics, 7, 108 (1994).