Author: mrogers
Date: 2006-10-01 14:23:41 +0000 (Sun, 01 Oct 2006)
New Revision: 10587
Modified:
trunk/apps/load-balancing-sims/phase6/ChkInsertHandler.java
trunk/apps/load-balancing-sims/phase6/ChkRequestHandler.java
trunk/apps/load-balancing-sims/phase6/Node.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:
Simple Kleinberg networks
Modified: trunk/apps/load-balancing-sims/phase6/ChkInsertHandler.java
===================================================================
--- trunk/apps/load-balancing-sims/phase6/ChkInsertHandler.java 2006-10-01
13:57:36 UTC (rev 10586)
+++ trunk/apps/load-balancing-sims/phase6/ChkInsertHandler.java 2006-10-01
14:23:41 UTC (rev 10587)
@@ -17,6 +17,12 @@
blocks = new Block[32];
}
+ public void start()
+ {
+ // Wait 10 seconds for the incoming transfer to start
+ Event.schedule (this, 10.0, DATA_TIMEOUT, null);
+ }
+
public void handleMessage (Message m, Peer src)
{
if (src == prev) {
Modified: trunk/apps/load-balancing-sims/phase6/ChkRequestHandler.java
===================================================================
--- trunk/apps/load-balancing-sims/phase6/ChkRequestHandler.java
2006-10-01 13:57:36 UTC (rev 10586)
+++ trunk/apps/load-balancing-sims/phase6/ChkRequestHandler.java
2006-10-01 14:23:41 UTC (rev 10587)
@@ -11,7 +11,6 @@
{
super (r, node, prev);
received = new boolean[32];
- forwardSearch();
}
public void handleMessage (Message m, Peer src)
Modified: trunk/apps/load-balancing-sims/phase6/Node.java
===================================================================
--- trunk/apps/load-balancing-sims/phase6/Node.java 2006-10-01 13:57:36 UTC
(rev 10586)
+++ trunk/apps/load-balancing-sims/phase6/Node.java 2006-10-01 14:23:41 UTC
(rev 10587)
@@ -49,16 +49,21 @@
bandwidth = new TokenBucket (BUCKET_RATE, BUCKET_SIZE);
}
- public void connect (Node n, double latency)
+ // Return true if a connection was added, false if already connected
+ public boolean connect (Node n, double latency)
{
+ if (n == this) return false;
+ if (peers.containsKey (n.net.address)) return false;
+ log ("adding peer " + n.net.address);
Peer p = new Peer (this, n.net.address, n.location, latency);
peers.put (n.net.address, p);
+ return true;
}
- public void connectBothWays (Node n, double latency)
+ public boolean connectBothWays (Node n, double latency)
{
- connect (n, latency);
- n.connect (this, latency);
+ if (connect (n, latency)) return n.connect (this, latency);
+ else return false;
}
// Calculate the circular distance between two locations
@@ -226,6 +231,7 @@
// Store the request handler and forward the search
ChkRequestHandler rh = new ChkRequestHandler (r, this, prev);
messageHandlers.put (r.id, rh);
+ rh.start();
}
private void handleChkInsert (ChkInsert i, Peer prev)
@@ -246,6 +252,7 @@
// Store the insert handler and wait for a DataInsert
ChkInsertHandler ih = new ChkInsertHandler (i, this, prev);
messageHandlers.put (i.id, ih);
+ ih.start();
}
private void handleSskRequest (SskRequest r, Peer prev)
@@ -298,6 +305,7 @@
// Store the request handler and forward the search
SskRequestHandler rh = new SskRequestHandler (r,this,prev,!pub);
messageHandlers.put (r.id, rh);
+ rh.start();
}
private void handleSskInsert (SskInsert i, Peer prev)
@@ -322,6 +330,7 @@
// Store the insert handler and possibly wait for the pub key
SskInsertHandler ih = new SskInsertHandler (i,this,prev,!pub);
messageHandlers.put (i.id, ih);
+ ih.start();
}
public void removeMessageHandler (int id)
Modified: trunk/apps/load-balancing-sims/phase6/RequestHandler.java
===================================================================
--- trunk/apps/load-balancing-sims/phase6/RequestHandler.java 2006-10-01
13:57:36 UTC (rev 10586)
+++ trunk/apps/load-balancing-sims/phase6/RequestHandler.java 2006-10-01
14:23:41 UTC (rev 10587)
@@ -9,6 +9,11 @@
super (s, node, prev);
}
+ public void start()
+ {
+ forwardSearch();
+ }
+
protected void handleAccepted (Accepted a)
{
if (searchState != SENT) node.log (a + " out of order");
Modified: trunk/apps/load-balancing-sims/phase6/Sim.java
===================================================================
--- trunk/apps/load-balancing-sims/phase6/Sim.java 2006-10-01 13:57:36 UTC
(rev 10586)
+++ trunk/apps/load-balancing-sims/phase6/Sim.java 2006-10-01 14:23:41 UTC
(rev 10587)
@@ -1,34 +1,41 @@
-// Interesting parameters to play with: txSpeed and rxSpeed, retransmission
-// timeout, window sizes, AIMD increase and decrease (Peer.java), queue sizes
-// (NetworkInterface.java), packet size (Packet.java).
-
class Sim
{
+ public static Node[] makeKleinbergNetwork (int n, int k, double speed)
+ {
+ Node[] nodes = new Node[n];
+ for (int i = 0; i < n; i++)
+ nodes[i] = new Node (1.0 / n * i, speed, speed);
+ int m = 0; // Number of directed edges
+ while (m < n * k) {
+ Node src = nodes[(int)(Math.random() * n)];
+ Node dest = nodes[(int)(Math.random() * n)];
+ double d = Node.distance (src.location, dest.location);
+ if (Math.random() * 0.5 < 0.5 - d)
+ if (src.connectBothWays (dest, 0.1)) m += 2;
+ }
+ return nodes;
+ }
+
public static void main (String[] args)
{
- double txSpeed = 20000, rxSpeed = 20000; // Bytes per second
+ double speed = 20000; // Tx and Rx speed, bytes per second
+
// rxSpeed = Math.exp (rand.nextGaussian() + 11.74);
// txSpeed = rxSpeed / 5.0;
Network.reorder = true;
Network.lossRate = 0.001;
- 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);
- }
+ Node[] nodes = makeKleinbergNetwork (100, 4, speed);
int key = Node.locationToKey (Math.random());
Event.schedule (nodes[0], 0.0,
Node.GENERATE_SSK_INSERT, key);
- Event.schedule (nodes[5], 30.0,
+ Event.schedule (nodes[25], 30.0,
Node.GENERATE_SSK_REQUEST, key);
- Event.schedule (nodes[10], 60.0,
+ Event.schedule (nodes[50], 60.0,
Node.GENERATE_SSK_COLLISION, key);
- Event.schedule (nodes[15], 90.0,
+ Event.schedule (nodes[75], 90.0,
Node.GENERATE_SSK_REQUEST, key);
// Run the simulation
Modified: trunk/apps/load-balancing-sims/phase6/SskInsertHandler.java
===================================================================
--- trunk/apps/load-balancing-sims/phase6/SskInsertHandler.java 2006-10-01
13:57:36 UTC (rev 10586)
+++ trunk/apps/load-balancing-sims/phase6/SskInsertHandler.java 2006-10-01
14:23:41 UTC (rev 10587)
@@ -14,10 +14,16 @@
{
super (i, node, prev);
data = i.data;
- // Wait 10 seconds for the previous hop to send the public key
- if (needPubKey) Event.schedule (this, 10.0, KEY_TIMEOUT, null);
+ if (!needPubKey) pubKey = new SskPubKey (id, key);
+ }
+
+ public void start()
+ {
+ if (pubKey == null) {
+ // Wait 10 seconds for the previous hop to send the key
+ Event.schedule (this, 10.0, KEY_TIMEOUT, null);
+ }
else {
- pubKey = new SskPubKey (id, key);
checkCollision();
forwardSearch();
}
Modified: trunk/apps/load-balancing-sims/phase6/SskRequestHandler.java
===================================================================
--- trunk/apps/load-balancing-sims/phase6/SskRequestHandler.java
2006-10-01 13:57:36 UTC (rev 10586)
+++ trunk/apps/load-balancing-sims/phase6/SskRequestHandler.java
2006-10-01 14:23:41 UTC (rev 10587)
@@ -14,7 +14,6 @@
super (r, node, prev);
this.needPubKey = needPubKey;
if (!needPubKey) pubKey = new SskPubKey (id, key);
- forwardSearch();
}
public void handleMessage (Message m, Peer src)
Modified: trunk/apps/load-balancing-sims/phase6/messages/Search.java
===================================================================
--- trunk/apps/load-balancing-sims/phase6/messages/Search.java 2006-10-01
13:57:36 UTC (rev 10586)
+++ trunk/apps/load-balancing-sims/phase6/messages/Search.java 2006-10-01
14:23:41 UTC (rev 10587)
@@ -2,7 +2,7 @@
public class Search extends Message
{
- public final static int MAX_HTL = 2; // Maximum amount of backtracking
+ public final static int MAX_HTL = 10; // Maximum amount of backtracking
public final int key; // The target of the search
public double closest; // The closest location seen so far
