Fault recovery in a distributed processing system

• US 4,710,926 A
• Filed: 12/27/1985
• Issued: 12/01/1987
• Est. Priority Date: 12/27/1985
• Status: Expired due to Term

• Current Assignee: Bell Telephone Laboratories, Inc. (Nokia Corporation)
• Original Assignee: American Telephone & Telegraph Company (AT&T, Inc.)
• Inventors: Brown, Donald W., Leth, James W., Vandendorpe, James E.
• Primary Examiner(s): Fleming, Michael R.
• Application Number:
  US06/814,115
• Time in Patent Office: 704 Days
• Field of Search: 371/9, 371/11, 371/10, 371/14, 371/15, 371/21, 371/25, 371/8, 364/186, 364/187, 364/131, 364/132, 364/134, 364/133, 364/184, 364/185
• US Class Current: 714/4.4
• CPC Class Codes: G06F 11/006 Identification G06F11/2289 takes precedence
• CPC Class Codes: G06F 11/0757 by exceeding a time limit, i.e. time-out, e.g. watchdogs
• CPC Class Codes: G06F 11/0763 by bit configuration check, e.g. of formats or tags
• CPC Class Codes: G06F 11/2028 eliminating a faulty processor or activating a spare
• CPC Class Codes: G06F 11/2038 with a single idle spare processing component
• CPC Class Codes: G06F 11/2046 where the redundant components share persistent storage G06F11/2043 takes precedence
• CPC Class Codes: H04Q 3/5455 Multi-processor, parallelism, distributed systems
• CPC Class Codes: H04Q 3/54591 Supervision, e.g. fault localisation, traffic measurements, avoiding errors, failure recovery, monitoring, statistical analysis

Abstract

A fault recovery method for a distributed processing system where a message called a heartbeat is broadcast among the processors once during each major processing cycle. The heartbeat message indicates the physical and logical identity of the transmitting processor with respect to the system arrangement as well as the processor'"'"'s present operational state. By monitoring the heartbeats from other processors, spare processors can autonomously take over the functions of failed processors without being required to consult or obtain the approval of an executive processor. The new physical location of a replaced processor will be automatically recorded by the other processors. The method has application to duplex standby and resource pool configurations as well as sparing arrangements.

Claims

1. In an arrangement comprising a plurality of processors interconnected for message communication and each having a logical identity defining functions performed by that processor with respect to said arrangement, a fault recovery method comprising

each of said processors repeatedly broadcasting heartbeat messages to others of said processors, which heartbeat messages each define the logical identity of the processor broadcasting the heartbeat message,

at least one of said processors maintaining an associated status table defining the logical identities of others of said processors based on heartbeat messages received therefrom and

said at least one of said processors, upon failing to receive heartbeat messages defining one of said logical identities defined in said status table, initiating performance of the functions defined by said one of said logical identities.

2. A method in accordance with claim 1 wherein said at least one of said processors has an associated sparing table defining logical identities each defining functions that said at least one of said processors can perform, said method further comprising

said at least one of said processors, upon failing to receive heartbeat messages defining said one of said logical identities and prior to said initiating step, reading said sparing table, and

said at least one of said processors determining based on said read sparing table, whether said at least one of said processors can perform the functions defined by said one of said logical identities,

wherein said initiating step is performed only upon a determination that said at least one of said processors can perform the functions defined by said one of said logical identities.

3. A method in accordance with claim 2 wherein said arrangement further comprises a database processor interconnected for message communication with said plurality of processors, wherein said initiating step further comprises

said at least one of said processors transmitting a download request message to said database processor,

and wherein said method further comprises

said database processor responding to said download request message by downloading information needed by said at least one of said processors to perform the functions defined by said one of said logical identities.

4. A method in accordance with claim 3 wherein said initiating step further comprises

said at least one of said processors repeatedly broadcasting heartbeat messages to others of said processors, which heartbeat messages each define said one of said logical identities.

5. A method in accordance with claim 1 wherein said arrangement further comprises a database processor interconnected for message communication with said plurality of processors, wherein said initiating step further comprises

said at least one of said processors transmitting a download request message to said database processor,

and wherein said method further comprises

said database processor responding to said download request message by downloading information needed by said at least one of said processors to perform the functions defined by said one of said logical identities.

