[Patch] Re: Mixminion random path selection

[tainaron@xxxxxxxxxxxxxxxx]

Hi,

Marco wrote:
> I saw that when using partial random path selection
> e.g.   -P "*3,pboxlevel3"
> nothing disallow double hit in path calculation, as for example
> Beowulf,pboxlevel3:sullust,pboxlevel3

If paths get longer it might not be desirable to completely disallow using
servers multiple times. Instead (as in mixmaster) you might like the idea to
keep a minimum distance between two occurences of the same server in a path.

At path generation mixminion so far tries to not use a server twice in a
row, so basically the minimum distance between two occurences of the same
server is one other node.

Please find below a patch that implements checking for this neighborhood
criterion. The minimum distance is not yet user-configurable, I'd like to
hear opinions first whether this is something sensible.

There might have been some thoughts about a "suggested path selection
algorithm", however the appendix A.2 seems to be missing from the directory
specification (as well as the occasionally referenced "path specification").

Ciao.

--- ClientDirectory.py
+++ ClientDirectory.py
@@ -1342,6 +1342,9 @@
         elif len(relays) == 1:
             LOG.warn("Only one relay known")

+        # Minimum hops between two occurences of the same server
+        minDistance = 3
+
         # Now fill in the servers. For each relay we need...
         for i in xrange(len(servers)):
             if servers[i] is not None:
@@ -1355,6 +1358,10 @@
                 next = servers[i+1]
             else:
                 next = None
+            # Get servers in neighborhood
+            leftScope = max(0, i-minDistance);
+            rightScope = min(i+minDistance, len(servers));
+            neighborhood = servers[leftScope:i] + servers[i+1:rightScope]
             # ...and see if there are any relays left that aren't adjacent?
             candidates = []
             for c in relays:
@@ -1374,6 +1381,9 @@
                 if ((prev and not prev.canRelayTo(c)) or
                     (next and not c.canRelayTo(next))):
                     continue
+                # Avoid hops in neighborhood
+                if c in neighborhood:
+                  continue
                 # Avoid first hops that we can't deliver to.
                 if (not prev) and not c.canStartAt():
                     continue