Electrical computers and digital processing systems: virtual mac – Task management or control – Process scheduling
Reexamination Certificate
1999-12-30
2004-05-18
Srivastava, Vivek (Department: 2611)
Electrical computers and digital processing systems: virtual mac
Task management or control
Process scheduling
C718S102000, C725S097000, C725S093000, C725S096000, C725S101000, C725S116000
Reexamination Certificate
active
06738972
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The invention relates generally to scheduling methods and more particularly to methods for scheduling a flow of information by selecting and scheduling portions of modules having the highest priorities.
2. Description of the Related Art
Interactive television systems are capable of providing a wide variety of services to viewers. These services may include delivery of television programming, interactive applications and the like. Interactive television systems are also capable of registering viewer responses to the audio and video information presented by the system. Interactive television systems may therefore be useful for a number of marketing, entertainment and educational purposes.
In an interactive television system, a broadcast service provider generates an interactive television signal for transmission to a viewer's television. The interactive television signal may include an interactive portion consisting of application code or control information, as well as an audio-video portion consisting of a television program. The broadcast service provider combines the audio-video and interactive portions into a single signal for transmission to a receiver connected to the user's television. The signal is generally compressed prior to transmission and is transmitted through typical broadcast channels, such as cable television (CATV) lines or direct satellite transmission systems.
The signal transmitted by the broadcast service provider is typically received by a set-top box coupled to a viewer's television. The set-top box separates the interactive portion from the audio-video portion and decompresses the respective portions of the signal. The set-top box may then execute received applications and pass received audio-video information to the television. The set-top box may also combine the audio-video information with interactive graphics or audio generated by the interactive application prior to transmitting the information to the television. The interactive graphics and audio may present additional information to the viewer, or may prompt the viewer for input. The set-top box may provide viewer input or other information to the broadcast service provider via a modem connection or another return path.
The interactive applications, television programming and other information transmitted by the interactive television system may consist of one or more information modules. These modules are normally formatted into packets, each of which contains a portion of the modules' information. The packets are transmitted to the set-top box, where they are reconstructed into the modules. The packets of a module may be transmitted consecutively, or they may be interspersed with packets containing portions of other modules.
The simple way of scheduling transmission of a module is to calculate (approximately) the time required to deliver the entire module and then subtract this from the scheduled delivery time. The duration of the transmission can be determined by dividing the size of the module by the bit rate at which its packets will be transmitted. This method for scheduling a module requires that the broadcast channel be reserved for this particular module and that all of the module's packets be transmitted consecutively. This may present considerable difficulty in scheduling the potentially large number of modules which may need to be transmitted by the system. An improved mechanism for scheduling delivery of the modules would therefore be desirable.
SUMMARY OF THE INVENTION
Broadly speaking, the invention comprises a system and method for scheduling the delivery of information modules. A scheduling algorithm is employed to prioritize the modules and to select a module with the highest priority to be scheduled. The priority of each module is based on corresponding scheduling information. Because this scheduling information may change as the modules or portions thereof are scheduled, the information must periodically be updated and the priorities of the modules recalculated. When a module is selected for scheduling, the amount of time which can elapse before recalculation is necessary is determined and only a corresponding portion of the selected module is scheduled. After the module information is updated to reflect the scheduling of the module and the resulting priorities are recalculated, a new module is selected for further scheduling.
One embodiment comprises a method for scheduling the flow of modules in an information transmission system. A list of modules to be transmitted is compiled. The list contains a minimum beginning time, a maximum beginning time and a remaining duration for each of the modules. The list is examined and any minimum beginning time which is prior to a current time is set to the current time. The list is then ordered, the first according to the minimum beginning times of the modules, and then according to the maximum beginning times of the modules. A module which is available for transmission (i.e., one which has a minimum beginning time prior to, or equal to, the current time) and which has the earliest maximum beginning time is then selected from the top of the list. The maximum portion of the selected module which can be transmitted before the order of the list must be recalculated is then scheduled. The current time is advanced by an amount equivalent to the scheduled portion of the module and the information corresponding to each of the modules is recalculated, if necessary (i.e., the length of the scheduled portion is subtracted from the maximum beginning time and duration of the scheduled module, and the minimum beginning time of each module is updated to the current time.) The list is then reordered according to the updated information for the modules and the steps above are repeated.
One embodiment comprises a computer readable storage medium which embodies the foregoing method. The storage medium may comprise floppy disks, magnetic tapes, optical disks, RAM, ROM, flash memory, etc. The storage media and has program instructions recorded therein for controlling the operation of a computer system. The program instructions are executable by the computer system to direct the computer system to examine the module information, order the modules, select the highest priority module, schedule at least portion of this module and recalculate the module information. These steps are repeated until the modules are completely scheduled.
One embodiment comprises a scheduler in an interactive television system for constructing a flow of modules. The scheduler is implemented in a broadcast station and is configured to determine the size and order in which portions of the modules will be broadcast to subscribers. The scheduler is configured to examine scheduling information for each module and to prioritize the modules according to this information. The information includes a minimum beginning time, a maximum beginning time and a duration for each module. The scheduler examines the minimum beginning times and, for each one which is prior to the current time, sets that one equal to the current time. The scheduler then lists the modules, in ascending order, according to their minimum beginning times. Modules which have the same minimum beginning time are ordered according to increasing maximum beginning times. The first module in the list is then selected to be scheduled. The scheduler determines how much of the module can be transmitted before the order of the modules (i.e., their priorities) must be recalculated. The scheduler schedules a corresponding portion of the module for transmission. The information for the modules is then updated, the priorities of the modules are recalculated and the next module (or portion thereof) is selected to be scheduled.
It should be noted that many additional embodiments of the present system and method will be apparent to persons of ordinary skill in the art of the invention. The embodiments disclosed herein are intended to be illustrative rather than li
Rousseau Jerome
Willard Pierre
Chung Jason
Meyertons Hood Kivlin Kowert & Goetzel P.C.
OpenTV, Inc.
Rankin Rory D.
Srivastava Vivek
LandOfFree
Method for flow scheduling does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method for flow scheduling, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for flow scheduling will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3241129