Author: mrogers
Date: 2006-10-08 21:19:49 +0000 (Sun, 08 Oct 2006)
New Revision: 10653
Added:
trunk/apps/load-balancing-sims/kleinberg-attack/
trunk/apps/load-balancing-sims/kleinberg-attack/Node.java
trunk/apps/load-balancing-sims/kleinberg-attack/Sim.java
Modified:
trunk/apps/load-balancing-sims/routing.txt
Log:
Some quick and dirty simulations of random and targetted node removal in
Kleinberg networks
Added: trunk/apps/load-balancing-sims/kleinberg-attack/Node.java
===================================================================
--- trunk/apps/load-balancing-sims/kleinberg-attack/Node.java 2006-10-08
20:49:08 UTC (rev 10652)
+++ trunk/apps/load-balancing-sims/kleinberg-attack/Node.java 2006-10-08
21:19:49 UTC (rev 10653)
@@ -0,0 +1,73 @@
+import java.util.HashSet;
+
+class Node
+{
+ private HashSet<Node> neighbours;
+ private double location;
+
+ public Node (double location)
+ {
+ neighbours = new HashSet<Node>();
+ this.location = location;
+ }
+
+ public void connect (Node n)
+ {
+ if (n == this || neighbours.contains (n)) return;
+ neighbours.add (n);
+ }
+
+ public void disconnect (Node n)
+ {
+ neighbours.remove (this);
+ }
+
+ public void die()
+ {
+ for (Node n : neighbours) n.disconnect (this);
+ neighbours.clear();
+ }
+
+ // Return the length of the longest link
+ public double longestDistance()
+ {
+ double best = 0.0;
+ for (Node n : neighbours) {
+ double d = distance (location, n.location);
+ if (d > best) best = d;
+ }
+ return best;
+ }
+
+ // Return the total length of all links
+ public double totalDistance()
+ {
+ double d = 0.0;
+ for (Node n : neighbours) d += distance (location, n.location);
+ return d;
+ }
+
+ public Node route (Node dest)
+ {
+ if (dest == this) return null;
+ Node bestNeighbour = null;
+ double bestDistance = Double.POSITIVE_INFINITY;
+ for (Node n : neighbours) {
+ double d = distance (n.location, dest.location);
+ if (d < bestDistance) {
+ bestNeighbour = n;
+ bestDistance = d;
+ }
+ }
+ if (bestDistance < distance (location, dest.location))
+ return bestNeighbour;
+ else return null;
+ }
+
+ // Return the circular distance between two locations
+ public static double distance (double a, double b)
+ {
+ if (a > b) return Math.min (a - b, b - a + 1.0);
+ else return Math.min (b - a, a - b + 1.0);
+ }
+}
Added: trunk/apps/load-balancing-sims/kleinberg-attack/Sim.java
===================================================================
--- trunk/apps/load-balancing-sims/kleinberg-attack/Sim.java 2006-10-08
20:49:08 UTC (rev 10652)
+++ trunk/apps/load-balancing-sims/kleinberg-attack/Sim.java 2006-10-08
21:19:49 UTC (rev 10653)
@@ -0,0 +1,109 @@
+class Sim
+{
+ private final static int NODES = 1000;
+ private final static int DEGREE = 20;
+ private final static int DEATHS = 30;
+ private final static int TRIALS = 1000;
+
+ private Node[] nodes;
+
+ public Sim()
+ {
+ nodes = new Node[NODES];
+ for (int i = 0; i < NODES; i++)
+ nodes[i] = new Node (1.0 / NODES * i);
+
+ // Calculate the normalising constant
+ double norm = 0.0;
+ for (int i = 1; i < NODES; i++)
+ norm += 1.0 / latticeDistance (0, i);
+
+ // Add DEGREE shortcuts per node, randomly with replacement
+ double outDegree = DEGREE * 0.5;
+ for (int i = 0; i < NODES; i++) {
+ for (int j = 0; j < NODES; j++) {
+ if (i == j) continue;
+ double p = 1.0 / latticeDistance (i, j) / norm;
+ for (int k = 0; k < outDegree; k++) {
+ if (Math.random() < p) {
+ nodes[i].connect (nodes[j]);
+ nodes[j].connect (nodes[i]);
+ break;
+ }
+ }
+ }
+ }
+ }
+
+ // Remove a randomly chosen node from the network
+ private void killRandomNode()
+ {
+ int i = (int) (Math.random() * NODES);
+ while (nodes[i] == null) i = (int) (Math.random() * NODES);
+ nodes[i].die();
+ nodes[i] = null;
+ }
+
+ // Remove the node with the longest links from the network
+ private void killBestNode()
+ {
+ int bestIndex = 0;
+ double bestDistance = Double.NEGATIVE_INFINITY;
+ for (int i = 0; i < NODES; i++) {
+ if (nodes[i] == null) continue;
+ double d = nodes[i].totalDistance();
+ // double d = nodes[i].longestDistance();
+ if (d > bestDistance) {
+ bestIndex = i;
+ bestDistance = d;
+ }
+ }
+ nodes[bestIndex].die();
+ nodes[bestIndex] = null;
+ }
+
+ // Route a message from a random source to a random destination, without
+ // backtracking. If the message arrives, return the number of hops. If
+ // the message does not arrive, return zero minus the number of hops.
+ private int route()
+ {
+ Node n = null, dest = null;
+ while (n == null) n = nodes[(int) (Math.random() * NODES)];
+ while (dest == null) dest = nodes[(int) (Math.random() *NODES)];
+ int hops;
+ for (hops = 0; n != dest && n != null; hops++)
+ n = n.route (dest);
+ if (n == null) return -hops;
+ else return hops;
+ }
+
+ // Return the Kleinberg 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);
+ }
+
+ public static void main (String[] args)
+ {
+ double successes = 0.0;
+ double successHops = 0.0;
+ double failureHops = 0.0;
+ Sim s = new Sim();
+
+ for (int i = 0; i < DEATHS; i++) s.killBestNode();
+ // for (int i = 0; i < DEATHS; i++) s.killRandomNode();
+
+ for (int i = 0; i < TRIALS; i++) {
+ int hops = s.route();
+ if (hops >= 0) {
+ successes++;
+ successHops += hops;
+ }
+ else failureHops -= hops;
+ }
+ System.out.println ("success rate " + (successes/TRIALS));
+ System.out.println ("success hops " + (successHops/successes));
+ System.out.println ("failure hops " +
(failureHops/(TRIALS-successes)));
+ }
+}
Modified: trunk/apps/load-balancing-sims/routing.txt
===================================================================
--- trunk/apps/load-balancing-sims/routing.txt 2006-10-08 20:49:08 UTC (rev
10652)
+++ trunk/apps/load-balancing-sims/routing.txt 2006-10-08 21:19:49 UTC (rev
10653)
@@ -16,7 +16,7 @@
If this is the closest node so far, update closest location and reset htl
Send Accepted
If data is in store or cache:
- If key is an SSK, send DataFound and SSKPubKey if requested, return
+ If key is an SSK, send SSKDataFound and SSKPubKey if requested, return
If key is a CHK, start a new BlockTransmitter and return
If there's a transferring RequestSender with the same key, coalesce
Otherwise if htl==0, send DataNotFound and return
@@ -134,7 +134,7 @@
Wait 60 seconds for DataNotFound, RouteNotFound, RejectedOverload, SSKPubKey,
CHKDataFound or SSKDataFound
If peer disconnects, try another peer
If wait times out, back off and return TIMED_OUT
- If DataNotFound, return data not found
+ If DataNotFound, return DATA_NOT_FOUND
If RouteNotFound, let htl=min(htl,newHtl) and try another peer
If local RejectedOverload, back off and try another peer
If non-local RejectedOverload, forward it
