On June 15, 2003 04:07 pm, Ian Clarke wrote:
> > I decided to take a look at routing to see if it could be improved before
> > NG routing is implemented. Think what I have come up with works better
> > that the current code.
>
> I fear that your approach, while I am sure it is an improvement over
> what we have now, it is a further step along the alchemy path - away
> from the true and non-arbitrary path of NGrouting ;-)
While there is alchemy in my changes, there is less than in the current
code.
> The idea of NGRouting is to have a consistent way to integrate all of
> the information you talk about in a non-arbitrary and easily tested
> manner - namely by combining all available information (including that
> which your changes uses) into a single estimated routing time. This way
> we aren't just arbitrarily combining this information.
You have two types of routing to consider. Non cached non cached. How
is it planned to have NG routing handle this?
> For example, why did you choose CP = CP + .1 * (weight - CP) as the CP
> updating formula? Where do the various constants you use come from
> (1.0, 0.0, 0.05, 0.01, 0.4, 0.6 etc)? Why do you use the following
> formula?:
> CP = CP + (.9-.8*((max_refs-refs)/max_refs)**2)*(1.0 - CP)
This is the biggest piece of alchemy in my changes. Its also something
that has a very good effect - without this nodes with lots of references
are dropped as quickly as nodes with one or two. Think NG routing will
benifit from something very much like this.
1.0 is used when we make a connection - 100% success
0.0 is the converse, when there is no chance the connection could have
worked.
0.05 and 0.01 are alchmey - anything other than 0.0 would work. I use this
when the connection might have worked and we do not what this failure to
count towards an ARK retrieval.
In the case where a connect is rejected we use the probability that the next
connection of the same type will work - which is _not_ alchmey and is a big
improvement over the current code.
> My point is that all of these decisions are pretty arbitrary guesses,
> and this is a continuation of the "alchemy" approach to deciding which
> nodes to contact that was introduced with the CP mechanism in the first
> place.
Actually there are less arbitray guesses than the current code.
> NGrouting offers a way to take all of this information into account in a
> completely non-arbitrary and testable way.
Could you please repost the NG specs. After working through the CP
code it will mean much more to me. I do suspect that there will be
"alchmey" required for some of the details...
> For example, we take the possibility of node-contact failure into
> account by adding the probability that the contact will fail multiplied
> by the time delay of selecting another node to contact. This is
> non-arbitrary and clearly optimal given the information available to us.
> We estimate the routing time for a given key with a given reference by
> looking at past routing times for other keys. Even if it is
> sub-optimal, at least we would know it and know what we need to do to
> improve it. Further, we can easily test how accurately routing times
> are being estimated and use this information to further refine
> NGrouting.
Actually the origin version(s) of my changes used a kalman predictor
to calculate the next CP. Experimenting showed that using 0.1 worked
as well as the more complex code... With a kalman predictor its possible
to calculate optimal values instead of using 0.1 - again there did not
seem to be any gain using this.
> NGrouting isn't just a more complicated replacement for the CP
> algorithm, it is a fundamental rethink of how we decide where a message
> should be routed that eliminates the need for the CP mechanism as a
> side-effect.
I would really like to see this code integrated. Think it will give us
benifits now. I am quite willing to start working towards NG routing but
do not see a reason not to use better code that is available today.
Thanks
Ed
_______________________________________________
devl mailing list
[EMAIL PROTECTED]
http://hawk.freenetproject.org:8080/cgi-bin/mailman/listinfo/devl
