Filing of Variable-Bit-Rate Video Information on Zoned Disks

The present invention relates to an architecture of filing variable-bit-rate (VBR) video data on zoned disks, especially to an architecture and method of filing VBR data on zoned disks based on the character of the VBR data and the character of the zoned disk. In the present invention, a "constant read-time" approach is disclosed to determine the filing layout of data.

As the advances of the networking technologies, the compression techniques and the storage devices, computer media are widely utilized in many applications, such as entertainment and education. When the video media is the case, the video contents are usually stored as a sequence of frames where each frame represents a single image snapshot. During the play-back, the timing of play-back of the video is critical in maintaining the quality of the video. Especially in the case of remote play-back, each frame has to be delivered to and played-back by the user work station within a time limit in order not to produce observable jitters.

Another reason for the timing constraint is to synchronize the video media with other media, such as voice and text, in a multimedia application. In order to sustain the system with high quality-of-service (QoS), the storage system has to guarantee its performance as it plays a major role in supporting a real-time video media.

Besides the real-time criteria, designing a video storage system needs to deal with the storing and the retrieving of large amount of video data. Compression techniques are popular in reducing the size of the video files. For instance, the MPEG 1 data compression standard can reduce the file size up to one fortieth of the original. Due to the nature of the compression algorithms, the compressed video frames have variable sizes where the term VBR video comes from.

In order to improve the throughput of the disks, the conventional design of the storage systems are focused on the scheduling and the data placement of the disks so that the seeking time of the data may be reduced. Of late, zoning technique has been developed to increase the capacities disks. Under the zoning design, a zone in a disk comprises a group of contiguous track with the equivalent number of sectors per track. There are typically 3 to 20 zones on a hard disk, and the number is likely to be doubled by the end of this decade. FIG. 1 shows the distribution of zones and tracks of a zoned disk with 3 zones. In order to fully use the disks' magnetized surface, there are more sectors in the outer zones than in the inner zones. In other words, the outer zones have larger track size then has the inner zones. Another effect of disk zoning is that the disk has higher data transfer rates (or bandwidths) in the outer zones than in the inner zones, as disks spin at a constant angular velocity. Such zoning technology helps to increase the throughput of disks of video servers. Generally speaking, storing larger and more frequently accessed blocks in the outer zones, and smaller and less frequently accessed blocks in the inner zones can obtain higher average throughput.

The effective bandwidth of a zone disk is not guaranteed due to the file layout and the access pattern of the blocks. To alleviate this problem, a concept of "logical track" is disclosed. A logical track means a group of tracks consisting of one track from each zone. Every logical track has a constant size and is treated as an access unit so that a uniformed bandwidth of the zone disks can be achieved. However, the overall disk throughput is low due to excessive seeking operations. Moreover, since the number of tracks differs from zone to zone, disk space in the zones with more tracks is wasted.

A track-pairing scheme was presented in the conventional art. In this scheme, two complementary tracks are grouped into a track pair and in filing the data, a pair of tracks is treated as a unit. This approach is a less restrictive alternative of the previous approach that takes a compromises between the uniformed bandwidth and the disk access time.

In the conventional art, also disclosed are an FIXB data placement method and a VARB data placement method. These methods work with a region-based data placement scheme which places data on zoned-disks for the continuous media services of constant bit-rate data.

In the FIXB method above, the block size is constant in every zone, while in the VARB method, the retrieval time of a block is constant in every zone. In both methods, data blocks in the outer zones are read in advance so to compensate the access of data in the inner zones. However, both FIXB and VARB methods are constrained by the parameters of the zones which parameters depend on the manufacture of the disks, and result in excessive waste of storage space, long initial delay, and large buffer requirements. These approaches may only apply to data with constant bit-rate but not to data with variable bit-rate (VBR).

For the storage of VBR data, Chang et al. presented the constant data-length (CDL) data placement and constant time length (CTL) data placement methods (Ed Chang and Avideh Zahkor: "Cost analyses for VBR video servers", Proceedings of SPIE Multimedia Computing and Networking, pp.381-397, 1996). The drawback of the CDL method is large buffer requirement, while CTL data placement causes the problem of disk fragmentation. Both methods suffer from complicated admission control due to the variable retrieval duration. They further proposed a hybrid method to compromise CDL and CTL. In this hybrid method, data are stored under the CTL data placement but retrieved a variable number of blocks in each service round.

