The Kappa Network with Faul-tolerant Destination Tag Algorithm
Original Publication Date: 1985-Jul-31
Included in the Prior Art Database: 2007-Mar-29
Software Patent Institute
Kothari, S.C.: AUTHOR [+4]
The Kappa Network with Fault-tolerant Destination Tag Algorithm S. C. Kothari ti- G. M. Prabhu
The Kappa Network with Fault-tolerant Destination Tag Algorithm
S. C. Kothari ti-
G. M. Prabhu ++
Robert Roberts *
Technical Report #85-20 July 1985
Department of Computer Science Iowa State University
Ames. 1A 50010
Division of Management University of Oklahoma Norman, OK 73019
A fault-tolerant multistage interconnection network, called the Kappa network, and a fault-tolerant control algorithm for this network are introduced. The novel feature of the network is the symmetry of duplicate links at the block level. This symmetry results in a simple control algorithm and enhanced fault-tolerance. The control algorithm is a simple modification of the destination tag algorithm, but it provides for fault-tolerance and is dynamic in nature. The Kappa network is presented as an improvement of the Gamma network, sharing its desirable combinatorial capability. The relationship between the Kappa network and other existing fault-tolerant networks is briefly discussed.
Index Terms : Block structure, block tree diagram, fault-tolerance. multistage intercon- nection network, parallel ~rocessing, routing techniques.
Multistage Interconnection Networks (MINs) have been objects of extensive study. They were introduced by Benes 121 for applications in telephone switching. A MIN with N inputs and N outputs contains several stages of switching elements (SEs) with intercon- nections between successive stages. The Benes network  is said to be rearrangeable, i.e., the network can be controlled to connect the N inputs to the N outputs in any order: this ability is often expressed by saying that the network can achieve any permutation of inputs to outputs. However, the control algorithm required to set the individual switching elements to realize a given permutation is complex .
With the advent of VLSl and the interest in multiprocessor computer architectures, MINs have gained importance as interconnection networks in multiprocessor and distri- buted systems [7, 8. 101. A plethora of MINs for special purpose architectures have been proposed in the last ten years [I. 5, 9. 101; these MINs share certain common properties :
(a) unique path property (UPP) : existence of a unique path between each input- output pair;
(b) block structure topology : separation of switches into blocks at successive stages of the network;
(c) destination tag control algorithm : a simple control algorithm that uses the i-th digit of the destination tag to set a switching element at the i-th stage of the network; (dl low combinatorial capability : realization of a limited number of permutations of inputs to outputs;