Breaking Network Logjams
An approach called network coding could dramatically enhance the efficiency and reliability of communications networks. At its core is the strange notion that transmitting evidence about messages can be more useful than conveying the messages themselves
Credits: MATT VINCENT
Why Network Coding Can Speed Transmissions With coding (figure 3), the transmitter can convert the three incoming messages into six new information streams, one for each link to the intermediate nodes. These new streams would be different linear combination of three original messages, and receipt of any three of these combinations would allow a receiver to reconstruct the original three messages. So, all receivers would get all three messages at once, and the reception rate would thus be three messages per second.
Typically, transmission speeds are discussed in terms of bits per second, rather than messages per second. If we extend this figure to include any even number--2h--of intermediate nodes and provide at least one receiver for each possible unique combination of h such nodes, we can transmit h bits per second with coding but fewer than 2 bits per second without it. So network coding speeds communication by a factor of h/2. Clearly, then, the benefit of network coding can be made very large as the network grows. –Michelle Effros, Ralf Koetter and Muriel Médard
Why Network Coding Can Speed Transmissions For any single message to make it to all receivers at once, it must be sent to more than half of the intermediate nodes, (at least four in this example). This requirement leaves too few links (two) open for the other two messages.
To understand why more than half of the intermediate nodes must be used for each message, imagine that the transmitter sends one missive (red) to half of the nodes—say, to A, B and F. In that case, receiver I (green), which gathers all of its information from the remaining three nodes (C, D and E), cannot get that message. The same problem would occur for any other set of three or fewer intermediate nodes. If the other messages are sent to the two unused intermediate nodes, some receivers may get more than one message in the same time interval, but at least one of the 10 receivers will fail to get the complete set of three messages sent by the transmitter.
Why Network Coding Can Speed Transmissions The network presented here (figure 1) can help to show how network coding can greatly improve data-delivery rates to receivers. We did not invent this example; it appears in many papers, including “Polynomial Time Algorithms for Multicast Network Code Construction,” by Sidharth Jaggi and co-authors including one of us (Effros), published in the IEEE Transactions on Information Theory, Vol. 51, pages 1973-1982, 2005.
In this network a transmitter feeds information (literally, bit streams) to 20 receivers (G through Z) but connects directly to only six intermediate nodes (A through F). Each receiver gets information from three of the intermediate nodes (labeled below the receivers); every possible combination of three distinct nodes is represented in the receivers and occurs only once. A single link, or “edge,” in our system can transmit one message per second downward through the figure. Because every receiver has just three incoming edges, the maximal achievable rate of information flow into each receiver is three messages per second. Suppose that the transmitter has received three messages (red, yellow and blue). Can all three get conveyed all 20 receivers simultaneously? Without coding, the answer is no; overall, fewer than two messages per second will be relayed to the receivers. Why so? See figure 2. Advertisement