System and method for fault tolerance in multi-node system

• US 6,918,063 B2
• Filed: 02/04/2002
• Issued: 07/12/2005
• Est. Priority Date: 02/04/2002
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Stockmeyer, Larry Joseph, Ho, Ching-Tien (Howard)
• Primary Examiner(s): Baderman, Scott
• Assistant Examiner(s): Damiano, Anne L.
• Application Number:
  US10/068,434
• Publication Number:
  US 20030149908A1
• Time in Patent Office: 1,254 Days
• Field of Search: 714/4, 714/43, 709/224, 709/225, 370/217
• US Class Current: 714/43
• CPC Class Codes: G06F 11/2007 using redundant communication media
• CPC Class Codes: H04L 45/00 Routing or path finding of packets in data switching networks routing or path finding in wireless networks H04W40/00
• CPC Class Codes: H04L 45/06 Deflection routing, e.g. hot-potato routing
• CPC Class Codes: H04L 45/22 Alternate routing
• CPC Class Codes: H04L 45/28 using route fault recovery

Abstract

A method and system for promoting fault tolerance in a multi-node computing system that provides deadlock-free message routing in the presence of node and/or link faults using only two rounds and, thus, requiring only two virtual channels to ensure deadlock freedom. A lamb set of nodes for use in message routing is introduced, with each node in the lamb set being used only as points along message routes, and not for sending or receiving messages.

Claims

1. A general purpose computer system having multiple nodes, comprising:

at least one processor executing method acts to promote tolerance of faults in the system, the method acts comprising;

based at least in part on the faults, determining a set of nodes; and

using nodes in the set of nodes only as points on routing paths of messages, and not using any node in the set of nodes for sending or receiving messages.

2. The system of claim 1, wherein the set is a lamb set.

3. The system of claim 2, wherein the act of determining undertaken by the processor includes:

finding small sets of partitions of candidate lamb nodes, each partition including a representative node.

4. The system of claim 3, wherein the act of finding undertaken by the processor includes:

partitioning nodes in the system into maximal intervals of sequential nodes, no node in an interval being a faulty node.

5. The system of claim 4, wherein the act of finding undertaken by the processor further includes:

returning at least some intervals as at least one set of partitions.

6. The system of claim 3, wherein the act of determining undertaken by the processor includes:

determining a reachability from at least one representative node to at least another representative node; and

using the reachability to establish a solution set, such that any node in the solution set can reach any other node in the solution set in at most k rounds.

7. The system of claim 6, wherein the act of determining a reachability undertaken by the processor includes:

computing at least one reachability matrix, using the solution set.

8. The system of claim 7, wherein the act of determining a reachability undertaken by the processor further includes:

computing at least one intersection matrix.

9. The system of claim 8, wherein the act of determining a reachability undertaken by the processor further includes:

returning at least one product of at least one reachability matrix and at least one intersection matrix.

10. The system of claim 6, wherein k equals two.

11. The system of claim 6, wherein the act of determining undertaken by the processor includes:

minimizing a solution set using at least one weighted graph G.

12. The system of claim 11, wherein the weighted graph is a weighted bipartite graph.

13. The system of claim 11, wherein the act of minimizing undertaken by the processor includes:

finding at least one vertex cover C of the graph G.

14. The system of claim 13, wherein the act of minimizing undertaken by the processor further includes:

using selected elements of the vertex cover C, establishing the lamb set.

15. The system of claim 1, wherein membership in the set of nodes depends at least partially on a number of processors in a node that are malfunctioning or not functioning.

16. A computer program device comprising:

a computer program storage device readable by a digital processing apparatus; and

a program on the program storage device and including instructions executable by the digital processing apparatus for promoting fault tolerance in a multi-node system, the program comprising;

means for designating a lamb set of nodes in the multi-node system to be used for routing messages within the system; and

means for finding small sets of partitions of prospective lamb nodes, each partition including a representative node.

17. The device of claim 16, wherein the lamb set of nodes contains nodes that are used only in messages routes.

18. The device of claim 16, wherein the means for finding includes:

means for partitioning nodes in the system into maximal intervals of sequential nodes, no node in an interval being a faulty node.

19. The device of claim 18, wherein the means for finding includes:

means for returning at least some intervals as at least one set of partitions.

20. The device of claim 16, wherein the means for designating includes:

means for determining a reachability from at least one representative node to at least another representative node; and

means for using the reachability to establish a solution set, such that any node in the solution set can reach any other node in the solution set in at most k rounds.

21. The device of claim 20, wherein the means for designating includes:

means for computing at least one reachability matrix;

means for computing at least one intersection matrix; and

means for returning at least one product of at least one reachability matrix and at least one intersection matrix.

22. The device of claim 20, wherein k equals two.

23. The device of claim 16, wherein the means for designating includes:

means for minimizing a solution set using at least one weighted graph G.

24. The device of claim 23, wherein the weighted graph is a weighted bipartite graph.

25. The device of claim 23, wherein the means for minimizing includes:

means for finding at least one vertex cover C of the graph C.

26. The device of claim 25, further comprising:

means for using selected elements of the vertex cover C to establish the lamb set.

27. The device of claim 16, wherein membership in the lamb set of nodes depends at least partially on a number of processors in a node that are malfunctioning or not functioning.

28. A method for promoting fault tolerance in a multi-node system, comprising the acts of:

for each of k rounds, finding multiple partitions of nodes, each partition having a representative node;

for each representative node, determining whether the node can reach at least one predetermined other representative node within a predetermined criteria;

minimizing the number of nodes and/or partitions using a weighted graph to establish a routing set of nodes; and

returning the routing set of nodes for use thereof in routing messages through the system in the presence of one or more node and/or link faults.

29. The method of claim 28, wherein the number of rounds is at most two.

30. The method of claim 28, wherein the number of rounds is two and only two.

31. The method of claim 28, wherein the weighted graph accounts for at least one node weight, the node weight being based at least on a number of operational processors in the node.

32. The method of claim 28, wherein the routing set of nodes is a lamb set containing nodes that are used only for routing messages.

33. The method of claim 28, further comprising finding small sets of partitions of prospective lamb nodes, each partition including a representative node.

34. The method of claim 33, comprising partitioning nodes in the system into maximal intervals of sequential nodes, no node in an interval being a faulty node.

35. The method of claim 34, comprising returning at least some intervals as at least one set of partitions.

36. The method of claim 28, wherein the act of determining whether the node can reach at least one predetermined other node comprises:

determining a reachability from as least one representative node to at least another representative node; and

using the reachability to establish the routing set, such that any node in the routing set can reach any other node in the routing set in at most k rounds.

37. The method of claim 36, wherein the act of determining whether the node can reach at least one predetermined other node comprises:

computing at least one reachability matrix;

computing at least one intersection matrix; and

returning at least one product of at least one reachability matrix and at least one intersection matrix.

38. The method of claim 28, wherein the act of minimizing includes:

finding at least one vertex cover of the weighted graph; and

using selected elements of the vertex cover to establish the routing set.

39. The method of claim 28, wherein the weighted graph is a weighted bipartite graph.