Method and apparatus for scheduling message processing

• US 20030016685A1
• Filed: 07/13/2001
• Published: 01/23/2003
• Est. Priority Date: 07/13/2001
• Status: Active Grant

• Current Assignee: Ericsson, Inc. (Telefonaktiebolaget LM Ericsson)
• Original Assignee: Ericsson, Inc. (Telefonaktiebolaget LM Ericsson)
• Inventors: Berggreen, Arthur
• Granted Patent: US 7,170,900 B2
• Time in Patent Office: Days
• US Class Current: 370/412
• CPC Class Codes: H04L 2012/5621 Virtual private network [VPN]; Private-network - network-interface (P-NNI)
• CPC Class Codes: H04L 2012/5679 Arbitration or scheduling
• CPC Class Codes: H04L 47/2441 relying on flow classification, e.g. using integrated services [IntServ]
• CPC Class Codes: H04L 47/50 Queue scheduling
• CPC Class Codes: H04L 47/58 Changing or combining different scheduling modes, e.g. multimode scheduling
• CPC Class Codes: H04L 47/626 channel conditions
• CPC Class Codes: H04L 47/6285 Provisions for avoiding starvation of low priority queues
• CPC Class Codes: H04Q 11/0478 Provisions for broadband connections

Abstract

The present invention provides a method and apparatus for scheduling message processing. The present invention provides a scheduling mechanism, or scheduler (602), that receives messages (608) and stores the messages (610 or 614) in a first queue (604) or a second queue (606) based, in part, on various criteria associated with the messages. The criteria include message attributes, such as message priority, virtual private network (“VPN”) classification and destination software function. The first queue (604) can be a first-in-first-out queue, and the second queue (606) can be a multi-dimensional queue. The scheduler (602) then schedules the queued messages (612 or 616) for processing based, in part, on various operating criteria (618), such as historical operating data, current operating data and anti-starvation criteria. In addition, the scheduler (602) can be programmed to function in a variety of operating modes.

Claims

1. An apparatus for scheduling one or more messages comprising:

a first queue;

a second queue;

a scheduler communicably coupled to the first queue and the second queue, the scheduler having at least a first and second operating mode;

the first operating mode comprising receiving the one or more messages, storing each message in the first queue based on a first-in-first-out order, and scheduling each queued message from the first queue based on the first-in-first-out order; and

the second operating mode comprising receiving the one or more messages, storing each message in the second queue based on one or more message attributes, and scheduling each queued message from the second queue based on one or more operating criteria.

2. The apparatus as recited in claim 1, wherein the first operating mode corresponds to low message traffic conditions.

3. The apparatus as recited in claim 1, wherein the scheduler operates in the first mode when the number of queued messages in the first queue is less than a first value and the number of queued messages in the second queue is zero.

4. The apparatus as recited in claim 1, wherein the second operating mode corresponds to high message traffic conditions.

5. The apparatus as recited in claim 1, wherein the scheduler operates in the second mode when the number of queued messages in the second queue is greater than a second value and the number of queued messages in the first queue is zero.

6. The apparatus as recited in claim 1, further comprising a third operating mode comprising receiving the one or more messages, storing each message in the second queue based one or more message attributes, and scheduling each queued message from the first queue based on the first-in-first-out order.

7. The apparatus as recited in claim 6, wherein the third operating mode corresponds to a transition from low traffic to high traffic.

8. The apparatus as recited in claim 6, wherein the scheduler switches to the third operating mode when the number of queued messages in the first queue is greater than or equal to the first value and continues to operate in the third operating mode until the scheduler switches to the second operating mode when the number of queued messages in the first queue is zero.

9. The apparatus as recited in claim 6, further comprising a fourth operating mode comprising receiving the one or more messages, storing each message in the first queue based on the first-in-first-out order, and scheduling each queued message from the second queue based on one or more operating criteria.

10. The apparatus as recited in claim 9, wherein the fourth operating mode corresponds to a transition from high traffic to low traffic.

11. The apparatus as recited in claim 9, wherein the scheduler switches to the fourth operating mode when the number of queued messages in the second queue is less than or equal to the second value and continues to operate in the fourth operating mode until the scheduler switches to the first operating mode when the number of queued messages in the second queue is zero.

12. The apparatus as recited in claim 1, wherein the second queue is a multi-dimensional queue.

13. The apparatus as recited in claim 1, wherein the one or more message attributes includes a message priority.

14. The apparatus as recited in claim 1, wherein the one or more message attributes includes a virtual private network classification.

15. The apparatus as recited in claim 1, wherein the one or more message attributes includes a destination software function.

16. The apparatus as recited in claim 1, wherein the one or more operating criteria is based on historical operating data.

17. The apparatus as recited in claim 1, wherein the one or more operating criteria is based on current operating data.

18. The apparatus as recited in claim 1, wherein the one or more operating criteria is based on one or more anti-starvation criteria.

19. The apparatus as recited in claim 1, further comprising a processor communicably coupled to the scheduler for processing the dispatched messages.

20. The apparatus as recited in claim 1, further comprising a memory communicably coupled to the scheduler for storing the one or more operating criteria.

21. A method for scheduling one or more messages comprising the steps of:

receiving the one or more messages;

selecting a first queue for input and output during a first operating mode;

selecting a second queue for input and output during a second operating mode;

storing each message in the first queue based on a first-in-first-out order whenever the first queue is selected for input or storing each message in the second queue based on one or more message attributes whenever the second queue is selected for input; and

scheduling each queued message from the first queue based on the first-in-first-out order whenever the first queue is selected for output or scheduling each queued message from the second queue based one or more operating criteria whenever the second queue is selected for output.

