US5802394A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method for accessing one or more streams in a video storage system using multiple queues and maintaining continuity thereof
Assignee: Starlight Networks Inc
•
Filing: 1994-06-06
•
Granted: 1998-09-01
•
Expires: 2014-06-06
Abstract
Abstract A method is disclosed for interfacing a video storage system, such as a disk array, and a video stream application executing on a computer network or stand-alone system. The interface provides a method for storing video stream data by allocating storage space in units of stripes and for accessing the data in units of fixed length segments, wherein each stripe includes one fixed length segment from each disk of the array. The interface also queues submitted I/O transaction requests so that I/O transactions requested on a current I/O cycle i are not performed until the next I/O cycle i+1. The I/O transactions thus queued are performed in an order which permits a maximum number of I/O transactions to be performed each I/O cycle, regardless of the order in which they were submitted. In addition, the interface also queues the submitted I/O transaction requests so that the completion of an I/O transaction on a current I/O cycle i is not returned until the next I/O cycle i+1. The completions of the I/O transactions thus queued are returned in the order they were submitted regardless of the order in which they were performed. Furthermore, the interface provides a state machine which controls the amount of data accessed each I/O cycle for a corresponding stream. The state machine permits no more than a particular allotted amount of data to be accessed each I/O cycle, wherein the allotted amount of data is selected according to the bandwidth requirement of the corresponding stream.
Inventors
- 👤 Randall B. Baird
- 👤 Martin J. McFadden
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-08 13:34
CPC Classifications
H; H04; H04N; H04N21/00; H04N21/20; H04N21/21; G; G06; G06F; G06F3/00; G06F3/06; G06F3/0601; G06F3/0602; G06F3/061; G06F3/0613; G06F3/0628; G06F3/0655; G06F3/0659; G06F3/0668; G06F3/0671; G06F3/0683; G06F3/0689; H04N21/23; G11; G11B; G11B20/00; G11B20/10; G11B20/12; G11B20/1217; G11B27/00; G11B27/10; G11B27/102; G11B27/105
Claims Analysis
Total Claims: 30
Claim 1
Independent Claim
124 words
A method for accessing data of one or more streams in a disk array of at least one disk comprising the steps of: (a) enqueuing one or more command descriptors for performing I/O transactions, corresponding to each request that issued during a current cycle i, into an inactive periodic queue, during said cycle i, (b) delaying performing said I/O transactions of said command descriptors in said inactive periodic queue until a subsequent cycle i+1, (c) at a beginning of said cycle i+1, placing said command descriptors in said inactive periodic queue into an active periodic queue, wherein during each cycle, I/O transactions are performed for each command descriptor in said active periodic queue, but not performed for command descriptors in said inactive periodic queue.
Claim 2
Independent Claim
124 words
A method for accessing data of one or more streams in a disk array of at least one disk comprising the steps of: (a) enqueuing one or more command descriptors for performing I/O transactions, corresponding to each request that issued during a current cycle i, into an inactive periodic queue, during said cycle i, (b) delaying performing said I/O transactions of said command descriptors in said inactive periodic queue until a subsequent cycle i+1, (c) at a beginning of said cycle i+1, placing said command descriptors in said inactive periodic queue into an active periodic queue, wherein during each cycle, I/O transactions are performed for each command descriptor in said active periodic queue, but not performed for command descriptors in said inactive periodic queue.
Claim 3
Dependent Claim
93 words
The method of claim 1 further comprising, prior to step (a), the steps of: (d) during said cycle i, enqueuing an I/O descriptor for each I/O transaction requested during said cycle i into a submit pending queue, (e) at said beginning of said cycle i+1: (e1) dequeuing each of said I/O descriptors from said submit pending queue and enqueuing each dequeued I/O descriptor into a submitted I/O transaction queue associated with the stream on which said I/O transaction of said I/O descriptor corresponds, (e2) for each of said I/O descriptors, performing steps (a)-(c).
Claim 4
Dependent Claim
41 words
The method of claim 2 further comprising, prior to said step (d), the steps of: (f) opening a chunk assigned to a particular stream on which one or more I/O transactions are to be performed and allocating resources for said chunk.
Claim 5
Dependent Claim
69 words
The method of claim 3 further comprising the steps of: (f1) allocating bandwidth for transmitting data read or written during each I/O transaction performed on said particular stream, (f2) generating an open descriptor for said particular stream including a submitted I/O transaction queue for storing I/O descriptors of submitted pending I/O transaction requests, and (f3) generating a completion context in which command descriptors for completed I/O transactions are enqueued.
Claim 6
Dependent Claim
38 words
The method of claim 4 further comprising the steps of: (g) if said chunk is closed but a second chunk is specified to be opened immediately thereafter, assigning said resources allocated to said chunk to said second chunk.
Claim 7
Dependent Claim
100 words
The method of claim 1 further comprising the steps of: (d) prior to said cycle i+1, ordering each command descriptor in said inactive periodic queue to increase the number of I/O transactions that can be performed during said cycle i+1, and (e) during said cycle i+1: (e1) dequeuing up to a predetermined number of command descriptors from the head of said active periodic queue and enqueuing each of said dequeued command descriptors into an in-progress queue, and (e2) sequentially issuing to said disk array a command for performing said I/O transaction corresponding to each command descriptor in said in-progress queue.
Claim 8
Dependent Claim
75 words
The method of claim 1 further comprising the steps of, as each I/O transaction completes: (d) dequeuing said command descriptor corresponding to a completed I/O transaction, (e) enqueuing said dequeued command descriptor corresponding to said completed I/O transaction onto a completion context corresponding to a stream for which said I/O transaction was performed, and (f) signaling a semaphore associated with said completion context onto which said command descriptor for said completed I/O transaction was dequeued.
Claim 9
Dependent Claim
111 words
The method of claim 6 further comprising the steps of: (f) as each I/O transaction completes, dequeuing said command descriptor corresponding to said completed I/O transaction, (g) if said active periodic queue is not empty, performing said steps (e), (e1) and (e2) and (h) if said active periodic queue is empty, dequeuing from an aperiodic queue one or more command descriptors for performing I/O transactions other than for reading or writing stream data, enqueuing each command descriptor that was dequeued from said aperiodic queue into said in-progress queue and sequentially issuing to said disk array a command for performing said I/O transaction corresponding to each command descriptor in said in-progress queue.
Claim 10
Dependent Claim
36 words
The method of claim 2 wherein in said step (e1), each I/O descriptor is enqueued into said submitted I/O transaction queue in the same order in which said requests for performing said I/O transactions are requested.
Claim 11
Dependent Claim
39 words
The method of claim 9 comprising the steps of: (f) dequeuing said I/O descriptors from said submitted I/O transaction queue in the same order in which they are stored when said I/O transactions corresponding to said I/O descriptors complete.
Claim 12
Dependent Claim
30 words
The method of claim 10 further comprising the step of: (g) limiting the number of outstanding submitted requests for performing I/O transactions for each stream to a predetermined maximum number.
Claim 13
Dependent Claim
44 words
The method of claim 11 further comprising the steps of: (h) decreasing a count of the number of outstanding submitted requests for performing I/O transactions on said particular stream for each I/O descriptor dequeued from said submitted I/O transaction queue of said particular stream.
Claim 14
Dependent Claim
60 words
The method of claim 6 further comprising the step of: (f) if at the end of said cycle i+1, at least one I/O transaction corresponding to a command descriptors enqueued into said active periodic queue at said start of said cycle i+1 is not complete, adjusting a duration of said cycle i+2 to prevent drifting of boundaries of said cycles.
Claim 15
Dependent Claim
30 words
The method of claim 1 further comprising the step of: (d) limiting the number of outstanding submitted requests for performing I/O transactions for each stream to a predetermined maximum number.
Claim 16
Dependent Claim
55 words
The method of claim 14 further comprising the steps of: (e) dequeuing an I/O descriptor from a submitted I/O transaction queue of a particular stream when said I/O transaction corresponding to said I/O descriptor completes, and (f) decreasing a count of the number of outstanding submitted requests for performing I/O transactions on said particular stream.
Claim 17
Dependent Claim
57 words
The method of claim 1 further comprising the step of: predefining the cycle time duration as N d S/W base , where N d is the number of disks in the array, S is the number of bits consumed or produced for each stream during the cycle and W base is a base bandwidth of each stream.
Claim 18
Independent Claim
198 words
A method for performing I/O transactions on stream oriented data comprising the steps of: (a) for each request to perform an I/O transaction on a stream issued during a current cycle i, enqueuing an I/O descriptor into a submit pending queue, (b) at the beginning of the next cycle i+1, dequeuing each of said I/O descriptors from said submit pending queue and enqueuing said dequeued I/O descriptors into a submitted I/O transaction queue associated with said stream on which said I/O transaction of said I/O descriptor is to be performed, said I/O descriptors being enqueued into each associated submitted I/O transaction queue in the same order in which said requests to perform said corresponding I/O transactions are requested, (c) performing said I/O transactions in an order that is independent of said order in which said I/O requests corresponding to said I/O transactions are stored in said submitted I/O transaction queues, and (d) maintaining continuity of said streams by retrieving said I/O descriptors from said respective submitted I/O transaction queue in the same order in which said I/O transactions are requested and independently of a specific order in which said I/O transactions corresponding to said I/O descriptors were performed.
Claim 19
Independent Claim
198 words
A method for performing I/O transactions on stream oriented data comprising the steps of: (a) for each request to perform an I/O transaction on a stream issued during a current cycle i, enqueuing an I/O descriptor into a submit pending queue, (b) at the beginning of the next cycle i+1, dequeuing each of said I/O descriptors from said submit pending queue and enqueuing said dequeued I/O descriptors into a submitted I/O transaction queue associated with said stream on which said I/O transaction of said I/O descriptor is to be performed, said I/O descriptors being enqueued into each associated submitted I/O transaction queue in the same order in which said requests to perform said corresponding I/O transactions are requested, (c) performing said I/O transactions in an order that is independent of said order in which said I/O requests corresponding to said I/O transactions are stored in said submitted I/O transaction queues, and (d) maintaining continuity of said streams by retrieving said I/O descriptors from said respective submitted I/O transaction queue in the same order in which said I/O transactions are requested and independently of a specific order in which said I/O transactions corresponding to said I/O descriptors were performed.
Claim 20
Dependent Claim
113 words
The method of claim 17 wherein said step (c) further comprises the steps of: (c1) enqueuing one or more command descriptors for performing I/O transactions, corresponding to each request that issued during said cycle i, into an inactive periodic queue, during said cycle i, (c2) delaying performing said I/O transactions of said command descriptors in said inactive periodic queue until said cycle i+1, (c) at a beginning of said cycle i+1, placing said command descriptors in said inactive periodic queue into an active periodic queue, wherein during each cycle, I/O transactions are performed for each command descriptor in said active periodic queue, but not performed for command descriptors in said inactive periodic queue.
Claim 21
Dependent Claim
41 words
The method of claim 17 further comprising, prior to said step (a), the steps of: (e) opening a chunk assigned to a particular stream on which one or more I/O transactions are to be performed and allocating resources for said chunk.
Claim 22
Dependent Claim
60 words
The method of claim 19 further comprising the steps of: (e1) allocating bandwidth for transmitting data read or written during said I/O transaction, (e2) generating an open descriptor for said stream including a queue for storing I/O descriptors for submitted pending I/O transaction requests, and (e3) generating a completion context in which command descriptors for completed I/O transactions are enqueued.
Claim 23
Dependent Claim
38 words
The method of claim 20 further comprising the steps of: (f) if said chunk is closed but a second chunk is specified to be opened immediately thereafter, assigning said resources allocated to said chunk to said second chunk.
Claim 24
Dependent Claim
104 words
The method of claim 18 further comprising the steps of: (e) prior to said cycle i+1, ordering each command descriptor in said inactive periodic queue to increase the number of I/O transactions that can be performed during said cycle i+1, and (f) during said cycle i+1: (g1) dequeuing up to a predetermined number of command descriptors from the head of said active periodic queue and enqueuing each of said dequeued command descriptors into an in-progress queue, and (g2) sequentially issuing to an array of at least one disk, a command for performing said I/O transaction corresponding to each command descriptor in said in-progress queue.
Claim 25
Dependent Claim
75 words
The method of claim 18 further comprising the steps of, as each I/O transaction completes: (e) dequeuing said command descriptor corresponding to said completed I/O transaction, (f) enqueuing said dequeued command descriptor corresponding to said completed I/O transaction onto a completion context corresponding to a stream for which said I/O transaction was performed, and (g) signaling a semaphore associated with said completion context onto which said command descriptor for said completed I/O transaction was dequeued.
Claim 26
Dependent Claim
107 words
The method of claim 22 further comprising the steps of: (h) as each I/O transaction completes, dequeuing said command descriptor corresponding to said completed I/O transaction, (i) if said active periodic queue is not empty, performing said steps (g), (g1) and (g2) and (j) if said active periodic queue is empty, dequeuing from an aperiodic queue one or more command descriptors for performing I/O transactions other than for reading or writing stream data, enqueuing each command descriptor that was dequeued from said aperiodic queue into said in-progress queue and sequentially issuing a command for performing said I/O transaction corresponding to each command descriptor in said in-progress queue.
Claim 27
Dependent Claim
60 words
The method of claim 22 further comprising the step of: (h) if at the end of said cycle i+1, at least one I/O transaction corresponding to a command descriptors enqueued into said active periodic queue at said start of said cycle i+1 is not complete, adjusting a duration of said cycle i+2 to prevent drifting of boundaries of said cycles.
Claim 28
Dependent Claim
30 words
The method of claim 17 further comprising the step of: (e) limiting the number of outstanding submitted requests for performing I/O transactions for each stream to a predetermined maximum number.
Claim 29
Dependent Claim
55 words
The method of claim 26 further comprising the steps of: (f) dequeuing an I/O descriptor from a submitted I/O transaction queue of a particular stream when said I/O transaction corresponding to said I/O descriptor completes, and (g) decreasing a count of the number of outstanding submitted requests for performing I/O transactions on said particular stream.
Claim 30
Dependent Claim
57 words
The method of claim 17 further comprising the step of: predefining the cycle time duration as N d S/W base , where N d is the number of disks in the array, S is the number of bits consumed or produced for each stream during the cycle and W base is a base bandwidth of each stream.
References Cited (Backward Citations)
US4536836A
Cited
US4636946A
Cited
US4688168A
Cited
US5008819A
Cited
US4888691A
Cited
WO1990000280A1
Cited
US5140683A
Cited
US5339449A
Cited
US5218695A
Cited
WO1991013404A1
Cited
EP0458554A2
Cited
US5263145A
Cited
WO1992004674A1
Cited
US5197143A
Cited
US5220653A
Cited
EP0521630A2
Cited
US5301297A
Cited
EP0535807A2
Cited
US5261072A
Cited
US5440683A
Cited
US5331417A
Cited
US5448315A
Cited
WO1994012937A2
Cited
US5455934A
Cited
US5446855A
Cited
EP0701198A1
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2001-08-31 | 2002-03-02 | 2002-09-01 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2005-08-31 | 2006-03-02 | 2006-09-01 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2009-08-31 | 2010-03-02 | 2010-09-01 | $7700.00 | Window Closed / Lapsed |