The first steps towards Network Coding

Early 2011 we were approached by 2 Danish students who were intrigued by the idea of implementing & exploring a concept called "Network Coding". A technique aiming at an increase of the WiFi throughput by aggregating multiple frames into a single frame, thus reducing the needed air time. With the help of mathematical calculations and some additional magic the receiving nodes would be able to decode & extract the frame they are interested in.

In the example illustrated below, the repeater R can save one transmission by sending the combined messages of A and B. A and B can calculate the message they want to receive by subtracting their own sent message.

Later in March the students joined the WirelessBattleMesh in Spain and gave a short introduction talk about their project which they named "C.A.T.W.O.M.A.N." (Coding Applied To Wireless On Mobile Ad-hoc Networks). The recorded talk discusses the mechanisms and benefits of Network Coding and should provide a good starting point to understand what this is all about.

Meanwhile they have continued working on the code and developed a first prototype which allowed gathering data about whether or not the concept brings benefits in the real world. The following graphs illustrates the throughput in kb/s with and without network coding (blue and greenline respectively) as well as the throughput gain (red line) achieved by network coding on a chain of 3 routers with clients attached to each end:

As the entire project was to become their master thesis it comes with an excellent documentation explaining every last detail of how it works and resulting performance analyses.

Their Network Coding enabled batman-adv code can is available on github for further testing / studies (it is based on a snapshot taken in early 2011). In the weeks / months to come we are going to polish the code until it can be officially merged with the Linux kernel code. [update] Meanwhile the Network Coding project and its code has moved to (catwoman branch), was rebased on the current master and further improved. An OpenWrt integration was also added to make testing easier. [/update] This should enable all interested parties to further test & extend the Network Coding concept.

Happy routing,

The B.A.T.M.A.N. team

coding.jpg (26.2 KB) Simon Wunderlich, 08/12/2011 07:42 PM

nc_gain.png (31.7 KB) Martin Hundebøll, 08/18/2011 07:04 PM