22. The method as recited in claim 21, wherein the first operating mode corresponds to low message traffic conditions.

23. The method as recited in claim 21, wherein the first operating mode occurs when the number of queued messages in the first queue is less than a first value and the number of queued messages in the second queue is zero.

24. The method as recited in claim 21, wherein the second operating mode corresponds to high message traffic conditions.

25. The method as recited in claim 21, wherein the second operating mode occurs when the number of queued messages in the second queue is greater than a second value and the number of queued messages in the first queue is zero.

26. The method as recited in claim 21, further comprising the step of selecting the second queue for input and the first queue for output during a third operating mode.

27. The method as recited in claim 26, wherein the third operating mode corresponds to a transition from low traffic to high traffic.

28. The method as recited in claim 26, wherein the third operating mode occurs when the number of queued messages in the first queue is greater than or equal to the first value and continues until switching to the second operating mode when the number of queued messages in the first queue is zero.

29. The method as recited in claim 26, further comprising the step of selecting the second queue for output and the first queue for input during a fourth operating mode.

30. The method as recited in claim 29, wherein the fourth operating mode corresponds to a transition from high traffic to low traffic.

31. The method as recited in claim 29, wherein the fourth operating mode occurs when the number of queued messages in the second queue is less than or equal to the second value and continues until switching to the first operating mode when the number of queued messages in the second queue is zero.

32. The method as recited in claim 21, wherein the second queue is a multi-dimensional queue.

33. The method as recited in claim 21 wherein the one or more message attributes includes a message priority.

34. The method as recited in claim 21, wherein the one or more message attributes includes a virtual private network classification.

35. The method as recited in claim 21, wherein the one or more message attributes includes a destination software function.

36. The method as recited in claim 21, wherein the one or more operating criteria is based on historical operating data.

37. The method as recited in claim 21, wherein the one or more operating criteria is based on current operating data.

38. The method as recited in claim 21, wherein the one or more operating criteria is based on one or more anti-starvation criteria.

40. The computer program as recited in claim 39, wherein the first operating mode corresponds to low message traffic conditions.

41. The computer program as recited in claim 39, wherein the first operating mode occurs when the number of queued messages in the first queue is less than a first value and the number of queued messages in the second queue is zero.

42. The computer program as recited in claim 39, wherein the second operating mode corresponds to high message traffic conditions.

43. The computer program as recited in claim 39, wherein the second operating mode occurs when the number of queued messages in the second queue is greater than a second value and the number of queued messages in the first queue is zero.

44. The computer program as recited in claim 39, further comprising a code segment for selecting the second queue for input and the first queue for output during a third operating mode.

45. The computer program as recited in claim 44, wherein the third operating mode corresponds to a transition from low traffic to high traffic.

46. The computer program as recited in claim 44, wherein the third operating mode occurs when the number of queued messages in the first queue is greater than or equal to the first value and continues until switching to the second operating mode when the number of queued messages in the first queue is zero.

47. The computer program as recited in claim 44, further comprising a code segment for selecting the second queue for output and the first queue for input during a fourth operating mode.

48. The computer program as recited in claim 47, wherein the fourth operating mode corresponds to a transition from high traffic to low traffic.

49. The computer program as recited in claim 47, wherein the fourth operating mode occurs when the number of queued messages in the second queue is less than or equal to the second value and continues until switching to the first operating mode when the number of queued messages in the second queue is zero.

50. The computer program as recited in claim 39, wherein the second queue is a multi-dimensional queue.

51. The computer program as recited in claim 39, wherein the one or more message attributes includes a message priority.

52. The computer program as recited in claim 39, wherein the one or more message attributes includes a virtual private network classification.

53. The computer program as recited in claim 39, wherein the one or more message attributes includes a destination software function.

54. The computer program as recited in claim 39, wherein the one or more operating criteria is based on historical operating data.

55. The computer program as recited in claim 39, wherein the one or more operating criteria is based on current operating data.

56. The computer program as recited in claim 39, wherein the one or more operating criteria is based on one or more anti-starvation criteria.

39. A computer program embodied on a computer readable medium for scheduling one or more messages, the computer program comprising:

a code segment for receiving the one or more messages;

a code segment for selecting a first queue for input and output during a first operating mode;

a code segment for selecting a second queue for input and output during a second operating mode;

a code segment for storing each message in the first queue based on a first-in-first-out order whenever the first queue is selected for input or storing each message in the second queue based on one or more message attributes whenever the second queue is selected for input; and

a code segment for scheduling each queued message from the first queue based on the first-in-first-out order whenever the first queue is selected for output or scheduling each queued message from the second queue based one or more operating criteria whenever the second queue is selected for output.

57. A communications switch comprising:

one or more ingress cards;

one or more signal processing cards, each signal processing card containing an array of digital signal processors;

one or more control cards containing one or more processors;

one or more egress cards;

a switch fabric communicably coupling the ingress cards, the signal processing cards, the control cards and the egress cards;

a TDM bus communicably coupling the ingress cards, the signal processing cards, the control cards and the egress cards;

a scheduler communicably coupled to each processor, the scheduler having at least a first and second operating mode;

a first queue communicably coupled to the scheduler;

a second queue communicably coupled to the scheduler;

the first operating mode comprising receiving the one or more messages, storing each message in the first queue based on a first-in-first-out order, and scheduling each queued message from the first queue based on the first-in-first-out order; and

the second operating mode comprising receiving the one or more messages, storing each message in the second queue based one or more message attributes, and scheduling each queued message from the second queue based one or more operating criteria.