Author: mrogers
Date: 2006-09-27 16:26:43 +0000 (Wed, 27 Sep 2006)
New Revision: 10517
Modified:
trunk/apps/load-balancing-sims/phase6/ChkInsertHandler.java
trunk/apps/load-balancing-sims/phase6/ChkRequestHandler.java
trunk/apps/load-balancing-sims/phase6/MessageHandler.java
trunk/apps/load-balancing-sims/phase6/Node.java
trunk/apps/load-balancing-sims/phase6/Packet.java
trunk/apps/load-balancing-sims/phase6/RequestHandler.java
trunk/apps/load-balancing-sims/phase6/Sim.java
trunk/apps/load-balancing-sims/phase6/SskInsertHandler.java
trunk/apps/load-balancing-sims/phase6/SskRequestHandler.java
trunk/apps/load-balancing-sims/phase6/messages/Search.java
Log:
Routing fixes
Modified: trunk/apps/load-balancing-sims/phase6/ChkInsertHandler.java
===================================================================
--- trunk/apps/load-balancing-sims/phase6/ChkInsertHandler.java 2006-09-27
11:34:42 UTC (rev 10516)
+++ trunk/apps/load-balancing-sims/phase6/ChkInsertHandler.java 2006-09-27
16:26:43 UTC (rev 10517)
@@ -6,7 +6,6 @@
class ChkInsertHandler extends MessageHandler implements EventTarget
{
private int inState = STARTED; // State of incoming transfer
- private int searchState = STARTED; // State of search
private HashSet<Peer> receivers; // Peers that should receive data
private Block[] blocks; // Store incoming blocks for forwarding
private int blocksReceived = 0;
@@ -78,8 +77,7 @@
private void handleCompleted (TransfersCompleted tc, Peer src)
{
receivers.remove (src);
- if (src == next) forwardSearch();
- else considerFinishing();
+ considerFinishing();
}
private void handleAccepted (Accepted a)
@@ -117,6 +115,8 @@
if (searchState != ACCEPTED) node.log (ir + " out of order");
if (prev == null) node.log (this + " succeeded");
else prev.sendMessage (ir); // Forward the message
+ searchState = COMPLETED;
+ considerFinishing();
}
public void forwardSearch()
@@ -144,10 +144,9 @@
// Decrement the htl if the next node is not the closest so far
double target = Node.keyToLocation (key);
if (Node.distance (target, next.location)
- > Node.distance (target, closest)) {
+ > Node.distance (target, closest))
htl = node.decrementHtl (htl);
- node.log (this + " has htl " + htl);
- }
+ node.log (this + " has htl " + htl);
node.log ("forwarding " + this + " to " + next.address);
next.sendMessage (makeSearchMessage());
nexts.remove (next);
Modified: trunk/apps/load-balancing-sims/phase6/ChkRequestHandler.java
===================================================================
--- trunk/apps/load-balancing-sims/phase6/ChkRequestHandler.java
2006-09-27 11:34:42 UTC (rev 10516)
+++ trunk/apps/load-balancing-sims/phase6/ChkRequestHandler.java
2006-09-27 16:26:43 UTC (rev 10517)
@@ -37,8 +37,8 @@
private void handleChkDataFound (ChkDataFound df)
{
- if (state != ACCEPTED) node.log (df + " out of order");
- state = TRANSFERRING;
+ if (searchState != ACCEPTED) node.log (df + " out of order");
+ searchState = TRANSFERRING;
if (prev != null) prev.sendMessage (df); // Forward the message
// Wait for the transfer to complete (FIXME: check real timeout)
Event.schedule (this, 120.0, TRANSFER_TIMEOUT, next);
@@ -46,7 +46,7 @@
private void handleBlock (Block b)
{
- if (state != TRANSFERRING) node.log (b + " out of order");
+ if (searchState != TRANSFERRING) node.log (b + " out of order");
if (received[b.index]) return; // Ignore duplicates
received[b.index] = true;
blocksReceived++;
Modified: trunk/apps/load-balancing-sims/phase6/MessageHandler.java
===================================================================
--- trunk/apps/load-balancing-sims/phase6/MessageHandler.java 2006-09-27
11:34:42 UTC (rev 10516)
+++ trunk/apps/load-balancing-sims/phase6/MessageHandler.java 2006-09-27
16:26:43 UTC (rev 10517)
@@ -22,6 +22,7 @@
protected Peer prev; // The previous hop of the search
protected Peer next = null; // The (current) next hop of the search
protected LinkedList<Peer> nexts; // Candidates for the next hop
+ protected int searchState = STARTED; // The state of the search
public MessageHandler (Search s, Node node, Peer prev)
{
Modified: trunk/apps/load-balancing-sims/phase6/Node.java
===================================================================
--- trunk/apps/load-balancing-sims/phase6/Node.java 2006-09-27 11:34:42 UTC
(rev 10516)
+++ trunk/apps/load-balancing-sims/phase6/Node.java 2006-09-27 16:26:43 UTC
(rev 10517)
@@ -22,12 +22,19 @@
private LruCache<Integer> sskStore;
private LruCache<Integer> sskCache;
private LruCache<Integer> pubKeyCache; // SSK public keys
+ private boolean decrementMaxHtl = false;
+ private boolean decrementMinHtl = false;
public TokenBucket bandwidth; // Bandwidth limiter
- private boolean timerRunning = false; // Is the timer running?
+ private boolean timerRunning = false; // Is the retx timer running?
public Node (double txSpeed, double rxSpeed)
{
- location = Math.random();
+ this (Math.random(), txSpeed, rxSpeed);
+ }
+
+ public Node (double location, double txSpeed, double rxSpeed)
+ {
+ this.location = location;
net = new NetworkInterface (this, txSpeed, rxSpeed);
peers = new HashMap<Integer,Peer>();
recentlySeenRequests = new HashSet<Integer>();
@@ -37,6 +44,8 @@
sskStore = new LruCache<Integer> (10);
sskCache = new LruCache<Integer> (10);
pubKeyCache = new LruCache<Integer> (10);
+ if (Math.random() < 0.5) decrementMaxHtl = true;
+ if (Math.random() < 0.25) decrementMinHtl = true;
bandwidth = new TokenBucket (BUCKET_RATE, BUCKET_SIZE);
}
@@ -85,8 +94,9 @@
// 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;
+ if ((htl == Search.MAX_HTL && !decrementMaxHtl)
+ || (htl == 1 && !decrementMinHtl)) return htl;
+ else return htl - 1;
}
// Add a CHK to the cache
Modified: trunk/apps/load-balancing-sims/phase6/Packet.java
===================================================================
--- trunk/apps/load-balancing-sims/phase6/Packet.java 2006-09-27 11:34:42 UTC
(rev 10516)
+++ trunk/apps/load-balancing-sims/phase6/Packet.java 2006-09-27 16:26:43 UTC
(rev 10517)
@@ -35,6 +35,6 @@
public String toString()
{
- return new String (src + ":" + dest + ":" + seq);
+ return new String ("packet " + src + ":" + dest + ":" + seq);
}
}
Modified: trunk/apps/load-balancing-sims/phase6/RequestHandler.java
===================================================================
--- trunk/apps/load-balancing-sims/phase6/RequestHandler.java 2006-09-27
11:34:42 UTC (rev 10516)
+++ trunk/apps/load-balancing-sims/phase6/RequestHandler.java 2006-09-27
16:26:43 UTC (rev 10517)
@@ -4,8 +4,6 @@
abstract class RequestHandler extends MessageHandler implements EventTarget
{
- protected int state = STARTED; // State of search
-
public RequestHandler (Search s, Node node, Peer prev)
{
super (s, node, prev);
@@ -13,21 +11,21 @@
protected void handleAccepted (Accepted a)
{
- if (state != SENT) node.log (a + " out of order");
- state = ACCEPTED;
+ if (searchState != SENT) node.log (a + " out of order");
+ searchState = ACCEPTED;
// Wait 60 seconds for a reply to the search
Event.schedule (this, 60.0, SEARCH_TIMEOUT, next);
}
protected void handleRejectedLoop (RejectedLoop rl)
{
- if (state != SENT) node.log (rl + " out of order");
+ if (searchState != SENT) node.log (rl + " out of order");
forwardSearch();
}
protected void handleRouteNotFound (RouteNotFound rnf)
{
- if (state != ACCEPTED) node.log (rnf + " out of order");
+ if (searchState != ACCEPTED) node.log (rnf + " out of order");
if (rnf.htl < htl) htl = rnf.htl;
// Use the remaining htl to try another peer
forwardSearch();
@@ -35,7 +33,7 @@
protected void handleDataNotFound (DataNotFound dnf)
{
- if (state != ACCEPTED) node.log (dnf + " out of order");
+ if (searchState != ACCEPTED) node.log (dnf + " out of order");
if (prev == null) node.log (this + " failed");
else prev.sendMessage (dnf); // Forward the message
finish();
@@ -64,21 +62,20 @@
// Decrement the htl if the next node is not the closest so far
double target = Node.keyToLocation (key);
if (Node.distance (target, next.location)
- > Node.distance (target, closest)) {
+ > Node.distance (target, closest))
htl = node.decrementHtl (htl);
- node.log (this + " has htl " + htl);
- }
+ node.log (this + " has htl " + htl);
node.log ("forwarding " + this + " to " + next.address);
next.sendMessage (makeSearchMessage());
nexts.remove (next);
- state = SENT;
+ searchState = SENT;
// Wait 5 seconds for the next hop to accept the search
Event.schedule (this, 5.0, ACCEPTED_TIMEOUT, next);
}
protected void finish()
{
- state = COMPLETED;
+ searchState = COMPLETED;
node.removeMessageHandler (id);
}
@@ -87,7 +84,7 @@
protected void acceptedTimeout (Peer p)
{
if (p != next) return; // We've already moved on to another peer
- if (state != SENT) return;
+ if (searchState != SENT) return;
node.log (this + " accepted timeout waiting for " + p);
forwardSearch(); // Try another peer
}
@@ -95,7 +92,7 @@
protected void searchTimeout (Peer p)
{
if (p != next) return; // We've already moved on to another peer
- if (state != ACCEPTED) return;
+ if (searchState != ACCEPTED) return;
node.log (this + " search timeout waiting for " + p);
if (prev == null) node.log (this + " failed");
finish();
@@ -103,7 +100,7 @@
protected void transferTimeout (Peer p)
{
- if (state != TRANSFERRING) return;
+ if (searchState != TRANSFERRING) return;
node.log (this + " transfer timeout receiving from " + p);
if (prev == null) node.log (this + " failed");
finish();
Modified: trunk/apps/load-balancing-sims/phase6/Sim.java
===================================================================
--- trunk/apps/load-balancing-sims/phase6/Sim.java 2006-09-27 11:34:42 UTC
(rev 10516)
+++ trunk/apps/load-balancing-sims/phase6/Sim.java 2006-09-27 16:26:43 UTC
(rev 10517)
@@ -13,24 +13,20 @@
Network.reorder = true;
Network.lossRate = 0.001;
- Node n0 = new Node (txSpeed, rxSpeed);
- Node n1 = new Node (txSpeed, rxSpeed);
- Node n2 = new Node (txSpeed, rxSpeed);
- Node n3 = new Node (txSpeed, rxSpeed);
- Node n4 = new Node (txSpeed, rxSpeed);
+ Node[] nodes = new Node[20];
+ for (int i = 0; i < 20; i++)
+ nodes[i] = new Node (0.05 * i, txSpeed, rxSpeed);
+ for (int i = 0; i < 20; i++) {
+ nodes[i].connectBothWays (nodes[(i+1)%20], 0.1);
+ nodes[i].connectBothWays (nodes[(i+2)%20], 0.1);
+ }
- 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);
-
int key = Node.locationToKey (Math.random());
- Event.schedule (n0, 0.0, Node.GENERATE_SSK_INSERT, key);
- Event.schedule (n4, 30.0, Node.GENERATE_SSK_REQUEST, key);
+ Event.schedule (nodes[0], 0.0, Node.GENERATE_SSK_INSERT, key);
+ Event.schedule (nodes[10], 30.0, Node.GENERATE_SSK_REQUEST,key);
key = Node.locationToKey (Math.random());
- Event.schedule (n3, 60.0, Node.GENERATE_CHK_INSERT, key);
- Event.schedule (n1, 90.0, Node.GENERATE_CHK_REQUEST, key);
+ Event.schedule (nodes[5], 60.0, Node.GENERATE_CHK_INSERT, key);
+ Event.schedule (nodes[15], 90.0, Node.GENERATE_CHK_REQUEST,key);
// Run the simulation
Event.run();
Modified: trunk/apps/load-balancing-sims/phase6/SskInsertHandler.java
===================================================================
--- trunk/apps/load-balancing-sims/phase6/SskInsertHandler.java 2006-09-27
11:34:42 UTC (rev 10516)
+++ trunk/apps/load-balancing-sims/phase6/SskInsertHandler.java 2006-09-27
16:26:43 UTC (rev 10517)
@@ -5,7 +5,7 @@
class SskInsertHandler extends MessageHandler implements EventTarget
{
- private int state = STARTED; // State of search
+ private int searchState = STARTED; // searchState of search
private SskPubKey pubKey = null;
public SskInsertHandler (SskInsert i, Node node,
@@ -45,7 +45,7 @@
private void handleSskPubKey (SskPubKey pk)
{
- if (state != STARTED) node.log (pk + " out of order");
+ if (searchState != STARTED) node.log (pk + " out of order");
pubKey = pk;
node.cachePubKey (key);
node.cacheSsk (key);
@@ -55,8 +55,8 @@
private void handleSskAccepted (SskAccepted sa)
{
- if (state != SENT) node.log (sa + " out of order");
- state = ACCEPTED;
+ if (searchState != SENT) node.log (sa + " out of order");
+ searchState = ACCEPTED;
// Wait 60 seconds for a reply to the search
Event.schedule (this, 60.0, SEARCH_TIMEOUT, next);
// Send the public key if requested
@@ -65,13 +65,13 @@
private void handleRejectedLoop (RejectedLoop rl)
{
- if (state != SENT) node.log (rl + " out of order");
+ if (searchState != SENT) node.log (rl + " out of order");
forwardSearch();
}
private void handleRouteNotFound (RouteNotFound rnf)
{
- if (state != ACCEPTED) node.log (rnf + " out of order");
+ if (searchState != ACCEPTED) node.log (rnf + " out of order");
if (rnf.htl < htl) htl = rnf.htl;
// Use the remaining htl to try another peer
forwardSearch();
@@ -79,7 +79,7 @@
private void handleInsertReply (InsertReply ir)
{
- if (state != ACCEPTED) node.log (ir + " out of order");
+ if (searchState != ACCEPTED) node.log (ir + " out of order");
if (prev == null) node.log (this + " succeeded");
else prev.sendMessage (ir); // Forward the message
finish();
@@ -108,21 +108,20 @@
// Decrement the htl if the next node is not the closest so far
double target = Node.keyToLocation (key);
if (Node.distance (target, next.location)
- > Node.distance (target, closest)) {
+ > Node.distance (target, closest))
htl = node.decrementHtl (htl);
- node.log (this + " has htl " + htl);
- }
+ node.log (this + " has htl " + htl);
node.log ("forwarding " + this + " to " + next.address);
next.sendMessage (makeSearchMessage());
nexts.remove (next);
- state = SENT;
+ searchState = SENT;
// Wait 10 seconds for the next hop to accept the search
Event.schedule (this, 10.0, ACCEPTED_TIMEOUT, next);
}
private void finish()
{
- state = COMPLETED;
+ searchState = COMPLETED;
node.removeMessageHandler (id);
}
@@ -140,7 +139,7 @@
private void keyTimeout()
{
- if (state != STARTED) return;
+ if (searchState != STARTED) return;
node.log (this + " key timeout waiting for " + prev);
finish();
}
@@ -148,7 +147,7 @@
private void acceptedTimeout (Peer p)
{
if (p != next) return; // We've already moved on to another peer
- if (state != SENT) return;
+ if (searchState != SENT) return;
node.log (this + " accepted timeout waiting for " + p);
forwardSearch(); // Try another peer
}
@@ -156,7 +155,7 @@
private void searchTimeout (Peer p)
{
if (p != next) return; // We've already moved on to another peer
- if (state != ACCEPTED) return;
+ if (searchState != ACCEPTED) return;
node.log (this + " search timeout waiting for " + p);
if (prev == null) node.log (this + " failed");
finish();
Modified: trunk/apps/load-balancing-sims/phase6/SskRequestHandler.java
===================================================================
--- trunk/apps/load-balancing-sims/phase6/SskRequestHandler.java
2006-09-27 11:34:42 UTC (rev 10516)
+++ trunk/apps/load-balancing-sims/phase6/SskRequestHandler.java
2006-09-27 16:26:43 UTC (rev 10517)
@@ -40,7 +40,7 @@
private void handleSskDataFound (SskDataFound df)
{
- if (state != ACCEPTED) node.log (df + " out of order");
+ if (searchState != ACCEPTED) node.log (df + " out of order");
data = df;
if (pubKey == null) return; // Keep waiting
if (prev == null) node.log (this + " succeeded");
@@ -55,7 +55,7 @@
private void handleSskPubKey (SskPubKey pk)
{
- if (state != ACCEPTED) node.log (pk + " out of order");
+ if (searchState != ACCEPTED) node.log (pk + " out of order");
pubKey = pk;
if (data == null) return; // Keep waiting
if (prev == null) node.log (this + " succeeded");
Modified: trunk/apps/load-balancing-sims/phase6/messages/Search.java
===================================================================
--- trunk/apps/load-balancing-sims/phase6/messages/Search.java 2006-09-27
11:34:42 UTC (rev 10516)
+++ trunk/apps/load-balancing-sims/phase6/messages/Search.java 2006-09-27
16:26:43 UTC (rev 10517)
@@ -2,7 +2,7 @@
public class Search extends Message
{
- public final static int MAX_HTL = 5; // Maximum amount of backtracking
+ public final static int MAX_HTL = 2; // Maximum amount of backtracking
public final int key; // The target of the search
public double closest; // The closest location seen so far
