On Monday 01 November 2010 17:13:27 Robert Hailey wrote: > > On 2010/10/30 (Oct), at 10:59 AM, Matthew Toseland wrote: > > > On Friday 29 October 2010 17:24:30 Robert Hailey wrote: > >> > >> It needs a little more work anyway :) > > I've tested the current head over the weekend and it now appears to be > behaving as intended. > > >>> We do not make significant changes to routing without detailed > >>> simulations. The Least Recently Used policy used for opennet has > >>> been extensively simulated and while it is not proven, there is also > >>> a very strong mathematical basis for it. There is every reason to > >>> think that it should perform well, in other words, and automatically > >>> establish a small world topology. Plus, it trades off performance > >>> against location in a way which is simple and avoids any need for > >>> extra layers of performance evaluation separate to optimising > >>> locations. > > Is the simulator under "freenet/node/simulator"? I did not see a > simulator for such opennet ideas. > > Anyway... if you even look at the output of the freenet/model/ > SmallWorldLinkModel, you can see that it forms the ideal link pattern > for a smallworld network. If the rest of the supporting code > successfully prefers nodes in this pattern (which is both its intent > and now seen to do by experimental observation) there is every reason > to believe that it will form a vastly-superior small world network on > the live network. > > As for LRU... my contribution also you to tune the networks clustering > coefficient! can you even speculate what LRU does in this respect?
LRU produces a small-world network, full stop. Go read the papers. I didn't write them. Oskar proposes it as a credible mechanism for explaining some natural small world networks, and shows in simulation and very nearly in hard math that it produces a small world topology very fast. And it does it without having to have extra layers just to identify poorly performing nodes. And it also adapts the local pattern according to whether there are a lot of local requests. > > >> I think that the announcement algorithm accounts for 95% of peer > >> selection. > >> > >> In my experience, nodes announce... get peers at the given > >> location... > >> and then are forevermore content with the announce-gathered peers. > >> LRU > >> would only have the effect that you state if we routinely dropped the > >> lowest peer (in such a way that they could not just reconnect). > > Perhaps a picture will help illustrate what I generally see: > > (link to picture instead) I see no picture... Hmmm, okay maybe this is slightly excessive. One broken node does not however justify changing the algorithms right across the network. > > How can you say this follows a smallworld link pattern? As I said I can't see the picture. However, the small world link pattern is a 1/d distribution. That means a lot of short links and very few long links. That is both normal and what we would expect. Now, exactly how concentrated this is depends on amongst other things how much local traffic versus remote traffic your node has. Locations evenly distributed across the keyspace is *not* small world and will *not* result in a topology that can be efficiently routed via greedy routing. > > If you want a security reason to merge my fix, I'll give you one! I > have reason to believe that *many* nodes have peer patterns just like > this (just a clump). In this case, all an attack has to do is get > *two* opennet connections to your node (one at +epsilon, and one at - > epsilon), and he can monitor 99% of all traffic coming from your node. This is inevitable, because of the "a few long links and a lot of short links" thing. With FOAF routing he can achieve this regardless of the link distribution, just by creating locations which allow him to capture the maximum possible keyspace. However we have countermeasures for it already, introduced when FOAF was introduced. (FOAF routing means we tell our peers our other peers' locations and take them into account when routing; it improves efficiency significantly according to published work, but returns diminish rapidly with more hops, so we only do it to one hop) > What's more, because the incoming requests are so specialized he can > be nearly 100% sure that the traffic originated from your node. And that's a GOOD thing in terms of *making routing actually work*. Specialisation has always been a metric of how well routing works. In the 0.5 era there was much less specialisation and this reflected the fact that *routing didn't work*! > > On the other hand, if the node gets anywhere close to the target link > pattern (blue dots), the most keyspace he could monitor with two > connections would be about 33% (and it must be the keyspace far from > the target, and he could *not* be sure it was coming from your node). As I've explained, it is possible to occupy a *large* proportion of the keyspace very easily. FOAF makes this spectacularly easy. We limit it to 30% but even so it is possible. But the bottom line is the security argument is irrelevant. Correlation attacks will always be possible on Freenet. If you have ONE malicious peer, you are dead. On opennet an attacker can connect to everyone, or cycle his way across the network, or he can do more sophisticated but cheaper attacks involving moving towards the request originator. But if he is directly connected to you, he can do a correlation attack, and he can bust you. Chaotic routing doesn't help because chaotic routing results in more traffic, more load-based exploits, more hops needed for a request (making the easy attacks easier) and fewer users, and therefore a smaller overall anonymity set. On darknet, this is much less of a problem because it is (relatively speaking) very expensive for him to get a connection: He needs to social-engineer the target, which involves human effort, and may not be feasible, or he needs to remote-compromise it electronically. Strategies such as offering a bribe for anyone who installs a special monitoring version of the node involve large amounts of cash and political capital, and are generally speaking *vastly* more expensive than simple electronic interventions on opennet. Anyway, routing must work. If routing works, Freenet will be reasonably fast, and we can afford to spend bandwidth on e.g. tunnels to provide extra layers of security. If routing works, darknet will work, and in many cases tunnels won't be needed. > > (link to picture instead) > > You will notice that my patch is not strict. There are still several > un-preferred opennet peers, and the peers for the "preferred slots" > fall some distance from the center (one-plus-sign-per-slot, the cut- > off line is about 1/2-way between the dots). Sorry, I haven't read it. > > >>> Finally, I don't believe routing is the problem limiting performance > >>> on the current network. The distribution of incoming requests is > >>> usually very specialised, for example. > > I'm thinking that it is the major problem. With my patch the incoming > distribution resembles a steep bell-curve. Specialisation is A GOOD THING from a Freenet point of view. It means data is found quickly, and the total capacity for storage is high. Although my incoming request distribution isn't that sharply specialised. > > >> The overall CHK success rate is a better measure of network health > >> IMO. > > > > And it's amazingly good by historical standards if you look at the > > higher HTL numbers. > > No doubt. IIRC, it was around the time of the htl increase and > implementation of turtle requests, no? Oh? You think turtles improved performance significantly? If that is true then it is very important because I'm about to turn them off ... > > > IMHO the rapid decline below 16 is to be expected because a lot of > > stuff is answered quickly. > > I'm sorry, but that doesn't make any sense... a high-htl request (even > if answered early at hop-4) should register a success/failure based on > the incoming htl. A high HTL request has a good chance of being answered quickly. If it is answered quickly it does not contribute to the low HTL figures. The low HTL success rates are therefore relatively poor because anything that reaches HTL 12 say hasn't been found in a reasonable number of hops and has little chance of being found. However we let it continue because if it IS found it can be propagated back to where it's supposed to be. > > My experiment shows an obvious and marked improvement in chk success > rate (across-the-board), but this might be expected because it judges > which peers to let fill the slots (and therefore hang on longer) based > on a measurement of chk success rate. And this is with only one node > running the fix! IMHO with every node running the fix we would see a major REDUCTION in success rates. > > (link to graph & data) > > > However, IMHO there are lots of possible problems that would cause > > poor performance by that measure other than poor routing. And they > > do. Data persistence in particular is relatively poor. And I believe > > this is caused by poor load management - inserts rejected by the > > nodes where the data should be stored, etc. > > But what is data persistence? it may simply be not being able to find > the data! No. Routing works. We know that because incoming requests are specialised. Therefore, the problem is not routing - it is IMHO load management. Which explains why if you do 3 inserts to the same key, which *all go to the same set of nodes* since failure tables don't apply to inserts, you vastly increase the persistence of that key. > > If backoff is an indication of bad load management, I'd say it has > been doing rather well recently! > > > Update Over Mandatory means auto-update will work in *almost* all > > cases unless we *really* mess things up in e.g. the transport layer > > or announcement. > > That is good to know! > > I'm sure you can understand my eagerness, IMO this may be the last > major functional holdout. Please go read the papers before proposing destroying routing. Thanks. -------------- next part -------------- A non-text attachment was scrubbed... Name: signature.asc Type: application/pgp-signature Size: 197 bytes Desc: This is a digitally signed message part. URL: <https://emu.freenetproject.org/pipermail/devl/attachments/20101102/5e16ae5d/attachment.pgp>
