Dynamic magnetic information storage or retrieval – General processing of a digital signal – Data in specific format
Reexamination Certificate
2001-05-30
2003-11-04
Faber, Alan T. (Department: 2651)
Dynamic magnetic information storage or retrieval
General processing of a digital signal
Data in specific format
C360S047000, C709S241000, C725S096000
Reexamination Certificate
active
06643083
ABSTRACT:
The invention relates to a system for in cycles retrieving blocks of data from a storage medium and supplying the blocks in the form of data streams to users, wherein a number of the blocks are stored multiple times in respective storage units of the storage medium.
The invention further relates to a method of in cycles retrieving blocks of data from a storage medium and supplying the blocks in the form of data streams to users, wherein a number of the blocks are stored multiple times in respective storage units of the storage medium.
The International Patent Application published under number WO 98/54657 describes a system that may be used in multimedia server, or more specifically, in a video-on-demand or near-video-on-demand server. A requirement in this system is to supply a continuous, uninterrupted stream of data to each active user. Data is read from a conventional storage medium, such as hard disks, which are arranged in a disk array, such as a RAID system. In general, a distinction can be made between a fixed consumption rate and a variable consumption rate system. In a fixed consumption rate system data is supplied to a user as a fixed rate data stream. Usually, the rate is identical for each stream in the system. An example of such a system is a near video-on-demand system, wherein a number of films can be played in parallel and the same film may be played several times in parallel, where regularly, for instance ever 15 minutes, a new copy of the same film is started. In a variable consumption rate system the rate at which a user consumes data varies over time. A maximum consumption rate can be defined for each data stream. In practice, an identical maximum consumption rate is used for all streams, although it may be possible to support streams with different maximum consumption rates. Variable consumption rate systems are, for instance, used for systems which support VCR-like functions such as pause or slow motion or systems which use a data compression technique with variable bit rate like MPEG-2.
To supply data to a user as a continuous stream, special scheduling schemes for reading data from the disks are required with an appropriate scheme for temporarily buffering the read data before the data is supplied to the user. The system operates in cycles, whereby in a cycle a stream consumes data from a buffer while new data is read from disk and supplied to the buffer for future consumption. For a fixed consumption rate system, at fixed regular intervals for each stream a fixed amount of data (sufficient to last one cycle) is read and stored in the buffer. Within a variable consumption rate system, different streams may empty a predetermined block of the buffer at different moments. During a cycle only data is read for streams whose buffers have room for a block of data. Other streams are skipped. As a consequence, the duration of a cycle in a variable consumption system is variable, bounded by the situation in which all active streams require a new block of data.
The storage medium in the known system comprises a number of independent storage units. The performance of a storage unit is limited and the system is designed in such a way that during a cycle of maximum duration, each storage can at least read a certain maximum number of data blocks. During normal operation, none of the storage units should be overloaded with requests, i.e. should not be requested to read more data blocks in one cycle than this maximum number of blocks. To improve the overall bandwidth of the storage medium, in the known system a portion of the data blocks is stored multiple times in the storage medium, whereby different copies of a block are stored in different, randomly chosen storage units. The scheduler of the system then has the freedom to choose the retrieval of such a duplicated block from one of the storage units on which the copies reside. This freedom is used to balance the load of the storage units so that the storage medium as a whole can read more data blocks per cycle. The probability that none of the storage units is overloaded can be chosen arbitrarily high by choosing a larger portion of the data blocks that are stored multiple times.
It is an object of the invention to provide a system as described in the preamble with a comparatively more efficient use of the storage medium. This object is achieved according to the invention in a system that comprises:
a determining means for determining a group of blocks of which it is expected that they can be read within one of a number of cycles spanning a planning horizon,
a scheduler for, for each block of the group, selecting from the set of storage units in which the block is stored one storage unit from which the block is to be read, the scheduler being operative to balance the load on the storage units,
a reader for in response to a block read request reading the corresponding block from the selected storage unit for supply in the corresponding stream.
In addition to the freedom to choose for some of the blocks from which storage unit the block will be read, the system according to the invention has the freedom to choose for some of the blocks during which cycle the block will be read. This additional freedom can be used to store a smaller portion of the blocks multiple times in the storage medium, while maintaining a comparable high probability that none of the storage units will be overloaded. By duplicating a smaller portion of the data blocks, obviously less storage space is required to store the file containing the film to be supplied to the user. Duplicating a smaller portion of the data blocks results in an increase of the probability of overload of a storage unit when assessed for a single cycle. However, the system according to the invention looks ahead a number of cycles and can prevent an overload situation by scheduling a critical block read request to another cycle. The probability that an actual overload for a storage unit would occur is very small, since that will only happen if for each of the cycles in which a certain block read request can be scheduled such a critical condition appeared that no additional read request can be allowed. For every cycle alone this is, even with a smaller portion of duplicated blocks, a small probability. Therefore, the probability that this would happen for all relevant cycles is very small.
Duplicating a smaller portion of the data blocks has a further advantage in that less data needs to be written to the storage medium. So less bandwidth of the storage medium is required for adding new titles. In a system where new titles are added on-line, i.e. while the system remains operational for supplying data to users, it is important that a smaller fraction of the available bandwidth needs to be reserved for writing data since a larger fraction can then be allocated to the retrieval of data for users thus making it possible to service more users.
In an embodiment of the system according to the invention, blocks are identified that must be read in the present cycles and easily allows the separate scheduling of reading those blocks in the present cycle.
In an embodiment of the system according to the invention, the classification of the group into the subgroups allows for different handling of the block read request according to their specific needs and characteristics.
In an embodiment of the system according to the invention, by balancing the load for the second subgroup, the storage units have more capacity available to schedule for the present cycle more read requests for blocks that are not yet necessary but will probably become necessary in the near future. By already scheduling and reading those future blocks in the present cycle, the probability for no overload in the future.
In an embodiment of the system according to the invention, by taking the expected block read request for all cycles in the planning horizon in to account, a better scheduling can be made for those cycles. This increases the total number of blocks that can be read by the storage units and therefore increas
Egner Sebastian
Korst Johannes Henricus Maria
LandOfFree
Method and system for retrieving blocks of data from a... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and system for retrieving blocks of data from a..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and system for retrieving blocks of data from a... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3126929