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 > Devl at freenetproject.org > http://emu.freenetproject.org/cgi-bin/mailman/listinfo/devl
