Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
2000-03-21
2002-11-05
Mizrahi, Diane D. (Department: 2175)
Data processing: database and file management or data structures
Database design
Data structure types
C707S793000, C707S793000, C707S793000, C707S793000, C710S052000, C710S018000
Reexamination Certificate
active
06477541
ABSTRACT:
The invention relates to a system for retrieving blocks of data, such as audio and/or video, from a storage medium and supplying the blocks in the form of a plurality of streams to users, wherein a stream of a first class of the streams may have an actual bit rate between a first minimum bit rate and a first maximum bit rate, the first minimum bit rate and the first maximum bit rate potentially being identical thus yielding a constant bit rate, wherein a stream of a second class of the streams may have an actual bit rate between a second minimum bit rate and a second maximum bit rate, the second minimum bit rate and the second maximum bit rate potentially being identical thus yielding a constant bit rate, and wherein the first maximum bit rate is substantially higher than the second maximum bit rate, the system comprising: for each stream an associated buffer for storing the blocks of data; a reader for in a sweep reading a data block from the storage medium for each stream of a selected group of the streams and for storing the read blocks in the respective buffers; and a scheduler for repeatedly selecting the group of the streams for which a block is to be read in a next sweep of the reader.
The invention further relates to a method of retrieving blocks of data, such as audio and/or video, from a storage medium and supplying the blocks in the form of a plurality of streams to users, wherein a stream of a first class of the streams may have an actual bit rate between a first minimum bit rate and a first maximum bit rate, the first minimum bit rate and the first maximum bit rate potentially being identical thus yielding a constant bit rate, wherein a stream of a second class of the streams may have an actual bit rate between a second minimum bit rate and a second maximum bit rate, the second minimum bit rate and the second maximum bit rate potentially being identical thus yielding a constant bit rate, and wherein the first maximum bit rate is substantially higher than the second maximum bit rate, the method comprising the steps of: for each stream storing the blocks of data in an associated buffer; in a sweep reading a data block from the storage medium for each stream of a selected group of the streams and storing the read blocks in the respective buffers; and repeatedly selecting the group of the streams for which a block is to be read in a next sweep.
Such a system and method are described in the paper “Disk scheduling for variable-rate data streams”, J. Korst, V. Pronk, and P. Coumans, Proceedings European Workshop on Interactive Distributed Multimedia Systems and Telecommunication Services, IDMS '97, Darmstadt, September 10-12, Lecture Notes in Computer Science, 1309 (1997) 119-132. The known system is a video on demand server, also called multimedia server, which provides a plurality of users with audio and video data, which is stored on the disks of the system. The system repeatedly fetches a block of data for each of the users and stores it in respective buffers, each of which has room for a number of data blocks. The buffers are implemented in relatively fast Random Access Memory. A user consumes data from a corresponding buffer via some communication network at a rate that may vary between zero and a maximum consumption rate. Users may have mutually different maximum consumption rates.
In order to use the disks efficiently, the known system operates in so-called sweeps, also called rounds, whereby blocks are fetched from disk in a single sweeping movement of the disk reading heads. A scheduler determines at the beginning of a sweep which buffers have enough free space for receiving a new block. The scheduler then orders a block of data for these buffers from the disk reader. The size of the buffer of each user is designed in such a way that the buffer does not become empty before actually receiving a new block. The cited paper describes for instance the double buffer algorithm for fixed consumption rates and the triple buffer algorithm for variable consumption rates. In the double buffer algorithm, the buffer can contain two blocks of data and in the triple buffer algorithm, the buffer can contain three blocks of data. A block must contain enough data for a user to consume at a maximum rate during the period of a worst-case sweep. The size of a block of each of the streams must therefore at least be equal to the product of the maximum duration of the sweep and the maximum consumption rate of the respective stream. The duration of a sweep is determined by the actual blocks to be fetched, since each block requires a switch time for locating the block on the disk and a transfer time for actually reading the block from the disk at a given transfer rate. The switch time and the transfer rate are dependent on the specific hard disks used in the system. The transfer time is further dependent on the size of the block to be read, since a larger block will require a longer time to be read. Given the above constraints, the minimum respective block sizes are calculated on the basis of the performance parameters of the hard disks of the system and on the basis of the required maximum number of users to be serviced.
It is an object of the invention to provide a system as described in the preamble in which the total memory required to implement the buffers for the streams is less than in the known system. This object is achieved according to the invention in a system, which is characterized in that the scheduler is operative to select a stream of the second class less often in the group for which a block is to be read than a stream of the first class, such in the situation where the actual bit rate of the stream of the second class equals the second maximum bit rate and the actual bit rate of the stream of the first class equals the first maximum bit rate. So in the steady situation, where both streams are consumed at their respective maximum rates, the stream of the second class, i.e. the one with the smaller consumption rate, is serviced less often. In the context of this description, servicing a stream means that the scheduler verifies whether the buffer of this stream has enough free space to receive a new block and if such is the case, selects this stream into the group for which a block is to be read in the next sweep, and have this block read. As a result of servicing this stream less often, the sweep or sweeps in which the data stream of the second class is not serviced will be shorter. This means that the size of a block for the stream of the first class may be designed smaller because it must contain now at least sufficient data to be consumed during the shorter period of the sweep. The penalty for not servicing the stream of the second class in every sweep is that the size of a block for this stream is to be designed larger, since it must contain enough data to be consumed during a number of sweeps. It can be shown that the decrease of the size of the block for the stream of the first class is larger than the increase of the size of the block for the stream of the second class. Therefore, the sum of the size of the blocks has decreased and the overall memory required for the buffers in the system has decreased. The fact that the sum of the block sizes has decreased is caused by the fact that the consumption rate of the stream of the second class is smaller than the one of the stream of the first class. In the known system, this has the result that the block size for the stream of the second class is relatively small and that the switch time for such a block is relatively large. By servicing the stream of the second class less often, the relative contribution of the switch time becomes smaller and the disk is being used more efficiently.
An embodiment of the system according to the invention is described in claim 2. In the steady situation of this embodiment, a high bit rate stream is serviced every sweep and a low bit rate stream every k sweeps, which provides a simple mechanism to service a low bit rate stream less often than a high bit rate stream. Choosing k in d
Coumans Pascal F. A.
Korst Johannes H. M.
Koninklijke Philips Electronics , N.V.
Mizrahi Diane D.
Piotrowski Daniel J.
Veillard Jacques
LandOfFree
Multimedia 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 Multimedia server, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Multimedia server will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2926002