Jump to content

Ban algorithm faulty in beta 4.25?


Lexxington

Recommended Posts

I'm sorry to keep banging on about this but...

The ban system used by uTorrent doesn't seem to be working correctly.

Case in point:

A torrent I'm downloading is suffering corruption. Not particularly severe, but noticeable with the 2 Mb piece size and quite a few clients marked up with Hash errors.

OK, the peer that is uploading to me at the highest rate and more than ANY of the other peers is being marked up as equal top of the Hash errors list!

That peer has given me over 180 Mb of data and has 3 'strikes' against his name. There is another peer also with 3 errors. This one has given me 5.8 Mb of data.

I 'ban' the 5.8 Mb peer using Peer Guardian 2 and the corruption stops (mostly), so I close and re-start uTorrent and start monitoring afresh.

Again, after a re-start the big gun gets marked up as a corruptor along with a few others and again creeps up to the top of the list along with another corruptor whom I also ban in Peer Guardian and this time the corruption stops dead thereafter!

Anyway, the point is that had I allowed this to continue un-monitored the 'big gun' would have been banned along with the real corruptors! To add insult to injury he was my absolute best peer too!

Ever heard of chucking the baby out with the bath water?!

It's obvious WHY the big gun is being marked up as a potential corruptor, 'cos he has his hand in quite a few pieces, but this won't prevent uTorrent from having him banned after being associated with the real corruptors!

Surely the programmers can separate out peers and assign them to separate pieces to discover just who is and who isn't guilty?

You could even be more cunning and log IPs versus 16 Kb blocks (you only need a few), and wait until you get a complete piece and retrospectively calculate the MD5s or SHA-1 hashes for those blocks to see which were corrupt and ban accordingly.

Easy really?!

Link to comment
Share on other sites

No, it's the fact that you can't do that. Every peer involved in a piece gets caught in the crossfire, unfortunately. Not much you can do about it because there's only an SHA-1 for the entire piece, not the individual 16K chunks.

Yes and No.

Yes, every peer involved gets tarred with the same brush, but thereafter we can ensure that it doesn't happen again.

You log the IP of the peers involved in d/ling that piece and thereafter keep a record of the MD5 / SHA-1 hash of one or two 16 Kb blocks associated with the same peers and piece.

You then sideline those peers (or assign them INDIVIDUALLY to a different piece each) until that previously corrupted piece is successfully downloaded and SHA-1 checked (from other peers). Having done so you can then compare the hashes of those 'suspect' 16 Kb blocks with the known good ones.

As I said, easy!

Just because hash checking the 16 Kb blocks isn't part of the BT protocol doesn't mean you can't retrospectively apply hash checking to those 16 Kb blocks when the need arises.

It's just the details, not the principle that needs sorting out.

The thing is, that it IS possible to do.

Banning your best peer seems stupid to me!

Link to comment
Share on other sites

  • 8 months later...

This is a revive of a pretty old thread, so I don't know if I am going to suggest something already said/done.

The banning algorithm above is good, although it requires more memory and bandwidth to be used, as well as longer time to detect the poisoner. I'd suggest something diferent, yet very similar:

1. If a failed piece is detected, mark all the peers involved in downloading (I believe uT is already doing this) - let's say there were 4 of them.

2. Since this piece (although bad) is already written on my hard-disk, re-download the 16K chunks that were got ONLY from peer #1 (out of 4 marked), but from another peer (peer not involved at all in this piece) - I know this needs additional info on what chunk relatees to what peer, and I believe uT is NOT doing this since it requires more memory, but could be implemented.

3. After re-downloading these "suspected" chunks try to hash-check the piece again. If it passes this time, then peer #1 is possible poisoner. Put him on "watch" list for future downloads, etc... you got the idea.

4. If second hash-check is still bad, try the same with peer #2, but with HIS chunks this time.

