Method and apparatus for the enumeration of sets of concurrently scheduled events

• US 6,901,592 B2
• Filed: 11/27/2001
• Issued: 05/31/2005
• Est. Priority Date: 11/27/2000
• Status: Active Grant

• Current Assignee: Ericsson AB (Telefonaktiebolaget LM Ericsson)
• Original Assignee: Redback Networks Inc. (Telefonaktiebolaget LM Ericsson)
• Inventors: Robinson, Gary, Westfall, Ronald, Mar, Aaron
• Primary Examiner(s): An, Meng-Al T.
• Assistant Examiner(s): Hoang, Phuong N.
• Application Number:
  US09/995,285
• Publication Number:
  US 20020078236A1
• Time in Patent Office: 1,281 Days
• Field of Search: 718/102, 719/318, 370/232, 709223-224
• US Class Current: 718/102
• CPC Class Codes: H04L 67/61 taking into account QoS or priority requirements
• CPC Class Codes: H04L 67/62 Establishing a time schedule for servicing the requests
• CPC Class Codes: H04L 69/329 in the application layer [OSI layer 7]
• CPC Class Codes: H04L 9/40 Network security protocols

Abstract

A method for enumerating sets of concurrent events handles single-shot events and recurring events. The method involves creating a data structure having records for time periods. The time periods begin and end on overall start and end times of scheduled events. In preferred embodiments the method creates the data structure by collapsing together master schedules for a plurality of resources. The method may create the master schedules by collapsing together mini-schedules of different priorities. The method can produce a minimal list of sets of concurrent events that will occur according to a universal master schedule in a form suitable for processing by an automatic validation system.

Claims

1. A computer implemented method for enumerating sets of concurrently scheduled events for automatic validation, the method comprising, in a programmed computer system:

a) providing a universal master schedule comprising a plurality of time period data records (TPDRs) each having a start time and an end time, at least some of the TPDRs comprising references to events, each event having an overall start time and an overall end time, the events including recurring events each having a period;

b) retrieving a TPDR from the universal master schedule;

c) establishing a time limit for the TPDR;

d) performing a time-based iteration to identify sets of concurrent events by;

1) establishing the start time of the TPDR as a selected time;

2) identifying a set of zero or more events occurring at the selected time;

3) creating a record of the set of zero or more events occurring at the selected time;

4) identifying a new selected time corresponding to a next time when an event referenced by the TPDR could start or stop; and

,

5) repeating actions (2) to (4) until the new selected time is in excess of the time limit; and

,

e) performing actions (b) through (d) for each TPDR in the universal master schedule.

2. The method of claim 1 wherein the time limit is a lesser one of a least common multiple of the periods of any recurring events reference by the TPDR and a length of the TPDR.

3. The method of claim 1 wherein the events comprise single-shot events and the method comprises determining whether all events associated with a TPDR are single-shot events and, if so, recording the set of single-shot events associated with the TPDR as a set of concurrent events for validation.

4. The method of claim 1 wherein providing the universal master schedule comprises:

a) providing a plurality of master schedule data structures, each master schedule data structure corresponding to a resource and comprising one or more TPDRs each associated with a time period;

b) collapsing the plurality of master schedule data structures into the universal master schedule data structure by;

1) providing an initial universal master schedule data structure comprising at least one TPDR;

2) selecting one of the TPDRs from one of the master schedule data structures as a current TPDR;

3) if necessary, modifying the universal master schedule data structure so that the start time of the current TPDR corresponds to the end time of one TPDR of the universal master schedule data structure and the start time of another TPDR of the universal master schedule data structure and the end time of the current TPDR corresponds to the end time of one TPDR of the universal master schedule data structure and the start time of another TPDR of the universal master schedule data structure;

4) in the universal master schedule data structure, associating each TPDR which has a start time greater or equal to the start time of the current TPDR and a finish time less than or equal to the finish time of the current TPDR with the events referenced by the current TPDR; and

,

5) repeating actions (2) through (4) for the remaining TPDRs of the master schedule data structures.

5. The method of claim 4 wherein modifying the universal master schedule data structure comprises, in either order:

