Network Coding

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

To achive 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. Every packets (linear combination!) contains a so called encoding vector that inticates the source nodes of the packages being forwarded. Every source node is associated with a proper unit vector which is the initial encoding vector. 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 ZebraNet Wildlife Tracker ("http://www.princeton.edu/~mrm/zebranet.html")

NetCod conference: http://www.netcod.org/indexold.htm

Software

Similarity flooding [1]