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 -------------- next part -------------- A non-text attachment was scrubbed... Name: nodes.gif Type: image/gif Size: 33059 bytes Desc: not available URL: <https://emu.freenetproject.org/pipermail/devl/attachments/20060622/7987767f/attachment.gif> -------------- next part -------------- A non-text attachment was scrubbed... Name: nodes.vsd Type: application/vnd.visio Size: 53760 bytes Desc: not available URL: <https://emu.freenetproject.org/pipermail/devl/attachments/20060622/7987767f/attachment.vsd>