locating a TPDR in the universal master schedule data structure for which the associated time period includes the start time of the current TPDR and, if the start time of the current TPDR is after the start time of the located TPDR, replacing the located TPDR in the universal master data structure with first and second altered TPDRs which differ from the located TPDR in that the end time of the first altered TPDR and the start time of the second altered TPDR are set to the start time of the current TPDR; and

, locating a TPDR in the universal master schedule data structure for which the associated time period includes the end time of the current TPDR and, if the end time of the current TPDR is after the start time of the located TPDR, replacing the located TPDR in the universal master data structure with first and second altered TPDRs which differ from the located TPDR in that the end time of the first altered TPDR and the start time of the second altered TPDR are set to the end time of the current TPDR.

6. The method of claim 4 wherein the initial universal master schedule data structure comprises a selected one of the master schedule data structures.

7. The method of claim 4 wherein providing one or more of the master schedules comprises:

a) providing a plurality of mini-schedule data structures, each mini-schedule data structure having a priority, corresponding to a resource and comprising one or more TPDRs each associated with a time period;

b) collapsing the plurality of mini-schedule data structures into the master schedule data structure by;

1) providing an initial master schedule data structure comprising at least one TPDR and selecting a lowest priority one of the mini-schedules as a current mini-schedule;

2) selecting one of the TPDRs from the current mini-schedule as a current TPDR;

3) if necessary, modifying the master schedule data structure so that the start time of the current TPDR corresponds to the end time of one TPDR of the universal master schedule data structure and the start time of another TPDR of the universal master schedule data structure—

and the end time of the current TPDR corresponds to the end time of one TPDR of the universal master schedule data structure and the start time of another TPDR of the universal master schedule data structure;

4) in the master schedule data structure, associating each TPDR which has a start time greater or equal to the start time of the current TPDR and a finish time less than or equal to the finish time of the current TPDR with the events referenced by the current TPDR;

5) repeating actions (2) through (4) for the remaining TPDRs of the current mini-schedule; and

,

6) repeating actions (2) through (5) for each of the mini-schedules in priority order.

8. The method of claim 7 wherein modifying the master schedule data structure comprises in either order:

locating a TPDR in the master schedule data structure for which the associated time period includes the start time of the current TPDR and, if the start time of the current TPDR is after the start time of the located TPDR, replacing the located TPDR in the master data structure with first and second altered TPDRs which differ from the located TPDR in that the end time of the first altered TPDR and the start time of the second altered TPDR are set to the start time of the current TPDR; and

,

locating a TPDR in the master schedule data structure for which the associated time period includes the end time of the current TPDR and, if the end time of the current TPDR is after the start time of the located TPDR, replacing the located TPDR in the master data structure with first and second altered TPDRs which differ from the located TPDR in that the end time of the first altered TPDR and the start time of the second altered TPDR are set to the end time of the current TPDR.

9. The method of claim 7 wherein, in collapsing the plurality of mini-schedules, associating a TPDR with the events referenced by the current TPDR comprises, if the current TPDR is associated with a single-shot event, replacing any references to events referenced by the TPDR with a reference to the single-shot event.

10. The method of claim 9 wherein, in collapsing the plurality of mini-schedules, associating a TPDR with the events referenced by the current TPDR comprises, if the current TPDR is associated with one or more recurring events, adding references to the one or more recurring events to the TPDR.

11. The method of claim 1 wherein creating a record of the set of zero or more events comprises providing a bit vector having one bit for each of a number of possible events and setting a bit in the bit vector corresponding to each of the zero or more events.

12. The method of claim 11 wherein creating a record of the set of zero or more events comprises checking a bit vector repository to determine if the bit vector is the same as any bit vector already stored in the bit vector repository and, if not, storing the bit vector in the bit vector repository.

13. The method of claim 1 wherein the events each comprise enabling a specific QoS policy on a data communication network.

14. The method of claim 1 wherein the universal master schedule data structure comprises a B-tree.

15. The method of claim 1 wherein the universal master schedule data structure comprises a skip list.

16. Apparatus for enumerating sets of concurrently scheduled events, the apparatus comprising:

a) a first means for collapsing a plurality of mini-schedules into a master schedule;

