US5583995A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Apparatus and method for data storage and retrieval using bandwidth allocation
Assignee: Veridian Information Solutions Inc
•
Filing: 1995-01-30
•
Granted: 1996-12-10
•
Expires: 2015-01-30
Abstract
Abstract An apparatus and method is provided for allocating a data file across a plurality of media servers in a network, wherein each media server has associated therewith one or more levels of I/O devices organized in a hierarchical manner. An attempt is made to allocate the storage of data across the I/O devices in such a way that the bandwidth imposed on the devices when the data file is sequentially accessed will be balanced, and optimum use of I/O bandwidths at all points in the system is achieved. This balancing can be done by incorporating knowledge regarding various bottlenecks in the system into the decisionmaking process required for distributing the data blocks. The method and apparatus further allows bandwidths to be allocated to various clients in the system at the time a data file is opened. Various checks are provided at the time a data file is accessed to ensure that the data rates actually imposed by the requesting client do not exceed that requested by the client at the time the data file was opened. The invention allows for much more efficient use of the I/O resources in a system and ensures that a given configuration will be able to support client requests.
Inventors
- 👤 Alan S. Gardner
- 👤 Rodney D. McElrath
- 👤 Stephen L. Harvey
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-26 06:31
CPC Classifications
G; G06; G06F; G06F11/00; G06F11/07; G06F11/08; G06F11/10; G06F11/1076; H; H04; H04L; H04L67/00; H04L67/01; H04L67/10; H04L67/1095; H04L9/00; H04L9/40; H04N; H04N7/00; H04N7/16; H04N7/173; H04N7/17309; H04N7/17318; H04N7/17336; G06F2211/00; G06F2211/10; G06F2211/1002; G06F2211/1028
Claims Analysis
Total Claims: 35
Claim 1
Independent Claim
174 words
A method of storing a data file across a plurality of media servers in a network, each media server having a plurality of first-level I/O devices and a plurality of second-level I/O devices, each second-level I/O device being controlled by one of the first-level I/O devices, the method comprising the steps of: (a) dividing the data file into a plurality of data blocks; (b) allocating the plurality of data blocks across each of the plurality of media servers; (c) allocating each of the data blocks allocated to each media server in step (b) to first-level I/O devices in that media server according to the bandwidth availability of the first-level I/O devices in that media server; (d) allocating each of the data blocks allocated to each first-level I/O device in step (c) to second-level I/O devices controlled by that first-level I/O device in accordance with the bandwidth availability of the second-level I/O devices; and (e) storing each of the data blocks onto the second-level I/O devices in accordance with the allocation made in step (d).
Claim 2
Independent Claim
174 words
A method of storing a data file across a plurality of media servers in a network, each media server having a plurality of first-level I/O devices and a plurality of second-level I/O devices, each second-level I/O device being controlled by one of the first-level I/O devices, the method comprising the steps of: (a) dividing the data file into a plurality of data blocks; (b) allocating the plurality of data blocks across each of the plurality of media servers; (c) allocating each of the data blocks allocated to each media server in step (b) to first-level I/O devices in that media server according to the bandwidth availability of the first-level I/O devices in that media server; (d) allocating each of the data blocks allocated to each first-level I/O device in step (c) to second-level I/O devices controlled by that first-level I/O device in accordance with the bandwidth availability of the second-level I/O devices; and (e) storing each of the data blocks onto the second-level I/O devices in accordance with the allocation made in step (d).
Claim 3
Dependent Claim
38 words
The method of claim 1, wherein step (c) comprises the step of using disk controllers as the first-level I/O devices, and wherein steps (d) and (e) each comprise the step of using disks as the second-level I/O devices.
Claim 4
Dependent Claim
58 words
The method of claim 1, wherein step (a) comprises the step of generating a plurality of error-correcting code (ECC) blocks for correcting errors in the plurality of data blocks, and wherein steps (b) through (e) collectively comprise the step of allocating and storing the plurality of ECC blocks in the same manner as the plurality of data blocks.
Claim 5
Dependent Claim
34 words
The method of claim 3, wherein step (a) comprises the step of generating a number of ECC blocks which is dependent on the number of media servers over which the data blocks are allocated.
Claim 6
Dependent Claim
44 words
The method of claim 4, wherein step (a) comprises the step of using a number of ECC blocks which is approximately equal to the number of data blocks divided by the number of media servers over which the data blocks are allocated minus one.
Claim 7
Dependent Claim
28 words
The method of claim 1, wherein step (b) comprises the step of allocating the data blocks across each media server in proportion to each media server's available bandwidth.
Claim 8
Dependent Claim
35 words
The method of claim 1, wherein steps (a) and (b) are performed in a media client coupled to the network, and wherein steps (c) through (e) are performed separately in each of the media servers.
Claim 9
Dependent Claim
82 words
The method of claim 1, further comprising the steps of: (f) from a media client, requesting that the data file be opened at a particular bandwidth; (g) determining whether the data file can be opened at the requested bandwidth on the basis of previous bandwidth allocations made for the media server across which the data file was previously stored; and (h) responsive to a determination that the data file cannot be opened in step (g), denying the request to open the file.
Claim 10
Dependent Claim
45 words
The method of claim 1, further comprising the step of grouping the plurality of media servers into two or more teams, and wherein step (b) comprises the step of allocating the data blocks only to media servers within one of the two or more teams.
Claim 11
Dependent Claim
61 words
The method of claim 1, wherein step (c) comprises the step of using a bandwidth availability of the first-level I/O devices which is approximately: MINIMUM{BW(a1), [BW(d1)+BW(d2)]}, where BW(a1) is a bandwidth sustainable by a first-level I/O device a1, BW(d1) is a bandwidth sustainable by a second-level I/O device d1, and BW(d2) is a bandwidth sustainable by a second-level I/O device d2.
Claim 12
Dependent Claim
170 words
Apparatus for storing a data file across a plurality of media servers in a network, each media server having a plurality of first-level I/O devices and a plurality of second-level I/O devices, each second-level I/O device being controlled by one of the first-level I/O devices, the apparatus comprising: means for dividing the data file into a plurality of data blocks; means for allocating the plurality of data blocks across each of the plurality of media servers; means for allocating each of the data blocks allocated to each media server to first-level I/O devices in that media server according to the bandwidth availability of the first-level I/O devices in that media server; means for allocating each of the data blocks allocated to each first-level I/O device to second-level I/O devices controlled by that first-level I/O device in accordance with the bandwidth availability of the second-level I/O devices; and means for storing each of the data blocks onto the second-level I/O devices in accordance with the allocations to the second-level I/O devices.
Claim 13
Dependent Claim
170 words
Apparatus for storing a data file across a plurality of media servers in a network, each media server having a plurality of first-level I/O devices and a plurality of second-level I/O devices, each second-level I/O device being controlled by one of the first-level I/O devices, the apparatus comprising: means for dividing the data file into a plurality of data blocks; means for allocating the plurality of data blocks across each of the plurality of media servers; means for allocating each of the data blocks allocated to each media server to first-level I/O devices in that media server according to the bandwidth availability of the first-level I/O devices in that media server; means for allocating each of the data blocks allocated to each first-level I/O device to second-level I/O devices controlled by that first-level I/O device in accordance with the bandwidth availability of the second-level I/O devices; and means for storing each of the data blocks onto the second-level I/O devices in accordance with the allocations to the second-level I/O devices.
Claim 14
Dependent Claim
25 words
The apparatus of claim 11, wherein said first-level I/O devices each comprise a disk controller, and wherein said second-level I/O devices each comprise a disk.
Claim 15
Dependent Claim
46 words
The apparatus of claim 11, further comprising means for generating a plurality of error-correcting code (ECC) blocks for correcting errors in the plurality of data blocks, wherein the plurality of ECC blocks are allocated and stored in the same manner as the plurality of data blocks.
Claim 16
Dependent Claim
31 words
The apparatus of claim 13, wherein the number of error-correcting code (ECC) blocks which are generated is dependent on the number of media servers over which the data blocks are allocated.
Claim 17
Dependent Claim
37 words
The apparatus of claim 14, wherein the number of ECC blocks generated is approximately equal to the number of data blocks divided by the number of media servers over which the data blocks are allocated minus one.
Claim 18
Dependent Claim
23 words
The apparatus of claim 11, wherein the data blocks are allocated across each media server in proportion to each media server's available bandwidth.
Claim 19
Dependent Claim
62 words
The method of claim 11, wherein the means for dividing the data file and the means for allocating the data blocks across each of the plurality of media servers is located at a media client coupled to the network, and wherein the means for allocating each of the data blocks to first-level I/O devices is replicated in each of the media servers.
Claim 20
Dependent Claim
82 words
The apparatus of claim 11, further comprising: means for, from a media client, requesting that the data file be opened at a particular bandwidth; means for determining whether the data file can be opened at the requested bandwidth on the basis of previous bandwidth allocations made for the media servers across which the data file was previously stored; and means, responsive to a determination that the data file cannot be opened at the requested bandwidth, denying the request to open the file.
Claim 21
Dependent Claim
37 words
The apparatus of claim 11, wherein the plurality of media servers are grouped into two or more teams, and wherein the data blocks are allocated only to media servers within one of the two or more teams.
Claim 22
Dependent Claim
58 words
The apparatus of claim 11, wherein the bandwidth availability of at least one of the first-level I/O devices which is approximately: MINIMUM{BW(a1), [BW(d1)+BW(d2)]}, where BW(a1) is a bandwidth sustainable by a first-level I/O device a1, BW(d1) is a bandwidth sustainable by a second-level I/O device d1, and BW(d2) is a bandwidth sustainable by a second-level I/O device d2.
Claim 23
Independent Claim
113 words
A method of retrieving a data file previously stored across a plurality of media servers, the method comprising the steps of: (a) from a media client, requesting that the data file be opened at a particular data bandwidth; (b) determining whether enough data bandwidth remains, on the basis of allocations previously made for the media servers across which the data file was previously stored, to satisfy the request made in step (a); (c) responsive to a determination in step (b) that sufficient bandwidth remains to satisfy the request, allocating the requested bandwidth toward the media servers across which the data file was previously stored; and (d) retrieving data blocks from the data file.
Claim 24
Independent Claim
113 words
A method of retrieving a data file previously stored across a plurality of media servers, the method comprising the steps of: (a) from a media client, requesting that the data file be opened at a particular data bandwidth; (b) determining whether enough data bandwidth remains, on the basis of allocations previously made for the media servers across which the data file was previously stored, to satisfy the request made in step (a); (c) responsive to a determination in step (b) that sufficient bandwidth remains to satisfy the request, allocating the requested bandwidth toward the media servers across which the data file was previously stored; and (d) retrieving data blocks from the data file.
Claim 25
Dependent Claim
25 words
The method of claim 21, further comprising the step of denying the request made in step (a) if the determination in step (b) is negative.
Claim 26
Dependent Claim
49 words
The method of claim 21, further comprising the steps of: (e) periodically measuring the actual data bandwidth used in retrieving the data blocks in step (d); and (f) responsive to a determination that the actual data bandwidth in step (e) has been exceeded, delaying one or more retrieval requests.
Claim 27
Dependent Claim
104 words
Apparatus for retrieving a data file previously stored across a plurality of media servers, comprising: means for, from a media client, requesting that the data file be opened at a particular data bandwidth; means for determining whether enough data bandwidth remains, on the basis of allocations previously made for the media servers across which the data file was previously stored, to satisfy the request; means for, responsive to a determination that sufficient bandwidth remains to satisfy the request, allocating the requested bandwidth toward the media servers across which the data file was previously stored; and means for retrieving data blocks from the data file.
Claim 28
Dependent Claim
104 words
Apparatus for retrieving a data file previously stored across a plurality of media servers, comprising: means for, from a media client, requesting that the data file be opened at a particular data bandwidth; means for determining whether enough data bandwidth remains, on the basis of allocations previously made for the media servers across which the data file was previously stored, to satisfy the request; means for, responsive to a determination that sufficient bandwidth remains to satisfy the request, allocating the requested bandwidth toward the media servers across which the data file was previously stored; and means for retrieving data blocks from the data file.
Claim 29
Dependent Claim
17 words
The apparatus of claim 24, further comprising means for denying the request if the determination is negative.
Claim 30
Dependent Claim
42 words
The apparatus of claim 24, further comprising: means for periodically measuring the actual data bandwidth used in retrieving the data blocks; and means for, responsive to a determination that the actual data bandwidth has been exceeded, delaying one or more retrieval requests.
Claim 31
Dependent Claim
33 words
The apparatus of claim 6, wherein the means for periodically measuring the actual data bandwidth used comprises means for accumulating a bill for the media client based on the actual data bandwidth used.
Claim 32
Dependent Claim
115 words
A media server, comprising: a plurality of disk devices for storing data; a plurality of disk controllers, each of which controls one or more of the disk devices; a network interface for interfacing with a network; a client/server protocol, coupled to the network interface, for communicating with media clients on the network; and means, responsive to a request received from one of the media clients on the network, for allocating a plurality of data file blocks across the plurality of disk devices in accordance with a predetermined bandwidth availability determination, such that the number of data file blocks stored on each disk is approximately proportional to that disk's contribution to the predetermined bandwidth availability determination.
Claim 33
Dependent Claim
115 words
A media server, comprising: a plurality of disk devices for storing data; a plurality of disk controllers, each of which controls one or more of the disk devices; a network interface for interfacing with a network; a client/server protocol, coupled to the network interface, for communicating with media clients on the network; and means, responsive to a request received from one of the media clients on the network, for allocating a plurality of data file blocks across the plurality of disk devices in accordance with a predetermined bandwidth availability determination, such that the number of data file blocks stored on each disk is approximately proportional to that disk's contribution to the predetermined bandwidth availability determination.
Claim 34
Dependent Claim
232 words
A video-on-demand system for storing and retrieving a video data file, comprising: plurality of media servers connected via a network, each media server comprising a plurality of first-level I/O devices; a plurality of second-level I/O devices each controlled by one of the first-level I/O devices; means for allocating a plurality of video data blocks comprising portions of said video data tile to said first-level I/O devices according to the bandwidth availability of each of the first-level I/O devices; means for further allocating each video data block allocated to each first-level I/O device to second-level I/O devices controlled by that first-level I/O device in accordance with the bandwidth availability of each of the second-level I/O devices; and means for storing each of the video data blocks onto the second-level I/O devices in accordance with the allocations to the second-level I/O devices; and a plurality of media clients connected to said network, each media client comprising means for requesting that said video data file be opened at a particular bandwidth; means tier determining whether said video data file can be opened at the requested bandwidth on the basis of previous bandwidth allocations made for all media servers across which said video data file was previously stored; and means for, responsive to a determination that said video data file can be opened, reading said plurality of video data blocks from said plurality of media servers.
Claim 35
Dependent Claim
232 words
A video-on-demand system for storing and retrieving a video data file, comprising: plurality of media servers connected via a network, each media server comprising a plurality of first-level I/O devices; a plurality of second-level I/O devices each controlled by one of the first-level I/O devices; means for allocating a plurality of video data blocks comprising portions of said video data tile to said first-level I/O devices according to the bandwidth availability of each of the first-level I/O devices; means for further allocating each video data block allocated to each first-level I/O device to second-level I/O devices controlled by that first-level I/O device in accordance with the bandwidth availability of each of the second-level I/O devices; and means for storing each of the video data blocks onto the second-level I/O devices in accordance with the allocations to the second-level I/O devices; and a plurality of media clients connected to said network, each media client comprising means for requesting that said video data file be opened at a particular bandwidth; means tier determining whether said video data file can be opened at the requested bandwidth on the basis of previous bandwidth allocations made for all media servers across which said video data file was previously stored; and means for, responsive to a determination that said video data file can be opened, reading said plurality of video data blocks from said plurality of media servers.
References Cited (Backward Citations)
US4920432A
Cited
US5166939A
Cited
US5274645A
Cited
US5133079A
Cited
US5093718A
Cited
US5132992A
Cited
US5237658A
Cited
US5389963A
Cited
WO1993016557A1
Cited
US5371532A
Cited
US5305438A
Cited
US5473362A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1999-12-10 | 2000-06-10 | 2000-12-10 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2003-12-10 | 2004-06-10 | 2004-12-10 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2007-12-10 | 2008-06-10 | 2008-12-10 | $7700.00 | Window Closed / Lapsed |