On Monday 08 November 2010 16:19:59 Robert Hailey wrote: > > On 2010/11/06 (Nov), at 8:44 AM, Matthew Toseland wrote: > > > On Friday 05 November 2010 22:37:48 Robert Hailey wrote: > >> > >> A working implementation is visible here: > >> > >> https://github.com/Osndok/fred-staging/tree/depth-first-announcement > >> > >> With a simulator that shows that: > >> (1) it doesn't break announcements, > >> (2) it seeks the deepest nodes first (away from the seed node), > >> (3) it gathers at most MAnnounceSender.MAX_ANNOUNCE_REPLIES (and in > >> my > >> sim run, precisely that many) > >> > >> For some reason github won't let me issue a pull request at the > >> moment. > > > > I don't have time to review this code right now. > > Then perhaps someone else would like to review the code. It is a > *very* short patch (+18-2; incl. many blanks and comments). > > https://github.com/Osndok/fred-staging/commit/4f8b4e27ac34a1413f0ab958711abc9e17f4c383
Sorry, I did review the patch and it didn't make sense. I thought you were posting a large and complex simulator to review. However, having finally understood what you are trying to do: - We don't send our noderef when the announcement reaches us. - We forward the originator's noderef. - When we have all the replies, we decide whether or not to send our ref as well. - We send our ref only if we want the ref and there are fewer than 6 refs so far. What this will mean in practice IMHO is either: 1) It does nothing. We send announcements when we have few peers, and most nodes don't want a node, so we will get fewer than 6 refs from each announcement, which will all be accepted. (Some of them will fail after being accepted). 2) It restricts the returned noderefs to the last 6 nodes on the path. It is reasonable to expect that we start out a long way away from the target, we move towards it quite quickly (within say 5-10 hops), and then for the rest of the announcement (at least another 8 hops, although this is reduced for loops) we wander around the target location. So I'd expect this to result in the connections returned being significantly more specialised than with the current algorithm. In either case it will make announcement take slightly more time, but this is not a big deal if it is beneficial. > > > However if you want "depth first announcement" accepted first you > > have to: > > 2) Produce a patch that accepts preferentially from the end; > > If it were not enough that I have *already* done that, and if it were > not enough that I wrote a simulator anyone can run that demonstrates > that, then perhaps you would accept the output of my simulator run??? Sorry, I was misunderstanding. > > ----simulator output---- > 4 : seeds: 1, connected: 1 opennet peers: 0, connected: 0 > Announcement to 127.0.0.1:8007 starting... > 5 : seeds: 1, connected: 1 opennet peers: 0, connected: 0 > [...snip...] > 15 : seeds: 1, connected: 1 opennet peers: 0, connected: 0 > Announcement to 127.0.0.1:8007 added node 127.0.0.1:8022. > Announcement to 127.0.0.1:8007 added node 127.0.0.1:8021. > Announcement to 127.0.0.1:8007 added node 127.0.0.1:8020. > Announcement to 127.0.0.1:8007 added node 127.0.0.1:8019. > 16 : seeds: 1, connected: 1 opennet peers: 4, connected: 3 > Completed bootstrap (3 peers) in 32231ms (32s) > Announcement to 127.0.0.1:8007 added node 127.0.0.1:8018. > Announcement to 127.0.0.1:8007 added node 127.0.0.1:8017. > 17 : seeds: 1, connected: 1 opennet peers: 6, connected: 6 > 18 : seeds: 1, connected: 1 opennet peers: 6, connected: 6 > ------end simulator output------ > > The node are strung together 8007(seed), 8008, 8009, 8010...8021, 8022. > > What this output shows is that from one announcement (to the only > simulated seed node), the previously-unconnected peer acquired 6 > connections (the max as defined and tunable in the patch) from twenty > chained nodes *deepest-first*... > > ***IT WORKS*** > > > as far as I can see yours doesn't. > > It does work, period. Sorry for messing you about, I agree that it works now. Whether it is beneficial is another question. > > I am sorry that (at the moment) you cannot see *how* it works, but > you'll just have to accept the fact that *IT DOES*. No, voodoo is not acceptable, in general. > > I would like to think that this patch is particularly readable and > easy to understand, so I will presume that the real matter is that you > presently do not have *time* to understand it for yourself. The version above makes sense, thanks for your effort on this count. > > > 1) Show that we are rejecting nodes from announcement towards the > > end of the path, having accepted too many early on > > That is totally not the point, and missing the larger picture. Let's > try for some objectivity here: I don't see the larger picture. As far as I can see it, the only change to the actual set of peers that are accepted occurs if we reach the MAX_ANNOUNCE_REPLIES limit. However if we do this results in more specialisation, not less. Unless you want to argue that the nodes towards the end are in fact not all that specialised because we've already overshot by that point. But it's certainly not going to give us any long links. IMHO the only way to get long links in announcement is not to start from the seednode. > > Shallow-first > THEORIZED to accept a good mix of a few long links and many short > links (by toad) > THEORIZED to be very destructive to routing (by me) > IN PRACTICE works "good enough" (provided grace periods keep seed- > nodes connected to network at-large, etc). > IN PRACTICE does not scale because it always tries to connect to > *ALL* nodes between the seed nodes and peripheria > > Depth-first > THEORIZED to provide many good short network links at a very-routable > location (absent my earlier path-folding point #2) > THEORIZED to relieve the network churn around the seed nodes (and > therefore possibly a degree of load) > THEORIZED to improve the routability of the network around the seed > node by the principal of destination sampling > IN PRACTICE does scale because it returns a fixed maximum nodes (some > distance from the seed nodes) > IN PRACTICE is guaranteed to be no-worse-than shallow-first, because > shallower nodes will return there refs if needed > > Is there really even a choice? Shallow-first is horribly broken!
signature.asc
Description: This is a digitally signed message part.
_______________________________________________ Devl mailing list Devl@freenetproject.org http://freenetproject.org/cgi-bin/mailman/listinfo/devl
