[mnet-devel] Re: [freenet-dev] (no subject)

[Todd Walton]

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


-------------------------------------------------------
This SF.Net email sponsored by: Free pre-built ASP.NET sites including
Data Reports, E-commerce, Portals, and Forums are available now.
Download today and enter to win an XBOX or Visual Studio .NET.
http://aspnet.click-url.com/go/psa00100003ave/direct;at.aspnet_072303_01/01
_______________________________________________
mnet-devel mailing list
mnet-devel at lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/mnet-devel