Thesis Defense: Highly Efficient Network Coded Multicast Despite Small Buffers and Network Dynamics


Event Speaker: 

Bernhard Haeupler

Event Location: 

32D-463 STAR

Event Date/Time: 

Thursday, April 18, 2013 - 3:00pm

I will begin with a brief overview over the research I have done during my time
at MIT. During the rest of the talk I will present one of my favorite set of
results namely a simple, efficient and robust way to disseminate information in
networks - using network coding. In particular, the talk will focus on the
following two aspects:

Network Coding Performance in Dynamic Networks:
The time needed to complete a multicast was not well understood even in many
simple settings. We introduce a novel analysis technique that gives optimal
bounds on how quickly network coding spreads information resolving all settings
considered in the literature. Beyond this, our technique shows that network
coding is extremely robust against changes in the network topology. In
particular network coding remains efficient and optimal even if an adaptive
adversary is allowed to completely change the topology at any time. This stands
in contrast to almost quadratically larger lower bounds for any algorithm not
using network coding.

Computational and Memory Complexity of Coding:
The standard implementation of network coding requires all nodes to buffer all
packets they received and furthermore access and code these packets together
during every communication step. We show that this significant memory and
computational overhead can be avoided in many scenarios. In particular, we
prove the surprising result that simply storing and updating just one packet in
each node often achieves the same order optimal performance as full blown
network coding. Even stronger, for any buffer size the simplified protocol can
be shown to stop whp at exactly the first time any protocol using the same
amount of memory could have stopped in hindsight.

Both newly uncovered aspects establish network coding as a powerful tool for
multicast in a wide range of networks in which efficient information
dissemination seemed impossible before. Sensor networks consisting of low
complexity/memory sensors will serve as one such example throughout the talk.
Jonathan Kelner, Muriel Medard, David Karger, Madhu Sudan, Robert Tarjan