Method and apparatus for enhancing the fault-tolerance of a netw

Details Method and apparatus for enhancing the fault-tolerance of a netw Method and apparatus for enhancing the fault-tolerance of a netw

1994-12-21

1997-01-07

Beausoliel, Jr., Robert W.

39518319, G06F 1134

Patent

active

055926100

ABSTRACT:
A method and apparatus for enhancing the fault-tolerance of a network finds a set of computing nodes within the network which are available for use in the network upon detection of a faulty component. This set of available computing nodes is found by first determining a set of computing nodes within the network which are physically connected together. A connectivity value for each computing node within this set is then determined. A subset of this set is then generated such that each computing node in the subset is able to transfer data to and from each other computing node in the subset. This subset is then utilized as the set of available computing nodes. In one embodiment, the set of computing nodes which are physically connected together is the largest set of physically connected computing nodes in the system.

REFERENCES:
patent: 5008882 (1991-04-01), Peterson et al.
patent: 5058105 (1991-10-01), Mansour et al.
patent: 5105424 (1992-04-01), Flaig et al.
patent: 5138615 (1992-08-01), Lamport et al.
patent: 5151900 (1992-09-01), Snyder et al.
patent: 5218676 (1993-06-01), Ben-Ayed et al.
M. Sultan Alam, et al. "Routing In Modular Fault Tolerant Multiprocessor Systems", 22nd Annual Intl. Symp. on Fault-tolerant Computing, pp. 185-193, 1992.
R. V. Bopanna, et al., "New Wormhole Routing Algorithms for Multicomputers", International Parallel Processing Symposium, pp. 419-423, 1993.
S. Borkar, et al., "iWarp: An Integrated Solution To High-speed Parallel Computing", Supercomputing '88, pp. 330-339, 1988.
J. Bruck, et al., "Efficient Fault-Tolerant Mesh and Hypercube Architectures", International Symposium on Fault-tolerant Computing, pp. 162-169, 1992.
S. Chalsani, et al., "Fault-tolerant Routing in MIN-based Supercomputers", Supercomputing, pp. 244-253, 1990.
M. S. Chen, et al., "Depth-first Search Approach For Fault-tolerant Routing In Hypercube Multicomputers", IEEE Trans. on Parallel and Distributed Systems, pp. 152-159, Apr. 1990.
A. A. Chien, et al., "Planar-adaptive Routing: Low-cost Adaptive Networks For Multiprocessors", Proc 19th Annual International Symposium on Computer Architecture, pp. 268-277, 1992.
L. Ciminiera, et al., "A Connecting Network With Fault Tolerance Capabilities", IEEE Transactions on Computers, pp. 578-580, Jun. 1986.
W. Dally, et al., "Adaptive Routing using Virtual Channels", Laboratory for Computer Science Massachusetts Institute of Technology, pp. 1-24, Jul. 1990.
W. Dally, et al., "Deadlock-free Adaptive Routing In Multicomputer Networks Using Virtual Channels", IEEE Trans. on Parallel and Distributed Computing, pp. 466-475, Apr. 1993.
W. Dally, et al., "Deadlock-Free Message Routing in Multiprocessor Interconnection Networks", IEEE Transactions on Computers, pp. 547-553, May 1987.
W. Dally, "Performance Analysis of k-ary n-cube Interconnection Networks", IEEE Transactions on Computers, pp. 775-785, Jun. 1990.
W. Dally, et al., "The torus routing chip", Distributed Computing, pp. 187-196, 1986.
W. Dally, "Virtual Channel Flow Control", IEEE Trans. on Parallel and Distributed Systems, pp. 194-205, 1990.
Abdel Aziz Farrag, "Tolerating A Faulty Edge In A Multi-Dimensional Mesh", International Phoenix Conference on Computers and Communications, pp. 9-15, 1993.
S. A. Felperin, et al., "Routing Techniques For Massively Parallel Communications", proceedings of the IEEE, pp. 488-503, 1991.
Tse-yun Feng, "A Survey of Interconnection Networks", Computer, pp. 5-20, 1981.
P. T. Gaughan, et al., "Pipelined Circuit-switching: A Fault-tolerant Variant of Wormhole Routing", Proc Fourth IEEE Symposium on Parallel and Distributed Processing, pp. 148-155/92.
C. J. Glass, et al., "Fault-tolerant Wormhole Routing In Meshes", 23rd Annual International Symposium on Fault-Tolerant Computing, pp. 240-249, 1993.
C. J. Glass, et al., "The Turn Model For Adaptive Routing", Proc 19th Annual Int. Symposium on Computer Architecture, pp. 278-287, 1992.
J. Gordon, et al., "Hypercube Message Routing In The Presence of Faults", 3rd Hypercube Computers Conference, pp. 318-327, 1988.
R. E. Johnson, et al, "Interconnect Topologies with Point-to-Point Rings", Computer Science Department University of Wisconsin-Madison, pp. 1-30 and A1-A6, Dec. 1991.
J. Kim, et al., "Deadlock-free Fault-tolerant Routing In Injured Hypercubes", IEEE Trans. on Computers, pp. 1078-1088, Sep. 1993.
S., Latifi, et al, "Optimal Ring Embedding In Hypercubes With Faulty Links", 22nd Annual Intl. Symp. on Fault-tolerant Computing, pp. 178-184, 1992.
T. Lee, et al., "A Fault-tolerant Communication Scheme for Hypercube Computers", IEEE Trans. on Computers, pp. 1242-1256, Oct. 1992.
X. Lin, et al., "Deadlock-Free Multicast Wormhole Routing in Multicomputer Networks", Department of Computer Science Michigan State University, pp. 1-24, Oct. 1990.
X. Lin, et al., "Performance Evaluation of Multicast Wormhole Routing in 2D-Mesh Multicomputers", 1991 International Conference on Parallel Processing, pp. 1-435-1-442, 1991.
D. H. Linder, et al., "An Adaptive and Fault Tolerant Wormhole Routing Strategy For k-ary n-cubes", IEEE Trans on Computers, pp. 2-12, 1991.
K. Padmanabhan, et al., "A Class of Redundant Path Multistage Interconnection Networks", IEEE Trans. on Computers, pp. 1099-1108, Dec. 1983.
M. Peercy, et al., "Distributed Algorithms for Shortest-Path, Deadlock-free Routing and Broadcasting In Arbitrarily Faulty Hypercubes", 20th Ann. Intl. Symp. on Fault-tolerant computing, pp. 218-225, 1990.
C. S. Raghavendra, et al., "Free Dimensions--An Effective Approach To Achieving Fault Tolerance In Hypercubes", 22nd Annual Intl. Symp. on Fault-tolerant Computing, pp. 170-177/92.
D. A. Reed, et al., "Interconnection Networks", IEEE Computer, pp. 63-73, Jun. 1987.
A. Varma, et al., "Fault-tolerant routing in Multistate Interconnection Networks", IEEE Transactions on Computers, pp. 385-393, Mar. 1989.
C. S., Yang, et al., "A Reconfigurable Modular Fault-tolerant Binary Tree Architecture", International Phoenix Conference on Computers and Communications, pp. 37-41, 1993.
J. T. Yantchev, et al., "Adaptive, Low-latency Deadlock-free Packet Routing For Networks of Processors", IEEE proceedings, pp. 178-186, May 1989.

Affiliated with

Also associated with

Rating

Method and apparatus for enhancing the fault-tolerance of a netw does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Method and apparatus for enhancing the fault-tolerance of a netw, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for enhancing the fault-tolerance of a netw will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-1772562