Basically, this is a simple algorithm that needs some more refining (it assumes there is only one poisoner - if there are more present, this could lead to recursive problems), but seems to be lowest-bandwidth consuming, IMHO.

If it is not too much to ask for, maybe Firon/ludde would like to describe current banning algorithm (ver 1.6)?

Also, related to this, is it possible to add feature like per-piece logging (right click on a row in piece tab ->log this piece), meaning logging only communication that involves this particular piece (for manual analyzing of peers involved)?

Link to comment
Share on other sites

Switeck, I believe your idea was to keep swarm as smallest as possible in order to identify corrupting peer more quickly?

I think that is not very efficient - even on very small swarms, I cannot expect to get whole 2MB or 4MB piece from one single peer. Also, it does not saves me from re-downloading one whole piece from scratch for several times (currently 6 times, if I'm correct) - again lots of wasted time.

And yes, it requires my personal monitoring, which I really don't want :)

Link to comment
Share on other sites

Then the problem also lies with whoever created the torrent/s not caring that their gigantic piece size makes a corruptor's job VERY easy.

If you don't want to do much personal monitoring, download better blocklists to begin with. While it's true there's corruptors operating out of regular consumer ip blocks, the worst ones are almost always in narrow commercial ip blocks. If you see a tight grouping of ips...you almost don't have to ASK if they're bad or not.

Force encryption and disable legacy connections. Your connectivity on the torrent may drop like a stone I admit, but it basically eliminates the older generation of corruptors. It also prevents them from bit-flipping data (to corrupt it) AFTER a BitTorrent client sends it out...using a man-in-the-middle style attack. Such data would be tossed on receiving as the encryption crc wouldn't match the data -- it might even force/demand resends from corruptors till they send you a chunk that matches the encryption crc. Burning their upload bandwidth at the price of your download bandwidth isn't such a bad thing. With a rewrite of µTorrent, each data packet a BT clients sends that does not match encryption crc could be treated as a hashfail -- eliminating them potentially without forcing the redownloading of a whole piece. A corruptor could be written to encrypt AFTER corrupting...but that won't be an easy job to do without bugs, which might allow us to attack them another way.

A simpler rewrite of the ban algorithm would be a ratio check of failed hashes versis total MB sent for each ip. If an ip sends 1+ GB and has 5 hashfails, I'd be more willing to forgive it than one that sent <1 MB and 5 hashfails. Also, as an advanced setting, it'd be a nice feature to set the goalpost for hash fails=ban...instead of setting it to 5, make it 10 or more.

Another possible feature to add to µTorrent would be automatic adding of hashfail ips to the ipfilter.dat instead of dropping/forgetting them on shutdown.

Link to comment
Share on other sites

No, it's the fact that you can't do that. Every peer involved in a piece gets caught in the crossfire, unfortunately. Not much you can do about it because there's only an SHA-1 for the entire piece, not the individual 16K chunks.

Well, the simple solution is to have a piece picking algorithm that works in the following way:

When you start downloading a piece off Peer A, only Peer A can be requested for subsequent blocks from that piece. If (when you get all the blocks in the piece) the piece fails the hashcheck, then you know your culprit.

To combat the problem of slow peers hogging up pieces, you implement EndGameMode which removes the limit that only peer A can be requested from a piece that Peer A started. (which seems to be uTorrent's current behavior). Some tweaks can be applied on top of that to improve efficiency*. It won't affect download speed but it will mean accurate tracking of failing hashes. The only place download speeds might be affected is the time period just before the torrent enters end game mode. But this can be minimised by optimising the point where you enter endgame mode.

*if a peer disconnects, you can allow a different peer to continue his piece, but if that piece doesn't pass the hashcheck, then you dont have to mark him as sending a bad piece.

Link to comment
Share on other sites

Ehm... how would that work? If you "remove the limit that only peer A can request a block" then you're just back to square 1: where we are right now.

Edit: Regarding the edit, then if the first person who disconnected WAS the person with the corrupt piece, the proposed ban algorithm would be useless, as it would end up not banning anyone at all -- anyone can share part of a corrupt piece and then snub.

Link to comment
Share on other sites

EndGame mode is typically implemented when you have 5-10 pieces remaining to download. I.e. the torrent is at about 99% completion. If you read up on endgame mode you'll see how it works.

The benefit is that for 97%+ of the torrents life you have accurate tracking of who sends bad pieces. For the remaining 3% (or less) when you enter endgame mode, it doesn't matter anymore, as you'll typically have finished the torrent within 2 minutes of entering endgame mode.

Edit: Regarding the edit, then if the first person who disconnected WAS the person with the corrupt piece, the proposed algorithm would be useless. Then anyone can share part of a piece and then snub.

Yes, they can. Those are corner cases which i haven't thought about. Your options are either mark both peers as providing failed pieces or mark neither. Alternatively, bite the bullet and if a peer disconnects, just drop all pieces he sent (which is what i do currently).

Link to comment
Share on other sites

What if a bunch of pieces were coming from a single peer who was poisoning the swarm? What if the peer disconnects from the swarm in the middle? In any of the cases, µTorrent won't chuck the pieces since it doesn't know if it's corrupt until it actually completes. If the latter case were the situation, would the piece still be locked to the disconnected peer?

Edit:

lol I'm starting to confuse myself... I need to make sense of what I just said =o (it made sense in my head earlier :<)

Either way, locking pieces can easily slow things down, as you're decreasing the possible sources for data by doing so. Having 2+ people work on a single piece is clearly faster than 1, and if you take all the pieces into account, the difference can really add up.

Link to comment
Share on other sites

Either way, locking pieces can easily slow things down, as you're decreasing the possible sources for data by doing so. Having 2+ people work on a single piece is clearly faster than 1, and if you take all the pieces into account, the difference can really add up.

It is faster if there is only once piece left, but having 2 peers work on two seperate pieces is *just as fast* as two peers working on one piece. Also the added advantage of being able to tell exactly what peer is causing corruption is a bonus, and the main point behind the alternate algorithm (which performs the same as uTorrents current one in 99% of cases).

Once again, it's up to the client to decide what to do with part finished pieces if a client disconnects. There are a few possibilities :P

In the case where there is only one piece left, you'll be in endgame mode, so you will have multiple peers downloading the same blocks from the same piece to get them in fast. Thats the way endgame works.

Link to comment
Share on other sites

You can only compare bad pieces to good if you want to reserve large chunks of ram (fast) or hard drive space (slow) to do so. Then you'd have to fail a hash and somehow get the piece completed in possibly a highly polluted environment...so the one place it's most needed, it wouldn't work too well.

Link to comment
Share on other sites

Bear in mind that this is just an example of how it could work:

Me -> request PeerA:Piece1:Chunk 1

Peera -> Sends piece

Me -> Write piece to disk

Me -> request PeerA:Piece1:Chunk 2

Peera -> Sends piece

Me -> Write piece to disk

Me -> request PeerA:Piece1:Chunk 3

Peera -> Sends piece

Me -> Write piece to disk

me -> having received all pieces, read em back off disk and hashcheck. If passed, all good. If failed, mark peer A as being bold.

Replace "write to disk" by "save in memory buffer and flush to disk when buffer is full" where necessary. Total memory usage isn't increased, but disk reads would be increased.

You can't have it both ways. You can't have low memory usage, low disk reads and 100% accurate tracking of who sends bad pieces. You can *only* get two out of those three, pick your 2.

Link to comment
Share on other sites

Now my point is if you're seeing a single piece come from multiple sources then in the event of a hash fail and then success you have to have recorded the entire failed piece as well as which ips sent you which parts of it.

To do that, either µTorrent starts eating mad amounts of ram in the event of multiple hash fails on the same piece (especially in the case of 2 or 4 MB pieces!) or your hard drive gets lots of "piece" files storing the failed pieces (along with index files telling which parts of each piece came from which ip). Either one will be a messy solution!

The problem is µTorrent tries too hard to get a single piece -- it attempts to download that piece from many sources at once. This is also coupled with corruptors intentional or otherwise may only be slipping in 16 KB of upload in a particular piece due to their inability (or not wanting) to upload quickly or for any extended period without problems.

What we're looking for is repeat offenders. The occassional hah fail from an ip should be ignored. Currently, it isn't...once an ip accumulates 5 hash fails, it gets banned till you reset µTorrent (or reset bans under advanced right-click menu on a torrent)...even if it sent 10 GB in the process!

Even a slight improvement in the process may make µTorrent automated enough to complete a torrent that has many corruptors on it.

*** Some process of "forgiving" hash fails for ips that give lots of good data MUST be added. There are too many D-Link router DMZ data destroyers out there to ignore! Going further, users should be better notified if they are sending some/lots of hash failed data!

Marginal contributions (16 KB or less) of a piece could have a discard option, as any connection that is broken in the middle of transfer has a much higher likelyhood of the transfer being corrupted in some way.

Tiny overlaps of data (like 1-5 bytes) between sources could be used as a checksum even in the event the piece is incomplete. If 2 ips offer overlaping data that doesn't match, then it won't do any good to attempt to download the same piece from BOTH of them again! Even better, at the start and end of each new piece you could grab 1-5 bytes from the previous or next piece. If you already had either piece (and is understood to have passed the hash test) then ANY ip offering bad data from the already-known-good piece gets instantly +1 hashfail rating.

A "smart" ban logic might enable dropping of marginal contributions by multiple sources and/or tiny overlaps of data only AFTER having a hash fail (or multiple hash fails in 'x' minutes) and disable these features after at least 1 repeat corruptor gets banned and/or considerable time (10mins? 1 hour?) has passed without another hash fail. This would avoid the extra bandwidth costs these features would have unless hash fails were occuring.

Link to comment
Share on other sites

Now my point is if you're seeing a single piece come from multiple sources then in the event of a hash fail and then success you have to have recorded the entire failed piece as well as which ips sent you which parts of it.

From the sounds of it, that's exactly what uTorrent is doing right now. It requests each block from each piece from different people. This means that a single piece finishes faster, but it's impossible to tell which block was corrupt, so if the overall piece fails the hashcheck you have to mark each peer who you requested a block off as a contributor to a hashfail. i.e. sending corrupt data. This is Not Good . That's the problem with this method. On the other hand, you know know that only pieces that have passed the hash check will be written to disk and they don't need to be re-read to hashcheck the piece.

Method 2: My way.

Once i start requesting blocks from Piece 10 off PeerA, i will only ever request blocks from Piece 10 from Peer A (unless he disconnects and i make someone else restart that piece). Now i *know* exactly who has sent me a corrupt piece as *all* the blocks have come from the same peer. The only problem with this method that would in any way make it inferior to the method that uTorrent is using now is that in order to run the hashcheck, each completed piece must be read back off the disk in order to hashcheck it. (unless you store each received block in memory until the entire piece has arrived. This woud be large memory bloat).

Other than the rereads, this method is just as memory efficient as uTorrents existing method. I think it's well worth the trade off. And anyone who has experienced the case where their "good peer" is being banned wrongly probably would agree.

You could also change the code to do a proportional thing. For example instead of banning on 5 peers, ban on 5% (tweak that value as needed) bad data received from that peer. But of course, you still end up with the problem that you might ban your good peer, but the risk might be reduced. I'm not too sure.

Also, overlapping requests by 10 bytes makes you 0.006% more likely to notice the corrupt section. You have to remember that each block is 16384 bytes long, and a piece being up to 2 megabytes. So that kind of method is useless, and a waste of memory.

EDIT: You can go into huge complicated algorithms for seperating out peers and monitoring how the hashfails occur then, but thats messy and ugly. The principle of KISS (keep it simple, stupid) would be much better applied :P Method two allows 2 lines of code to 100% accurately track how many hashfails each peer has had.

if(piece.HashPassed == false)

peer.HashFails++;

That is a lot better than writing a 500 line block of code which still has a good chance of banning the wrong peer. If you're really worred about memory usage in both methods, check out the screenshots. http://picasaweb.google.com/alan.mcgovern/DebianTorrent. I assume uTorrents high memory usage is due to the disk cache. My disk cache is 256kB. My method's effiency doesnt improve unless you have a *huge* memory buffer. So 256kB is perfect.

Link to comment
Share on other sites

"From the sounds of it, that's exactly what uTorrent is doing right now."

No, µTorrent obviously stores a list of peers which sent a piece...BUT it only has 1 "working copy" of the piece (regardless of success or failure) from what I can tell. It probably scraps the entire piece if the hash fails and redownloads it as though there were nothing there.

The ram cache could be treated as a separate "copy" of a piece in the event of a hash fail -- but as of now there's NO attempt by µTorrent to compare the ram cache "new copy" with the failed hash "old copy" piece that was already written to the drive. And there's probably no memory, rhyme, or reason to which sources a piece is re-downloaded from after a hash fail. So when a piece is reattempted, it could be a whole new set of ips that it is downloaded from. Without some consistancy, you cannot use scientific method.

"it's impossible to tell which block was corrupt, ... That's the problem with this method."

The problem as I pointed out is multi-part:

1.µTorrent tries too hard to get a single piece -- by using multiple sources

2.Corruptors need only slip in 1 wrong BIT to ruin the whole piece, though they may have to give 16 KB to do so.

3.An ip has to generate 5 hash fails before it will be banned...giving an array of corruptors using 100's of ips many chances to corrupt your download.

4.Good ips are obviously and often getting banned in the process because they also contributed to pieces that fail hash check.

"Once i start requesting blocks from Piece 10 off PeerA, i will only ever request blocks from Piece 10 from Peer A (unless he disconnects and i make someone else restart that piece). Now i *know* exactly who has sent me a corrupt piece as *all* the blocks have come from the same peer."

Yes, the simpliest solution is to just force downloading of a single piece from a single ip. That way, there's only 1 ip that's possibly at fault for any corruption it would seem. Except actually it's at least 2 ips that's possibly at fault...the ip you got the bad block from, and your own ip...because your end may be the cause of the failed hashes.

In the instance of 2 MB piece size and 50 seeds+peers connected to you...for you to attempt to download a separate piece from each one would either require 100+ MB of ram cache to make it quick to check as it goes, or it has to write to disk long before finishing each piece and read whole pieces back from disk anytime a piece completes to hash-check it.

I don't think µTorrent is that memory-wasteful. In µTorrent's Speed window, Disk Statistics...while seeding the read statistics show average size "grabs" from cache as 15.9 KB size and 127 KB from file. This is in spite of piece sizes for all my active torrents being 256 KB and larger -- µTorrent does not seem to be pulling whole pieces into ram at once.

I'm not arguing that µTorrent probably shouldn't be rewritten to do single source per piece downloading, only that it would NOT be a simple rewrite to do so! ...and also that there are some semi-reasonable memory and logic reasons that µTorrent wasn't programmed this way to begin with.

I *definitely* think µTorrent should have an option to download from only 1 source per piece. For very slow connections, it could even be enabled by default...but is probably left disabled otherwise. Better yet, it could turn itself on/off automatically in the event of a hash fail! After 1 hash fail, all "questionable" ips that took part in the failed hash piece could be checked by being forced to contribute a complete piece by themselves. There would be minimal bandwidth loss that way. Only if there's very few unstarted pieces would this be impratical because the remaining piece/s would download much more slowly because they are restricted to 1 source each.

"You could also change the code to do a proportional thing. For example instead of banning on 5 peers, ban on 5% ... you still end up with the problem that you might ban your good peer, but the risk might be reduced."

On a torrent where corruptors outnumber good sources, this is not only possible...it's most likely outcome! The corruptors are trying to poison every piece and only need to slip in 1 bad 16 KB section to do so. Until an ip gets banned I think µTorrent makes no distinction on which ips it uses for a piece, except loosely based on speed and whether the source has you choked/snubbed. In short, it's possible every noncorrupt peer may end up banning every other noncorrupt peer before the true corruptors are weeded out!

"Once i start requesting blocks from Piece 10 off PeerA, i will only ever request blocks from Piece 10 from Peer A (unless he disconnects and i make someone else restart that piece)."

I disagree strongly. A piece should not be restarted unless it is confirmed to be bad due to a hash fail. Otherwise you may incur wasteage amounts that top 20% even on a torrent with NO bad sources just due to connection churn! The threat of a bad piece simply does not justify throwing away all the data already gotten, only maybe the last (partial?) 16 KB block. Even that will cause some wasteage, but alot less for piece size >128 KB.

"Also, overlapping requests by 10 bytes makes you 0.006% more likely to notice the corrupt section. You have to remember that each block is 16384 bytes long, and a piece being up to 2 megabytes. So that kind of method is useless, and a waste of memory."

The download requests do not have to fall on even block intervals. The only criteria is no more than 16 KB can be requested at a time. Only the starting and ending points for a source need to extend into the next source's section. So the amount of extra data requested may be even LESS than 0.006%.

I strongly disagree on how likely this will be to spot a corrupted section. This depends ENTIRELY on the nature and type of corruption.

There's multiple kinds of corruptors:

1.Some corrupt a random bit/byte. Very hard to spot and possibly due to subtle coding errors in their program.

2.Some corrupt larger amounts -- maybe 1 packet of 200-1400 bytes. D-Link router DMZ Data Destroyers would probably fall here.

3.Some send a consistant but empty (00's or FF's) data set. Bloody obvious no matter what range you check.

4.Others generate random values on the fly. Pretty obvious when compared to known, good data. Or even when redownloading the same range from that source again!

5."Smarter" ones generate random but consistant values, so they always come up with the same pattern per file section. Still obvious when compared to known, good data.

As someone in the know, the corruptors are run on server farms and running many torrents at once...so much so that the hard drive space for all the fake/corrupt files is non-trivial and would require considerable disk reads/writes. In the event many of the torrents are based on the same bad file template, there is still the issue of multiple reads from it due to many torrents needing to access it. So quite likely server-farm corruptors use methods 3, 4, and 5. ...which is exactly what my 1-5 byte "checksum" method can easily catch. Even the "work-from-home" "use your private broadband connection to make money" corruptors also use hard drive space-saving tricks. I read a bit about one of them, so even it likely uses methods 3, 4, and/or 5.

"I assume uTorrents high memory usage is due to the disk cache. My disk cache is 256kB. My method's effiency doesnt improve unless you have a *huge* memory buffer. So 256kB is perfect."

µTorrent's memory useage is due to being a swiss-army-knife BitTorrent client that is compressed extremely well into a tiny executable that has to uncompress on runtime. Only Azureus has significantly more features. Its gui graphics and interface probably eat the majority of memory outside the disk cache (which can be estimated in size by resizing the disk cache). That gui also seems to cause some cpu and video "lag" on slower systems when the window is open.

In conclusion, the easy way (1 source PER piece) may be the shortest/simplest route...but like murphy's law of combat it's always mined with obvious and hidden problems.

Link to comment
Share on other sites

Firstly, don't get me wrong. I still use uTorrent. I love it. It is by far the best client i've ever used (and is the reason why i began to write my own cross-platform client, which runs on *every* OS). I wanted to match uTorrent for CPU and Memory usage and at the moment the only 3 BitTorrent related features that uTorrent supports that i don't support are Fast peers, Peer exchange and DHT. The only one which might increase memory usage is DHT. The others are just candy floss. Everything else that uTorrent has is a GUI feature (which again is candy floss, but *very* nice candy floss). I wont be using my own client until i have a GUI of equivalent standards.

Now, onto the main point of my argument ;)

...BUT it only has 1 "working copy" of the piece (regardless of success or failure) from what I can tell. It probably scraps the entire piece if the hash fails and redownloads it as though there were nothing there.

The ram cache could be treated as a separate "copy" of a piece in the event of a hash fail -- but as of now there's NO attempt by µTorrent to compare the ram cache "new copy" with the failed hash "old copy"

Without knowing how uTorrent is coded, i can't say ye or nay. The "smart" thing to do would be to internally mark each block in that piece as being "dirty" and then continue downloading all remaining blocks. If the resulting piece passes the hashcheck, that's great. If not, just redownload the "dirty" blocks one at a time and after each replacement check if the piece passes the hashcheck. If the piece still fails the hashcheck after replacing the dirty blocks, then you know the current peer is hashfailing. Otherwise the previous peer was hashfailing. Either way, you have caught the peer that was hashfailing. Therefore this method would be superior to the current method that uTorrent appears to use.

1.µTorrent tries too hard to get a single piece -- by using multiple sources

2.Corruptors need only slip in 1 wrong BIT to ruin the whole piece, though they may have to give 16 KB to do so.

3.An ip has to generate 5 hash fails before it will be banned...giving an array of corruptors using 100's of ips many chances to corrupt your download.

4.Good ips are obviously and often getting banned in the process because they also contributed to pieces that fail hash check.

And my method fixes problems 2, 3 and 4. The corrupter will *only* corrupt their own piece, not affecting good peers (which are probably fast uploading peers). Thats 2 "solved". You know exactly who the corrupter is, so you can quickly mark up each hashfail from him. Thats 3 solved. You will never accidently mark a bad peer as hashfailing a piece, so you won't accidently ban him. Thats 4 solve.

Except actually it's at least 2 ips that's possibly at fault...the ip you got the bad block from, and your own ip...because your end may be the cause of the failed hashes.

That will be the problem with *every* method. If you were to take that attitude you could say that every hashfail is your own fault and therefore you shouldn't mark a peer as being bad. You have to assume that your own connection is perfect, otherwise there's no point in monitoring hashfails. uTorrents current method would be affected by this too....

In the instance of 2 MB piece size and 50 seeds+peers connected to you...for you to attempt to download a separate piece from each one would either require 100+ MB of ram cache to make it quick to check as it goes, or it has to write to disk long before finishing each piece and read whole pieces back from disk anytime a piece completes to hash-check it.

Which is why you do not store whole pieces in memory. It'd be insane to do that. I fully agree. Bear in mind that the average HD can read data at over 60MB/sec. So reading a 2meg piece back into memory isn't going to take that long. You either store the whole piece in memory (which requires you to download the same piece from multiple peers) or write each block out to the disk until you have the whole piece, in which case you read it back to memory and hashcheck it.

I don't think µTorrent is that memory-wasteful. In µTorrent's Speed window, Disk Statistics...while seeding the read statistics show average size "grabs" from cache as 15.9 KB size and 127 KB from file. This is in spite of piece sizes for all my active torrents being 256 KB and larger -- µTorrent does not seem to be pulling whole pieces into ram at once.
I'm not arguing that µTorrent probably shouldn't be rewritten to do single source per piece downloading, only that it would NOT be a simple rewrite to do so! ...and also that there are some semi-reasonable memory and logic reasons that µTorrent wasn't programmed this way to begin with.

There's only three things that need to be changed.

1) In the piece picking algorithm you change it so that you pass in the peerId as a parameter to the PickNextPiece method. This method will then lookup the internal list of currently downloading pieces and if that peer is already there, pick a block from the current piece. Otherwise start a new piece, and put that peer in the list linked with that piece. Probably 30-50 lines. Maybe more, maybe less. I don't know how the current PiecePicker is written.

