Title of Invention	A REDUNDANT SYSTEM APPARATUS
Abstract	A redundant system apparatus (20) comprising: a first unit (21) and a second unit (22) each including plural state machines (SM) for performing tasks, at least some of the state machines provided at the first unit (21) simultaneously performing same tasks as at least corresponding ones of some of the state machines provided at the second unit (22); characterized by a synchronization server which receives a resynchronization request (2-1) from a resync requesting state machine of the second unit (22) and thereupon provides an out-of-synchronization indication to a corresponding state machine of the first unit (21); in response to the out-of-synchronization indication from the synchronization server (24), the corresponding state machine of the first unit (21) generates a resynchronization request (2-2); in response to the resynchronization request (2-3) from the state machine of the first unit (21), the synchronization server (24) issues a resynchronization command (2-4) to both the corresponding state machine of the first unit (21) and the resync requesting state machine of second unit (22); the resync requesting state machine of second unit (22) and the corresponding state machine of the first unit (21) simultaneously resynchronize in response to the resynchronization command (2-4).

Title of Invention

A REDUNDANT SYSTEM APPARATUS

Abstract

A redundant system apparatus (20) comprising: a first unit (21) and a second unit (22) each including plural state machines (SM) for performing tasks, at least some of the state machines provided at the first unit (21) simultaneously performing same tasks as at least corresponding ones of some of the state machines provided at the second unit (22); characterized by a synchronization server which receives a resynchronization request (2-1) from a resync requesting state machine of the second unit (22) and thereupon provides an out-of-synchronization indication to a corresponding state machine of the first unit (21); in response to the out-of-synchronization indication from the synchronization server (24), the corresponding state machine of the first unit (21) generates a resynchronization request (2-2); in response to the resynchronization request (2-3) from the state machine of the first unit (21), the synchronization server (24) issues a resynchronization command (2-4) to both the corresponding state machine of the first unit (21) and the resync requesting state machine of second unit (22); the resync requesting state machine of second unit (22) and the corresponding state machine of the first unit (21) simultaneously resynchronize in response to the resynchronization command (2-4).

