| Abstract: | Many proposed packet switching systems for high-speed networks have employed the Batcher–banyan fabric due to its modular structure, self-routeing functionality, and distributed conflict-resolving mechanism. In this paper, we present a systematic fault-tolerant design for the Batcher–banyan class of switches. Our first concern is the development of an on-line error detection mechanism which is the prerequisite of any effective fault tolerant operation. Based on the technique developed by Davis, we propose a general fault-testing technique and verify it for a variety of unique-path self-routeing networks. Furthermore, we extend this method to Batcher sorting networks and construct a fault-tolerant Batcher sorter. Lastly, after contemplating the technique constraints and system performance, we deploy the above techniques into different levels of the Batcher–banyan networks and achieve a fault-tolerant version of the StarBurst switch, a member of the Batcher–banyan class of switches. |
