A class of communication networks which is suitable for “multiple processor systems” was studied by Pradhan and Reddy. The underlying graph (to be called Shift and Replace graph or SRG) is based on DeBruijn digraphs and is a function of two parameters r and m. Pradhan and Reddy have shown that the node-connectivity of SRG is at least r. The same authors give a routing algorithm which generally requires 2m hops if the number of node failures is ≤r − 1). In this paper we show that the node connectivity of SRG is 2r − 2. This would immediately imply that the system can tolerate up to (2r − 3) node failures. We then present routing methods for situations with a certain number of node failures. When this number is ≤r − 2) our routing algorithm requires at most m + 3 + logr m hops if 3 + logr m:9- T≤9Tm. When the number of node failures is ≤2r − 3) our routing algorithm requires at most m + 5 + logr m hops if 4 + logr m ≤9Tm. In all the other situations our routing algorithm requires no more than 2m hops. The routing algorithms are shown to be computationally efficient.
--Authors’ Abstract
This is a research paper that deals with a class of fault-tolerant interconnect- ion networks called the Shift and Replace Graph (SRG). Some general properties regarding the node-connectivity and routing algorithm of this class of network has already been reported in [1]. The present paper improves upon these theoretical results and, hence, can be considered a sequel to the previous study. The Abstract quoted above provides a nice summary of what has been done.
With these achievements, the authors have certainly made a useful contribution to the state of the art. Furthermore, they have provided some useful insight into the construction and properties of the SRG topology in Section II. However, the rest of the paper is full of symbols and not easy to read.
The paper would be more comprehensible had it been organized in such a way that the main text gives only the major results and highlights the key steps of the proofs. The detailed development should have been left to a series of appendices, so that the flow of the presentation would not be interrupted and the reader would not be buried in a myriad of technicalities.
