This research aims to develop and study randomized, fault- tolerant, fast, self-routing algorithms for Clos networks. These algorithms are suitable for synchronous as well as asynchronous routing, and apply to the buffered packet- switching mode as well as to the unbuffered circuit-switching mode. The algorithms are based on the idea that setting the first column of a Clos network results in a self-routable network. The algorithm sets the first column randomly. Several new randomization approaches will be developed yielding various routing algorithms of constant time control and very small routing delay. The performance of each of the algorithms in fault-free and faulty Clos networks will be studied using both probabilistic analysis and simulation. The performance metrics, measured as a function of the switch size and the number of faulty switches, are the number of network cycles per permutation in synchronous routing, and the message delay and network throughput in asynchronous routing. Performance comparisons will be made between the algorithms to identify the best algorithm(s), and between the buffered packet-switching mode and the unbuffered circuit-switching mode to determine whether the added cost of buffers is justifiable in randomized routing. The universality, high fault tolerance, self-routedness, and the expected small routing delays of our novel randomized routing algorithms make Clos networks not only superior to other networks, but also so fast and fault tolerant that they greatly improve the speed, throughput and reliability of parallel computer systems.
