Thomas Bruderer wrote: > I want to mention at least something: If we have a small world topology we > have > many links to nearby nodes, and we have a few long links. The long links will > probably have more traffic then the nearby links. If such long links would be > between nodes with more capacity this would also help the rest of the network.
For what it's worth, I did some quick-and-dirty simulations a while back to test this theory - like you I thought longer links would have higher load, but it turns out the opposite is true. However my sims didn't include caching - if nearby nodes have similar items in their caches, that might relieve some of the load on short links. Cheers, Michael
<<inline: load.png>>
import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
class Node
{
public final static boolean TRACE = false;
public ArrayList<Node> neighbours = new ArrayList<Node>();
public HashMap<Node,Integer> load = new HashMap<Node,Integer>();
public double loc;
public Node (double loc)
{
this.loc = loc;
}
public void connect (Node n)
{
if (n == this || neighbours.contains (n)) return;
neighbours.add (n);
}
double distance (double targ)
{
if (loc > targ) return Math.min (loc - targ, targ - loc + 1.0);
else return Math.min (targ - loc, loc - targ + 1.0);
}
void incrementLoad (Node n)
{
Integer i = load.get (n);
if (i == null) load.put (n, 1);
else load.put (n, i + 1);
}
public int forward (double target, int htl, HashSet<Node> visited)
{
if (loc == target) {
if (TRACE) System.err.println (loc + " Y"); // Success
return -1;
}
if (htl == 0) {
if (TRACE) System.err.println (loc + " N"); // Failure
return 0;
}
if (!visited.add (this)) {
if (TRACE) System.err.print (loc + " L "); // Loop
return htl; // Backtrack
}
HashSet<Node> candidates = new HashSet<Node> (neighbours);
while (htl > 0) {
if (TRACE) System.err.print (loc + " ");
double bestDist = Double.POSITIVE_INFINITY;
Node bestNode = null;
for (Node n : candidates) {
double d = n.distance (target);
if (d < bestDist) {
bestDist = d;
bestNode = n;
}
}
if (bestNode == null) {
if (TRACE) System.err.print ("D "); // Dead-end
return htl; // Backtrack
}
candidates.remove (bestNode);
incrementLoad (bestNode);
htl = bestNode.forward (target, htl - 1, visited);
}
return htl;
}
public void printLoad()
{
for (Node n : neighbours) {
Integer i = load.get (n);
if (i == null) i = 0;
System.out.println (distance (n.loc) + " " + i);
}
}
}
import java.util.HashSet;
class SimpleRoutingTest
{
final static int NODES = 1000;
final static int DEGREE = 10;
final static int MESSAGES = 10000;
final static int HTL = 15;
Node[] nodes = new Node [NODES];
public SimpleRoutingTest()
{
for (int i = 0; i < NODES; i++)
nodes[i] = new Node ((double) i / NODES);
makeKleinbergNetwork();
}
static 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);
}
void makeKleinbergNetwork()
{
// 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
for (int i = 0; i < NODES; i++) {
for (int j = 0; j < i; j++) {
double p = 1.0 / latticeDistance (i, j) / norm;
for (int k = 0; k < DEGREE; k++) {
if (Math.random() < p) {
nodes[i].connect (nodes[j]);
nodes[j].connect (nodes[i]);
break;
}
}
}
}
}
void testForwarding()
{
for (int i = 0; i < MESSAGES; i++) {
Node n = nodes[(int)(Math.random() * NODES)];
double target = nodes[(int)(Math.random() * NODES)].loc;
if (Node.TRACE) System.err.print (target + ": ");
n.forward (target, HTL, new HashSet<Node>());
}
for (Node n : nodes) n.printLoad();
}
public static void main (String[] args)
{
new SimpleRoutingTest().testForwarding();
}
}
_______________________________________________ Devl mailing list [email protected] http://emu.freenetproject.org/cgi-bin/mailman/listinfo/devl
