Electrical computers and digital processing systems: memory – Storage accessing and control – Control technique
Reexamination Certificate
1998-06-29
2001-03-20
Cabeca, John W. (Department: 2752)
Electrical computers and digital processing systems: memory
Storage accessing and control
Control technique
C709S231000, C710S006000, C710S052000
Reexamination Certificate
active
06205525
ABSTRACT:
BACKGROUND OF THE INVENTION
A system for retrieving blocks of data from a storage medium and supplying the data to users in the form of a plurality of at maximum n
max
data streams; wherein each data stream is in one of a plurality of states including at least a new and an active state, where a data stream upon creation is in the new state in which no sufficient data is present for consumption by a user and where for an active data stream a user may consume data; said system comprising:
for each data stream an associated buffer for storing data; and
a reader for reading in one sweep from the storage medium for each data stream of a selected group of data streams a predetermined size data block and for storing the read data blocks in the buffers associated with the data streams;
a scheduler for repeatedly selecting the group of data streams for which a data block of a predetermined size needs to be read during a next sweeping operation of the reader; the group comprising active data streams whose associated buffers have room for storing the data block; and causing the reader to read data for the selected group.
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 a variable bit rate MPEG-2 encoding.
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. Typically, in successive intervals data blocks of a predetermined size are read for a group of data streams. To minimise disk access overhead, the data blocks for streams of the group are read in a sweeping movement of the head(s) of the disk(s) (e.g. from the outer edge to the inner edge of the disk or vice versa). The size of the block is determined such that in a worst case scenario, wherein a maximum number of streams allowed by the system all require data, no underflow of buffers can occur. As such, the block size corresponds to the number of data elements required to survive consumption at the maximum allowed bit-rate for the worst case duration of a sweeping movement wherein a data block is read for the maximum number of streams.
A conventional scheduling algorithm for a fixed consumption rate system is the so-called SCAN algorithm. In this algorithm at fixed regular intervals for each stream a fixed-size data block is read and stored in the buffer. Typically, for each stream a buffer with capacity for storing two blocks is used: one for reading data from the disk and one for supplying data to the user(s). Normally, the sweep and the buffer reading are synchronised: the buffers for all streams are read from the same buffer position and a new sweep is started at the moment when all read positions change from one block to the other (implying that in each buffer a block has become empty). The interval typically corresponds to a worst case duration of a sweeping movement wherein a data block is read for the maximum number of streams allowed by the system. Disk access is in the order in which the data for the streams happens to be located on the disk. No pre-conditions are made for storing the data on the disk, implying that a specific stream in one sweep may be serviced first and in a next sweep may be serviced last. As a consequence, a buffer of twice the block size is required.
Within a variable consumption rate system, different streams may empty a predetermined block of the buffer at different moments. Typically, during a reading operation data is only read for streams whose buffers have room for a predetermined size block of data. For those streams a block of data of the predetermined size is read. The other streams are skipped and may be serviced during the next interval. Due to the variable rate, different streams may empty one of the buffer blocks at different moments. To be prepared for the worst case for each stream a buffer of three blocks is required. As an example. a stream may have almost (but not entirely) emptied a block at the beginning of a sweep. This results in the stream being skipped for this sweep, since no entire block can be read. At the beginning of the next sweep, the stream may have almost emptied two blocks, resulting in one block being loaded in this sweep. To cope with the situation that the stream may be serviced last during this sweep, a total of three blocks are required. Such a scheduling algorithm is known as the Triple Buffering Algorithm. Due to streams not requiring a block being skipped, the duration of reading data in a sweeping movement is variable, bounded by a worst case sweep in a situation where the maximum number of streams all require a new data block.
New streams are only allowed to enter a not yet fully loaded system after a sweeping operation has been completed. Furthermore, an initial block of data needs to be read in a subsequent sweep. If no capacity is available in the subsequent sweep, the delay becomes even longer. As such the duration of a sweep determines the access time for new streams.
SUMMARY OF THE INVENTION
It is an object of the invention to provide a system of the kind set forth allowing for a reduced access time.
To achieve this object, the system according to the invention is characterised in that the scheduler is operative to variably determine the size of the data block for each next sweeping operation through an expression that, with respect to a number of data streams, is substantially based on an actual number n
act
of active data streams. The inventor has realised that although it is required to dimension the system for a worst case scenario, wherein for the maximum number of streams allowed by the system a data block is read of a size sufficient to survive consumption at the maximum allowed bit-rate for the worst case duration of a sweeping movement, the size of the block to be read in a less demanding situation can be smaller. Instead of basing the size on maximum allowed number of data streams, the size is based on the actual number n
act
of data streams which at that moment are active. In principle this technique can be applied for both fixed rate and variable rate systems. Particularly for video on demand systems, wherein significant changes in active number of data streams occur, the access time can be significantly reduced if the system is not fully loaded. For instance, if the system is loaded for 50% (i.e. the number of active streams is half the maximum allowed number), on average the duration of a sweep would be roughly half of the duration co
Cabeca John W.
Piotrowski Daniel J.
Tran Denise
U.S. Philips Corporation
LandOfFree
System for supplying data steams 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 supplying data steams, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System for supplying data steams will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2468019