Jump to content United States-English
HP.com Home Products and Services Support and Drivers Solutions How to Buy
» Contact HP

HP.com home


Technical Reports



» 

HP Labs

» Research
» News and events
» Technical reports
» About HP Labs
» Careers @ HP Labs
» Worldwide sites
» Downloads
Content starts here

 
Click here for full text: PDF

On the Complexity of Variants of Cooperative Peer-to- peer Repair for Wireless Broadcasting

Cheung, Gene; Li, Danjue; Chuah, Chen-Nee

HPL-2006-90

Keyword(s): multimedia; wireless networks; complexity

Abstract: The well-known NAK implosion problem for wireless broadcast can be addressed by leveraging cooperative peer-to-peer connectivity to repair corrupted data. This paper studies the Cooperative Peer-to-peer Repair (CPR) framework for multimedia broadcast. We show that CPR can be formulated as an optimization problem that minimizes the number of iterations it takes to wirelessly disseminate a desired message from peers 'with' the content to peers 'without' it. Complicating the problem are transmission conflicts, where pre- specified sets of links cannot simultaneously transmit due to interference. In this paper, we formalize CPR as a discrete optimization problem, and prove that CPR and its many variants are NP-hard. Notes:

4 Pages

Back to Index

»Technical Reports

» 2009
» 2008
» 2007
» 2006
» 2005
» 2004
» 2003
» 2002
» 2001
» 2000
» 1990 - 1999

Heritage Technical Reports

» Compaq & DEC Technical Reports
» Tandem Technical Reports
Printable version
Privacy statement Using this site means you accept its terms Feedback to HP Labs
© 2009 Hewlett-Packard Development Company, L.P.