The Overlay Network Content Distribution Problem

Chip Killian, Michael Vrable, Alex C. Snoeren, Amin Vahdat and Joseph Pasquale
CS2005-0824
May 18, 2005

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 constant-competitive 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.


How to view this document


The authors of these documents have submitted their reports to this technical report series for the purpose of non-commercial dissemination of scientific work. The reports are copyrighted by the authors, and their existence in electronic format does not imply that the authors have relinquished any rights. You may copy a report for scholarly, non-commercial purposes, such as research or instruction, provided that you agree to respect the author's copyright. For information concerning the use of this document for other than research or instructional purposes, contact the authors. Other information concerning this technical report series can be obtained from the Computer Science and Engineering Department at the University of California at San Diego, techreports@cs.ucsd.edu.


[ Search ]


NCSTRL
This server operates at UCSD Computer Science and Engineering.
Send email to webmaster@cs.ucsd.edu