Physical Sciences and Mathematics Commons^™

Fault-Tolerant Circuit-Switching Networks, Nicholas Pippenger, Geng Lin

All HMC Faculty Publications and Research

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)² ) and depth Θ( log n ).