Mechanisms and algorithms for arbitrating between and synchronizing state of duplicated media processing components

• US 7,912,075 B1
• Filed: 05/26/2006
• Issued: 03/22/2011
• Est. Priority Date: 05/26/2006
• Status: Active Grant

• Current Assignee: Avaya Incorporated
• Original Assignee: Avaya Incorporated
• Inventors: Tucker, Luke A., Tamny, Michael A., Kim, Bhum C., McKinnon, Fraser A., Pillai, Dicky A., Sueper, Dave, Rodrig, Benny, Kelley-Johnson, Margaret L., Chandler, Matthew A., Kramer, Randall B., Holland, David S., Gibbons, Lee D.
• Primary Examiner(s): Yao; Kwang B
• Assistant Examiner(s): Bokhari; Syed
• Application Number:
  US11/441,595
• Time in Patent Office: 1,761 Days
• Field of Search: 714/6, 714/13, 714/4, 364/200, 370/401, 370/89, 370/217, 370/362, 370/254, 370/216, 709/203, 710/316, 395/551, 708/700, 371/21
• US Class Current: 370/401
• CPC Class Codes: H04L 65/80 Responding to QoS

Abstract

The present invention is directed, in various embodiments, to a hardware supported duplication token for arbitrating active and standby module states, a weighted state of health exchange for identifying unhealthy module states and relative module health states, and a packet sequence number synchronization technique for maintaining desired levels of synchronization between the active and standby modules.

Claims

1. A method, comprising:

(a) providing first and second processing devices, the second processing device providing duplicate functions to the first processing device;

(b) determining, by the first processing device, that a token grab value in a memory of the first processing device has a first, but not a second, value, wherein the first value requires the first processing device to attempt to obtain ownership of a duplication token and a second value requires the first processing device not to attempt to obtain ownership of the duplication token;

(c) in response to the token grab value having the first value, determining, by the first processing device, whether the second processing device has asserted a duplication token; and

(d) in a first mode, determining, by the first processing device, that the second processing device has not asserted the duplication token, and asserting, by the first processing device, the duplication token, wherein, upon assertion by the first processing device, the duplication token is owned by the first processing device and the first processing device is in the active state and the second processing device is in the standby state; and

(e) in a second mode, determining, by the first processing device, that the second processing device has asserted the duplication token and that the duplication token is in contention between the first and second processing devices, and applying, by the first processing device, an arbitration rule to determine which of the first and second processing devices is to have ownership of the duplication token.

2. The method of claim 1, wherein the duplication token is a hardware supported semaphore that signals unequivocally that one of the first and second processing devices is in possession of a Time Division Multiplexed (“

TDM”

) resource and an electronic address.

3. The method of claim 2, wherein the duplication token is maintained by a tick function of an operating system of one of the first and second processing devices, and wherein the duplication token is asserted in a register of a field programmable gate array in each of the first and second processing devices, and wherein the duplication token resolves to a single memory value, the single memory value indicating a state of the duplication token and the state being one of available, owned, and contended.

4. The method of claim 1, wherein, when the second processing device does not release the duplication token during a selected time interval, the second processing device is forced to reset.

5. The method of claim 1, wherein the first mode is performed.

6. The method of claim 1, wherein the second mode is performed and wherein the first and second processing devices assign ownership of the duplication token based on at least one selected criterion that is associated with each of the first and second processing devices.

7. The method of claim 6, wherein the selected criterion is at least one of a Time Division Multiplexed (“

TDM”

) bus timeslot address, module hardware identifier, and a mathematically differentiable value unique between the first and second processing devices contending wherein the first and second processing devices are configured to access a TDM bus, wherein the first and second processing devices are interconnected by a private and arbitration link, each link having a bus configuration, wherein the duplication token is asserted over the private link, and wherein the first and second processing devices arbitrate ownership of the token over the arbitration link.

8. The method of claim 1, further comprising:

(f) determining a bit array comprising a plurality of bit sets, each bit set corresponding to at least one functional parameter, each of the functional parameters defining a state of a functional aspect of the corresponding one of the first and second processing devices, a first type of functional parameter indicating a critical functional aspect and a second type of functional parameter indicating a noncritical functional aspect;

(g) for each of the first and second processing devices, arithmetically assigning, based on the values of the plurality of bit sets, respectively, first and second cumulative health state values;

(h) when the second cumulative health state value equals or exceeds the first cumulative health state values, maintaining the second processing device in the active state; and

(i) when the first cumulative health state value exceeds the second cumulative health state value, changing the state of the first processing device from the standby to the active state and the state of the second processing device from the active to the standby state.

