[BitTorrent] Sharing packets

Harold Feit - Depthstrike.com Administrator dwknight at depthstrike.com
Fri Aug 27 12:50:37 EDT 2004


There is no 100% sure-fire way to implement a function into the BitTorrent
protocol that completely prevents these sort of collisions of missing data,
simply because of the possibility that anyone with data that is otherwise
missing from the swarm could disappear off the face of the earth at any
given time. There is however an already-implemented seeding algorithm
designed specifically to deal with situations where a number of pieces of a
torrent are absent or rarer then the others.
http://bittornado.com/docs/superseed.txt is the technical document on John
Hoffman's Super-Seed mode which is designed specifically to prevent that
sort of collision set in the initial seed base. The algorithm was designed
primarily for the initial seeding of a file or for a reseed later on when
self-sustainability of the torrent has been lost.

I've actually seen how super-seed mode works in situations where a torrent
is started and other people who download from the torrent already have
pieces of it (usually in the case of multiple file torrents where someone
gets one or more of the files from another source. With that super-seed
mode, when a small set of pieces exists already on the torrent, those pieces
aren't uploaded by any super-seeds until after all other pieces that have
not yet been uploaded are. Because of these supplemental partial-seeds, I
have seen a torrent reach self-sustaining capabilities before the 75% mark
in total uploaded.

I haven't gone over the code in the algorithm you're proposing yet so I
don't know for sure how different from the primary seeding algorithm or
super-seed mode it is, but I do know that there is already code implemented
in advanced clients that has been written for handling the absence of rare
data.
  -----Original Message-----
  From: Robert C. Helling [mailto:helling at atdotde.de]
  Sent: Tuesday, August 24, 2004 7:23 AM
  To: BitTorrent at yahoogroups.com
  Subject: [BitTorrent] Sharing packets


  Hi,

  I learnt about bittorrent only a couple of minutes ago so please forgive
  me if this posting is not relevant (ie misunderstanding of my part,
  already considered, already implemented etc).

  From what I saw on the website, bittorrent works by chopping a file into
  pieces and then organising peers to share those pieces. Is this correct?
  Then there is the obvious question of what happens if there are collisions
  in the sense that A wants a piece that nobody else but the original server
  has. From what I see, you have spend some thoughts on how to prevent this
  but let me nevertheless make another suggestion:

  There is an easy algorithm (involving some randomness) to start from a big
  file (size L say) and derive from it a new file that is L/N in size (plus
  some small, fixed size administrative overhead). That by itself is not
  interesting. But every time you run this algorithm it produces a different
  size L/N file, even if you run it much more often than N times. And now
  there is a reverse algorithm that takes _any_ (actually nearly any) N of
  the smaller files and reconstructs the original size L file from it.
  Actually it is possible to take M of the smaller files and produce new
  size N/L size files from them such that those tertiary files can replace
  any of the M files themselves.

  So if you implemented this algorithm in bittorrent it would eliminate the
  need for bookkeeping and risk of collisions nearly completely. (Of course
  if a peer as only part of a file it cannot share more information than it
  already has but it is most likely to be independent of the information
  that other peers have and the probability for overlap of information would
  be reduced significantly).

  This was the advertising bit. Now some technical details. This it how it
  works: It is based on linear algebra and there is an easy visualisation.
  Assume that the information we would like to share is the position and
  orientation of a plane in 3-space. Then this can be done by specifying
  three points on it that are not on a common line. But any such three
  points do the trick. So to spread out the information about the plane I
  tell people about random points on the plane. And whenever three of them
  come together they can share their points and reconstruct the plane.

  Now you do this with hyperplanes in N-space and this is your algorithm.
  For computer applications, it is of course better to use some finite field
  for your vector space in order to be able to do integer arithmetic and not
  floating point (with rounding errors).

  This algorithm has of course many uses (RAID disks are one), distributing
  files over floppy disks with some redundancy is another one, but file
  distribution systems like bittorrent sound like an obvious other one.

  Some time ago, we implemented the splitting and reconstruction programs in
  both Perl and C (as proof of concept) but I just realised that at least I
  don't have the C versions anymore. I only have the perl versions (that are
  very slow, C worked in a split second even on large files) and you can
  find them as

  http://www.damtp.cam.ac.uk/user/rch47/holosplit.tgz

  Usage (after unpacking) is

  ./split.pl split 3 filename > a
  ./split.pl split 3 filename > b
  ./split.pl split 3 filename > c

  to split filename in three parts a b and c (repeat ad lib) and then

  ./split.pl combine 3 a b c >out.file

  which reconstructs filename as out.file.

  Have fun
  Robert

  --
  .oOo.oOo.oOo.oOo.oOo.oOo.oOo.oOo.oOo.oOo.oOo.oOo.oOo.oOo.oOo.oOo.oOo.oOo.o
Oo.oO
  Robert C. Helling     Department of Applied Mathematics and Theoretical
Physics
                        University of Cambridge
  print "Just another   Phone: +44/1223/766870
      stupid .sig\n";   http://www.aei-potsdam.mpg.de/~helling


        Yahoo! Groups Sponsor
              ADVERTISEMENT





----------------------------------------------------------------------------
--
  Yahoo! Groups Links

    a.. To visit your group on the web, go to:
    http://groups.yahoo.com/group/BitTorrent/

    b.. To unsubscribe from this group, send an email to:
    BitTorrent-unsubscribe at yahoogroups.com

    c.. Your use of Yahoo! Groups is subject to the Yahoo! Terms of Service.


---
Outgoing mail is certified Virus Free.
Checked by AVG anti-virus system (http://www.grisoft.com).
Version: 6.0.744 / Virus Database: 496 - Release Date: 8/24/2004


[Non-text portions of this message have been removed]




------------------------ Yahoo! Groups Sponsor --------------------~--> 
$9.95 domain names from Yahoo!. Register anything.
http://us.click.yahoo.com/J8kdrA/y20IAA/yQLSAA/dkFolB/TM
--------------------------------------------------------------------~-> 

 
Yahoo! Groups Links

<*> To visit your group on the web, go to:
    http://groups.yahoo.com/group/BitTorrent/

<*> To unsubscribe from this group, send an email to:
    BitTorrent-unsubscribe at yahoogroups.com

<*> Your use of Yahoo! Groups is subject to:
    http://docs.yahoo.com/info/terms/
 



More information about the BitTorrent mailing list