Full Text	FORM 2 THE PATENTS ACT 1970 [39 OF 1970] & THE PATENTS RULES, 2003 COMPLETE SPECIFICATION [See Section 10; rule 13] "A REDUNDANT SYSTEM APPARATUS' TELEFONAKTIEBOLAGET LM ERICSSON (PUBL), a Swedish company, of S-126 25 Stockholm, Sweden, The following specification particularly describes the invention and the manner in which it is to be performed: The present invention relates to a redundant system apparatus. The present invention pertains to synchronizing of a redundant system, and particularly to synchronizing of a redundant computer system having two independent units which execute the same tasks simultaneously. 2. RELATED ART AND OTHER CONSIDERATIONS Some activities are so supremely important that it is judicious to have two units or processors for perfonning the activities, just in case one of the units malfunctions or terminates (e.g., crashes). Such is expected to be the case in future generations of mobile telecommunications systems, for example. See US Patent 5,469,503 to Butensky et al. which discloses a recovery algorithm for a redundant system in a telecommunications environment. In such mission critical situations, multiple units (e.g., computer processors or CPUs) are employed. In some instances, one or more of the units serves the role of a standby unit that is essentially idle until such time as it is necessary to replace an active unit. In other instances, multiple redundant units execute the same tasks simultaneously but independentiy. Unfortunately, in these other instances, the redundant units can, under certain circumstances, become out of phase with one another. In such circumstances it is necessary to re-coordinate or "resynchronize" the redundant units. Coordination of redundant Units has heretofore been addressed using various techniques. One known technique is to have the two redundant systems, e.g., two CPUs, using a same clock and same memory. In this technique, the two CPUs execute the same instructions out of the same memory at the same time, thereby obviating the need for software synchronization. A third unit compares the results from the two CPUs. A disadvantage of this technique is that its implementation requires specialized hardware rather than conventional components. Employment of a third unit which coordinates synchronization of two processors is taught in US Patent 5,748,873 to Ohguro et al. When a first processor needs to resynchronize with a second processor, the first processor sends a re-synchronizing indication to a match control logic, which then outputs synchronous reset indication signals so that both the first and second processors are reset in synchronism. Some redundant units (independently executing the same task) comprise state machines which are synchronized on the basis of external stimuli, such as bus events. But if one of the redundant units is reset (e.g., rebooted after a failure or the like), the reset unit somehow has to catch up with the other unit so that the tasks and any state machines of the reset unit can be synchronized. A possible solution to this synchronization problem is to ignore external stimuli and transfer all states from an active unit to the newly reset unit. Unfortunately, this solution would necessitate both units as appearing isolated, at least temporarily during the transfer of states, to external equipment communicating with the two units. If the overall system contains much state information, such resynchronization time might be unacceptably long. What is needed, therefore, and an object of the present invention, is an effective way of resynchronizing redundant units which employ external stimuli-synchronized state machines. BRIEF SUMMARY OF THE INVENTION A redundant system comprises a first unit, a second unit, and a synchronization server. The first unit and a second unit each include plural state machines for performing tasks. At least some of the state machines provided at the first unit simultaneously perform same tasks as at least corresponding ones of some of the state machines provided at the second unit. In accordance with the invention, when a state machine of a second unit determines that it needs to be resynchronized, the synchronization server receives a resynchronization request from the state machine requesting resynchronization and thereupon provides an out-of-synchronization indication to a corresponding state machine in the first unit. In response to the out-of-synchronization indication from the synchronization server, the corresponding state machine in the first unit generates a resynchronization request at an time deemed appropriate by the corresponding state machine in the first unit. In response to the resynchronization request from the corresponding state machine in the first unit, the synchronization server issues a resynchronization command to both the corresponding state machine in the first unit and the state machine requesting of the second unit which sought resynchronization. The state machines of the first and second units simultaneously resynchronize in response to the resynchronization command. At least one of the first unit and the second unit includes a restart logic that prescribes an order of restart of the plural state machines when a unit is restarted or rebooted. This provides for a gradual start up of the state machines of the redundant units. Preferably, the prescribed order is on a basis of one state machine at a time. When a state machine is restarted, it is up to the individual state machine when to synchronize in accordance with the steps summarized above. In an illustrated embodiment, the first unit and the second unit are situated in a node of a cellular telecommunications system, such as a base station (BTS) node, for example. The synchronization server can be a distinct unit, or can be included in one of the first unit and the second unit. BRIEF DESCRIPTION OF THE DRAWINGS The foregoing and other objects, features, and advantages of the invention will be apparent from the following more particular description of preferred embodiments as illustrated in the accompanying drawings in which reference characters refer to the same parts throughout the various views. The drawings are not necessarily to scale, emphasis instead being placed upon illustrating the principles of the invention. Fig. 1 is a schematic view of a redundant system according to a first embodiment of the invention. Fig. 1A is a schematic view of a redundant system according to another embodiment of the invention. Fig. IB is a schematic view of a redundant system according to another embodiment of the invention wherein restart logic is located in a synchronization server node. Fig. 1C is a schematic view of a redundant system according to another embodiment of the invention wherein restart logic is located in a node distinct from a node of the first unit, the node of the second unit, or the node of the synchronization server. Fig. 2 is a schematic view showing a message scheme for resynchronization of a state machine for the embodiment of Fig. 1. Fig. 3 is a schematic view illustrating a restart sequence according to one mode of the present invention. Fig. 3A is a schematic view illustrating a restart sequence another mode of the present invention. Fig. 4 is a schematic view showing implementation of the embodiment of Fig. 1 in a node of a cellular telecommunications system. DETAILED DESCRIPTION OF THE DRAWINGS In the following description, for purposes of explanation and not limitation, specific details are set forth such as particular architectures, interfaces, techniques, etc. in order to provide a thorough understanding of the present invention. However, it will be apparent to those skilled in the art that the present invention may be practiced in other embodiments that depart from these specific details. In other instances, detailed descriptions of well known devices, circuits, and methods are omitted so as not to obscure the description of the present invention with unnecessary detail. Fig. 1 shows a redundant system 20 according to a first embodiment of the invention. The redundant system 20 includes first and second units, illustrated as first CPU 21 and second CPU 22, as well as resynchronization server 24. Each of first CPU 21 and second CPU 22 is preferably a processing unit such as a programmed microprocessor or the like. Each of first CPU 21 and second CPU 22 includes plural software state machines. As shown in Fig. 1, first CPU 21 has state machines SM1,A, SM,1,B,... SM,,N while second CPU 22 has state machines SM2,A, SM2.a,... SM2,N. Since system 20 is a redundant system, with first CPU 21 and second CPU 22 independently but (under normal circumstances) simultaneously execute the same tasks, state machine SM,.A of first CPU 21 performs the same task of state machine SM2.A of second CPU 22; state machine SM,.B of first CPU 21 performs the same task of state machine SM2,B of second CPU 22; and so forth in accordance with an alphabetically subscripted pattern. Thus, the redundancy of system 20 has the state machines of Fig. 1 provided in pairs, a first pair SM1,A and SMl -B; a second pair SM2,A and SM2.B; and so forth continuing to a nth pair SM1-N and SMl N. Preferably one or more of the pairs of state machines shown in Fig. 1 are synchronized on the basis of external stimuli, such as bus events. Fig. 1 illustrates that a stimulus A is applied concurrently to state machine SMi. A and state machine SM2-A; a stimulus B is applied concurrently to state machine SM1.B and state machine SM2,B; and so forth. In normal operation, the state machines of each pair are maintained in synchronization by virtue of the fact that both state machines of the pair are simultaneously receiving the same stimulus. Each of first CPU 21 and second CPU 22 also include restart logic. In Fig. 1, first CPU 21 is depicted as having restart logic 301 while second CPU 22 is shown as having restart logic 302. In the particular embodiment shown in Fig. 1, resynchronization server 24 is a separate unit distinct from first CPU 21 and second CPU 22 but connected to both first CPU 21 and second CPU 22 over a bus system 34. In Fig. 1A, by contrast, resynchronization server 24' is included in second CPU 22'. Such inclusion of resynchronization server 24' with second CPU 22' is the primary difference between the embodiments of Fig. 1 and Fig. 1 A, it being understood that the analogous elements of the embodiment of Fig. 1A are shown with primed reference numerals relative to the Fig. 1 counterparts. The principles of operation of the invention, as further described herein, are understood to be equally applicable to both embodiments. Fig. 2 shows a basic message scheme facilitating resynchronization in the context of the embodiment of Fig. 1. In the scenario depicted in Fig. 2, it is assumed that state machine SM2,B is out of synchronization, as determined by state machine SM2,B or otherwise. In such case, Fig. 2 shows state machine SM2,B sending a resynchronization request 2-1 on bus system 34 to resynchronization server 24. Upon receiving the resynchronization request 2-1, resynchronization server 24 provides an out-of-synchronization indication 2-2 to the corresponding state machine in CPU 21. i.e., state machine SMl B. Then, at an appropriate time as determined by state machine SMt.B, and in response to the out-of-synchronization indication 2-2 from the resynchronization server 24, state machine SM1,B of first CPU 21 generates its own resynchronization request 2-3 which is sent to resynchronization server 24 over bus system 34. Then, having received both the resynchronization request 2-1 from both state machine SM2iB and the resynchronization request 2-3 from state machine SMI.B, resynchronization server 24 issues a resynchronization command 2-4 which is applied to both state machine SMi.B of first CPU 21 and state machine SM2,B of second CPU 22. Upon receipt of the resynchronization command 2-4, both state machine SMI.-B and state machine SM2,B are restarted. After restart of state machine SM1-B and state machine SM2.B, synchronization is accomplished by the receipt of both state machines by bus events from stimulus B. In accordance with one mode of the present invention as illustrated in Fig. 3, when either first CPU 21 or second CPU 22 must be restarted or rebooted (e.g., after a system crash), the restart logic of each CPU has a prescribed order for initializing and executing the plural state machines. An example of such prescribed order is illustrated in Fig. 3, wherein a representative one of the restart logics (restart logic 302) is shown along with prescribed time ordering of restart of the state machines for second CPU 22. In the example of Fig. 3, it is seen that restart logic 302 first starts state machine SM2.A (indicated by action 3-1) before starting state machine SM2-B, and that after starting state machine SM2.B (indicated by action 3-2) the restart and resynchronization logic 302 must receive a predefined response or acknowledgement (indicated by action 3-3) prior to starting any other state machine. Fig. 3 shows that state machine SM2,N is started by action 3-q. Thus, in the particular mode illustrated herein, it so happens that the plural state machines of a CPU are restarted on a basis of one state machine at a time. In another mode of the invention, illustrated in Fig. 3A, when either first CPU 21 or second CPU 22 must be restarted or rebooted, each state machine on the rebooting CPU determines for itself when it will synchronize. In the particular scenario illustrated in Fig. 3A, restart control logic 302 of second CPU 22 simultaneously starts each of state machines SM2>A, SM2-B, and SM2,N2 as indicated by arrows 3 A-1 through 3A-N, respectively, at time Tl. Thereafter, each state machine determines when it will begin its own resynchronization process. For example, state machine SM2,A determines that it will begin its resynchronization at time T2; state machine SM2,B determines that it will begin its resynchronization at time T3; state machine SM2.N determines that it will begin its resynchronization at time T4. The following discussion of the resynchronization process is applicable both to the modes of Fig. 3 and Fig. 3A and variations thereof. As any one of the state machines of a CPU begins it resynchronization, the restarted state machine sends the resynchronization request 2-1 of Fig. 2 to resynchronization server 24, and the activities of Fig. 2 are performed relative to the restarted state machine and its corresponding or paired state machine in the other CPU. Thus, in the situation of a CPU restart, the resynchronization procedures and activities illustrated in Fig. 2 are conducted for each state machine in the restarted CPU which requires resynchronization. Upon receipt of the out-of-synchronization indication 2-2, whether the corresponding state machine in the other CPU is in a position to resynchronize depends upon that corresponding state machine in the other CPU. In this regard, and as stated above, it was noted in Fig. 2 that the state machine of first CPU 21 generates its own resynchronization request 2-3 at a time deemed appropriate by the state machine of first CPU 21. In this regard, if the state machine of the first CPU 21 is conducting an important activity at the time it receives the out-of-synchronization indication 2-2, the state machine of first CPU 21 does not cease that important activity in deference to the out-of-synchronization indication 2-2. Rather, the state machine of first CPU 21 determines for itself when it has a satisfactory opportunity to resynchronize, e.g., when there are no critical activities currently being performed or critical external stimuli requiring attention. What is determined to be "critical" can be assessed by the state machine of first CPU 21 in accordance with predefined priorities. Thus, the state machine of first CPU 21 generates a resynchronization request only after the state machine of first CPU 21 has completed any activity of predefined priority. Fig. 4 shows an example implementation of the embodiment of Fig. 1 in a node of a cellular telecommunications system, particularly in a base station (BTS) 40. The base station (BTS) 40 comprises plural transmitter/receiver boards (Tx/Rx) 42 which communicate over air interface 44 with mobile stations, such as user equipment 46 shown in Fig. 4. Also included in base station (BTS) 40 are redundant units 40-21 and 40-22, which correspond basically to first CPU 21 and second CPU 22 of the Fig. 1 embodiment. The base station (BTS) 40 also has an extension terminal (ET) 47 and a switch 48. In the particular example base station (BTS) 40 shown in Fig. 4, the switch 48 is an ATM (Asynchronous Transfer Mode) switch which routes ATM cells between boards attached to ports of the switch core. Thus, in the example shown in Fig. 4, each of transmitter/receiver boards (Tx/Rx) 42, redundant units 40-21 and 40-22, and extension terminal (ET) 47 are situated on circuit boards connected to corresponding ports of the core of switch 48. Although Fig. 4 shows the redundant units 40-21 and 40-22 as being connected directly to switch 48, it should be understood that redundant units 40-21 and 40-22 are rather situated on boards that are connected to switch 48, and that on such boards various other devices such as switch port interface circuits may be mounted intermediate the redundant units and switch 48. The extension terminal (ET) 47 serves to connect base station (BTS) 40 over terrestrial link 49 to another node of the telecommunications system of Fig. 4, particularly to radio network controller (RNC) 50. In the illustration of Fig. 4, the resynchronization server 50-24, corresponding to resynchronization server 24 of the embodiment of Fig. 1, is situated in radio network controller (RNC) 50. The structure and operation of examples nodes such as base station (BTS) 40 and radio network controller (RNC) 50 can be understood from, for example, the following United States Patent applications, all of which are incorporated herein by reference: U.S. Patent Application SN 09/188,102 for "Asynchronous Transfer Mode System"; U.S. Patent Application SN 09/035,821 for "Telecommunications Inter-Exchange Measurement Transfer"; U.S. Patent Application SN 09/035,788 for "Telecommunications Inter-Exchange Congestion Control"; and U.S. Patent Application SN 09/071,886 for "Inter-Exchange Paging". In the particular example shown in Fig. 4, the redundant units 40-21 and 40-22 can perform various activities for base station (BTS) 40, including various control functions. One such function is performing radio link measurements, e.g., power measurements for each connection over air interface 44 and determining signal to noise ratios for the radio link with respect to each connection. Such information is important in mobile communications such as CDMA mobile communications for diversity and soft handover from one base station to another base stations. Involvement with such a measurement may, in fact, be one of the critical operations performed by one of the state machines of the redundant units which must be handled prior to sending a synchronization request 2-3. In the embodiment of Fig. 4, each of the state machines SM of the CPUs handles or is associated with a radio channel or an ATM link. Fig. IB shows another embodiment of the invention wherein restart logic 30B is located in a synchronization server 24. The synchronization server 24 can be either a distinct node as shown in Fig. 1 and Fig. 1 B, or in one of the unit nodes 21 or 22 as shown in Fig. 1A. Fig. 1C shows yet another embodiment of the invention wherein restart logic 30C is located in a node 60 which is distinct from a node of the fir„st unit 21, the node of the second unit 22, or the node of the synchronization server 24. In both the Fig. IB and Fig. 1C embodiment, the restart logic learns that a CPU needs to be rebooted, for example, and sends restart messages to each state machine. An illustration of the sending of such restart messages is provided by arrow 1C-1 in Fig. 1C. It should be understood that the restart messages can be sent in a predefined sequence in the manner of Fig. 3, or simultaneously in the manner of Fig. 3A. The synchronization of each state machine is understood with reference to Fig. 2 as discussed above. Thus, the present invention starts up the state machines of a reset unit in a gradual, predefined manner which allows each state machine to decide by itself when it should be synchronized. Moreover, the present invention provides a scheme for the state machines to employ a third party, e.g., the server 24, in the resynchronization process. Of course, the reset unit must know what state machines are to be restarted, and in what order or sequence or logic pattern. Thus, when one of the CPUs (e.g., a standby CPU) needs to be restarted, the gradual restarting of the present invention will never leave the other or active CPU appearing lost relative to the outside world. The only part of the overall system which will seem lost relative to its external environment is any state machine which is currently resynchronizing itself. But by letting each state machine decide when to perform resynchronization, the time that the state machine seems lost is negligible (since the state machine itself may know or anticipate the best time for it to resynchronize). It should be understood, that the term "unit" as employed herein is not necessarily confined to a processor which executes programmed instructions, but extends to any type of logic device or circuit which supervises plural state machines. Nor does the fact that the state machines illustrated herein are realized in software preclude the invention from applying to hardware or circuit-formed state machines which utilize the resynchronization principles of the present invention. Nor should particular significance be attached to the fact that the state machines illustrated herein are depicted as receiving only one stimulus. Such simplified illustration has been provided merely for purposes of clarity. Plural stimulus applied to state machines is certainly envisioned by the present invention. The location of resynchronization server 24 and resynchronization server 24' as described herein is not limiting in the sense that the person skilled in the art will realize the resynchronization servers can be situated and connected in other manners, e.g., that other elements can be connected between resynchronization server and one or more of the CPUs. Moreover, the illustration provided in Fig. 4 of an ATM-based base station (BTS) is but one example of how the present invention can be implemented in a node of a telecommunications system. The node for implementation need not be a base station, but can be other nodes such as the radio network controller (RNC) node, for example. Moreover, it should be understood that employment of the present invention is certainly not linked to employment of ATM or any other particular protocol. The present invention can be utilized to synchronize SSCOP links, radio links and other links in a redundant system. While the invention has been described in connection with what is presently considered to be the most practical and preferred embodiment, it is to be understood that the invention is not to be limited to the disclosed embodiment, but on the contrary, is intended to cover various modifications and equivalent arrangements included within the spirit and scope of the appended claims. WE CLAIM: 1. A redundant system apparatus (20) comprising: a first unit (21) and a second unit (22) each including plural state machines (SM) for performing tasks, at least some of the state machines provided at the first unit (21) simultaneously performing same tasks as at least corresponding ones of some of the state machines provided at the second unit (22); characterized by a synchronization server which receives a resynchronization request (2-1) from a resync requesting state machine of the second unit (22) and thereupon provides an out-of-synchronization indication to a corresponding state machine of the first unit (21); in response to the out-of-synchronization indication from the synchronization server (24), the corresponding state machine of the first unit (21) generates a resynchronization request (2-2); in response to the resynchronization request (2-3) from the state machine of the first unit (21), the synchronization server (24) issues a resynchronization command (2-4) to both the corresponding state machine of the first unit (21) and the resync requesting state machine of second unit (22); the resync requesting state machine of second unit (22) and the corresponding state machine of the first unit (21) simultaneously resynchronize in response to the resynchronization command (2-4). 2. The apparatus as claimed in claim 1,wherein the corresponding state machine of the first unit (21) generates a resynchronization request (2-1) only after the corresponding state machine of the first unit (21) has completed an activity of predefined priority. 3. The apparatus as claimed in claim 1, wherein at least one of the first unit (21) and the second unit (22) has a restart logic (30) that prescribes an order of restart of the plural state machines. 4. The apparatus as claimed in claim 3, wherein the restart logic (30) prescribes restart of the plural state machines on a basis of one state machine at a time. 5. The apparatus as claimed in claim 1, wherein at least one of the synchronization server (24) and a third unit (60) has a restart logic (30) that prescribes an order of restart of the plural state machines. 6. The apparatus as claimed in claim 5, wherein the restart logic (30) prescribes restart of the plural state machines on a basis of one state machine at a time. 7. The apparatus as claimed in claim 1, wherein restart logic (30) restarts plural state machines of a unit, and wherein upon restart each state machine of the unit decides when it will resynchronize. 8. The apparatus as claimed in claim 1, wherein the first unit (21) and the second unit (22) are situated in a node (40) of a cellular telecommunications system . 9. The apparatus as claimed in claim 1, wherein the synchronization server (24) is included in one of the first unit (21) and the second unit (22). 10. The apparatus as claimed in claim 1, wherein the synchronization server (24) is situated at a node (50) which does not include the first unit (21) or the second unit (22). 11. The apparatus as claimed in claim 1, wherein at least some of state machines at the first unit (21) and the second unit (22) are synchronized by external stimuli 12. A telecommunications system comprising: a node (40) having a redundant system (20) as claimed in claim 1 Dated this 24th day of August, 2001. (RITUSHKA NEGI) OF REMFRY & SAGAR ATTORNEY FOR THE APPLICANTS

