Browse Prior Art Database

The Kappa Network With Fault-tolerant Destination Tag Algorithm

IP.com Disclosure Number: IPCOM000128008D
Original Publication Date: 1985-Dec-31
Included in the Prior Art Database: 2005-Sep-14
Document File: 13 page(s) / 44K

Publishing Venue

Software Patent Institute

Related People

S. C. Kothari: AUTHOR [+5]

Abstract

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 processing, routing techniques.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 8% of the total text.

Page 1 of 13

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

The Kappa Network With Fault-tolerant Destination Tag Algorithm

S. C. Kothari G. M. Prabhu Robert Roberts

Technical Report # 85-20 July 1985 Department of Computer Science Iowa State University Ames, IA 50010 MIS Program Division of Management University of Oklahoma Norman. OK 73019

Abstract

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 processing, routing techniques.

1. Introduction

Multistage Interconnection Networks (MINs) have been objects of extensive study. They were introduced by Benes (2] 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 [2] 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 [3]. With the advent of VLSI and the interest in multiprocessor computer architectures, MINs have gained importance as interconnection networks in multiprocessor and distri-buted systems (7, 8, 10]. A plethora of MINs for special purpose architectures have been proposed in the last ten years [1, 5, 9, 10]; 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;

(d) low combinatorial capability : realization of a limited number of permutations of inputs to outputs;

Iowa State University Page 1 Dec 31, 1985

Page 2 of 13

The Kappa Network With Fault-tolerant Destination Tag Algorithm

(e) inability to function in the presence of a fault : this inability arises as a direct consequence of the UPP. Two of the problems of unique-path-property MI...