6. A method in accordance with claim 1 wherein said initiating step further comprises

said at least one of said processors repeatedly broadcasting heartbeat messages to others of said processors, which heartbeat messages each define said one of said logical identities.

7. A method in accordance with claim 1 wherein said at least one of said processors and one of said processors having said one of said logical identities, operate in a duplex standby mode of operation.

8. A method in accordance with claim 1 wherein each of said plurality of processors can have multiple logical identities, wherein said at least one of said processors has a given logical identity prior to said initiating step, and wherein said initiating step further comprises

said at least one of said processors repeatedly broadcasting heartbeat messages to others of said processors, which heartbeat messages each define said given logical identity, and

said at least one of said processors repeatedly broadcasting heartbeat messages to others of said processors, which heartbeat messages each define said one of said logical identities.

9. In an arrangement comprising a plurality of processors interconnected for message communication and each having a physical identity with respect to said arrangement and a logical identity defining functions performed by that processor with respect to said arrangement, a fault recovery method comprising

each of said processors repeatedly broadcasting heartbeat messages to others of said processors, which heartbeat messages each define the physical identity and the logical identity of the processor broadcasting the heartbeat message,

each of said processors maintaining an associated status table defining the physical and logical identities of others of said processors based on heartbeat messages received therefrom, and

a given one of said processors, upon failing to receive heartbeat messages defining one of the logical identities defined in the status table associated with said given processor, initiating performance of the functions defined by said one of said logical identities.

10. A method in accordance with claim 9 wherein said initiating step further comprises

said given processor repeatedly broadcasting heartbeat messages to others of said processors, which heartbeat messages each define the physical identity of said given processor and said one of said logical identities.

11. A method in accordance with claim 10 further comprising

ones of said processors responding to said heartbeat messages defining the physical identity of said given processor and said one of said logical identities, by updating their associated status tables to define said given processor as having said one of said logical identities.

12. In an arrangement comprising a resource pool of processors and at least one other processor interconnected for message communication, a method for use by said other processor for selecting a processor from said resource pool comprising

each of said resource pool of processors repeatedly transmitting heartbeat messages to said other processor, which heartbeat messages each define a present processor state of the processor transmitting the heartbeat message,

said other processor maintaining based on heartbeat messages received from said resource pool of processors, a status table defining a present processor state of each of said resource pool of processors and

said other processor selecting a processor from said resource pool based on the processor state defined by said status table for said selected processor.

13. A method in accordance with claim 12 wherein said selecting step comprises

said other processor selecting a processor from said resource pool that is defined as being in an active processor state by said status table.

14. A method in accordance with claim 12 further comprising the following steps prior to said selecting step:

one of said resource pool of processors terminating the transmission of heartbeat messages and

said other processor, upon failing to receive heartbeat messages from said one of said resource pool of processors, changing said status table to define the present state of said one of said resource pool of processors as being out-of-service.

15. A method in accordance with claim 14 wherein said selecting step comprises

said other processor selecting a processor from said resource pool that is defined as being in an active processor state by said status table.

16. In an arrangement comprising a plurality of processors interconnected for message communication and including N active processors and at least one spare processor, N being a positive integer greater than one, each of said plurality of processors having a logical identity defining functions performed by that processor with respect to said arrangement, a method of recovering from a failure of any one of said N active processors comprising

each of said plurality of processors repeatedly broadcasting heartbeat messages to others of said plurality of processors,

each of said plurality of processors monitoring the receipt of heartbeat messages from others of said plurality of processors,

said one processor terminating its broadcasting of heartbeat messages, and

said spare processor, upon failing to receive heartbeat messages from said one processor, initiating performance of the functions defined by the logical identity of said one processor.

17. A method in accordance with claim 16 wherein further comprising a database processor interconnected for message communication with said plurality of processors, and wherein said at least one of said processors further comprises

means for transmitting a download request message to said database processor, and

wherein said database processor comprises means responsive to said download request message for downloading information needed by said at least one of said processors to perform the functions defined by said one of said logical identities.

18. In an arrangement comprising a plurality of processors interconnected for message communication and including N active processors, at least one primary square processor, and at least one secondary spare processor, N being a positive integer greater than one, each of said plurality of processors having a logical identity defining functions performed by that processor with respect to said arrangement, a method of recovering from a failure of any one of said N active processors comprising

