Update of /cvsroot/freenet/freenet/src/freenet/node/rt
In directory sc8-pr-cvs1:/tmp/cvs-serv32518/src/freenet/node/rt
Modified Files:
CPAlgoRoutingTable.java FilterRoutingTable.java
ResponseTimeEstimator.java Routing.java RoutingTable.java
StoredRoutingTable.java TreeRouting.java TreeRoutingTable.java
Added Files:
ComparableStringMap.java DecayingRunningAverage.java
Estimate.java FFTTimeEstimator.java NGRouting.java
NGRoutingTable.java NodeEstimator.java
NodeEstimatorComparator.java NodeEstimatorFactory.java
RunningAverage.java RunningAverageFactory.java
StandardNodeEstimator.java StandardNodeEstimatorFactory.java
TerminatableRouting.java TimeEstimator.java
TimeEstimatorFactory.java
Log Message:
6163: Merge NGRouting
* Routing table switch: new config option routingTableImpl - "classic" or "ng"
* New diagnostics variables: normalizedSuccessTime, successSearchTime,
successTransferRate, requestSuccessRatio, requestFailureRoutingOrNotRatio,
routingSuccessRatio. These are reported by both RT modes, so should be usable for
comparative purposes.
* Significant changes to Node Status Servlet, including a page with several graphs for
each node in the RT.
* Significant changes to ConnectionOpener. Fixes to races that were causing
RouteNotFound errors, a toString(), much more and better logging.
* Make a distinction between failed caching a DataReply due to IOE in the store and
due to IOE on the stream when caching a DataReply. Use this in the code to make sure
we respond correctly w.r.t. routing (it's more important in NGRouting).
* RoutingTable.route() now takes extra params: HTL, size, whether it is an insert.
Added reportConnectionSuccess, reportConnectionFailure, used by ConnectionOpener to
tell RT about connections.
* Major changes to the existing ResponseTimeEstimator class. Changed logic, changed
serialization, changed interface, just about everything. Now implements the generic
TimeEstimator, knows about time versus transfer rate versus probability, wraps around
properly, has some significant algorithm changes.
* Change Routing interface significantly. Several new me methods, old ones have been
given new arguments. Caller must for stats eventually call terminate(), or another
terminal method (transferSuccess, dataNotFound). New base class, TerminatableRouting
(implements Routing, base of NGRouting and TreeRouting), handles most of the stats.
* Add code all over states/ (mostly request, but also the others) for notifying the
Routing of timings and status, terminating the Routing, some reporting bugfixes, get
rid of the old "NGROUTING" debug log diagnostics.
* Lots of completely new code for NGRouting, mostly in freenet/node/rt/
Misc fixes etc
* Fix a deadlock in ConnectionHandler
* Iakin fix for 1.4.2 and later changed static initialization behaviour w.r.t.
Core.params.
* Added messageSuccessRatio, tracks proportion of messages successfully sent
* Fix some NullPointerExceptions
* Spelling fixes to descriptions of diagnostic variables by Edward J. Huff
* Fixes to AbstractSelectorLoop.queueClose*, connection close notifications were being
missed.
* Catch all throwables thrown by process() processing maintenance queue
Minor/future
* Notes on inserts (attacks, NGRouting)
* Give the ref to the GPL on the RNF page a filename
* Even more logging improvements
* More minor reindenting/restyling
Index: CPAlgoRoutingTable.java
===================================================================
RCS file: /cvsroot/freenet/freenet/src/freenet/node/rt/CPAlgoRoutingTable.java,v
retrieving revision 1.53
retrieving revision 1.54
diff -u -r1.53 -r1.54
--- CPAlgoRoutingTable.java 8 Aug 2003 18:26:59 -0000 1.53
+++ CPAlgoRoutingTable.java 30 Aug 2003 23:16:52 -0000 1.54
@@ -589,13 +589,6 @@
return new CPSortableStringMap(REF_PROPERTIES, values);
}
- protected Node node = null;
-
- public void setNode(Node node) {
- if(node == null) throw new IllegalStateException("Tried to set node to null!");
- this.node = node;
- }
-
final CPAlgoData getProperty(RoutingMemory mem, String name,
Node node) {
CPAlgoData ret;
@@ -1041,6 +1034,8 @@
}
}
+ public void reportConnectionSuccess(Identity id, long time) {};
+ public void reportConnectionFailure(Identity id, long time) {};
}
Index: FilterRoutingTable.java
===================================================================
RCS file: /cvsroot/freenet/freenet/src/freenet/node/rt/FilterRoutingTable.java,v
retrieving revision 1.6
retrieving revision 1.7
diff -u -r1.6 -r1.7
--- FilterRoutingTable.java 26 Jul 2003 21:36:29 -0000 1.6
+++ FilterRoutingTable.java 30 Aug 2003 23:16:52 -0000 1.7
@@ -56,10 +56,11 @@
return rt.getNodeReference(id);
}
- public final Routing route(Key k, boolean force) {
- return rt.route(k, force);
+ public final Routing route(Key k, int htl, long size, boolean force,
+ boolean isInsert) {
+ return rt.route(k, htl, size, force, isInsert);
}
-
+
public final RoutingStore getRoutingStore() {
return rt.getRoutingStore();
}
@@ -70,6 +71,14 @@
public final RTDiagSnapshot getSnapshot() {
return rt.getSnapshot();
+ }
+
+ public final void reportConnectionSuccess(Identity id, long time) {
+ rt.reportConnectionSuccess(id, time);
+ }
+
+ public final void reportConnectionFailure(Identity id, long time) {
+ rt.reportConnectionFailure(id, time);
}
}
Index: ResponseTimeEstimator.java
===================================================================
RCS file: /cvsroot/freenet/freenet/src/freenet/node/rt/ResponseTimeEstimator.java,v
retrieving revision 1.4
retrieving revision 1.5
diff -u -r1.4 -r1.5
--- ResponseTimeEstimator.java 29 Jun 2003 23:54:00 -0000 1.4
+++ ResponseTimeEstimator.java 30 Aug 2003 23:16:52 -0000 1.5
@@ -1,60 +1,244 @@
package freenet.node.rt;
-//import freenet.*;
+import freenet.Key;
+import freenet.Core;
+import freenet.support.Logger;
+import freenet.support.DataObjectPending;
+import freenet.support.graph.*;
+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;
+import java.io.OutputStream;
+
+// class Key {
+// byte[] b;
+// public byte[] getVal() {
+// return b;
+// }
+// public Key(Random r) {
+// b = new byte[23];
+// r.nextBytes(b);
+// }
+// public Key(int i) {
+// b = new byte[23];
+// b[22] = (byte) i;
+// }
+// }
-class Key {
- byte[] b;
- public byte[] getVal() {
- return b;
- }
- public Key(Random r) {
- b = new byte[23];
- r.nextBytes(b);
- }
- public Key(int i) {
- b = new byte[23];
- b[22] = (byte) i;
- }
-}
-
-public class ResponseTimeEstimator {
+public class ResponseTimeEstimator implements TimeEstimator {
BigInteger key[];
int time[];
+ double sensitivity[];
+ //I need to see these from subclass --zab
+ protected static int RECENT_LENGTH = 64;
+ protected BigInteger recentKeys[] = new BigInteger[RECENT_LENGTH];
+ 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,
BYTES = KEYBYTES + TIMEBYTES;
-
+
+ static final int DEFAULT_ACCURACY = 16;
+ static final int MAX_ACCURACY = 32;
+ static final BigInteger keyspace = BigInteger.ONE.shiftLeft(KEYBYTES << 3);
+ static final BigInteger halfkeyspace =
+ BigInteger.ONE.shiftLeft((KEYBYTES << 3) - 1);
+
+ public int getDataLength() {
+ return 4 + key.length * (4 + KEYBYTES);
+ }
+
+ public ResponseTimeEstimator(DataInputStream i) throws IOException {
+ int version = i.readInt();
+ if(version != 1) throw new IOException("unrecognized version "+i);
+ int accuracy = i.readInt();
+ if(accuracy < 0) throw new IOException("failed read");
+ if(accuracy == 0 || accuracy > MAX_ACCURACY) // seems reasonable bounds
+ throw new IOException("Invalid accuracy word "+accuracy);
+ key = new BigInteger[accuracy];
+ time = new int[accuracy];
+ sensitivity = new double[accuracy];
+ BigInteger prev = BigInteger.ZERO;
+ for(int x = 0; x<accuracy;x++) {
+ time[x] = i.readInt();
+ if(time[x] < 0) throw new IOException("negative value");
+ byte[] b = new byte[KEYBYTES];
+ i.readFully(b);
+ key[x] = new BigInteger(1, b);
+ if(key[x].signum() == -1) throw new IOException("negative key");
+ if(key[x].compareTo(keyspace) == 1)
+ throw new IOException("exceeded keyspace");
+ if(key[x].compareTo(prev) == -1)
+ throw new IOException("smaller than prev");
+ prev = key[x];
+ sensitivity[x] = i.readDouble();
+ }
+ try {
+ recentPtr = i.readInt();
+ if(recentPtr >= RECENT_LENGTH)
+ throw new IOException("recentPtr too high");
+ if(recentPtr < 0)
+ throw new IOException("invalid negative recentPtr");
+ recentCount = i.readInt();
+ if(recentCount < 0)
+ throw new IOException("invalid negative recentCount");
+ } catch (IOException e) {
+ // Not fatal - probably upgrading
+ recentCount = recentPtr = 0;
+ }
+ int x = 0;
+ try {
+ for(x = 0; x<recentTimes.length;x++) {
+ recentTimes[x] = i.readInt();
+ if(recentTimes[x] < 0) throw new IOException("negative value");
+ byte[] b = new byte[KEYBYTES];
+ i.readFully(b);
+ recentKeys[x] = new BigInteger(1, b);
+ if(recentKeys[x].signum() == -1) throw new IOException("negative key");
+ if(recentKeys[x].compareTo(keyspace) == 1)
+ throw new IOException("exceeded keyspace");
+ }
+ } catch (IOException ioe) {
+ recentPtr = recentCount = 0;
+ }
+ }
+
+ public void writeTo(DataOutputStream o) throws IOException {
+ logDEBUG("Serializing to disk, accuracy "+time.length);
+ o.writeInt(1); // current version. Using negative numbers for compatibility.
+ o.writeInt(time.length);
+ synchronized(this) {
+ for(int i=0;i<time.length;i++) {
+ o.writeInt(time[i]);
+ byte[] b = key[i].toByteArray();
+ if(b.length > KEYBYTES + 1)
+ throw new IllegalStateException("Key too long in serializing:
"+b.length);
+ if(b.length < KEYBYTES) {
+ int skip = KEYBYTES - b.length;
+ for(int x=0;x<skip;x++)
+ o.writeByte(0);
+ o.write(b);
+ } else o.write(b, b.length - KEYBYTES, KEYBYTES);
+ // in case of zero padding
+ o.writeDouble(sensitivity[i]);
+ }
+ o.writeInt(recentPtr);
+ o.writeInt(recentCount);
+ for(int i=0;i<recentTimes.length;i++) {
+ o.writeInt(recentTimes[i]);
+ byte[] b;
+ if(recentKeys[i] == null) {
+ b = new byte[KEYBYTES];
+ for(int ii=0;ii<KEYBYTES;ii++) b[ii] = 0;
+ } else {
+ b = recentKeys[i].toByteArray();
+ if(b.length > KEYBYTES + 1)
+ throw new IllegalStateException("Key too long in serializing:
"+
+ b.length);
+ }
+ if(b.length < KEYBYTES) {
+ int skip = KEYBYTES - b.length;
+ for(int x=0;x<skip;x++)
+ o.writeByte(0);
+ o.write(b);
+ } else o.write(b, b.length - KEYBYTES, KEYBYTES);
+ // in case of zero padding
+ }
+ }
+ }
+
+ private void logMINOR(String s) {
+ if(Core.logger.shouldLog(Logger.MINOR))
+ Core.logger.log(this, s+" ("+this+")", Logger.MINOR);
+ }
+
+ private static void slogMINOR(String s) {
+ if(Core.logger.shouldLog(Logger.MINOR))
+ Core.logger.log(ResponseTimeEstimator.class,
+ s, Logger.MINOR);
+ }
+
+ private void logDEBUG(String s) {
+ if(Core.logger.shouldLog(Logger.DEBUG))
+ Core.logger.log(this, s+" ("+this+")", Logger.DEBUG);
+ }
+
+ private void logNORMAL(String s) {
+ if(Core.logger.shouldLog(Logger.NORMAL))
+ Core.logger.log(this, s+" ("+this+")", Logger.NORMAL);
+ }
+
+ private static void slogNORMAL(String s) {
+ if(Core.logger.shouldLog(Logger.NORMAL))
+ Core.logger.log(ResponseTimeEstimator.class,
+ s, new Exception("debug"), Logger.NORMAL);
+ }
+
+ public ResponseTimeEstimator(int initTime, int accuracy) {
+ this(accuracy);
+ for(int i=0;i<accuracy;i++) {
+ time[i] = initTime;
+ }
+ }
+
+ public ResponseTimeEstimator(Key k, int high, int low, int accuracy) {
+ key = new BigInteger[accuracy];
+ time = new int[accuracy];
+ sensitivity = new double[accuracy];
+
+ // Center on k
+ // b = keyspace / accuracy
+ // c = k % c
+ // Then set keys as in monadic constructor, except adding k
+ BigInteger a = keyspace.subtract(BigInteger.ONE);
+ BigInteger b = a.divide(BigInteger.valueOf(accuracy));
+ BigInteger ik = convert(k);
+ BigInteger[] dr = ik.divideAndRemainder(b);
+ BigInteger c = dr[1]; // remainder. positive!
+ if(c.signum() < 0) throw new IllegalStateException("argh");
+ int kOffset = dr[0].intValue();
+ for(int i = 0; i < accuracy; i++) {
+ key[i] = c;
+ c.add(b);
+ }
+ // Now the times
+ int val = high;
+ int valStep = (high - low) / accuracy;
+ for(int i = 0; i < accuracy; i++) {
+ int offset = (kOffset + i) % accuracy;
+ time[offset] = val;
+ if(i <= accuracy / 2)
+ val -= valStep;
+ else
+ val += valStep;
+ }
+ }
+
public ResponseTimeEstimator(int accuracy) {
key = new BigInteger[accuracy];
time = new int[accuracy];
+ sensitivity = new double[accuracy];
// Let's evenly distribute the keys across the whole
// keyspace and leave the time values at zero.
- BigInteger a = BigInteger.ONE.shiftLeft(KEYBYTES <<
3).subtract(BigInteger.ONE);
- BigInteger b = a.divide(BigInteger.valueOf(accuracy - 1));
+ BigInteger a = keyspace.subtract(BigInteger.ONE);
+ BigInteger b = a.divide(BigInteger.valueOf(accuracy));
for (int i = key.length; --i >= 0; a = a.subtract(b))
key[i] = a;
}
- public ResponseTimeEstimator(byte[] b) {
- key = new BigInteger[b.length / BYTES];
- time = new int[b.length / BYTES];
-
- byte[] tmp = new byte[KEYBYTES];
- for (int n = 0, i = 0; n < key.length; n++, i += BYTES) {
- time[n] = b[i] << 24 | b[i + 1] << 16 | b[i + 2] << 8 | b[i + 3];
- System.arraycopy(b, i + TIMEBYTES, tmp, 0, KEYBYTES);
- key[n] = new BigInteger(1, tmp);
- }
- }
-
// Return offset of the biggest key that's still less than n.
final int search(BigInteger n) {
int mid, low = 0, high = key.length - 1;
-
+
for (;;) {
mid = (high + low) >> 1;
int i = key[mid].compareTo(n);
@@ -71,53 +255,489 @@
// Interpret key as value between 0 and 2^183.
final BigInteger convert(Key k) {
- return new BigInteger(1, k.getVal());
+ byte[] b = k.getVal();
+ if(b.length < KEYBYTES) {
+ byte[] ob = new byte[KEYBYTES];
+ System.arraycopy(b,0,ob,0,b.length);
+ b = ob;
+ }
+ if(b.length > KEYBYTES) {
+ Core.logger.log(this, "Very long key detected!: "+k,
+ new Exception("debug"), Logger.NORMAL);
+ byte[] ob = new byte[KEYBYTES];
+ System.arraycopy(b,0,ob,0,KEYBYTES);
+ }
+ return new BigInteger(1, b);
+ }
+
+ protected final class MySorter implements Sortable {
+ public final int compare(int index1, int index2) {
+ return key[index1].compareTo(key[index2]);
+ }
+
+ public final void swap(int index1, int index2) {
+ BigInteger bi = key[index1];
+ key[index1] = key[index2];
+ key[index2] = bi;
+ }
+
+ public final int size() {
+ return key.length;
+ }
+ }
+
+ final MySorter ms = new MySorter();
+
+ protected void orderKeys() {
+ Core.logger.log(this, "Reordering keys", Logger.DEBUG);
+ dumpLog();
+ // We cannot simply find the lowest value and then shift,
+ // Becuase we are not using anything like strict gravity
+ // We move the first key 1/2 the distance closer, the second 1/4 its distance
+ // closer, the third 1/8 its distance closer etc
+ // They get reordered!
+ QuickSorter.quickSort(ms);
+ dumpLog();
+ }
+
+ static final BigDecimal DEC_ONE = new BigDecimal(1.0);
+ static final BigInteger THREE = BigInteger.valueOf(3);
+ static final BigInteger FOUR = BigInteger.valueOf(4);
+
+ protected synchronized int reportDecreasing(BigInteger lowerBound,
+ BigInteger upperBound,
+ BigInteger center,
+ int usec,
+ int initialSteps,
+ int lowerBoundPos,
+ int upperBoundPos) {
+ Core.logger.log(this, "reportDecreasing("+lowerBound.toString(16)+","+
+ upperBound.toString(16)+","+center.toString(16)+","+
+ initialSteps+","+lowerBoundPos+","+upperBoundPos+")",
+ new Exception("debug"), Logger.DEBUG);
+ dumpLog();
+ if(upperBoundPos >= key.length-1)
+ upperBoundPos = key.length - 1;
+ if(lowerBoundPos >= key.length-1)
+ lowerBoundPos = key.length - 1;
+ if(lowerBoundPos < 0)
+ lowerBoundPos = 0;
+ if(upperBoundPos < 0)
+ upperBoundPos = 0;
+ // Loop from lowerBoundPos to upperBoundPos, inclusive
+ // We are increasing
+ // inc shiftAmount each time we move a point
+ int shiftAmount = initialSteps;
+ while(key[upperBoundPos].compareTo(upperBound) == 1) {
+ upperBoundPos--;
+ if(upperBoundPos < 0) return initialSteps;
+ }
+ while(key[lowerBoundPos].compareTo(lowerBound) == -1) {
+ lowerBoundPos++;
+ if(lowerBoundPos >= key.length) return initialSteps;
+ }
+ if(lowerBoundPos > upperBoundPos) return initialSteps;
+ for(int i=lowerBoundPos;i<=upperBoundPos;i++) {
+ Core.logger.log(this, "Trying key["+i+"]: "+
+ key[i].toString(16)+","+time[i],
+ Logger.DEBUG);
+ 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);
+ // 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
+ */
+ // Multiply by 75% to prevent points from collapsing on each other
+ 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);
+ diff = diff.multiply(THREE).divide(FOUR);
+ 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];
+ double fracTimediff = (double)timediff;
+ double resultTimediff = fracTimediff/(sens+1.0);
+ timediff = ((int)resultTimediff) >> shiftAmount;
+ timediff = (timediff*3)/4;
+ 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;
+ }
+
+ protected synchronized int reportIncreasing(BigInteger lowerBound,
+ BigInteger upperBound,
+ BigInteger center,
+ int usec,
+ int initialSteps,
+ int lowerBoundPos,
+ int upperBoundPos) {
+ Core.logger.log(this, "reportDecreasing("+lowerBound.toString(16)+","+
+ upperBound.toString(16)+","+center.toString(16)+","+
+ initialSteps+","+lowerBoundPos+","+upperBoundPos+")",
+ new Exception("debug"), Logger.DEBUG);
+ dumpLog();
+ if(upperBoundPos >= key.length-1)
+ upperBoundPos = key.length - 1;
+ if(lowerBoundPos >= key.length-1)
+ lowerBoundPos = key.length - 1;
+ if(lowerBoundPos < 0)
+ lowerBoundPos = 0;
+ if(upperBoundPos < 0)
+ upperBoundPos = 0;
+ // Loop from lowerBoundPos to upperBoundPos, inclusive
+ // We are increasing
+ // inc shiftAmount each time we move a point
+ int shiftAmount = initialSteps;
+ while(key[upperBoundPos].compareTo(upperBound) == 1) {
+ upperBoundPos--;
+ if(upperBoundPos < 0) return initialSteps;
+ }
+ while(key[lowerBoundPos].compareTo(lowerBound) == -1) {
+ lowerBoundPos++;
+ if(lowerBoundPos >= key.length) return initialSteps;
+ }
+ if(lowerBoundPos > upperBoundPos) return initialSteps;
+ for(int i=upperBoundPos;i>=lowerBoundPos;i--) {
+ Core.logger.log(this, "Trying key["+i+"]: "+
+ key[i].toString(16)+","+time[i],
+ Logger.DEBUG);
+ 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);
+ 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);
+ diff = diff.multiply(THREE).divide(FOUR);
+ 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];
+ double fracTimediff = (double)timediff;
+ double resultTimediff = fracTimediff/(sens+1.0);
+ timediff = ((int)resultTimediff) >> shiftAmount;
+ timediff = (timediff*3)/4;
+ 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;
}
-
- public void report(Key k, int usec) {
+
+ public synchronized void report(Key k, int usec) {
BigInteger n = convert(k);
+
+ if(usec < 0) throw new IllegalArgumentException("negative usec in report()");
+
+ recentKeys[recentPtr] = n;
+ recentTimes[recentPtr] = usec;
+ recentCount++;
+ recentPtr++;
+ if(recentPtr >= RECENT_LENGTH) recentPtr = 0;
+
int pos = search(n);
-
+
+ Core.logger.log(this, "report("+n.toString(16)+","+usec+")",
+ Logger.DEBUG);
+
+ dumpLog();
+ int x = n.compareTo(halfkeyspace);
+ if(x == 1) {
+ Core.logger.log(this, "Above half keyspace",
+ Logger.DEBUG);
+ // We are above the half way point
+ // n ... keyspace, 0 ... n-halfkeyspace moved left
+ // n-halfkeyspace ... n moved right
+ BigInteger m = n.subtract(halfkeyspace);
+ int mpos = search(m);
+ int steps = reportDecreasing(n, keyspace, n, usec, 0, pos+1, key.length-1);
+ reportDecreasing(BigInteger.ZERO, m, n, usec, steps, 0, mpos);
+ reportIncreasing(m, n, n, usec, 0, mpos+1, key.length-1);
+ orderKeys(); // if the edge wraps, over the next section, then we
orderKeys before the next section is done, we are stuffed
+ } else if(x == -1) {
+ Core.logger.log(this, "Below half keyspace",
+ Logger.DEBUG);
+ // We are below the half way point
+ // n ... n+halfkeyspace moved left
+ // 0 ... n moved right
+ // n+halfkeyspace .. keyspace moved right
+ BigInteger c = n.add(halfkeyspace);
+ int cpos = search(c);
+ reportDecreasing(n, c, n, usec, 0, pos+1, cpos);
+ int steps = reportIncreasing(BigInteger.ZERO, n, n, usec, 0, 0, pos);
+ reportIncreasing(c, keyspace, n, usec, steps, cpos+1, key.length-1);
+ orderKeys();
+ } else {
+ Core.logger.log(this, "Dead on half keyspace",
+ Logger.DEBUG);
+ // We are in the exact center
+ int mpos = search(halfkeyspace);
+ reportIncreasing(BigInteger.ZERO, halfkeyspace, halfkeyspace, usec,
+ 0, 0, mpos);
+ reportDecreasing(halfkeyspace, keyspace, halfkeyspace, usec,
+ 0, mpos+1, key.length-1);
+ orderKeys();
+ }
+ Core.logger.log(this, "report("+n.toString(16)+","+usec+") completed",
+ Logger.DEBUG);
// Descending...
- if (pos > 0) {
- for (int g = 0, i = pos; ++g < KEYBYTES << 3 && i > 0; i--)
- key[i] = key[i].add(n.subtract(key[i]).shiftRight(g));
-
- for (int g = 0, i = pos; ++g < 32 && i > 0; i--)
- time[i] += (usec - time[i]) >> g;
- }
-
- // Ascending...
- if (pos < key.length - 1) {
- if (pos == 0 && n.compareTo(key[0]) < 0)
- pos--;
-
- for (int g = 0, i = pos; ++g < KEYBYTES << 3 && ++i < key.length;)
- key[i] = key[i].add(n.subtract(key[i]).shiftRight(g));
-
- for (int g = 0, i = pos; ++g < 32 && ++i < key.length;)
- time[i] += (usec - time[i]) >> g;
- }
+// if (pos > 0) {
+// for (int g = 0, i = pos; ++g < KEYBYTES << 3 && i >= 0; i--)
+// key[i] = key[i].add(n.subtract(key[i]).shiftRight(g));
+
+// for (int g = 0, i = pos; ++g < 32 && i >= 0; i--)
+// time[i] += (usec - time[i]) >> g;
+// }
+ }
+
+ public void dumpHtml(java.io.PrintWriter pw) throws IOException {
+ 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><td>"+sensitivity[x]+
+ "</td></tr>");
+ }
+ pw.println("<tr><td>Maximum</td><td colspan=\"2\">"+
+ keyspace.toString(16)+
+ "</td></tr>");
+ // I hope there is an optimized toString(16) ...
+ pw.println("</table>");
+// if(recentCount > 0) {
+// pw.println("<p>Recent points</p>");
+// pw.println("<table border=\"0\">");
+// int l = recentPtr;
+// if(recentCount > RECENT_LENGTH) l = RECENT_LENGTH;
+// for(int i=0;i<l;i++) {
+// pw.println("<tr><td>"+i+"</td><td>"+recentKeys[i].toString(16)+
+// "</td><td>"+recentTimes[i]+"</td></tr>");
+// }
+// pw.println("</table>");
+// }
+ }
+
+ public void dumpLog() {
+ StringBuffer sb = new StringBuffer();
+ for(int x=0;x<key.length;x++) {
+ sb.append(key[x].toString(16));
+ sb.append(": ");
+ sb.append(Integer.toString(time[x]));
+ sb.append("\n");
+ }
+ Core.logger.log(this, "Dump of "+this+": \n"+sb.toString(),
+ Logger.MINOR);
+ }
+
+ public double guessTime(Key k) {
+ synchronized(this) {
+ return (double)guess(k); // resolution 1ms
+ }
+ }
+
+ protected final double intToProbability(int x) {
+ double p = ((double)x) / (1<<30);
+ if(p < 0.0) {
+ logMINOR("Guessed Probability < 0");
+ return 0.0;
+ }
+ if(p > 1.0) {
+ logMINOR("Guessed Probability > 1");
+ return 1.0;
+ }
+ return p;
+ }
+
+ public double guessProbability(Key k) {
+ int x;
+ synchronized(this) {
+ x = guess(k);
+ }
+ return intToProbability(x);
+ // range 0.0 to 1.0, so we can use lots of bits
+ }
+
+ public double guessTransferRate(Key k) {
+ int x;
+ synchronized(this) {
+ x = guess(k);
+ }
+ double p = ((double)x) / (16*1000);
+ // 1/16th second resolution. Return in bytes per millisecond.
+ if(x <= 1) logMINOR("Guessed transfer rate very low!");
+ return p;
+ }
+
+ private static int convertTime(long millis) {
+ int x;
+ if(millis < 0)
+ throw new IllegalArgumentException("Negative time "+millis);
+ if(millis > Integer.MAX_VALUE) {
+ slogNORMAL("Very high reported time: "+millis);
+ x = Integer.MAX_VALUE;
+ } else x = (int)millis;
+ return x;
+ }
+
+ public void reportTime(Key k, long millis) {
+ int x = convertTime(millis);
+ synchronized(this) {
+ report(k, x);
+ }
+ }
+
+ public void reportProbability(Key k, double p) {
+ if(p < 0.0)
+ throw new IllegalArgumentException("Negative probability");
+ if(p > 1.0)
+ throw new IllegalArgumentException("Probability over 1.0");
+ int x = (int) (p * (1<<30));
+ synchronized(this) {
+ report(k, x);
+ }
+ }
+
+ public void reportTransferRate(Key k, double rate) {
+ int x = convertRate(rate);
+ synchronized(this) {
+ report(k, x);
+ }
+ }
+
+ private static int convertRate(double rate) {
+ if(rate < 0.0)
+ throw new IllegalArgumentException("Negative transfer rate");
+ rate = rate * 1000; // convert to bytes per second
+ int x;
+ if(rate > (((float)Integer.MAX_VALUE) / 16)) {
+ slogNORMAL("Really high transfer rate!: "+rate);
+ x = Integer.MAX_VALUE;
+ } else {
+ x = (int)(rate * 16);
+ }
+ return x;
+ }
+
+ public long guessRaw(Key k) {
+ return (long)guess(k);
+ }
+
+ public long highestRaw() {
+ int highest = 0;
+ for(int x=0;x<time.length;x++) {
+ if(time[x] > highest) highest = time[x];
+ }
+ return highest;
+ }
+
+ public long lowestRaw() {
+ int lowest = Integer.MAX_VALUE;
+ for(int x=0;x<time.length;x++) {
+ if(time[x] < lowest) lowest = time[x];
+ }
+ return lowest;
+ }
+
+ public double convertFromRaw(long x, int type) {
+ if(type == TIME) return (double)x;
+ if(type == PROBABILITY) return intToProbability((int)x);
+ if(type == TRANSFER_RATE) return ((double)x) / (16*1000);
+ throw new IllegalArgumentException("unknown type");
+ }
+
+ public String formatFromRaw(long x, int type) {
+ if(x < 0) {
+ dumpLog();
+ throw new IllegalArgumentException("negative!");
+ }
+ if(type == TIME) return Long.toString(x)+"ms";
+ if(type == PROBABILITY) {
+ if(x > Integer.MAX_VALUE) throw new IllegalArgumentException("to big
probability");
+ return Double.toString(intToProbability((int)x));
+ }
+ if(type == TRANSFER_RATE)
+ return Double.toString(((double)x) / (16*1000)) + "bytes/second";
+ throw new IllegalArgumentException("unknown type");
}
public int guess(Key k) {
- BigInteger n = convert(k);
+ return guess(convert(k));
+ }
+
+ public int guess(BigInteger n) {
int pos = search(n);
-
+
// It's off the charts...
- if (pos == 0 && n.compareTo(key[0]) < 0 || pos == key.length - 1)
- return time[pos];
-
+ //if (pos == 0 && n.compareTo(key[0]) < 0 || pos == key.length - 1)
+ //return time[pos];
+
+ int npos;
+ BigInteger beforeKey, afterKey;
+ int beforeTime, afterTime;
+ int opos = pos;
+ if ((pos == 0 && n.compareTo(key[0]) < 0) ||
+ (pos == key.length - 1)) {
+ // Off the end/beginning
+ // Doesn't matter which
+ pos = key.length -1;
+ npos = 0;
+ beforeTime = time[pos];
+ afterTime = time[npos];
+ BigInteger a = keyspace;
+ beforeKey = key[key.length-1].
+ subtract(a);
+ // Yes, beforeKey should be negative
+ if(opos == key.length -1)
+ n = n.subtract(a);
+ afterKey = key[0];
+ } else {
+ // In the middle
+ //pos = pos;
+ npos = pos + 1;
+ beforeTime = time[pos];
+ afterTime = time[npos];
+ beforeKey = key[pos];
+ afterKey = key[npos];
+ }
+
// Solve for the time given key and two bounding points.
- BigInteger i = BigInteger.valueOf(time[pos + 1] - time[pos])
- .multiply(n.subtract(key[pos]))
- .divide(key[pos + 1].subtract(key[pos]))
- .add(BigInteger.valueOf(time[pos]));
-
- System.out.println("\n"+key[pos]+"="+time[pos]);
- System.out.println(n+"="+i.intValue());
- System.out.println(key[pos+1]+"="+time[pos+1]);
-
+ BigInteger i = BigInteger.valueOf(afterTime - beforeTime)
+ .multiply(n.subtract(beforeKey))
+ .divide(afterKey.subtract(beforeKey))
+ .add(BigInteger.valueOf(beforeTime));
+
+ //System.out.println("\n"+key[pos]+"="+time[pos]);
+ //System.out.println(n+"="+i.intValue());
+ //System.out.println(key[pos+1]+"="+time[pos+1]);
+
// 2^31 microseconds is 36 minutes.
return i.intValue();
}
@@ -150,12 +770,49 @@
for (int i = 0; i < key.length; i++)
System.out.println(i+":\t"+key[i]+"\t"+time[i]);
}
-
+
+ public static TimeEstimatorFactory factory() {
+ return factory(DEFAULT_ACCURACY);
+ }
+
+ public static TimeEstimatorFactory factory(int accuracy) {
+ return new ResponseTimeEstimatorFactory(accuracy);
+ }
+
+ public static class ResponseTimeEstimatorFactory
+ implements TimeEstimatorFactory {
+ int accuracy;
+ public ResponseTimeEstimatorFactory(int accuracy) {
+ this.accuracy = accuracy;
+ }
+
+ public TimeEstimator create(DataInputStream dis) throws IOException {
+ return new ResponseTimeEstimator(dis);
+ }
+
+ public TimeEstimator create(Key k, long high, long low) {
+ return new ResponseTimeEstimator(k, convertTime(high),
+ convertTime(low), accuracy);
+ }
+
+ public TimeEstimator createZero() {
+ return new ResponseTimeEstimator(accuracy);
+ }
+
+ public TimeEstimator createInitTransfer(double initRate) {
+ return new ResponseTimeEstimator(convertRate(initRate),
+ accuracy);
+ }
+ }
+
public static void main(String[] args) {
-// Random r = new Random();
+ Random r = new Random();
ResponseTimeEstimator rte = new ResponseTimeEstimator(1024);
rte.print();
- rte.report(new Key(5), 64);
+ byte[] b = new byte[5];
+ r.nextBytes(b);
+ Key k = new Key(b);
+ rte.report(k, 64);
rte.print();
/*
for (int i = 0; i < 1000; i++) {
@@ -171,5 +828,57 @@
rte.report(new Key(r), i);
rte.print();
}*/
+ }
+
+ public void drawGraphBMP(int width, int height, boolean dontClipPoints,
+ OutputStream os)
+ throws IOException {
+ int[] val = new int[width];
+ BigInteger a = keyspace.subtract(BigInteger.ONE);
+ BigInteger b = a.divide(BigInteger.valueOf(width));
+ BigInteger at = BigInteger.ZERO;
+ int lowest = Integer.MAX_VALUE;
+ int highest = 0;
+ for(int i=0;i<width;i++) {
+ val[i] = guess(at);
+// Core.logger.log(this, "Guess for "+at+": "+val[i],
+// Logger.DEBUG);
+ if(val[i] < lowest) lowest = val[i];
+ if(val[i] > highest) highest = val[i];
+ at = at.add(b);
+ }
+ int x = recentPtr;
+ if(recentCount > RECENT_LENGTH) x = RECENT_LENGTH;
+ if(dontClipPoints) {
+ for(int i=0;i<x;i++) {
+ if(recentTimes[i] < lowest) lowest = recentTimes[i];
+ if(recentTimes[i] > highest) highest = recentTimes[i];
+ }
+ }
+ // lowest ... highest
+ // lowest mapped to 0
+ // highest mapped to height
+ double multiplier = ((double)height-1) / ((double)(highest - lowest));
+ Bitmap bmp = new Bitmap(width, height);
+ bmp.setPenColor(new Color(0,0,0));
+ for(int i=0;i<width;i++) {
+ int position = (int)((val[i] - lowest) * multiplier);
+ position = height - (position + 1);
+ bmp.setPixel(i, position);
+ }
+ // Now plot the recent points
+ bmp.setPenColor(new Color(255,0,0));
+ for(int i=0;i<x;i++) {
+ int w = recentKeys[i].divide(b).intValue();
+ int h = (int)((recentTimes[i] - lowest) * multiplier);
+ if(h < 0) h = 0;
+ if(h > height-1) h = height-1;
+ h = height - (h+1);
+ bmp.drawPlus(w,h);
+ }
+ BitmapEncoder enc = new DibEncoder();
+ enc.setBitmap(bmp);
+ enc.encode(os);
+ os.close();
}
}
Index: Routing.java
===================================================================
RCS file: /cvsroot/freenet/freenet/src/freenet/node/rt/Routing.java,v
retrieving revision 1.6
retrieving revision 1.7
diff -u -r1.6 -r1.7
--- Routing.java 19 Apr 2003 15:32:54 -0000 1.6
+++ Routing.java 30 Aug 2003 23:16:52 -0000 1.7
@@ -2,6 +2,7 @@
import freenet.Identity;
import freenet.node.NodeReference;
+import freenet.Key;
/**
* Supplies a sequence of NodeReferences in order of routing
@@ -44,7 +45,7 @@
* Called if the routed node is connected to
* and authorized with successfully.
*/
- void routeConnected();
+ void routeConnected(boolean cached);
/**
* Called if communications with the routed node fail.
@@ -88,7 +89,7 @@
/**
* Called if the routed node fails during file transfer.
*/
- void transferFailed();
+ void transferFailed(long time, int htl, long size, long etime);
/**
* Called if the routed node sends bad data.
@@ -101,6 +102,25 @@
* request is answered with a QueryRejected.
*/
void queryRejected(boolean cached, long attenuation);
+
+ /**
+ * Called if the node sends the message, then times out
+ * before OR after after sending the message
+ */
+ void searchFailed(long time);
+
+ /**
+ * Called when we get a DataNotFound
+ */
+ void dataNotFound(int htl);
+
+ void transferSucceeded(long time, int htl, long size, long etime);
+
+ /**
+ * Called to terminate the Routing, when it will no longer be called,
+ * because of external circumstances e.g. ran out of HTL
+ */
+ void terminate(boolean success, boolean routingRelated);
}
Index: RoutingTable.java
===================================================================
RCS file: /cvsroot/freenet/freenet/src/freenet/node/rt/RoutingTable.java,v
retrieving revision 1.6
retrieving revision 1.7
diff -u -r1.6 -r1.7
--- RoutingTable.java 26 Jul 2003 21:36:29 -0000 1.6
+++ RoutingTable.java 30 Aug 2003 23:16:52 -0000 1.7
@@ -33,13 +33,18 @@
* Returns a Routing object which can be used to get
* a sequence of NodeReference objects in order of
* routing preference, and which accepts feedback
- * about the results of routing.
+ * about the results of routing. Different
+ * implementations will use or ignore different
+ * parameters (all should use the key though).
*
- * @param k the key to find routes for
+ * @param k the key to find routes for
+ * @param htl the hops to live of the message we are about to send
+ * @param size the size of the file we are trying to obtain or send
* @param force whether to try to contact backed off nodes
- * @return the generated Routing object
+ * @return the generated Routing object
*/
- Routing route(Key k, boolean force);
+ Routing route(Key k, int htl, long size, boolean force,
+ boolean isInsert);
/**
* NOTE: It is important to hold the sync-lock
@@ -76,7 +81,18 @@
* Returns the total number of references found when
* initializing
*/
- public long initialRefsCount();
+ long initialRefsCount();
+
+ // NGRouting helpers
+ /**
+ * Report a successful connection
+ */
+ void reportConnectionSuccess(Identity id, long time);
+
+ /**
+ * Report a failed connection
+ */
+ void reportConnectionFailure(Identity id, long time);
}
Index: StoredRoutingTable.java
===================================================================
RCS file: /cvsroot/freenet/freenet/src/freenet/node/rt/StoredRoutingTable.java,v
retrieving revision 1.4
retrieving revision 1.5
diff -u -r1.4 -r1.5
--- StoredRoutingTable.java 20 Aug 2003 17:11:33 -0000 1.4
+++ StoredRoutingTable.java 30 Aug 2003 23:16:52 -0000 1.5
@@ -21,7 +21,7 @@
protected final RoutingStore routingStore;
protected final int maxNodes;
-
+
protected Node node = null;
public StoredRoutingTable(RoutingStore routingStore,
@@ -48,6 +48,7 @@
}
return mem;
}
+
//all threads end up being stuck here
//routingTime goes up several seconds
//cpu load goes 100%
@@ -104,8 +105,11 @@
Core.logger.log(this, "discard("+onum+") locked RT for
"+length,
length>500?Core.logger.MINOR:Core.logger.DEBUG);
DiscardSort d;
- while (num-- > 0 && null != (d = (DiscardSort) heap.pop()))
+ while (num-- > 0 && null != (d = (DiscardSort) heap.pop())) {
remove(d.mem, d.ident);
+ if(Core.logger.shouldLog(Logger.DEBUG))
+ Core.logger.log(this, "Removing "+d,
Logger.DEBUG);
+ }
Core.logger.log(this, "Discarded "+onum+" references",
Core.logger.DEBUG);
}
@@ -117,6 +121,9 @@
final Comparable cmp;
final Identity ident;
final RoutingMemory mem;
+ public String toString() {
+ return "DiscardSort: "+mem+","+ident+","+cmp;
+ }
DiscardSort(Comparable cmp, RoutingMemory mem) {
this.cmp = cmp;
this.mem = mem;
Index: TreeRouting.java
===================================================================
RCS file: /cvsroot/freenet/freenet/src/freenet/node/rt/TreeRouting.java,v
retrieving revision 1.23
retrieving revision 1.24
diff -u -r1.23 -r1.24
--- TreeRouting.java 29 Jul 2003 17:30:46 -0000 1.23
+++ TreeRouting.java 30 Aug 2003 23:16:52 -0000 1.24
@@ -16,7 +16,7 @@
* if its RoutingMemory can pass the isRoutable() test.
* @author tavin
*/
-class TreeRouting implements Routing {
+class TreeRouting extends TerminatableRouting {
protected final Hashtable steps = new Hashtable();
@@ -69,6 +69,7 @@
desperate+", doDesperate="+
doDesperate+", stepCount="+stepCount+" for "+
refWalk, Logger.DEBUG);
+ terminate(false, true);
return null;
} else {
if(logDEBUG)
@@ -216,7 +217,7 @@
return mem == null ? null : mem.getIdentity();
}
- public final void routeConnected() {
+ public final void routeConnected(boolean cached) {
rt.routeConnected(mem);
}
@@ -241,10 +242,6 @@
rt.timedOut(mem);
}
- public final void transferFailed() {
- rt.transferFailed(mem);
- }
-
public final void verityFailed() {
rt.verityFailed(mem);
}
@@ -253,11 +250,41 @@
rt.queryRejected(mem, cached, attenuation);
}
- public void searchFailed(long time, int htl) {};
+ public void searchFailed(long time) {};
+
+ public void transferFailed(long time, int htl, long size, long etime) {
+ rt.transferFailed(mem);
+ // Not usually terminal
+ };
+
+ public void transferSucceeded(long time, int htl, long size, long etime) {
+ terminate(true, true);
+ long stdFileSize;
+ if(node.dir.countKeys() > 16)
+ stdFileSize = (node.storeSize - node.dir.available()) /
+ node.dir.countKeys();
+ else stdFileSize = 100000;
+ long normalizedTime = time + (etime*stdFileSize/size);
+ Core.diagnostics.occurrenceContinuous("normalizedSuccessTime",
+ normalizedTime);
+ Core.diagnostics.occurrenceContinuous("successSearchTime",
+ time);
+ if(size > 16384)
+ Core.diagnostics.occurrenceContinuous("successTransferRate",
+ ((double)size*1000)/
+ ((double)etime));
+ };
- public void messageFailed(long time, int htl, long etime) {};
+ public void dataNotFound(int htl) {
+ terminate(false, true);
+ // We don't care
+ }
- public void messageSucceeded(long time, int htl, long etime) {};
+ protected void reallyTerminate(boolean success, boolean routingRelated) {
+ super.reallyTerminate(success, routingRelated);
+ desperate = true;
+ stepCount = node.maxRoutingSteps+1;
+ }
}
Index: TreeRoutingTable.java
===================================================================
RCS file: /cvsroot/freenet/freenet/src/freenet/node/rt/TreeRoutingTable.java,v
retrieving revision 1.24
retrieving revision 1.25
diff -u -r1.24 -r1.25
--- TreeRoutingTable.java 29 Jul 2003 17:30:46 -0000 1.24
+++ TreeRoutingTable.java 30 Aug 2003 23:16:52 -0000 1.25
@@ -96,11 +96,13 @@
}
}
- public synchronized Routing route(Key k) {
- return route(k, false);
+ public synchronized Routing route(Key k, int htl, long size) {
+ return route(k, htl, size, false, false);
}
- public synchronized Routing route(Key k, boolean doDesperate) {
+ public synchronized Routing route(Key k, int htl, long size,
+ boolean doDesperate,
+ boolean isInsert) {
long x = -1;
boolean logDEBUG = Core.logger.shouldLog(Logger.DEBUG);
_______________________________________________
cvs mailing list
[EMAIL PROTECTED]
http://dodo.freenetproject.org/cgi-bin/mailman/listinfo/cvs
