[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [Mldonkey-users] feature suggestion: forward error correction
From: |
Goswin Brederlow |
Subject: |
Re: [Mldonkey-users] feature suggestion: forward error correction |
Date: |
06 Sep 2002 05:59:57 +0200 |
User-agent: |
Gnus/5.0808 (Gnus v5.8.8) XEmacs/21.4 (Honest Recruiter) |
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