Update of /cvsroot/freenet/freenet/src/freenet/node/rt
In directory sc8-pr-cvs1:/tmp/cvs-serv9494/src/freenet/node/rt
Modified Files:
Tag: ngrouting
ResponseTimeEstimator.java
Log Message:
try new algorithm, with sensitivity per point
Index: ResponseTimeEstimator.java
===================================================================
RCS file: /cvsroot/freenet/freenet/src/freenet/node/rt/ResponseTimeEstimator.java,v
retrieving revision 1.4.2.20
retrieving revision 1.4.2.21
diff -u -r1.4.2.20 -r1.4.2.21
--- ResponseTimeEstimator.java 26 Aug 2003 19:33:27 -0000 1.4.2.20
+++ ResponseTimeEstimator.java 27 Aug 2003 01:08:44 -0000 1.4.2.21
@@ -7,6 +7,7 @@
import freenet.support.sort.*;
import java.util.Random;
import java.math.BigInteger;
+import java.math.BigDecimal;
import java.io.DataOutputStream;
import java.io.DataInputStream;
import java.io.IOException;
@@ -38,6 +39,7 @@
protected int recentTimes[] = new int[RECENT_LENGTH];
protected int recentPtr = 0;
protected int recentCount = 0; //TOTHINK: this could grow fast, may be better off
with long
+ protected static final double SENSITIVITY_MAX = 10.0;
static final int KEYBYTES = 23,
TIMEBYTES = 4,
@@ -297,6 +299,8 @@
QuickSorter.quickSort(ms);
dumpLog();
}
+
+ static final BigDecimal DEC_ONE = new BigDecimal(1.0);
protected synchronized int reportDecreasing(BigInteger lowerBound,
BigInteger upperBound,
@@ -335,18 +339,42 @@
Core.logger.log(this, "Trying key["+i+"]: "+
key[i].toString(16)+","+time[i],
Logger.DEBUG);
- shiftAmount++;
+ if(sensitivity[i] > SENSITIVITY_MAX)
+ sensitivity[i] = SENSITIVITY_MAX;
+ double sens = sensitivity[i];
BigInteger diff = key[i].subtract(center);
if(diff.signum() == -1) diff = diff.add(keyspace);
- key[i] = key[i].subtract(diff.shiftRight(shiftAmount));
+ // Result = old position + ((old position * sensitivity) / (sensitivity +
1)
+ // >> shiftAmount
+
+ // Use BigDecimal's (yuck!)
+ // Shift afterwards
+ /*
+ * R = O + ((S-O)/(r+1))*m
+ *
+ * Where R is the result, O is the old value, r is the sensitivity,
+ * m is the shift multiplier
+ */
+ BigDecimal fracDiff = new BigDecimal(diff);
+ BigDecimal fracSens = new BigDecimal(sens);
+ BigDecimal fracOrig = new BigDecimal(center);
+ BigDecimal resultDiff = fracDiff.divide(fracSens.add(DEC_ONE),
+ BigDecimal.ROUND_DOWN);
+ diff = resultDiff.toBigInteger().shiftRight(shiftAmount);
+ key[i] = key[i].subtract(diff);
if(key[i].signum() == -1)
key[i] = key[i].add(keyspace);
if(key[i].compareTo(keyspace) == 1)
key[i] = key[i].subtract(keyspace);
int timediff = usec - time[i];
- time[i] += (timediff >> shiftAmount);
+ double fracTimediff = (double)timediff;
+ double resultTimediff = fracTimediff/(sens+1.0);
+ timediff = ((int)resultTimediff) >> shiftAmount;
+ time[i] += timediff;
Core.logger.log(this, "key["+i+"] now: "+key[i].toString(16)+
","+time[i], Logger.DEBUG);
+ sensitivity[i] += 1.0/(1<<shiftAmount);
+ shiftAmount++;
}
dumpLog();
return shiftAmount;
@@ -389,19 +417,31 @@
Core.logger.log(this, "Trying key["+i+"]: "+
key[i].toString(16)+","+time[i],
Logger.DEBUG);
- shiftAmount++;
+ if(sensitivity[i] > SENSITIVITY_MAX)
+ sensitivity[i] = SENSITIVITY_MAX;
+ double sens = sensitivity[i];
BigInteger diff = center.subtract(key[i]);
if(diff.signum() == -1) diff = diff.add(keyspace);
- // Math not quite the same because of modular arithmetic
+ BigDecimal fracDiff = new BigDecimal(diff);
+ BigDecimal fracSens = new BigDecimal(sens);
+ BigDecimal fracOrig = new BigDecimal(center);
+ BigDecimal resultDiff = fracDiff.divide(fracSens.add(DEC_ONE),
+ BigDecimal.ROUND_DOWN);
+ diff = resultDiff.toBigInteger().shiftRight(shiftAmount);
key[i] = key[i].add(diff.shiftRight(shiftAmount));
if(key[i].signum() == -1)
key[i] = key[i].add(keyspace);
if(key[i].compareTo(keyspace) == 1)
key[i] = key[i].subtract(keyspace);
int timediff = usec - time[i];
- time[i] += (timediff >> shiftAmount);
+ double fracTimediff = (double)timediff;
+ double resultTimediff = fracTimediff/(sens+1.0);
+ timediff = ((int)resultTimediff) >> shiftAmount;
+ time[i] += timediff;
Core.logger.log(this, "key["+i+"] now: "+key[i].toString(16)+
","+time[i], Logger.DEBUG);
+ sensitivity[i] += 1.0/(1<<shiftAmount);
+ shiftAmount++;
}
dumpLog();
return shiftAmount;
@@ -475,7 +515,8 @@
pw.println("<table border=\"0\">");
for(int x=0;x<key.length;x++) {
pw.println("<tr><td>"+x+"</td><td>"+key[x].toString(16)+
- "</td><td>"+time[x]+"</td>"+sensitivity[x]+"</td></tr>");
+ "</td><td>"+time[x]+"</td><td>"+sensitivity[x]+
+ "</td></tr>");
}
pw.println("<tr><td>Maximum</td><td colspan=\"2\">"+
keyspace.toString(16)+
_______________________________________________
cvs mailing list
[EMAIL PROTECTED]
http://dodo.freenetproject.org/cgi-bin/mailman/listinfo/cvs
