Network Coding: Difference between revisions
Jump to navigation
Jump to search
No edit summary |
No edit summary |
||
| Line 1: | Line 1: | ||
==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 |
NetCod conference: http://www.netcod.org/indexold.htm |
||