Real time fault tolerant transaction processing system

• US 5,084,816 A
• Filed: 12/12/1989
• Issued: 01/28/1992
• Est. Priority Date: 11/25/1987
• Status: Expired due to Term

• Current Assignee: TTI Inventions C LLC (Intellectual Ventures LLC)
• Original Assignee: Bell Communications Research, Inc. (Telefonaktiebolaget LM Ericsson)
• Inventors: Boese, John O., Donnelly, Patrick J., Gifford, Warren S., Schlanger, Gabriel G.
• Primary Examiner(s): Chan, Eddie P.
• Application Number:
  US07/453,042
• Time in Patent Office: 777 Days
• Field of Search: 364/200 MS File, 364/900 MS File
• US Class Current: 714/4.21
• CPC Class Codes: B82Y 15/00 Nanotechnology for interacting, sensing or actuating, e.g. quantum dots as markers in protein assays or molecular motors
• CPC Class Codes: G06F 11/2005 using redundant communication controllers
• CPC Class Codes: G06F 11/2007 using redundant communication media
• CPC Class Codes: G06F 11/201 between storage system components
• CPC Class Codes: G06F 11/2035 without idle spare hardware
• CPC Class Codes: G06F 11/2046 where the redundant components share persistent storage G06F11/2043 takes precedence
• CPC Class Codes: G06F 11/2089 Redundant storage control functionality
• CPC Class Codes: G06F 2201/85 Active fault masking without idle spares active fault masking without idle spare hardware where processing functionality is redundant G06F11/2035
• CPC Class Codes: H04Q 2213/13141 Hunting for free outlet, circuit or channel
• CPC Class Codes: H04Q 2213/13167 Redundant apparatus
• CPC Class Codes: H04Q 2213/13176 Common channel signaling, CCS7
• CPC Class Codes: H04Q 3/0016 Arrangements providing connection between exchanges

Abstract

A real time fault tolerant transaction processing system, particularly one suited for use in a service control point (SCP), is described. Specifically, the system utilizes a communication protocol, such as signalling system 7, that adaptively distributes message packets on an equal basis over multiple physical links that connect two points, such as an SCP and a signalling transfer point (STP), and non-fault tolerant front end and back end processors that are connected to each physical link for processing packets appearing on that link and providing corresponding responses thereto. All the front and back end processors are loosely coupled together for purposes of processor synchronization and re-assignment. Through this system, all the physical links simultaneously carry an equal number of packets which are, in turn, processed by all the processors connected thereto. In the event any physical link or either a front or back end processor connected thereto fails, then that link is declared to be out of service. Consequently, the protocol merely re-assigns all subsequently occurring packets to the other links until such time as the fault is cleared. As the result of link re-assignment, there is advantageously no need to connect a fault tolerant processor to each physical link. This, in turn, substantially and advantageously reduces the complexity and cost of the fault tolerant transaction processing system.

Claims

1. A fault tolerant transaction processing system comprising:

first and second nodes for communicating pluralities of first and second messages therebetween having pluralities of first and second application portions, each of said first and second messages respectively having either a first or second application portion, wherein said first node provides one of said first messages and in response thereto said second node provides a corresponding one of said second messages,

a link set having a plurality of individual links interconnecting said first and second nodes;

means, operative in said first node for distributing individual ones of said first messages on an approximately equal basis among available links within said link set for carriage thereover to said second node; and

a processing system contained within said second node having;

a plurality of first processors and a plurality of second processors, each of said first processors being connected to a different corresponding one of said links, wherein each one of said first processors receives over the link connected thereto ones of said first messages appearing thereon to yield received first messages, extracts ones of said first application portions from said received first messages to provide extracted first application portions and provides said extracted first application portions to a corresponding one of said second processors, wherein said one first processor receives ones of said second application portions from said one second processor and associated with said extracted first application portions, forms one of said second messages containing said ones of the second application portions and applies said ones of the second messages to the link connected thereto for carriage thereover to said first node, and wherein each one of said second processors is connected to a corresponding one of said first processors for processing ones of the extracted first application portions provided thereby to yield associated ones of said second application portions and for providing said associated ones of said second application portions to said corresponding one of said first processors; and

inter-processors coordination means, collectively situated within all the first and second processors and operative in response to an abnormal condition of any one of said links, the first processor connected thereto or the second processor associated therewith, for generating a third message and transmitting the third message over an available one of the links to said distributing means in order to declare that said any one link is unavailable;

whereby while the abnormal condition exists the distributing means applies substantially no subsequently occurring ones of the first messages to the unavailable link and distributes substantially all the subsequently occurring ones of the first messages among remaining available ones of said links for processing by the first processors connected thereto and the second processors associated therewith so as achieve fault tolerant transaction processing.

2. The processing system in claim 1 further comprising an inter-processor communication path interconnecting all of said first and second processors;

and wherein said inter-processor coordination means further comprises means, situated in each of said first and second processors and operative in conjunction with said inter-processor communication path, for controllably co-ordinating the operation of said first and second processors in a pre-defined manner and in response to the abnormal condition in order to transfer processing of said first messages and formation of said second messages between different ones of said first processors or to transfer processing of said first application portions and providing of corresponding ones of said second application portions between different ones of said second processors.

3. The system in claim 2 wherein said distributing means comprises means operative in response to a command received over a link and originating from one of said second processors for re-distributing subsequent ones of said first messages among functioning non-congested links situated within said link set in the event of a failure of or congestion in a link, failure of an associated one of said first processors connected thereto or failure of one of second processors associated therewith or failure of a processes executing within said first or second processor.

