Fault recovery in concurrent queue management systems

• US 20060274372A1
• Filed: 06/02/2005
• Published: 12/07/2006
• Est. Priority Date: 06/02/2005
• Status: Active Grant

• Current Assignee: Avaya Incorporated
• Original Assignee: Avaya Technology Corporation Miami Lakes FLA US
• Inventors: Qutub, Sami, Sitkowski, Rafal
• Granted Patent: US 7,770,061 B2
• Time in Patent Office: Days
• US Class Current: 358/1.160
• CPC Class Codes: G06F 11/1479 Generic software techniques for error detection or fault masking
• CPC Class Codes: G06F 11/3006 where the computing system is distributed, e.g. networked systems, clusters, multiprocessor systems multiprogramming arrangements G06F9/46; allocation of resources G06F9/50
• CPC Class Codes: G06F 11/3055 Monitoring arrangements for monitoring the status of the computing system or of the computing system component, e.g. monitoring if the computing system is on, off, available, not available error or fault processing without redundancy G06F11/0703; error detection or correction by redundancy in data representation G06F11/08; error detection or correction by redundancy in operation G06F11/14; error detection or correction by redundancy in hardware G06F11/16
• CPC Class Codes: H04L 41/0654 using network fault recovery ring fault isolation or reconfiguration in loop networks without recovery actions by a network management system H04L12/437

Abstract

A method for fault tolerance and fault recovery in multiprocessor systems that concurrently manage queues is disclosed. The illustrative embodiment comprises a plurality of servers, a queue of jobs to be assigned to the servers, and two queue managers—a primary unit and a secondary unit—such that the secondary fills in for the primary unit while the primary unit is down. The illustrative embodiment provides for smooth transitions from the normal state into the failure state and back into the normal state without losing jobs or violating the queue discipline of the system.

Claims

1. A method comprising:

queuing at a first queue manager a first job to be served by a first server;

queuing at a second queue manager a second job to be served by said first server;

transmitting a first idle/busy indicator for said first server to said first queue manager and said second queue manager;

assigning said second job to said first server within a first time interval after said first idle/busy indicator becomes idle; and

assigning said first job to said first server only after said first idle/busy indicator has been idle for at least said first time interval.

2. The method of claim 1 further comprising:

queuing a third job to be served by said first server at said first queue manager after said first job is queued at said first queue manager; and

assigning said third job to said first server by said first queue manager within a first time interval after said first idle/busy indicator becomes idle.

3. The method of claim 1 wherein said second job is queued at said second queue manager before said first job is queued at said first queue manager.

4. The method of claim 1 wherein said second job is assigned to said first server before said first job is assigned to said first server.

5. The method of claim 1 further comprising:

queuing a third job to be served by a second server at said first queue manager;

queuing a fourth job to be served by said second server at said second queue manager;

transmitting a second idle/busy indicator for said second server to said first queue manager and said second queue manager;

assigning said fourth job to said second server by said second queue manager within a second time interval after said second idle/busy indicator becomes idle; and

assigning said third job to said second server by said first queue manager only after said second idle/busy indicator has been idle for at least said second time interval.

6. The method of claim 5 wherein said second job and said fourth job are queued in said second queue manager before said first job and said third job are queued in said first queue manager.

7. The method of claim 5 wherein said fourth job is assigned to said second server before said third job is assigned to said second server.

8. The method of claim 5 wherein said third job is assigned to said second server before said first job is assigned to said first server.

9. The method of claim 1 wherein said first job is a telephone call.

10. A method comprising:

queuing a first plurality of jobs at a first queue manager;

queuing a second plurality of jobs at a second queue manager;

assigning one of said first plurality of jobs to a first server after said second queue manager has not assigned any of said second plurality of jobs to said first server for at least a first time interval; and

assigning one of said first plurality of jobs to a second server after said second queue manager has not assigned any of said second plurality of jobs to said second server for at least said first time interval.

11. The method of claim 10 wherein said first plurality of jobs are queued at said first queue manager after said second plurality of jobs are queued at said second queue manager.

12. The method of claim 10 wherein after said first queue manager has assigned one of said first plurality of jobs to said first server, said first queue manager assigns a second of said first plurality of jobs to said first server immediately upon said first server becoming idle.

13. The method of claim 10 wherein after said first queue manager has assigned one of said first plurality of jobs to said first server, said second queue manager does not assign any of said second plurality of jobs to said first server.

14. The method of claim 10 wherein said first plurality of jobs and said second plurality of jobs are telephone calls.

17. The method of claim 10 wherein said first plurality of jobs are queued at said first queue manager after said second plurality of jobs are queued at said second queue manager.

18. The method of claim 10 wherein said first plurality of jobs and said second plurality of jobs are telephone calls.

15. A method comprising:

queuing a first plurality of jobs at a first queue manager;

queuing a second plurality of jobs at a second queue manager; and

assigning one of said first plurality of jobs to a first server after said second queue manager has not assigned any of said second plurality of jobs to said first server for at least a first time interval;

wherein after said first queue manager has assigned one of said first plurality of jobs to said first server, said second queue manager does not assign any of said second plurality of jobs to said first server.

16. The method of claim 15 further comprising assigning one of said first plurality of jobs to a second server after said second queue manager has not assigned any of said second plurality of jobs to said second server for at least said first time interval.

19. A method comprising:

recovering a queue manager from a failure, wherein said queue manager is for assigning jobs to a server; and

inferring that a queue external to said queue manager does not contain any jobs that arrived prior to the recovery of said queue manager from said failure.

20. The method of claim 19 wherein the inference is performed without knowledge of the contents of said queue.

21. The method of claim 20 wherein the inference occurs if, and only if, said server is idle for more than N seconds, wherein N is a positive real number.

22. The method of claim 19 further comprising:

receiving a job at said queue manager after the recovery of said queue manager from said failure; and

refraining from assigning said job until after the inference is made.

23. The method of claim 19 wherein during said failure another queue manager assigns one or more jobs to said server.

24. The method of claim 23 wherein said queue manager and said other queue manager employ different queue disciplines.

25. The method of claim 19 wherein at least one of said jobs is a telephone call.

26. The method of claim 19 wherein at least one of said jobs is an Internet Protocol packet.