On 2010/11/04 (Nov), at 11:06 AM, Matthew Toseland wrote:
On Wednesday 03 November 2010 20:00:48 Robert Hailey wrote:
Example patch attached. Small, but untested!
Could you please explain what it is that you think is going on, and
what the patch will do to fix it?
For all this, I presume the correctness principals concerning
destination sampling. Specifically the "small worldness" of making a
connection at the end point of a route builds a more routable network.
As best I can see, then, there may be major problems with the current
announcement and path folding implementations:
(1) announcements gather at non-destination points (in fact, shallow
first),
(2) the RequestSender logic will always eat an incoming path folding
request if we want a peer (often for very short paths),
(3) the RequestHandler logic will probabilistically drop an incoming
path folding request (about once every HTL)
(4) if path folding request is dropped (or not wanted), an
intermediate node might forward it's reference instead
I think the behavior of 2, 3, & 4 are more likely to be making the
peer-clumps, which (as you said) might not be a horrible thing. But I
think all of these points go against the original intent of
destination sampling.
I think the behavior of 1 (this patch) is forming a specialized
"backbone" of routability around the seed nodes.
In theory, announcements are routed to a specific random keyspace
location (expressed as a number), starting from the seednode.
In code, announcements are routed to the node's current location only
(one thing modified in my experiments), and only to the seed nodes
(even if we have connected peers).
I would expect them to run (approximately) the same paths each time,
therefore.
They rapidly approach the target location, and thus having the
opportunity to connect on each node should roughly give us the 1/d
distribution that theory tells us is necessary: A few long links and
a lot of short links.
...
This is plausible given that I'd expect the nodes close to the
seednodes, where you might get your few long links from, to be
overloaded.
Yea, by announcing shallow-first, all the nodes around the seed nodes
will (nearly always) not want a peer. If we go depth first we could
even count the number of forwarded refs, and only send our ref if that
count is too low.
I'm not sure we can realistically expect to get any specific
proportion of short/long links with announcement only. And even if we
could, they would all fall along the common announcement-path (not to
a more deserving node at the same location).
What is d? or what does 1/d come out to? Should I expect one long link
among 12 peer connections?
As far as I can see, your theory is that 1) announcements are making
up a large proportion of a node's connections,
Judging by one of my nodes, announcements make up for about 1/3 of
connections. And because a node currently announces to it's location,
these will almost surely be all short links (because I am not a seed
node), and reachable from the perspective of the seed node.
and 2) announcements are tending to get a bunch of noderefs that are
*all* very close to the target, rather than getting the 1/d
distribution which we need, which would include lots of short links
but also some long links. Which results in all your peer locations
being clustered together, with apparently no long links, as you've
shown.
In theory, shouldn't it be just as correct to announce to one of our
peers (instead of a seednode)? Depth-first/shallow-first, our-location/
random-location... I think it makes a big difference!
I think it needs to be depth-first to our-location to be generally
correct, and I think it would be much improved to use our peers over
seed nodes [[seed nodes breath a sigh of relief across the network]].
What can we do to further investigate this theory? It would be good
to gather some more data before applying potentially major changes.
Compare routability statistics of seednodes to "normal" nodes (or
"leaf" / far from seed nodes).
What exactly does your patch do,
Instead of sending our ref once we accept an announcement, it sends
the ref just-before sending the completion message (that is, after we
have routed the deeper replies).
and what is it intended to do (not necessarily the same thing)?
It is intended to deliver the announcement replies in a depth-first
order to the originator, in practice out-of-order messages might make
them only "roughly" depth first.
--
Robert Hailey
_______________________________________________
Devl mailing list
Devl@freenetproject.org
http://freenetproject.org/cgi-bin/mailman/listinfo/devl
