An efficient retrieval selection algorithm for video servers with random duplicated assignment storage technique.

DOI10.1016/S0020-0190(02)00210-7MaRDI QIDQ1853091zbMATH OpenOpenAlexFDO

Authors Chor-Ping Low

Publication date 21 January 2003

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0020-0190(02)00210-7

zbMATH Keywords

AlgorithmsBreadth-first searchLoad balancingPolynomial-time algorithmsRandom duplicated assignment

Mathematics Subject Classification ID

Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Information storage and retrieval of data (68P20) General topics in the theory of algorithms (68W01)

Review text

Random duplicated assignment is an approach in which video data is stored by assigning a number of copies of each data block to different, randomly chosen disks. It has been shown that this approach results in smaller response times and lower disk and RAM costs compared to the well-known disk stripping techniques. Based on this storage approach, one has to determine, for each given batch of data blocks, from which disk each of the data blocks is to be retrieved. This is to be done in such a way that the maximum load of the disks is minimized. The problem is called the Retrieval Selection Problem (RSP). In this paper, we propose a new efficient algorithm for RSP. This algorithm is based on the breadth-first search approach and is able to guarantee optimal solutions for RSP in \(O(n^{2}+mn)\), where \(m\) and \(n\) correspond to the number of data blocks and the number of disks, respectively. We will show that our proposed algorithm has a lower time complexity than an existing algorithm, called the MFS algorithm.

Recommendations

• Random duplicate storage strategies for load balancing in multimedia servers
• Load balancing for redundant storage strategies: Multiprocessor scheduling with machine eligibility
• FST TCS 2003: Foundations of Software Technology and Theoretical Computer Science
• An efficient scheduling algorithm for information delivery on VoD system
• Algorithms for non-uniform size data placement on parallel disks

Cites work

• Random duplicate storage strategies for load balancing in multimedia servers

Cited in

(7)

• Multipurpose machine scheduling with rejection and identical job processing times
• Parallel machine scheduling with nested processing set restrictions
• Efficient algorithms for scheduling equal-length jobs with processing set restrictions on uniform parallel batch machines
• Faster algorithms for semi-matching problems
• Random duplicate storage strategies for load balancing in multimedia servers
• CEA: a cyclic expansion algorithm for data migration in parallel video servers
• An approximation algorithm for the load-balanced semi-matching problem in weighted bipartite graphs

This page was built for publication: An efficient retrieval selection algorithm for video servers with random duplicated assignment storage technique.

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1853091)