Retrieval problems in multimedia storage servers

A multimedia server offers continuous streams of multimedia data to multiple users. In a multimedia server one can often distinguish three parts: an array of hard disks to store the data, an internal network, and a fast memory from which the users consume, which is usually implemented in RAM. The multimedia data is stored on the hard disks in blocks, such that a data stream is realized by a series of blocks. In the server we need a cost-efficient storage and retrieval strategy, that guarantees, either deterministically or statistically, that the buffers do not underflow or overflow.

The cost of a multimedia server mainly consists of the costs of hard disks and RAM. The load balancing performance of a storage strategy is an important factor in the disk costs, as an efficient usage of the available bandwidth of the disk array increases the maximum number of allowed users. We focus on the load balancing performance of random redundant storage strategies, in which each data block of a stream is stored on a randomly chosen subset of the disks. Redundancy gives the freedom to obtain a balanced load. To exploit this freedom we have to decide for each data block which of the disks to use for its retrieval.

In the past year, we have developed a general model for the retrieval problems incurred by redundant storage strategies. We considered two load balancing approaches: block-based and time-based load balancing. In the first approach the retrieval problems can be solved to optimality in polynomial time with max-flow algorithms, whereas in the second approach the retrieval problems are NP-complete. We have developed LP-based heuristics for the latter NP-complete problems. Future research will focus on the actual cost consequences of the storage and retrieval strategies.