Neufeld et al. presented a read ahead buffering algorithm to contribute to said hybrid method (Gerald Neufeld, Dwight Makaroff and Norman Hutchinson: "Design of a variable bit rate continuous media file server for an ATM network", Preceedings of SPIE Multimedia Computing and Networking, pp. 370-380, 1996). This approach accommodates more users by using a pre-fetched-buffering technique. A generalized CDL method was proposed for VBR video data by Biersack et al. (Ernst Biersack, Frederic Thiesse and Christoph Bernhardt: "Constant data length retrieval for video servers with variable bit-rate streams", Proceedings of International conf. On Multimedia Computing and Systems, pp. 151-155, 1996). In this method VBR video data are cut into segments to which the CDL method is applied. The method helps to reduce the buffer requirement. These improvements, however, did not solve the problems of both CDL and CTL methods.

The purpose of this invention is to provide a novel filing architecture for VBR data on zoned disks.

Another purpose of this invention is to provide a filing architecture for VBR data on zoned disks with which the buffer requirement in the real-time play-back of the data may be reduced or even minimized.

Another purpose of this invention is to provide a segmented algorithm to further reduce the time and the complexity in filing and retrieving VBR data on zoned disks.

According to this invention, VBR data are stored on zoned disks. An optimization of data placement for VBR data on zoned disks is presented to minimize the server buffer size and to maximize the utilization of the disks, under the constraint of the timing in playing-back the VBR data. In this invention, a "constant read-time" (CRT) approach is disclosed where a constant period of time is allocated to retrieve each data block. As in this invention, the distribution of the data is determined by the sequence of retrieving the data, a multistage graph is used to describe the structure of the filing system of this invention. The invention also provides a segmentation algorithm to reduce time and space complexities in the processing of the VBR data.

The above and other purposes and advantages of this invention can be clearly understood from the detailed description by referring to the following drawings.

FIG. 1 illustrates the distribution of zones and tracks on a zoned disk with 3 zones.

FIG. 2 illustrates the flow chart of determining the filing architecture of VBR data on zoned disks of this invention.

FIG. 3 shows the relation between the buffer requirement and the utilization rate of the disk in playing-back the video data of the famous movie: "Starwar".

FIG. 4 illustrates an example of a multistage path map.

FIG. 5 illustrates a multistage path map in retrieving data from disks, as applicable in the embodiments of this invention.

Table 1 shows the block size and the block numbers in each zone and the number of the zero blocks, as the data file of movie "Starwar" is stored under the filing architecture of this invention.

Table 2 shows the buffer requirement and the utilization rates in other embodiments of this invention.

Table 3 shows the relation between the number of segmentation and the operation time, while a segmentation algorithm is used.

The following is a detailed description of the filing architecture of variable bit-rate (VBR) data on zoned disks of this invention.

In the present invention, the VBR data are stored in zoned disks to be accessed (retrieved) by a number of clients. Under the architecture of this invention, the distribution of data (files) on the zoned disks is determined by the sequence of retrieving the data. In playing-back the data, a service round in which each of a collection of clients is served in sequence for one time, is considered a unit of service.

In order to satisfy the need of real-time service, the distribution of data on the disks, i.e., the scheduling of retrieving the data from the disks, shall comply with the timing constraint of the play-back. In this invention, a "constant read-time" (CRT) algorithm is presented to filing the VBR data on zoned disks such that the timing constraint and other constraints may be complied with. Under the CRT algorithm, a constant read-time is allocated to each data block and each admitted user is allocated with a fixed time interval for every service round. A user may decide to be active or idle in a service round. In each access, a user reads a data block from one of the zones in the disk.

Although it is not intended to limit the scope of this invention, it is found that, while a constant read-time is allocated to each data block, under the structure of the zoned disk, a retrieval path map may be used to determine the retrieval schedule of the data and the optimal distribution of data on zone disks may be obtained. Under such distribution of data, while the zoned disk is the case, the buffer requirement in the server may be minimized. While the access time for every user is fixed, the admission control is trivial where only the residual access time is checked.

The following is a description of the method for determining the data distribution on zoned disks of this invention. FIG. 2 illustrates the flow chart of determining the filing architecture of VBR data on zoned disks of this invention. As shown in this figure, the steps to determine the filing structure of VBR data on zoned disks include:

At 101 the number of the zero blocks, i.e., the idle service rounds, (N.sub.0) is first determined. This number can be decided according to the data transfer rate (or bandwidth) of the disk and will be described in details hereinafter.

