Minimizing cost of network upgrade for overlay multicast – heuristic approach

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.