[freenet-cvs] r13497 - trunk/freenet/src/freenet/node

[toad at freenetproject.org]

Author: toad
Date: 2007-06-08 18:42:22 +0000 (Fri, 08 Jun 2007)
New Revision: 13497

Modified:
   trunk/freenet/src/freenet/node/NodeDispatcher.java
Log:
Implement limited forking on the return path for probe requests.
This is an attempt to test the lost-down-a-rabbit-hole algorithm.
Will only take effect if the next node returns a list of best-seen-not-visited-so-far.

Modified: trunk/freenet/src/freenet/node/NodeDispatcher.java
===================================================================
--- trunk/freenet/src/freenet/node/NodeDispatcher.java	2007-06-08 18:17:09 UTC (rev 13496)
+++ trunk/freenet/src/freenet/node/NodeDispatcher.java	2007-06-08 18:42:22 UTC (rev 13497)
@@ -428,6 +428,7 @@
 		double nearest;
 		double best;
 		Vector notVisitedList; // List of best locations not yet visited by this request
+		int forkCount;
 
 		public ProbeContext(long id, double target, double best, double nearest, short htl, short counter, PeerNode src, ProbeCallback cb) {
 			visitedPeers = new HashSet();
@@ -488,10 +489,12 @@
 			for(int i=0;i<locsNotVisited.length;i++)
 				notVisitedList.add(new Double(locsNotVisited[i]));
 		}
-		return innerHandleProbeRequest(src, id, lid, target, best, nearest, htl, counter, true, true, false, null, notVisitedList);
+		innerHandleProbeRequest(src, id, lid, target, best, nearest, htl, counter, true, true, false, null, notVisitedList);
+		return true;
 	}
 
 	final int MAX_LOCS_NOT_VISITED = 3;
+	final int MAX_FORKS = 2;
 	
 	/**
 	 * 
@@ -509,7 +512,7 @@
 	 * @param locsNotVisited 
 	 * @return
 	 */
-	private boolean innerHandleProbeRequest(PeerNode src, long id, Long lid, final double target, double best, 
+	private void innerHandleProbeRequest(PeerNode src, long id, Long lid, final double target, double best, 
 			double nearest, short htl, short counter, boolean checkRecent, boolean canReject, 
 			boolean fromRejection, ProbeCallback cb, Vector locsNotVisited) {
 		short max = node.maxHTL();
@@ -554,7 +557,7 @@
 			} catch (NotConnectedException e) {
 				Logger.error(this, "Not connected rejecting a probe request from "+src);
 			}
-			return true;
+			return;
 		}
 		if(ctx.counter < counter) ctx.counter = counter;
 		if(logMINOR)
@@ -625,7 +628,7 @@
 				} catch (NotConnectedException e) {
 					Logger.error(this, "Not connected completing a probe request from "+src);
 				}
-				return true;
+				return;
 			} else {
 				complete("success", target, best, nearest, id, ctx, counter);
 			}
@@ -681,7 +684,7 @@
 				} else {
 					complete("RNF", target, best, nearest, id, ctx, counter);
 				}
-				return true;
+				return;
 			}
 
 			visited.add(pn);
@@ -702,7 +705,7 @@
 			forwarded.addSubMessage(sub);
 			try {
 				pn.sendAsync(forwarded, null, 0, null);
-				return true;
+				return;
 			} catch (NotConnectedException e) {
 				Logger.error(this, "Could not forward message: disconnected: "+pn+" : "+e, e);
 				// Try another one
@@ -739,7 +742,23 @@
 		short counter = m.getShort(DMT.COUNTER);
 		if(logMINOR)
 			Logger.minor(this, "Probe reply: "+id+ ' ' +target+ ' ' +best+ ' ' +nearest);
-		// Just propagate back to source
+		
+		// New backtracking algorithm
+		
+		// Allow forking on the way home - but only if the location we'd fork to would be at least as good as the third best location seen but not visited so far.
+		
+		// First get the list of not visited so far nodes
+		
+		Message notVisited = m.getSubMessage(DMT.FNPBestRoutesNotTaken);
+		double[] locsNotVisited = null;
+		Vector notVisitedList = new Vector();
+		if(notVisited != null) {
+			locsNotVisited = Fields.bytesToDoubles(((ShortBuffer)notVisited.getObject(DMT.BEST_LOCATIONS_NOT_VISITED)).getData());
+			for(int i=0;i<locsNotVisited.length;i++)
+				notVisitedList.add(new Double(locsNotVisited[i]));
+		}
+
+		// Find it
 		ProbeContext ctx;
 		synchronized(recentProbeContexts) {
 			ctx = (ProbeContext) recentProbeContexts.get(lid);
@@ -747,11 +766,22 @@
 				Logger.normal(this, "Could not forward probe reply back to source for ID "+id);
 				return false;
 			}
-			recentProbeContexts.push(lid, ctx); // promote or add
+			recentProbeContexts.push(lid, ctx); // promote
 			while(recentProbeContexts.size() > MAX_PROBE_CONTEXTS)
 				recentProbeContexts.popValue();
 		}
 
+		// Maybe fork
+		
+		if(notVisitedList.size() > 0) {
+			if(ctx.forkCount < MAX_FORKS) {
+				ctx.forkCount++;
+				innerHandleProbeRequest(src, id, lid, target, best, nearest, ctx.htl, counter, false, false, false, null, notVisitedList);
+				return true;
+			}
+		}
+		
+		// Just propagate back to source
 		if(ctx.src != null) {
 			Message complete = DMT.createFNPProbeReply(id, target, nearest, best, counter++);
 			Message sub = m.getSubMessage(DMT.FNPBestRoutesNotTaken);
@@ -844,7 +874,8 @@
 			for(int i=0;i<locsNotVisited.length;i++)
 				notVisitedList.add(new Double(locsNotVisited[i]));
 		}
-		return innerHandleProbeRequest(src, id, lid, target, best, nearest, htl, counter, false, false, true, null, notVisitedList);
+		innerHandleProbeRequest(src, id, lid, target, best, nearest, htl, counter, false, false, true, null, notVisitedList);
+		return true;
 	}
 
 	public void startProbe(double d, ProbeCallback cb) {