Dynamic hierarchical network resource scheduling for continuous media

• US 6,041,354 A
• Filed: 09/08/1995
• Issued: 03/21/2000
• Est. Priority Date: 09/08/1995
• Status: Expired due to Term

• Current Assignee: Nokia of America Corporation (Nokia Corporation)
• Original Assignee: Lucent Technologies, Inc. (Nokia Corporation)
• Inventors: Panagos, Euthimios, Hillyer, Bruce K., Biliris, Alexandros
• Primary Examiner(s): Asta, Frank J.
• Assistant Examiner(s): PIERCE, IVAN
• Application Number:
  US08/525,937
• Time in Patent Office: 1,656 Days
• Field of Search: 395/673, 395/200.61, 395/200.34, 395/200.56
• US Class Current: 709/226
• CPC Class Codes: G06F 2209/485 Resource constraint
• CPC Class Codes: G06F 9/4887 involving deadlines, e.g. rate based, periodic
• CPC Class Codes: H04N 21/2393 involving handling client requests scheduling or organising the servicing of application requests H04L67/60
• CPC Class Codes: H04N 21/241 Operating system [OS] processes, e.g. server setup
• CPC Class Codes: H04N 7/17336 Handling of requests in head-ends

Abstract

An apparatus and method is provided that supports continuous media for conventional networked workstations and PC'"'"'s. Described are user-level mechanisms and policies designed to give good, efficient multimedia service under the mild assumption that the operating system provides a preemptive real-time scheduling class that can be used to give CPU cycles to the multimedia processes in preference to other processes that are not time sensitive. There are no modifications to the operating system kernel and isochronous networks are not required. It suffices for an application to state that it wants to play a particular stream of a type known to the server (e.g. a file containing MPEG-1 video 320×240 pixels, 8-bit color, 30 frames per second), or for the application to specify a frame rate and an index describing the offset of each frame in a file.

Claims

1. A method of playing back continuous media data comprising the steps of:

performing job admission based on loading of a server;

performing hierarchically scheduling of a plurality of resources based on an estimate of consumption of a plurality of data streams from each of said plurality of resources with respect to available time during a single schedule cycle of a plurality of schedule cycles substantially ensuring completion of at least one of said plurality of data streams within a particular time frame of said single schedule cycle;

dynamically monitoring actual resource consumption to improve utilization of said plurality of resources with conservative admission at beginning of said single cycle and slack filling additional available time during said particular time frame of said single cycle;

degrading a first part of one of said plurality of data streams with respect to a second part of one of said plurality of data streams deemed less important according to an application specified prioritization policy of said server.

2. The method of claim 1 wherein said job admission further comprises the steps of:

trivially admitting said at least one of said plurality of data streams when said server is underloaded;

trivially rejecting said at least one of said plurality of data streams when said server is overloaded; and

conditionally admitting said at least one of said plurality of data streams when said server is in a normal load condition.

3. The method of claim 1 wherein said hierarchial scheduling further comprises the step of generating a first batch of data streams from said plurality of data streams that are to complete within said time frame of said single schedule cycle.

4. The method of claim 3 wherein said hierarchial scheduling further comprises the step of generating a plurality of waiting queues on said resources of said plurality of data streams that are not members of said first batch of data streams.

5. The method of claim 4 wherein said improving utilization of said plurality of resources by slack filling further comprises the steps of comparing actual resource consumption with predictions of said hierarchical resource scheduling and conditionally admitting a second batch of data streams from said plurality of waiting queues when said actual resource consumption is smaller.

6. The method of claim 2 wherein the step of trivially admitting said at least one data stream further comprises the steps of estimating the resource consumption and determining that said at least one data stream will fit within said slack.

7. The method of claim 1 wherein said plurality of resources includes a memory subsystem.

8. The method of claim 1 wherein said plurality of resources includes a network controller.

9. The method of claim 1 wherein said plurality of resources includes a disk controller.

10. The method of claim 1 wherein said plurality of resources includes a disk.

11. The method of claim 1 wherein said performing hierarchical scheduling is done based on a plurality of network and disk cycles.

12. The method of claim 11 wherein said plurality of cycles includes a first cycle and a second cycle, said second cycle having extra time when said first cycle finishes early.

13. The method of claim 1 wherein said specified prioritization policy increases protection from degradation of said at least one of said plurality of data streams in proportion to said plurality of schedule cycles of which said at least one of said plurality of data streams has been served.

14. A method of playing back continuous media comprising the steps of:

performing hierarchical scheduling of a plurality of resources based on estimating the resource consumption and determining that at least one data stream will fit within a schedule cycle among a collection of data streams for each of said plurality of resources;

dynamically monitoring actual resource consumption to improve utilization of said plurality of resources with conservative admission at beginning of said single cycle and by comparing actual resource consumption with predictions of hierarchical resource scheduling and serving additional data streams from said collection of data streams from a plurality of waiting queues when said actual resource consumption is smaller as a means of slack filling any available time during said schedule cycle; and

degrading parts of said at least one data stream deemed less important than remaining data streams of said collection of data streams according to an application specified prioritization policy.

15. An apparatus to play back continuous media comprising:

schedule means for performing hierarchical scheduling of a plurality of resources based on estimating resource consumption for determining that at least one data stream will fit within a schedule cycle of a plurality of schedule cycles among a collection of data streams for each of said plurality of resources;

means for dynamically monitoring actual resource consumption to improve utilization of said plurality of resources with conservative admission at beginning of said single cycle and for comparing actual resource consumption with predictions of hierarchical resource scheduling and serving additional data streams from said collection of data streams from a plurality of waiting queues when said actual resource consumption is smaller as a means of slack filling any available time during said schedule cycle; and

degrading means for degrading parts of said at least one data stream not fully served and deemed less important than remaining data streams of said collection of data streams according to an application specified prioritization policy.

16. The apparatus of claim 15 wherein said specified prioritization policy increases protection from degradation of said at least one data stream in proportion to said plurality of schedule cycles of which said at least one data stream has been served.