9. The method of claim 6, wherein a third party does not perform arbitration between the first and second processing devices, wherein the duplication token is a bit value asserted in a register of a field programmable gate array, and wherein the token grab value is stored in memories of the first and second processing devices.

10. The method of claim 1, wherein the second processing device has, for each call, a transmit packet stream and a second transmit packet sequence number and transmit rollover counter value, wherein the first processing device has, for each call, a first transmit packet sequence number and transmit rollover counter value, the first transmit packet sequence number being representative of the second transmit packet sequence number and the first transmit rollover counter value being representative of the second transmit rollover counter value and further comprising:

(e) the first processing device incrementing the first transmit packet sequence number and rollover counter while in the standby state; and

(f) upon the occurrence of a trigger event, adjusting the first transmit packet number and/or rollover counter values by a shift value representative of a temporal drift between the relative values of the first and second transmit packet number values.

11. A duplicated processing system, comprising:

first and second processing devices, the second processing device providing duplicate functions to the first processing device, wherein;

the first processing device is operable to (a) determine that a token grab value in a memory of the first processing device has a first, but not a second, value, the first value requiring the first processing device to attempt to obtain ownership of a duplication token and a second value requiring the first processing device not to attempt to obtain ownership of the duplication token, (b) in response to the token grab value having the first value, determine whether the second processing device has asserted a duplication token; and

(c) operate in the following modes;

(i) in a first mode when the second processing device has not asserted the duplication token, the first processing device asserts the duplication token, wherein, upon assertion by the first processing device, the duplication token is owned by the first processing device and the first processing device is in the active state and the second processing device is in the standby state; and

(ii) in a second mode when the second processing device has asserted the duplication token, the duplication token is in contention between the first and second processing devices and the first processing device applies an arbitration rule to determine which of the first and second processing devices is to have ownership of the duplication token.

12. The system of claim 11, wherein the duplication token is a hardware supported semaphore that signals unequivocally that one of the first and second processing devices is in possession of a Time Division Multiplexed (“

TDM”

) resource and an electronic address.

13. The system of claim 11, wherein the duplication token is maintained by a tick function of an operating system of one of the first and second processing devices, and wherein the duplication token is asserted in a register of a field programmable gate array in each of the first and second processing devices, and wherein the duplication token resolves to a single memory value, the single memory value indicating a state of the duplication token and the state being one of available, owned, and contended.

14. The system of claim 11, wherein, when the second processing device does not release the duplication token during a selected time interval, the second processing device is forced to reset.

15. The system of claim 11, wherein, in the second mode, the first and second processing devices assign ownership of the duplication token based on at least one selected criterion that is associated with each of the first and second processing devices.

16. The system of claim 15, wherein the selected criterion is at least one of a Time Division Multiplexed (“

TDM”

) bus timeslot address, module hardware identifier, and a mathematically differentiable value unique between the first and second processing devices contending wherein the first and second processing devices are configured to access a TDM bus, wherein the first and second processing devices are interconnected by a private and arbitration link, each link having a bus configuration, wherein the duplication token is asserted over the private link, and wherein the first and second processing devices arbitrate ownership of the token over the arbitration link.

17. The system of claim 11, further comprising:

a state-of-health agent, executable by a processor, operable to;

determine a bit array comprising a plurality of bit sets, each bit set corresponding to at least one functional parameter, each of the functional parameters defining a state of a functional aspect of the corresponding one of the first and second processing devices, a first type of functional parameter indicating a critical functional aspect and a second type of functional parameter indicating a noncritical functional aspect;

for each of the first and second processing devices, arithmetically assign, based on the values of the plurality of bit sets, respectively, first and second cumulative health state values;

in a first mode when the second cumulative health state value equals or exceeds the first cumulative health state values, maintaining the second processing device in the active state; and

in a second mode when the first cumulative health state value exceeds the second cumulative health state value, changing the state of the first processing device from the standby to the active state and the state of the second processing device from the active to the standby state.

18. The system of claim 15, wherein a third party does not perform arbitration between the first and second processing devices, wherein the duplication token is a bit value asserted in a register of a field programmable gate array, and wherein the token grab value is stored in memories of the first and second processing devices.

19. The system of claim 11, wherein the second processing device has, for each call, a transmit packet stream and a second transmit packet sequence number and transmit rollover counter value, wherein the first processing device has, for each call, a first transmit packet sequence number and transmit rollover counter value, the first transmit packet sequence number being representative of the second transmit packet sequence number and the first transmit rollover counter value being representative of the second transmit rollover counter value and further comprising:

a packet sequence synchronization agent, executable by a processor, operable to;

