On Thu, 14 Aug 2003, Zooko wrote: > Ian Clarke wrote: > > > Yep. Since Mnet has (temporarily) lost economic mechanisms, since Freenet is > adding erasure coding, and since both projects are currently developing new > routing schemes, the two designs have grown closer.
Freenet adding erasure coding? From the Mnet FAQ I understood "erasure coding" to be the equivalent of FEC, which Freenet already uses. > > Anyway, one high-level point that I think is worth making at the outset > > is that it is important to draw a distinction between NGrouting, which > > is more of a general principal, and the specifics of our current > > implementation. > > Ah! That *is* interesting. The abstraction of NGrouting requires only that > the decision of which node to send to is based on past history, including both > performance and keyspace. > > I think you also want a sort of "convergence" property -- you want it to be > the case that even if node A and node B use *different* NGrouting > implementations to evaluate node C, that they tend to come to similar > conclusions about which part of the keyspace node C specializes in. This > would seem to be a natural result of almost any reasonable NGrouting scheme, > wouldn't it? Yes, you are right. The abstraction of NGRouting requires not just that the routing decision be based on past data. In that case an algorithm that routes to the node least likely to have the data would fit the bill. The abstraction of NGRouting requires that routing be done based on past history *and* to the node that will give the best response. To the extent that "best" is objective, then there will be the convergence you speak of. To the extent that "best" is subjective, then one's as good as the other and it doesn't matter to the overall network. The beauty of NGRouting is that convergence is something that arises naturally. It's not necessary that every node be *made* to converge on the same thing. They'll do it on their own. Even sub-optimal algorithms that fall short of objective best will be dealt with accordingly by other nodes. > Hm. The longer I think about it, the more ways I come up with for two > different NGrouting schemes to develop divergent views of which peers handle > which keyspace. That would be bad. That wouldn't be bad, necessarily. The responses my node gets from your node may, in reality, be different than the responses somebody else's node tends to get from your node. In that case, they *should* have different views of your node. > > Well, I am not so sure - we can observe the accuracy of the estimates > > produced by this NGrouting implementation for a single node, and based > > on that accuracy we should be able to make inferences about the > > network's performance as a whole. > > Hm. Better performance from the perspective of a single node *does* suggest > better performance of the network as a whole, but only assuming fairly > convergent routing. That is: if people inserting data into the network > are choosing different nodes to store the data than the people > requesting the data from the network choose to query, then the network > as a whole will suffer even though from any individual node's > perspective his own strategy is locally optimal. A similar argument > goes for two different queriers using different routing, because if > their routes are divergent they lose caching, and maybe they even get > DNFs. One thing that may be different between Mnet and Freenet is that data in Freenet isn't "stored" so much as it "floats". What I mean is that a chunk of data (small file, FEC block) is cached on a particular node only probabilistically. If a request comes for it, then each of the chain of nodes that it passes through on its way back to the requester has a chance of caching it in their own datastore. The further the data gets from its original source, the less the chance that the node will decide to cache it. In this way, the data tends to move topographically closer to where it's wanted. So, data is inserted and lands on whatever nodes. Then, someone requests it. The request meanders it's way through the network, hopefully coming to the node that actually has it. That node sends it back through the chain. The data moves (with some probability) a hop or two closer to the node that originally requested it. If subsequent requests for that data come, and they happen to hit one of the nodes that cached the data on the original request, then those requests are filled all that much sooner, and also the data will move a hop or two closer to those new request origination points. As this is all happening, requests for other data are coming in. Those requests are causing other data to be pulled through those nodes. The nodes will be able to fulfill those new requests to some degree, the total effect being that a node's specialty moves towards what the rest of the network thinks it is. So, even if two nodes have different ideas about what nodes will have which data, and even if one is more right than the other (from the global perspective) yet each node's ideas are locally optimal, it will still work out. The data will be more accessible to the "righter" node, other nodes will adjust their routing to reflect this (to the extent that they wish to optimize their own routing) and the "wronger" node's request chain will be honed in. It sounds like you viewed the situation as frozen. That if one node has the wrong views about who has what, then all hope is lost. But the network evolves. Not only does routing evolve to find the location of the data (as new performance info comes in), but the location of the data evolves to fit the routing, to different extents. If a node is wrong, it'll come to be more right. Even if it's using the wrong set of parameters to determine who best to route to (and thus is stuck at a sub-optimal solution), the rest of the network will compensate some for it. It's important, I think, to remember that all nodes in the request route matter to routing. Even if one node's routing is sub-optimal, it's only hurting itself, not the network. If the rest of the network has better ways of doing NGRouting, they will help the sub-optimal node when it makes a request, and will demote the sub-optimal node accordingly with respect to requesting of it, and thus the sub-optimal node will get less requests, and will drag down the rest of the network less. Again, the beauty of NGRouting is that we don't *have* to worry so much about the routing ability of the rest of the network, and whether other nodes have converged on the same answers. You only have to worry about making your own node the best router it can be. -todd _______________________________________________ devl mailing list [EMAIL PROTECTED] http://hawk.freenetproject.org:8080/cgi-bin/mailman/listinfo/devl
