Author: mrogers
Date: 2006-09-12 19:20:52 +0000 (Tue, 12 Sep 2006)
New Revision: 10459
Modified:
trunk/apps/load-balancing-sims/phase6/ChkRequestHandler.java
trunk/apps/load-balancing-sims/phase6/Node.java
trunk/apps/load-balancing-sims/phase6/Sim.java
trunk/apps/load-balancing-sims/phase6/messages/ChkRequest.java
trunk/apps/load-balancing-sims/phase6/messages/RouteNotFound.java
Log:
Hops to live
Modified: trunk/apps/load-balancing-sims/phase6/ChkRequestHandler.java
===================================================================
--- trunk/apps/load-balancing-sims/phase6/ChkRequestHandler.java
2006-09-12 19:04:31 UTC (rev 10458)
+++ trunk/apps/load-balancing-sims/phase6/ChkRequestHandler.java
2006-09-12 19:20:52 UTC (rev 10459)
@@ -1,4 +1,4 @@
-// The state of an outstanding CHK request, stored at each node along the path
+// The state of an outstanding CHK request as stored at each node along the
path
import java.util.LinkedList;
import messages.*;
@@ -12,8 +12,11 @@
public final static int TRANSFERRING = 3;
public final static int COMPLETED = 4;
- public final int id; // The unique ID of the request
- public final int key; // The requested key
+ private final int id; // The unique ID of the request
+ private final int key; // The requested key
+ private double best; // The best location seen so far
+ private int htl; // Hops to live for backtracking
+
private Node node; // The owner of this RequestHandler
private Peer prev; // The previous hop of the request
private Peer next = null; // The (current) next hop of the request
@@ -25,10 +28,20 @@
{
id = r.id;
key = r.key;
+ best = r.best;
+ htl = r.htl;
this.node = node;
this.prev = prev;
nexts = new LinkedList<Peer> (node.peers());
nexts.remove (prev);
+ // If this is the best node so far, update best & reset htl
+ double target = Node.keyToLocation (key);
+ if (Node.distance (target, node.location)
+ < Node.distance (target, best)) {
+ node.log ("resetting htl of " + this);
+ best = node.location;
+ htl = ChkRequest.MAX_HTL;
+ }
}
// Remove a peer from the list of candidates for the next hop
@@ -48,6 +61,8 @@
handleChkDataFound ((ChkDataFound) m);
else if (m instanceof DataNotFound)
handleDataNotFound ((DataNotFound) m);
+ else if (m instanceof RouteNotFound)
+ handleRouteNotFound ((RouteNotFound) m);
else if (m instanceof Block) handleBlock ((Block) m);
else if (m instanceof RouteNotFound) forwardRequest();
else if (m instanceof RejectedLoop) forwardRequest();
@@ -57,7 +72,7 @@
private void handleAccepted (Accepted a)
{
if (state != REQUEST_SENT) node.log (a + " out of order");
- state = ACCEPTED;
+ if (state != TRANSFERRING) state = ACCEPTED;
// Wait 60 seconds for the next hop to start sending the data
Event.schedule (this, 60.0, FETCH_TIMEOUT, next);
}
@@ -80,6 +95,15 @@
state = COMPLETED;
}
+ private void handleRouteNotFound (RouteNotFound rnf)
+ {
+ if (state != ACCEPTED) node.log (rnf + " out of order");
+ if (rnf.htl < htl) htl = rnf.htl;
+ // Use the remaining htl to try another peer
+ nexts.remove (next);
+ forwardRequest();
+ }
+
private void handleBlock (Block b)
{
if (state != TRANSFERRING) node.log (b + " out of order");
@@ -89,9 +113,9 @@
node.log ("forwarding " + b);
prev.sendMessage (b);
}
- // If the transfer is complete, store the data
+ // If the transfer is complete, cache the data
if (receivedAll()) {
- node.storeChk (key);
+ node.cacheChk (key);
if (prev == null) node.log (this + " succeeded");
node.chkRequestCompleted (id);
state = COMPLETED;
@@ -100,26 +124,42 @@
public void forwardRequest()
{
- next = closestPeer();
+ // If the request has run out of hops, send DataNotFound
+ if (htl == 0) {
+ node.log ("data not found for " + this);
+ if (prev == null) node.log (this + " failed");
+ else prev.sendMessage (new DataNotFound (id));
+ node.chkRequestCompleted (id);
+ state = COMPLETED;
+ return;
+ }
+ // Forward the request to the best remaining peer
+ next = bestPeer();
if (next == null) {
node.log ("route not found for " + this);
if (prev == null) node.log (this + " failed");
- else prev.sendMessage (new RouteNotFound (id));
+ else prev.sendMessage (new RouteNotFound (id, htl));
node.chkRequestCompleted (id);
state = COMPLETED;
+ return;
}
- else {
- node.log ("forwarding " + this + " to " + next.address);
- next.sendMessage (new ChkRequest (id, key));
- nexts.remove (next);
- state = REQUEST_SENT;
- // Wait 5 seconds for the next hop to accept the request
- Event.schedule (this, 5.0, ACCEPTED_TIMEOUT, next);
+ // Decrement htl if next node is not best so far
+ double target = Node.keyToLocation (key);
+ if (Node.distance (target, next.location)
+ > Node.distance (target, best)) {
+ htl = node.decrementHtl (htl);
+ node.log (this + " has htl " + htl);
}
+ node.log ("forwarding " + this + " to " + next.address);
+ next.sendMessage (new ChkRequest (id, key, best, htl));
+ nexts.remove (next);
+ state = REQUEST_SENT;
+ // Wait 5 seconds for the next hop to accept the request
+ Event.schedule (this, 5.0, ACCEPTED_TIMEOUT, next);
}
- // Find the closest peer to the requested key
- private Peer closestPeer ()
+ // Find the best remaining peer
+ private Peer bestPeer ()
{
double keyLoc = Node.keyToLocation (key);
double bestDist = Double.POSITIVE_INFINITY;
@@ -137,8 +177,9 @@
// Mark a block as received, return true if it's a duplicate
private boolean receivedBlock (int index)
{
- boolean duplicate = (blockBitmap & 1 << index) != 0;
- blockBitmap |= 1 << index;
+ int mask = 1 << index;
+ boolean duplicate = (blockBitmap & mask) != 0;
+ blockBitmap |= mask;
return duplicate;
}
Modified: trunk/apps/load-balancing-sims/phase6/Node.java
===================================================================
--- trunk/apps/load-balancing-sims/phase6/Node.java 2006-09-12 19:04:31 UTC
(rev 10458)
+++ trunk/apps/load-balancing-sims/phase6/Node.java 2006-09-12 19:20:52 UTC
(rev 10459)
@@ -70,21 +70,8 @@
return (int) (location * Integer.MAX_VALUE);
}
- // Add a CHK to the cache and consider adding it to the store
- public void storeChk (int key)
- {
- log ("key " + key + " added to CHK cache");
- chkCache.put (key);
- // Add the key to the store if this node is as close to the
- // key's location as any of its peers
- if (isClosest (keyToLocation (key))) {
- log ("key " + key + " added to CHK store");
- chkStore.put (key);
- }
- }
-
// Return true if this node is as close to the target as any peer
- private boolean isClosest (double target)
+ private boolean closerThanPeers (double target)
{
double bestDist = Double.POSITIVE_INFINITY;
for (Peer peer : peers.values()) {
@@ -94,6 +81,29 @@
return distance (target, location) <= bestDist;
}
+ // Decrement a request or insert's hops to live
+ public int decrementHtl (int htl)
+ {
+ // FIXME: don't always decrement at min/max
+ return htl - 1;
+ }
+
+ // Add a CHK to the cache
+ public void cacheChk (int key)
+ {
+ log ("key " + key + " added to CHK cache");
+ chkCache.put (key);
+ }
+
+ // Consider adding a CHK to the store
+ public void storeChk (int key)
+ {
+ if (closerThanPeers (keyToLocation (key))) {
+ log ("key " + key + " added to CHK store");
+ chkStore.put (key);
+ }
+ }
+
// Called by Peer
public void startTimer()
{
@@ -195,7 +205,7 @@
// Event callback
private void generateRequest (int key)
{
- ChkRequest r = new ChkRequest (key);
+ ChkRequest r = new ChkRequest (key, location);
log ("generating " + r);
handleChkRequest (r, null);
}
Modified: trunk/apps/load-balancing-sims/phase6/Sim.java
===================================================================
--- trunk/apps/load-balancing-sims/phase6/Sim.java 2006-09-12 19:04:31 UTC
(rev 10458)
+++ trunk/apps/load-balancing-sims/phase6/Sim.java 2006-09-12 19:20:52 UTC
(rev 10459)
@@ -17,20 +17,17 @@
Node n1 = new Node (txSpeed, rxSpeed);
Node n2 = new Node (txSpeed, rxSpeed);
Node n3 = new Node (txSpeed, rxSpeed);
+ Node n4 = new Node (txSpeed, rxSpeed);
- n0.connectBothWays (n1, 0.001);
- n1.connectBothWays (n2, 0.001);
- n1.connectBothWays (n3, 0.001);
- n2.connectBothWays (n3, 0.001);
+ n0.connectBothWays (n1, 0.1);
+ n1.connectBothWays (n2, 0.1);
+ n1.connectBothWays (n3, 0.1);
+ n2.connectBothWays (n3, 0.1);
+ n3.connectBothWays (n4, 0.1);
- // DEBUG
- n2.faulty = true;
-
- for (int i = 0; i < 4; i++) {
+ for (int i = 0; i < 2; i++) {
int key = Node.locationToKey (Math.random());
- // Half the requests will succeed, half will time out
- if (i % 2 == 0) n3.storeChk (key);
- else n2.storeChk (key);
+ if (i % 2 == 0) n4.cacheChk (key);
Event.schedule (n0, 0.0, Node.GENERATE_REQUEST, key);
}
Modified: trunk/apps/load-balancing-sims/phase6/messages/ChkRequest.java
===================================================================
--- trunk/apps/load-balancing-sims/phase6/messages/ChkRequest.java
2006-09-12 19:04:31 UTC (rev 10458)
+++ trunk/apps/load-balancing-sims/phase6/messages/ChkRequest.java
2006-09-12 19:20:52 UTC (rev 10459)
@@ -2,23 +2,31 @@
public class ChkRequest extends Message
{
+ public final static int MAX_HTL = 5; // Maximum amount of backtracking
+
private static int nextId = 0;
public final int key; // The requested key
+ public double best; // The best location seen so far
+ public int htl; // Hops to live for backtracking
// Start a new request
- public ChkRequest (int key)
+ public ChkRequest (int key, double location)
{
id = nextId++;
this.key = key;
+ best = location;
+ htl = MAX_HTL;
size = Message.HEADER_SIZE + Message.KEY_SIZE;
}
// Forward a request
- public ChkRequest (int id, int key)
+ public ChkRequest (int id, int key, double best, int htl)
{
this.id = id;
this.key = key;
+ this.best = best;
+ this.htl = htl;
size = Message.HEADER_SIZE + Message.KEY_SIZE;
}
Modified: trunk/apps/load-balancing-sims/phase6/messages/RouteNotFound.java
===================================================================
--- trunk/apps/load-balancing-sims/phase6/messages/RouteNotFound.java
2006-09-12 19:04:31 UTC (rev 10458)
+++ trunk/apps/load-balancing-sims/phase6/messages/RouteNotFound.java
2006-09-12 19:20:52 UTC (rev 10459)
@@ -2,14 +2,17 @@
public class RouteNotFound extends Message
{
- public RouteNotFound (int id)
+ public int htl; // Hops to live for backtracking
+
+ public RouteNotFound (int id, int htl)
{
this.id = id;
+ this.htl = htl;
size = Message.HEADER_SIZE;
}
public String toString()
{
- return new String ("route not found (" + id + ")");
+ return new String ("route not found (" + id + "," + htl + ")");
}
}