each of said plurality of processors repeatedly broadcasting heartbeat messages to others of said plurality of processors,

each of said plurality processors monitoring the receipt of hearbeat messages from others of said plurality of processors,

said one processor terminating its broadcasting of heartbeat messages,

said primary spare processor, upon failing to receive hearbeat messages from said one processor, initiating performance of the functions defined by the logical identity of said one processor, and

upon said primary spare processor initiating performance of the functions defined by the logical identity of said one processor, said secondary spare processor initiating performance of the functions defined by the logical identity of said primary spare processor.

19. In an arrangement comprising a plurality of processors interconnected for message communication and including at least one active processor, at least one primary spare processor, and at least one secondary spare processor, each of said plurality of processors having a logical identity defining functions performed by that processor with respect to said arrangement, a method of recovering from a failure of said one active processor comprising

each of said plurality of processors repeatedly broadcasting heartbeat messages to others of said plurality of processors, which heartbeat messages each define the logical identity of the processor broadcasting the heartbeat message,

each of said plurality of processors monitoring the receipt of heartbeat messages from others of said plurality of processors,

said one active processor terminating its broadcasting of heartbeat messages,

upon failing to receive heartbeat messages from said one active processor, said primary spare processor terminating its broadcasting of heartbeat messages defining the logical identity of said primary spare processor and initiating performance of the functions defined by the logical identity of said one active processor,

said secondary spare processor, upon failing to receive heartbeat messages defining the logical identity of said primary spare processor, initiating performance of the functions defined by the logical identity of said primary spare processor.

20. In an arrangement comprising a plurality of processors interconnected for message communication and each having a logical identity defining the functions performed by that processor with respect to said arrangement, a fault recovery method comprising

each of said processors repeatedly broadcasting heartbeat messages to others of said processors, said heartbeat messages each defining the logical identity of the processor broadcasting the heartbeat message,

any one of said processors terminating the broadcasting of its heartbeat messages and

another of said processors, upon failing to receive heartbeat messages from said any one of said processors, initiating performance of the functions defined by the logical identity of said any one of said processors.

21. A method in accordance with claim 20 wherein each of said processors has an associated sparing table defining logical identities each defining functions that said each processor can perform, said method further comprising

said another of said processors, upon failing to receive heartbeat messages from said any one of said processors and prior to said initiating step, reading the sparing table associated with said another of said processors, and

said another of said processors determining based on said read sparing table, whether said another of said processors can assume said logical identity of said any one of said processors,

wherein said initiating step is performed only upon a determination that said another of said processors can perform the functions defined by said logical identity of said any one of said processors.

22. A method in accordance with claim 20 wherein said initiating step further comprises

said another of said processors repeatedly broadcasting heartbeat messages to others of said processors, which heartbeat messages each define said logical identity of said any one of said processors.

23. A distributed processing arrangement comprising a plurality of processors interconnected for message communication and each having a logical identity defining functions performed by that processor with respect to said arrangement, wherein each of said processors comprises

means for repeatedly broadcasting heartbeat messages to others of said processors, which heartbeat messages each define the logical identity of said each processor,

and wherein at least one of said processors further comprises

means for maintaining a status table defining the logical identities of others of said processors based on heartbeat messages received therefrom, and

means responsive to a failure to receive heartbeat messages defining one of said logical identities defined in said status table, for initiating performance of the functions defined by said one of said logical identities.

24. An arrangement in accordance with claim 23 wherein said at least one of said processors further comprises

means for storing a sparing table defining logical identities each defining functions that said at least one of said processors can perform, and

means for reading said sparing table, and

means for determining based on said read sparing table, whether said at least one of said processors can perform the functions defined by said one of said logical identities, and

wherein said at least one of said processors initiates performance of the functions defined by said one of said logical identities only upon a determination by said determining means that said at least one of said processors can perform the functions defined by said one of said logical identities.

25. An arrangement in accordance with claim 24 further comprising a database processor interconnected for message communication with said plurality of processors, and wherein said at least one of said processors further comprises

means for transmitting a download request message to said database processor, and

wherein said database processor comprises means responsive to said download request message for downloading information needed by said at least one of said processors to perform the functions defined by said one of said logical identities.

