Unified read requests

E. Hwang, B. Prabhakaran

Research output: Contribution to journalArticlepeer-review


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 describe a Request Merging (RM) module that takes as input, a set of client requests, and a set of constraints on the desired performance such as client waiting time or maximum disk bandwidth, and a cost function. It produces as output, a Unified Read Request (URR), telling the storage server which data items to read, and when the clients would like these data items to be delivered to them. Given a cost function of, a URR is optimal if there is no other URR satisfying the constraints with a lower cost. We present three algorithms in this paper, each of which accomplishes this kind of request merging. The first algorithm OptURR is guaranteed to produce minimal cost URRs with respect to arbitrary cost functions. In general, the problem of computing an optimal URR is NP-complete, even when only two data objects are considered. To alleviate this problem, we develop two other algorithms, called GreedyURR and FastURR 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.

Original languageEnglish
Pages (from-to)203-224
Number of pages22
JournalMultimedia Tools and Applications
Issue number3
Publication statusPublished - 2003 Aug
Externally publishedYes

Bibliographical note

Funding Information:
We would like to thank Dr. S. Khuller and Dr. R. Bhatia for the proofs of the theorems and Dr. V.S. Subrahmanian for the useful comments on the paper. This work was supported by Ajou Research Fund Grant, Ministry of Education of Korea(BK21 Project supervised by Korea Research Foundation), and University Research Program by Ministry of Information and Communication in Korea.


  • Cost function
  • Multimedia storage server
  • Optimality
  • Request merging

ASJC Scopus subject areas

  • Software
  • Media Technology
  • Hardware and Architecture
  • Computer Networks and Communications


Dive into the research topics of 'Unified read requests'. Together they form a unique fingerprint.

Cite this