Re: [dtn-interest] Question

I think a lot of work in reliable multicasts has foundations in tornado
codes such as digital fountain.  They may be using non-proprietary stuff
here.

http://en.wikipedia.org/wiki/Tornado_code

Interleaving helps with gaps.

That being said, most of this discussion  is related to reliable transport
(convergence layer) more so than store and forward.

Will

******************************
William D. Ivancic
Phone 216-433-3494
Fax 216-433-8705
Networking Lab 216-433-2620
Mobile 440-503-4892
http://roland.grc.nasa.gov/~ivancic

> From: Daniel Ellard <dellard@bbn.com>
> Date: Mon, 28 Jan 2013 21:12:14 -0600
> To: "dtn-interest@irtf.org" <dtn-interest@irtf.org>
> Subject: Re: [dtn-interest] Question
> 
> On 1/28/13 8:44 PM, sitaraman@nmsworks.co.in wrote:
>> I did, and my understanding is it is an erasure code  with a larger margin
>> of error allowed for the signal can be recovered from a subset of the
>> encoded signals...so it still cant handle losses?
> 
> It is correct that a "digital fountain" is an instance of a forward
> error-correcting code.
> 
> As such, it has the property that it encodes a string of data D of
> length N as a set of much smaller strings e0, e1, ..., eX such that
> the original string D can be reconstructed from any subset of e0,
> e1, ... eX if the sum of the lengths of each e in the subset is
> greater or equal to N.  (an "efficient" FEC is one such that any
> subset of length N will suffice; my recollection is that fountain
> codes are not guaranteed to be efficient, but are generally within a
> small margin of it.)  It is possible to choose an encoding method to
> make each e computable independently of the rest, and the set of all
> possible e's for a given D practically unlimited.
> 
> The sender can continuously compute and transmit e's, and as soon as
> the receiver receives enough e's, the receiver is successful.  It
> doesn't matter how many e's are lost en route (or which are lost) as
> long as enough arrive eventually.
> 
> Fountain codes are one example of a FEC with this property, but the
> last time I checked (which was a while ago, admittedly) they had two
> drawbacks: first, the efficient implementations were protected by
> patents, and second, they weren't well-described or available as
> open-source.  Perhaps that has changed.
> 
> In any case, if you want to understand the basic theory of efficient
> FECs, Rabin's "Information Dispersal Algorithm", based on polynomial
> interpolation, is a good place to start.  For implementations of
> related codes that can be implemented efficiently, James Plank's
> work on erasure codes for storage is the most practical work of
> which I am aware.
> 
> -Dan
> 
> -- 
> Daniel Ellard, Ph.D.
> Senior Scientist, Network Research
> Raytheon BBN Technologies
> dellard@bbn.com
> 
> _______________________________________________
> dtn-interest mailing list
> dtn-interest@irtf.org
> https://www.irtf.org/mailman/listinfo/dtn-interest