On the Capacity of Information Networks

Опубликовано 6 сентября 2016, 5:21

Traditionally, routers in a communication network forward each data packet to a single neighbor. Under this assumption, information in a communication network flows much like a fluid though a system of pipes. But recent work has explored other ways that information can ``flow'' that a fluid cannot. In a network using {\em network coding}, a router can transmit any function of the information it receives; for example, after receiving bytes $x$ and $y$, it can transmit the function $x + y$. How much is the capacity of a network increased by giving such computation power to routers? And how powerful must the routers be to achieve the maximum capacity? We provide some answers in this talk, but many fundamental open questions remain.