Quite precise description of after-download error correction

[doker]

Quite precise description of after-download error correction using Hashing.

I'd like to show how i see a good file error handling.
Befor i start:
my: - my dc
other: - other dc

this will be kind of a dialog and an algorithm, also.
--
me: thinks "file x.avi is downloaded."
me: thinks "Chcecking whole file hash."
me: thinks "Error. File hash is incorect"

-=now=-
me -> other: "please send me a hash of x.avi from 1 byte of 10485760bytes (10mb)"
other: "hashing the part of the file"
other -> me: "hash for the part is (ex) XADFG2"
me: thinks " this part is ok. lets chce the other"

-= and now =-
me -> other: "please send me a hash of x.avi from 10485762bytes of 10485760bytes (10mb)"
other: "hashing the part of the file"
other -> me: "hash for the part is (ex) GHTOSD0"
me: thinks " this part has an eror. let's dig hear"

-=then =-
me -> other: "please send me a hash of x.avi from 10485762bytes of half of 10485760bytes (10mb)"
other: "hashing the part of the file"
other -> me: "hash for the part is (ex) ASFGX"
me: thinks " this part is ok. lets chce the other"

-=then =-
me -> other: "please send me a hash of x.avi from 10485762bytes + half of 10485760bytes, of half of 10485760bytes (10mb)"
other: "hashing the part of the file"
other -> me: "hash for the part is (ex) 7SFGX"
me: thinks " this part is ok. lets dig inhere"

and so on until:
me: thinks " this part is erratic and the size is about 1mb so lets download this part."

-----------
for ex. eMule correction is worse because emule randomise the pleace in the part where he starts downloading from.


----
"my" correction could be done even during first download after ending for ex. every 10mb.

CU,

Doker

PS. What do you thing? You think it's good and possible?

[GargoyleMT]

That's... elaborate.

The scheme that BCDC is using is a Tiger Tree hash. There are two limits AFAIK, there's a depth limit (of how many child hashes will be kept), and a minimum block size (for when the tree depth < max depth). The whole hash will be exchanged in C2C, and is a relatively small transfer - well < 100kbytes. The downloading DC will be able to use the tree hash all by itself to verify the file, and will not need a back and forth communication method like you describe.

The above description is an approximation, as I don't have first hand experience with Cologic's hash code. However, it should give you an idea of what's done, and how it compares with what you're thinking.

[doker]

well, the best would be to send file part hash after every segment downloaded or better before (should be send twice to verifie it's errorless).

But speaking about correcting downloaded files (which is impossible now) my algorithm is (if you say your is about 100kb) would use less bandwidth, i think (estimating).

[GargoyleMT]

well, the best would be to send file part hash after every segment downloaded or better before (should be send twice to verifie it's errorless).

No, not at all. The QueueManager should have the full hash for the initial file that you downloaded, and all alternates should be added because they have the same hash, or because when downloaded, the hash checks them out fine.

When the tree is sent, you can hash the subnodes to make sure that the root hash is good, the TTH is capable of self-verification in that respect.

But speaking about correcting downloaded files (which is impossible now) my algorithm is (if you say your is about 100kb) would use less bandwidth, i think (estimating).

That size (100kb) is just a guess, and no, I think that the scheme cologic came up with (which others in turn originated) is more logical, and would save bandwidth because you only have to transfer the hash tree once. The rest of the segments can be downloaded with $GetZBlock, and that means no real overhead.


If you really think your scheme is better, you're free to implement it... and see if it wins out in practice over the hash scheme in BCDC.

[doker]

No, not at all. The QueueManager should have the full hash for the initial file that you downloaded, and all alternates should be added because they have the same hash, or because when downloaded, the hash checks them out fine.

I can see you don't understand me.
Also file should have its hash and every segment downloaded shuld aslo have it to now straight off if the part has an error.

my method does not download whole tree but only those roots that have errors, and there are no limits.

Yes, its a good idea to hash parts of file already when file is being hashed to use cpu only once (not every time there is a hash query) but there should be a query for thiner parts.

[doker]

And no(!), what i've shown is nothng new. eMule checkes downloaded part straight off after downloading it.

[GargoyleMT]

Yes, in discussing with cologic, it seems I missed part of your basic assumption, which is bisecting the file until you find the corrupted segment.

That's a fine way to do it if you're hashing on the fly... which seems to be your basic assumption.


Hashing on the fly neglects some of the other benfits of hashing - like integration with hash archives - like bitzi.com, so I never considered it a viable option. BCDC currently has background hashing of all files in the share, so unless someone proposes an alternate scheme and codes it, this is likely how it will be thoughout the DC++ mods.

You probably feel I've missed some of the finer points of your post, feel free to point them out with a little more clarity.