Minimizing cost of network upgrade for overlay multicast – heuristic approach

• Autorzy: Szostak M. , Walkowiak K.
• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

multicasting; network design; optimization; overlay network; streaming

• Wydawca: Instytut Łączności - Państwowy Instytut Badawczy
• Czasopismo: Journal of Telecommunications and Information Technology
• Rocznik: 2013
• Tom: nr 3
• Strony: 66--73
• Opis fizyczny: Bibliogr. 19 poz., rys., tab.

Twórcy

autor

Szostak M.

• Department of Systems and Computer Networks, Wrocław University of Technology, Wybrzeże Wyspiańskiego st 27, 50-370 Wrocław, Poland

autor

Walkowiak K.

• Faculty of Electronics, Department of Systems and Computer Networks, Wrocław University of Technology, Wybrzeże Wyspiańskiego st 27, 50-370 Wrocław, Poland

Bibliografia

• [1] “Cisco visual networking index: Forecast and methodology, 2011–2016”, Cisco, 2012.
• [2] S. Banerjee et al., “Omni: An efficient overlay multicast infrastructure for real-time applications”, Comp. Netwo.: The Int. J. Comp. Telecommun. Netw., vol. 50, iss. 6, pp. 826–841, 2006.
• [3] J. Bufford, H. Yu, and E. K. Lua, P2P Networking and Applications. Morgan Kaufmann Series in Networking, D. Clark, Ed. Morgan Kaufmann, 2008.
• [4] M. Szostak and K. Walkowiak, “Incremental approach to Overlay Network Design Problem”, in Proc. 17th Polish Teletraf. Symp. 2012, Zakopane, Poland, 2012.
• [5] M. Pióro and D. Medhi, Routing, Flow and Capacity Design in Communication and Computer Networks. Morgan Kaufman, 2004.
• [6] T. Small, B. Li, and B. Liang, “Outreach: Peer-to-peer topology construction towards minimized server bandwidth costs”, IEEE J. Selec. Areas Commun., vol. 25, no. 1, pp. 35–45, 2007.
• [7] C. Wu and B. Li, “On meeting P2P streaming bandwidth demand with limited supplies”, in Proc. 15th Ann. SPIE/ACM Int. Conf. Multime. Comput. Netwo. MMCN 2008, San Jose, CA, USA, 2008.
• [8] B. Akbari, H. Rabiee, and M. Ghanabari, “An optimal discrete rate allocation for overlay video multicasting”, Comp. Commun., vol. 31, pp. 551–562, 2008.
• [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.
• [10] M. Kwon and S. Fhamy, “Path-aware overlay multicast”, Comp. Netw., vol. 47, no. 1, pp. 23–45, 2005.
• [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.
• [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.
• [13] S. Gopal and K. Jain, “On network augumentation”, IEEE Trans. Reliabil., vol. 35, no. 5, pp. 541–543, 1986.
• [14] H. Lee and D. Dooly, “Heuristic algorithms for the fiber optic network expansion problem”, Telecommun. Sys., vol. 7, pp. 355–378, 1997.
• [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.
• [16] A. Tero et al., “Rules for biologically inspired adaptive network design”, Science, vol. 327, pp. 439–442, 2010.
• [17] S. Shi and J. Turner, “Multicast routing and bandwidth dimensioning in overlay networks”, IEEE J. Selec. Areas Commun., vol. 45, no. 8, pp. 1444–1455, 2002.
• [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.
• [19] “Ilog cplex version 12.5 user’s manual”, IBM Software.