Full Text

FORM 2
THE PATENTS ACT 1970
[39 OF 1970]
&
THE PATENTS RULES, 2003
COMPLETE SPECIFICATION
[See Section 10; rule 13]
"A REDUNDANT SYSTEM APPARATUS'
TELEFONAKTIEBOLAGET LM ERICSSON (PUBL), a Swedish company, of S-126 25 Stockholm, Sweden,
The following specification particularly describes the invention and the manner in which it is to be performed:

The present invention relates to a redundant system apparatus.
The present invention pertains to synchronizing of a redundant system, and particularly to synchronizing of a redundant computer system having two independent units which execute the same tasks simultaneously.
2. RELATED ART AND OTHER CONSIDERATIONS
Some activities are so supremely important that it is judicious to have two units or processors for perfonning the activities, just in case one of the units malfunctions or terminates (e.g., crashes). Such is expected to be the case in future generations of mobile telecommunications systems, for example. See US Patent 5,469,503 to Butensky et al. which discloses a recovery algorithm for a redundant system in a telecommunications environment.
In such mission critical situations, multiple units (e.g., computer processors or CPUs) are employed. In some instances, one or more of the units serves the role of a standby unit that is essentially idle until such time as it is necessary to replace an active unit. In other instances, multiple redundant units execute the same tasks simultaneously but independentiy. Unfortunately, in these other instances, the redundant units can, under certain circumstances, become out of phase with one another. In such circumstances it is necessary to re-coordinate or "resynchronize" the redundant units.
Coordination of redundant Units has heretofore been addressed using various techniques. One known technique is to have the two redundant systems, e.g., two CPUs, using a same clock and same memory. In this technique, the two CPUs execute

