Author: mrogers
Date: 2006-10-04 20:02:47 +0000 (Wed, 04 Oct 2006)
New Revision: 10600
Modified:
trunk/apps/load-balancing-sims/phase6/MessageHandler.java
trunk/apps/load-balancing-sims/phase6/Sim.java
trunk/apps/load-balancing-sims/phase6/messages/Message.java
Log:
Slightly less broken Kleinberg networks (thanks Toad)
Modified: trunk/apps/load-balancing-sims/phase6/MessageHandler.java
===================================================================
--- trunk/apps/load-balancing-sims/phase6/MessageHandler.java 2006-10-04
18:41:49 UTC (rev 10599)
+++ trunk/apps/load-balancing-sims/phase6/MessageHandler.java 2006-10-04
20:02:47 UTC (rev 10600)
@@ -38,7 +38,7 @@
double target = Node.keyToLocation (key);
if (Node.distance (target, node.location)
< Node.distance (target, closest)) {
- node.log ("resetting htl of " + this);
+ node.log ("resetting htl of " + this); // FIXME
closest = node.location;
htl = Search.MAX_HTL;
}
Modified: trunk/apps/load-balancing-sims/phase6/Sim.java
===================================================================
--- trunk/apps/load-balancing-sims/phase6/Sim.java 2006-10-04 18:41:49 UTC
(rev 10599)
+++ trunk/apps/load-balancing-sims/phase6/Sim.java 2006-10-04 20:02:47 UTC
(rev 10600)
@@ -1,44 +1,68 @@
class Sim
{
- public static Node[] makeKleinbergNetwork (int n, int k, double speed)
+ private final int NODES = 100; // Number of nodes
+ private final int DEGREE = 4; // Average degree
+ private final double SPEED = 20000; // Bytes per second
+ private final double LATENCY = 0.1; // Seconds
+ private Node[] nodes;
+
+ public Sim()
{
- 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 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 = makeKleinbergNetwork (100, 4, speed);
+ // Create the nodes
+ nodes = new Node[NODES];
+ for (int i = 0; i < NODES; i++)
+ nodes[i] = new Node (1.0 / NODES * i, SPEED, SPEED);
+ // Connect the nodes
+ makeKleinbergNetwork();
int key = Node.locationToKey (Math.random());
Event.schedule (nodes[0], 0.0,
Node.GENERATE_SSK_INSERT, key);
- Event.schedule (nodes[25], 30.0,
+ Event.schedule (nodes[NODES/4], 30.0,
Node.GENERATE_SSK_REQUEST, key);
- Event.schedule (nodes[50], 60.0,
+ Event.schedule (nodes[NODES/2], 60.0,
Node.GENERATE_SSK_COLLISION, key);
- Event.schedule (nodes[75], 90.0,
+ Event.schedule (nodes[3*NODES/4], 90.0,
Node.GENERATE_SSK_REQUEST, key);
// Run the simulation
Event.run();
}
+
+ // Return the lattice distance between a and b
+ private int latticeDistance (int a, int b)
+ {
+ if (a > b) return Math.min (a - b, b - a + NODES);
+ else return Math.min (b - a, a - b + NODES);
+ }
+
+ private void makeKleinbergNetwork()
+ {
+ // Add exactly DEGREE/2 outgoing edges to each node
+ for (int i = 0; i < NODES; i++) {
+ // Calculate the normalising constant
+ double c = 0.0;
+ for (int j = 0; j < NODES; j++) {
+ if (i == j) continue;
+ c += 1.0 / latticeDistance (i, j);
+ }
+ // Add the outgoing edges
+ int deg = 0;
+ for (int j = 0; deg < DEGREE/2; j = (j+1) % NODES) {
+ if (i == j) continue;
+ double prob = 1.0 / latticeDistance (i, j) / c;
+ if (Math.random() < prob)
+ if (nodes[i].connectBothWays
+ (nodes[j], LATENCY)) deg++;
+ }
+ }
+ }
+
+ public static void main (String[] args)
+ {
+ new Sim();
+ }
}
Modified: trunk/apps/load-balancing-sims/phase6/messages/Message.java
===================================================================
--- trunk/apps/load-balancing-sims/phase6/messages/Message.java 2006-10-04
18:41:49 UTC (rev 10599)
+++ trunk/apps/load-balancing-sims/phase6/messages/Message.java 2006-10-04
20:02:47 UTC (rev 10600)
@@ -6,7 +6,7 @@
{
public final static int HEADER_SIZE = 12; // Bytes, including unique ID
public final static int KEY_SIZE = 32; // Size of a routing key, bytes
- public final static int PUB_KEY_SIZE = 256; // Size of a pub key, bytes
+ public final static int PUB_KEY_SIZE = 1024; // Size of a pub key, bytes
public final static int DATA_SIZE = 1024; // Size of a data block, bytes
public static int nextId = 0; // Each request and insert has a unique ID
