Constant Time Permutation: An Efficient Block Allocation Strategy for Variable-Bit-Rate Continuous Media Data.

Yueh-Min Huang, Jen-Wen Ding, Shiao-Li Tsao: Constant Time Permutation: An Efficient Block Allocation Strategy for Variable-Bit-Rate Continuous Media Data. VLDB J. 8(1): 44-54(1999)

@article{DBLP:journals/vldb/HuangDT99,
  author    = {Yueh-Min Huang and
               Jen-Wen Ding and
               Shiao-Li Tsao},
  title     = {Constant Time Permutation: An Efficient Block Allocation Strategy
               for Variable-Bit-Rate Continuous Media Data},
  journal   = {VLDB J.},
  volume    = {8},
  number    = {1},
  year      = {1999},
  pages     = {44-54},
  ee        = {db/journals/vldb/HuangDT99.html},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

To provide high accessibility of continuous-media (CM) data, CM servers generally stripe data across multiple disks. Currently, the most widely used striping scheme for CM data is round-robin permutation (RRP). Unfortunately, when RRP is applied to variable-bit-rate (VBR) CM data, load imbalance across multiple disks occurs, thereby reducing overall system performance. In this paper, the performance of a VBR CM server with RRP is analyzed. In addition, we propose an efficient striping scheme called constant time permutation (CTP), which takes the VBR characteristic into account and obtains a more balanced load than RRP. Analytic models of both RRP and CTP are presented, and the models are verified via trace-driven simulations. Analysis and simulation results show that CTP can substantially increase the number of clients supported, though it might introduce a few seconds/minutes of initial delay.

Key Words

Continuous-media server - Video-on-demand (VOD) - Striping - Data placement - Load balancing

Copyright © 1999 by Springer, Berlin, Heidelberg. Permission to make digital or hard copies of the abstract is granted provided that copies are not made or distributed for profit or direct commercial advantage, and that copies show this notice along with the full citation.

Online Edition (Springer)

Citation Page

ACM SIGMOD Anthology

CDROM Version: Load the CDROM "Volume 5 Issue 2, JACM, VLDB-J, POS, ..." and ...

Windows: Click the letter of your CD drive
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
Mac: Click here
UNIX/LINUX: mount the CD and click on the path of your mount point:
/Anthology/An5-2 or /cdrom

DVD Version: Load ACM SIGMOD Anthology DVD 2" and ...

Windows: Click the letter of your CD drive
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
Mac: Click here
UNIX/LINUX: mount the DVD and click on the path of your mount point:
/Anthology/aDVD2 or /dvd

References

[AOG92]: David P. Anderson, Yoshitomo Osawa, Ramesh Govindan: A File System for Continuous Media. ACM Trans. Comput. Syst. 10(4): 311-337(1992)
[Che94]: Peter M. Chen, Edward L. Lee, Garth A. Gibson, Randy H. Katz, David A. Patterson: RAID: High-Performance, Reliable Secondary Storage. ACM Comput. Surv. 26(2): 145-185(1994)
[CZ96]: Edward Y. Chang, Avideh Zakhor: Cost Analyses for VBR Video Servers. IEEE MultiMedia 3(4): 56-71(1996)
[CZ94]: ...
[Den96]: ...
[FT96]: Robert Flynn, William H. Tetzlaff: Disk Striping and Block Replication Algorithms for Video File Servers. ICMCS 1996: 590-597
[Gem95]: Jim Gemmell, Harrick M. Vin, Dilip D. Kandlur, P. Venkat Rangan, Lawrence A. Rowe: Multimedia Storage Servers: A Tutorial. IEEE Computer 28(5): 40-49(1995)
[Has96]: Roger L. Haskin, Frank B. Schmuck: The Tiger Shark File System. COMPCON 1996: 226-231
[HT97]: ...
[Lee98]: Jack Y. B. Lee: Parallel Video Servers: A Tutorial. IEEE MultiMedia 5(2): 20-28(1998)
[ORS96]: Banu Özden, Rajeev Rastogi, Abraham Silberschatz: Disk Striping in Video Server Environments. ICMCS 1996: 580-589
[PGK88]: David A. Patterson, Garth A. Gibson, Randy H. Katz: A Case for Redundant Arrays of Inexpensive Disks (RAID). SIGMOD Conference 1988: 109-116
[Red95]: A. L. Narasimha Reddy: Scheduling and Data Distribution in a Multiprocessor Video Server. ICMCS 1995: 256-263
[Red97]: ...
[Ros95]: ...
[Ros97]: ...
[Ste95]: Ralf Steinmetz: Analyzing The Multimedia Operating System. IEEE MultiMedia 2(1): 68-84(1995)
[SV97]: ...
[TH98]: ...
[VGG94]: Harrick M. Vin, Pawan Goyal, Alok Goyal: A Statistical Admission Control Algorithm for Multimedia Servers. ACM Multimedia 1994: 33-40
[VRG95]: Harrick M. Vin, S. S. Rao, Pawan Goyal: Optimizing the Placement of Multimedia Objects on Disk Arrays. ICMCS 1995: 158-166
[WS96]: ...
[YCK92]: Philip S. Yu: Mon-Song Chen, Dilip D. Kandlur: Design and Analysis of a Grouped Sweeping Scheme for Multimedia Storage Management. NOSSDAV 1992: 44-55
[YM97]: ...