This project focuses on the challenges when designing a storage system suitable for realtime video and audio retrieval. It is motivated by the Yima continous media server project. The Yima server is based on a cluster design. Each cluster node is an off-the-shelf personal computer with attached storage devices, such as magnetic disk drives. The research focuses on the following aspects:

• Online Scalability: How do we scale the storage system incrementally while (a) the system continues operation, (b) the minimal amount of data is reorganized, and (c) the system continues to be load balanced.
• Heterogeneous Disk Storage: How do we maximize the resource use of disks with different data transfer rates and storage sizes while at the same time ensuring that none of the real-time constraints for audio and video data retrievals are violated.

SCADDAR: An Efficient Randomized Technique to Reorganize Continuous Media Blocks

Scalable storage architectures allow for the addition of disks to increase storage capacity and/or bandwidth. This is an important requirement for continuous media servers for two reasons. First, multimedia objects are ever increasing in size, numbers and bandwidth requirements. Second, magnetic disks are continuously improving in capacity and transfer rate. In its general form, disk scaling also refers to disk removals when either capacity needs to be conserved or old disk drives are retired. There are two basic approaches to scatter the blocks of a continuous media object on multiple disk drives: random and constrained placement. Assuming random placement, our optimization objective is to redistribute a minimum number of media blocks after disk scaling. This objective should be met under two restrictions. First, uniform distribution and hence a balanced load should be ensured after redistribution. Second, the redistributed blocks should be retrieved at the normal mode of operation in one disk access and through low complexity computation. We propose a technique that meets the objective, while we prove that it also satisfies both restrictions. The SCADDAR approach is based on using a series of REMAP functions which can derive the location of a new block using only its original location as a basis.

Adding one storage node to a four node cluster results in a minimal movement of data with the SCADDAR algorithm. Only 20% of the data need to be moved from each old node to the new node.

Roger Zimmermann

• Research Assistant Professor at the USC Computer Science Department
• Email: rzimmerm@imsc.usc.edu
• Phone: (213) 740-7654

Cyrus Shahabi

• Assistant Professor at USC Computer Science Department (see InfoLab)
  
• Email: cshahabi@cs.usc.edu
• Phone: (213) 740-8162

Shu-Yuen Didi Yao

• Research Assistant
• Ph.D. Student
• 2001-02 Intel Foundation Graduate Fellowship Award Recipient
• Email: didiyao@usc.edu
• Phone: (213) 740-2289

Beomjoo Seo

• Research Assistant
• Ph.D. Student
• Email: bseo@usc.edu
• Phone: (213) 740-4177

For licensing information please see USC's Office of Technology Licensing.

Get the PDF reader from Adobe.

• SCADDAR: An Efficient Randomized Technique to Reorganize Continuous Media Blocks.
  Ashish Goel, Cyrus Shahabi, Shu-Yuen Didi Yao, and Roger Zimmermann.
  Proceedings of the 18th International Conference on Data Engineering (ICDE 2002), San Jose, California, February 26-March 1, 2002.
  Abstract Postscript (85 KB) PDF (141 KB)
  

  ---

• HERA: Heterogeneous Extension of RAID.
  Roger Zimmermann and Shahram Ghandeharizadeh.
  Proceedings of the 2000 International Conference on Parallel and Distributed Processing Techniques and Applications (PDPTA 2000), Las Vegas, Nevada, June 26-29, 2000.
  Abstract Postscript (57 KB) PDF (125 KB)

Maintained by Roger Zimmermann
Last updated: Thursday January 2, 2003.
All Rights Reserved © NUS Data Management Research Laboratory 1999 - 2007.