Scheduling storage accesses for multiple continuous media streams

• US 6,438,630 B1
• Filed: 10/06/1999
• Issued: 08/20/2002
• Est. Priority Date: 10/06/1999
• Status: Expired due to Term

• Current Assignee: Oracle America, Inc. (Oracle Corporation)
• Original Assignee: Sun Microsystems Incorporated (Oracle Corporation)
• Inventors: DeMoney, Michael A.
• Primary Examiner(s): Gaffin, Jeffrey
• Assistant Examiner(s): ELAMIN, ABDELMONIEM I
• Application Number:
  US09/413,102
• Time in Patent Office: 1,049 Days
• Field of Search: 710/56, 710/5, 709/103, 711/158, 711/114
• US Class Current: 710/56
• CPC Class Codes: H04N 21/2312 Data placement on disk arrays data placement in general G06F3/0604
• CPC Class Codes: H04N 21/2326 Scheduling disk or memory reading operations

Abstract

A system for scheduling storage accesses of multiple continuous media streams may include a plurality of media stream clients. Associated with each media stream client is one of a plurality of media stream managers. Each media stream manager maintains a ring of buffers configured to buffer media stream data between its associated media stream client and one or more storage systems. A different deadline queue may be associated with each one of the storage systems. Each deadline queue may be configured to queue buffer requests from the media stream managers. Each buffer request may include a deadline by which the buffer request must be fulfilled by the corresponding storage system. Each media stream manager may be configured so that once one of its buffers is consumed by the associated media stream client, the media stream manager submits a buffer request and deadline for that buffer to the appropriate deadline queue. Buffer requests may be ordered in each deadline queue from earliest to latest deadline. Each media stream manager may be configured to provide a guaranteed maximum media stream rate to its associated media stream client. The system may also include an admission controller configure to negotiate a maximum media stream rate with each media stream client. The admission controller may allow additional media stream clients only if negotiated maximum media stream rates can be maintained for all current media stream clients. The system may also include a bandwidth allocator that allocates bandwidth between guaranteed rate requests and non-rate-guaranteed requests.

Claims

1. A system for scheduling storage accesses of multiple continuous media streams, comprising:

a plurality of media stream clients;

a plurality of media stream managers, wherein each media stream manager is associated with a different one of said media stream clients and maintains a ring of buffers configured to buffer media stream data between its associated media stream client and one or more storage systems, wherein each media stream manager is configured to provide a guaranteed maximum media stream rate to its associated media stream client;

a different deadline queue associated with each one of said one or more storage systems;

wherein each deadline queue is configured to queue buffer requests from said media stream managers, wherein each buffer request includes a deadline by which the buffer request must be fulfilled by the corresponding storage system to meet the corresponding guaranteed maximum media stream rate, wherein each deadline is calculated as;

current_time+(N−

1)*buf_time, wherein current_time is a time reference for the system, N is the number of buffers in the ring of buffers, and buf_time is the minimum time in which the media stream client can consume one of the buffers without exceeding the guaranteed maximum media stream rate;

wherein each media stream manager is configured so that once one of its buffers is consumed by the associated media stream client, the media stream manager submits a buffer request and deadline for that buffer to the appropriate deadline queue; and

wherein buffer requests are ordered in each deadline queue from earliest to latest deadline.

2. The system as recited in claim 1, wherein each media stream manager is further configured to allow its associated media stream client to vary its media stream rate up to said guaranteed maximum media stream rate.

5. The system as recited in claim 1, wherein each buffer is equally sized to hold one block size of data, wherein data is accessed in said one or more storage systems according to said block size.

6. The system as recited in claim 1, wherein each buffer in the ring of buffers is consumed by the associated media stream client one after another in a circular order.

7. The system as recited in claim 1, wherein said one or more storage systems comprise one or more RAID systems.

3. A system for scheduling storage accesses of multiple continuous media streams, comprising:

a plurality of media stream clients;

