Erasure-Coding Based Routing for Opportunistic Networks: Difference between revisions
No edit summary |
No edit summary |
||
| Line 3: | Line 3: | ||
==Erasure Codes== |
==Erasure Codes== |
||
Erasure Codes convert a message into a large number of code blocks so, that any sufficient large subset of this blocks can be used to reconstruct the message. In more detail, if an erasure code has a message of size <math>M</math> and a replication factor <math>r</math> as input, it produces <math>M*r/b</math> equal sized code blocks of size <math>b</math>. Any <math>M/b</math> code blocks can be used to reconstruct the message. So only <math>1/r</math> code blocks are needed. |
|||
<math>\frac{1}{n} </math> |
|||
==Material== |
==Material== |
||
Revision as of 18:04, 19 October 2006
Introduction
Most current approaches for routing in DTN are based on sending multiple identical copies of packages over different paths. There is always a tradeoff between overhead and delay. The flooding algorithm, for example, has the best delay, but the worst overhead. The direct algorithm on the other side has the worst delay but the best overhead. We present an erasure coding based algorithm, that achieves a better worst-case delay performance than existing approaches wiht a fixed overhead.
Erasure Codes
Erasure Codes convert a message into a large number of code blocks so, that any sufficient large subset of this blocks can be used to reconstruct the message. In more detail, if an erasure code has a message of size and a replication factor as input, it produces equal sized code blocks of size . Any code blocks can be used to reconstruct the message. So only code blocks are needed.
