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