a plurality of media stream managers, wherein each media stream manager is associated with a different one of said media stream clients and maintains a ring of buffers configured to buffer media stream data between its associated media stream client and one or more storage systems;

a different deadline queue associated with each one of said one or more storage systems;

wherein each deadline queue is configured to queue buffer requests from said media stream managers, wherein each buffer request includes a deadline by which the buffer request must be fulfilled by the corresponding storage system;

wherein each media stream manager is configured so that once one of its buffers is consumed by the associated media stream client, the media stream manager submits a buffer request and deadline for that buffer to the appropriate deadline queue;

wherein buffer requests are ordered in each deadline queue from earliest to latest deadline; and

an admission controller configured to negotiate a maximum media stream rate with each media stream client, wherein the admission controller is further configured to allow additional media stream clients only if negotiated maximum media stream rates can be maintained for all current media stream clients.

4. The system as recited in claim 3, wherein said admission controller is further configured to determine a maximum admission bandwidth by characterizing the overall system performance with a synthetic load that reflects characteristics of a typical storage load of media streams, wherein the admission controller allows additional media stream clients only if the aggregate of all negotiated maximum media stream rates does not exceed the maximum admission bandwidth.

8. A system for scheduling storage accesses of multiple continuous media streams, comprising:

a plurality of media stream clients;

a plurality of media stream managers, wherein each media stream manager is associated with a different one of said media stream clients and maintains a ring of buffers configured to buffer media stream data between its associated media stream client and one or more storage systems;

a different deadline queue associated with each one of said one or more storage systems;

wherein each deadline queue is configured to queue buffer requests from said media stream managers, wherein each buffer request includes a deadline by which the buffer request must be fulfilled by the corresponding storage system;

wherein each media stream manager is configured so that once one of its buffers is consumed by the associated media stream client, the media stream manager submits a buffer request and deadline for that buffer to the appropriate deadline queue;

wherein buffer requests are ordered in each deadline queue from earliest to latest deadline; and

wherein each ring of buffers contains a number of buffers wherein the number is chosen according to a maximum stream rate requested by the associated media stream client, wherein the number is chosen to provide just enough buffers to avoid underrun at the maximum stream rate.

9. A system for scheduling storage accesses of multiple continuous media streams, comprising:

a plurality of media stream clients;

a plurality of media stream managers, wherein each media stream manager is associated with a different one of said media stream clients and maintains a ring of buffers configured to buffer media stream data between its associated media stream client and one or more storage systems;

a different deadline queue associated with each one of said one or more storage systems;

wherein each deadline queue is configured to queue buffer requests from said media stream managers, wherein each buffer request includes a deadline by which the buffer request must be fulfilled by the corresponding storage system;

wherein each media stream manager is configured so that once one of its buffers is consumed by the associated media stream client, the media stream manager submits a buffer request and deadline for that buffer to the appropriate deadline queue;

wherein buffer requests are ordered in each deadline queue from earliest to latest deadline; and

an admission controller configured to negotiate a maximum media stream rate with each media stream client, wherein the admission controller is further configured to allow an additional media stream client only if sufficient memory is available for a ring of buffers to be established for the additional media stream client having a number of buffers just sufficient to prevent underrun at the negotiated maximum media stream rate.

10. A system for scheduling storage accesses of multiple continuous media streams, comprising:

a plurality of media stream clients;

a plurality of media stream managers, wherein each media stream manager is associated with a different one of said media stream clients and maintains a ring of buffers configured to buffer media stream data between its associated media stream client and one or more storage systems;

a different deadline queue associated with each one of said one or more storage systems;

wherein each deadline queue is configured to queue buffer requests from said media stream managers, wherein each buffer request includes a deadline by which the buffer request must be fulfilled by the corresponding storage system;

wherein each media stream manager is configured so that once one of its buffers is consumed by the associated media stream client, the media stream manager submits a buffer request and deadline for that buffer to the appropriate deadline queue;

