On May 27, 2003 02:17 am, Niklas Bergh wrote:
> It seems to work. Just thought I should mention it.
>
> Using stable builds (currently 598) I have not seen a Total Successes/Total
> Trials ratio above 55% or so for many months. Yesterday I switched my
> primary node over to build 6043 and today, 8 hours later, the ratio is
> about 75% 170k/220k. I guess that is a good thing.
On unstable I typically see 50-60%. I have been playing with the code for
calculating CP. The patch below seems to do better than the current. It gets
66% here, an increase of about 10%.
On irc toad_ pointed out that the stats for connections are incomplete. The
numbers quoted above measure the percentage of routes that work - the
actual number of FNP level connections is (guessing) a little less.
The patch changes three things.
One it starts CPs at 0.6 instead of 1.0. This stops us from considering new
nodes the best ones - they still get routed to quite quickly though.
Two, it gives nodes that we detect a key reference from a boost. Nodes reset
the data source to themselves when they want more traffic. The current code
will tend to add these nodes to the routing table. This does not change the
adding logic and will accept hints for entries already in the table.
The third item is it changes the CP estimator to use a kalman filter, which is
feed the running average of the last five 'connects'. Why five? It works best
here... I am still fiddling with CP estimators. I have tried using estimators
that
track weak and strong connects separately and combine them to get the CP,
but the included code works best so far.
Comments?
Ed Tomlinson
-----------
--- CPAlgoRoutingTable.java.bak 2003-05-23 16:37:57.000000000 -0400
+++ CPAlgoRoutingTable.java 2003-05-26 22:21:35.000000000 -0400
@@ -221,6 +221,27 @@
remove((RoutingMemory)(routingStore.getNode(i)), i);
}
+ /*
+ * Nodes set references to themselves when they want more
+ * traffic - lets take that into account. This should help
+ * conserve nodes with lots of keys, which should lead to
+ * better route selections.
+ */
+ public synchronized void reference(Key k, NodeReference nr) {
+ super.reference(k, nr);
+ RoutingMemory mem = routingStore.getNode(nr.getIdentity());
+ if (mem != null) {
+ CPAlgoData cpd = getProperty(mem, RMKEY, node);
+ cpd.increaseContactProbability(false);
+ mem.setProperty(RMKEY, cpd);
+ Core.logger.log(this, "key reference increased CP",
+ Core.logger.DEBUG);
+ } else {
+ Core.logger.log(this, "key reference found null mem",
+ Core.logger.DEBUG);
+ }
+ }
+
private final synchronized void succeed(RoutingMemory mem, boolean cached,
boolean attenuated, boolean weak) {
CPAlgoData cpd = getProperty(mem, RMKEY, node);
@@ -635,7 +656,10 @@
class CPAlgoData implements DataObject {
// persisted.
- float contactProbability = 1.0f;
+ float contactProbability = 0.6f;
+ float k = 0.00f;
+ float p = 0.50f;
+ boolean hist[] = {true, false, true, false};
// Diagnostic info
long successes = 0;
@@ -745,14 +769,32 @@
}
return contactProbability;
}
+
+ // use a first order Kakman predictor to predict the CP
+ final void nextCP(float value, boolean weak) {
+ if (weak)
+ k = p/(p+0.1f);
+ else
+ k = p/(p+0.4f);
+ contactProbability = contactProbability + k*(value -
contactProbability);
+ p = (1-k)*p+0.02f;
+ }
+
+ // running average from last (hist.length+1) tries
+ final float runningAverage(boolean value) {
+ int n = hist[0] ? 1 : 0;
+ for (int i=1; i<hist.length; i++) {
+ n += hist[i] ? 1 : 0;
+ hist[i-1] = hist[i];
+ }
+ hist[hist.length-1] = value;
+ n += value ? 1 : 0;
+ return ((float) n) / ((float) (hist.length+1));
+ }
// returns true if the node should be dereferenced.
final boolean decreaseContactProbability(boolean weak) {
- contactProbability =
- (float)(weak ? ((96.0 * contactProbability) / 100.0) :
- (((4.0 * contactProbability) /* + 0.0 */) / 5.0));
- // Decrease by 4% for weak, 20% for strong
- if(contactProbability < minCP) contactProbability = minCP;
+ nextCP(runningAverage(false) , weak);
consecutiveFailures++;
// When consecutiveFailures reaches some value, start an ARK lookup
if(consecutiveFailures >= consecutiveFailuresLookupARK &&
@@ -779,15 +821,8 @@
node.diagnostics.occurrenceCounting("successLookupARK",1);
justFetchedARK = false;
}
- if(contactProbability < minCP) contactProbability = minCP;
consecutiveFailures = 0;
- float f = (float)
- (weak ? (((19 * contactProbability) + 1.0) / 20.0) :
- (((3.0 * contactProbability) + 1.0) / 4.0));
- // Move closer to 1.0 by 5% for weak
- // 25% for strong
- if(f>1) f = 1;
- contactProbability = f;
+ nextCP(runningAverage(true), weak);
lastRetryMs = lastSuccessfulContact = System.currentTimeMillis();
synchronized(lookupLock) {
if(lookup != null) {
@@ -796,11 +831,11 @@
}
}
}
-
+
final boolean fetchingARK() {
return lookup != null;
}
-
+
protected final FreenetURI getARKURI() {
return ref.getARKURI(ref.revision()+1);
}
-----------
_______________________________________________
devl mailing list
devl at freenetproject.org
http://hawk.freenetproject.org:8080/cgi-bin/mailman/listinfo/devl
