[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
>>correctly.
> 
> 
> Are you sure?. I thought BT client used the "sparse file" concept.

yes.

> 
> 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!
http://us.click.yahoo.com/L5YrjA/eSIIAA/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