On Fri, Aug 13, 2004 at 12:07:29PM +0200, thomasV wrote:
Brian M. Rzycki wrote:
Hi everyone,
I stumbled across Circle about 3 weeks ago and am interested in it as
a personalizable p2p framework. I saw Ricardo (I think?) was working
on a refactoring effort to compatmentalize core circle code as well as
using the twisted framework. I was wondering what the status of this
was? I'd like to pitch in a bit if nudged in the right direction. ;)
hi,
I did not have much time to work on Circle recently;
there has been no commit for about 2 months, as
you can see from cvs...
I might get back to it soon, however.
if you 'd like to participate, you are very welcome!
it was Rodrigo's idea to rewrite the core using Twisted.
However I do not think he ever wrote a draft of it...
The circle code is fairly complex, and it is true that it would
certainly need some refactoring. However, if you want to
contribute, I can only suggest to start with small things,
before you get an overall picture of how the code works.
It is necessary to get this overall picture before you start
working on a refactoring, and you won't get this picture
overnight.
Concerning the "right direction", my recommendation is:
- start with small things before you do big things.
there are plenty of bugs/feature requests to be fixed
(see todolist).
- do whatever you like. implement the features you want to see.
FYI, here is a list of (not so small) things that I would like to
do/have done:
- write a complete http interface (similar to mldonkey's)
- write an interface to bittorrent (circle would play the
role of a tracker, and would add search capability)
- use the kademlia algorithm instead of chord
I've looked through the code more and more, along with twisted. From what
I can see, these are the primary advantages from a code refactoring into the
twisted framework:
1. The HTTP interface is much nicer to work with...the conversion to a web
interface will be somewhat easier.
2. The existing structure is heavily threaded. This would go away and be
replaced with a single-threaded reactor-style system. Deferred's will replace
a lot of the thread-glue logic. And no more locks (not necessary since there
are no thread conflicts).
3. Adding features that are already coded in twisted such as e-mail or
instant-messaging type interfaces becomes trivial.
4. The application interface becomes available which automatically handles
hot-replugging of the code (basically, edit the code as it is running instead
of rebooting the daemon), and handles persistent option storage trivially.
5. A pluggable interface where the various features such as the download
manager, chat interface, gossip interface, etc., can be loaded/unloaded at
will. And adding additional features becomes easy.
The only real hassle that I can see is unravelling the threading that is
written into basically everything.
One question that I see. Why oh why would you want to switch from a Chord
system to Kademlia?
Kademlia's primary advantage is that it is less structured than Chord. The
proponents claim that it is more robust to node failures. However, from what
I've seen, the major problem is that Kademlia's lack of structure makes it
extremely prone to divide-and-conquer or surround-and-conquer type attacks.
It also seems to perform just as well as Chord so other than the fact that
the "maintenance protocol" is basically piggybacked onto searches, it seems
to have no inherent advantages that I can see.
Personally, I'm leaning towards a Symphony-style structure. This converts
the network from a O(log N) diameter with log N links to one with either the
same diameter and constant (small) number of links, or to O(log N/log log N)
diameter with log N links.
Symphony is very simple. With Chord, you have to keep track of neighbors at
specific non-random points on the circle. With Symphony, the neighbors are
random and just chosen from a specific distribution. Or with one of the slight
modifications, simply chop the ring up into K distinct pieces (with K
neighbors) and randomly pick any node from each piece. Nodes pass their lists
of neighbors around, and routing is done while looking at not only the
links but also the neighbors of the links. This second pass takes very little
extra communication overhead but allows the above mentioned O(log N/log log N)
diameter (which is the minimum possible diameter with log N links). Since
regular Chord has a fixed structure, the neighbors-of-links trick doesn't
work (no short paths). Also, individual users can trivially tune the
performance (within limits) of their own nodes by simply changing the K
parameter. Higher numbers of links results in shorter paths, while lowering
the number of links reduces communication overhead.
Since specific neighbors don't matter, a node can also optimize link
round trip times. Simply contact a potential neighbor (as before) and ask for
the neighbors of that neighbor. Check response times to each of those and
choose the shortest one as a link.
By the way, there's also a randomized Chord variant. Instead of picking the
node at N/2, use N/2-N, N/4-N/2, N/8-N/4, etc. Any node in that range works.
And the advantage is that the above-mentioned neighbors-of-links trick works,
and you can also do round-trip-time optimization. The disadvantage is that
it's not quite as simple as Symphony and that the tunable neighbor trick is
lost.
If you want the Kademlia structure still, there's another one out of France
that simplifies Kademlia and picks up some of the advantages of the Symphony
structure. It's called "Broose". It essentially models the De Brujin network
(the theoretical lowest diameter network) in a Kademlia framework, which
picks up the O(log N/log log N) diameter advantage. Also Broose only contains
two buckets of nodes to track vs. several more in Kademlia.
_______________________________________________
Circle-discuss mailing list
address@hidden
http://lists.nongnu.org/mailman/listinfo/circle-discuss