increment, in the standby second processing device, the first transmit packet sequence number and rollover counter while in the standby state; and

upon the occurrence of a trigger event, adjust the first transmit packet number and/or rollover counter values by a shift value representative of a temporal drift between the relative values of the first and second transmit packet number values.

20. A method, comprising:

(a) determining, by each of first and second processing devices, a corresponding bit array comprising a plurality of bit sets, each bit set corresponding to at least one functional parameter, each of the functional parameters defining a state of a functional aspect of a corresponding processing device, a first type of functional parameter indicating a critical functional aspect and a second type of functional parameter indicating a noncritical functional aspect;

(b) by each of the first and second processing devices, arithmetically assigning, based on the values of the plurality of bit sets in the corresponding bit array first and second cumulative health state values respectively;

(c) in a first mode, determining by one of the first and second processing devices that the second cumulative health state value equals or exceeds the first cumulative health state value and, in response, maintaining the second processing device in an active state; and

(d) in a second mode, determining by one of the first and second processing devices that the first cumulative health state value exceeds the second cumulative health state value and, in response, changing the state of the first processing device from a standby to the active state and the state of the second processing device from the active to the standby state.

21. The method of claim 20, wherein, in the arithmetically assigning step (b), the first type of functional parameters are weighted more heavily than the second type of functional parameters and wherein the arithmetic operation is addition.

22. The method of claim 20, wherein each of the functional parameters has a corresponding monitor, wherein a first type of monitor must be constantly activated to remain in a good state, wherein a second type of monitor is in a faulted state unless activated, and wherein a third type of monitor is set to one of the good or faulted states at each activation.

23. The method of claim 20, wherein, in the comparison of the first and second cumulative health state values, the second cumulative health state value is biased, wherein each of the functional parameters has a weight value that is a function of a priority level of the parameter, wherein the first and second processing devices exchange respective cumulative state values periodically, and further comprising:

(e) each of the first and second processing devices comparing the respective one of the first and second cumulative health state values to a selected threshold to determine whether the corresponding processing device is sufficiently healthy to be in the active state.

24. The method of claim 20, wherein the second processing device has, for each call, a transmit packet stream and a second transmit packet sequence number and transmit rollover counter value, wherein the first processing device has, for each call, a first transmit packet sequence number and transmit rollover counter value, the first transmit packet sequence number being representative of the second transmit packet sequence number and the first transmit rollover counter value being representative of the second transmit rollover counter value and further comprising:

(e) the first processing device incrementing the first transmit packet sequence number and rollover counter while in the standby state; and

(f) upon the occurrence of a trigger event, adjusting the first transmit packet number and/or rollover counter values by a shift value representative of a temporal drift between the relative values of the first and second transmit packet number values.

25. The method of claim 20, further comprising:

(e) the first processing device determining whether a duplication token has been asserted by the second processing device during a selected time interval;

(f) when the duplication token has been asserted by the second processing device during the selected time interval, maintaining the first processing device in the standby state; and

(g) when the duplication token has not been asserted by the second processing device during the selected time interval, changing the state of the first processing device from the standby state to the active state, thereby causing the first processing device to assume control of a function performed previously by the second processing device.

26. The method of claim 25, wherein the selected time interval is a function of a tick function, wherein the function is control of a time division multiplexed bus and further comprising:

(h) when the duplication token has not been released by the second processing device during the selected time interval, resetting the second processing device.

27. The method of claim 25, wherein steps (e) and (f) are performed when the second processing owns the token and further comprising:

(h) the first and second processing devices each asserting a duplication token with a selected time period such that the ownership of the duplication token is contended by the first and second processing devices, wherein the first and second processing devices assign ownership of the token based on at least one selected criterion that is associated with each of the first and second processing devices.

28. The method of claim 25, wherein, when the duplication token is not owned by either the first or second processing device, further comprising:

(h) assigning ownership of the duplication token to the second processing device, when the first processing device fails to assert the token within a selected time period.

29. A system, comprising:

first and second processing devices, each of the first and second processing devices comprising a respective processor to execute a state-of-health agent, the state-of-health agent, when executed, performs the following operations;

(a) determine, for a corresponding one of the first and second processing devices, a corresponding bit array comprising a plurality of bit sets, each bit set corresponding to at least one functional parameter, each of the functional parameters defining a state of a functional aspect of the corresponding first or second processing device, a first type of functional parameter indicating a critical functional aspect and a second type of functional parameter indicating a noncritical functional aspect;

(b) arithmetically assign, based on the values of the plurality of bit sets in the corresponding bit array, a corresponding cumulative health state value, the first processing device having a first cumulative health state and the second processing device having a second cumulative health state;

