Re: [Mldonkey-users] feature suggestion: forward error correction

[Goswin Brederlow]

Christian Brandt <address@hidden> writes:

> Am Donnerstag, 5. September 2002 12:26 schrieben Sie:
> 
> > Why should that increase bandwith? Now you need X blocks for a
> > file. With FEC you still need X blocks for a file. The only thing that
> > grows is the block list each client has.
> 
>  Ok, you got me :-)
> 
>  You are right, why download more than those junks needed to do a partial 
> reconstruction? Well, some good mathematics should now do a complete check 
> of the factors if this really helps the case or just makes it complicated. 
> There is surelly no trivial way to prove efficency for this as it also 
> depends a lot on the actual implementation.

As for efficiency I assume that bandwith and availability are the
limiting factors. CPU and disk speeds should be plenty.

So how efficient is FEC? Hard to tell.

Think about what happens if 2 clients connect and both want a certain
file. Unless something happens they will exchange all chunks the other
doesn't have. A chunk both clients have can't be exchanged.

How likely is it that two clients can't share a single block? It
certainly depends on how many blocks each client has and how many
blocks each client wants, which adds up to the number blocks in a
file.

If the file has N blocks and both clients have x blocks the
probability that they can't share a block is 1/[N over x].

Lets say both clients have 4 chunks and the file has 5 chunks:

5 over 4 = 5*4*3*2/1*2*3*4 = 5  =>  1/5 = 20% chance they can't share.

With FEC there are more chunks:

6  over 4 = 6*5*4*3/1*2*3*4 = 15  =>  1/15  = ~6.7% chance they can't share.
7  over 4 = 7*6*5*4/1*2*3*4 = 35  =>  1/35  = ~2.9% chance they can't share.
8  over 4 = 8*7*6*5/1*2*3*4 = 70  =>  1/70  = ~1.4% chance they can't share.
9  over 4 = 9*8*7*6/1*2*3*4 = 126 =>  1/126 = ~0.8% chance they can't share.

As you see with FEC its more likely that a connect results in sharing
a block. You get more successfull connects. I would say thats more
efficient.


The number of FEC blocks existing increases with the popularity of a
file. Everyone who has the complete file can generate new FEC blocks
and should do so in random order.

MfG
        Goswin