4. The system in claim 3 wherein said distributing means further comprises means for allocating individual ones of said first messages among individual available links within a link set such that all such available links within the link set carry a substantially equal number of messages.

5. The system in claim 4 wherein said allocating means comprises:

means for choosing a link set emanating from said first node based upon a value of a bit located within a pre-determined selection field located within said first message;

means for choosing a link within the link set to carry said first message based upon the value of a pre-determined number of remaining bits located within the selection field; and

means for rotating the bits comprising the selection field at least one place and storing resultant rotated bits within the selection field prior to transmitting the resulting selection field as part of said first message from said first node to another node.

6. The system in claim 2 further comprising a network having said first node and a corresponding pair of second nodes, wherein said first node is connected by a respective link set to each of said second nodes such that said first node is capable of routing individual ones of said first messages to any one of said second nodes.

7. The system in claim 6 wherein one of said pair of second nodes is a mate second node to the other one of said second nodes and wherein said inter-processor coordination means in said one second node and in said mate second mode further comprises means, operative in conjunction with first and second selected ones of said second processors in said one second node and said mate second node, respectively, and corresponding ones of the first processors associated therewith, for transferring in a controlled pre-defined manner processing of the first application portions that would otherwise occur within said one second node to the mate second node in the even of a failure occurring within said one second node.

8. The system in claim 7 wherein said transferring means operative in conjunction with said first selected one of said second processors in said one second node further comprises means for determining whether sufficient operating resources exist within said processing system therein for supporting an application process and, in response thereto, invoking said application process therein in order to process subsequent incoming ones of the first application portions, or, if insufficient resources exist within said one second node, transferring in a controlled pre-defined manner and in conjunction with said transferring means operative in conjunction with said second selected one of said second processors in said mate second node processing of said subsequent incoming ones of the first application portions to said mate second node for processing therein.

9. The system in claim 8 wherein said transferring means further comprises means for maintaining status information regarding each of said first and second processors contained within the processing system in said one second node and processes executing therein.

10. The system in claim 9 wherein said inter-processor coordination means in said one node further comprises means collectively operative in conjunction with all of said second processors in said one node for detecting a failure condition occurring within any one of said first and second processors therein or any process executing therein and means for signalling, over said inter-processor communication path, said transferring means to initiate a determination, based upon said status information, of whether sufficient operating resources exist within said processing system in said one node.

11. The system in claim 10 wherein said failure condition detecting means comprises means situated in each separate one of said second processors comprising:

means for maintaining information regarding status of said separate second processor, the associated one of said first processors connected thereto and the processes executing on both said separate second processor and the associated one of the first processors;

means responsive to said information maintaining means for logging a number of times a pre-defined fault condition occurs in said separate second processor, said associated one of the first processors or any of said processes executing therein;

means responsive to said logging means for comparing said number against a pre-determined threshold value; and

means responsive to said comparing means for instituting based upon a difference between said threshold value and said number appropriate corrective action within said separate second processor or the associated first processor to remedy the fault condition.

12. The system in claim 11 wherein said inter-processor coordination means further comprises:

means operative in conjunction with each of said first processors for maintaining information regarding status of everyone of said first processors located within said one second node and for communicating pre-defined commands over said inter-processor communication path among said first processors connected thereto and situated within said one second node; and

means operative in conjunction with said first selected one of said second processors and responsive to said transferring means for issuing appropriate ones of said commands to said maintaining and communicating means in said each first processor in said one second node through said inter-processor communication path to each remaining one of the first processors in said second node to order to either allow a particular application process to execute within said second processors in said one second node or prohibit the execution of said application process therein.

13. The system of claim 10 wherein said processing system further comprises means connected to said inter-processor communication path for obtaining status information from any of the first and second processors situated therein and for providing suitable commands thereto.

14. The system in claim 10 wherein the number of links in any one of said link sets includes at least one additional link in excess of a number minimally necessary to carry an expected number of messages between two nodes inter-connected by the one link set.

15. The system in claim 10 wherein each link contained within a link set connected to any one of said second nodes is connected within said any one second noes to a single one of said first processors located therein and said single first processor is connected to only a single one of said second processors also located therein.

16. The processing system in claim 10 further comprising means operative within each of the first processors in each of said second nodes for maintaining network status information regarding the nodes that collectively form said network and for updating said network status information in the even of an associated failure condition effecting any such node.

17. The system in claim 10 wherein said network further comprises at least one third node which generates said first application message and is connected to said first node.

18. The system in claim 17 wherein said network further comprises a pair of said first nodes and a corresponding pair of second nodes, wherein each node within said pair of said first nodes is connected by a respective link set to each of said second nodes such that said first nodes are capable of routing individual ones of said first messages through links comprising two different link sets to any one of said second nodes.

19. The system in claim 18 wherein each of said first nodes is a signal transfer point and each of said second nodes is a service control point and wherein each of said first nodes is inter-connected through a separate link set to two other ones of said first nodes.

20. The system in claim 19 wherein said network comprises a multi-level hierarchy of signal transfer points wherein each of said signal transfer points situated in one level is inter-connected by a different link set to each of two signal transfer points situated in a next successive level.

21. The system in claim 10 wherein said first application portion is a query and said second application portion is an appropriate response to a corresponding query.

22. The system in claim 10 wherein said processing system further comprises a memory device capable of being accessed by each of said second processors, wherein said memory device stores databases that provide the appropriate response for each query.

23. The system in claim 22 wherein said memory device is dual ported and wherein said processing system further comprises a coupling device that provides a path between each of said second processors and either port of said memory device.