Study of cache placement for time-shifted TV cluster using genetic algorithm

ABSTRACT

The designing of a streaming media system, especially Time-shifted TV cluster faces an optimization cache problem of deciding how to cache channels to multiple servers so that the blocking probability is minimized subject to memory capacity constraints. In this paper, we investigate the crucial problem by evaluating the blocking performance for a feasible assignment. A popularity-based random placement (PRP) scheme together with the genetic algorithm (GA) is developed to find an optimal or approximate optimal solution of the problem. The experiment results reveal that our proposed algorithm is efficient on improving the performance of Time-shifted TV cluster in terms of minimizing blocking probability.

REFERENCES

• 1: Chakareski, J. and Frossard, P. 2007. Adaptive Systems for Improved Media Streaming Experience, IEEE Communications Magazine, vol. 45, no. 1, 77--83.
• 2: J.C. Zhuo, G. Wu, J. Li and S. Xu, 2008. Efficient Cache Placement Scheme for Clustered Time-shifted TV Servers, IEEE Transactions on Consumer Electronics, vol.54, no.4, 1947--1955.
• 3: W. Xiang, G. Wu, Q. Ling and L. Wang, 2007. Piecewise Patching for Time-shifted TV over HFC Networks, IEEE Transactions on Consumer Electronics, vol.53, no.3, 891--897.
• 4: Mounir A. Tantaoui , Kien A. Hua , Simon Sheu, A Scalable Technique for VCR-Like Interactions in Video-on-Demand Applications, Proceedings of the 22nd International Conference on Distributed Computing Systems, p.246-251, July 02-05, 2002
• 5: T. Wauters , W. Van de Meerssche , F. De Turck , Bart Dhoedt , P. Demeester , T. Van Caenegem , E. Six, Co-operative Proxy Caching Algorithms for Time-Shifted IPTV Services, Proceedings of the 32nd EUROMICRO Conference on Software Engineering and Advanced Applications, p.379-386, August 29-September 01, 2006 [doi>10.1109/EUROMICRO.2006.29]
• 6: Y. Guo, et al., 2006. Dynamic cache reconfiguration strategies for cluster-based streaming proxy, Computer Communications, vol. 29, no.10, 1710--1721.
• 7: Davis, L. 1991. Handbook of Genetic Algorithms, Van Nostrand Reinhold, New York, U.S.A.
• 8: J. Guo, et al., 2008. Performance Analysis of Resource Selection Schemes for a Large Scale Video-on-Demand System, IEEE Transactions on Multimedia, vol. 10, no. 1, 153--159.
• 9: K.S Tang et al., 2001. Optimal file placement in VOD system using genetic algorithm, Industrial Electronics, IEEE Transactions on, vol. 48, no. 5, 891--897.
• 10: H. Akimaru and K. Kawashima, 1999. Teletraffic: Theory and Applications, 2nd ed. London, U.K.: Springer-Verlag.
• 11: Xiaobo Zhou , Cheng-Zhong Xu, Efficient algorithms of video replication and placement on a cluster of streaming servers, Journal of Network and Computer Applications, v.30 n.2, p.515-540, April, 2007 [doi>10.1016/j.jnca.2006.03.001]
• 12: T. Bektas, O. Oguz, and I. Ouveysi, 2006. A novel optimization algorithm for video placement and routing, Communications Letters, IEEE, vol.10, no. 2, 114--116.
• 13: G. K. Zipf, 1949. Human Behavior and the Principle of Least Effort: An Introduction to Human Ecology. Cambridge, MA: Addison-Wesley.
• 14: Cristiano P. Costa , Italo S. Cunha , Alex Borges , Claudiney V. Ramos , Marcus M. Rocha , Jussara M. Almeida , Berthier Ribeiro-Neto, Analyzing client interactivity in streaming media, Proceedings of the 13th international conference on World Wide Web, May 17-20, 2004, New York, NY, USA [doi>10.1145/988672.988744]
• 15: K. F. Man , K. S. Tang , S. Kwong , M. Johnson , M. Grimble, Genetic Algorithms: Concepts and Designs with Disk, Springer-Verlag New York, Inc., Secaucus, NJ, 1999
• 16: Broadcasters' audience research board, http://www.barb.co.uk

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.5 INFORMATION INTERFACES AND PRESENTATION (I.7)
      H.5.1 Multimedia Information Systems

General Terms:
Algorithms, Experimentation

Keywords:
blocking probability, cache placement, genetic algorithm, time-shifted tv (tstv)