the same instructions out of the same memory at the same time, thereby obviating the need for software synchronization. A third unit compares the results from the two CPUs. A disadvantage of this technique is that its implementation requires specialized hardware rather than conventional components.
Employment of a third unit which coordinates synchronization of two processors is taught in US Patent 5,748,873 to Ohguro et al. When a first processor needs to resynchronize with a second processor, the first processor sends a re-synchronizing indication to a match control logic, which then outputs synchronous reset indication signals so that both the first and second processors are reset in synchronism.
Some redundant units (independently executing the same task) comprise state machines which are synchronized on the basis of external stimuli, such as bus events. But if one of the redundant units is reset (e.g., rebooted after a failure or the like), the reset unit somehow has to catch up with the other unit so that the tasks and any state machines of the reset unit can be synchronized. A possible solution to this synchronization problem is to ignore external stimuli and transfer all states from an active unit to the newly reset unit. Unfortunately, this solution would necessitate both units as appearing isolated, at least temporarily during the transfer of states, to external equipment communicating with the two units. If the overall system contains much state information, such resynchronization time might be unacceptably long.
What is needed, therefore, and an object of the present invention, is an effective way of resynchronizing redundant units which employ external stimuli-synchronized state machines.
BRIEF SUMMARY OF THE INVENTION
A redundant system comprises a first unit, a second unit, and a synchronization server. The first unit and a second unit each include plural state machines for performing tasks. At least some of the state machines provided at the first unit simultaneously perform same tasks as at least corresponding ones of some of the state machines provided at the second unit.

