In this talk we address the issue of separation of channel coding and ``smart routing'', also referred to as network coding, in multihop network. In the seminal work by Ahlswede et al. it was shown that coding over independent information streams allows to better share the available network resources and increase the overall throughput in multicast scenarios, even in the case where the links in the network are error-free. This model implicitly assumes that relay nodes can operate without delay and complexity constraints. In this work we constrain the processing capability of the relay nodes. We consider a source that transmits to a receiver by routing the information packets over a communication network represented by a directed graph. We examine rate benefits that finite complexity processing at the intermediate nodes may offer. We show that the processing capabilities of the intermediate nodes affect not only the end-to-end achievable rate, but also the optimal routing strategy. We show that there exist configurations where the optimal rate is achieved only when coding across independent information streams (channel coding and routing cannot be separated); that optimal processing is function of the particular set of channel parameters and not only of the network topology; that small processing capability suffices to achieve a large fraction of the ultimate network performance; and that there exists a connection between linear codes and routing for a special class of graphs.

(Joint work Christina Fragouli at EPFL).

Daniela Tuninetti joined the Electrical and Computer Engineering Department at the University of Illinois at Chicago in January 2005 as an Assistant Professor. She received her PhD from the Eurecom Institute/Telecom Paris (Sophia Antipolis, France) in 2002. She held a post-doc position for two years with the Mobile Communication Laboratory at the Swiss Federal Institute of Technology (Lausanne, Switzerland).