Fault-Tolerant Circuit-Switching Networks

Authors

Nicholas Pippenger, Harvey Mudd CollegeFollow
Geng Lin, Bell-Northern Research

Document Type

Article

Department

Mathematics (HMC)

Publication Date

1994

Abstract

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 ).

Rights Information

© 1994 Society for Industrial and Applied Mathematics

DOI

10.1137/S0895480192229790

Recommended Citation

Nicholas Pippenger and Geng Lin. "Fault-Tolerant Circuit-Switching Networks", Society for Industrial and Applied Mathematics Journal of Discrete Mathematics, 7, 108 (1994).