[BitTorrent] Really random?

Arvid Norberg c99ang at cs.umu.se
Wed Jul 14 15:56:46 EDT 2004

Jesus Cea Avion wrote:
> Arvid Norberg wrote:
>>It is downloading random chunks. It's just that it puts those random
>>chunks sequentially in the file and rearranges them during the
>>download. And when the download is finished, they are sorted
> Are you sure?. I thought BT client used the "sparse file" concept.


> Could you give details about the algorithm, besides seeing the source
> code?.

This is, roughly, the algorithm I employ in libtorrent, I'm pretty sure 
it's the same for all clients supporting this kind of storage.

storing a piece:

1. let A be a newly downloaded piece, with index n
2. let s be the number of slots allocated in the file we're
    downloading to. (the number of pieces it has room for)
3. if n >= s then allocate a new slot and put the piece there
4. if n < s then allocate a new slot, move the data at
    slot n to the new slot and put A in slot n

allocating a new slot:

1. if there's an unassigned slot (a slot that doesn't
    contain any piece), return that slot index.
2. append the new slot at the end of the file
3. let i be the index of newly allocated slot
4. if we have downloaded piece index i already (to slot j) then
4.1. move the data at slot j to slot i
4.2. return slot index j as the newly allocated free slot
5. return i as the newly allocated slot

I wrote this from the top of my head, I may very well have forgotten 
something, feel free to correct any mistakes.

Arvid Norberg

------------------------ Yahoo! Groups Sponsor --------------------~--> 
Make a clean sweep of pop-up ads. Yahoo! Companion Toolbar.
Now with Pop-Up Blocker. Get it for free!

Yahoo! Groups Links

<*> To visit your group on the web, go to:

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

<*> Your use of Yahoo! Groups is subject to:

More information about the BitTorrent mailing list