2) Small rewrite of the DiskCache to not wait for a full piece to write a block out to the disk. That change would probably be 20 lines at the most.

3) Small rewrite of the hash checking section to read the full piece back into memory as opposed to assuming it's in the disk cache already and hashcheck it then. Probably about a dozen lines of code.

Better yet, it could turn itself on/off automatically in the event of a hash fail! After 1 hash fail, all "questionable" ips that took part in the failed hash piece could be checked by being forced to contribute a complete piece by themselves.

All i'd say is go the whole hog or not at all. The point in the algorithm is to catch all hashfails and mark to a single peer.

On a torrent where corruptors outnumber good sources, this is not only possible...it's most likely outcome! The corruptors are trying to poison every piece and only need to slip in 1 bad 16 KB section to do so. Until an ip gets banned I think µTorrent makes no distinction on which ips it uses for a piece, except loosely based on speed and whether the source has you choked/snubbed. In short, it's possible every noncorrupt peer may end up banning every other noncorrupt peer before the true corruptors are weeded out!

Exactly the scenario where the new algorithm wins head over heels above the existing algorithm in uTorrent.

1.Some corrupt a random bit/byte. Very hard to spot and possibly due to subtle coding errors in their program.

2.Some corrupt larger amounts -- maybe 1 packet of 200-1400 bytes. D-Link router DMZ Data Destroyers would probably fall here.

