Virtual private networks (VPN) are often used to distribute live content, such as video or audio streams, from a single source to a large number of destinations. Streaming caches or splitters are deployed in these multicast networks to allow content distribution without overloading the network. In this paper, we consider two combinatorial optimization problems that arise in multicast networks. In the Tree Cache Placement Problem (TCPP), the objective is to find a routing tree on which the number of cache nodes needed for multicasting is minimized. We also discuss a modification of this problem, called the Flow Cache Placement Problem (FCPP), where we seek any feasible flow from the source to the destinations which minimizes the number of cache nodes. We prove that these problems are NP-hard using a transformation from SATISFIABILITY. This transformation allows us to give a proof of non-approximability by showing that it is gap-preserving. We also consider approximation algorithms for the TCPP and FCPP and special cases where these problems can be solved in polynomial time.
Citation
AT&T Technical Report, May 30, 2003.