Network Coding for Efficient Communication in Extreme Networks

Introduction

Network coding is an experimental protocol for delay tolerant networks. It aims on optimizing the packet delivery ratio in sparse and very sparse networks. Furthermore the network coding protocol (NCP) reduces the total number of transmissions in comparison with simple flooding algorithms.

Transmission method

Simple flooding algorithms simply forward a packet several times to increase the possibility that the packet will reach it's destination in a certain time interval or after a certain number of hops. Thus we have to trust to chance that we are forwarding the right packet to adequate nodes. Moreover the energy consumption of every single node might be important. Many packet transmissions cause a high energy use. Therefore a protocol that gets along with less transmissions reach the destination node is needed.

To achieve a lower number of transmissions every node in the network keeps sending linear combinations of the packages it has received or it is going to send itself instead of forwarding every single packet. Every packet (linear combination!) contains a so called encoding vector that indicates the source nodes of the packages being forwarded. Every source node is associated with a proper unit vector which is the initial encoding vector. Consequently a linear combination of two packets is made of a tuple consisting of a linear combination of the encoding vectors and a linear combination of the information vectors (data).

A new linear combination is called innovative if it increases the rank of the set of received packets of a node. Thus a solvable linear equation system is generated by each node. As soon as the rank of the set of received packets equals or exceeds the number of unit vectors (linear combinations of unit vectors!) in the equation system, the node can resolve the equation system an extract every single packet.

Managing Packet Generations

Of course we need to be aware of older and newer packets. Therefore a hash value over each packet id and source id is generated. Depending on the result of this operation the packet is added to the corresponding matrix. Depending on the generation age the rank of each matrix is reduced stepwise by replacing the last two rows of the matrix by a linear combination of these rows. Thus the probability that a packet that might be generated from that matrix is innovative is not reduced.

references

the paper: "Network Coding for Efficient Communication in Extreme Networks"

"The ZebraNet Wildlife Tracker"