Merging Retrieval Requests for Multimedia Storage Server

Abstract

Most work on multimedia storage systems has assumed that clients will be serviced using a round-robin strategy. The server services the clients in rounds and each client is allocated a time slice within that round. Furthermore, most such algorithms are evaluated on the basis of a tightly specified cost function. This is the basis for well known algorithms such as FCFS, SCAN, SCAN-EDF, etc. In this paper, we first describe a request merging module that takes as input, a set of client requests, a set of constraints on the desired performance, and a cost function. It produces as output, a unified read request(URR), telling the storage server, which data items to read, and when these data items to be delivered to clients. And then, we present three algorithms, each of which accomplishes request merging. The first algorithm OptURR is guaranteed to produce optimal URRs with respect to arbitrary cost functions. Since the problem of computing an optimal URR is NP-complete, we develop two other algorithms that may produce sub-optimal URRs, but which have some nicer computational properties. We will report on the pros and cons of these algorithms through an experimental evaluation.