(c) in a first mode, determine, by at least one of the state-of-health agents in the first and second processing devices, that the second cumulative health state value equals or exceeds the first cumulative health state value and, in response, maintain the second processing device in an active state; and

(d) in a second mode, determine, by at least one of the state-of-health agents in the first and second processing devices, that the first cumulative health state value exceeds the second cumulative health state value and, in response, change the state of the first processing device from a standby to the active state and the state of the second processing device from the active to the standby state.

30. The system of claim 29, wherein, in the arithmetically assigning operation (b), the first type of functional parameters are weighted more heavily than the second type of functional parameters and wherein the arithmetic operation is addition.

31. The system of claim 29, wherein each of the functional parameters has a corresponding monitor, wherein a first type of monitor must be constantly activated to remain in a good state, wherein a second type of monitor is in a faulted state unless activated, and wherein a third type of monitor is set to one of the good or faulted states at each activation.

32. The system of claim 29, wherein, in the comparison of the first and second cumulative health state values, the second cumulative health state value is biased, wherein each of the functional parameters has a weight value that is a function of a priority level of the parameter, wherein the first and second processing devices exchange respective cumulative state values periodically, and further comprising the operation:

(e) each of the first and second processing devices compares the respective one of the first and second cumulative health state values to a selected threshold to determine whether the corresponding processing device is sufficiently healthy to be in the active state.

33. The system of claim 29, wherein the second processing device has, for each call, a transmit packet stream and a second transmit packet sequence number and transmit rollover counter value, wherein the first processing device has, for each call, a first transmit packet sequence number and transmit rollover counter value, the first transmit packet sequence number being representative of the second transmit packet sequence number and the first transmit rollover counter value being representative of the second transmit rollover counter value and further comprising the operations:

(e) the first processing device increments the first transmit packet sequence number and rollover counter while in the standby state; and

(f) upon the occurrence of a trigger event, the first transmit packet number and/or rollover counter values is adjusted by a shift value representative of a temporal drift between the relative values of the first and second transmit packet number values.

34. The system of claim 29, further comprising the operations:

(e) the first processing device determines whether a duplication token has been asserted by the second processing device during a selected time interval;

(f) when the duplication token has been asserted by the second processing device during the selected time interval, the first processing device is maintained in the standby state; and

(g) when the duplication token has not been asserted by the second processing device during the selected time interval, the state of the first processing device is changed from the standby state to the active state, thereby causing the first processing device to assume control of a function performed previously by the second processing device.

35. The system of claim 34, wherein the selected time interval is a function of a tick function, wherein the function is control of a time division multiplexed bus and further comprising the operation:

(h) when the duplication token has not been released by the second processing device during the selected time interval, the second processing device is reset.

36. The system of claim 34, wherein operations (e) and (f) are performed when the second processing owns the token and further comprising the operation:

(h) the first and second processing devices each assert a duplication token with a selected time period such that the ownership of the duplication token is contended by the first and second processing devices, wherein the first and second processing devices assign ownership of the token based on at least one selected criterion that is associated with each of the first and second processing devices.

37. The system of claim 34, wherein, when the duplication token is not owned by either the first or second processing device, further comprising the operation:

(h) ownership of the duplication token is assigned to the second processing device, when the first processing device fails to assert the token within a selected time period.

38. A method, comprising:

(a) providing first and second processing systems, the second processing system being in the active state and the first processing system being in the standby state, the second processing system having, for each call, a transmit packet stream and a second transmit packet sequence number and transmit rollover counter value, wherein the first processing system has, for each call, a first transmit packet sequence number and transmit rollover counter value, the first transmit packet sequence number being representative of the second transmit packet sequence number and the first transmit rollover counter value being representative of the second transmit rollover counter value;

(b) the first processing system incrementing the first transmit packet sequence number and rollover counter value while in the standby state; and

(c) upon the occurrence of a trigger event, adjusting the first transmit packet sequence number and/or rollover counter value by a shift value representative of a temporal drift between the relative values of the first and second transmit packet sequence numbers, wherein the drift causes the first and second transmit packet sequence numbers to be different and wherein the drift is caused by silence suppression.

39. The method of claim 38, wherein the second processing system has, for each call, a receive packet stream and a second receive packet sequence number and receive rollover counter value, wherein the first processing system has, for each call, a first receive packet sequence number and receive rollover counter value, the first receive packet sequence number being representative of the second receive packet sequence number and the first receive rollover counter value being representative of the second receive rollover counter value, wherein the second receive packet sequence number and rollover counter values are exchanged upon the occurrence of the trigger event, and wherein the trigger event is one or more of the passage of a selected period of time, the establishment of a call on the second processing system, validation by the second processing system of data associated with an active call, establishment of a call on the first processing system, and validation by the first processing system of data associated with an active call.