wherein buffer requests are ordered in each deadline queue from earliest to latest deadline;

one or more non-rate-guaranteed clients; and

a bandwidth allocator configured to receive rate guaranteed requests from said deadline queues and non-rate-guaranteed requests from said non-rate-guaranteed clients, wherein said bandwidth allocator is configured to allocate a set portion of storage system bandwidth to said rate guaranteed requests and remaining bandwidth to said non-rate-guaranteed requests.

11. The system as recited in claim 10, further comprising a different priority queue associated with each one of said one or more storage systems, wherein each priority queue is configured to queue non-rate-guaranteed requests according to a priority.

12. The system as recited in claim 10, further comprising a seek reorder queue associated with each one of said one or more storage systems, wherein said rate guaranteed requests and said non-rate-guaranteed requests are migrated to said seek reorder queue by said bandwidth allocator according to said set portion of storage system bandwidth, wherein all requests are ordered in said seek reorder queue in order of the requested block physical address.

13. The system as recited in claim 12, wherein request are satisfied from said seek reorder queue in one direction of the queue until the end of the queue is reached and then the direction is reversed.

14. A method for scheduling storage accesses of multiple continuous media streams, comprising:

establishing a guaranteed maximum stream rate for each of a plurality of multimedia streams;

establishing a ring of buffers for each multimedia stream;

each multimedia stream fulfilling multimedia data requests from its associated ring of buffers;

as each buffer in one of said rings of buffers is consumed, queuing a request for that buffer in a deadline queue associated with the storage system from which the request is to be satisfied, wherein said queuing a request comprises;

calculating a deadline time indicating the latest time by which the buffer request can be fulfilled and still meet the corresponding guaranteed maximum stream rate, wherein the deadline time is calculated as current_time+(N−

1)*buf_time, wherein current_time is a time reference for the system, N is the number of buffers in the associated ring of buffers, and buf_time is the minimum time in which a media stream client can consume one of the buffers without exceeding the guaranteed maximum media stream rate;

queuing the deadline time with the request in the deadline queue; and

ordering requests in the deadline queue from earliest to latest deadline; and

for each deadline queue, issuing requests from the deadline queue to the associated storage system, wherein the request with the earliest deadline is issued first.

15. The method as recited in claim 14, wherein each buffer is equally sized to hold one block size of data, wherein data is accessed in the storage system according to the block size.

16. The method as recited in claim 14, further comprising a different media stream client associated with each ring of buffers consuming the buffers in the associated ring one after another in a circular order.

17. A method for scheduling storage accesses of multiple continuous media streams, comprising:

establishing a guaranteed maximum stream rate for each of a plurality of multimedia streams;

establishing a ring of buffers for each multimedia stream;

each multimedia stream fulfilling multimedia data requests from its associated ring of buffers;

as each buffer in one of said rings of buffers is consumed, queuing a request for that buffer in a deadline queue associated with the storage system from which the request is to be satisfied;

for each deadline queue, issuing requests from the deadline queue to the associated storage system, wherein the request with the earliest deadline is issued first;

receiving a request from a media stream client to access a media file at a stream rate up to a requested maximum stream rate; and

admitting the media stream client only if the requested maximum stream rate can be met in addition to all existing guaranteed maximum stream rates.

18. A method for scheduling storage accesses of multiple continuous media streams, comprising:

establishing a guaranteed maximum stream rate for each of a plurality of multimedia streams;

establishing a ring of buffers for each multimedia stream;

each multimedia stream fulfilling multimedia data requests from its associated ring of buffers;

as each buffer in one of said rings of buffers is consumed, queuing a request for that buffer in a deadline queue associated with the storage system from which the request is to be satisfied;

for each deadline queue, issuing requests from the deadline queue to the associated storage system, wherein the request with the earliest deadline is issued first; and

allocating a portion of storage system bandwidth to rate guaranteed media streams and the remaining bandwidth portion to non-rate-guaranteed requests.

