Fractional spanning tree packing problem with survivability constraints for throughput maximization in overlay multicast networks
Michał Kucharzak, Krzysztof M. Walkowiak · International Conference on Ultra Modern Telecommunications · 2011
Overlay-based multicast has been proposed as an efficient solution to ensure multicast communication in the Internet. In contrast to IP multicast, it uses a virtual topology created in an overlay network and eliminates many drawbacks related to scalability or management control. In this paper we focus on modelling and optimization of survivability of overlay multicast system which is aimed at throughput maximization. Based on fractional Steiner trees, we employ the fractional spanning tree packing problem and propose various constraints in order to model features of real systems comprising robustness against a single link failure. The paper compares optimal results of the tree packing model with a general formulation based on conceptual flows dedicated to maximizing throughput in an overlay multicast system with node capacity constraints. Although the linear program of tree packing problem cannot guarantee globally the best utilization of overlay system's resources, but it provides a relative tradeoff between applicability in result quality and time consumption meaning.