At 102 the play-back time of a block (s) is determined and, based on this play-back time, the size of the blocks (B.sub.i) and the number of blocks in each zone (N.sub.i) are determined. In this invention, size of data allocated to each zone is not constant but is proportional to the storage capacity of a zone. This helps to balance the utilization of the space of the zones.

At 103 a multistage retrieval path map is used to determine the sequence of the play-back ({X.sub.i }) such that the buffer requirement may be minimized.

At 104 the data are stored in the zoned disks according to the play-back sequence.

The above steps will be described in details in the followings.

Number of the Zero Blocks

In the first step, the number of the zero blocks (N.sub.0) is determined. This block number can be determined according to the utilization rate of the disk.

It is found that the buffer requirement and the utilization of the disk in playing-back the data are relative. FIG. 3 shows the relation between the buffer requirement and the utilization rate of the disk in playing-back the video data of the famous movie: "Starwar". This figure is obtained by simulations. As shown in this figure, when the utilization rate of the disk is greater than a threshold, the buffer requirement increases with the decrease of number of the zero blocks. While the utilization rate is below the threshold, the buffer requirement starts to increase. This means, when introducing too many zero blocks, i.e., too many idle service rounds, the size of data blocks shall be increased to meet the utilization rate of the disk. Therefore, it results in large buffer size. The utilization can thus be determined according to the purpose of the application.

Once a utilization rate is selected, the number of the zero blocks (N.sub.0) may be determined according to the following equation: ##EQU1##

where N is the number of service rounds.

Here, a general utilization rate may be designated for use in video data with similar characters.

Determination of Block Sizes and Block Numbers in the Zones

According to this invention, the quantity of data allocated to each zone is not fixed but is proportional to the size of the zone, as follows: ##EQU2##

wherein L is the length of the data file (bytes), L.sub.i is the length of the data allocated to the i.sup.th zone and C.sub.i is the capacity of the i.sup.th zone. This proportional allocation helps to balance the space utilization among zones. The number of blocks of each zone may be decided as follows: ##EQU3##

wherein B.sub.i is the block size of the i.sup.th zone, i.e., the i.sup.th service round.

From equation (3) we have: ##EQU4##

From equation (2) we further have: ##EQU5##

In the present invention, the block size in each zone is fixed and the block size is proportional to the data transfer rate in the zone. We thus have: ##EQU6##

wherein B.sub.i is the block size in the i.sup.th zone, D.sub.i is the data transfer rate in the i.sup.th zone, z is the number of zones in a disk and s is the play-back time. Equation (5) can thus be replaced by: ##EQU7##

And thus: ##EQU8##

Because the play-back time for each zone is fixed, the block size (B.sub.i) can be determined by s.times.D.sub.i and the block number (N.sub.i) can be determined by ##EQU9##

Distribution of Data

Suppose the intermediate points of a retrieval sequence are denoted as (n.sub.0, n.sub.i, . . . ,n.sub.k) wherein n.sub.i stands for the number of the blocks in the i.sup.th zone which have been played-back in the sequence. At the initial stage, all n.sub.i 's are set to be 0. Once a block in the i.sup.th zone is retrieved, n.sub.i is incremented by 1.

For example, if a client retrieves one block from the first zone at service round 1 and one block from the second zone at service round 2, the intermediate points shall be (1,1,0). In this invention, the intermediate points will be used to describe the data distribution on the zoned disks.

From the previous discussion, it is found that the optimization of the data distribution on disks may be considered an optimization of data retrieval, under a combination of several factors, as follows: We have k zones. Each zone has N.sub.z blocks which are of the same size. Each time a client is served (a "service run") and in each service run one block is retrieved where the length of data needed by a client is l.sub.i in the i.sup.th service run. A retrieval sequence {Z.sub.i } may be found:

wherein K is the number of zones in the disk, N is the run number of a data file. When Z.sub.i =0, no data is retrieved. When Z.sub.i =g, the g.sup.th zone is retrieved a block in the i.sup.th service run. The sequence set {Z.sub.i } defines a possible retrieval schedule and the place of blocks in the disk as well.

FIG. 4 illustrates a directed multistage retrieval path map. As shown in this figure, the path denotes a possible retrieval sequence of the data from a zoned disk. This model, however, may be used to describe the distribution of blocks in a zoned disk.