19. The method as recited in claim 18, further comprising queuing the non-rate-guaranteed requests in a priority queue, wherein non-rate-guaranteed requests are issued from the priority queue according in order of priority and subject to the portion of storage system bandwidth allocated to non-rate-guaranteed requests.

20. The method as recited in claim 18, further comprising dynamically reallocating any unused bandwidth allocated for rate guaranteed requests to non-rate-guaranteed requests.

21. The method as recited in claim 18, further comprising dynamically reallocating any unused bandwidth allocated for non-rate-guaranteed requests to rate guaranteed requests.

22. The method as recited in claim 18, further comprising:

migrating rate guaranteed requests from said deadline queue and non-rate-guaranteed requests from said priority queue to a seek reorder queue;

ordering all requests in said seek reorder queue by the physical storage address of the location; and

issuing requests from the seek reorder queue to the storage system in one direction of the seek reorder queue until the end of the seek reorder queue is reached and then reversing the direction for issuing requests.

23. A method for scheduling storage accesses of multiple continuous media streams, comprising:

establishing a guaranteed maximum stream rate for each of a plurality of multimedia streams;

establishing a ring of buffers for each, multimedia stream, wherein said establishing a ring of buffers comprises allocating memory for a number of buffers, wherein the number of buffers is chosen according to the guaranteed maximum stream rate for the associated multimedia stream so that just enough buffers are allocated to avoid underrun at the guaranteed maximum stream rate;

each multimedia stream fulfilling multimedia data requests from its associated ring of buffers;

as each buffer in one of said rings of buffers is consumed, queuing a request for that buffer in a deadline queue associated with the storage system from which the request is to be satisfied; and

for each deadline queue, issuing requests from the deadline queue to the associated storage system, wherein the request with the earliest deadline is issued first.

24. A method for scheduling storage accesses of multiple continuous media streams, comprising:

creating a table of buffer numbers for a plurality of stream rates, wherein said creating a table comprises;

generating a number of stream simulators sufficient to consume an entire bandwidth allocated for rate guaranteed streams;

each stream simulator generating stream requests from a model buffer ring having a number of buffers;

adjusting the number of buffers in each model buffer ring up or down depending on whether or not an underrun condition occurred;

repeating said generating stream requests and said adjusting until an optimum number of buffers for each buffer ring is found that just avoids an underrun condition; and

creating said table by repeating said generating a number of stream simulators, said generating stream requests, said adjusting, and said repeating said generating stream requests, until an optimum buffer number is found for each of a plurality of stream rates;

establishing a guaranteed maximum stream rate for each of a plurality of multimedia streams;

establishing a ring of buffers for each multimedia stream;

each multimedia stream fulfilling multimedia data requests from its associated ring of buffers;

as each buffer in one of said rings of buffers is consumed, queuing a request for that buffer in a deadline queue associated with the storage system from which the request is to be satisfied; and

for each deadline queue, issuing requests from the deadline queue to the associated storage system, wherein the request with the earliest deadline is issued first.

25. The method as recited in claim 24, wherein said establishing a ring of buffers comprises allocating memory for a number of buffers, wherein the number is chosen from said table according to the guaranteed maximum stream rate.

26. A method for scheduling storage accesses of multiple continuous media streams, comprising:

establishing a guaranteed maximum stream rate for each of a plurality of multimedia streams;

establishing a ring of buffers for each multimedia stream;

each multimedia stream fulfilling multimedia data requests from its associated ring of buffers;

as each buffer in one of said rings of buffers is consumed, queuing a request for that buffer in a deadline queue associated with the storage system from which the request is to be satisfied; and

for each deadline queue, issuing requests from the deadline queue to the associated storage system, wherein the request with the earliest deadline is issued first, wherein requests issued to the associated storage system access a storage disk, wherein each request for a particular stream alternates between an inner disk zone and an outer disk zone.

