Network coding is a method of optimizing the flow of digital data in a network by transmitting digital evidence about messages. The "digital evidence" is, itself, a composite of two or more messages. When the bits of digital evidence arrive at the destination, the transmitted message is deduced rather than directly reassembled.
The concept of network coding was first introduced by R. W. Yeung and Z. Zhang in 1999 as an alternative to routing. In a traditional packet-switched network, data flows in defined, discrete "pieces" from the source to the destination like corpuscles in the bloodstream. At the transmitting station, the outgoing message is broken into packets, each of which contains some of the message data intact. The packets do not necessarily all travel along the same route but they all eventually arrive at the same destination, where the receiving computer reassembles them into the original message. The main problem with this method is that when the overall network traffic volume is high, bottlenecks are common, resulting in long delays. Packets tend to bunch up at certain nodes, sometimes in excess of the nodes' ability to process them. Other routes and nodes may remain under-utilized.
In network coding, routers and switches are replaced by devices called coders. Instead of directing the packets toward their ultimate destination like blood cells through a system of arteries, the coders transmit metadata in the form of digital evidence about the message along multiple paths simultaneously. Conversely, the metadata arriving from two or more sources may be combined into a single packet. This distribution method can increase the effective capacity of a network by minimizing the number and severity of bottlenecks. The improvement is most pronounced when network traffic volume is near the maximum capacity obtainable with traditional routing. When a receiver has enough digital evidence, it can compute the intended message/packet. Even if some packets on some of the routes are lost or mutilated, the original message gets through if the received digital evidence is sufficient.
In network coding, the data does not depend only on one transmitted message but also on the contents of other messages that happen to be sharing the route at the time of transmission. For this reason, network coding is more resistant to hacking, eavesdropping and other forms of attack than traditional data transmission. The extent of throughput improvement that network coding can provide depends on the network topology and on the frequency and severity of bottlenecks. In no event does network coding reduce the throughput compared with the routing method. Network coding may prove especially useful in multicast networks, wireless sensor networks, digital file distribution and peer-to-peer (P2P) file sharing.