On the bandwidth of a multi-stage network in the presence of faulty components

The authors analyze the performance (over time) of multistage multiprocessors in the presence of faults. A commonly used measure for the performance of an interconnection network is the bandwidth, BW (t), defined as the expected number, at time, t, of requests for the shared memory which are accepted per cycle. They present two models for calculating the bandwidth of the multistage network. These models generalize previously suggested models to allow the presence of faulty links, faulty processors, and faulty memories. The first model is computationally simple but too pessimistic, since it assumes that a memory request blocked by the network is lost. The second model assumes that when a processor´s memory request is blocked, it reissues its request in the consecutive network cycle. This model which is computationally more complex, provides an upper estimate for the network bandwidth. The second model allows the calculation of other measures for the system´s performance