Network Coding

Recently I read the paper "XORs in The Air: Practical Wireless Network Coding", and was impressed with the use of network coding. The idea behind network coding is simple. First, there is the principle that if A xor B = C, then B = A xor C and A= B xor C. Applied to a wireless network setting, suppose there are 2 hosts and a router. Host 1 has A but wants B, and host 2 has B but wants A. The router can satisfy the hosts in 2 transmissions by providing each hosts with the needed packet. Or, the router can satisfy both hosts by simply transmitting C to both simultaneously.

Network coding has large potential benefits for wireless communication, because often the bottleneck is the wireless medium. By reducing the amount of transmission by a node, more data is able to be sent. The paper I mentioned names several topologies and classifies the coding gain, or the amount by which network coding reduces the number of data packets to be sent. Some topologies provide a 1-2x coding gain, and a special "wheel-like" topology provided an unbounded coding gain. A wheel topology is where you have N hosts around 1 router. Given a sending host, every other one except for the host directly across it can hear the sender. They mention that classifying coding gain for an arbitrary topology is a hard problem though. I wonder what has been researched in that area.