Terminal reliability assessment of gamma and extra‐stage gamma networks

Abstract

PURPOSE – Multistage Interconnection Networks (MINs) are a class of network systems designed to improve communication in large‐scale parallel processing systems. These networks facilitate the communications to perform a single overall task in a parallel processing system consisting of a large number of processors that are working together. The purpose of this paper is to discuss two types of MINs: gamma networks and extra‐stage gamma networks. It is shown that a specific modification in the structure of a standard gamma network will add multiple paths from a specific source to a specific destination. DESIGN/METHODOLOGY/APPROACH – The terminal reliability of these networks are evaluated and analyzed in terms of the number of their paths connecting a source i, i=1, 2, … , N to any terminal. Numerical examples are also given to demonstrate each network's performance. FINDINGS – In this paper, terminal reliability as a function of the reliability of a switching element of MINs is analyzed. Terminal reliability, generally used as a measure of robustness of a MIN, is the probability of existence of at least one fault free path between a designated pair of input (s) and output (t) terminals. The fault‐tolerance and terminal reliability capabilities as well as the reliability of these networks are evaluated. It is observed that the additional stage provides more redundant paths in the networks. Therefore, an additional stage leads to extra paths and improves the system's fault tolerance. It has been shown that in a Shuffle‐Exchange Network Systems, an addition of an extra stage leads to higher terminal reliability of that network. However, the additional stage does not necessarily improve the terminal reliability of the gamma network. The additional stage could add to the switch complexity and increase the probability of a path failure as well. Therefore, the extra‐stage gamma network has multiple paths in every source‐destination pair including the case when the tag value is 0, that is, when (s=t). ORIGINALITY/VALUE – Other authors have not done this kind of research analysis.