Optimal packing of group multicastings

Abstract

This paper presents algorithms, heuristics and lower bounds addressing optimization issues in many-to-many multicasting. Two main problems are addressed: (1) a precise combinatorial comparison of optimal multicast trees with optimal multicast rings, (2) an optimized sharing of network resources (i.e., nodes and links) among multiple multicast groups that coexist. The former is central to the choice of multicast protocols and their performance, while the latter is crucial for network utilization. The first problem is treated as a comparison of Steiner tree and traveling salesman problems on the same input set. The underlying integer programming problems are solved to optimum by using cutting-plane inequalities and the branch-and-cut algorithm. In addition to these exact solutions, fast heuristics are presented for approximate solutions. The second problem is formulated as a packing problem in which the network tries to accommodate all the multicast groups by optimizing the utilization of resources. Precise mathematical programming formulations, lower bounds and a heuristic for the underlying optimization problem are presented. The heuristic aims to accommodate multiple multicast groups while avoiding bottlenecks on the links for higher throughput. The heuristics and exact algorithms are implemented on various networks and multicast groups. The simulations show that multicast trees can be built by using 25% fewer links than the rings, both for optimal and suboptimal constructions. The packing heuristic is also implemented and its performance is compared to the constructive lower bound.