Author: vive
Date: 2007-08-20 17:58:17 +0000 (Mon, 20 Aug 2007)
New Revision: 14808
Added:
trunk/apps/load-balancing-sims/phase7/sim/SimpleEstimator.java
trunk/apps/load-balancing-sims/phase7/sim/SimpleLink.java
trunk/apps/load-balancing-sims/phase7/sim/SimplePeer.java
Modified:
trunk/apps/load-balancing-sims/phase7/sim/SimpleGraph.java
trunk/apps/load-balancing-sims/phase7/sim/SimpleNode.java
trunk/apps/load-balancing-sims/phase7/sim/SimpleQuery.java
Log:
Updates on the simple model...
Added: trunk/apps/load-balancing-sims/phase7/sim/SimpleEstimator.java
===================================================================
--- trunk/apps/load-balancing-sims/phase7/sim/SimpleEstimator.java
(rev 0)
+++ trunk/apps/load-balancing-sims/phase7/sim/SimpleEstimator.java
2007-08-20 17:58:17 UTC (rev 14808)
@@ -0,0 +1,81 @@
+package sim;
+
+class SimpleEstimator {
+
+ double[] length_times; // Map from [0,1]->[0,maxt]
+ static double alpha = 0.1; // Parameter for exponential moving average
+
+ /*
+ * @resolution: resolution on estimation in keyspace
+ */
+ public SimpleEstimator(int resolution) {
+ length_times = new double[resolution];
+ }
+
+ /*
+ * update estimator with an observed roundtrip time for a distance
+ *
+ * @dist: distance for service
+ * @rtt: observed roundtrip time when using this estimator
+ */
+ public void update(double dist,double rtt) {
+ // int i = (int) Math.floor(length_times.length * 2*dist);
+ int i = (int) Math.floor(length_times.length*dist);
+
+ if(length_times[i] == 0) {
+ length_times[i] = rtt;
+ } else {
+ length_times[i] = rtt*alpha + length_times[i]*(1-alpha);
+ }
+ }
+
+ /*
+ * estimate required time based on previously seen performance,
+ * simple linear average when no performance seen
+ *
+ * @dist: distance we wonder about
+ */
+ public double estimate(double dist) {
+ // int i = (int) Math.floor(length_times.length * 2*dist);
+ int i = (int) Math.floor(length_times.length*dist);
+
+ if(i==length_times.length) // Boundary node, farthest away
+ i--;
+
+ // Direct estimation?
+ if (length_times[i] != 0) {
+ return length_times[i];
+ } else {
+
+ if((i==0) || (i==length_times.length-1)) {
+ return 0;
+ } else {
+ // Try interferring estimation from farther and nearer
+ double lower=0,upper=0;
+
+ for (int j=i-1; j>0; j--) {
+ if (length_times[j]>0) {
+ lower = length_times[j];
+ break;
+ }
+ }
+
+ for (int j=i+1; j<(length_times.length-1); j++) {
+ if (length_times[j]>0) {
+ upper = length_times[j];
+ break;
+ }
+ }
+
+ if ((lower==0)||(upper==0)) {
+ return 0;
+ } else {
+ return ((lower+upper)/2);
+ }
+
+ }
+ }
+
+ }
+
+}
Modified: trunk/apps/load-balancing-sims/phase7/sim/SimpleGraph.java
===================================================================
--- trunk/apps/load-balancing-sims/phase7/sim/SimpleGraph.java 2007-08-20
17:00:45 UTC (rev 14807)
+++ trunk/apps/load-balancing-sims/phase7/sim/SimpleGraph.java 2007-08-20
17:58:17 UTC (rev 14808)
@@ -1,37 +1,255 @@
-/*
- * Graph of SimpleNodes
- */
+//
+// The graph holding the simulation network topology
+// Takes care of routing, position randomization, also some node configuration
+//
package sim;
-
import java.util.Random;
+import java.util.Vector;
+import java.util.LinkedList;
class SimpleGraph {
- SimpleNode[] nodes;
- private Random rand;
-
- public SimpleGraph(int n) {
- nodes = new SimpleNode[n];
+ // SimpleNode[] nodes;
+ Vector<SimpleNode> nodes; // Growable, but array should be more
efficient
+ private static Random rand = new Random(System.currentTimeMillis() %
10000);
+ private boolean delays = false; // If to vary delays by default
+
+ /*
+ * @n: number of nodes
+ * @estsize: size of estimation table
+ * @delays: if to sample delays between nodes, or to use unity
+ */
+ public SimpleGraph(int n, int estsize, boolean delays) {
+ this.delays = delays;
+ // nodes = new SimpleNode[n];
+ nodes = new Vector<SimpleNode>();
for (int i=0; i<n; i++) {
- nodes[i] = new SimpleNode((double)i/n);
+ double location = (double)i/n;
+ nodes.add(new SimpleNode(location, estsize));
}
- rand = new Random((int) (System.currentTimeMillis() % 10000));
}
/*
+ * To enable opennet for all nodes.
+ * @opennet_maxpeers: max peers that a node wants to take on opennet
+ */
+ public void enableOpennet(int opennet_maxpeers) {
+ for (SimpleNode n: nodes) {
+ n.enableOpennet(opennet_maxpeers);
+ }
+ }
+
+ /*
+ * To disable opennet for all nodes.
+ */
+ public void disableOpennet() {
+ for (SimpleNode n: nodes) {
+ n.disableOpennet();
+ }
+ }
+
+ /*
+ * Make a route in the network (possibly affecting opennet if enabled)
+ * Peers chosen uniformly at random
+ *
+ * @htl: Hops to Live
+ */
+ public void randomroute(int htl) {
+ SimpleNode src = nodes.get(rand.nextInt(nodes.size()));
+ SimpleNode dst = nodes.get(rand.nextInt(nodes.size()));
+ LinkedList<SimpleQuery> route = src.route(new
SimpleQuery(src,null,dst,null,SimpleQuery.FORWARD,htl,false));
+ unlock(route);
+ }
+
+ /*
+ * Unlock simple trackkeeping of route participation
+ *
+ * @route: The route with all parcitipants
+ */
+
+ public void unlock(LinkedList<SimpleQuery> route) {
+ for (SimpleQuery rq: route) {
+ rq.source.busy = false;
+ }
+ }
+
+ /*
+ * Randomly assign new locations in [0,1) to nodes
+ */
+ public void randLocations() {
+ for (SimpleNode n: nodes) {
+ n.setLocation(rand.nextDouble());
+ }
+ }
+
+ /*
+ * Randomly shuffle the existing positions
+ */
+ public void shuffleLocations() {
+ for(int j=0; j<nodes.size(); j++) {
+ int nn = rand.nextInt(nodes.size());
+ SimpleNode nj = nodes.get(j);
+ SimpleNode swapto = nodes.get(nn);
+
+ double tmp = nj.getLocation();
+ nj.setLocation(swapto.getLocation());
+ swapto.setLocation(tmp);
+
+ nodes.set(j,swapto);
+ nodes.set(nn,nj);
+ }
+ }
+
+ /*
+ * Generate a delay of 0.1 + a harmonic (1/x) distribution and with mean 1.
+ *
+ * fixme: try a Gaussian with mean 1? (restricted downwards by a min value)
+ */
+ public static double sampleDelay() {
+ double delaymin = 0.1;
+ // return (delaymin + 0.9*0.1*Math.pow(37.5,rand.nextDouble()));
+ return (delaymin + 0.9*0.0001*Math.pow(119000,rand.nextDouble()));
+ //return ((rand.nextDouble()<0.5)?0.1:1.9);
+ // return ((rand.nextDouble()<0.5)?0.5:1.5);
+ }
+
+ /*
+ * Patch a node into Kleinbergs original model
+ * Warning: this does NOT give a Kleinberg model, dont use this for
growing networks
+ * Used to evaluate quick churn into the darknet model.
+ *
+ * @avgdeg: resulting average degree of the nodes
+ * @directed: if to use directed edges
+ * @local: if to add nearest-neighbor connections
+ * @inconst: if to keep the *indegree* constant (fixme)
+ *
+ */
+ public SimpleNode insertNode(double avgdeg, boolean directed, boolean
local, boolean inconst) {
+
+ int i = rand.nextInt(nodes.size());
+ SimpleNode newnode = new SimpleNode(rand.nextDouble(),0);
+ nodes.insertElementAt(newnode,i);
+
+ double degree,delay;
+ if(directed) {
+ degree = avgdeg;
+ } else {
+ degree = avgdeg/2;
+ }
+
+ SimpleNode src = nodes.get(i);
+ if (local) {
+ SimpleNode dst;
+ SimpleLink link;
+
+ if(delays)
+ delay = sampleDelay();
+ else
+ delay = 1;
+ dst = nodes.get((i+1)%nodes.size());
+ link = new SimpleLink(src,dst,delay);
+ src.connect(dst,link,SimplePeer.t_DARKNET);
+ dst.connect(src,link,SimplePeer.t_DARKNET);
+
+ if(delays)
+ delay = sampleDelay();
+ else
+ delay = 1;
+ dst = nodes.get((i-1)%nodes.size());
+ link = new SimpleLink(src,dst,delay);
+ src.connect(dst,link,SimplePeer.t_DARKNET);
+ dst.connect(src,link,SimplePeer.t_DARKNET);
+ }
+
+ for(int j=0; j<degree; j++) {
+ boolean found = false;
+ while(!found) {
+ double r = rand.nextFloat();
+ int d = (int) Math.floor (Math.exp (r*Math.log
(nodes.size()/2.0)));
+ int destpos;
+
+ if (rand.nextFloat()<0.5) {
+ destpos = i - d;
+ } else {
+ destpos = i + d;
+ }
+
+ if (destpos>=nodes.size()) {
+ destpos = destpos - nodes.size();
+ } else if (destpos<0) {
+ destpos = destpos + nodes.size();
+ }
+
+ SimpleNode dst = nodes.get(destpos);
+
+ if(delays)
+ delay = sampleDelay();
+ else
+ delay = 1;
+
+ if (directed) {
+ if (inconst) {
+ if (!dst.hasNeighbor(src)) {
+ found = true;
+ SimpleLink sl = new SimpleLink(src,dst,delay);
+ dst.connect(src,sl,SimplePeer.t_DARKNET);
+ }
+ } else {
+ if (!src.hasNeighbor(dst)) {
+ found = true;
+ SimpleLink sl = new SimpleLink(dst,src,delay);
+ src.connect(dst,sl,SimplePeer.t_DARKNET);
+ }
+ }
+ } else {
+ if (!src.hasNeighbor(dst) && !dst.hasNeighbor(src)) {
+ found = true;
+ SimpleLink sl = new SimpleLink(src,dst,delay);
+ src.connect(dst,sl,SimplePeer.t_DARKNET);
+ dst.connect(src,sl,SimplePeer.t_DARKNET);
+ }
+ }
+ }
+ }
+
+ return newnode;
+ }
+
+ /*
+ * Remove a node from the graph
+ *
+ * fixme: also remove load stats/counters
+ * @n: node to remove
+ */
+ public void removeNode (SimpleNode n) {
+
+ Vector<SimpleNode> toDisconnect = new Vector<SimpleNode>();
+
+ for (SimplePeer peer: n.neighbors) {
+ peer.n.disconnect(n);
+ toDisconnect.add(peer.n);
+ }
+
+ for (SimpleNode disconnecter: toDisconnect) {
+ n.disconnect(disconnecter);
+ }
+
+ nodes.removeElement(n);
+ }
+
+ /*
* Generating a Kleinberg small-world graph with shortcuts proportional to
1/d
*
* @avgdeg: average degree of nodes
* @directed: if to have directed edges
* @local: if to have local edges (to nearest-neighbors in the lattice)
* @inconst: if to have a constant number of indegree edges (when using
directed edges),
- * else use constant outdegree
+ * otherwise use constant outdegree (default)
*/
-
public void CreateKleinbergGraph(double avgdeg, boolean directed, boolean
local, boolean inconst) {
- double degree;
+ double degree,delay;
if(directed) {
degree = avgdeg;
} else {
@@ -39,28 +257,30 @@
}
if(local) {
- for(int i=0; i<nodes.length; i++) {
- SimpleNode src = nodes[i];
- SimpleNode dst = nodes[(i+1)%nodes.length];
- src.connect(dst);
- dst.connect(src);
+ for(int i=0; i<nodes.size(); i++) {
+ if(delays)
+ delay = sampleDelay();
+ else
+ delay = 1;
+
+ SimpleNode src = nodes.get(i);
+ SimpleNode dst = nodes.get((i+1)%nodes.size());
+ SimpleLink link = new SimpleLink(src,dst,delay);
+ src.connect(dst,link,SimplePeer.t_DARKNET);
+ dst.connect(src,link,SimplePeer.t_DARKNET);
}
}
System.err.println("Giving each node " + degree + " shortcuts" + (local
? " and nearest-neighbor connections " : "") + " (average degree="+ (local ?
(avgdeg+2) : avgdeg) +")");
- for(int i=0; i<nodes.length; i++) {
- SimpleNode src = nodes[i];
-
+ for(int i=0; i<nodes.size(); i++) {
+ SimpleNode src = nodes.get(i);
for(int j=0; j<degree; j++) {
boolean found = false;
while(!found) {
-
- // assuming nodes are equally spaced out in [0,1] we can
use integers as offsets
- // fixme: option for sampling directly in [0,1]
double r = rand.nextFloat();
- int d = (int) Math.floor (Math.exp (r*Math.log
(nodes.length/2.0)));
+ int d = (int) Math.floor (Math.exp (r*Math.log
(nodes.size()/2.0)));
int destpos;
if (rand.nextFloat()<0.5) {
@@ -69,40 +289,174 @@
destpos = i + d;
}
- if (destpos>=nodes.length) {
- destpos = destpos - nodes.length;
+ if (destpos>=nodes.size()) {
+ destpos = destpos - nodes.size();
} else if (destpos<0) {
- destpos = destpos + nodes.length;
+ destpos = destpos + nodes.size();
}
- SimpleNode dst = nodes[destpos];
+ SimpleNode dst = nodes.get(destpos);
+ if(delays)
+ delay = sampleDelay();
+ else
+ delay = 1;
+
if (directed) {
if (inconst) {
if (!dst.hasNeighbor(src)) {
found = true;
- dst.connect(src);
+ SimpleLink sl = new SimpleLink(src,dst,delay);
+ dst.connect(src,sl,SimplePeer.t_DARKNET);
}
} else {
if (!src.hasNeighbor(dst)) {
found = true;
- src.connect(dst);
+ SimpleLink sl = new SimpleLink(dst,src,delay);
+ src.connect(dst,sl,SimplePeer.t_DARKNET);
}
}
} else {
if (!src.hasNeighbor(dst) && !dst.hasNeighbor(src)) {
found = true;
- src.connect(dst);
- dst.connect(src);
+ SimpleLink sl = new SimpleLink(src,dst,delay);
+ src.connect(dst,sl,SimplePeer.t_DARKNET);
+ dst.connect(src,sl,SimplePeer.t_DARKNET);
}
- }
-
-
+ }
}
+ }
+ }
+ }
+
+
+ /*
+ * Evaluate swap directly without no delay
+ *
+ * @randsteps: steps for random walk from source to dest (0=uniform
selection)
+ * @randomize_interval: if to enable position randomization with a period
of swaps
+ */
+ public void tryswap(int randsteps, int randomize_interval) {
+
+ int i,j;
+ SimpleNode na=null,nb=null;
+
+ if (randsteps==0) {
+ do {
+ i = rand.nextInt(nodes.size());
+ j = rand.nextInt(nodes.size());
+ } while (i==j);
+
+ na = nodes.get(i);
+ nb = nodes.get(j);
+ } else {
+ // Fixme: let the node initialize the request itself
+ do {
+ i = rand.nextInt(nodes.size());
+ na = nodes.get(i);
+ int s = randsteps;
+ nb = na;
+ while (s > 0) {
+ nb = nb.neighbors.get(rand.nextInt(nb.neighbors.size())).n;
+ s--;
+ }
+ } while (na==nb);
+
+ }
+
+ if (randomize_interval > 0) {
+ if (na.rand_interval > 0) {
+ na.rand_interval--;
+ } else {
+ na.setLocation(rand.nextDouble());
+ na.rand_interval = na.rand_interval + randomize_interval;
}
+ }
+ double p =
Math.exp(na.logDists(na.getLocation())+nb.logDists(nb.getLocation())-na.logDists(nb.getLocation())-nb.logDists(na.getLocation()));
+
+ // Evaluate step
+ if (rand.nextDouble()<p) {
+ double tmp = na.getLocation();
+ na.setLocation(nb.getLocation());
+ nb.setLocation(tmp);
}
}
+ /*
+ * Print nodes and edges between them
+ *
+ * @stdout: if stdout!= 0 we print to stdout, if stdout==0 print to stderr
+ */
+ public void printNodes(int stdout) {
+ for(int i=0; i<nodes.size(); i++) {
+ int start = (int)
Math.round(nodes.size()*nodes.get(i).getLocation());
+ Vector<SimplePeer> neighbors = nodes.get(i).neighbors;
+ for (SimplePeer peer: nodes.get(i).neighbors) {
+ int stop = (int) Math.round(nodes.size()*peer.n.getLocation());
+
+ if(stdout==1) {
+ System.out.println(start + "\t" + stop);
+ } else {
+ System.err.println(start + "\t" + stop);
+ }
+ }
+ }
+ }
+
+ /*
+ * Print only locations for nodes (in topology order)
+ *
+ * @stdout: if stdout!= 0 we print to stdout, if stdout==0 print to stderr
+ */
+ public void printLocations(int stdout) {
+ for(SimpleNode n: nodes) {
+ ((stdout==0) ? System.err : System.out).println(n.getLocation());
+ }
+ }
+
+ /*
+ * Enable all nodes for learning route delays
+ */
+ public void learning() {
+ for (SimpleNode n: nodes) {
+ n.learning = true;
+ }
+ }
+
+ /*
+ * Disable learning of route delays
+ */
+ public void unlearning() {
+ for (SimpleNode n: nodes) {
+ n.learning = false;
+ }
+ }
+
+ /*
+ * Use delays for generating edges
+ */
+ public void edgedelays() {
+ this.delays = true;
+ }
+
+ /*
+ * Enable delay usage for nodes in routing
+ */
+ public void usedelays() {
+ for (SimpleNode n: nodes) {
+ n.delays = true;
+ }
+ }
+
+ /*
+ * Disable delays usage for nodes in routing
+ */
+ public void nodelays() {
+ for (SimpleNode n: nodes) {
+ n.delays = false;
+ }
+ }
+
}
Added: trunk/apps/load-balancing-sims/phase7/sim/SimpleLink.java
===================================================================
--- trunk/apps/load-balancing-sims/phase7/sim/SimpleLink.java
(rev 0)
+++ trunk/apps/load-balancing-sims/phase7/sim/SimpleLink.java 2007-08-20
17:58:17 UTC (rev 14808)
@@ -0,0 +1,42 @@
+package sim;
+
+import java.util.LinkedList;
+import java.util.Random;
+
+class SimpleLink {
+
+ double d;
+ SimpleNode a,b;
+ static boolean use_delays=false;
+ static final Random rand = new Random(System.currentTimeMillis() % 10000);
+ // fixme: event queue for delivery of messages
+
+ public void use_delays() {
+ use_delays = true;
+ }
+
+ public SimpleLink(SimpleNode aend,SimpleNode bend) {
+ this(aend,bend,SimpleGraph.sampleDelay());
+ }
+
+ public SimpleLink(SimpleNode aend,SimpleNode bend,double delay) {
+ a = aend;
+ b = bend;
+ d = delay;
+ }
+
+ // Assumption: the application will know how to handle a link if its
directed (fixme?)
+ public LinkedList<SimpleQuery> send(SimpleQuery q) {
+
+ if (q.source==a) {
+ return b.recv(q);
+ } else if (q.source==b) {
+ return a.recv(q);
+ } else {
+ System.err.println("SimpleLink.send(): Simulation error, unknown
target?");
+ System.exit(-1);
+ }
+ return null;
+ }
+
+}
Modified: trunk/apps/load-balancing-sims/phase7/sim/SimpleNode.java
===================================================================
--- trunk/apps/load-balancing-sims/phase7/sim/SimpleNode.java 2007-08-20
17:00:45 UTC (rev 14807)
+++ trunk/apps/load-balancing-sims/phase7/sim/SimpleNode.java 2007-08-20
17:58:17 UTC (rev 14808)
@@ -12,40 +12,86 @@
class SimpleNode {
boolean print_steps = false;
- Random rand;
+ static Random rand;
+ boolean learning = false;
+ boolean delays = false;
+ int rand_interval;
double location;
- public Vector<SimpleNode> neighbors; // Symmetric for undirected, outgoing
when directed
- public Vector<SimpleNode> incoming; // Incoming when directed
+ public Vector<SimplePeer> neighbors; // Symmetric for undirected, outgoing
when directed
+ public Vector<SimplePeer> incoming; // Incoming when directed
public HashMap<SimpleNode,Integer> traffic_incoming;
public HashMap<SimpleNode,Integer> traffic_outgoing;
public HashMap<SimpleNode,Integer> init_local; // Outgoing traffic,
locally initiated
public HashMap<SimpleNode,Integer> init_remote; // Outgoing traffic,
remotely initated
public HashMap<SimpleNode,Integer> new_received; // New messages
received on an edge
public HashMap<SimpleNode,Integer> new_sent; // New messages sent
on an edge
+ public HashMap<SimpleNode,SimpleEstimator> estimators;
+ // SimpleEstimator est;
+ /* Distance time estimation
+ * Let D(y) be the time to neighbor y
+ * In a Kleinberg network we know that E[T|routing via y to z] = D(y) +
log(|z-y|)*c
+ * c is the unknown factor which we need to derive
+ * Route for a while: each time we route and get a response update c
(running average)
+ * NB: possibly we need to estimate c depending on neighbors, varying
connections to the network
+ */
+
/*** stats ***/
int load = 0;
- int loadmem = 0; // Internal
- boolean busy = false;
+ int loadmem = 0; // Total load seen
+ boolean busy = false; // Busy with current query?
+ boolean opennet = false; // Participate or not
+ int opennet_maxpeers = 0; // LRU-scheme to keep max this number
+ int estsize; // Size of routing estimation table
/*** constants ***/
public static final int LOCALORIG = 0;
public static final int REMOTEORIG = 1;
- public SimpleNode(double x) {
+ /*
+ * @x: location to take (on circle)
+ * @estsize: size of routing delay-estimation table (set to 0 if not used)
+ */
+ public SimpleNode(double x, int estsize) {
this.location = x;
- neighbors = new Vector<SimpleNode>();
- incoming = new Vector<SimpleNode>();
+ this.estsize = estsize;
+ neighbors = new Vector<SimplePeer>();
+ incoming = new Vector<SimplePeer>();
traffic_incoming = new HashMap<SimpleNode,Integer>();
traffic_outgoing = new HashMap<SimpleNode,Integer>();
init_local = new HashMap<SimpleNode,Integer>();
init_remote = new HashMap<SimpleNode,Integer>();
new_received = new HashMap<SimpleNode,Integer>();
new_sent = new HashMap<SimpleNode,Integer>();
- rand = new Random ((int) (System.currentTimeMillis() % 10000));
+ // est = new SimpleEstimator(estsize);
+ // rand = new Random ((int) (System.currentTimeMillis() % 10000));
+ estimators = new HashMap<SimpleNode,SimpleEstimator>();
+ rand = new Random(System.currentTimeMillis() % 10000);
}
+ /*
+ * Enable opennet peering/attempts for this node
+ *
+ * @desired_peers: number of desired peers before LRU-dropping
+ */
+ public void enableOpennet(int desired_peers) {
+ opennet = true;
+ opennet_maxpeers = desired_peers;
+ }
+
+ /*
+ * Disable opennet for this node
+ */
+ public void disableOpennet() {
+ opennet = false;
+ }
+
+ /*
+ * Keep incoming stats for a new query
+ *
+ * @inq: the query to register
+ */
public void load_incoming(SimpleQuery inq) {
load++;
loadmem++;
@@ -71,6 +117,15 @@
}
}
+ /*
+ * Keep outgoing stats for a query to be sent
+ *
+ * fixme: change this to be called from the level sending the query
+ * @n: target of the query
+ * @srctype: if source is local (SimpleNode.LOCALORIG) or if remote
+ * (SimpleNode.REMOTEORIG), which is used to separate load
+ * based on locally/remotely initiated query usage
+ */
public void load_outgoing(SimpleNode n, int srctype) {
// Total traffic
if(!traffic_outgoing.containsKey(n)) {
@@ -97,13 +152,26 @@
}
}
- // fixme: fresh taget going to target
+ // fixme: fresh taget going to target
}
+ /*
+ * Receive a generic query
+ */
+ public LinkedList<SimpleQuery> recv(SimpleQuery q) {
+ return route(q);
+ }
+
+ /*
+ * Route from q.source to q.target
+ *
+ * NB: if q.dest==null we count that the query q is internally handled as
starting request
+ * @q: The query that specifies which target we're on to
+ */
public LinkedList<SimpleQuery> route(SimpleQuery q) {
int htl = q.htl; // Internal htl value
int init; // local or remote origin?
- //load_incoming(q.source);
+ SimpleLink srclink = q.link;
load_incoming(q);
if(q.source == this) {
@@ -112,112 +180,314 @@
init = SimpleNode.REMOTEORIG;
}
- if(print_steps)
- printQueryState(htl);
-
LinkedList<SimpleQuery> result = new LinkedList<SimpleQuery>();
if(this.location == q.target.getLocation()) {
- result.addLast(new
SimpleQuery(this,q.source,q.target,SimpleQuery.SUCCESS,0));
+ result.addLast(new
SimpleQuery(this,q.source,q.target,srclink,SimpleQuery.SUCCESS,0,opennet_wantPeer()));
load_outgoing(q.source, init);
return result;
}
if(htl == 0) {
- result.addLast(new
SimpleQuery(this,q.source,q.target,SimpleQuery.HTLSTOP,0));
+ result.addLast(new
SimpleQuery(this,q.source,q.target,srclink,SimpleQuery.HTLSTOP,0,false));
load_outgoing(q.source, init);
return result;
}
if(busy) {
- result.addLast(new
SimpleQuery(this,q.source,q.target,SimpleQuery.REJECTLOOP,htl-1));
+ result.addLast(new
SimpleQuery(this,q.source,q.target,srclink,SimpleQuery.REJECTLOOP,htl-1,false));
load_outgoing(q.source, init);
return result;
}
busy = true;
- HashSet<SimpleNode> peers = new HashSet<SimpleNode>(neighbors);
- peers.remove(q.source);
+ /*
+ * Available peers
+ * fixme: do this lookup in a nicer way, get called directly from a
peer event
+ */
+ HashSet<SimplePeer> peers = new HashSet<SimplePeer>(neighbors);
+ SimplePeer srcpeer = null;
+ if((q.dest!=null) && (q.source!=this)) { // Ignore internal and
locally initiated
+ for (SimplePeer peer: neighbors) {
+ if(peer.n == q.source) {
+ srcpeer = peer;
+ break;
+ }
+ }
+ if(srcpeer == null) {
+ System.err.println("route(): at "+ this.getLocation() +": no
source peer at " + q.source.getLocation());
+ EvalKleinbergLoad.printNeighbors(this);
+ System.exit(0);
+ }
+ }
+ peers.remove(srcpeer);
+ /*
+ * Make selection until hops left in query.
+ * If using delays, then routing on is still restricted to nodes closer
+ * to target (dont let time dominate query getting closer)
+ */
int time = 0;
while(htl>0) {
-
- if(print_steps && (time>0))
- printQueryState(htl);
time++;
-
double bestdist = Double.MAX_VALUE;
- SimpleNode bestpeer = null;
+ double loc_bestdist = Double.MAX_VALUE;
+ SimplePeer bestpeer = null;
+ SimplePeer loc_bestpeer = null;
- for (SimpleNode peer: peers) {
- double dist = peer.distanceTo(q.target);
- if(dist < bestdist) {
- bestdist = dist;
- bestpeer = peer;
- } else if (dist == bestdist) {
- if(rand.nextDouble()<0.5) {
+ for (SimplePeer peer: peers) {
+ double dist,loc_dist;
+
+ /*
+ // Cheating for the optimal value *knowing* which neighbors
have already seen query (avoid loops)
+ if(peer.n.busy)
+ continue;
+ */
+
+ // dist = peer.l.d;
+ loc_dist = peer.n.distanceTo(q.target);
+
+ if (delays) {
+ // Dist to location
+ // dist = 2*peer.l.d + est.estimate(loc_dist);
+ // Dist but neighbor-sensitive
+ // dist = 2*peer.l.d +
estimators.get(peer.n).estimate(loc_dist);
+ // Location-based
+ dist = 2*peer.l.d +
estimators.get(peer.n).estimate(q.target.getLocation());
+ } else {
+ dist = loc_dist;
+ }
+
+ // Only consider a time-distance if node is physically closer
+ if (loc_dist<this.distanceTo(q.target)) {
+ if (dist<bestdist) {
bestdist = dist;
bestpeer = peer;
+ } else if ((dist==bestdist)&&(rand.nextDouble()<0.5)) {
+ bestdist = dist;
+ bestpeer = peer;
}
}
+
+ // Always compute loc-best
+ if (loc_dist<loc_bestdist) {
+ loc_bestdist = loc_dist;
+ loc_bestpeer = peer;
+ } else if ((loc_dist==loc_bestdist)&&(rand.nextDouble()<0.5)) {
+ loc_bestdist = loc_dist;
+ loc_bestpeer = peer;
+ }
}
-
- if(bestpeer == null) {
- result.addLast(new
SimpleQuery(this,q.source,q.target,SimpleQuery.DEADEND,htl-1));
+
+ if ((bestpeer==null) || (delays==false)) {
+ bestpeer = loc_bestpeer;
+ }
+
+ // Do we have an option? Otherwise the final (internal) load.
+ if (bestpeer==null) {
+ result.addLast(new
SimpleQuery(this,q.source,q.target,srclink,SimpleQuery.DEADEND,htl-1,false));
load_outgoing(q.source, init);
return result;
}
- result.addLast(new
SimpleQuery(this,bestpeer,q.target,SimpleQuery.FORWARD,htl-1));
+ // Pass on message and monitor timing (fixme: freenet HTL heuristic)
+ result.addLast(new
SimpleQuery(this,bestpeer.n,q.target,bestpeer.l,SimpleQuery.FORWARD,htl-1,false));
peers.remove(bestpeer);
- if(print_steps)
- System.err.println("sending to " + bestpeer.getLocation() +
"(attempt #"+time+")");
-
- // fixme: Freenet HTL heuristic
- load_outgoing(bestpeer, init);
- LinkedList<SimpleQuery> attempt = bestpeer.route(new
SimpleQuery(this,bestpeer,q.target,SimpleQuery.FORWARD,htl-1));
+ // Send the packet: load outgoing, route, load incoming result
+ load_outgoing(bestpeer.n, init);
+ LinkedList<SimpleQuery> attempt = bestpeer.l.send(new
SimpleQuery(this,bestpeer.n,q.target,bestpeer.l,SimpleQuery.FORWARD,htl-1,false));
load_incoming(attempt.getLast());
-
result.addAll(attempt);
+ // Learn from overheard/returned message (fixme: penalize when
routes have been sent wrong/HTLSTOP/...)
+ if (this.learning && (attempt.getLast().type==SimpleQuery.SUCCESS))
{
+ double routedist = bestpeer.n.distanceTo(q.target);
+ double rtt = routeTime(result)-2*result.getLast().link.d;
+ if(rtt<0) {
+ EvalKleinbergLoad.printRoute(attempt);
+ EvalKleinbergLoad.printRoute(result);
+ System.err.println("WTF?"); System.exit(0);
+ }
+
+ // Update estimators
+ // double rtt = routeTime(attempt)-2*attempt.getLast().link.d;
+ // est.update(routedist,rtt);
+ // estimators.get(bestpeer.n).update(routedist,rtt);
+ //
estimators.get(bestpeer.n).update(q.target.getLocation(),rtt);
+ estimators.get(bestpeer.n).update(q.target.getLocation(),rtt);
+ }
+
+ // Pass back
switch(attempt.getLast().type) { // Did this branch
succeed?
case SimpleQuery.SUCCESS:
if(q.source != this) {
- result.addLast(new
SimpleQuery(this,q.source,q.target,SimpleQuery.SUCCESS,0));
+ result.addLast(new
SimpleQuery(this,q.source,q.target,srclink,SimpleQuery.SUCCESS,0,q.openref));
load_outgoing(q.source, init);
}
+
+ // fixme: more advanced decision on whether to let destsampling
or not
+ if(opennet) {
+ opennet_destsampling(q.target);
+ }
+
return result;
- case SimpleQuery.HTLSTOP:
+ case SimpleQuery.HTLSTOP: // No more Hops To
Live
if(q.source != this) {
- result.addLast(new
SimpleQuery(this,q.source,q.target,SimpleQuery.HTLSTOP,0));
+ result.addLast(new
SimpleQuery(this,q.source,q.target,srclink,SimpleQuery.HTLSTOP,0,false));
load_outgoing(q.source, init);
}
return result;
- default:
+ default: // Continue as long
as possible
htl = attempt.getLast().htl;
break;
}
}
- if(q.source != this) {
- result.addLast(new
SimpleQuery(this,q.source,q.target,SimpleQuery.HTLSTOP,0));
+ if(q.source != this) { // No more Hops To
Live
+ result.addLast(new
SimpleQuery(this,q.source,q.target,srclink,SimpleQuery.HTLSTOP,0,false));
load_outgoing(q.source, init);
}
return result;
}
+
+ /*
+ * Sample destination, using opennet connections as LRU
+ * fixme: support for directed edges
+ *
+ *
+ 1. Check if we want to drop some opennet peer for a new one
+ 2. Check which one to drop
+ 3. Connect to new node (ask if still wants us)
+ 4. If success, disconnect the old node
+ */
+ void opennet_destsampling(SimpleNode dest) {
+ if (this.hasNeighbor(dest) || rand.nextDouble()>0.1) {
+ return;
+ }
+
+ SimpleNode dropnode = null;
+ if (!opennet_wantPeer()) {
+ dropnode = opennet_nodeToDrop();
+ if (dropnode==null) {
+ return; // Cant drop a node at the moment
+ }
+ opennet_drop(dropnode);
+ }
+
+ if (dest.opennet_acceptpeer(this)) {
+ SimpleLink link = new SimpleLink(this,dest);
+ this.connect(dest,link,SimplePeer.t_OPENNET);
+ dest.connect(this,link,SimplePeer.t_OPENNET);
+ } else {
+ System.err.println("NOT accepting peer!"); System.exit(-1); // fixme
+ }
+ }
+
+ // fixme: concurrency
+ public boolean opennet_wantPeer() {
+
+ int opennet_peers=0;
+ for (SimplePeer p: neighbors) {
+ if (p.t == SimplePeer.t_OPENNET) {
+ opennet_peers++;
+ }
+ }
+
+ if(opennet_peers<opennet_maxpeers) {
+ return true;
+ } else {
+ return false;
+ }
+
+ }
+
+ // LRU-drop opennet nodes (Vector.add places on end)
+ public SimpleNode opennet_nodeToDrop() {
+ SimpleNode dropnode=null;
+ for (SimplePeer p: neighbors) {
+ if (p.t == SimplePeer.t_OPENNET) {
+ dropnode = p.n;
+ break;
+ }
+ }
+ return dropnode;
+ }
+
+ public boolean opennet_acceptpeer(SimpleNode n) {
+ if (this.hasNeighbor(n)) { // fixme: concurrency
+ System.err.println("Error: dest target already has the peer");
System.exit(0);
+ }
+
+ int opennet_peers=0;
+ for (SimplePeer p: neighbors) {
+ if (p.t == SimplePeer.t_OPENNET) {
+ opennet_peers++;
+ }
+ }
+
+ while (opennet_peers>=opennet_maxpeers) {
+ SimpleNode dropnode = opennet_nodeToDrop();
+ if (dropnode == null) { System.err.println("Error: cant find node
to drop"); System.exit(-1); }
+ opennet_drop(dropnode);
+ opennet_peers--;
+ }
+
+ return true;
+ }
+
+ /*
+ * Drop a node that is assumed to be as an opennet peer
+ */
+ public void opennet_drop(SimpleNode dropnode) {
+ if (!hasNeighbor(dropnode)) {
+ System.err.println("Error: does not have neighbor to drop");
System.exit(-1);
+ }
+
+ if (nodeToPeer(dropnode).t!=SimplePeer.t_OPENNET) {
+ System.err.println("Error: not opennet peer"); System.exit(-1);
+ }
+
+
+
+ disconnect(dropnode);
+ dropnode.disconnect(this);
+ }
+
+
+ double routeTime(LinkedList<SimpleQuery> route) {
+ double t = 0;
+ for (SimpleQuery q: route) {
+ t = t + q.link.d;
+ }
+ return t;
+ }
+
+
public double getLocation() {
return location;
}
+
+ public void setLocation(double loc) {
+ if((location < 0)||(location>=1)) {
+ System.err.println("setLocation(): setting location to " +
location);
+ System.exit(0);
+ }
+
+ location = loc;
+ }
+
+
public double distanceTo(SimpleNode target) {
return distanceTo(target.location);
}
+
public double distanceTo(double pos) {
if ((pos<0) || (pos>1)) {
System.err.println("SimpleNode.distanceTo(): malformed distance");
System.exit(-1);
@@ -225,45 +495,135 @@
return Math.min(Math.max(location,pos)-Math.min(location,pos),
Math.min(location,pos)+1.0-Math.max(location,pos));
}
- public void connect(SimpleNode target) {
+
+ public double distanceFrom(double from,double to) {
+ return Math.min(Math.max(from,to)-Math.min(from,to),
Math.min(from,to)+1.0-Math.max(from,to));
+ }
+
+
+ public void connect(SimpleNode target,SimpleLink link,int type) {
if (target == this) {
System.err.println("SimpleNode.connect(): connecting itself");
System.exit(-1);
}
+ if (this.hasNeighbor(target)) {
+ System.err.println("SimpleNode.connect(): neighbor exists");
System.exit(-1);
+ }
+ if (!(type==SimplePeer.t_DARKNET || type==SimplePeer.t_OPENNET)) {
+ System.err.println("SimpleNode.connect(): unknown type " + type);
System.exit(-1);
+ }
- if (neighbors.contains(target)) {
- System.err.println("SimpleNode.connect(): neighbors exists");
System.exit(-1);
- }
- neighbors.add(target);
- target.connectIncoming(this);
+ neighbors.add(new SimplePeer(target,link,type));
+ target.connectIncoming(this,link,type);
+ estimators.put(target,new SimpleEstimator(this.estsize));
}
+
// This is for easy book-keeping when we are evaluating a directed model
- public void connectIncoming(SimpleNode source) {
+ public void connectIncoming(SimpleNode source,SimpleLink link,int type) {
if(source == this) {
System.err.println("SimpleNode.connectIncoming(): connecting
itself"); System.exit(-1);
}
- if(incoming.contains(source)) {
+ if(this.hasIncoming(source)) {
System.err.println("SimpleNode.connectIncoming(): source exists");
System.exit(-1);
}
- incoming.add(source);
+ if (!(type==SimplePeer.t_DARKNET || type==SimplePeer.t_OPENNET)) {
+ System.err.println("SimpleNode.connect(): unknown type " + type);
System.exit(-1);
+ }
+
+ incoming.add(new SimplePeer(source,link,SimplePeer.t_DARKNET));
}
- public boolean hasNeighbor(SimpleNode peer) {
- return neighbors.contains(peer);
+
+ /*
+ * Disconnect a peer
+ * note: for directed edges the source should always disconnect
+ * fixme: load counting and disconnection
+ */
+ public void disconnect(SimpleNode target) {
+ if (nodeToPeer(target)==null) {
+ System.err.println("SimpleNode.disconnect(): peer not in
neighbors");
+ System.exit(-1);
+ }
+
+ for (SimplePeer p: neighbors) {
+ if (p.n == target) {
+ neighbors.remove(p);
+ break;
+ }
+ }
+
+ for (SimplePeer p: incoming) {
+ if (p.n == target) {
+ incoming.remove(p);
+ break;
+ }
+ }
+
+ traffic_incoming.remove(target);
+ traffic_outgoing.remove(target);
+ init_local.remove(target);
+ init_remote.remove(target);
+ new_received.remove(target);
+ new_sent.remove(target);
+ estimators.remove(target);
+
}
+ public SimplePeer nodeToPeer(SimpleNode n) {
+ for (SimplePeer p: neighbors) {
+ if (p.n == n) {
+ return p;
+ }
+ }
+ return null;
+ }
+
+ public boolean hasNeighbor(SimpleNode node) {
+ //return neighbors.contains(peer);
+ for(SimplePeer p: neighbors) {
+ if(p.n == node)
+ return true;
+ }
+ return false;
+ }
+
+
+ public boolean hasIncoming(SimpleNode node) {
+ for(SimplePeer p: incoming) {
+ if(p.n == node)
+ return true;
+ }
+ return false;
+ }
+
+
public int getDegree() {
return neighbors.size();
}
+
+ public double logDists(double from) {
+ double sum = 0;
+
+ for (SimplePeer p: neighbors) {
+ if (p.n.getLocation()==from) {
+ sum = sum + Math.log(distanceFrom(from,this.getLocation()));
+ } else {
+ sum = sum + Math.log(distanceFrom(from,p.n.getLocation()));
+ }
+ }
+ return sum;
+ }
+
+
public void printQueryState(int htl) {
System.err.print("[htl="+htl+"]");
System.err.print("location " + location +":\t");
System.err.print("[ ");
- for(SimpleNode n: neighbors) {
+ for(SimplePeer p: neighbors) {
+ SimpleNode n = p.n;
System.err.print(n.getLocation() + " ");
}
System.err.print("]\t");
}
-
}
Added: trunk/apps/load-balancing-sims/phase7/sim/SimplePeer.java
===================================================================
--- trunk/apps/load-balancing-sims/phase7/sim/SimplePeer.java
(rev 0)
+++ trunk/apps/load-balancing-sims/phase7/sim/SimplePeer.java 2007-08-20
17:58:17 UTC (rev 14808)
@@ -0,0 +1,34 @@
+//
+// Peer representation as seen from a SimpleNode
+//
+package sim;
+
+class SimplePeer {
+
+ static final int t_DARKNET=0;
+ static final int t_OPENNET=1;
+
+ SimpleNode n; // The peer node
+ SimpleLink l; // Link to peer
+ int t;
+
+ /*
+ * @target: the node which will become the peer
+ * @link: the link to the peer
+ * @type: type of peer (t.DARKNET or t_OPENNET)
+ */
+ public SimplePeer(SimpleNode target,SimpleLink link,int type) {
+ n = target;
+ l = link;
+ t = type;
+ }
+
+ public boolean drknetPeer() {
+ return (t==t_DARKNET);
+ }
+
+ public boolean opennetPeer() {
+ return (t==t_OPENNET);
+ }
+}
+
Modified: trunk/apps/load-balancing-sims/phase7/sim/SimpleQuery.java
===================================================================
--- trunk/apps/load-balancing-sims/phase7/sim/SimpleQuery.java 2007-08-20
17:00:45 UTC (rev 14807)
+++ trunk/apps/load-balancing-sims/phase7/sim/SimpleQuery.java 2007-08-20
17:58:17 UTC (rev 14808)
@@ -1,3 +1,6 @@
+//
+// Queries to track network traffic
+//
package sim;
class SimpleQuery {
@@ -2,2 +5,3 @@
+ // Message types
public static final int SUCCESS=0;
@@ -11,15 +15,31 @@
final SimpleNode source;
final SimpleNode dest;
final SimpleNode target;
+ final SimpleLink link;
final int type;
int htl;
+ boolean openref;
- public SimpleQuery (SimpleNode source, SimpleNode dest, SimpleNode target,
int type, int htl) {
+ /*
+ * @source: sender of query
+ * @dest: destination of query
+ * @target: ultimate target of query (ignored if without meaning)
+ * @l: the link over which the query is sent
+ * @type: type of query
+ * @htl: HTL left on query
+ * @opennet: if this contains an opennet reference (from a successful CHK)
+ */
+ public SimpleQuery (SimpleNode source, SimpleNode dest, SimpleNode target,
SimpleLink l, int type, int htl, boolean opennet) {
this.source = source;
this.dest = dest;
this.target = target;
+ this.link = l;
this.type = type;
this.htl = htl;
+ this.openref = opennet;
}
+ public boolean internalQuery() {
+ return (link==null);
+ }
}
