On Wed, Oct 22, 2003 at 12:41:46PM +0100, Simon Porter wrote: > Just spotted an interesting message on Frost that I though might be of > interest to those on this list. > > Simon > > I just noticed that the "Status for X" in the "Routing Table Status" in > "Node Status Interface" in the Web Interface contains an estimator for the > node X's probability of DNF (pDNF) as a function of key. Presumably this > information is used by NGRouting (why else would it be there ?).
There are also a number of other estimators used by NGRouting. > > Now, consider how Frost works. It requests guessable keys. However, a large > proportion of these requests, possibly even most of them, result in DNF - > not because the node is incabable of finding this type of data, but simply > because no one has yet inserted any data under that key. > > So Frost causes the node to try dozens of nonexistent keys. Furthermore, it > seems that Frost and FUQID are AFAIK the only applications which work well > in the current Freenet - Freesites simply aren't comfortably browsable at > this stage. Also, FUQID is used a lot less than Frost (because, to get the > URI for download, you typically have to use Frost). So, basically, the main > source for traffick nowadays is Frost. > > Now then, consider what all this means. I'm assuming that the keys Frost > uses are, in their crypted form (which Freenet uses internally), distributed > about evenly in keyspace (a reasonable assumption, since if it was > otherwise, it wouldn't be a particularly good crypt algorithm). Also assume > that the node tries to route to the "best" node, that is, each request is > likely to get forwarded to whatever node in the routing table is calculated > to be likely to get us the data fastest. > > Since Frost requests for nonexistant keys, whatever node such a request gets > routed to is unable to find the data (since the key doesn't exist), and is > thus rated a little lower for this particular key. The more key requests it > gets, the lower it gets rated (since the pDNF rises). Eventually, it goes > beneath the next-best node, which, being the best node now, gets the > impossible-to-fill requests and, failing to fulfill them, gets rated down. Maybe. The node's failure time estimators would also be updated. The NGRouting formula includes the probability of failure, the time it will take, and the cost of retrying successfully, for various failure modes including DNF. > > Following this course to it's logical conclusion, it would seem that all the > nodes in the routing table will start to look the same to our node - > whenever one of them starts to look better, it gets graded down by the flood > of requests for nonexisting keys. This will happen whether you are running > Frost or not, since most of the traffick passing by your node is Frost > traffick. Since each node looks alike, it's impossible to make sensible > routing choices between them, and all routing is completely random - which > is equivalent to no routing at all. Apart from what I said above, there is also the failure table cache, which stops requests for keys that have recently failed at the same or a higher HTL. As long as routing is working at all, that should help to damp down frost traffic. And NGRouting *should* be capable of dealing with a constant, low fraction of requested content being in the network - as I said, it is not only successes that it considers, it also considers all the various failure modes. > > Of course, the reality isn't this grim. Some Frost requests actually manage > to fetch new messages, FUQID downloads existing files, and some patient > souls still browse the Freesites. All this provides Fred with legitimate > routing information - but, as long as the majority (or a large percentage) > of requests in Freenet are for nonexisting keys, they will generate "routing > noise", obscuring under it the legitimate routing info and thereby severely > disturbing the network (not unlike the white noise in radio drowning out the > voice). We have a mechanism called "probability of legitimate DNF", which should compensate for most of this noise. > > The old routing didn't have this problem. Only successes were counted, not > failures. Therefore most queries being for nonexistent keys wasn't a problem > - they never affected routing information. The NGRouting, however, uses pDNF > in it's internal calculations and is therefore extremely vulnerable for such > queries. Indeed. Of course that meant that whether the old routing worked at all was open to question, and it was grossly vulnerable to cancer nodes by not being accountable - continuing to send requests to a node that occasionally succeeds but almost always DNFs is not acceptable. > > I see five possible ways to solve the problem: > > 1) Everyone stops using Frost - obvious, but unlikely and wouldn't really > solve the problem (weakness in Freenet), just cut the symptoms. > > 2) Radical changes in how Frost operates - again unlikely, and again > wouldn't solve the problem. Could be assisted by Freenet in this. Nearer or after 1.0, there are some protocol changes I have been keen on for a while that would make Frost have less impact. > > 3) Increase other traffick - if the majority of requests in the network are > for existing keys, the disturbance caused by Frost will be smaller (the > "good" information will drown it out). The freesites might be such an > application since a link going nowhere is most likley an error from the > makers part. Unfortunately, the freesites aren't really in a usable > condition currently. Furthermore, since edition sites usually contain a link > and an activelink image to a future edition, and since that edition isn't > inserted yet, they also procude some nonlegitimate routing info. And again, > wouldn't solve the real problem. Well, there are problems with FCP, but I have been concentrating on RNFs and the lack of routing success recently. > > 4) Drop pDNF from NGRouting calculations - would solve the problem, for > Frost and any other application which might cause this. Might make NGRouting > less effective. I recommend trying this and seeing how it affects the > situation - the effect should be instantenous, and it can allways be added > back with little hassle. Yuck. You might as well go back to traditional routing if you do this. The whole point of NGRouting is to determine an expected time for success, including any retries (using a global success-only estimator), given that you route to any given node, and then choose the best one. > > 5) Increase the size and time to last of failure tables a lot - this would > cause failed traffick to be stopped on it's tracks, lessening it's effect on > routing. Unfortunately, it would hinder Frost considerably, since a key > that's failed now doesn't neccessarily stay failed for very long (someone > might be inserting a new message this very minute...). It would also hinder > other messaging system type programs. Maybe. But it may be useful nonetheless. We could perhaps reduce the time to last a bit and increase the table size a lot... > > > The point number 4 should be the easiest to test, since any changes to the > local node should get immediate results. Could someone out there please test > this (I can't code Java well, and couldn't even figure out where the routing > calculations are made, much less how to change the formulas :( ) ? I could, but I think you are wrong. > > If you think I'm wrong, please explain why. -- Matthew J Toseland - [EMAIL PROTECTED] Freenet Project Official Codemonkey - http://freenetproject.org/ ICTHUS - Nothing is impossible. Our Boss says so.
signature.asc
Description: Digital signature
_______________________________________________ Devl mailing list [EMAIL PROTECTED] http://dodo.freenetproject.org/cgi-bin/mailman/listinfo/devl
