US5734925A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method for scheduling I/O transactions in a data storage system to maintain the continuity of a plurality of video streams
Assignee: Starlight Networks Inc
•
Filing: 1996-09-10
•
Granted: 1998-03-31
•
Expires: 2016-09-10
Abstract
Abstract A method for operating a disk storage system, comprising a disk and forming part of a communications network, simultaneously maintains the continuity of a plurality of data streams. Typically, each stream transfers video data to or from the disk storage system. Illustratively, each of the data streams is produced in the network at a rate of W base bits/sec and consumed by the disk storage system or produced by said disk storage system and consumed in the network at a rate of W base bits/sec. One I/O transaction is performed for each stream in each of a plurality of I/O cycles of duration S/W base , wherein in each I/O transaction a segment of S bits is retrieved from or stored in the disk. The number of streams whose continuity can be maintained in this manner is limited by the number of I/O's which can be performed in a cycle of duration S/W base . More generally, when a stream has a bit rate (A/B)W base bits/sec where A and B are integers chosen independently for each stream, then for this stream A I/O transactions are performed in B cycles of duration S/W base . If the number of disks is N d ,N d ≧1, then the I/O cycles have a duration N d S/W base and then A I/O transactions are performed in each disk for each stream in B I/O cycles.
Inventors
- 👤 Fouad A. Tobagi
- 👤 Joseph M. Gang, Jr.
- 👤 Randall B. Baird
- 👤 Joseph W. M. Pang
- 👤 Martin J. McFadden
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-01 15:50
CPC Classifications
H; H04; H04N; H04N21/00; H04N21/20; H04N21/21; G; G06; G06F; G06F16/00; G06F16/10; G06F3/00; G06F3/06; G06F3/0601; G06F3/0602; G06F3/061; G06F3/0628; G06F3/0655; G06F3/0659; G06F3/0668; G06F3/067; G11; G11B; G11B27/00; G11B27/10; G11B27/102; G11B27/105; H04N21/23; H04N7/00; H04N7/16; H04N7/173; H04N7/17309; H04N7/17336; H04N7/24; G11B2220/00; G11B2220/20
Claims Analysis
Total Claims: 28
Claim 1
Independent Claim
327 words
A method for scheduling I/O transactions for a data storage system comprising N d storage units, said data storage system storing data for a plurality of full motion video streams, each of said streams having a bit rate of (A/B)W base where A and B are integers chosen independently for each of said streams, said method comprising the steps of maintaining the continuity of said full motion video streams simultaneously by performing for each of said streams A I/O transactions in each of said N d storage units within each set of B I/O cycles in a sequence of sets of B I/O cycles, each I/O cycle having a duration of N d S/W base , in each of said I/O transactions a segment of S bits is retrieved from one of said storage units or written into one of said storage units, the duration of each I/O transaction being shorter than S/W base , for streams in which segments are retrieved from said storage system, the segments of a stream retrieved from said storage system in each particular set of B I/O cycles being consumed in a particular set of B consumption cycles in a sequence of sets of B consumption cycles, the particular set of B consumption cycles beginning after the first I/O transaction is performed for the stream in the particular set of B I/O cycles, the duration of a consumption cycle being N d S/W base , for streams in which segments are written into said storage system, the segments of a stream written into said storage system in each particular set of B I/O cycles being produced in a particular set of B production cycles in a sequence of sets of B production cycles, the particular set of B production cycles ending prior to performing the last I/O transaction for the stream in the particular set of B I/O cycles; the duration of a production cycle being N d S/W base .
Claim 2
Independent Claim
327 words
A method for scheduling I/O transactions for a data storage system comprising N d storage units, said data storage system storing data for a plurality of full motion video streams, each of said streams having a bit rate of (A/B)W base where A and B are integers chosen independently for each of said streams, said method comprising the steps of maintaining the continuity of said full motion video streams simultaneously by performing for each of said streams A I/O transactions in each of said N d storage units within each set of B I/O cycles in a sequence of sets of B I/O cycles, each I/O cycle having a duration of N d S/W base , in each of said I/O transactions a segment of S bits is retrieved from one of said storage units or written into one of said storage units, the duration of each I/O transaction being shorter than S/W base , for streams in which segments are retrieved from said storage system, the segments of a stream retrieved from said storage system in each particular set of B I/O cycles being consumed in a particular set of B consumption cycles in a sequence of sets of B consumption cycles, the particular set of B consumption cycles beginning after the first I/O transaction is performed for the stream in the particular set of B I/O cycles, the duration of a consumption cycle being N d S/W base , for streams in which segments are written into said storage system, the segments of a stream written into said storage system in each particular set of B I/O cycles being produced in a particular set of B production cycles in a sequence of sets of B production cycles, the particular set of B production cycles ending prior to performing the last I/O transaction for the stream in the particular set of B I/O cycles; the duration of a production cycle being N d S/W base .
Claim 3
Dependent Claim
15 words
The method of claim 1 wherein said storage system is located in a communications network.
Claim 4
Dependent Claim
19 words
The method of claim 1 wherein the network produces or consumes W base bits/sec for each of the streams.
Claim 5
Dependent Claim
15 words
The method of claim 1 wherein said streams share buffer capacity in a local buffer.
Claim 6
Dependent Claim
76 words
The method of claim 1 wherein said streams are divided into G groups, wherein the production or consumption cycles of the streams within each group are aligned with each other, but the production and consumption cycles of successive groups are offset from the production and consumption cycles of the previous group by (1/G) th of an I/O cycle, and wherein each I/O cycle is divided into G I/O subcycles of duration N d S/W base G.
Claim 7
Dependent Claim
36 words
The method of claim 5 wherein in each I/O subcycle there is one I/O transaction performed in each storage unit for each stream in the group whose production or consumption cycle begins immediately after the subcycle.
Claim 8
Dependent Claim
23 words
The method of claim 5 wherein in each subcycle, one I/O transaction is performed for each stream in each of N d groups.
Claim 9
Dependent Claim
29 words
The method of claim 1 wherein the number of I/O transactions performed in each I/O cycle for each storage unit for active streams does not exceed a predetermined number.
Claim 10
Dependent Claim
40 words
The method of claim 8 further comprising the step of activating one or more new streams if the number of I/O transactions performed in each I/O cycle for each storage unit for active streams is less than said predetermined number.
Claim 11
Dependent Claim
25 words
The method of claim 9 wherein excess capacity for I/O transactions in said storage units is used for start-up data for said newly activated streams.
Claim 12
Dependent Claim
16 words
The method of claim 9 wherein new streams are activated according to a predetermined service discipline.
Claim 13
Dependent Claim
24 words
The method of claim 11 wherein the predetermined service discipline is chosen from the group comprising first-come-first-served, round robin, last-come-first-served, and shortest job first.
Claim 14
Dependent Claim
31 words
The method of claim 10 wherein in each I/O cycle, the I/O transactions of previously active streams and I/O transactions for the start-up data of newly activated streams are sorted together.
Claim 15
Dependent Claim
45 words
The method of claim 10 wherein in each I/O cycle, the I/O transactions of previously active streams are sorted and performed in one subcycle and the I/O transactions for the start-up data of newly activated streams are separately sorted and performed in a separate subcycle.
Claim 16
Dependent Claim
13 words
The method of claim 1 wherein said network is a local area network.
Claim 17
Dependent Claim
11 words
The method of claim 1 wherein said streams contain video data.
Claim 18
Dependent Claim
26 words
The method of claim 1 wherein I/O transactions for said streams have a predetermined order which does not change from one I/O cycle to the next.
Claim 19
Dependent Claim
20 words
The method of claim 1 wherein the I/O transactions have an order which is separately determined for each I/O cycle.
Claim 20
Dependent Claim
16 words
The method of claim 1 wherein the storage system is a Redundant Array of Inexpensive Disks.
Claim 21
Dependent Claim
23 words
The method of claim 1 wherein B has a fixed value for all streams N super , where N super is an integer.
Claim 22
Dependent Claim
24 words
The method of claim 1 wherein segments of said streams are allocated to the storage units in said array in a regular cyclic pattern.
Claim 23
Dependent Claim
24 words
The method of claim 1 wherein for each stream the A I/O transactions for each storage unit are uniformly spread in B I/O cycles.
Claim 24
Dependent Claim
75 words
The method of claim 20 wherein N super I/O cycles form a supercycle, wherein in each I/O cycle of a supercycle, for each stream L stripes are fetched from or written into said storage system, wherein each stripe comprises one segment of S bits fetched from or written into each of said N d storage units, and wherein for each stream the variance of the number L over the cycles of a supercycle is minimized.
Claim 25
Dependent Claim
35 words
The method of claim 23 wherein the variance of the total number of stripes fetched from or written into said storage system, for all of said streams in each cycle of a supercycle is minimized.
Claim 26
Dependent Claim
45 words
The method of claim 1 wherein segments are grouped into data stripes of N d consecutive segments, wherein said array is organized into bin stripes comprising locations in each of said N d storage units, and wherein data stripes are randomly allocated to bin stripes.
Claim 27
Independent Claim
394 words
A method for scheduling I/O transactions for a data storage system comprising N d storage units to enable full motion video streams to be written into said data storage system and to be retrieved from said data storage system, said data storage system storing data for a plurality of said full motion video streams, said streams being divided into G groups, said method comprising the steps of: maintaining simultaneously the continuity of said full motion video streams to be written into said data storage system and to be retrieved from said data storage system by performing for each of said streams a predetermined number of I/O transactions in each of said N d data storage units in each of a plurality of successive I/O cycles, each I/O cycle having a duration of N d S/W base , where S is a number of bits and W base is a basic rate, in each of said I/O transactions a segment of S bits is retrieved from one of said storage units or written into one of said storage units, the duration of an I/O transaction being shorter than the duration of an I/O cycle so that multiple I/O transactions can be scheduled for each said data storage unit in an I/O cycle, for streams in which segments are retrieved from said storage system, the segments of a stream being retrieved from the storage system in each particular I/O cycle being consumed in a particular consumption cycle in a sequence of consumption cycles, the particular consumption cycle beginning after a first I/O transaction for the stream in the particular I/O cycle, for streams in which segments are written into said storage system, all of the segments of a stream being written into the storage system in each particular I/O cycle being produced in a particular production cycle in a sequence of production cycles, the particular production cycle ending prior to a last I/O transaction for the stream in the particular I/O cycle, and wherein the production or consumption cycles of the streams within each group are aligned with each other, but the production and consumption cycles of successive groups are offset from the production and consumption cycles of the previous group by (1/G) th of an I/O cycle, and wherein each I/O cycle is divided into G I/O subcycles of duration N d S/W base G.
Claim 28
Independent Claim
394 words
A method for scheduling I/O transactions for a data storage system comprising N d storage units to enable full motion video streams to be written into said data storage system and to be retrieved from said data storage system, said data storage system storing data for a plurality of said full motion video streams, said streams being divided into G groups, said method comprising the steps of: maintaining simultaneously the continuity of said full motion video streams to be written into said data storage system and to be retrieved from said data storage system by performing for each of said streams a predetermined number of I/O transactions in each of said N d data storage units in each of a plurality of successive I/O cycles, each I/O cycle having a duration of N d S/W base , where S is a number of bits and W base is a basic rate, in each of said I/O transactions a segment of S bits is retrieved from one of said storage units or written into one of said storage units, the duration of an I/O transaction being shorter than the duration of an I/O cycle so that multiple I/O transactions can be scheduled for each said data storage unit in an I/O cycle, for streams in which segments are retrieved from said storage system, the segments of a stream being retrieved from the storage system in each particular I/O cycle being consumed in a particular consumption cycle in a sequence of consumption cycles, the particular consumption cycle beginning after a first I/O transaction for the stream in the particular I/O cycle, for streams in which segments are written into said storage system, all of the segments of a stream being written into the storage system in each particular I/O cycle being produced in a particular production cycle in a sequence of production cycles, the particular production cycle ending prior to a last I/O transaction for the stream in the particular I/O cycle, and wherein the production or consumption cycles of the streams within each group are aligned with each other, but the production and consumption cycles of successive groups are offset from the production and consumption cycles of the previous group by (1/G) th of an I/O cycle, and wherein each I/O cycle is divided into G I/O subcycles of duration N d S/W base G.
References Cited (Backward Citations)
US4536836A
Cited
US4636946A
Cited
US4688168A
Cited
US5008819A
Cited
WO1990000280A1
Cited
US5140683A
Cited
US5218695A
Cited
WO1991013404A1
Cited
US5263145A
Cited
EP0458554A2
Cited
WO1992004674A1
Cited
US5197143A
Cited
US5220653A
Cited
EP0521630A2
Cited
US5301297A
Cited
EP0535807A2
Cited
US5261072A
Cited
US5440683A
Cited
US5331417A
Cited
US5448315A
Cited
WO1994012937A2
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-03-30 | 2001-09-29 | 2002-03-31 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2005-03-30 | 2005-09-29 | 2006-03-31 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2009-03-30 | 2009-09-29 | 2010-03-31 | $7700.00 | Window Closed / Lapsed |