In accordance with the invention, when a state machine of a second unit determines that it needs to be resynchronized, the synchronization server receives a resynchronization request from the state machine requesting resynchronization and thereupon provides an out-of-synchronization indication to a corresponding state machine in the first unit. In response to the out-of-synchronization indication from the synchronization server, the corresponding state machine in the first unit generates a resynchronization request at an time deemed appropriate by the corresponding state machine in the first unit. In response to the resynchronization request from the corresponding state machine in the first unit, the synchronization server issues a resynchronization command to both the corresponding state machine in the first unit and the state machine requesting of the second unit which sought resynchronization. The state machines of the first and second units simultaneously resynchronize in response to the resynchronization command.
At least one of the first unit and the second unit includes a restart logic that prescribes an order of restart of the plural state machines when a unit is restarted or rebooted. This provides for a gradual start up of the state machines of the redundant units. Preferably, the prescribed order is on a basis of one state machine at a time. When a state machine is restarted, it is up to the individual state machine when to synchronize in accordance with the steps summarized above.
In an illustrated embodiment, the first unit and the second unit are situated in a node of a cellular telecommunications system, such as a base station (BTS) node, for example.
The synchronization server can be a distinct unit, or can be included in one of the first unit and the second unit.
BRIEF DESCRIPTION OF THE DRAWINGS
The foregoing and other objects, features, and advantages of the invention will be apparent from the following more particular description of preferred embodiments as illustrated in the accompanying drawings in which reference characters refer to the same parts throughout the various views. The drawings are not necessarily to scale, emphasis instead being placed upon illustrating the principles of the invention.

