Network Coded Wireless Architecture
Sachin Rajsekhar Katti
Network Coded Wireless Architecture
by
Sachin Rajsekhar Katti
M.S., Electrical Engineering and Computer Science, Massachusetts Institute of Technology, 2 005
B.Tech., Electrical Engineering, Indian Institute of Technology, Bombay, 2003
Submitted to the
Department of Electrical Engineering and Computer Science
in partial fulfillment of the requirements for the degree of
Doctor of Philosophy in C omputer Science and Engineering
at the
Massachusetts Institute of Technology
September 2008
c
Massachusetts Institute of Technology 2008. All rights reserved.
Author . . . . . .. . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . .. . . . . . . .
Department of Electrical Engineering and Computer Science
August 29, 2008
Certified by . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . .
Dina Katabi
Associate Professor of Computer Science and Engineering
Thesis Supervisor
Accepted by . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Terry P. Orlando
Chairman, Dep artment Committee on Gradua te Students
2
Network Coded Wireless Ar chitecture
by
Sachin Rajsekhar Katti
Submitted to the Department of Electrical Engineering and Computer Science
on A ugust 29, 2008, in partial fulfillment of the
requirements for the degree of
Doctor of Philosophy in Computer Science and Engineering
Abstract
Wireless mesh netwo r ks promise cheap Internet access, easy deployment, and extended
range. In their current for m, however, these ne tworks suffer from both limited through-
put and low reliability; hence they cannot meet the demands o f applications such as file
sharing, high definition video, and gaming. Motivated by these problems, we explore an
alternative design that addresses these challenges .
This dissertation presents a network coded architecture that significantly improves
throughput and reliability. It makes a simple yet fundamental switch in network design:
instead of routers just storing and forwarding received packets, the y mix (or code) pack-
ets’ content before forwarding. We show through practical systems how routers can ex-
ploit this new functionality to harness the intrinsic characteristics of the wireless medium
to improve p erformance. We develop three systems; each reveals a different benefit of
our network coded design. COPE observes that w ireless broadcast naturally creates an
overlap in packet s received across routers, and develops a new network coding algorithm
to exp loit this overlap to deliver the same data in fewer transmissions, thereby improv-
ing throughput. ANC pushes network coding to the signal level, sho wing how to exploit
strategic interference to correctly deliver data from concurrent senders, further increasing
throughput. Finally, MIXIT presents a symbol-level network code that exploits wireless
spatial diversity, forwarding correct symbols even if t h ey are contained in corrupte d pack-
ets to provide high throughput reliable trans fers.
The contributions of this dissertation are multifold. First, it builds a strong connec-
tion between the theory of network coding and wireless syst em design. Specifically, the
systems presented in this dissertation were the first to show that network coding can
be cleanly inte grated into the w ireless network stack to deliver practical and me asurable
gains. The wor k also presents novel algorithms that enrich the theory of network cod ing ,
extending it to operate over multiple unicast flows, analog signals, and soft-information.
Second, we present prototype implementations and testbed evaluations of our syst ems.
Our results show that network coding delivers large performance gains ranging from a few
percent to several-fold dep ending on the tr affic mix and the to pology. Finally, this work
makes a clear departure from conventional network design. Res earch in wireless net works
has largely proceeded in isolation, with the electrical engineers focusing o n the physical
and lower layers, while the computer scientists worked up from the network layer, with
the packet being the only interface. This diss ertation pokes a hole in this contract, dispos-
ing of artificial abstractions such as indivisible packe ts and point-to-point links in favor
of a more natural abstraction that allows the network and the lower layers to collaborate
on the common objectives of improving throughput and reliability using network coding
as the building block. At the same time, the design maintains desirable properties such