Minimizing Cost of Network Upgrade for Overlay Multicast – Heuristic Approach
DOI:
https://doi.org/10.26636/jtit.2013.3.1225Keywords:
multicasting, network design, optimization, overlay network, streamingAbstract
A rapid increase of the Internet users and traffic at the rate of 31% in years 2011–2016 contributes to emerging of new approaches to the content distribution. Among other approaches, the overlay multicasting seems to be one of the most interesting concepts according to relatively low deployment costs and large scalability. In this paper, the authors formulate a new incremental multicast overlay design problem. In particular, authors assumed that the overlay network is to be upgraded due to an increase of the number of participating users and the need to improve the streaming quality. However, the existing multicast tree structure is assumed to remain fixed. The goal was to minimize the cost of the upgrade, represented in euro/month. To achieve it, for each peer participating in the transmission, a link type offered by one of the ISPs was selected and overlay trees were constructed, rooted at the source of the content. The authors also present a new heuristic algorithm to efficiently solve this problem. According to experiments, the biggest factor influencing the upgrade cost and determining possible streaming quality values that the system can be upgraded to is the initial tree structure.
Downloads
References
[1] „Cisco visual networking index: Forecast and methodology, 2011-2016”, Cisco, 2012.
View in Google Scholar
[2] S. Banerjee et al., „Omni: An efficient overlay multicast infrastructure for real-time applications”, Comput. Netw., vol. 50, iss. 6, pp. 826-841, 2006.
View in Google Scholar
[3] J. Bufford, H. Yu, and E. K. Lua, P2P Networking and Applications. Morgan Kaufmann Series in Networking, D. Clark, Ed. Morgan Kaufmann, 2008.
View in Google Scholar
[4] M. Szostak and K. Walkowiak, „Incremental approach to Overlay Network Design Problem”, in Proc. 17th Polish Teletraf. Symp. 2012, Zakopane, Poland, 2012.
View in Google Scholar
[5] M. Pióro and D. Medhi, Routing, Flow and Capacity Design in Communication and Computer Networks. Morgan Kaufmann, 2004.
View in Google Scholar
[6] T. Small, B. Li, and B. Liang, „Outreach: Peer-to-peer topology construction towards minimized server bandwidth costs”, IEEE J. Select. Areas Commun., vol. 25, no. 1, pp. 35-45, 2007.
View in Google Scholar
[7] C. Wu and B. Li, „On meeting P2P streaming bandwidth demand with limited supplies”, in Proc. 15th Ann. SPIE/ACM Int. Conf. Multimed. Comput. Netw. MMCN 2008, San Jose, CA, USA, 2008.
View in Google Scholar
[8] B. Akbari, H. Rabiee, and M. Ghanabari, „An optimal discrete rate allocation for overlay video multicasting”, Comput. Commun., vol. 31, pp. 551-562, 2008.
View in Google Scholar
[9] Y. Cui, Y. Xue, and K. Nahrstedt, „Optimal resource allocation in overlay multicast”, IEEE Trans. Parall. Distrib. Sys., vol. 17, no. 8, pp. 808-823, 2006.
View in Google Scholar
[10] M. Kwon and S. Fahmy, „Path-aware overlay multicast”, Comput. Netw., vol. 47, no. 1, pp. 23-45, 2005.
View in Google Scholar
[11] Y. Zhu and B. Li, „Overlay networks with linear capacity constraints”, IEEE Trans. Parall. Distrib. Sys., vol. 19, no. 2, pp. 159-173, 2008.
View in Google Scholar
[12] N. Geary, A. Antonopoulos, E. Drakopoulos, and J. O’Reilly, „Analysis of optimization issues in multi-period DWDM network planning”, in Proc. 20th Ann. Joint Conf. IEEE Comp. Commun. Soc. IEEE INFOCOM 2001, Anchorage, Alaska, USA, 2001, vol. 1, pp. 152-158.
View in Google Scholar
[13] S. Gopal and K. Jain, „On network augmentation”, IEEE Trans. Reliabil., vol. 35, no. 5, pp. 541-543, 1986.
View in Google Scholar
[14] H. Lee and D. Dooly, „Heuristic algorithms for the fiber optic network expansion problem”, Telecommun. Sys., vol. 7, pp. 355-378, 1997.
View in Google Scholar
[15] A. Meyerson, K. Munagala, and S. Plotkin, „Designing networks incrementally”, in Proc. 42nd Ann. Symp. Foundations Comp. Sci. FOCS 2001, Las Vegas, Nevada, USA, 2001.
View in Google Scholar
[16] A. Tero et al., „Rules for biologically inspired adaptive network design”, Science, vol. 327, pp. 439-442, 2010.
View in Google Scholar
[17] S. Shi and J. Turner, „Multicast routing and bandwidth dimensioning in overlay networks”, IEEE J. Select. Areas Commun., vol. 45, no. 8, pp. 1444-1455, 2002.
View in Google Scholar
[18] M. Szostak and K. Walkowiak, „Two approaches to network design problem for overlay multicast with limited tree delay - model and optimal results”, Int. J. Electron. Telecommun., vol. 57, no. 3, pp. 335-340, 2011.
View in Google Scholar
[19] „IBM ILOG CPLEX version 12.5 user’s manual”, IBM Software.
View in Google Scholar
Downloads
Submitted
Published
Issue
Section
License
Copyright (c) 2013 Journal of Telecommunications and Information Technology
This work is licensed under a Creative Commons Attribution 4.0 International License.
