We investigate the video assignment problem of a hierarchical Video-on-Demand (VOD) system in heterogeneous environments where different quality levels of videos can be encoded using either replication or layering. In such systems, videos are delivered to clients either through a proxy server or video broadcast/unicast channels. The objective of our work is to determine the appropriate coding strategy as well as the suitable delivery mechanism for a specific quality level of a video such that the overall system blocking probability is minimized. In order to find a near-optimal solution for such a complex video assignment problem, an evolutionary approach based on genetic algorithm (GA) is proposed. From the results, it is shown that the system performance can be significantly enhanced by efficiently coupling the various techniques. 1. Introduction With the explosive growth of the Internet, the demand for various multimedia applications is rapidly increasing in recent years. Among different multimedia applications, Video-on-Demand (VOD) is playing a very important role. With VOD, customers can choose their desired video at arbitrary time they wish via public communication networks. Nevertheless, the VOD system is required to store several hundreds of videos as well as serve thousands of customers simultaneously. In order to build a cost-effective and scalable system, various designs have been proposed in terms of system architecture [1], bandwidth allocation [2], and transmission schemes [3]. Among different techniques, data broadcasting and proxy caching are two commonly used approaches. To improve the scalability of a VOD system using data broadcasting, the broadcast capability of a network is exploited such that video contents are distributed along a number of video channels shared among clients. Staggered broadcasting [4] is the simplest way to support broadcast services in the early day. After that, a number of efficient broadcasting protocols [5–8] were proposed. Apart from data broadcasting, hierarchical architectures [3] have also been explored to reduce the resources requirement. To leverage the workload of the central server and reduce the service latencies, an intermediate device called proxy is sit between the central server and the clients. In such architecture, a portion of video is cached in the proxy. The request generated by a client is served by the proxy if it caches the requested portion of the video. Meanwhile, the central server also delivers the remaining portion of the video to the client directly. Existing caching mechanisms can
References
[1]
F. Thouin and M. Coates, “Video-on-demand networks: design approaches and future challenges,” IEEE Network, vol. 21, no. 2, pp. 42–48, 2007.
[2]
A. Dan, P. Shahabuddin, D. Sitaram, and D. Towsley, “Channel allocation under batching and VCR control in Video-on-Demand systems,” Journal of Parallel and Distributed Computing, vol. 30, no. 2, pp. 168–179, 1995.
[3]
K. A. Hua, M. A. Tantaoui, and W. Tavanapong, “Video delivery technologies for large-scale deployment of multimedia applications,” Proceedings of the IEEE, vol. 92, no. 9, pp. 1439–1451, 2004.
[4]
J. W. Wong, “Broadcast delivery,” Proceedings of the IEEE, vol. 76, no. 12, pp. 1566–1577, 1988.
[5]
K. A. Hua and S. Sheu, “Skyscraper broadcasting: a new broadcasting scheme for metropolitan video-on-demand systems,” in Proceedings of the Conference on Communications Architectures, Protocols and Applications (SIGCOMM '97), pp. 89–100, 1997.
[6]
L.-S. Juhn and L.-M. Tseng, “Harmonic broadcasting for video-on-demand service,” IEEE Transactions on Broadcasting, vol. 43, no. 3, pp. 268–271, 1997.
[7]
W. C. Liu and J. Y. B. Lee, “Constrained consonant broadcasting—a generalized periodic broadcasting scheme for large scale video streaming,” in Proceedings of the IEEE International Conference on Multimedia & Expo, Baltimore, Md, USA, July 2003.
[8]
E. M. Yan and T. Kameda, “An efficient VoD broadcasting scheme with user bandwidth limit,” in Proceedings of the SPIE/ACM Conference on Multimedia Computing and Networking, vol. 5019, pp. 200–208, Santa Clara, Calif, USA, 2003.
[9]
J. Liu and J. Xu, “Proxy caching for media streaming over the internet,” IEEE Communications Magazine, vol. 42, no. 8, pp. 88–94, 2004.
[10]
R. Tewari, H. M. Vin, A. Dan, and D. Sitaram, “Resource-based caching for web servers,” in Proceedings of the Multimedia Computing and Networking (MMCN ’98), pp. 191–204, San Jose, Calif, USA, January 1998.
[11]
S. Sen, J. Rexford, and D. Towsley, “Proxy prefix caching for multimedia streams,” in Proceedings of the 18th Annual Joint Conference of the IEEE Computer and Communications Societie (INFOCOM '99), pp. 1310–1319, New York, NY, USA, March 1999.
[12]
S. Chen, B. Shen, S. Wee, and X. Zhang, “Designs of high quality streaming proxy systems,” in Proceedings of the IEEE Conference on Computer Communications (INFOCOM '04), pp. 1512–1521, Hong Kong, March 2004.
[13]
Z.-L. Zhang, Y. Wang, D. H. C. Du, and D. Su, “Video staging: a proxy-server-based approach to end-to-end video delivery over wide-area networks,” IEEE/ACM Transactions on Networking, vol. 8, no. 4, pp. 429–442, 2000.
[14]
T. Jiang, M. H. Ammar, and E. W. Zegura, “Inter-receiver fairness: a novel performance measure for multicast ABR sessions,” in Proceedings of the ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems, vol. 26, pp. 202–211, Madison, Wis, USA, June 1998.
[15]
R. Rejaie and J. Kangasharju, “Mocha: a quality adaptive multimedia proxy cache for Internet streaming,” in Proceedings of the 11th IEEE International Workshop on Network and Operating System Support for Digital Audio and Video, pp. 3–10, January 2001.
[16]
J. Kangasharju, F. Hartanto, M. Reisslein, and K. W. Ross, “Distributing layered encoded video through caches,” IEEE Transactions on Computers, vol. 51, no. 6, pp. 622–636, 2002.
[17]
T. Kim and M. H. Ammar, “A comparison of layering and stream replication video multicast schemes,” in Proceedings of the IEEE International Workshop on Network and Operating System Support for Digital Audio and Video, pp. 63–72, New York, NY, USA, 2001.
[18]
F. Hartanto, J. Kangasharju, M. Reisslein, and K. W. Ross, “Caching video objects: layers vs. versions,” in Proceedings of IEEE International Conference on Multimedia and Expo (ICME '02), vol. 2, pp. 45–48, Lausanne, Switzerland, August 2002.
[19]
K.-M. Ho, W.-F. Poon, and K.-T. Lo, “Performance study of large-scale video streaming services in highly heterogeneous environment,” IEEE Transactions on Broadcasting, vol. 53, no. 4, pp. 763–773, 2007.
[20]
J. H. Holland, Adaptation in Natural and Artificial Systems, The MIT Press, Cambridge, Mass, USA, 1975.
[21]
K.-S. Tang, K.-T. Ko, S. Chan, and E. W. M. Wong, “Optimal file placement in VOD system using genetic algorithm,” IEEE Transactions on Industrial Electronics, vol. 48, no. 5, pp. 891–897, 2001.
[22]
W. K. S. Tang, E. W. M. Wong, S. Chan, and K.-T. Ko, “Optimal video placement scheme for batching VOD services,” IEEE Transactions on Broadcasting, vol. 50, no. 1, pp. 16–25, 2004.
[23]
J. I. Kimura, F. A. Tobagi, J. M. Pulido, and P. J. Emstad, “Perceived quality and bandwidth characterization of layered MPEG-2 video encoding,” in International Symposium Voice, Video and Data Communications, vol. 3845 of Proceedings of SPIE, pp. 308–319, Boston, Mass, USA, 1999.
[24]
A. Ganjam and H. Zhang, “Internet multicast video delivery,” Proceedings of the IEEE, vol. 93, no. 1, pp. 159–170, 2005.
[25]
C. Costa, I. Cunha, A. Borges, C. Ramos, M. Rocha, J. Almeida, and B. Ribeiro-Neto, “Analyzing client interactivity in streaming media,” in Proceedings of the 13th International World Wide Web Conference Proceedings (WWW '04), pp. 534–543, May 2004.
[26]
G. Zipf, Human Behavior and the Principle of Least Effort, Addison-Wesley, Reading, Mass, USA, 1949.
[27]
J. Medhi, Stochastic Process, Wiley InterScience, New York, NY, USA, 2nd edition, 1994.
[28]
Z. Michalewicz, Genetic Algorithms + Data Structures = Evolution Program, Springer, Berlin, Germany, 3rd edition, 1996.
[29]
D. E. Goldberg, Genetic Algorithms in Search, Optimization, and Machine Learning, Addison-Wesley, London, UK, 1989.
[30]
K. F. Man, K. S. Tang, and S. Kwong, Genetic Algorithm: Concepts and Designs, Springer, London, UK, 1999.
[31]
C. R. Reeves, “Using genetic algorithms with small populations,” in Proceedings of the 5th International Conference on Genetic Algorithms (ICGA '93), pp. 92–99, 1993.
[32]
GAlib, http://lancet.mit.edu/ga/.
[33]
R. Rejaie, M. Handley, and D. Estrin, “Layered quality adaptation for Internet video streaming,” IEEE Journal on Selected Areas in Communications, vol. 18, no. 12, pp. 2530–2543, 2000.
[34]
H. Schwarz, D. Marpe, and T. Wiegand, “Overview of the scalable video coding extension of the H.264/AVC standard,” IEEE Transactions on Circuits and Systems for Video Technology, vol. 17, no. 9, pp. 1103–1120, 2007.