Fig. 1 is a schematic view of a redundant system according to a first embodiment of the invention.
Fig. 1A is a schematic view of a redundant system according to another embodiment of the invention.
Fig. IB is a schematic view of a redundant system according to another embodiment of the invention wherein restart logic is located in a synchronization server node.
Fig. 1C is a schematic view of a redundant system according to another embodiment of the invention wherein restart logic is located in a node distinct from a node of the first unit, the node of the second unit, or the node of the synchronization server.
Fig. 2 is a schematic view showing a message scheme for resynchronization of a state machine for the embodiment of Fig. 1.
Fig. 3 is a schematic view illustrating a restart sequence according to one mode of the present invention.
Fig. 3A is a schematic view illustrating a restart sequence another mode of the present invention.
Fig. 4 is a schematic view showing implementation of the embodiment of Fig. 1 in a node of a cellular telecommunications system.
DETAILED DESCRIPTION OF THE DRAWINGS
In the following description, for purposes of explanation and not limitation, specific details are set forth such as particular architectures, interfaces, techniques, etc. in order to provide a thorough understanding of the present invention. However, it will be apparent to those skilled in the art that the present invention may be practiced in other embodiments that depart from these specific details. In other instances, detailed descriptions of well known devices, circuits, and methods are omitted so as not to

obscure the description of the present invention with unnecessary detail.
Fig. 1 shows a redundant system 20 according to a first embodiment of the invention. The redundant system 20 includes first and second units, illustrated as first CPU 21 and second CPU 22, as well as resynchronization server 24. Each of first CPU 21 and second CPU 22 is preferably a processing unit such as a programmed microprocessor or the like. Each of first CPU 21 and second CPU 22 includes plural software state machines. As shown in Fig. 1, first CPU 21 has state machines SM1,A, SM,1,B,... SM,,N while second CPU 22 has state machines SM2,A, SM2.a,... SM2,N. Since system 20 is a redundant system, with first CPU 21 and second CPU 22 independently but (under normal circumstances) simultaneously execute the same tasks, state machine SM,.A of first CPU 21 performs the same task of state machine SM2.A of second CPU 22; state machine SM,.B of first CPU 21 performs the same task of state machine SM2,B of second CPU 22; and so forth in accordance with an alphabetically subscripted pattern. Thus, the redundancy of system 20 has the state machines of Fig. 1 provided in pairs, a first pair SM1,A and SMl -B; a second pair SM2,A and SM2.B; and so forth continuing to a nth pair SM1-N and SMl N.
Preferably one or more of the pairs of state machines shown in Fig. 1 are synchronized on the basis of external stimuli, such as bus events. Fig. 1 illustrates that a stimulus A is applied concurrently to state machine SMi. A and state machine SM2-A; a stimulus B is applied concurrently to state machine SM1.B and state machine SM2,B; and so forth. In normal operation, the state machines of each pair are maintained in synchronization by virtue of the fact that both state machines of the pair are simultaneously receiving the same stimulus.
Each of first CPU 21 and second CPU 22 also include restart logic. In Fig. 1, first CPU 21 is depicted as having restart logic 301 while second CPU 22 is shown as having restart logic 302.
In the particular embodiment shown in Fig. 1, resynchronization server 24 is a separate unit distinct from first CPU 21 and second CPU 22 but connected to both first CPU 21 and second CPU 22 over a bus system 34. In Fig. 1A, by contrast, resynchronization server 24' is included in second CPU 22'. Such inclusion of resynchronization server 24' with second CPU 22' is the primary difference between

the embodiments of Fig. 1 and Fig. 1 A, it being understood that the analogous elements of the embodiment of Fig. 1A are shown with primed reference numerals relative to the Fig. 1 counterparts. The principles of operation of the invention, as further described herein, are understood to be equally applicable to both embodiments.
Fig. 2 shows a basic message scheme facilitating resynchronization in the context of the embodiment of Fig. 1. In the scenario depicted in Fig. 2, it is assumed that state machine SM2,B is out of synchronization, as determined by state machine SM2,B or otherwise. In such case, Fig. 2 shows state machine SM2,B sending a resynchronization request 2-1 on bus system 34 to resynchronization server 24. Upon receiving the resynchronization request 2-1, resynchronization server 24 provides an out-of-synchronization indication 2-2 to the corresponding state machine in CPU 21. i.e., state machine SMl B. Then, at an appropriate time as determined by state machine SMt.B, and in response to the out-of-synchronization indication 2-2 from the resynchronization server 24, state machine SM1,B of first CPU 21 generates its own resynchronization request 2-3 which is sent to resynchronization server 24 over bus system 34. Then, having received both the resynchronization request 2-1 from both state machine SM2iB and the resynchronization request 2-3 from state machine SMI.B, resynchronization server 24 issues a resynchronization command 2-4 which is applied to both state machine SMi.B of first CPU 21 and state machine SM2,B of second CPU 22. Upon receipt of the resynchronization command 2-4, both state machine SMI.-B and state machine SM2,B are restarted. After restart of state machine SM1-B and state machine SM2.B, synchronization is accomplished by the receipt of both state machines by bus events from stimulus B.
In accordance with one mode of the present invention as illustrated in Fig. 3, when either first CPU 21 or second CPU 22 must be restarted or rebooted (e.g., after a system crash), the restart logic of each CPU has a prescribed order for initializing and executing the plural state machines. An example of such prescribed order is illustrated in Fig. 3, wherein a representative one of the restart logics (restart logic 302) is shown along with prescribed time ordering of restart of the state machines for second CPU 22. In the example of Fig. 3, it is seen that restart logic 302 first starts state machine SM2.A (indicated by action 3-1) before starting state machine SM2-B, and that after starting state machine SM2.B (indicated by action 3-2) the restart and resynchronization logic 302