b) a second means for collapsing a plurality of master schedules into a universal master schedule, the second means connected to receive a plurality of master schedules generated by the first means; and

,

c) a third means for extracting a plurality of sets of concurrent events, the third means connected to receive a universal master schedule from the second means and to store a data record containing information identifying sets of concurrent events scheduled in the universal master schedule, wherein the third means comprises means for performing a time-based iteration comprising,

a) means for establishing a start time of a time period data record (TPDR) as a selected time;

b) means for identifying a set of zero or more events occuring at the selected time;

c) means for creating a record of the set of zero or more events occuring at the selected time;

d) means for identifying a new selected time corresponding to a next time when an event referenced by the TPDR could start or stop; and

,

e) means for repeating actions (b) to (d) until the new selected time is in excess of a time limit of the TPDR.

17. The apparatus of claim 16 comprising means for determining whether all events in a set of concurrent events are single-shot.

18. A computer readable medium containing instructions which, when executed by a processor, cause the processor to perform operations comprising:

a) providing a universal master schedule comprising a plurality of time period data records (TPDRs) each having a start time and an end time, at least some of the TPDRs comprising references to events, each event having an overall start time and an overall end time, the events including recurring events each having a period;

b) retrieving a TPDR from the universal master schedule;

c) establishing a time limit for the TPDR;

c) performing a time-based iteration to identify sets of concurrent events by;

1) establishing the start time of the TPDR as a selected time;

2) identifying a set of zero or more events occurring at the selected time;

3) creating a record of the set of zero or more events occurring at the selected time;

4) identifying a new selected time corresponding to a next time when an event referenced by the TPDR could start or stop; and

,

5) repeating action (2) to (4) until the new selected time is in excess of the time limit; and

,

e) performing actions (b) through (d) for each TPDR in the universal master schedule.

19. The computer readable medium of claim 18 wherein the time limit is a lesser one of a least common multiple of the periods of any recurring events reference by the TPDR and a length of the TPDR.

20. The computer readable medium of claim 18 wherein the events comprise single-shot events and the method comprises determining whether all events associated with a TPDR are single-shot events and, if so, recording the set of single-shot events associated with the TPDR as a set of concurrent events for validation.

21. The computer readable medium of claim 18 wherein providing the universal master schedule comprises:

a) providing a plurality of master schedule data structures, each master schedule data structure corresponding to a resource and comprising one or more TPDRs each associated with a time period;

b) collapsing the plurality of master schedule data structures into the universal master schedule data structure by;

1) providing an initial universal master schedule data structure comprising at least one TPDR;

2) selecting one of the TPDRs from one of the master schedule data structures as a current TPDR;

3) if necessary, modifying the universal master schedule data structure so that the start time of the current TPDR corresponds to the end time of one TPDR of the universal master schedule data structure and the start time of another TPDR of the universal master schedule data structure and the end time of the current TPDR corresponds to the end time of one TPDR of the universal master schedule data structure and the start time of another TPDR of the universal master schedule data structure;

4) in the universal master schedule data structure, associating each TPDR which has a start time greater or equal to the start time of the current TPDR and a finish time less than or equal to the finish time of the current TPDR with the events referenced by the current TPDR; and

,

5) repeating actions (2) through (4) for the remaining TPDRs of the master schedule data structures.

22. The computer readable medium of claim 21 wherein modifying the universal master schedule data structure comprises, in either order:

locating a TPDR in the universal master schedule data structure for which the associated time period includes the start time of the current TPDR and, if the start time of the current TPDR is after the start time of the located TPDR, replacing the located TPDR in the universal master data structure with first and second altered TPDRs which differ from the located TPDR in that the end time of the first altered TPDR and the start time of the second altered TPDR are set to the start time of the current TPDR, and, locating a TPDR in the universal master schedule data structure for which associated time period includes the end time of the current TPDR and, if the end time of the current TPDR is after the start time of the located TPDR, replacing the located TPDR in the universal master data structure with first and second altered TPDRs which differ from the located TPDR in that the end time of the first altered TPDR and the start time of the second altered TPDR are set to the end time of the current TPDR.

23. The computer readable medium of claim 18 wherein the events each comprise enabling a specific QoS policy on a data communication network.