Electrical computers and digital processing systems: multicomput – Computer-to-computer data routing – Least weight routing
Reexamination Certificate
2000-06-23
2004-03-30
Follansbee, John (Department: 2126)
Electrical computers and digital processing systems: multicomput
Computer-to-computer data routing
Least weight routing
C709S241000, C713S600000, C710S054000
Reexamination Certificate
active
06714959
ABSTRACT:
FIELD OF THE INVENTION
The present system describes methods for use and flexibility in scheduling events in computers and system networks whereby improved methods of scheduling events are provided.
BACKGROUND OF THE INVENTION
In many computer networks, computerized telephone and billing systems, there is intercommunication mechanisms in computers and other types of systems which handle multiple events are often presented with the problem of scheduling a certain event to happen at a particular time which is to be arranged for set-up in the system.
Many memory systems for example, have queues of items to be accessed or handled in a particular sequence. Many programs have lists of instructions which are sequenced also to be handled in a particular arrangement of time events. Sometimes, thousands of different items are placed in queues in order to be available for access in a particular sequence or order.
For example, in the compilation of a telephone directory or a directory of certain businesses in a certain location or a directory of the names of people associated with a certain group, these are all examples of data words or information which are placed in queues and which may be accessed, acquired and used at certain moments of time.
Additionally, once such a list is compiled, it is very often necessary to place insertions into the queue list, for example, new person's names may be added to a group organization list, or new telephone numbers and addresses and names may be put in a telephone book. Similarly, and often in Kerberos Security Systems, a list of authenticated users and appropriate passwords and tickets may be involved in a list of such useful items.
In each and any of the cases, when it is necessary to add to a particular list, it is sometimes a rather magnitudinous task to achieve this type of event when there is required the normal situation where the system must check through each of the items in the list step-by-step until it reaches its selected position where the insertion must be made, after which a stop operation must occur after which the new item is inserted into the system and which performs the completion of this operation. However, in so doing, sometimes thousands and thousands of entries must be sequenced through to find the exact point where the new insertion is to be made. This is very time-consuming and exceedingly complex in terms of programming the event to be inserted at a particular point in a large sequence of items in a list.
The normal method for this to happen is that there be a sequential scan of each item, item-by-item, step-by-step, until there is reached or achieved the proper insertion point. Thus, the performance cost of queue searching for insertion events which need to be handled at some fixed time in the future, is quite an expensive proposition. However, the queues which must be scanned sequentially are used very often for these purposes because they are simple to implement and maintain, and can reflect the linear nature of the problem to be solved in finding the correct placement point or item into which the new event is to be inserted. Additionally, such a technique is inherently slow, and thus also becomes increasingly costly, as more entries are added to the queue, and considerable time latency factors are involved in the mechanism which of must traverse through the queue in order to find the right new entrance point.
Traditionally, time events are maintained in a queue structure, and each timer event has a value associated with it. The value of the timer event determines when the event would or should happen after the previous timer event has happened.
As an example, if five events are to happen at t+3, then t+8, then t+45, then t+55, then t+56, (where “t” is current time), then as an example, the queue may be considered to look as follows:
TE(3) - - - TE(5) - - - TE(37) - - - TE(10) - - - TE(1)
Where “t” is the current time and the (X) represents the added time, for example in seconds, which indicates the event occurring just after the previous event has occurred.
In this particular operation, after one tick of time has occurred (that is to say, at t+1), then the timer queue could be represented to look as follows:
TE(2) - - - TE(5) - - - TE(37) - - - TE(10) - - - TE(1)
The difference here, is that the first item has now changed from TE(3) to now be TE(2).
With this type of scheme being used, it is seen to be very time-consuming to insert a timer event in the queue, since the timer entries need to be scanned from the “start” of the queue until the correct place is found. For example, if a New Timer Event (NTE) is to be added, for example, which is to happen after 48 ticks, then the entries of the timer queue will need to be scanned until an event is found which will happen after 48 ticks, and then the New Timer Event (NTE) needs to be inserted just prior to that event. Thus, in the above example, it would be necessary to scan step-by-step for entries.
Thus, in the above example, the timer queue after the new event insertion will now appear as shown below:
TE(2) - - - TE(5) - - - TE(37) - - - TE(4) - - - NTE(6) - - - TE(1)
Thus, the New Timer Event insertion which is TE(6) required the scanning of four previous entries.
Now, in the situation where the queue has thousands of entries, this type of operation will be seen to be very time-consuming in order to provide for a new event insertion.
The present invention involves a method for managing timer events which does not require any scan of the existing entries in the queue, and as a result, provides for an extensive speeding-up for handling the insertion of events in a queue. The new method uses the operation of the timer queue as if it were maintained as a circular queue. Here, the circular queue would have “N” permanent entries, where “N” is a chosen number, but an arbitrary one depending on the number of permanent entries or FTE fixed time entries that one would like to configure into the queue. Also, the number “N” then determines the maximum number of timer events that can be handled by this type of configuration.
For example, if the timer “tick” or “period” between events is 100 milliseconds, and “N” is 9,000, then this queue will then be capable of handling any timer event over a period of 15 minutes. Now, since 100 milliseconds is {fraction (1/10)}th of a second, and 9,000 would equate to 900 seconds, then with 60 seconds to the minute, it is seen that 900 seconds would be equivalent to 15 minutes.
SUMMARY OF THE INVENTION
The present method provides for the maintenance of a timer queue as a circular queue which has “N” permanent entries which are designated as Fixed Timer Entries (FTEs). The chosen number for the configuration, which is the number “N”, determines the maximum number of timer events that can be handled.
The method involves allocating “N” timer event entries and assigning a timer value of “1” to each of these timer events. These timer entries are linked to form a circularly linked list and the addresses of these timer entries are saved in an array which is used to access the fixed elements of the queue directly.
A current Timer Index is assigned so that this is equivalent to the current time in ticks, multiplied by the mod list “N”.
The next step involves an entry insertion which involves converting the event time to “ticks” and if the ticks are greater than “N”, then an exit is required since the system cannot handle more than “N”. The next step is to allocate a timer event entry, to assign a timer value of “0” to this entry, then to assign a handle to this entry. The index will be inserted at “Timer Index”, with the assigned value of (CURRENT_TIME_IN_TICKS+NEW_TIMER_TICKS) mod “N”. Then, there is made an insertion of this timer entry prior to the timer entry which is pointed by Timer Index within the timer Q.
REFERENCES:
patent: 5721891 (1998-02-01), Murray et al.
patent: 5740467 (1998-04-01), Chmielecki, Jr. et al.
patent: 5758137 (1998-05-01), Armstrong, Jr. et al.
patent: 6032207 (2000-02-01), Wilson
patent:
Dangi Salil
Jones Roger Andrew
Cass Nathan
Follansbee John
Kozak Alfred W.
Nguyen V. H.
Starr Mark T.
LandOfFree
System and method for optimizing insertions for timer queue... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with System and method for optimizing insertions for timer queue..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System and method for optimizing insertions for timer queue... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3188797