Consider a network consisting of point-to-point communication
channels. Each channel transmits information noiselessly subject to the
channel capacity. Data is to be transmitted from the source node to a
prescribed set of destination nodes. Given the transmission requirements,
a natural question is whether the network can fulfill these
requirements and how it can be done efficiently.
In existing computer networks, information is transmitted from the
source node to each destination node through a chain of intermediate
nodes by a method known as store-and-forward. In this method, data
packets received from an input link of an intermediate node are stored
and a copy is forwarded to the next node via an output link. In the
case when an intermediate node is on the transmission paths toward
multiple destinations, it sends one copy of the data packets onto each
output link that leads to at least one of the destinations. It has been
a folklore in data networking that there is no need for data processing
at the intermediate nodes except for data replication.