The overlay network content distribution problem

Due to the lack of deployment of a network-layer multicast service, many overlay multicast protocols have been designed and deployed across the Internet to support content distribution. To our knowledge, however, none have provided a rigorous analysis of the problem or the effectiveness of their proposed solutions. Here, we set aside the engineering challenges of protocol design to focus on the fundamental graph problem. We begin by formulating the Overlay Network Content Distribution (OCD) problem and show that variants that attempt to optimize for either speed or bandwidth utilization are NP-complete. Using both a time-indexed Integer Program and a branch-and-bound search strategy, we calculate optimal solutions for small graphs. While solutions to OCD provide performance bounds, realistic deployment scenarios will not have global network information. Hence, we introduce an on-line variant, the Local-knowledge Overlay Content Distribution (LOCD) problem and show that no constantcompetitive approximation exists. Instead, we present several heuristics that perform well in realistic topologies. We conclude with an evaluation of our global and local heuristics and enumerate a number of open problems. 1