40. The method of claim 38, wherein the adjustment is performed by the following substeps:

(c1) converting the shift time into a sequence number using the codec frame size defined for the call; and

(c2) converting the shift time to the timestamp resolution defined for the call.

41. The method of claim 38, further comprising:

(d) the first processing system determining whether a duplication token has been asserted by the second processing system during a selected time interval;

(e) when the duplication token has been asserted by the second processing system during the selected time interval, maintaining the first processing system in the standby state; and

(f) when the duplication token has not been asserted by the second processing system during the selected time interval, changing the state of the first processing system from the standby state to the active state, thereby causing the first processing system to assume control of a function performed previously by the second processing system.

42. The method of claim 38, further comprising:

(d) determining a bit array comprising a plurality of bit sets, each bit set corresponding to at least one functional parameter, each of the functional parameters defining a state of a functional aspect of a corresponding processing system, a first type of functional parameter indicating a critical functional aspect and a second type of functional parameter indicating a noncritical functional aspect;

(e) for each of first and second processing systems, arithmetically assigning, based on the values of the plurality of bit sets, respectively, first and second cumulative health state values;

(f) when the second cumulative health state value equals or exceeds the first cumulative health state values, maintaining the second processing system in an active state; and

(g) when the first cumulative health state value exceeds the second cumulative health state value, changing the state of the first processing system from a standby to the active state and the state of the second processing system from the active to the standby state.

43. The system of claim 38, further comprising the operations:

(c) determining a bit array comprising a plurality of bit sets, each bit set corresponding to at least one functional parameter, each of the functional parameters defining a state of a functional aspect of a corresponding processing device, a first type of functional parameter indicating a critical functional aspect and a second type of functional parameter indicating a noncritical functional aspect;

(d) for each of first and second processing devices, arithmetically assigning, based on the values of the plurality of bit sets, respectively, first and second cumulative health state values;

(e) when the second cumulative health state value equals or exceeds the first cumulative health state values, maintaining the second processing device in an active state; and

(f) when the first cumulative health state value exceeds the second cumulative health state value, changing the state of the first processing device from a standby to the active state and the state of the second processing device from the active to the standby state.

44. A system, comprising:

first and second processing devices, the second processing device being in the active state and the first processing device being in the standby state, the second processing device having, for each call, a transmit packet stream and a second transmit packet sequence number and transmit rollover counter value, wherein the first processing device has, for each call, a first transmit packet sequence number and transmit rollover counter value, the first transmit packet sequence number being representative of the second transmit packet sequence number and the first transmit rollover counter value being representative of the second transmit rollover counter value;

wherein the first processing device comprises a processor operable to execute a packet sequence synchronization agent, the packet sequence synchronization agent, when executed, is operable to perform the following operations;

(a) increment the first transmit packet sequence number and rollover counter value while in the standby state; and

(b) upon the occurrence of a trigger event, adjust the first transmit packet number and/or rollover counter values by a shift value representative of a temporal drift between the relative values of the first and second transmit packet number values, wherein the drift causes the first and second transmit packet number values to be different and wherein the drift is caused by silence suppression.

45. The system of claim 44, wherein the second processing device has, for each call, a receive packet stream and a second receive packet sequence number and receive rollover counter value, wherein the first processing device has, for each call, a first receive packet sequence number and receive rollover counter value, the first receive packet sequence number being representative of the second receive packet sequence number and the first receive rollover counter value being representative of the second receive rollover counter value, wherein the second receive packet sequence number and rollover counter values are exchanged upon the occurrence of the trigger event, and wherein the trigger event is one or more of the passage of a selected period of time, the establishment of a call on the second processing device, validation by the second processing device of data associated with an active call, establishment of a call on the first processing device, and validation by the first processing device of data associated with an active call.

46. The system of claim 44, wherein the adjustment is performed by the following suboperations:

(b1) converting the shift time into a sequence number using the codec frame size defined for the call; and

(b2) converting the shift time to the timestamp resolution defined for the call.

47. The system of claim 44, further comprising the operations:

(c) the first processing device determining whether a duplication token has been asserted by the second processing device during a selected time interval;

(d) when the duplication token has been asserted by the second processing device during the selected time interval, maintaining the first processing device in the standby state; and

(e) when the duplication token has not been asserted by the second processing device during the selected time interval, changing the state of the first processing device from the standby state to the active state, thereby causing the first processing device to assume control of a function performed previously by the second processing device.