Network Coding: Difference between revisions

From
Jump to navigation Jump to search
No edit summary
No edit summary
Line 1: Line 1:
==Introduction==
NetCod conference: http://www.netcod.org/indexold.htm


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==
==Software==

Revision as of 17:08, 19 October 2006

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]