Cited By
View all- Lee HSong B(1997)Performance Analysis of STC104 Interconnection NetworksProceedings of the High-Performance Computing on the Information Superhighway, HPC-Asia '9710.5555/523549.822918Online publication date: 28-Apr-1997
A Synthesis Approach to Design Optimally Fault Tolerant Network Architecture
Abstract
A synthesis approach to the design of a class of regular networks which provide optimal fault tolerance and are of small diameter is presented. The approach makes it possible to design a regular network in the form of a directed graph when the number of nodes n and the number of connections per node d are given, for any n and d. The designed graph will have node connectivity d and a diameter proportional to (og/sub d/ n).
References
[1]
{1} J. R. Armstrong and F. G. Gray, "Fault diagnosis in Boolean n-cube array of microprocessors," IEEE Trans. Comput., vol. C-30, pp. 590-596, Aug. 1981.
[2]
{2} J. Kuhl and S. M. Reddy, "Distributed fault tolerance for large multiprocessor systems," in Proc. 7th Annu. Symp. Comput. Architecture, May 1980, pp. 23-30.
[3]
{3} L. Bhuyan and D. P. Agrawal, "Generalized hypercube and hyperbus structure for a computer network," IEEE Trans Comput., vol. C-33, Apr. 1984.
[4]
{4} F. P. Preparata and J. Vuillemin, "The cube connected cycles: A versatile network for parallel computation," in Proc. 20th Annu. IEEE Symp. Foundations Comput. Sci., 1979.
[5]
{5} E. Horowitz and A. Zorat, "The binary tree as an interconnection network: Applications to multiprocessor systems and VLSI," IEEE Trans. Comput., vol. C-30, pp. 247-253, Apr. 1981.
[6]
{6} M. L. Schlumberger, "DeBruijn communication networks," Ph.D. dissertation, Stanford Univ., Stanford, 1974.
[7]
{7} D. K. Pradhan, "Fault tolerant multiprocessor link and bus network architecture," IEEE Trans. Comput., vol. C-34, pp. 33-45, Jan. 1985.
[8]
{8} D. K. Pradhan and S. M. Reddy, "A fault tolerant communication architecture for distributed systems," IEEE Trans. Comput., vol. C-31, Sept. 1982.
[9]
{9} D. K. Pradhan, Z. Hanquan, and M. L. Schlumberger, "Fault tolerant multibus architecture for multiprocessors," in Proc. 14th Int. Conf. Fault-Tolerant Comput., 1984, pp. 400-408.
[10]
{10} M. Imase, T. Soneoka, and K. Okada, " Connectivity of regular directed graphs with small diameters," IEEE Trans. Comput., vol. C-34, pp. 267-273, Mar. 1985.
[11]
{11} S. B. Akers, "On the construction of (d, k) graphs," IEEE Trans. Electron. Comput., vol. EC-15, pp. 253-254, Apr. 1966.
[12]
{12} J. P. Hayes, "A graph model for fault-tolerant computing systems," IEEE Trans. Comput., vol. C-25, pp. 876-884, Sept. 1976.
[13]
{13} D. K. Pradhan, "Interconnection topologies for fault-tolerant parallel and distributed architecture," in Proc. 1981 Int. Conf. Parallel Processing, Aug. 1981.
[14]
{14} S. M. Reddy, J. G. Kuhl, and S. H. Hosseini, "On digraphs with minimum diameter and maximum connectivity," in Proc. 20th Annu. Allerton Conf., Oct. 1982.
[15]
{15} H. Lee, "On design of least vulnerable networks of minimum delay," Tech. Rep., Comput. Sci. Dept., Northwestern Univ., Evanston, IL.
[16]
{16} L. W. Hawkes, "A regular fault-tolerant architecture for interconnection networks," IEEE Trans. Comput., vol. C-34, pp. 677-680, July 1985.
[17]
{17} A. Sengupta, A. Sen, and S. Bandyopadhyay, "On an optimally fault tolerant multiprocessor network architecture," IEEE Trans. Comput., vol. C-36, pp. 619-623, May 1987.
[18]
{18} U. Schumacher, "An algorithm for k-connected graph with minimum number of edges and quasiminimal diameter," Networks, vol. 14, pp. 63-74, 1984.
[19]
{19} T. Y. Chung, S. Rai, and D. P. Agrawal, "Doubly connected multidimensional regular topologies for MANs and LANs," in Proc. INFOCOM '88, New Orleans, LA, 1988, pp. 551-557.
[20]
{20} M. G. Hluchyj and M. J. Karol, "ShuffleNet: An application of generalized perfect shuffles to multihop lightwave networks," in Proc. INFOCOM '88, New Orleans, LA, 1988, pp. 379-390.
[21]
{21} N. F. Maxemchuk, "Regular mesh topologies in local and metropolitan area networks," AT&T Tech. J., vol. 64, pp. 1659-1685, Sept. 1985.
[22]
{22} P. W. Dowd and K. Jabbour, "A unified approach to local area network interconnection," IEEE J. Select. Areas Commun., vol. SAC-5, pp. 1418-1425, Dec. 1987.
[23]
{23} C. Berge, Graphs and Hypergraphs. Amsterdam, The Netherlands: North-Holland, 1973.
Index Terms
- A Synthesis Approach to Design Optimally Fault Tolerant Network Architecture
Recommendations
Fault-Tolerant Networks Based on the de Bruijn Graph
The authors introduce a novel class of networks based on the de Bruijn graph. These directed graphs are regular of degree, have N=k/sup n/ vertices for some n, and can tolerate up to k-2 node faults. Their fault-free diameter is n=log/sub k/N, and this ...
Fault Injection and Dependability Evaluation of Fault-Tolerant Systems
The authors describe a dependability evaluation method based on fault injection that establishes the link between the experimental evaluation of the fault tolerance process and the fault occurrence process. The main characteristics of a fault injection ...
Fault-Tolerant Multiprocessor Link and Bus Network Architectures
This paper presents a general class of regular networks which provide optimal (near-optimal) fault tolerance.
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Copyright © Copyright © 1991 IEEE. All Rights Reserved.
Publisher
IEEE Computer Society
United States
Publication History
Published: 01 January 1991
Author Tags
Qualifiers
- Research-article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- View Citations1Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 03 Mar 2025
Other Metrics
Citations
Cited By
View all- Lee HSong B(1997)Performance Analysis of STC104 Interconnection NetworksProceedings of the High-Performance Computing on the Information Superhighway, HPC-Asia '9710.5555/523549.822918Online publication date: 28-Apr-1997