diff options
author | Peter Palfrader <peter@palfrader.org> | 2003-10-19 15:08:35 +0000 |
---|---|---|
committer | Peter Palfrader <peter@palfrader.org> | 2003-10-19 15:08:35 +0000 |
commit | a4c0d3d6d878da55435cb9d9cc8cff6199644199 (patch) | |
tree | e066aabfb7a143cd39c3740b4aedd701df5ac758 /src/org/noreply/fancydress/type3/PathSpec.java | |
parent | 46a03a3ea3c26a65e4428bc9de036a01487aeda3 (diff) |
Support random path creation
Diffstat (limited to 'src/org/noreply/fancydress/type3/PathSpec.java')
-rw-r--r-- | src/org/noreply/fancydress/type3/PathSpec.java | 366 |
1 files changed, 312 insertions, 54 deletions
diff --git a/src/org/noreply/fancydress/type3/PathSpec.java b/src/org/noreply/fancydress/type3/PathSpec.java index cbc608f..9e975c6 100644 --- a/src/org/noreply/fancydress/type3/PathSpec.java +++ b/src/org/noreply/fancydress/type3/PathSpec.java @@ -11,53 +11,125 @@ import java.util.*; public class PathSpec { - String pathSpec; - Path singlePath; + Directory dir; + PathComponent[] pathComponents; + boolean singleLeg; - private String[] tokenize(String path) throws Mix3Exception { - ArrayList nicks = new ArrayList(); - int indexFrom = 0; - int indexOf; - - while ((indexOf = path.indexOf(',', indexFrom)) != -1) { - String v = path.substring(indexFrom, indexOf).trim(); - if (v.equals("")) - throw new Mix3Exception("Invalid path."); - nicks.add( v ); - indexFrom = indexOf + 1; + private class PathComponent { + public final static double GAUSS_STD_DEV = 1.5; + + public final static int TYPE_NICKNAME = 1; + public final static int TYPE_RANDOM = 2; + public final static int TYPE_RANDOM_GAUSS = 3; + public final static int TYPE_CROSSOVER = 4; + int type; + Server byNickname; + int numRandoms; + + public PathComponent(Directory dir, String component) throws Mix3BadArgumentsIllegalPathSpecException { + String c = component.trim(); + if (c.equals("")) + throw new Mix3BadArgumentsIllegalPathSpecException("Invalid path: empty path component"); + char b = c.charAt(0); + + Integer integer; + switch (b) { + case '*' : + try { + integer = new Integer(c.substring(1)); + } catch (NumberFormatException e) { + throw new Mix3BadArgumentsIllegalPathSpecException("Invalid path: illegal path component '"+c+"'"); + } + type = TYPE_RANDOM; + numRandoms = integer.intValue(); + break; + case '~' : + try { + integer = new Integer(c.substring(1)); + } catch (NumberFormatException e) { + throw new Mix3BadArgumentsIllegalPathSpecException("Invalid path: illegal path component '"+c+"'"); + } + type = TYPE_RANDOM_GAUSS; + numRandoms = integer.intValue(); + break; + case '?' : + if (c.length() > 1) + throw new Mix3BadArgumentsIllegalPathSpecException("Invalid path: illegal path component '"+c+"'"); + type = TYPE_RANDOM; + numRandoms = 1; + break; + case ':' : + if (c.length() > 1) + throw new Mix3BadArgumentsIllegalPathSpecException("Invalid path: illegal path component '"+c+"'"); + type = TYPE_CROSSOVER; + break; + default : + Server server = dir.getServer(c); + if (server == null) + throw new Mix3BadArgumentsIllegalPathSpecException("Invalid path: Nickname '"+c+"' not found"); + if (!server.isUseable()) + throw new Mix3BadArgumentsIllegalPathSpecException("Invalid path: Nickname '"+c+"' is not useable"); + byNickname = server; + type = TYPE_NICKNAME; + break; + } } - String v = path.substring(indexFrom).trim(); - if (v.equals("")) - throw new Mix3Exception("Invalid path."); - nicks.add( v ); - String[] result = new String[nicks.size()]; - for (int i=0; i<result.length; i++) - result[i] = (String) nicks.get(i); + public boolean isCrossover() { + return (type == TYPE_CROSSOVER); + } - return result; + public Server[] getHops() { + Server[] result; + switch (type) { + case TYPE_NICKNAME : + result = new Server[1]; + result[0] = byNickname; + break; + case TYPE_RANDOM : + result = new Server[numRandoms]; + break; + case TYPE_RANDOM_GAUSS : + double d = CryptoPrimitives.normal(numRandoms, GAUSS_STD_DEV); + int num = (int) (d+0.5); + result = new Server[ num<0 ? 0 : num ]; + break; + default : + throw new Error("Unkown type "+type); + } + return result; + } } - private Hop[] parseHalfPath(Directory dir, String path) throws Mix3Exception { - String[] nicks = tokenize(path); - Hop[] hops = new Hop[nicks.length]; - - for (int i=0; i<hops.length; i++) { - Server server = dir.getServer(nicks[i]); - if (server == null) - throw new Mix3Exception("Invalid path: "+nicks[i]+" not found"); - ServerDescriptor desc = server.getDescriptor(); - IncomingMMTPSection incoming = desc.getIncomingMMTPSection(); - Routing routing; - - if (incoming.getHostname() != null) { /* FIXME */ - routing = new RoutingHOST(incoming.getHostname(), incoming.getPort(), server.getKeyID()); - } else { - routing = new RoutingIP4(incoming.getIP(), incoming.getPort(), server.getKeyID()); - } - hops[i] = new Hop(routing, desc.getPacketKey()); + private void splitCrossover(ArrayList tokens, String s) throws Mix3BadArgumentsIllegalPathSpecException { + int indexOf = s.indexOf(':'); + if (indexOf != -1) { + String s1 = s.substring(0, indexOf).trim(); + String s2 = s.substring(indexOf+1).trim(); + if (s1.equals("")) + throw new Mix3BadArgumentsIllegalPathSpecException("Invalid path: Empty hop before crossover point."); + if (s2.equals("")) + throw new Mix3BadArgumentsIllegalPathSpecException("Invalid path: Empty hop after crossover point."); + tokens.add(s1.trim()); + tokens.add(s2.trim()); + } else { + if (s.equals("")) + throw new Mix3BadArgumentsIllegalPathSpecException("Invalid path: Empty hop in path."); + tokens.add(s); } - return hops; + } + + private PathComponent[] parsePath(Directory dir, String path) throws Mix3BadArgumentsIllegalPathSpecException { + ArrayList nicks = new ArrayList(); + String[] tokens = Util.tokenize(path, ','); + for (int i=0; i<tokens.length; i++) + splitCrossover( nicks, tokens[i] ); + + PathComponent[] components = new PathComponent[nicks.size()]; + for (int i=0; i<nicks.size(); i++) + components[i] = new PathComponent(dir, (String) nicks.get(i)); + + return components; } @@ -70,26 +142,212 @@ public class PathSpec { * * @param path given path */ - public PathSpec(Directory dir, String pathSpec, boolean singleLeg) throws Mix3Exception { - this.pathSpec = pathSpec; + public PathSpec(Directory dir, String pathSpec, boolean singleLeg) throws Mix3BadArgumentsIllegalPathSpecException { + this.dir = dir; + this.singleLeg = singleLeg; + + if (singleLeg) { + /* single legs do not have a crossover point */ + int crossover = pathSpec.indexOf(':'); + if (crossover >= 0) + throw new Mix3BadArgumentsIllegalPathSpecException("Path is not a valid path: crossover point specified in single leg path."); + } else { + /* full paths may have up to one specified crossover point */ + int crossover = pathSpec.indexOf(':'); + if (crossover >= 0) + if (pathSpec.indexOf(':', crossover+1) >= 0) + throw new Mix3BadArgumentsIllegalPathSpecException("Path is not a valid path: more than one crossover points specified."); + } + + this.pathComponents = parsePath(dir, pathSpec); + } + + private class ServerWithCrossover { + public Server[] servers; + public int crossoverPoint; + + public Server getLastServer() { + return (servers[servers.length - 1]); + } + + public void setLastServer(Server s) { + servers[servers.length - 1] = s; + } + + public Server getSecondToLastServer() { + return (servers[servers.length - 2]); + } + + private void fillInRandoms() throws Mix3PathProblemException { + Server[] recommended = dir.getRecommendedServers(); + for (int i=servers.length-1; i>=0 ; i--) { + if (servers[i] != null) + continue; + ArrayList s = new ArrayList(); + for (int r=0; r<recommended.length; r++) + if ( + /* last hop or */ + ((i == servers.length-1) || ( + /* next hop is different */ + (recommended[r] != servers[i+1]) && + /* and can talk to next hop */ + dir.areFriends(recommended[r], servers[i+1]) )) && + /* first hop, or previos hop is random, or */ + ((i == 0) || (servers[i-1] == null) || ( + /* previous hop is different */ + (recommended[r] != servers[i-1]) && + /* and prev hop can talk to this */ + dir.areFriends(servers[i-1], recommended[r]) )) + ) + s.add(recommended[r]); + if (s.size() == 0) + throw new Mix3PathProblemException("Cannot find useable servers for random hop."); + servers[i] = (Server) s.get(CryptoPrimitives.randInt(s.size())); + } + } + + public Path getPath() throws Mix3PathProblemException { + fillInRandoms(); + Hop[] hops = new Hop[servers.length]; + for (int i=0; i<hops.length ; i++) + hops[i] = new Hop(servers[i]); + + if (crossoverPoint == -1) + crossoverPoint = (hops.length+1)/2; + int len1 = crossoverPoint; + int len2 = hops.length - len1; + Hop[] l1 = new Hop[len1]; + Hop[] l2 = new Hop[len2]; + System.arraycopy(hops, 0, l1, 0, len1); + System.arraycopy(hops, len1, l2, 0, len2); + return new Path(l1, l2); + } + } + + /** + * Concat path components, getting random amount of hops where requested. + */ + private ServerWithCrossover concatComponents() throws Mix3PathProblemException { + Server[][] components = new Server[pathComponents.length][]; + int length = 0; + int crossoverBefore = -1; + for (int i=0; i<pathComponents.length ; i++) { + if (pathComponents[i].isCrossover()) + crossoverBefore = length; + else { + components[i] = pathComponents[i].getHops(); + length += components[i].length; + } + } + Server[] servers = new Server[length]; + int c = 0; + for (int i=0; i<pathComponents.length ; i++) { + if (components[i] != null) { + System.arraycopy(components[i], 0, servers, c, components[i].length); + c += components[i].length; + } + } + if (c != length) + throw new Error ("Did not fill in length hops ("+c+" vs "+length+")"); + + ServerWithCrossover result = new ServerWithCrossover(); + result.servers = servers; + result.crossoverPoint = crossoverBefore; + return result; + } + + /** + * get one instance of this path spec. + * + * Also we filter acceptable exit nodes according to the payload's + * constraints. + * + * @return one path constructed from the PathSpec + */ + /* + private Object getPathInstance() throws Mix3PathProblemException { - int crossover = pathSpec.indexOf(':'); - if (crossover < 0) - throw new Mix3Exception("Path is not a valid path: no crossover point specified."); + ServerWithCrossover path = concatComponents(); + fillInRandoms(path.components); - Hop[] leg1 = parseHalfPath(dir, pathSpec.substring(0, crossover)); - Hop[] leg2 = parseHalfPath(dir, pathSpec.substring(crossover+1)); - singlePath = new Path(leg1, leg2); + if (singleLeg) + throw new Error("not implemented yet"); // FIXME + else + return path.getPath(); } + */ /** - * Return a path constructed from this PathSpec + * Return paths constructed from this PathSpec. + * + * Build paths from this pathspec that are able to deliver the payload + * in <code>payload</code>. * - * @param dir a directory - * @return path + * We build as many paths as <code>payload.numPackets()</code> requires. + * + * Also we filter acceptable exit nodes according to the payload's + * constraints. + * + * @param payload the payload + * @return paths constructed from the PathSpec */ - public Path getPath() throws Mix3Exception { - return singlePath; + public Path[] getPath(Payload payload) throws Mix3PathProblemException { + if (singleLeg) + throw new IllegalArgumentException("getPath() may not be called for single leg path specs."); + + + ServerWithCrossover[] paths = new ServerWithCrossover[payload.numPackets()]; + for (int i=0; i<paths.length; i++) { + paths[i] = concatComponents(); + if (paths[i].servers.length < 2) + throw new Mix3PathProblemException("Path too short."); + } + + Server lastHop = paths[0].getLastServer(); + for (int i=1; i<paths.length; i++) + if (lastHop != paths[i].getLastServer()) + throw new Mix3PathProblemException("Exit hop must be the same in all paths (random or fixed)"); + + Server[] possibleExitHops = payload.filterExithops( dir.getRecommendedServers() ); + if (lastHop == null) { + boolean[] unuseable = new boolean[possibleExitHops.length]; + for (int i=0; i<paths.length; i++) { + Server stls = paths[i].getSecondToLastServer(); + if (stls == null) + continue; + for (int j=0; j<unuseable.length; j++) + if (unuseable[j]) + continue; + else + if (! dir.areFriends(stls, possibleExitHops[j] )) + unuseable[j] = true; + } + ArrayList list = new ArrayList(); + for (int j=0; j<unuseable.length; j++) + if (! unuseable[j]) + list.add(possibleExitHops[j]); + + if (list.size() == 0) + throw new Mix3PathProblemException("No useable exit hops found"); + + lastHop = (Server) list.get( CryptoPrimitives.randInt(list.size()) ); + for (int i=0; i<paths.length; i++) + paths[i].setLastServer(lastHop); + } else { + boolean exitHopOK = false; + for (int j=0; j<possibleExitHops.length; j++) + if (possibleExitHops[j] == lastHop) { + exitHopOK = true; + break; + } + if (! exitHopOK) + throw new Mix3PathProblemException("Exit hop "+lastHop.getNickname()+" does not meet constraints."); + } + + Path[] result = new Path[paths.length]; + for (int i=0; i<paths.length; i++) + result[i] = paths[i].getPath(); + + return result; } } - |