27. A method for scheduling storage accesses of multiple continuous media streams, comprising:

establishing a guaranteed maximum stream rate for each of a plurality of multimedia streams;

establishing a ring of buffers for each multimedia stream;

each multimedia stream fulfilling multimedia data requests from its associated ring of buffers;

as each buffer in one of said rings of buffers is consumed, queuing a request for that buffer in a deadline queue associated with the storage system from which the request is to be satisfied;

for each deadline queue, issuing requests from the deadline queue to the associated storage system, wherein the request with the earliest deadline is issued first; and

determining a maximum storage system bandwidth, wherein said determining comprises;

creating a synthetic load of data blocks in the storage system, wherein said creating a synthetic load comprises allocating blocks randomly in inner and outer storage disk zones, wherein said allocating blocks randomly alternates between the inner and outer zones; and

determining a maximum storage bandwidth using said synthetic load.

28. The method as recited in claim 27, further comprising admitting a new multimedia stream only if a requested maximum stream rate for the new stream plus the aggregate guaranteed maximum stream rate for all current multimedia streams does not exceed the maximum storage bandwidth.

29. A method for managing a multimedia data stream, comprising:

receiving a request from a stream requester to establish a multimedia data stream to access a multimedia file stored on a storage system at a guaranteed max stream rate;

linking to the multimedia file;

creating a ring of buffers, wherein said creating a ring of buffers comprises establishing a number of buffers, wherein the number of buffers established is just enough to prevent buffer underrun at the guaranteed maximum stream rate;

initially filling said ring of buffers with multimedia data for said stream; and

after said initially filling said ring of buffers, streaming multimedia data between the multimedia file on the storage system and the multimedia stream requester.

30. The method as recited in claim 29, wherein said creating a ring of buffers comprises obtaining a predetermined block size, wherein each buffer corresponds to one block, and wherein the multimedia data is streamed between the multimedia stream requester and storage system in blocks according to said block size.

31. The method as recited in claim 29, wherein the rate of said streaming varies, but does not exceed a maximum guaranteed rate.

32. A method for managing a multimedia data stream, comprising:

receiving a request from a stream requester to establish a multimedia data stream to access a multimedia file stored on a storage system at a guaranteed max stream rate;

linking to the multimedia file;

creating a ring of buffers, wherein said creating a ring of buffers comprises establishing a number of buffers, wherein the number is selected from a predetermined table of optimum buffer ring sizes according to maximum stream rates to prevent buffer underrun at the guaranteed max steam rate;

initially filling said ring of buffers with multimedia data for said stream; and

after said initially filling said ring of buffers, streaming multimedia data between the multimedia file on the storage system and the multimedia stream requester.

33. A method for managing a multimedia data stream, comprising:

receiving a request from a stream requester to establish a multimedia data stream to access a multimedia file stored on a storage;

linking to the multimedia file;

creating a ring of buffers;

initially filling said ring of buffers with multimedia data for said stream;

after said initially filling said ring of buffers, streaming multimedia data between the multimedia file on the storage system and the multimedia stream requester, wherein said streaming multimedia data comprises;

consuming one of the buffers in said ring of buffers;

generating a request and a deadline for the just consumed buffer, wherein said deadline indicates the latest time the request must be fulfilled in order to prevent buffer underrun;

issuing the request and deadline for the just consumed buffer to a deadline queue, wherein the request is ordered in said deadline queue according to said deadline; and

consuming a next buffer in the ring of buffers and repeating said generating and said issuing for said next buffer, wherein said buffers are consumed in a circular order.

34. The method as recited in claim 33, wherein said generating a request and a deadline comprises calculating the deadline as:

current_time+(N−

1)*buf_time;

wherein current_time is a time reference, N is the number of buffers in the ring of buffers, and buf_time is the minimum time in which the multimedia stream requester can consume one of the buffers without exceeding a guaranteed maximum stream rate.