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)
  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,}


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 ... DVD Version: Load ACM SIGMOD Anthology DVD 2" and ... BibTeX


David P. Anderson, Yoshitomo Osawa, Ramesh Govindan: A File System for Continuous Media. ACM Trans. Comput. Syst. 10(4): 311-337(1992) BibTeX
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) BibTeX
Edward Y. Chang, Avideh Zakhor: Cost Analyses for VBR Video Servers. IEEE MultiMedia 3(4): 56-71(1996) BibTeX
Robert Flynn, William H. Tetzlaff: Disk Striping and Block Replication Algorithms for Video File Servers. ICMCS 1996: 590-597 BibTeX
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) BibTeX
Roger L. Haskin, Frank B. Schmuck: The Tiger Shark File System. COMPCON 1996: 226-231 BibTeX
Jack Y. B. Lee: Parallel Video Servers: A Tutorial. IEEE MultiMedia 5(2): 20-28(1998) BibTeX
Banu Özden, Rajeev Rastogi, Abraham Silberschatz: Disk Striping in Video Server Environments. ICMCS 1996: 580-589 BibTeX
David A. Patterson, Garth A. Gibson, Randy H. Katz: A Case for Redundant Arrays of Inexpensive Disks (RAID). SIGMOD Conference 1988: 109-116 BibTeX
A. L. Narasimha Reddy: Scheduling and Data Distribution in a Multiprocessor Video Server. ICMCS 1995: 256-263 BibTeX
Ralf Steinmetz: Analyzing The Multimedia Operating System. IEEE MultiMedia 2(1): 68-84(1995) BibTeX
Harrick M. Vin, Pawan Goyal, Alok Goyal: A Statistical Admission Control Algorithm for Multimedia Servers. ACM Multimedia 1994: 33-40 BibTeX
Harrick M. Vin, S. S. Rao, Pawan Goyal: Optimizing the Placement of Multimedia Objects on Disk Arrays. ICMCS 1995: 158-166 BibTeX
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 BibTeX
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
VLDB Journal: 1992-1995 Copyright © by VLDB Endowment / 1996-... Copyright © by Springer Verlag,
ACM SIGMOD Anthology: Copyright © by ACM (, Corrections:
DBLP: Copyright © by Michael Ley (, last change: Sun May 17 00:31:36 2009