Random Duplicated Assignment:
An Alternative to Striping in Video Servers

ACM Copyright Notice

Abstract

An approach is presented for storing video data in large disk arrays. Video data is stored by assigning a number of copies of each data block to different, randomly chosen disks, where the number of copies may depend on the popularity of the corresponding video data. The approach offers an interesting alternative to the well-known striping techniques. Its use results in smaller response times and lower disk and RAM costs if many continuous variable-rate data streams have to be sustained simultaneously. It also offers some practical advantages relating to reliability and extendability.

Based on this storage approach, three retrieval algorithms are presented that determine, for a given batch of data blocks, from which disk each of the data blocks should be retrieved. The performance of these algorithms is evaluated from an average-case as well as a worst-case perspective.

Keywords

video server, striping, disk array, RAID, multimedia, variable rate

Table of contents

• Introduction
• Striping techniques
  • Striping across all disks in the disk array
  • Striping across a subset of the disks
• Random duplicated assignment
• Performance of retrieval algorithms
• Disk and RAM costs, response times
• Reliability and extendability
• Additional remarks
• Acknowledgements
• References

Introduction

A video server offers continuous data streams to multiple users, possibly in an interactive setting. To realize small access times at a reasonable cost, the video data is usually stored on an array of magnetic disks, using RAID technology [Patterson, Gibson & Katz, 1988]. A continuous data stream is offered to each user by repeatedly fetching a data block from disk and storing it in a corresponding buffer. The buffers are implemented in random access memory (RAM) and are part of the server. A user consumes from his buffer via a communication network. The disk accesses for the different users should be scheduled in such a way that buffers neither under- nor overflow.

In this paper we assume that a user consumes from his buffer at a variable rate. This variability may be caused by the fact that the video data is variable-bit-rate-encoded MPEG-2 data, by stop/continue or slow-motion requests issued by the user, or by the interactive nature of an on-demand service, where user input influences when and at what rate data is consumed. For disk scheduling algorithms that specifically handle variable-rate data streams we refer to Dengler, Bernhardt & Biersack [1996] and Korst, Pronk & Coumans [1997].

The hardware cost of a video server is dominated by the disk and RAM costs. The available RAM must be large enough to implement the buffers for a given maximum number n of users. The number m of disks must be large enough (i) to store a given collection of video data and (ii) to offer a guaranteed total transfer rate that is required for servicing n users simultaneously. The transfer of data between the disks and the buffers is realized by one or more busses. The total transfer rate of the busses is assumed to exceed the total transfer rate offered by the disks. To avoid an excessively large seek overhead, i.e., an ineffective use of the disks, data blocks are retrieved in batches from the disks, so that a disk can fetch a number of data blocks in a single sweep of its reading head; see e.g. Gemmell [1993]. The time interval in which a batch of data blocks is retrieved is called a cycle. The effectiveness of disk usage, i.e., the fraction of time that is actually spent on reading data, is to a large extent determined by the size of the data blocks that are repeatedly fetched from disk.

In this paper we assume that many data streams have to be serviced simultaneously, i.e., that n is large. Given this assumption, it is reasonable to assume that the required number of disks is completely determined by the required transfer rate. In other words, we assume that the available disk storage space is much larger than is required for storing the given collection of video data. As an example, suppose that we want to offer an on-demand service to a maximum of 1,000 users. The service offers a choice from, say, 25 interactive videos, each with a duration of 90 minutes and encoded at 4 Mbit/s. Suppose that we use Seagate Barracuda 4LP disks, having a guaranteed sustained data rate of 60 Mbit/s and a storage capacity of 4,350 MBytes. For the 25 videos we require a total of 64,373 MBytes of storage. Hence, 15 disks suffice to store the 25 videos. However, to obtain a total transfer rate that is sufficient for servicing the 1,000 users simultaneously, we require at least 67 disks. Consequently, there is room enough to store each video at least 4 times. Even if we use disks with the same sustained data rate but with a storage capacity of only 2,150 MBytes, we still have room enough to store each video at least twice.

In this paper we show that, under the above assumptions, the existing striping techniques are less suitable for storing video data cost-effectively. We propose an alternative storage technique, called Random Duplicated Assignment (RDA). The underlying idea is simply to assign c_i copies of each data block i to different, randomly chosen disks, instead of striping a single copy across all or part of the disks in the disk array. In this way, data block i can be retrieved from c_i different disks. As we will see, this offers enough freedom to obtain, with high probability, an extremely good balance of the disk loads, even if c_i = 2 for each data block i. Furthermore, the resulting response times will improve considerably.