3.Some send a consistant but empty (00's or FF's) data set. Bloody obvious no matter what range you check.

4.Others generate random values on the fly. Pretty obvious when compared to known, good data. Or even when redownloading the same range from that source again!

5."Smarter" ones generate random but consistant values, so they always come up with the same pattern per file section. Still obvious when compared to known, good data.

Either way, you'll have to download that block at least 1 more time (maybe 2 depending on how you code your algorithm) before you know if it's the corrupt block or not. Then you have to remember who sent the block beforehand and then mark them as being the bad ones. Of course, if you have a 2megabyte block and you request it in 16kB chunks (128 blocks of data in total) and more than one of those is corrupt, it'll become more and more messy to figure out which peer is sending bad data.

You'd have to Keep copies of all the blocks in the previous piece and then compare them to all the blocks in the piece when you download it again. So assuming the second download is ok, you just check the blocks off each other and using you rmemory of who sent what block, you can mark off the bad peers.

But what if the second download is also corrupt. Or the third download. Or the fourth. How will you decide who's corrupting then? You cant, so you mark all the peers as corrupting. If you had just requested all the pieces from one peer originally, you'd have no mess.

I do agree that methods 3, 4 and 5 are the most likely alright. Which would be caught by your method, but only if you are guaranteed to download a full non-corrupt piece the second time round (which is unlikely in the event of a corrupter farm in your torrent for the reasons i mentioned above).

µTorrent's memory useage is due to being a swiss-army-knife BitTorrent client that is compressed extremely well into a tiny executable that has to uncompress on runtime.

My client is less than 200kB for a tracker, client and (really basic but usable) GUI.

In conclusion, the easy way (1 source PER piece) may be the shortest/simplest route...but like murphy's law of combat it's always mined with obvious and hidden problems.

I don't really see the problem ;) The only problem is that the piece has to be read back off the disk to hashcheck (or you run a 100meg disk cache). Considering 95%+ of the time you will be downloading non-corrupt pieces, writing to the disk before hash checking is a safe, non-wasteful thing to do.

EDIT: This thoughts are coming from direct experience with coding a bittorrent library. I have to say, the conversation has given me a few new ideas on how to manage bad peers. I've said a few things here that i should really implement myself which would improve efficiency at my end (such as using "Dirty blocks" as opposed to dumping the piece).

Link to comment
Share on other sites

Archived

This topic is now archived and is closed to further replies.

×
×
  • Create New...