Abstract

Bobby Kleinberg: Network Coding

       What is the maximum rate at which one can simultaneously transmit data streams in a network with error-free links of finite capacity? Surprisingly, this fundamental question has never been answered.  When the only operation that can be performed on data is routing (i.e. storing and forwarding packets without modifying their contents) then the problem is called multi-commodity flow, and its solution is well known.  But when nodes are allowed to send outgoing messages by combining two or more incoming messages (e.g. taking the XOR of two packets) the situation is much less well understood.  There are examples of directed graphs where these "network coding solutions" achieve a faster transmission rate than that which can be achieved by routing.  For undirected graphs in which each stream has a single sender and single receiver, no such examples are known.

I will introduce the subject of network coding via some illustrative examples, and then I'll present some recent results and open problems in this area, guided by questions such as: "How much faster can we transmit data streams using network coding versus routing?  Can we identify broad classes of situations in which there is or isn't a speedup?  How is the network coding rate related to combinatorial parameters like the sparsest cut in the network?  How does it depend on other network properties such as packet sizes, or the amount of memory used for buffering messages?"