New bounds on the reliability of augmented shuffle-exchange networks

摘要

The reliability resulting from two forms of redundancy, spatial and temporal, in multistage interconnection networks is examined. The extra-stage shuffle-exchange network (SEN+) which is an example of the former is investigated here. The SEN+ is decomposed into two subnetworks connected by two extreme stages. Given k random faults in one subnetwork, our problem reduces to estimating the maximum and minimum number of switches in the other subnetwork that must be operational for full access, i.e., connection between every input (processor) and output (memory) pair. This investigation results in obtaining analytical estimates for the upper and lower bounds on its reliability which are a substantial improvement over existing ones. We next examine the effect of wrap-around connections from each output node to its corresponding input node. This may provide a path between a source-destination pair under faults by diverting a given packet through one or more intermediate destinations. The reliability offered by this scheme that provides temporal redundancy is also estimated and compared with the scheme employing hardware redundancy.