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 vive at 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?
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 835 bytes
Desc: This is a digitally signed message part.
URL:
<https://emu.freenetproject.org/pipermail/devl/attachments/20090513/c04a19a9/attachment.pgp>
