OK, here is an idea I have been working on for a while. It's a bit long, so please
respond to it piecemeal.
Here is a solution that I think can make NGrouting work correctly, aid load balancing,
lower Query rejecting, prevent users from overloading the network, and end world
hunger. Well, scratch that last one...
The idea is this: We eliminate the notion of HTL. Instead we replace it with a trust
based system with TTL.
Each node has a amount of trust in each other node that it connects with. This is
initially 0. Everytime a node makes a request it gives a trust level it is willing to
spend in order to have it fulfilled. If the node does not have that much trust built
up, it is reduced to the maximum that it has.
Trust is measured in seconds. Each node will forward a request with the Trust level it
came in with minus any time that has elapsed since then. Upon the successful return of
data a node is rewarded by the requesting node giving it trust.
The amount of trust rewarded is equal to:
(2 * TTL^2 - Time^2)^(1/2)
I selected this because it insures that:
1. There is a finite limit to the amount of trust that can be gained.
2. There is a finite time beyond which returning the data is no longer valuable.
3. Over performance rewards all the nodes in the path, by increasing their net trust
level gain. Not just the node that overpreformed.
4. Under performance reduces the regard for all nodes in the request path, not just
the node that underpreformed.
5. The bonus or penalty for performance it proportional to how close one is to where
the difference happened.
Here is some pseudo code for an implementation. Could someone please turn this in to
real Java code that would work in Freenet, and add it to the experiential branch?
//Incoming request for a key with a TTL.
//The code is basically the same for an insert. The only differences are the same as
they are now.
void processRequest(Node node,Key key, TTL ttl)
{
float load=getCurrentLoad(); //Check our current load.
//Tenitively subtract the maximum amount of credit that the node could owe
us.
//Subtract returns the amount it took away. (never more than there was there)
float credit = node.credit.subtract(ttl * 1.414214);
//Check how much credit the node has. And reduce the request if necessary
if ( credit < ttl * 1.414214 ) ttl = credit / 1.414214;
if ( Node.DataStore.Contians(key) )
{
//return the data...
}
else if ( shouldAccept(load, credit, this) )
{
//Accept the query and pass our load back to the requesting node.
QuerryAccept(node,key,load);
route(key,ttl);
}
else
{
//Reject the query and pass our load and estimated retrieval time back
to the requesting node.
QuerryReject(node,key,load,tSuccess( r.key ));
}
}
bool shouldAccept(float load, Request r)
{
if(load<1) return true;
// Calculate reject presentage
float rejectRate = (1 - load) / load;
// Hum this may not be aggressive enough.
// perhaps instead it should be ( 1 - load ) that way we overshoot a little.
if (rejectRate >= 1) return false;
// Compair running average of how much credit we gain per request to current
estimate.
// CreditGainPresentile returns the given percentile of how much credit we
are currently gaining per request.
// To be safe it should round up if necessary.
if ( ExpectedNetCreditGain(r) < CreditGainPresentile(rejectRate) ) return
false;
else return true;
}
float ExpectedNetCreditGain(Request r)
{
//Use global estimator tSuccess which works exactly as it does now
float returnTime = tSuccess( r.key );
//SendTime and ReceveTime are global running averages of the trip time for all
the nodes in the routing table.
//sendTime estimates: The time it will take for our request to land
on the next node.
//receveTime estimates The time it will take for the other node to forward us
the data once it gets it.
//Note: for both of the above, we only want to be sure to have a good average
bound on the number,
// so we should probably average the roundtrip time for a message
of the appropriate size.
return Max( 0, squareRoot( 2 * r.ttl^2 - returnTime^2 ) -
squareRoot( 2 * ( r.ttl - r.elapsedTime() -sendTime
-receveTime )^2 - ( returnTime - receveTime )^2 ) );
}
void requestComplete( Node requester, Node provider, TTL requesterTTL, TTL
providerTTL, float requesterTime, float providerTime, bool successful)
{
if (successful)
{
if ( requester != me )
{ //add back the amount we took away minus the amount they owe
us.
requester.trust.add( requesterTTL * 1.414214 - Max( 0 ,
squareRoot( 2 * requesterTTL^2 - requesterTime^2 ) ) );
requester.trustInMe.add( Max( 0 , squareRoot( 2 *
requesterTTL^2 - requesterTime^2 ) ) );
}
//Pay out. Pay up.
if ( provider != me )
{
provider.trust.add( Max( 0 , squareRoot( 2 * providerTTL^2 -
providerTime^2 ) ) );
//add back the amount they took away minus the amount we owe
them.
provider.trustInMe.add( providerTTL * 1.414214 - Max( 0 ,
squareRoot( 2 * providerTTL^2 - providerTime^2 ) ) );
}
}
else
{
//everything already subtracted. Nothing to add.
}
}
Routing works the same as it does now, except we do not need to estimate the
probability of DNF. This is a BIG gain! This takes all the alchemy out of NGrouting.
It is assumed that all node could EVENTUALLY find the data, but they will reject the
request if they cannot do so profitably. So we just go through all the nodes and sort
them by the largest ( estimatedTime - ttl ) where ttl is:
ttl = Min ( ttl - elapsedTime() - sendTime - receveTime() , them.trustInMe );
If they don't think that they can they can process the request profitably, then they
will reject it. If our first node rejects, goto the second then the third, and so
forth. The ttl we froward will become smaller and smaller. At some point even if the
node responds in the predicted time, we will not make a profit. At this point we QR.
Query rejects contain both the load and the estimated time it would have taken to get
the data.
If the load is high, back off.
If the time is higher than our estimated time of their performance. Add their
estimated time into our estimator, as though they had succeeded with that time.
If their estimated time is lower, back off.
Ideally this would encompass inserts too. But I can't think of a really good way to do
this. So in the mean time I would suggest that they keep the HTL. Then have the TTL ==
HTL so each node to forward it gains one TTL (net).
Problems this solves.
1. No single user can abuse the network.
2. Users that donate more in their data store or bandwidth get rewarded by better
network performance.
3. NGrouting can have accurate estimates because it does not need to know pDNF which
previously was calculated without taking into account the HTL.
4. All data will ether be found or fail in a fixed time frame.
5. Requesting Non existant keys cannot DOS the network
6. We learn about a nodes specialization even if the request does not work.
7. EVERYTHING can now we done non-alchemisticly. (Data store contents, Caching,
Rejecting, etc.) Nodes maximize for profit.
8. Current overload and routing problems go away.
Debatable issues:
Is there a better reward function? The one I chose rewards the person that had the
data a LOT. If we use it, frowarding requests will not be nearly as profitable as a
large data store. If someone can come up with a different formula that meets all of
the criteria I specified then please do. I played around with some parabolic
functions, those could work too...
What about decreasing the TTL for credit gain? A malicious node could deliberately
decrease the TTL more than necessary. However in doing so, they decrease the chance of
the request succeeding, and as a result under preform. I am of the opinion that this
is a non-issue, because the amount of trust they grant another node is never
transmitted, it is only calculated on their node. So they could simply never give
anyone credit, or give each person less, but if they do, they gain nothing. Others
would simply think they were preforming poorly, so they would have less potential to
earn credit.
Should we trust as much as we do? Originally I thought making Freenet into a positive
trust biased network would, require creating estimators for the relative value of each
nodes trust, and then calculating the relative gain between each pair of nodes for
each request, before we can even determine if the request was worth while. First I
realized that, if we have X trust in another node, that means that we owe them X. They
have already fulfilled our request for X, so we should pay them back regardless of
what we gain. However when we become loaded, we want to process the requests that will
be the most valueable to us. In this implementation I assume that the relative value
of each nodes data is proportional to the amount of time it offers us out of the
amount that we currently owe it biased on as of yet unrepaied requests that it has
processed on our behalf. Although this is alchemistic, it is not unreasonable. If the
node has given us data before, and it says it will allow us
to ask for the same amount again, if we repay it by answering this request, it is
not unreasonable to trust it. This greatly simplifies implementation.
Injecting trust into the system. Originally I had proposed not charding for our
services if we are idle. Then someone on the list pointed out that this made the
system vulnerable to attack. Multiple conspiring nodes could suck up all of a nodes
idle time and use it to gain a huge amount of trust in that node. So I have a new
proposal. We do something similar to what we are doing now. That is, every so often,
say 30 sec, we find the node in our table that we have not spoken with the longest. If
we don't have enough trust in that node to get an average query through, nor they with
us, we get a key that we successfully fetched recently, and ask it for that key. Now,
because we have no trust with that node, we send it with a TTL of 0. This means if the
node is at all busy, it will drop it. However if it is not, or just really wants to
talk to you, then it forwards it, still with an TTL of 0 along it's route. TTL of 0 is
a special designation. It has no expiration time it instead
dies after a certain large number of hops, say 25. So it is forwarded whenever the
node that has it decides it is not busy enough to process it. When the data eventually
comes back, the provider does not subtract any credit from the requester. BUT the
requester gives the provider some constant amount of credit. Say 5. Then when the data
gets back to the original node, the node that it asked for the data, now has enough
credit with it to ask it for any single key. So starting a request with a TTL of 0 is
like saying, "Look, I don't have enough credit with you do ask for data, and you don't
have enough with me, so if you answer this request, I'll grant you one request for
Free."
TTL = 0 could also be used a form of a passive request. New nodes of course would have
to make all their requests at TTL = 0 for a time. To help accelerate this, we could
also give a node connecting to us, a piece of data from our store. Say a somewhat
popular one. Then we could remove it from our store (If they have held on to it
properly), and send incoming requests for the data to it. So we gain, but they are
regarded for holding the data. This would get new node trust fast. However it does
require other nodes to be generous and reduce their potential for future trust gain
somewhat.
Any additional proposals for speeding the intrigration of new nodes are welcome.
Things that need to be done:
-Flamewar
-Make the code work in Freenet.
-Make the dozzens of other changes in the code necessary to get all this together.
-Ether fix the data size, or make all the estimators smart enough to deal with varring
sizes at various trust levels. (I suspect this will be easy for someone, but I have no
idea how to do it.)
-Make traffic more symmetric. (Implement multiplexing?)
-Commit this to experiential.
-Set up a test network.
-See how well it works.
-Make data store maximize for profit.
-Make bigger test.
-Merge.
*Anything I forgot.
Unfortunately I won't be able to read my e-mail for several days. But I hope to see
some good discussion and progress when I get back.
_______________________________________________
Devl mailing list
[EMAIL PROTECTED]
http://dodo.freenetproject.org/cgi-bin/mailman/listinfo/devl
