Interactive video distribution systems – User-requested video program system – Video-on-demand
Reexamination Certificate
1993-11-30
2001-10-09
Chauhan, Ulka J. (Department: 2671)
Interactive video distribution systems
User-requested video program system
Video-on-demand
C725S087000, C719S323000, C711S114000
Reexamination Certificate
active
06301711
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Technical Field
The invention relates to a system and method of reproducing asynchronous full motion video on a plurality of nodes of a network from a Redundant Array of Inexpensive Disks type mass storage system.
2. Description of the Related Art
Use of disk memory continues to be important in computers because it is nonvolatile and because memory size demands continue to outpace practical amounts of main memory. For conventional data processing applications, single disks deliver data at rates slower than the system central processing unit (CPU) can utilize it. While main memory buffers the CPU from the disk, system performance for conventional applications is often limited by disk access speed. Thus, it has been seen as necessary for improving overall system performance to increase memory size and data access speed of disk drive units. For a discussion of this, see Michelle Y. Kim, “Synchronized Disk Interleaving”,
IEEE Transactions On Computers
, Vol. C-35, No. 11, November 1986.
A variety of techniques have been utilized to improve data access speed. Disk cache memory capable of holding an entire track of data has been used to eliminate seek and rotation delays for successive accesses to data on a single track. Multiple read/write heads have been used to interleave blocks of data on a set of disks (data striping) or on a set of tracks on a single disk. Common data block sizes are byte size, word size, and sector size. Disk interleaving is a known supercomputer technique for increasing performance, and is discussed, for example, in the above-noted article.
While data striping yields advantages in data bandwidth, it unfortunately reduces the mean time to failure, which varies inversely with the number of disks in the array used to store the data. To correct for this decreased mean time to failure of the system, error recognition and correction has been added to the data to produce so called Redundant Arrays of Inexpensive Disks (RAID) architectures. Five types of RAID architecture are referred to as RAID levels 1-5. See, David A. Patterson, et al., “A Case for Redundant Arrays of Inexpensive Disks (RAID)”, Report No. UCB/CSD 87/89, December, 1987, Computer Science Division (EECS), University of California, Berkeley, Calif. 94720.
RAID level 1 utilizes complete duplication (mirroring) of data from a primary disk to a backup disk. RAID level 1 has been primarily regarded as a data redundancy scheme to provide fault tolerance. Because of its relatively small performance per disk ratio over a conventional drive it has rarely been used in other applications.
RAID level 2 improves on the performance of RAID level 1 as well as increasing the capacity per disk ratio by utilizing error correction codes that enable a reduction of the number of extra disks needed to provide data and disk failure recovery. In RAID level 2, data is interleaved onto a group of G data disks and error correction codes (ECC) are generated and stored onto an additional set of C disks referred to as “check disks” to detect and correct a single error. The ECC are used to detect and enable correction of random single bit errors in data and also enables recovery of data if one of the G data disks crashes. Since only G of the C+G disks carries user data, the performance per disk is proportional to G/(G+C). G/C is typically significantly greater than 1, so RAID level 2 exhibits and improvement in performance per disk over RAID level 1. One or more spare disks can be included in the system so that if one of the disk drives fails, the spare disk can be electronically switched into the RAID to replace the failed disk drive.
RAID level 3 is a variant of RAID level 2 in which the error detecting capabilities that are provided by most existing inexpensive disk drives are utilized to enable the number of check disks to be reduced to one, thereby increasing the relative performance per disk over that of RAID level 2. Typically parity data is substituted for ECC. Either ECC, some other error code, or parity data may be termed redundant data. For both RAID levels 2 and 3 the transaction time for disk accesses for large or grouped data is reduced because bandwidth into all of the data disks can be exploited.
The performance criteria for small data transfers, such as is common in transaction processing, is known to be poor for RAID levels 2 and 3 because data is interleaved among the disks in bit-sized blocks, such that even for a data access of less than one sector of data, all disks must be accessed. To improve this performance parameter, in RAID level 4, a variant of RAID level 3, data is interleaved onto the disks in sector interleave mode instead of in bit interleave mode as in levels 1-3. In other words, individual I/O transfers involve only a single data disk. The benefit of this is from the potential for parallelism of the input/output operations. This reduces the amount of competition among separate data access requests to access the same data disk at the same time.
The performance of RAID level 4 remains limited because of access contention for the check disk during write operations. For all write operations, the check disk must be accessed in order to store updated parity data on the check disk for each stripe (i.e., row of sectors) of data into which data is written. Patterson et al. observed that in RAID level 4 and level 5, an individual write to a single sector does not involve all of the disks in a logical mass storage device since the parity bit on the check disk is just a single exclusive OR of all the corresponding data bits in a group. In RAID level 4, write operations interfere with each other, even for small data accesses. RAID level 5, a variant of RAID level 4, mitigates the contention for access to the parity data problem on write operations by distributing the parity check data and user data across all disks.
While various RAID architectures have successfully met data processing demands for increased bandwidth, the application of striped disks or RAID to real time reproduction of independent video segments on a plurality of processors has been less successful. Full motion video playback differs from conventional data transfers such as copying files or accessing a spreadsheet in that it requires a sustained high data rate rather than a burst of data. The data is also time critical. As little as a 0.5 second delay in data delivery can result in the reproduced video breaking up. Full motion video playback on a plurality of platforms over a network complicates data recovery by introducing contention issues as well.
In RAID levels 4 and 5 the independent sources of demand for data can result in all requests from around a network occasionally falling on just one drive. This inevitably results in failure to recover data quickly enough to meet the real time reproduction demands.
Striping and RAID levels 2 and 3 also fail. Striping and RAID levels 2 and 3 were intended to meet a small number of sequential requests for massive quantities of data. To meet this end they increased bandwidth. However, they do nothing to improve performance in terms of seek time and rotational latency, since the disks are conventionally synchronized. No advantage is gained in meeting multiple non-sequential requests.
The various RAID architectures were conceived as tools for closing the gap between Input/output performance and CPU performance. However, multimedia data is typically stored in compressed formats not suitable for conventional data processing. Compression also relieves bandwidth problems to and from a disk. Because of the vast quantities of data required to store images, compression of video data is a requirement if more than a few minutes of video is to be stored on disk in a digital format. Decompression of these formats is a processor intensive operation. In fact, when it comes to handling some types of compressed digital video data, central processing units such as the Intel 8088, 80286 and 80836SX microprocessors cannot keep up with the rate at which a conventional disk dri
Bracewell & Patterson L.L.P.
Chauhan Ulka J.
International Business Machines - Corporation
LaBaw Jeffrey S.
LandOfFree
System and method for the network support of full motion... 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 and method for the network support of full motion..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System and method for the network support of full motion... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2595207