A simple example will be used to illustrate this mapping model. Given a sequence set {Z.sub.i }, {Z.sub.i }={1, 0, 2, 1}, to denote that a block is retrieved from 1.sup.st zone in the first service run, no data is retrieved in the second service run, one block is then retrieved from the 2.sup.nd zone in the fourth service run and one block is retrieved from the 1.sup.st zone in the final service run. The path (and the intermediate points) of this retrieval sequence is shown in FIG. 4.

As different paths may be given to each sequence set {Z.sub.i }, the nodes (intermediate points) of the map may be labeled by vectors (n.sub.0, n.sub.1, . . . , n.sub.z).

In order to find a path with the least buffer requirement, under the timing restraint L.sub.i, the buffer requirement may be determined by selecting a retrieval sequence set or to select a retrieval path. The buffer requirement of each service run may be calculated by: ##EQU10##

With graphic variables, we have: ##EQU11##

wherein bk represents the size of the k.sup.th block during the retrieval sequence.

It is thus obvious that B.sub.i is constant during the retrieval. The buffer requirement under a retrieval sequence set or path is: ##EQU12##

As described above, the optimized data distribution on the disk may be described with a model of the retrieval path. FIG. 5 illustrates a multistage path map in retrieving data from disks. Let G(V,E) represent the paths where V represents the nodes and E represents the connections of the stages. In this function, nodes V are divided into N stages (corresponding to the zones of the disk). The nodes in the j.sup.th stage may be denoted as V.sub.j. Here every node V.sub.j connects to nodes in the (j-1).sup.th and the (j+1).sup.th stages but not to nodes in other stages. Only one entry point (s) and one end point (v) can be found in this map, as shown in FIG. 5.

Based on this model, a penalty in each mode may be found, as follows: ##EQU13##

wherein .alpha. represents (n.sub.0, n.sub.1, . . . , n.sub.z) and .SIGMA.n.sub.k =j, since .alpha..epsilon.V.sub.j.

Although there are many possible paths which lind s and v and each path has a maximum penalty, the minimal length of the path may be selected to so that the least buffer requirement in retrieving the data may be found.

In finding the shortest path, any applicable method may be used in this invention. In the embodiment of this invention, the dynamic programming solution is adopted. Reference for the dynamic programming solution may be made to E. Horowitz and S. Sahni: "Fundamentals of Computer Algorithms", Chapter 5: Dynamic Programming. This approach may be taken for reference in this invention.

In finding the shortest path using the dynamic programming solution, let D.sup.(j) (.alpha.) represent the shortest path from s to v. The shortest path D.sup.(j) (.alpha.) may be found from the following equation: ##EQU14##

The path so obtained insures the minimum buffer requirement in retrieving the data.

Segmentation of Data Files

The distribution of data on zoned disk as obtained from the above processes may be optimal while the buffer requirement is concerned. Still, the calculations in the CRT approach consume substantially long operation time. A segmentation algorithm is presented to divide the data files into segments with equal size in order to reduce the complexity of the processing. The segmentation of the data file may be as follows (while two segments is the case): ##EQU15##

wherein N.sub.i and i have the same definitions respectively, h1.sub.I represents the block number in the i.sup.th zone in a segment with the size of B.sub.i.

The operation time may be dramatically reduced after the segmentation.

Several video files are processed according to the architecture of this invention. Table 1 shows the block size and the block numbers in each zone and the number of the zero blocks, as the data file of movie "Starwar" is stored under the filing architecture of this invention. In this embodiment, the data file consisting of 174,136 frames, assuming that the period of a service round is 10 seconds and that each disk includes 3 zones. Time required to calculate the optimal distribution of the data on the zoned disk may be:

The buffer memory required in processing this data file is the above number times the space needed to process a block and to temporarily keep the data.

In other embodiments, the buffer requirement and the utilization rates are shown in Table 2. In this table, B/B denotes the ratio of the minimum buffer requirement over the largest disk block and the utilization rate may be determined from equation (1).

Although the above architecture can satisfy the needs of the minimum buffer requirement and the real-time play-back, the files contain substantially large number of blocks and consume long operation time. By using the segmentation algorithm the operation time can be dramatically reduced, as shown in Table 3. This table shows the relation between the number of segmentation and the operation time.

As shown in this table, if a file is divided into 8 segments, the operation time will be reduced from 676 seconds to 6 seconds. When the file is divided into 16 segments, the buffer requirement will dramatically increase, without improvements in the operation time.

As the present invention has been shown and described with reference to preferred embodiments thereof, those skilled in the art will recognize that the above and other changes may be made therein without departing from the spirit and scope of the invention.