Electrical computers and digital processing systems: multicomput – Computer-to-computer protocol implementing – Computer-to-computer data transfer regulating
Reexamination Certificate
1998-05-21
2002-07-02
Wiley, David (Department: 2158)
Electrical computers and digital processing systems: multicomput
Computer-to-computer protocol implementing
Computer-to-computer data transfer regulating
C348S086000
Reexamination Certificate
active
06415328
ABSTRACT:
The invention relates to a system for retrieving blocks of data, such as audio and/or video data, from a storage medium and supplying the blocks in the form of a plurality of at maximum N
max
data streams to users, wherein each data stream has an identical maximum consumption rate of R
max
data elements per second and the storage medium has a bandwidth of at least N
max
*R
max
data elements per second; the storage medium comprising a plurality of storage units.
A system of this kind is used in a multimedia server and, more specifically, in a video on demand or near video on demand server. A general requirement in such systems is to supply a continuous, un-interrupted stream of data to each active user. Typically, 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, typically, 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, every five or fifteen 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. Typically, a maximum consumption rate can be defined for each data stream. In practice, usually an identical maximum consumption rate is used for all streams, although it may be possible to efficiently support streams with different maximum consumption rates ( e.g. one maximum for an audio stream and another maximum for a combined video and audio stream). 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 scheme with a variable bit rate, such as MPEG-2.
To supply data to a user as a continuous data 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. For a fixed consumption rate system, typically, at fixed regular intervals for each stream a fixed amount of data (sufficient to last one period) 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. Typically, during an interval 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 the interval for reading data is variable, bounded by the situation in which all active streams require a new data block.
To guarantee a large disk bandwidth, which is required when all data streams consume at the maximum data rate, the data is usually striped across all disks in the array. Particularly for variable data rate systems this is achieved by partitioning each data block over all disks, such that a request for reading this block implies a disk access to each of the disks. As a result, the load on the disks is optimally balanced.
In general the number of disks in the disk array is determined by the required bandwidth in view of the number of data streams which are supported in parallel. As such, the number of disks linearly grows with the maximum number of data streams. In order to ensure that the effectiveness of accessing a disk remains more or less constant, the size of a block read from an individual disk for one data stream should remain the same (reading too small blocks of a disk increases the overhead, particularly if the size drops below the size of a track). As a consequence, the size of the accumulated block, which is striped over all disks, grows linearly with the number of disks and, as such, with the maximum number of data streams. This results in the size of the buffer also growing linearly with the maximum number of data streams. Since for each data stream a buffer is required, the combined effect is that the total size of the buffer depends substantially quadratically on the maximum number of data streams, making the costs of the buffer a dominant factor, particularly, for systems supporting a large number of data streams. A further negative effect is that the response time of the system for allowing a new data stream to become active increases substantially linearly, since the time interval required to re-fill the buffers increases linearly and during such interval no new users can enter the system.
It is an object of the invention to provide a system of the kind set forth in which the buffer costs grow substantially linearly with the maximum number of supported data streams. A further object is to provide such a system wherein the response time remains substantially the same regardless of the maximum number of supported data streams.
To achieve this object, the system according to the invention is characterised in that a predetermined selection of blocks is stored multiple times in the storage medium by individual blocks of the selection being stored in its entirety in at least two different and randomly selected storage units; and the system comprises:
a scheduler for controlling reading of blocks for the data streams from the storage medium by, for each block, selecting from a corresponding set of all storage units in which the block is stored one storage unit from which the block is to be read and assigning a corresponding read request to the selected storage unit; the scheduler being operative to select the storage unit from the set such that the load on the plurality of storage units is balanced; and
a reader for, in response to a block read request, reading the corresponding block from the assigned storage unit for supply in the corresponding data stream to a user.
By ensuring that a block is stored in at least two different storage units, the scheduler has a choice in selecting from which of the storage units the block is read during play-back. This makes it possible for the scheduler to choose the storage units in such a way that the load on the storage units is balanced. By storing the blocks in randomly selected storage units a relatively even load can be achieved during playback even for variable rate systems for which it is otherwise difficult or even impossible to predict how the load on individual storage units will develop in time for the active streams. In a simple system, all blocks of all titles are stored twice in the system, i.e. in two different storage units of the system. The selection of blocks may alternatively be a part of all blocks, where the remaining blocks are stored only once.
The solution offered by the system according to the invention benefits from the insight that, unlike the bandwidth, capacity of the storage medium is not a major determining factor and increasingly will become less of a determining factor since capacity of hard-disks grows on average at a higher rate (typically 60% a year) than the bandwidth (typically a growth of 40% a year). Assuming that in two years time a typical disk will have a storage capacity of 25 Gbyte and a guaranteed data rate of 85 Mbits/sec, the following two scenario's can be envisioned. In a first scenario, a video on demand version of the system according to the invention is used to offer a range of up to 20 films, like in a cinema, to a maximum of a 1000 users. The films are encoded using MPEG2 at an average rate of 4 Mbits/sec. Assuming that on average a film has a length of 90 min., a total storage capacity of 90*60*4.10
6
=21.6*109 bits=2.5 Gbyte per film is required, resulting in a total required storage capacity of approximately 50 Gbyte. If all blocks are stored twice, the capacity will have to be approximately 100 Gbyte, corresponding to 4 or 5 disks. To be able to support simultaneously 1000 users, a total guarant
Piotrowski Daniel J.
Wiley David
LandOfFree
System for retrieving data in a video server does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with System for retrieving data in a video server, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System for retrieving data in a video server will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2874247