The organization of this paper is as follows. In Section 2, we discuss the striping techniques that are usually applied in video servers, and indicate why they work less well for video servers with a large number of users. In Section 3, we introduce the alternative storage technique. In addition, we present three retrieval algorithms that determine, for a given batch of data blocks, from which disk each of the data blocks should be retrieved. A comparison of the average-case and worst-case performance of the retrieval algorithms is given in Section 4. Section 5 gives an example of how RDA can reduce the disk and RAM costs of a video server as well as the worst-case response times. In Section 6 we consider the advantages of RDA in terms of reliability and extendability. We end with some additional remarks in Section 7.

<-- Table of Contents

Striping techniques

We consider two striping alternatives: in the first one, data is striped across all disks, in the second one, data is striped across a subset of the disks. For a more elaborate discussion on striping alternatives we refer to Chua et al. [1996].

Striping across all disks in the disk array

Most papers on video servers assume that video data is striped across all disks in the disk array, i.e., each data block is partitioned into m sub-blocks, where the jth sub-block is stored on disk j. In this way, the video server guarantees a transfer rate that is m times the guaranteed transfer rate of a single disk. By striping across all disks, one avoids the possible occurrence of load imbalance: if a batch of n data blocks has to be retrieved, then each disk has to fetch exactly n sub-blocks.

However, for a large number of users, this approach results in an unacceptably high hardware cost. This can be seen as follows. Let us consider how the disk and RAM costs grow with n. As already mentioned, the effectiveness of disk usage is largely determined by the size of the sub-blocks that are repeatedly fetched from disk. We assume, for the moment, that the size of a sub-block is fixed. Consequently, the number m of disks that is required to service n users will grow linearly with n. Clearly, the number of buffers will also grow linearly with n. Since sub-blocks are of a fixed size and m grows linearly with n, the size of the data blocks will also grow linearly with n . Since a buffer must be able to store a fixed number of data blocks, the total buffer requirements will thus grow quadratically with n. Consequently, for large n, this leads to an unacceptably high hardware cost.

The above argumentation is valid under the assumption that sub-blocks are of fixed size. This, however, need not be an optimal approach. By choosing, for each number of users, the number of disks that minimizes the sum of the disk and RAM costs, the total hardware cost will grow less fast. However, in that case, we still observe a quadratic term in the hardware cost function. Figure 1 shows the minimum disk and RAM costs per user as a function of the maximum number of users for the on-demand service example discussed in the introduction, assuming that the video data is striped across all disks.

For n up to 132, the cost per user is dominated by the cost of the 15 disks that are required for storing the 25 videos. Here, the cost per user decreases rapidly with n, since the cost of the 15 disks is divided over more and more users. For 132 users, the disk and RAM costs per user are approximately 112 US dollars. For larger n, we observe that the required number of disks is determined by the required transfer rate, resulting in an almost linear growth of the disk and RAM costs per user. For 1,000 users, the disk and RAM costs per user are 282 US dollars. We further elaborate on the on-demand service example in Section 5.

Consequently, striping the video data across all disks either results in a quadratic growth of the total RAM cost (if the size of the sub-blocks are fixed) or in a decreasing effectiveness of disk usage (if the size of the sub-blocks are allowed to decrease with n), which also results in a super-linear growth of the total hardware cost.

<-- Striping Techniques

Striping across a subset of the disks

To circumvent these problems, Oyang et al. [1995], amongst others, have proposed to stripe data across a fixed number of disks, as follows. The set of all disks is partitioned into k so-called parity groups, numbered g₀,...,g_k-1. A data block is then only striped across the disks of one parity group. The successive data blocks of a video are assigned in a round-robin fashion to the different parity groups, i.e., the ith data block is assigned to parity group g_{i mod k}. The total set of users is then partitioned into k user groups, where in the ith cycle each user in user group j reads a data block from parity group g_{(i+j) mod k}. The problem with this approach is that it assumes the consumption of the users to be synchronized. This assumption is invalid if users consume at variable rates. In that case, users cycle around the parity groups at variable speeds. Consequently, clustering will inevitably occur in such a way that many users require to read from the same parity group in the same cycle. Furthermore, the worst-case response time will be as large as k + 1 cycles. Hence, for sustaining variable-rate data streams, this does not work well.

In an interesting alternative, proposed by Berson, Muntz & Wong [1996], data blocks are striped across k randomly chosen disks. For a given batch of data blocks, this will generally result in a certain imbalance of the loads of the different disks. However, if one of the sub-blocks contains parity data, as may be required for improving the reliability of the disk array, then only k-1 of the total k sub-blocks need to be retrieved to reconstruct the complete data block. This gives additional freedom to improve the possible load imbalance. The authors propose a heuristic algorithm to determine which sub-blocks should be retrieved, stating that to their knowledge no efficient algorithm exists. It can be shown, however, that along the same lines as the max-flow selection algorithm presented in Section 3, an optimization algorithm can be constructed for this application. Striping across a small number of disks, i.e., choosing k small, leads to a high storage overhead required for parity data. For the graphics application considered by Berson, Muntz & Wong, storage capacity is generally an issue, so that k cannot be chosen very small.

<-- Striping Techniques

<-- Table of Contents

Random duplicated assignment

As stated in the introduction, the idea of RDA is simply to store c_i copies of a data block i on different, randomly chosen disks.

Let the n variable-rate data streams be sustained by repeatedly fetching a batch of at most n data blocks, i.e., during each cycle at most one data block is fetched for each user. In this way, one can guarantee that buffers neither under- nor overflow; see e.g. Korst, Pronk & Coumans [1997].

Consequently, in each cycle we have to determine for each data block of a given set of data blocks the disk from which it must be retrieved. We want to do this in such a way that the maximum load is minimized. This combinatorial optimization problem can be formally stated as follows.

Retrieval Selection Problem (RSP)
Let S be a set of at most n data blocks that must be retrieved in a given cycle. Let D be a set of m disks and let for each i in S the subset of disks on which i is stored be denoted by D(i) Then the problem is to find an assignment a: S -> D such that a(i) in D(i), for each i in S, and l_max is minimal, where l_max = max_{j in D} l(j) and l(j) = |{i in S | a(i) = j}|.

We now present three algorithms for handling RSP: two linear-time heuristic algorithms and one optimization algorithm. For reasons of convenience, we assume in the rest of this paper that |S| = n, that c_i = 2 for each i in S, and that the two disks on which i is stored are denoted by d₁(i) and d₁(i). We also assume that n << m. Furthermore, let D = {1,...,m} and let S = {1,...,n}.

Linear Selection (LS)
LS assigns the data blocks one by one to the disk that has the smallest current load. A precise formulation of LS is given in Figure 2. Clearly, LS runs in O(n) time.

Linear Reselection (LR)
LR starts by creating an initial selection using LS. Next, the data blocks are again considered one by one in the same order as in LS. If the current load of the disk to which a data block is assigned is larger than the current load of the alternative disk, then the data block is reassigned to the latter. A precise formulation of LR is given in Figure 3 . Clearly, LR also runs in O(n) time.

Max-Flow Selection (MFS)
Finally, we present a retrieval algorithm that results in an optimal selection, i.e., an assignment a for which l_max is minimal. The algorithm iteratively improves a given assignment until optimality is established.

Given an assignment a, the question whether l_max can be lowered by k units can be reformulated as a max-flow problem, as follows. With a given assignment a of n data blocks to m disks , we associate a directed network (V,E). For each disk i we define a vertex v_i in V, labeled with l(i), the load of the associated disk in assignment a. For each ordered pair v_i,v_j in V, we define a directed edge (v_i,v_j) in E, labeled with a capacity c(v_i,v_j), giving the number of data blocks that a assigns to disk i but can be reassigned to disk j. The capacity of an edge (v_i,v_j) gives an upper bound on the flow that may run from v_i to v_j. This resulting network is now extended by two additional vertices called source s and drain d. For each v_i in V, an edge (s,v_i) is added with capacity c(s,v_i) = max(k + l(i) - l_max, 0), and an edge (v_i,d) is added with capacity c(v_i,d) = max(l_max - k - l(i), 0). Now, it can be shown that the maximum load in a given assignment a can be lowered by k units if and only if a flow of size sum_{i = 1,...,m} max(k + l(i) - l_max, 0) can be realized from s to d, i.e., if and only if all outgoing edges from source s have a flow equal to their capacity. Indeed, the maximum load l_max can be lowered by k units if and only if for each disk i with l(i) > l_max - k, its load can be lowered by at least l(i) - l_max + k units (by appropriate reassignment of data blocks to other disks), and for each disk j with l(j) < l_max - k, its load is increased by at most l_max - k - l(j) units.

Since a given assignment that is obtained by using LS or LR has a maximum load of at most ceiling(n/2) and the maximum load of an optimal assignment is at least ceiling(n/m), we derive that the maximum load can be lowered by at most ceiling(n/2) - ceiling(n/m) units. If a binary search strategy is used, we derive that O(log n) iterations are required to obtain an optimal assignment. In each iteration, a max-flow problem is solved, which takes O(m³) time; see e.g. Van Leeuwen [1990] . Hence, MFS runs in O(m³ log n) time. Taking into account the time required for constructing an initial solution, we obtain the following result.

Theorem 1. RSP can be solved in O(n + m³ log n) time.

Since n >> m, this is polynomial in n. This time complexity also holds if c_i > 2 for some data blocks i.

<-- Table of Contents

Performance of retrieval algorithms

Theorem 2. For each instance I of RSP
ceiling(n/m) <= MFS(I) <= LR(I) <= LS(I) <= ceiling(n/2).

Proof. Evidently, ceiling(n/m) gives a lower bound on the maximum load of any assignment, which proves the first relation. Since MFS produces an optimal assignment, the second relation must hold. The third relation follows from the fact that the maximum load of a given LS assignment cannot increase by the reassignment postprocessing step in LR. Finally, the last relation follows from the fact that ceiling(n/2) gives an upper bound on any LS assignment.

>From Theorem 2 and n >> m, one can easily derive an upper bound on the worst-case performance ratio for LS by
LS(I)/OPT(I) = LS(I)/MFS(I) <= ceiling(n/2)/ ceiling(n/m) <= (m + 1)/2,
where OPT(I) denotes the maximum load that can be obtained by an optimal assignment for instance I. Evidently, the upper bound on the performance ratio, as given above, also holds for LR. It is important to realize that instances I exist for which MFS(I) = ceiling(n/2), i.e., for which all n data blocks are stored on the same two disks, but these instances occur at an extremely low probability.

To evaluate the average-case performance of the three algorithms we have carried out simulations for different values of m and n. The results are presented in Tables 1 and 2.

Each entry in Table 1 gives for a given choice of m and n/m the maximum load that is observed for 1,000,000 instances for each of the three algorithms. For each instance, d₁(i) is uniformly drawn from D and d₂(i) is uniformly drawn from D\d₁(i) for each data block i in S. Table 2 gives the corresponding average of the maximum loads observed for these instances.

For LS, we observe that for only 2 of the 36,000,000 instances the algorithm obtains a maximum load of ceiling(n/m) + 4. For all other instances the maximum load is at most ceiling(n/m) + 3. For LR, we observe that for 910 of the instances the algorithm obtains a maximum load of ceiling(n/m) + 2. For all other instances the maximum load is at most ceiling(n/m) + 1. For MFS, we observe that for 64 of the instances the algorithm obtains a maximum load of ceiling(n/m) + 2. For all other instances the maximum load is at most ceiling(n/m) + 1.
We conclude that, on average, all three retrieval algorithms obtain a very good load balance.

For LS we also determined the exact probability distribution of the maximum load, for relatively small values of m and n. This can be determined by induction on n. Let (d₀, d₁, d₂,...,d_k) denote a load distribution for n data blocks on m disks, where k = ceiling(n/2) and d_i gives the number of disks with load i. For such an (n,m) load distribution it must hold that sum_{i = 0,...,k} d_i = m and that sum_{i = 0,...,k} i.d_i = n. Given that we know the probability of each (n-1,m) load distribution, we can determine the probability of each (n,m) load distribution, assuming that the extra data block can be retrieved from two random disks and that it is assigned to the disk with the smallest current load. Clearly, when LS is used, the only possible (1,m) and (2,m) load distributions are (m-1,1,0,...,0) and (m-2,2,0,...,0), respectively. The two possible (3,m) load distributions are (m-3,3,0,...,0) and (m-2,1,1,0,...,0), occurring with probabilities 1 - 2/(m(m-1)) and 2/(m(m-1)), respectively. From these, we can derive the probabilities of all (4,m) load distributions, etc. As an example, the resulting probability distribution of l_max for m = 10 and n = 100 is given in Table 3. For the asymptotic behavior of LS, i.e., for m to infinity, we refer to Azar, Broder, Karlin & Upfal [1994]. These authors examined the algorithm in an on-line processor scheduling context.

Despite their simplicity, LS and especially LR obtain very good load balances at a high probability. It is now tempting to try to derive an upper bound on the worst-case performance ratio that is much tighter than the one given above. However, instances I can be constructed for which LS(I)/OPT(I) = LR(I)/OPT(I) = 2. An example is given in Figure 4.

Actually, from a worst-case perspective, the situation is even worse. Without proof we state the following result.
Theorem 3 For each positive integer c, instances I exist for which LR(I)/OPT(I) > c.
Fortunately, these instances occur at a very low probability and do not occur in situations with few disks.

<-- Table of Contents

Disk and RAM costs, response times

Let us now examine how RDA can be used in practice, and how it may influence the disk and RAM costs of a server. Given the small probability of LR obtaining a maximum load that exceeds ceiling(n/m) + 2, especially when m > 10 and n/m > 5, we could choose the size B of a data block such that it is large enough to survive a worst-case cycle where some disk fetches a batch of ceiling(n/m) + 2 data blocks of size B, assuming that a user consumes at his maximum rate.

If we would have striped the video data across all disks, then the size B of a data block should be chosen such that it is large enough to survive a worst-case cycle where each disk fetches a batch of n sub-blocks of size B/m.

Hence, by using RDA, the disks read fewer blocks but they have a larger size, leading to a more effective use of the disks. As an example, let us again consider the on-demand service example presented in the introduction. For this example, the disk and RAM costs per user, as a function of the maximum number of users, are given in Figure 5.

As in Figure 1, we observe that for small n, the hardware cost is dominated by the cost of the disks required for storing the 25 videos. For duplicated storage we require 30 disks. For n larger than 300, we observe constant total disk and RAM costs of approximately 78 US dollars per user. Hence, by using RDA, the total disk and RAM costs grow linearly with n, for larger values of n. The corresponding worst-case response times for RDA and striping are shown in Figure 6.

Let us now readdress the results for striping as illustrated in Figure 1. We observe that the cost per user is minimal if n = 132. Hence, if we want to service substantially more users, then for striping it is more profitable to operate a number of smaller independent video servers in parallel, each with approximately 132 users. For example, having a total of 1,000 users we can operate 8 servers in parallel, each with 125 users. This lowers the disk and RAM costs per user to 113 US dollars (with additional parity overhead not yet taken into account), which is still approximately 30% more expensive than the RDA alternative. Furthermore, note that each video must, in that case, be stored 8 times, leaving little or no room for storing additional videos. When RDA is used, then for 1,000 users 91 disks are used, which leaves enough disk storage space to increase the number of videos to 76, without additional costs. Also, the worst-case response time for RDA is still considerably better. For 1,000 users, RDA obtains a worst-case response time that is more than 50% better than for the parallel server alternative that uses striping. In addition, the replacement of videos requires more effort if we have 8 copies instead of 2.

Hence, by using RDA, one can reduce the disk and RAM costs substantially, provided of course that the required number of disks needed to service the n users, i.e., to obtain the required guaranteed transfer rate, is large enough to store the video data in duplicated form. At the same time, the worst-case response times are also reduced considerably.

<-- Table of Contents

Relialibity and extendability

An important property of striping techniques in RAID systems is that a very reliable system can be realized by adding redundant data on an extra so-called parity disk. In this way, if one disk fails, its data can still be reconstructed from the remaining disks, and the system can maintain the same service level.

Let us consider the reliability of RDA when each data block is stored on two disks. If one disk fails, then at least one copy of each data block is still available. The remaining single copies will be uniformly distributed over the remaining disks. The average load on the remaining disks will increase by a factor of m/(m-1). The lower bound on the maximum load of ceiling(n/m) increases to ceiling(n/(m-1)). If m is not too small, then the probability that the load of each disk will not exceed ceiling(n/m) + 2 is still very high when LR is used. Tables 4 and 5 give simulation results for the situation where one disk fails. At the top of each entry in these tables the lower bound ceiling(n/(m-1)) is given in italics. The results are based on 10,000 batches.

The total amount of data that must be read from the remaining disks to rebuild a new disk that replaces the failing disk equals the storage capacity of a single disk. If data is striped across all disks, then (m-1) times as much data must be read to rebuild a new disk. Hence, when RDA is used, rebuilding can be completed much more quickly.

Another important practical advantage of RDA is that extending a video server with one or more disks is considerably simpler. When data is striped across all disks, then adding disks requires all data to be reassigned to the disks. This also holds if data is assigned to parity groups in a round-robin fashion. When RDA is used, randomly chosen data blocks can be reassigned to the new disk(s). This can be implemented as a background process, which completes when the used storage space on all disks has been balanced again. During this process, the maximum number of users that can be serviced simultaneously can be increased gradually.

<-- Table of Contents

Additional remarks

If variable-period disk scheduling algorithms are used, such as the triple buffering and dual sweep algorithms presented by Korst, Pronk & Coumans [1997], then the number of data blocks that has to be retrieved per cycle is, on average, considerably smaller than the maximum number n that was worst-case accounted for. As a consequence, the probability that the load of a disk will ever exceed the bound ceiling(n/m) + 2 is even smaller than quantified in this paper. Furthermore, even if the load for some disk in some cycle is ceiling(n/m) + 3, then it will probably finish within the worst-case cycle, which is based on worst-case transfer rates, seek times and rotational latencies.

The running times that MFS requires in practice are substantially better than suggested by the O(m³ log n) time complexity. If LR is used to generate an initial assignment, then very often LR obtains a maximum load equal to the lower bound ceiling(n/m), which is clearly optimal. In all other observed cases, LR obtains a maximum load that deviates only one or two from this lower bound. In that case, MFS requires only one or two iterations, with k = 1.

In this paper we assumed that c_i for each data block i. Simulations indicate that if only, say, 75% of the data blocks is stored in duplicated form, we still obtain a good load balance with a high probability. Furthermore, we can base the value of c_i on the popularity of the corresponding video data. Less popular video data is stored only once, popular video data is stored twice or more times.

The retrieval algorithms presented in this paper assume that the disks are synchronized in the sense that repeatedly a batch of disk access requests is distributed among the disks. The next batch is distributed when the previous one is completely finished. The retrieval algorithms can be adjusted such that the disks are less synchronized.

Finally, we remark that future developments are expected to make RDA even more interesting. Disk prices are assumed to decrease at a steeper rate than RAM prices. Also, disk storage spaces are assumed to increase at a steeper rate than disk transfer rates. Both assumptions can be shown to be advantageous for RDA.

<-- Table of Contents

Acknowledgments

I thank Pascal Coumans for his support in analyzing the cost reductions implied by RDA, and Dee Denteneer for his assistance in the probabilistic analysis of the retrieval algorithms.

<-- Table of Contents

References

Azar, Y., A.Z. Broder, A.R. Karlin, and E. Upfal [1994], Balanced allocations, Proceedings of the 26th ACM Symposium on Theory of Computing , Montreal, Quebec, Canada, pp. 593-602.

Berson, S., R.R. Muntz, and W.R. Wong [1996], Randomized data allocation for real-time disk I/O, Proceedings of the 41st IEEE Computer Society Conference, COMPCON'96, Santa Clara, CA, February 25-28.

Chua, T.S., J. Li, B.C. Ooi, and K.-L. Tan [1996], Disk striping strategies for large video-on-demand servers, Proceedings ACM Multimedia '96, Boston, MA, November 18-22, 297-306.

Dengler, J., Ch. Bernhardt, and E. Biersack [1996], Deterministic admission control strategies in video servers with variable bit rate streams, in: B. Butscher, E. Moeller, and H. Pusch (Eds.), Proceedings Workshop Interactive Distributed Multimedia Systems and Services, Berlin, Germany, March 4-6, pp. 245-264.

Gemmell, D.J. [1993], Multimedia network file servers: Multi-channel delay sensitive data retrieval, Proceedings ACM Multimedia '93, Anaheim, CA, August 1-6, pp. 243-250.

Korst, J., V. Pronk, and P. Coumans [1997], Disk scheduling for variable-rate data streams, accepted for publication in Proceedings European Workshop on Interactive Distributed Multimedia Systems and Telecommunication Services, IDMS'97, Darmstadt, Germany, September 10-12.

Oyang, Y.-J., C.-H. Wen, C.-Y. Cheng, M.-H. Lee, and J.-T. Li [1995], A multimedia storage system for on-demand playback, IEEE Transactions on Consumer Electronics 41, 53-64.

Patterson, D.A., G.A. Gibson, and R.H. Katz [1988], A case for redundant arrays of inexpensive disks (RAID), Proceedings of the ACM Conference on Management of Data, pp. 109-116.

Van Leeuwen, J. [1990], Graph algorithms, in: J. van Leeuwen (Ed.), Handbook of Theoretical Computer Science, Volume A, Algorithms and Complexity, Elsevier/MIT Press, pp. 525-631.

<-- Table of Contents