This approach is reminiscent of an idea called "next generation
routing" that we tried with 0.5. Unfortunately we never got that to
work too well, although it is unclear whether the problem was with
NGR, or with some other aspect of 0.5's implementation. The basic
principal of NGR was that each node would collect data about the
performance of other nodes (how long they took to retrieve particular
keys etc), and then when routing, use this data to predict the node
that will respond most quickly for a given key - and route to it.
You can find out more about NGR on this page:
http://freenetproject.org/ngrouting.html
I think, however, that we need to get the basic algorithm working
before we try to embellish it with something like this, and then when
we do introduce more sophisticated routing schemes, we need to do-so
cautiously lest we wind up with an algorithm that is clever, but far
too complicated to figure out why it isn't working.
Ian.
On 21 Jun 2006, at 16:29, Ruud Javi wrote:
On IRC I have discussed about a different approach to routing, one
that would take the speed/ bandwidth of nodes into account. The
system I propose is using ‘stochastic modeling”. It’s still unsure
if it’s usable, but I really think that it has potential for Freenet.
I have seen a lot of messages discussing misrouting and how to
handle it. Misrouting is something that should be minimized, I
agree on that. Here is my point of view on the current routing:
1. Misrouting is currently already here, as we have backed-off
nodes. Routing to a 2nd best location because of backed-off is
still misrouting.
2. In my opinion sometimes it could be better not to route to the
neighbor that is the closest to the destination, for example when
that node is very slow. In that case in my view it is misrouting to
route to that closest node, because it would be too slow.
In Freenet, requests are forwarded often to find a target. In this
way a chain would be followed to a target and backwards to deliver
it to the requestor. If one or more nodes are very slow, this will
result in a very slow transfer.
For as far as I can see, different nodes have different amounts of
bandwidth dedicated to Freenet. One could argue that Freenet should
take advantage of this by routing more often to nodes with high
bandwidth. The danger is that for security/ anonymity reasons, you
do not want a few nodes getting lots of requests. They would get
too much information about their neighbors.
Still although we do not want very fast nodes to get too many
requests, we can still give slow nodes fewer requests and spread
those requests equally on all non-slow nodes. This would probably
improve the speed of Freenet.
An addition to ‘Load Balancing for Freenet 0.7’ (with tokens) by
making use of stochastic modeling:
I think that speed should be taken into account to determine the
optimal route, like it’s done in the theory of ‘stochastic modeling’.
To explain this I will use a small network with 10 nodes. Please
see the attachment (nodes.vsd or nodes.gif) for the exact network
that I use. The first situation is when node A is requesting a key
that is at location 0,50 (node E). With our current routing this
will go via node B (blue arrows). Node A will choose his neighbor
(node B) that is closest to the target destination.
With stochastic modeling you take into account how long you would
take to go from node to node. For that it’s important to know the
travel time of a transfer between 2 nodes. Node A could choose
neighbor B, it would gain 0,20 in the direction of the target and
the estimated transfer time is 4,0 seconds. That gain is 0,20 / 4,0
seconds = 0,05 a second. An alternative is routing via neighbor C,
it would gain 0,10 to the target in an estimated time of 1,0
second. 0,10 / 1,0 = 0,10 gain a second. The higher value of
neighbor C indicates that it is smarter to route via this node
(brown arrows). The advantage of this system is that it would use
slow nodes less often.
Routing in this way will not always perform better, as shown when
node H is trying to route to location 0,90. The disadvantage is
that it would use very fast nodes (ubernodes) very often, and we
don’t want that, but we could use something against that.
A simple way to handle accordingly is by setting a minimum to the
travel time. When the travel time is lower than X, we would still
use X for our calculation. X could be determined in many ways, but
I think its best when it’s determined by the speed of our direct
neighbors. If you would use the median (never use an average here)
of all the speeds of your neighbors and use this as X, you would
treat the fastest-half of your nodes equally and you would route
with them the same as the current routing. The slowest-half of your
nodes would be threatened in such a way that the slower the node
is, the fewer requests it would receive.
On IRC people told me that the above mechanism is not realistic, I
still don’t see why not. Ubernodes will not get more requests as
other non-slow nodes. For this mechanism you only need to know data
from your direct neighbors. You need to know their location and an
estimation of the transfer speed of keys (travel time).
Some questions:
- Is it misrouting to route A-C-D-E, instead of A-B-E in above
example. You would need one additional node, but you prevent the
use of a slow bottleneck node (that in the current situation would
probably back-off from time to time).
- This mechanism would only take time into affect between nodes.
Does it also take time on a node itself? It could be added easily
into the formula.
- Does this mechanism have disadvantages compared with the current
routing?
- Is it hard to determine travel times between nodes? How long does
a transfer take on average and how long does a request take on
average?
_________________________________________________________________
MSN Search, for accurate results! http://search.msn.nl
<nodes.gif>
<nodes.vsd>
_______________________________________________
Devl mailing list
[email protected]
http://emu.freenetproject.org/cgi-bin/mailman/listinfo/devl
_______________________________________________
Devl mailing list
[email protected]
http://emu.freenetproject.org/cgi-bin/mailman/listinfo/devl