must receive a predefined response or acknowledgement (indicated by action 3-3) prior to starting any other state machine. Fig. 3 shows that state machine SM2,N is started by action 3-q. Thus, in the particular mode illustrated herein, it so happens that the plural state machines of a CPU are restarted on a basis of one state machine at a time.
In another mode of the invention, illustrated in Fig. 3A, when either first CPU 21 or second CPU 22 must be restarted or rebooted, each state machine on the rebooting CPU determines for itself when it will synchronize. In the particular scenario illustrated in Fig. 3A, restart control logic 302 of second CPU 22 simultaneously starts each of state machines SM2>A, SM2-B, and SM2,N2 as indicated by arrows 3 A-1 through 3A-N, respectively, at time Tl. Thereafter, each state machine determines when it will begin its own resynchronization process. For example, state machine SM2,A determines that it will begin its resynchronization at time T2; state machine SM2,B determines that it will begin its resynchronization at time T3; state machine SM2.N determines that it will begin its resynchronization at time T4.
The following discussion of the resynchronization process is applicable both to the modes of Fig. 3 and Fig. 3A and variations thereof. As any one of the state machines of a CPU begins it resynchronization, the restarted state machine sends the resynchronization request 2-1 of Fig. 2 to resynchronization server 24, and the activities of Fig. 2 are performed relative to the restarted state machine and its corresponding or paired state machine in the other CPU. Thus, in the situation of a CPU restart, the resynchronization procedures and activities illustrated in Fig. 2 are conducted for each state machine in the restarted CPU which requires resynchronization.
Upon receipt of the out-of-synchronization indication 2-2, whether the corresponding state machine in the other CPU is in a position to resynchronize depends upon that corresponding state machine in the other CPU. In this regard, and as stated above, it was noted in Fig. 2 that the state machine of first CPU 21 generates its own resynchronization request 2-3 at a time deemed appropriate by the state machine of first CPU 21. In this regard, if the state machine of the first CPU 21 is conducting an important activity at the time it receives the out-of-synchronization indication 2-2, the state machine of first CPU 21 does not cease that important activity in deference to the out-of-synchronization indication 2-2. Rather, the state machine of first CPU 21

determines for itself when it has a satisfactory opportunity to resynchronize, e.g., when there are no critical activities currently being performed or critical external stimuli requiring attention. What is determined to be "critical" can be assessed by the state machine of first CPU 21 in accordance with predefined priorities. Thus, the state machine of first CPU 21 generates a resynchronization request only after the state machine of first CPU 21 has completed any activity of predefined priority.
Fig. 4 shows an example implementation of the embodiment of Fig. 1 in a node of a cellular telecommunications system, particularly in a base station (BTS) 40. The base station (BTS) 40 comprises plural transmitter/receiver boards (Tx/Rx) 42 which communicate over air interface 44 with mobile stations, such as user equipment 46 shown in Fig. 4. Also included in base station (BTS) 40 are redundant units 40-21 and 40-22, which correspond basically to first CPU 21 and second CPU 22 of the Fig. 1 embodiment. The base station (BTS) 40 also has an extension terminal (ET) 47 and a switch 48.
In the particular example base station (BTS) 40 shown in Fig. 4, the switch 48 is an ATM (Asynchronous Transfer Mode) switch which routes ATM cells between boards attached to ports of the switch core. Thus, in the example shown in Fig. 4, each of transmitter/receiver boards (Tx/Rx) 42, redundant units 40-21 and 40-22, and extension terminal (ET) 47 are situated on circuit boards connected to corresponding ports of the core of switch 48. Although Fig. 4 shows the redundant units 40-21 and 40-22 as being connected directly to switch 48, it should be understood that redundant units 40-21 and 40-22 are rather situated on boards that are connected to switch 48, and that on such boards various other devices such as switch port interface circuits may be mounted intermediate the redundant units and switch 48.
The extension terminal (ET) 47 serves to connect base station (BTS) 40 over terrestrial link 49 to another node of the telecommunications system of Fig. 4, particularly to radio network controller (RNC) 50. In the illustration of Fig. 4, the resynchronization server 50-24, corresponding to resynchronization server 24 of the embodiment of Fig. 1, is situated in radio network controller (RNC) 50.
The structure and operation of examples nodes such as base station (BTS) 40 and radio network controller (RNC) 50 can be understood from, for example, the following

United States Patent applications, all of which are incorporated herein by reference: U.S. Patent Application SN 09/188,102 for "Asynchronous Transfer Mode System"; U.S. Patent Application SN 09/035,821 for "Telecommunications Inter-Exchange Measurement Transfer"; U.S. Patent Application SN 09/035,788 for "Telecommunications Inter-Exchange Congestion Control"; and U.S. Patent Application SN 09/071,886 for "Inter-Exchange Paging".
In the particular example shown in Fig. 4, the redundant units 40-21 and 40-22 can perform various activities for base station (BTS) 40, including various control functions. One such function is performing radio link measurements, e.g., power measurements for each connection over air interface 44 and determining signal to noise ratios for the radio link with respect to each connection. Such information is important in mobile communications such as CDMA mobile communications for diversity and soft handover from one base station to another base stations. Involvement with such a measurement may, in fact, be one of the critical operations performed by one of the state machines of the redundant units which must be handled prior to sending a synchronization request 2-3. In the embodiment of Fig. 4, each of the state machines SM of the CPUs handles or is associated with a radio channel or an ATM link.
Fig. IB shows another embodiment of the invention wherein restart logic 30B is located in a synchronization server 24. The synchronization server 24 can be either a distinct node as shown in Fig. 1 and Fig. 1 B, or in one of the unit nodes 21 or 22 as shown in Fig. 1A. Fig. 1C shows yet another embodiment of the invention wherein restart logic 30C is located in a node 60 which is distinct from a node of the fir„st unit 21, the node of the second unit 22, or the node of the synchronization server 24. In both the Fig. IB and Fig. 1C embodiment, the restart logic learns that a CPU needs to be rebooted, for example, and sends restart messages to each state machine. An illustration of the sending of such restart messages is provided by arrow 1C-1 in Fig. 1C. It should be understood that the restart messages can be sent in a predefined sequence in the manner of Fig. 3, or simultaneously in the manner of Fig. 3A. The synchronization of each state machine is understood with reference to Fig. 2 as discussed above.
Thus, the present invention starts up the state machines of a reset unit in a gradual, predefined manner which allows each state machine to decide by itself when it should be synchronized. Moreover, the present invention provides a scheme for the

