Computer Science – Information Theory
Scientific paper
2010-02-06
Computer Science
Information Theory
accepted by ISIT 2010
Scientific paper
To reduce computational complexity and delay in randomized network coded content distribution (and for some other practical reasons), coding is not performed simultaneously over all content blocks but over much smaller subsets known as generations. A penalty is throughput reduction. We model coding over generations as the coupon collector's brotherhood problem. This model enables us to theoretically compute the expected number of coded packets needed for successful decoding of the entire content, as well as a bound on the probability of decoding failure, and further, to quantify the tradeoff between computational complexity and throughput. Interestingly, with a moderate increase in the generation size, throughput quickly approaches link capacity. As an additional contribution, we derive new results for the generalized collector's brotherhood problem which can also be used for further study of many other aspects of coding over generations.
Li Yao
Soljanin Emina
Spasojevic Predrag
No associations
LandOfFree
Collecting Coded Coupons over Generations does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Collecting Coded Coupons over Generations, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Collecting Coded Coupons over Generations will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-636506