Equipment allocation in video-on-demand network deployments

ABSTRACT

Video-on-Demand (VoD) services are very user-friendly, but also complex and resource demanding. Deployments involve careful design of many mechanisms where content attributes and usage models should be taken into account. We define, and propose a methodology to solve, the VoD Equipment Allocation Problem of determining the number and type of streaming servers with directly attached storage (VoD servers) to install at each potential location in a metropolitan area network topology such that deployment costs are minimized. We develop a cost model for VoD deployments based on streaming, storage and transport costs and train a parametric function that maps the amount of available storage to a worst-case hit ratio. We observe the impact of having to determine the amount of storage and streaming cojointly, and determine the minimum demand required to deploy replicas as well as the average hit ratio at each location. We observe that common video-on-demand server configurations lead to the installation of excessive storage, because a relatively high hit-ratio can be achieved with small amounts of storage so streaming requirements dominate.

REFERENCES

• 1: Almeida, J. M., Eager, D. L., Vernon, M. K., and Wright, S. 2004. Minimizing delivery cost in scalable streaming content distribution systems. IEEE Trans. Multimed. 6, 356--365.
• 2: Cornuejols, G., Nemhauser, G., and Wolsey, L. 1990. The uncapacitated facility location problem. In Discrete Location Theory, P. Mirchandani and R. Francis, Eds. Wiley, 119--171.
• 3: Couch, K. 2005. Raising the bar for triple play with VoD. Converge! Network Digest. http://www.convergedigest.com/blueprints/ttp03/2005nortel1.asp?ID=189&ctgy=Headend.
• 4: R. Fletcher, Practical methods of optimization; (2nd ed.), Wiley-Interscience, New York, NY, 1987
• 5: Krishna P. Gummadi , Richard J. Dunn , Stefan Saroiu , Steven D. Gribble , Henry M. Levy , John Zahorjan, Measurement, modeling, and analysis of a peer-to-peer file-sharing workload, Proceedings of the nineteenth ACM symposium on Operating systems principles, October 19-22, 2003, Bolton Landing, NY, USA
• 6: Karlsson, M., Karamanolis, C., and Mahalingam, M. 2002. A unified framework for evaluating replica placement algorithms. Tech. rep. Hewlett-Packard Laboratories.
• 7: Kim, S.-J. and Choi, M. 2003. A genetic algorithm for server location and storage allocation in multimedia-on-demand network. In Proceedings of the Symposium on Trends in Communications.
• 8: P. Krishnan , Danny Raz , Yuval Shavitt, The cache location problem, IEEE/ACM Transactions on Networking (TON), v.8 n.5, p.568-582, Oct. 2000 [doi>10.1109/90.879344]
• 9: Laoutaris, N., Zissimopoulos, V., and Stavrakakis, I. 2005. On the optimization of storage capacity allocation for content distribution. Comput. Netw. J. 47, 409--428.
• 10: Markman, J. 2006. 2007 is showtime for video on demand. http://articles.moneycentral.msn.com/Investing/SuperModels/2007IsShowtimeForVideoOnDemand.aspx.
• 11: Masa, M. and Parravicini, E. 2003. Impact of request routing algorithms on the delivery performance of content delivery networks. In Proceedings of the International Performance Computing Communications Conference (IPCCC).
• 12: Mundur, P., Simon, R., and Sood, A. 2004. End-to-end analysis of distributed Video-on-Demand systems. IEEE Trans. Multimed. 6, 129--141.
• 13: Nguyen, T., Chou, C., and Boustead, P. 2003. Resource optimization for content distribution networks in shared infrastructure environment. In Proceedings of the Australian Telecommunications Networks and Applications Conference. Melbourne, Australia.
• 14: Tang, W., Wong, E., Chan, S., and Ko, K. 2004. Optimal video placement scheme for batching vod services. IEEE Trans. Broad. 50, 16--25.
• 15: Thouin, F. and Coates, M. 2007a. Video-on-Demand networks: design approaches and future challenges. IEEE Network—Special Issue on Convergence of Internet and Broadcasting Systems 21, 42--48.
• 16: Thouin, F. and Coates, M. 2007b. Video-on-Demand server selection and placement. In Proceedings of the International Teletraffic Congress (ITC). Ottawa, Canada.
• 17: Frederic Thouin , Mark Coates , Dominic Goodwill, Video-on-Demand Equipment Allocation, Proceedings of the Fifth IEEE International Symposium on Network Computing and Applications, p.103-110, July 24-26, 2006 [doi>10.1109/NCA.2006.56]
• 18: Vinokurov, A. 2005. Tools for optical networks design. In Proceedings of the European Next Generation Internet Design and Engineering (EURO-NGI).
• 19: Wang, B., Sen, S., Adler, M., and Towsley, D. 2002. Optimal proxy cache allocation for efficient streaming media distribution. In Proceedings of the IEEE Infocom.
• 20: Wauters, T., Colle, D., Pickavet, M., Dhoedt, B., and Demeester, P. 2005. Optical network design for video on demand services. In Proceedings of the Conference on Optical Network Design and Modelling. Milan, Italy.
• 21: Ling-Yun Wu , Xiang-Sun Zhang , Ju-Liang Zhang, Capacitated facility location problem with general setup cost, Computers and Operations Research, v.33 n.5, p.1226-1241, May 2006 [doi>10.1016/j.cor.2004.09.012]
• 22: Yang, M. and Fei, Z. 2003. A model for replica placement in content distribution networks for multimedia applications. In Proceedings of the IEEE International Conference on Communications. Anchorage, AK.
• 23: Hongliang Yu , Dongdong Zheng , Ben Y. Zhao , Weimin Zheng, Understanding user behavior in large-scale video-on-demand systems, Proceedings of the 1st ACM SIGOPS/EuroSys European Conference on Computer Systems 2006, April 18-21, 2006, Leuven, Belgium

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Distributed networks

General Terms:
Design, Management

Keywords:
Video-on-demand, equipment allocation, optimization, resource allocation