Browse Prior Art Database

The Kappa Network with Faul-tolerant Destination Tag Algorithm

IP.com Disclosure Number: IPCOM000148439D
Original Publication Date: 1985-Jul-31
Included in the Prior Art Database: 2007-Mar-29
Document File: 28 page(s) / 1M

Publishing Venue

Software Patent Institute

Related People

Kothari, S.C.: AUTHOR [+4]

Abstract

The Kappa Network with Fault-tolerant Destination Tag Algorithm S. C. Kothari ti- G. M. Prabhu

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 8% of the total text.

Page 1 of 28

     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

MIS Program
Division of Management University of Oklahoma Norman, OK 73019

[This page contains 1 picture or other non-text object]

Page 2 of 28

[This page contains 1 picture or other non-text object]

Page 3 of 28

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

[This page contains 1 picture or other non-text object]

Page 4 of 28

1. Introduction

   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 [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 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;
(el in...