Method for flow scheduling

• US 6,738,972 B1
• Filed: 12/30/1999
• Issued: 05/18/2004
• Est. Priority Date: 12/30/1999
• Status: Expired due to Term

• Current Assignee: OpenTV, Inc. (Kudelski SA)
• Original Assignee: OpenTV, Inc. (Kudelski SA)
• Inventors: Willard, Pierre, Rousseau, Jerome
• Primary Examiner(s): Srivastava, Vivek
• Assistant Examiner(s): Chung, Jason
• Application Number:
  US09/476,722
• Time in Patent Office: 1,601 Days
• Field of Search: G06/F.900, 370/395.4, 370/395.42, 725/97, 725/93, 725/96, 725/101, 725/116, 709/103, 709/102, 718/102, 718/103
• US Class Current: 718/103
• CPC Class Codes: H04N 21/235 Processing of additional data, e.g. scrambling of additional data or processing content descriptors
• CPC Class Codes: H04N 21/262 Content or additional data distribution scheduling, e.g. sending additional data at off-peak times, updating software modules, calculating the carousel transmission frequency, delaying a video stream transmission, generating play-lists scheduling strategies for dispatcher in multiprogramming arrangements G06F9/4881; arrangements for scheduling broadcast services or broadcast-related services H04H60/06; flow control in packet networks H04L47/10; establishing a time schedule or organising the servicing of application requests H04L67/62
• CPC Class Codes: H04N 21/26233 involving content or additional data duration or size, e.g. length of a movie, size of an executable file
• CPC Class Codes: H04N 21/435 Processing of additional data, e.g. decrypting of additional data, reconstructing software from modules extracted from the transport stream
• CPC Class Codes: H04N 21/8166 involving executable data, e.g. software arrangements for executing specific programs G06F9/44; broadcasting computer programmes in broadcast systems H04H20/91; involving the movement of software or configuration parameters H04L67/34
• CPC Class Codes: H04N 7/165 Centralised control of user terminal subsequent to an upstream request signal H04N7/17345; Registering at central by two-way working H04N7/17309

Abstract

A system and method implemented in an interactive television system for scheduling delivery of modules of interactive television applications from a broadcast station to a receiving station. In one embodiment, a list of modules and corresponding start times, end times and durations is provided. Minimum beginning times and maximum beginning times are determined for each of the modules. The modules in the list are prioritized, first according to minimum beginning times and then according to maximum beginning times. A module having the earliest maximum beginning time is selected from those modules for which the minimum beginning time is equal or prior to a current time. A portion of the selected module is scheduled. After a portion of a module is scheduled, the information in the module list is updated, the modules in the list are re-prioritized, and another module is selected for scheduling. This is repeated until all of the modules have been scheduled.

Claims

1. A method for scheduling the flow of modules in an information transmission system, wherein said method comprises:

a processor examining a list of module entries stored in a memory, each said module entry having a minimum beginning time, a maximum beginning time and a remaining duration; and

for each said module entry, said processor;

setting said minimum beginning time to a current time if said minimum beginning time is prior to said current time;

ordering said list of module entries by earliest minimum beginning time and, within module entries having identical minimum beginning times, ordering by earliest maximum beginning time;

selecting a first entry in said list of module entries;

scheduling a portion of said first entry to be scheduled, wherein scheduling said portion comprises determining a time period by taking the smaller of;

the difference between said current time and an earliest minimum beginning time of ones of said module entries having minimum beginning times later than said current time; and

the difference between said maximum beginning time of said first module entry and the earliest maximum beginning time of ones of said module entries having minimum beginning times less than or equal to said current time;

subtracting said portion from said remaining duration of said first entry;

adding said portion to said maximum beginning time of said first entry; and

adding said portion to said current time.

2. The method of claim 1 wherein scheduling a portion of said first entry to be scheduled comprises determining a time period by subtracting an earliest maximum beginning time of said plurality of module entries from said current time and scheduling a maximum portion of said first entry which can be transmitted in said time period.

3. A method for scheduling the flow of modules in an information transmission system, said method comprising:

providing in a memory a plurality of module entries, wherein each said module entry includes a minimum beginning time and a maximum beginning time; and

a processor;

selecting one of said plurality of module entries from a first group of said plurality of module entries, wherein said minimum beginning time of said one of said plurality of module entries in said first group is less than or equip to a current time, and wherein said maximum beginning time of said selected one of said plurality of module entries is no more than said maximum beginning time of the remainder of said module entries in said first group; and

scheduling at least a portion of a module corresponding to said selected one of said plurality of module entries; and

calculating said portion of said module by taking the smaller of;

the difference between a current time and an earliest minimum beginning time of ones of said plurality of module entries having minimum beginning times later than said current time; and

the difference between said maximum beginning time of said selected module entry and the earliest maximum beginning time of ones of said plurality of module entries having minimum beginning times earlier than or equal to said current time.

4. The method of claim 3 further comprising recalculating said maximum beginning time of said selected one of said plurality of module entries and repeating said selecting.

5. The method of claim 3 wherein said selecting comprises:

if any of said plurality of module entries has a minimum beginning time less than a current time, setting said minimum beginning time to said current time;

providing a list of said plurality of module entries;

ordering skid list, first according to said minimum beginning time, and second according to said maximum beginning time; and

selecting the first of said plurality of module entries in said list.

6. The method of claim 3 wherein said minimum beginning time for each module entry is initially set to a start time identified for said each module entry.

7. The method of claim 3 further comprising transmitting said portion of said selected one of said plurality of nodule entries.

8. The method of claim 3 presenting an indication of an error if, for any of said plurality of module entries, a duration of said any module entry is greater than an end time of said any module entry minus said current time.

9. The method of claim 3 further comprising calculating said portion of said module by subtracting an earliest maximum beginning time of said plurality of module entries from a current time.

10. The method of claim 3, further comprising

presenting an indication of an error if, for any of said plurality of module entries, a duration of said any module entry is greater than an end time of said any module entry minus said current time.

11. The method of claim 3, further comprising calculating said portion of said module by subtracting an earliest maximum beginning time of said plurality of module entries from a current time.

12. The method of claim 3 wherein said maximum beginning time for each module entry is initially determined by subtracting a duration of said each module entry from an end time for said each module entry.

13. A scheduler comprising:

a processor; and

a first memory coupled to said processor and configured to store a plurality of module entries, each said module entry having a corresponding minimum beginning time, a maximum beginning time, an ending time and a duration;

wherein said processor is configured to examine said module entries, to select a first one of said module entries and to schedule said first one of said module entries, wherein said first one of said module entries has a highest priority, wherein said highest priority indicates that said first one of said module entries has said minimum beginning time less than or equal to a current time and has an earliest maximum beginning time among said module entries having said minimum beginning time prior or equal to said current time;

wherein said processor is further configured to determine a portion of a module corresponding to said selected module entry such that, after scheduling of said portion of said module, a second one of said module entries has said highest priority.

14. The scheduler of claim 13 wherein said processor is configured to periodically re-order said module entries in said memory.

15. The scheduler of claim 14 wherein said processor is configured to re-order said module entries in said memory when scheduling of said first one of said module entries causes one or more priorities associated with said plurality of module entries to change.

16. The scheduler of claim 13 wherein said scheduler is configured to generate a schedule and to store said schedule in a second memory.

17. The scheduler of claim 13 wherein said scheduler is coupled to one or more module sources and is configured to select modules provided by said module sources to a broadcast transmitter.