26. An arrangement in accordance with claim 25 wherein the broadcasting means of said at least one of said processor initiates, upon said at least one of said processors initiating performance of the functions defined by said one of said logical identities, the repeated broadcasting of heartbeat messages to others of said processors, which heartbeat messages each define said one of said logical identities.

27. An arrangement in accordance with claim 23 further comprising a database processor interconnected for message communication with said plurality of processors, and wherein said at least one of said processors further comprises

means for transmitting a download request message to said database processor, and

wherein said database processor comprises means responsive to said download request message for downloading information needed by said at least one of said processors to perform the functions defined by said one of said logical identities.

28. An arrangement in accordance with claim 23 wherein the broadcasting means of said at least one of said processors initiates, upon said at least one of said processors initiating performance of the functions defined by said one of said logical identities, the repeated broadcasting of heartbeat messages to others of said processors, which heartbeat messages each define said one of said logical identities.

29. An arrangement in accordance with claim 23 wherein each of said plurality of processors has a physical identity with respect to said arrangement, wherein each of said plurality of processors is in one of a plurality of processor states, and wherein the heartbeat messages broadcast by the broadcasting means of each of said plurality of processors, each define the logical identity, physical identity, and present processor state of the processor broadcasting the heartbeat message.

30. An arrangement in accordance with claim 23 wherein said arrangement is included in a distributed control switching system.

31. A distributed processing arrangement comprising a plurality of processors interconnected for message communication and each having a physical identity with respect to said arrangement and a logical identity defining functions performed by that processor with respect to said arrangement, wherein each of said processors comprises

means for repeatedly broadcasting heartbeat messages to others of said processors, which heartbeat messages each define the physical identity and the logical identity of the processor broadcasting the heartbeat message, and

means for maintaining an associated status table defining the physical and logical identities of others of said processors based on heartbeat messages received therefrom, and

wherein a given one of said processors further comprises means responsive to a failure to receive heartbeat messages defining one of the logical identities defined in the status table associated with said given processor, for initiating performance of the functions defined by said one of said logical identities.

32. An arrangement in accordance with claim 31 wherein the broadcasting means of said given processor initiates, upon said given processor initiating performance of the functions defined by said one of said logical identities, the repeated broadcasting of heartbeat messages to others of said processors, which heartbeat messages each define the physical identity of said given processor and said one of said logical identities.

33. An arrangement in accordance with claim 32 wherein the maintaining means of each of said processors is responsive to the receipt of said heartbeat messages defining the physical identity of said given processor and said one of said logical identities, for updating the status table associated with said each processor to define said given processor as having said one of said logical identities.

34. A distributed processing arrangement comprising a resource pool of processors and at least one other processor interconnected for message communication,

each of said resource pool of processors comprising means for repeatedly transmitting heartbeat messages to said other processor, which heartbeat messages each define a present processor state of the processor transmitting the heartbeat message, and

said other processor comprising means for maintaining based on heartbeat messages received from said resource pool of processors, a status table defining a present processor state of each of said resource pool of processors, and means for selecting a processor from said resource pool based on the processor state defined by said status table for the selected processor.

35. A distributed processing arrangement comprising a plurality of processors interconnected for message communication and each having a logical identity defining functions performed by that processor with respect to said arrangement, wherein each of said processors comprises

means for repeatedly broadcasting heartbeat messages to others of said processors, said heartbeat messages each defining the logical identity of the processor broadcasting the heartbeat message,

means responsive to a termination in receiving heartbeat messages from any one of said processors, for initiating performance of the functions defined by the logical identity of said any one of said processors.

36. An arrangement in accordance with claim 35 wherein said each processor further comprises

means for storing an associated sparing table defining logical identities each defining functions that said each processor can perform,

means responsive to said termination, for reading the sparing table associated with said each processor, and

means for determining based on said read sparing table, whether said each processor can perform the functions defined by said logical identity of said any one of said processors,

wherein said initiating means is responsive to said determining means for initiating performance of the functions defined by said logical identity of said any one of said processors only when said determining means determines that each each processor can perform the functions defined by said logical identity of said any one of said processors.

37. An arrangement in accordance with claim 35 wherein said initiating means further comprises

means for repeatedly broadcasting heartbeat messages to others of said processors, which heartbeat messages each define said logical identity of said any one of said processors.