Talks & Seminars
Title: Efficient Set Reconciliation and Measuring Traffic at all Time Scales
George Varghese , University of California San Diego (currently visiting Microsoft Research, Bangalore)
Date & Time: June 17, 2011 14:30
Venue: SIC 301, Kanwal Rekhi Building
If you and I both have a million song titles, of which almost all are the same, how can we efficiently communicate the difference? We describe a new and practical algorithm for computing the set difference using communication proportional to the difference, linear computation, and small latency. A key component is a new estimator for the set difference that outpeforms earlier estimators such as MinWise sketches for small values of the set difference. Potential applications include trading blocks in a peer-to-peer environment, link state routing and data de-duplication. I will describe when this algorithm is useful from a systems perspective and a few (obvious in retrospect) things we learned after implementing the algorithm. I will also show that the basic algorithm shares a strong similarity with the "peeling algorithm" used in say Tornado codes. This is not surprising because there is an intimate connection between computing set difference and coding. Second, measuring bandwidth at fine timescales produces valuable debugging and tuning information. It is well known that traffic can be "smooth" at coarse time scales and yet bursty at finer time scales and this can cause phenomena such as microbursts in data centers that use commodity switches. However, it is hard to identify in advance which time scales cause bursty behavior. We ask the question: how can we measure bandwidth at all time scales without explicitly keeping state for all time scales? I will describe two algorithms to compactly summarize streams of fine-grain bandwidth samples to identify bursty traffic behavior. The algorithms record very little information but allow bandwidth statistics to be generated for arbitrary time scales down to microseconds. The set reconciliation work is joint with D. Eppstein, M. Goodrich, and F. Uyeda and will appear in SIGCOMM 2011. The multiple time scale bandwidth measurement is joint with F. Uyeda, L. Foschini, and L. Foschini and appeared in NSDI 2010
Speaker Profile:
List of Talks


Faculty CSE IT
Forgot Password
    [+] Sitemap     Feedback