[BitTorrent] Re: Trackerless BitTorrent

Elliott Mitchell ehem at m5p.com
Thu Dec 30 18:57:26 EST 2004

>From: Olaf van der Spek <OvdSpek at LIACS.NL>
> >>From: Olaf van der Spek <OvdSpek at LIACS.NL>
> >> > The real problem is the one I was pointing to above. From your peers
> >> > you'll get other peers that are already close to you in network terms
> >> > (degree 2). This is extraordinarily unhealthy for the swarm. Any piece
> >>
> >> And from those other peers you can get degree 3, 4, 5 and so on. Or not?
> >> Also, you could ask peers at random instead of asking all peers.
> >
> > This would mean every client would need to keep track of a *lot* of other
> > clients. In order to have those higher degree peers, your neighbors must
> > know of the existance of the peer, and then forward that information
> > without ever connecting. This does give you high degree peers, but those
> Or you connect to a degree 2 peer to get a list of degree 3 peers. Connect 
> to degree 3 to get degree 4, etc.

You might think that, but this is not correct. For the purposes of this
explanation, I'll designate directly connected clients as degree 0 peers.

When you ask a degree 0 peer you'll get a list of degree 0 and 1 peers.
If it doesn't filter the list, you'll even get a degree -1 peer
(yourself). Depending upon the size of the swarm it is likely you'll get
a couple degree 0 peers, ones you're already connected to, these can be
easily filtered out though. In a really small swarm or one where the
swarm mesh has broken down, you might get zero degree 1 peers.

With those degree 1 peers, you can briefly connect and ask them for peers
(if you stay connected, they're now really degree 0; but I'll ignore
this). From the degree 1 peer's list, you're guarenteed to find at least
one degree 0 peer, the one you used to jump to it. Assuming anything
remains of the list (again, tiny swarm, or unhealthy mesh), there will
be degree 1 peers (other intermediates that you haven't contacted) and
even further out degree 2 peers. Contact a degree 2 peer, and you'll get
a list of degree 1, 2 and 3 peers. Contact a degree N peer, and you'll
get a list of degree N-1, N and N+1 peers.

The problem hits once you're contacted the degree 1 and greater peers,
and gotten the list consisting of degree 1 and 2 peers. How do you tell
what degree a peer is? If you ask *all* your degree 0 peers for their
lists, you can build a complete list of degree 1 peers, and filter them
out and have a list of degree 2 peers. This does mean you've got to
spend those 300 (900 for v6) bytes on every connection asking for peers.
So, you can build a list of degree 2 peers. How about building a list of
degree 3 peers? Well, connect to all your degree 1 peers...

The basic issue is you're trying to detect an unhealthy mesh, and this
quickly becomes prohibitively expensive. Yet you must do so, otherwise
you risk getting stuck on an island completely separated from the swam.
Wherever the border where you stop constructing complete lists of peers
a gap could form and disconnect you from the swarm.

So the main issue becomes, how dangerous is this? The presence of a
tracker doesn't guarentee this won't happen, it merely makes it
extraordinarily unlikely (good old stochastic methods work). It boils
down to the issue, do peer lists aggravate island-forming behavior?
Looking for higher degree peers won't stop island forming behavior,
merely make those islands larger.


> >> But that's quite useless if for whatever reason the tracker isn't 
> >> reachable.
> >
> > True, true. Wasn't the original proposal to completely get rid of the
> My get_peers/peers idea was in addition to the tracker.

The original poster was proposing completely getting rid of the tracker,
so this was the model I was commenting on. As these two are diverging
I'll respond separately.

> > tracker though? Also if the tracker is up long enough for you to get any
> > peers, isn't it likely you'll get a sufficient set from the tracker in
> > the first place?
> Not if you disconnect and then reconnect a week later to the peers you used 
> to be connected too. 

In this circumstance though, are *any* of your old peers likely to be
valid? (DHCP/address changes, download completions, etc)

(\___(\___(\______          --=> 8-) EHM <=--          ______/)___/)___/)
 \   (    |         EHeM at gremlin.m5p.com PGP 8881EF59         |    )   /
  \_  \   |  _____  -O #include <stddisclaimer.h> O-   _____  |   /  _/
    \___\_|_/82 04 A1 3C C7 B1 37 2A*E3 6E 84 DA 97 4C 40 E6\_|_/___/

------------------------ Yahoo! Groups Sponsor --------------------~--> 
$4.98 domain names from Yahoo!. Register anything.

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