Modeling (Coded) Chunk-Based Content Delivery by the Coupon Collector's Problem
May 04, 2012
from 10:00 AM to 11:30 AM
|Where||ENGR. IV Bldg., Tesla Room 53-125|
|Contact Name||Lara Dolecek|
|Add event to calendar||
In chunk-based content distribution, files are fragmented at the source and the fragments (chunks) are distributed individually throughout the network. The way the chunks are circulated in the network affects the overall throughput of the network. Instead of distributing the original file chunks, nodes can send out linear combinations of the chunks they hold, and these result in a throughput increase. But for a number of practical concerns (e.g., computational complexity and synchronization), chunks are grouped into (possibly overlapping) sets known as generations, and only chunks within the same generation are allowed to be linearly combined. A price to pay for combining (coding) only within generations is throughput reduction. We analyze the effects of generation size on the throughput by modeling the collection of (coded) chunked content as a "coupon collector's brotherhood" problem. Further, we extend the results from the collector's brotherhood problem and characterize the impact of introducing random overlaps between generations on the throughput. It is shown that proper choice of generation overlaps can improve throughput without raising computational complexity. The performance of these codes is also tested in UDP broadcasts to smartphones.
Yao Li obtained her Bachelor's degree in Information Engineering and Electronics from Tsinghua University, Beijing, China, and subsequently joined WINLAB of Rutgers University, the State University of New Jersey, as a Ph.D student in Electrical Engineering. There she has been working on content distribution solutions with coding techniques. In Fall 2011, she was with the ETIS lab of ENSEA and CNRS in Cergy-Pontoise, France, as a visiting research scientist. There she worked on the problem of storage allocation in distributed storage systems. Her research interests lie in the areas of rateless codes, network coding, probabilistic analysis, and information theory.