state machines to employ a third party, e.g., the server 24, in the resynchronization process. Of course, the reset unit must know what state machines are to be restarted, and in what order or sequence or logic pattern.
Thus, when one of the CPUs (e.g., a standby CPU) needs to be restarted, the gradual restarting of the present invention will never leave the other or active CPU appearing lost relative to the outside world. The only part of the overall system which will seem lost relative to its external environment is any state machine which is currently resynchronizing itself. But by letting each state machine decide when to perform resynchronization, the time that the state machine seems lost is negligible (since the state machine itself may know or anticipate the best time for it to resynchronize).
It should be understood, that the term "unit" as employed herein is not necessarily confined to a processor which executes programmed instructions, but extends to any type of logic device or circuit which supervises plural state machines. Nor does the fact that the state machines illustrated herein are realized in software preclude the invention from applying to hardware or circuit-formed state machines which utilize the resynchronization principles of the present invention.
Nor should particular significance be attached to the fact that the state machines illustrated herein are depicted as receiving only one stimulus. Such simplified illustration has been provided merely for purposes of clarity. Plural stimulus applied to state machines is certainly envisioned by the present invention.
The location of resynchronization server 24 and resynchronization server 24' as described herein is not limiting in the sense that the person skilled in the art will realize the resynchronization servers can be situated and connected in other manners, e.g., that other elements can be connected between resynchronization server and one or more of the CPUs.
Moreover, the illustration provided in Fig. 4 of an ATM-based base station (BTS) is but one example of how the present invention can be implemented in a node of a telecommunications system. The node for implementation need not be a base station, but can be other nodes such as the radio network controller (RNC) node, for example.

Moreover, it should be understood that employment of the present invention is certainly not linked to employment of ATM or any other particular protocol. The present invention can be utilized to synchronize SSCOP links, radio links and other links in a redundant system.
While the invention has been described in connection with what is presently considered to be the most practical and preferred embodiment, it is to be understood that the invention is not to be limited to the disclosed embodiment, but on the contrary, is intended to cover various modifications and equivalent arrangements included within the spirit and scope of the appended claims.

WE CLAIM:
1. A redundant system apparatus (20) comprising:
a first unit (21) and a second unit (22) each including plural state machines (SM) for performing tasks, at least some of the state machines provided at the first unit (21) simultaneously performing same tasks as at least corresponding ones of some of the state machines provided at the second unit (22); characterized by
a synchronization server which receives a resynchronization request (2-1) from a resync requesting state machine of the second unit (22) and thereupon provides an out-of-synchronization indication to a corresponding state machine of the first unit (21);
in response to the out-of-synchronization indication from the synchronization server (24), the corresponding state machine of the first unit (21) generates a resynchronization request (2-2); in response to the resynchronization request (2-3) from the state machine of the first unit (21), the synchronization server (24) issues a resynchronization command (2-4) to both the corresponding state machine of the first unit (21) and the resync requesting state machine of second unit (22); the resync requesting state machine of second unit (22) and the corresponding state machine of the first unit (21) simultaneously resynchronize in response to the resynchronization command (2-4).
2. The apparatus as claimed in claim 1,wherein the corresponding
state machine of the first unit (21) generates a
resynchronization request (2-1) only after the corresponding
state machine of the first unit (21) has completed an activity of
predefined priority.

3. The apparatus as claimed in claim 1, wherein at least one of the first unit (21) and the second unit (22) has a restart logic (30) that prescribes an order of restart of the plural state machines.
4. The apparatus as claimed in claim 3, wherein the restart logic (30) prescribes restart of the plural state machines on a basis of one state machine at a time.
5. The apparatus as claimed in claim 1, wherein at least one of the synchronization server (24) and a third unit (60) has a restart logic (30) that prescribes an order of restart of the plural state machines.
6. The apparatus as claimed in claim 5, wherein the restart logic (30) prescribes restart of the plural state machines on a basis of one state machine at a time.
7. The apparatus as claimed in claim 1, wherein restart logic (30) restarts plural state machines of a unit, and wherein upon restart each state machine of the unit decides when it will resynchronize.
8. The apparatus as claimed in claim 1, wherein the first unit (21) and the second unit (22) are situated in a node (40) of a cellular telecommunications system .
9. The apparatus as claimed in claim 1, wherein the synchronization server (24) is included in one of the first unit (21) and the second unit (22).
10. The apparatus as claimed in claim 1, wherein the synchronization server (24) is situated at a node (50) which does not include the first unit (21) or the second unit (22).

11. The apparatus as claimed in claim 1, wherein at least some of state machines at the first unit (21) and the second unit (22) are synchronized by external stimuli
12. A telecommunications system comprising: a node (40) having a redundant system (20) as claimed in claim 1
Dated this 24th day of August, 2001.
(RITUSHKA NEGI)
OF REMFRY & SAGAR
ATTORNEY FOR THE APPLICANTS

A REDUNDANT SYSTEM APPARATUS

Documents:

Inventors:

PCT Conventions: