Load balancing for redundant storage strategies: Multiprocessor scheduling with machine eligibility

An important cost issue in multimedia servers is disk load balancing, such that the available hard disks are used as efficiently as possible. Disk load balancing is often done on a block basis, but can also be done on a time basis, by taking into account the actual transfer times of the blocks. In the latter approach we can also embed the disk switch times. In this paper we revisit block-based load balancing and introduce time-based load balancing. For each approach we present a mathematical model and analyse the complexity of the corresponding retrieval problem. We give algorithms with a performance bound for the NP-hard time-based retrieval problem and use simulation to compare the results of these algorithms with a maximum flow algorithm for the block-based retrieval problem. Copyright (C) 2001 John Wiley & Sons, Ltd.