US5852705A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method and apparatus for guaranteeing average case disk transfer bandwidth and seek time for a video server
Assignee: Sun Microsystems Inc
•
Filing: 1995-05-22
•
Granted: 1998-12-22
•
Expires: 2015-05-22
Abstract
Abstract In a video server hard disk storage unit, video layout ensures average case bandwidth and case seek time during bounded-time information transfers, to maximize access of users S. The storage unit includes D hard disks whose platters are divided into Z zones. Each movie is divided into i blocks and is striped across all D disks such that movie block i is stored on disk (i mod D). In one embodiment, movie block i is placed in zone (i/D) mod Z of disk (i mod D). User streams are organized into slots containing N=S/D streams and the number of streams in each slot accessing a zone is ≦(N/Z). Seeking is to the nearest end of a set of accesses, where total seek time for a set of N accesses is ≦N*seek (1.5/N). Preferably two storage buffers/stream are used. Admission policy permits stream assignment to any slot, but streams do not transfer until the needed data block is on the disk needed by the other streams in the slot, and until the block is in the proper disk zone. A second embodiment optimizes disk seeks by placing movie block i in zone (((i/D)+(i mod D)) mod Z) of disk (i mod D) to reduce buffer unit requirements. The S streams progress in order 0 to S-1 through disks 0 to D-1, all streams accessing each disk from the same zone before moving through the disk in another zone.
Inventors
- 👤 James G. Hanko
- 👤 Steve Kleiman
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-06 05:59
CPC Classifications
H; H04; H04N; H04N21/00; H04N21/40; H04N21/47; H04N21/472; H04N21/47202; H04N21/20; H04N21/23; H04N21/232; H04N21/2326; H04N7/00; H04N7/16; H04N7/173; H04N7/17309; H04N7/17318
Claims Analysis
Total Claims: 31
Claim 1
Independent Claim
159 words
A method for achieving substantially average case hard disk drive transfer bandwidth in a video server system having a plurality of D hard disk drives whereon blocks of video movies are stored before transfer to a buffer unit, the method comprising the following steps: (a) dividing each of said hard disk drives into Z substantially equal storage zones; (b) recording a portion of each of said video movies across all of said storage zones such that each of said storage zones contains a substantially equal number of blocks of a video movie; and (c) for said video server system, defining a substantially equal number of user streams per a slot using each of said zones, wherein a sum S of said user streams represents a maximum number of users that can access said video server system at one time; wherein worst case bandwidth for each slot is determinable given worst case bandwidth information for transfers from each said zone.
Claim 2
Independent Claim
159 words
A method for achieving substantially average case hard disk drive transfer bandwidth in a video server system having a plurality of D hard disk drives whereon blocks of video movies are stored before transfer to a buffer unit, the method comprising the following steps: (a) dividing each of said hard disk drives into Z substantially equal storage zones; (b) recording a portion of each of said video movies across all of said storage zones such that each of said storage zones contains a substantially equal number of blocks of a video movie; and (c) for said video server system, defining a substantially equal number of user streams per a slot using each of said zones, wherein a sum S of said user streams represents a maximum number of users that can access said video server system at one time; wherein worst case bandwidth for each slot is determinable given worst case bandwidth information for transfers from each said zone.
Claim 3
Dependent Claim
44 words
The method of claim 1, wherein step (b) further includes recording each of said video movies across all of said D hard disk drives such that each of said D hard disk drives contains a substantially equal number of blocks of a video movie.
Claim 4
Dependent Claim
27 words
The method of claim 1, wherein at step (b), for each of said video movies, movie block i is recorded on hard disk drive (i mod D).
Claim 5
Dependent Claim
32 words
The method of claim 1, wherein at step (b), for each of said video movies, movie block i is recorded in zone ((i/D) mod Z) of hard disk drive (i mod D).
Claim 6
Dependent Claim
25 words
The method of claim 1, wherein at step (c), said user streams are organized into said slots such that each slot contains substantially N=S/D streams.
Claim 7
Dependent Claim
71 words
The method of claim 1, wherein said method also achieves substantially an average case hard disk drive seek time, said method including the following additional step: (d) seeking information from said D hard disk drives by seeking to a nearest end of a set of N ordered seeks, and then proceeding through said set to a nearest subsequent position; wherein substantially average case hard disk drive transfer seek time is achieved.
Claim 8
Dependent Claim
17 words
The method of claim 6, wherein total seek time for a set of N access is ≦N*seek(1.5/N).
Claim 9
Dependent Claim
10 words
The method of claim 1, wherein at step (a), Z=2.
Claim 10
Dependent Claim
62 words
The method of claim 1, wherein said video server system buffer unit includes a set of buffers providing at least two buffers per stream, wherein at any time interval one of said buffers receives blocks from said hard disk drives while a second of said buffers provides blocks to said users, which provided blocks were received during an immediately preceding time interval.
Claim 11
Dependent Claim
26 words
The method of claim 9, wherein said set of buffers each store about 256 Kbytes and transfer a block of 256 Kbytes in about 500 ms.
Claim 12
Dependent Claim
19 words
The method of claim 1, wherein at least 6 streams/hard disk drive are accommodated by said video server system.
Claim 13
Dependent Claim
27 words
The method of claim 1, wherein said video server system provides at least two of said video movies asynchronously to at least two users over a network.
Claim 14
Dependent Claim
37 words
The method of claim 1, wherein at step (b), for each of said video movies, movie block i is recorded on hard disk drive zone (((i/D)+(i mod D)) mod Z) of hard disk drive (i mod D).
Claim 15
Dependent Claim
53 words
The method of claim 13, wherein: at step (c), said user streams are organized into said slots such that each slot contains substantially N=S/D streams; and data for streams in said slots are stored in order in said buffer unit, and are read into and played out of said buffer unit in order.
Claim 16
Independent Claim
222 words
A method for achieving substantially average case hard disk drive transfer bandwidth and substantially average case hard disk drive seek time in a video server system having a plurality of D hard disk drives whereon blocks of video movies are stored before transfer to a buffer unit and play-out to a plurality of users over a network, the method comprising the following steps: (a) dividing each of said hard disk drives into Z substantially equal storage zones; (b) recording, for each of said video movies, movie block i on hard disk drive (i mod D), and in zone ((i/D) mod Z) of hard disk drive (i mod D); (c) for said video server system, defining substantially N=S/D user streams/slot using each of said zones, wherein a sum S of said user streams represents a maximum number of users that can access said video server system at one time without substantial degradation of video server system performance; wherein worst case bandwidth for each slot is determinable given worst case bandwidth information for transfers from each said zone; and (d) seeking information from said D hard disk drives by seeking to a nearest end of a set of N ordered seeks, and then proceeding through said set to a nearest subsequent position; wherein substantially average case hard disk drive transfer seek time is achieved.
Claim 17
Independent Claim
222 words
A method for achieving substantially average case hard disk drive transfer bandwidth and substantially average case hard disk drive seek time in a video server system having a plurality of D hard disk drives whereon blocks of video movies are stored before transfer to a buffer unit and play-out to a plurality of users over a network, the method comprising the following steps: (a) dividing each of said hard disk drives into Z substantially equal storage zones; (b) recording, for each of said video movies, movie block i on hard disk drive (i mod D), and in zone ((i/D) mod Z) of hard disk drive (i mod D); (c) for said video server system, defining substantially N=S/D user streams/slot using each of said zones, wherein a sum S of said user streams represents a maximum number of users that can access said video server system at one time without substantial degradation of video server system performance; wherein worst case bandwidth for each slot is determinable given worst case bandwidth information for transfers from each said zone; and (d) seeking information from said D hard disk drives by seeking to a nearest end of a set of N ordered seeks, and then proceeding through said set to a nearest subsequent position; wherein substantially average case hard disk drive transfer seek time is achieved.
Claim 18
Dependent Claim
68 words
The method of claim 15, wherein at step (a), Z=2, and wherein said video server system buffer unit includes a set of buffers providing at least two buffers per stream, wherein at any time interval one of said buffers receives blocks from said hard disk drives while a second of said buffers provides blocks to said users, which provided blocks were received during an immediately preceding time interval.
Claim 19
Dependent Claim
173 words
A disk layout unit for use with a video server that stores video movies before they are output to a buffer on a plurality of D hard disk drives that are each divisible into Z substantially equal storage zones, each of said video movies being divisible into i blocks, the disk layout unit including: a mechanism causing each a portion of said video movies to be recorded across all of said storage zones such that each of said storage zones such that each of said storage zones contains a substantially equal number of blocks of a video movie; wherein a substantially equal number of user streams is defined per a slot using each of said zones, wherein a sum S of said user streams represents a maximum number of users that can access said video server system at one time; wherein worst case bandwidth for each slot is determinable given worst case bandwidth information for transfers from each said zone; and wherein substantially average case hard disk drive transfer seek time is achieved.
Claim 20
Dependent Claim
173 words
A disk layout unit for use with a video server that stores video movies before they are output to a buffer on a plurality of D hard disk drives that are each divisible into Z substantially equal storage zones, each of said video movies being divisible into i blocks, the disk layout unit including: a mechanism causing each a portion of said video movies to be recorded across all of said storage zones such that each of said storage zones such that each of said storage zones contains a substantially equal number of blocks of a video movie; wherein a substantially equal number of user streams is defined per a slot using each of said zones, wherein a sum S of said user streams represents a maximum number of users that can access said video server system at one time; wherein worst case bandwidth for each slot is determinable given worst case bandwidth information for transfers from each said zone; and wherein substantially average case hard disk drive transfer seek time is achieved.
Claim 21
Dependent Claim
47 words
The disk layout unit of claim 17, wherein said mechanism causes each of said video movies to be recorded across all of said D hard disk drives such that each of said D hard disk drives contains a substantially equal number of blocks of a video movie.
Claim 22
Dependent Claim
30 words
The disk layout unit of claim 17, wherein said mechanism causes movie block i for each of said movie videos to be recorded on hard disk drive (i mod D).
Claim 23
Dependent Claim
35 words
The disk layout unit of claim 17, wherein said mechanism causes movie block i for each of said movie videos to be recorded in zone ((i/D) mod Z) of hard disk drive (i mod D).
Claim 24
Dependent Claim
26 words
The disk layout unit of claim 17, wherein each of said user streams is organized into said slots such that each slot contains substantially N=S/D streams.
Claim 25
Independent Claim
154 words
A system for achieving substantially average case hard disk drive transfer bandwidth in a video server system having a plurality of D hard disk drives, each divisible into Z substantially equal storage zones, whereon blocks of video movies are stored before transfer to a buffer unit, the system comprising: a disk layout unit causing a portion of each of said video movies to be recorded across all of said storage zones such that each of said storage zones contains a substantially equal number of blocks of a video movie; and an admission mechanism that defines a substantially equal number of user streams per a slot using each of said zones, wherein a sum S of said user streams represents a maximum number of users that can access said video server system at one time; wherein worst case bandwidth for each slot is determinable given worst case bandwidth information for transfers from each said zone.
Claim 26
Independent Claim
154 words
A system for achieving substantially average case hard disk drive transfer bandwidth in a video server system having a plurality of D hard disk drives, each divisible into Z substantially equal storage zones, whereon blocks of video movies are stored before transfer to a buffer unit, the system comprising: a disk layout unit causing a portion of each of said video movies to be recorded across all of said storage zones such that each of said storage zones contains a substantially equal number of blocks of a video movie; and an admission mechanism that defines a substantially equal number of user streams per a slot using each of said zones, wherein a sum S of said user streams represents a maximum number of users that can access said video server system at one time; wherein worst case bandwidth for each slot is determinable given worst case bandwidth information for transfers from each said zone.
Claim 27
Dependent Claim
47 words
The system of claim 22, wherein said disk layout unit causes each of said video movies to be recorded across all of said D hard disk drives such that each of said D hard disk drives contains a substantially equal number of blocks of a video movie.
Claim 28
Dependent Claim
57 words
The system of claim 22, wherein said disk layout unit causes movie block i for each of said movie videos to be recorded in a format selected from the group consisting of (i) recording on hard disk drive (i mod D), and (ii) recording on in zone ((i/D) mod Z) of hard disk drive (i mod D).
Claim 29
Dependent Claim
24 words
The system of claim 22, wherein said admission unit organizes said user streams into said slots such that each slot contains substantially N=S/D streams.
Claim 30
Dependent Claim
48 words
The system of claim 22, wherein said system further includes a buffer unit coupled to an output of said D hard disk drives, and wherein said slots are stored in order in said buffer unit, and are read into and played out of said buffer unit in order.
Claim 31
Dependent Claim
51 words
The system of claim 22, wherein: information is sought from said D hard disk drives by seeking to a nearest end of a set of N ordered seeks, and then proceeding through said set to a nearest subsequent position; and said system achieves substantially average case hard disk drive seek time.
References Cited (Backward Citations)
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2001-12-21 | 2002-06-22 | 2002-12-22 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2005-12-21 | 2006-06-22 | 2006-12-22 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2009-12-21 | 2010-06-22 | 2010-12-22 | $7700.00 | Window Closed / Lapsed |