On Friday 24 April 2009 20:03:41 vive wrote: > On Fri, Apr 10, 2009 at 09:03:12PM +0100, Matthew Toseland wrote: > > On Wednesday 11 February 2009 13:53:50 v...@freenetproject.org wrote: > > > Author: vive > > > Date: 2009-02-11 13:53:49 +0000 (Wed, 11 Feb 2009) > > > New Revision: 25585 > > > Added: > > > > Log: > > > simsalabim: Freenet 0.7 simulator ... > > > + > > > + public DarknetRoute findRoute(CircleKey k, DarknetRoute dnr) { > > > + > > > + if (!inNetwork) > > > + throw new Error("Node not in Network routed to: " + > > > this); > > > + if (!isActive()) > > > + throw new Error("Node that is active routed to: " + > > > this); > > > + > > > + /* > > > + * Routing with > > > + * 1) Backtracking > > > + * 2) HTL (fixed decrease per node, not probabilistic as in > > > freenet) > > > + * > > > + * Cache/Store: when route has completed > > > + */ > > > + > > > + if (dnr == null) > > > + dnr = new DarknetRoute(god.N_BEST, god.HTL); > > > + > > > + dnr.atNode(this, k); > > > + numQueries++; > > > + > > > + if (data.contains(k) || cache.contains(k)) // > > > terminate on success > > > + return dnr; > > > + > > > + while (dnr.htl > 0) { > > > + double bd = Double.MAX_VALUE; > > > + DarknetNode cand = null; > > > + > > > + for (Iterator<DarknetNode> it = neighbors() ; > > > it.hasNext() ;) { > > > + DarknetNode t = it.next(); > > > + if (dnr.contains(t)) > > > + continue; > > > > We never route to the same node twice even to be rejected in your simulation. > > I wonder what impact this has? I mean, it would be easy enough to use a local > > set in this function, and check contains at the beginning of the function... > > Yes, routes only cross specific nodes once (except when they backtrack). > This is the best approximation I have found since I was unable to understand a few > heuristics in the node. I am looking forward to a good (but short!) summary of routing > heuristics or I will need to read code myself to make routing more realistic in further > versions.
Hmmm, I always thought RejectedLoop was pretty clear. > > > Is there some basic load simulation? Your conclusions about network merging > > may be way off if you're not taking into account the limited capacity of the > > bridge nodes...? Or have you eliminated that somehow? > > It may be way off, but I checked that the load on the border nodes was fairly > low. I found that the success rate depends on the data finding its way over > the network borders once or twice, before becoming available in a different > component. Swapping specialization happens very slow with few border nodes, > which leads to content specialization and failed routes in the other component. > With more border nodes, specialization goes faster but at the same time there > are more border nodes able to take the load... > > No, there is no simulation of the load-mgmt that nodes do. Its not event-based > down on a fine level of detail, high-level events such as routing and swapping > only *complete* at certain times. I am currently working on an event-based version. > Cool. ... > > > + } > > > + } > > > + > > > + for (Iterator<DarknetNode> it = openNeighbors.iterator() ; > > it.hasNext() ; ) { > > > + DarknetNode open = it.next(); > > > + open.openNeighbors.remove(this); > > > + } > > > + openNeighbors.clear(); > > > + > > > + // Dormant nodes dont remove data > > > + if (permanent) { > > > + for (Iterator<Data> it = data.data() ; it.hasNext() ;) { > > > + it.next().removedFrom(this); > > > + } > > > + > > > + for (Iterator<Data> it = cache.data() ; it.hasNext() ;) { > > > + it.next().removedFrom(this); > > > + } > > > + } > > > + > > > + return n; > > > + } > > > + > > > + public boolean isSink(CircleKey k) { > > > + for (DarknetNode n : neighbors) { > > > + if (k.dist(n.pos) < k.dist(pos)) > > > + return false; > > > + } > > > + return true; > > > + } > > > > We have uptime requirements in this in the real node, it'd be nice to have > > some theoretical support for that decision... I guess it would require some > > sort of distribution of uptimes though... > > Yes, but it could also be based on some heuristic. Storing join and leave time > in the simulation is no problem. Do you have any suggestion for why it is needed? > Well, we store on 3 nodes's stores typically. So if these are all low-uptime, or worse, newbie nodes that appear and then vanish forever, it will be impossible to find the data, or it will take a very long time. > > > + > > > + public boolean hasData(CircleKey k) { > > > + return data.contains(k) || cache.contains(k); > > > + } > > > + > > > + public Data findData(CircleKey k) { > > > + Data cached = cache.get(k); > > > + > > > + return (cached != null) ? cached : data.get(k); > > > + } > > > + > > > + /** > > > + * Always store in cache > > > + * @sink: Whether to store in the long-term storage > > > + */ > > > + > > > + public void storeData(Data<CircleKey> d, boolean sink) { > > > + if (sink) { > > > + if (!data.contains(d.key())) > > > + d.addedTo(this); > > > + Data r = data.put(d); > > > + if (r != null) > > > + r.removedFrom(this); > > > + } > > > > We don't store in the cache if we have stored in the store. > > Are you sure?! Hmmm, in fact we do store in both. Do you have any opinion on this? > > > + > > > + /** > > > + * Calculates the log distance to the neighbors of this node from newpos. > > If > > > + * a neighbor has position newpos, then it is given my current position. > > > + */ > > > + private double logdist(CircleKey newpos) { > > > + double val = 0.0f; > > > + for (Iterator<DarknetNode> it = neighbors.iterator() ; it.hasNext() ;) { > > > + DarknetNode dn = it.next(); > > > + val += Math.log(dn.pos == newpos ? pos.dist(newpos) : > > > + dn.pos.dist(newpos)); > > > > Doh! We just ignore it if we are neighbours in LocationManager.java! Granted > > this is a pretty small effect, but it needs to be fixed... > > ??? In LocationManager, when we are deciding whether to do a swap, if the location of a neighbour of the swap target is equal to our location (or theirs, depending on the bit of the calculation), and would thus introduce a zero, we don't include it in the calculation: double A = 1.0; for(int i=0;i<friendLocs.length;i++) { if(Math.abs(friendLocs[i] - myLoc) <= Double.MIN_VALUE*2) continue; A *= Location.distance(friendLocs[i], myLoc); } for(int i=0;i<hisFriendLocs.length;i++) { if(Math.abs(hisFriendLocs[i] - hisLoc) <= Double.MIN_VALUE*2) continue; A *= Location.distance(hisFriendLocs[i], hisLoc); } // B = the same, with our two values swapped double B = 1.0; for(int i=0;i<friendLocs.length;i++) { if(Math.abs(friendLocs[i] - hisLoc) <= Double.MIN_VALUE*2) continue; B *= Location.distance(friendLocs[i], hisLoc); } for(int i=0;i<hisFriendLocs.length;i++) { if(Math.abs(hisFriendLocs[i] - myLoc) <= Double.MIN_VALUE*2) continue; B *= Location.distance(hisFriendLocs[i], myLoc); } > > > Hmm. Because of network bugs / race conditions, it is occasionally possible > > for two nodes to have the same location... Should we ignore when a peer of > > his has our location, or should we assume they are us and calculate it for > > their location? Is this different for before vs after calculations? > > If they have the same location it does not matter... right? The switch can > not load to any difference. So the code above is correct? > > > > + } > > > + return val; > > > + } > > > + > > > + > > ... > > > Added: trunk/apps/simsalabim/DarknetRoute.java > > > =================================================================== > > > --- trunk/apps/simsalabim/DarknetRoute.java > > > (rev 0) > > > +++ trunk/apps/simsalabim/DarknetRoute.java 2009-02-11 13:53:49 UTC > > > (rev > > 25585) > > ... > > > + > > > + public Data findData(CircleKey k) { > > > + for (Iterator<DarknetNode> it = route.iterator() ; it.hasNext() > > > ;) { > > > + Data d = it.next().findData(k); > > > + if (d != null) > > > + return d; > > > + } > > > + return null; > > > + } > > > > You don't check on each hop as you reach it? Is this some idea about visiting > > all the nodes on the route even if we find the data early on, so we can store > > it everywhere for better data robustness? (And considerably worse performance > > on popular data!) > > Its just a matter of implemetation. The routes terminate for different reasons. > When a route has terminated, the implementation checks if the data was found. It > corresponds to the node checking the message directly in the real node. But you only cache it on nodes before the one where the data was found?
signature.asc
Description: This is a digitally signed message part.
_______________________________________________ Devl mailing list Devl@freenetproject.org http://emu.freenetproject.org/cgi-bin/mailman/listinfo/devl