System for and method of accessing blocks on a storage medium
View Patent ↗A system ( 100, 300 ) like a video on demand server has a storage medium ( 106 ) with a number of files ( 200 ) from which data can be fetched or in which data can be stored. A file contains a number of clusters ( 202, 204, 206 ) and each cluster contains a number of storage sectors ( 208 ) that are physically successively organized on the storage medium. When a new stream is requested, either for reading or writing, a block size ( 210 ) is determined for the new stream. The block size is large enough to support the rate of the stream and is chosen such that a cluster can be read with an integer number of blocks by evenly partitioning the size of the cluster into the size of the blocks reading the cluster.
1. A system for periodically fetching blocks of data from a storage medium and supplying the blocks in the form of streams, wherein the blocks of data are fetched from a file comprising logically successive clusters, a cluster having a cluster size C and having physically successive storage sectors for holding the data, the system comprising:
admission control means for controlling the admission of a new stream having a maximum bit rate c max , and
read means for in a period of maximum duration P fetching blocks of data from the storage medium for respective ones of the streams,
wherein the admission control means is arranged:
to determine a minimal block size B lower for the blocks for the new stream whereby a block of size B lower is sufficiently large to sustain consumption at rate c max during a period of length P,
to determine the number of times k a block of size B lower fits in the cluster of size C, to determine for k blocks to be used for reading the cluster a respective block size by evenly partitioning the cluster size C into the k block sizes so as to arrange that the cluster can be completely read by means of the k blocks, and to determine the minimal block size B lower according to the following equation:
B lower =P·c max.
2. A system as claimed in claim 1 , wherein the admission control means is arrange to determine k according to the following equation:
k= floor( C/B lower ),
in which C and B lower are expressed in numbers of sectors.
3. A system as claimed in claim 1 , wherein the admission control means is arranged to determine for the k blocks to be used for reading the cluster that
(C mod k) blocks have a block size equal to ceiling (C/k), and
(k−C mod k) blocks have a block size equal to floor (C/k).
4. A system as claimed in claim 1 , wherein the respective block sizes for the k blocks for reading the cluster are mutually the same and a divisor of C, the cluster size C and the respective block sizes being expressed in numbers of sectors.
5. A system as claimed in claim 1 , wherein the cluster size C has as divisors at least the numbers 2, 3, 4, 5, 6, 7, 8, 9 and 10, the cluster size C being expressed in numbers of sectors.
6. A system as claimed in claim 1 , wherein the admission control means is arranged to determine a maximum block size B upper for the blocks of the new stream whereby a block of size B upper is sufficiently small to be fetched from the storage medium within a period of length P while in the same period blocks are fetched for the existing streams, and wherein the admission control means is arranged to deny the admission of the new stream if that stream requires for at least one of the k blocks used for reading the cluster a block size larger than the maximum block size B upper .
7. A system as claimed in claim 1 , wherein the admission control means is arranged to determine the maximum block size B upper according the following equation:
P
≥
∑
j
=
1
n
+
1
B
j
r
min
+
s
(
n
+
1
)
in which:
B j, upper is the maximum block size of stream j,
r min is the guaranteed transfer rate from the storage medium,
n is the number of existing streams to which the new stream is added
s(x) is the switching overhead for x accesses to the storage medium in a period P, and
P is the maximum duration of period of fetching blocks from the storage medium.
8. A system for periodically writing blocks of data to a storage medium, whereby the blocks are received in the form of streams, wherein the blocks of data are stored into a file comprising logically successive clusters, a cluster having a cluster size C and having physically successive storage sectors for storing the data, the system comprising:
admission control means for controlling the admission of a new stream having a maximum bit rate c max , and
write means for in a period of maximum duration P storing blocks of data to the storage medium for respective ones of the streams,
wherein the admission control means is arranged:
to determine a minimal block size B lower for the blocks for the new stream whereby a block of size B lower is sufficiently large to store data received at rate c max during a period of length P,
to determine the number of times k a block of size B lower fits in the cluster of size C, to determine for k blocks to be used for writing to the cluster a respective block size by evenly partitioning the cluster size C into the k block sizes so as arrange that the cluster can be completely written by means of the k blocks, and to determine the minimal block size B lower according to the following equation:
B lower =P·c max.
9. Method of periodically fetching blocks of data from a file on a storage medium and supplying the blocks in the form of streams, wherein the blocks of data are fetched from a file comprising logically successive clusters, a cluster having a cluster size C and having physically successive storage sectors for holding the data, the method comprising the steps of:
controlling the admission of a new stream having a maximum bit rate c max , and
periodically fetching blocks of data from the storage medium for respective ones of the streams, a period having a maximum duration P,
whereby controlling the admission includes:
determining a minimal block size B lower for the blocks for the new stream whereby a block of size B lower is sufficiently large to sustain consumption at rate c max during a period of length P,
determining the number of times k a block of size B lower fits in the cluster of size C, determining for k blocks to be used for reading the cluster a respective block size by evenly partitioning the cluster size C into the k block sizes so as to arrange that the cluster can be completely read by means of the k blocks, and determining the minimal block size B lower according to the following equation:
B lower =P·c max.
10. Method of periodically writing blocks of data to a file on a storage medium, whereby the blocks are received in the form of streams and whereby the blocks of data are stored into a file comprising logically successive clusters, a cluster having a cluster size C and having physically successive storage sectors for storing the data, the method comprising the steps of:
controlling the admission of a new stream having a maximum bit rate c max , and
periodically storing blocks of data to the storage medium for respective ones of the streams, a period having a maximum duration P,
whereby controlling the admission includes:
determining a minimal block size B lower for the blocks for the new stream whereby a block of size B lower is sufficiently large to store data received at rate c max during a period of length P,
determining the number of times k a block of size B lower fits in the cluster of size C,
determining for k blocks to be used for writing to the cluster a respective block size by evenly partitioning the cluster size C into the k block sizes so as arrange that the cluster can be completely written by means of the k blocks, and determining the minimal block size B lower according to the following equation:
B lower =P·c max.