On the Throughput Improvement due to Limited Complexity Processing at Relay Nodes

We consider a source that transmits information to a receiver by routing it over a communication network represented by a graph and examine rate benefits that finite complexity processing at the intermediate nodes may offer. 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 a function of the particular set of channel parameters and not only of the network topology; and that there exists a connection between linear codes and routing for a special class of graphs.