Multi-stage timer implementation for telecommunications transmission

• US 5,838,957 A
• Filed: 02/01/1996
• Issued: 11/17/1998
• Est. Priority Date: 02/01/1996
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Rajaraman, Balachandar, Varma, Subir
• Primary Examiner(s): Heckler, Thomas M.
• Application Number:
  US08/595,065
• Time in Patent Office: 1,020 Days
• Field of Search: 395/557
• US Class Current: 713/502
• CPC Class Codes: G06F 9/4825 Interrupt from clock, e.g. time of day

Abstract

Telecommunications networks require a large number of timers to support the necessary dispatching of tasks. These timers require significant CPU cycles. The present invention describes a method and apparatus for reducing the CPU requirements of timers while maintaining their utility and accuracy by using multi-class periodic timers.

Claims

1. In a telecommunications network containing one or more host computers, each host computer containing a plurality of tasks, each of said plurality of tasks periodically generating timer requests wherein each timer request specifies the time interval in which it is to expire, a system for implementing a timing control mechanism for controlling said periodically generated timer requests:

a first burst timer set for controlling said timer requests characterized by having specified that they are to expire within a first time interval;

a second burst timer set for controlling said timer requests characterized by having specified that they are to expire after said first time interval, but before a second time interval, wherein said second time interval is longer than said first time interval; and

a third timer set, organized according to a timing wheel structure, for controlling said timer requests characterized by having specified that they are to expire after said second time interval.

2. A system for implementing a timing control mechanism as in claim 1, wherein said telecommunications network is High Performance Routing (HPR) capable.

7. A system for implementing a timing control mechanism as in any of claims 1-6, wherein each of said burst timer sets is organized as a linked list.

3. In a communications system containing one or more host computers, each host computer containing a plurality of tasks, each of said plurality of tasks periodically generating timer requests wherein each timer request specifies the time interval in which it is to expire, a system for implementing a timing control mechanism for controlling said periodically generated timer requests, comprising:

a plurality of burst timer sets, each of said burst timer sets having associated therewith a unique expiration time; and

a final timer set organized as a timing wheel, said final timer set characterized by having multiple, unique expiration times associated therewith, wherein the minimum of said multiple unique expiration times of said final timer set is greater than the maximum expiration time of any of said plurality of burst timer sets.

4. A system for implementing a timing control mechanism as in claim 3, wherein said communications system is High Performance Routing (HPR) capable.

5. In a communications system containing one or more host computers, each host computer containing a plurality of tasks, each of said plurality of tasks periodically generating timer requests wherein each timer request specifies the time interval in which it is to expire, a system for implementing a timing control mechanism for controlling said periodically generated timer requests, comprising:

a plurality of burst timer sets, each of said burst timer sets having associated therewith a predetermined interval of time in which all timer requests in the timer set are to expire;

a timing wheel set, said timing wheel set having associated therewith a predetermined interval of time in which all timer requests in the timing wheel set are to expire; and

a means for determining which of said periodically generated timer requests are to be members of the burst timer sets and which of said periodically generated timer requests are to be members of the timing wheel set.

6. A system for implementing a timing control mechanism as in claim 5, wherein said means determines that a timer request is to be a member of the burst timer sets, or of the timing wheel set, by balancing the number of outstanding timer requests that are members of each timer set.

8. A system for implementing a timing control mechanism as in claims 5 or 6, wherein said communication system is High Performance Routing (HPR) capable.

9. A system for implementing a timing control mechanism as in claim 5, further comprising:

a plurality of said timing wheel sets, each of said sets having associated therewith a predetermined interval of time that is different from each of other said sets; and

wherein said means for determining further comprises means for selecting one of said timing wheel sets after having determined that a timer request is to be a member of a timing wheel set.

10. In a computer network containing one or more host computers, each host computer containing a plurality of tasks, each of said plurality of tasks periodically generating timer requests wherein each timer request specifies a time interval in which it is to expire, a system for implementing a timing control mechanism for controlling said periodically generated timer requests, comprising:

a plurality of burst timer sets,

a timing wheel set, and

wherein each of said timer requests is assigned to become a member of one of said burst timer sets or said timing wheel set by a means for balancing the number of said timer requests assigned to become members of each of said timer sets.

11. In a computer connected to a communications network, said computer containing a plurality of tasks, each of said plurality of tasks periodically generating timer requests wherein each timer request specifies the time interval in which it is to expire, a system for implementing a timing control mechanism for controlling said periodically generated timer requests, said timing mechanism comprising:

means for executing a plurality of said periodically generated timer requests;

means for scheduling said plurality of periodically generated timer requests, wherein said means comprise;

a plurality of burst timer sets;

a timing wheel set; and

means for determining whether each of said timer requests should become a member of one of said burst timer sets, or should become a member of said timing wheel set.

12. A system for implementing a timing control mechanism as in claim 11, wherein said timing wheel set includes an overflow slot.

13. A system for implementing a timing control mechanism as in claim 11 or 12 wherein said communications network is High Performance Routing (HPR) capable.

14. A system for implementing a timing control mechanism as in claim 11, further comprising:

a plurality of said timing wheel sets; and

wherein said means for determining further comprises means for selecting one of said timing wheel sets after having determined that a timer request is to be a member of a timing wheel set.

15. In a telecommunications network containing one or more host computers, each host computer containing a plurality of tasks, each of said plurality of tasks periodically generating timer requests wherein each timer request specifies the time interval in which it is to expire, a system for implementing a timing control mechanism for controlling said periodically generated timer requests, comprising:

a linked list wherein the entries in the list include at least one Timer Control Block (TCB) and zero or more timing wheel blocks, wherein;

each of said TCBs or timing wheel blocks has associated therewith a task expiration time interval;

said linked list is ordered in ascending order of said task expiration time interval; and

,

each of said timing wheel blocks points to a timing wheel set; and

means for inserting said TCBs and timing wheel blocks into said linked list so as to maintain said linked list in ascending order of said associated task expiration time interval.

16. In a computer network containing one or more host computers, each host computer containing a plurality of tasks, each of said plurality of tasks periodically generating timer requests wherein each timer request specifies the time interval in which it is to expire, a system for implementing a timing control mechanism for controlling said periodically generated timer requests, comprising:

a plurality of burst timer sets,

a plurality of timing wheel sets, and

wherein each of said timer requests is assigned to become a member of one of said burst timer sets or one of said timing wheel sets by a means for balancing the number of said timer requests assigned to become members of each of said timer sets.