US6438630B1
Expired / Lapsed
US
⏱️ 0.0 years remaining
Scheduling storage accesses for multiple continuous media streams
Assignee: Oracle America Inc
•
Filing: 1999-10-06
•
Granted: 2002-08-20
•
Expires: 2019-10-06
Abstract
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.
Inventors
- 👤 Michael A. DeMoney
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-01 16:11
CPC Classifications
H; H04; H04N; H04N21/00; H04N21/20; H04N21/23; H04N21/231; H04N21/2312; H04N21/232; H04N21/2326
Claims Analysis
Total Claims: 49
Claim 1
Independent Claim
252 words
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.
Claim 2
Independent Claim
252 words
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.
Claim 3
Dependent Claim
37 words
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.
Claim 4
Independent Claim
214 words
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.
Claim 5
Independent Claim
214 words
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.
Claim 6
Dependent Claim
69 words
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.
Claim 7
Dependent Claim
37 words
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.
Claim 8
Dependent Claim
31 words
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.
Claim 9
Dependent Claim
21 words
The system as recited in claim 1 , wherein said one or more storage systems comprise one or more RAID systems.
Claim 10
Independent Claim
215 words
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.
Claim 11
Independent Claim
215 words
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.
Claim 12
Independent Claim
236 words
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.
Claim 13
Independent Claim
236 words
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.
Claim 14
Independent Claim
221 words
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.
Claim 15
Independent Claim
221 words
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.
Claim 16
Dependent Claim
39 words
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.
Claim 17
Dependent Claim
72 words
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.
Claim 18
Dependent Claim
37 words
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.
Claim 19
Independent Claim
218 words
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.
Claim 20
Independent Claim
218 words
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.
Claim 21
Dependent Claim
34 words
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.
Claim 22
Dependent Claim
35 words
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.
Claim 23
Independent Claim
157 words
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.
Claim 24
Independent Claim
157 words
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.
Claim 25
Independent Claim
129 words
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.
Claim 26
Independent Claim
129 words
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.
Claim 27
Dependent Claim
45 words
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.
Claim 28
Dependent Claim
23 words
The method as recited in claim 18 , further comprising dynamically reallocating any unused bandwidth allocated for rate guaranteed requests to non-rate-guaranteed requests.
Claim 29
Dependent Claim
23 words
The method as recited in claim 18 , further comprising dynamically reallocating any unused bandwidth allocated for non-rate-guaranteed requests to rate guaranteed requests.
Claim 30
Dependent Claim
84 words
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.
Claim 31
Independent Claim
159 words
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.
Claim 32
Independent Claim
159 words
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.
Claim 33
Independent Claim
249 words
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.
Claim 34
Independent Claim
249 words
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.
Claim 35
Dependent Claim
38 words
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.
Claim 36
Independent Claim
139 words
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.
Claim 37
Independent Claim
139 words
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.
Claim 38
Independent Claim
169 words
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.
Claim 39
Independent Claim
169 words
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.
Claim 40
Dependent Claim
45 words
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.
Claim 41
Independent Claim
117 words
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.
Claim 42
Independent Claim
117 words
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.
Claim 43
Dependent Claim
50 words
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.
Claim 44
Dependent Claim
23 words
The method as recited in claim 29 , wherein the rate of said streaming varies, but does not exceed a maximum guaranteed rate.
Claim 45
Independent Claim
127 words
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.
Claim 46
Independent Claim
127 words
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.
Claim 47
Independent Claim
179 words
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.
Claim 48
Independent Claim
179 words
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.
Claim 49
Dependent Claim
64 words
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.
References Cited (Backward Citations)
US5644786A
Cited
US5303347A
Cited
EP0625858A1
Cited
US5526356A
Cited
US5802394A
Cited
US5805821A
Cited
EP0701370A1
Cited
US5761692A
Cited
US6085234A
Cited
EP0716370A2
Cited
US5721956A
Cited
US5758076A
Cited
US5787482A
Cited
EP0757310A2
Cited
EP0766473A2
Cited
US5933603A
Cited
US5708632A
Cited
US6317775B1
Cited
US5944792A
Cited
US5928327A
Cited
US5881245A
Cited
US6021464A
Cited
US5926649A
Cited
WO1998028915A2
Cited
US6138221A
Cited
US6026452A
Cited
US6205475B1
Cited
US6292834B1
Cited
US6253248B1
Cited
WO1999015953A1
Cited
US6240094B1
Cited
US6192029B1
Cited
US6023720A
Cited
US6157963A
Cited
US6243761B1
Cited
US6067107A
Cited
US6304297B1
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2005-08-19 | 2006-02-18 | 2006-08-20 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2009-08-19 | 2010-02-18 | 2010-08-20 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2013-08-19 | 2014-02-18 | 2014-08-20 | $7700.00 | Window Closed / Lapsed |