Fast Fault-Tolerant Parallel Communication for de Bruijn and Digit-Exchange Networks Using Information Dispersal
Resource
Networks,23,365-378.
Journal
Networks
Journal Volume
23
Journal Issue
4
Pages
365-378
Date Issued
1993-05
Date
1993-05
Author(s)
Abstract
Abstract In this paper, the space‐efficient Information Dispersal Algorithm (IDA) is applied to fault‐tolerant parallel communication in the de Bruijn and d ‐way digit‐exchange networks, which is a generalized butterfly (Omega) network. Let N = d n denote the size of the de Bruijn network. Our routing scheme runs in 2 n + 1 time using constant size buffers (if the routing information is not counted). For d = [ n In n ], it probability of successful routing is at least 1 − N −In N /2 . The scheme also tolerates O(N) random link failures with probability at least 1 − N (7−InIn n )/6 . We also propose a routing scheme for the d‐way digit‐exchange network such that similar bounds hold. Both schemes run within the said time bounds without queuing delay. © 1993 by John Wiley & Sons, Inc.
Abstract In this paper, the space‐efficient Information Dispersal Algorithm (IDA) is applied to fault‐tolerant parallel communication in the de Bruijn and d ‐way digit‐exchange networks, which is a generalized butterfly (Omega) network. Let N = d n denote the size of the de Bruijn network. Our routing scheme runs in 2 n + 1 time using constant size buffers (if the routing information is not counted). For d = [ n In n ], it probability of successful routing is at least 1 − N −In N /2 . The scheme also tolerates O(N) random link failures with probability at least 1 − N (7−InIn n )/6 . We also propose a routing scheme for the d‐way digit‐exchange network such that similar bounds hold. Both schemes run within the said time bounds without queuing delay. © 1993 by John Wiley & Sons, Inc.
Type
journal article