Changeset f965466

Timestamp:

May 11, 2011 2:40:55 PM (10 years ago)

Author:

zzz <zzz@…>

Branches:

master

Children:

ffa9ea9

Parents:

5ce06d02

Message:

• Use partitions of fast tier for various hops of client tunnels; minor cleanups

Files:

• history.txt (modified) (1 diff)
• router/java/src/net/i2p/router/RouterVersion.java (modified) (1 diff)
• router/java/src/net/i2p/router/peermanager/ProfileOrganizer.java (modified) (13 diffs)
• router/java/src/net/i2p/router/tunnel/pool/ClientPeerSelector.java (modified) (1 diff)
• router/java/src/net/i2p/router/tunnel/pool/TunnelPeerSelector.java (modified) (2 diffs)

history.txt

@@ +1 @@
+2011-05-11 zzz
+    * Use partitions of fast tier for various hops of client tunnels
+
 2011-05-06 zzz
     * Tunnels and profiles:

router/java/src/net/i2p/router/RouterVersion.java

@@ -19 +19 @@
     public final static String ID = "Monotone";
     public final static String VERSION = CoreVersion.VERSION;
-    public final static long BUILD = 2;
+    public final static long BUILD = 3;
 
     /** for example "-test" */

router/java/src/net/i2p/router/peermanager/ProfileOrganizer.java

@@ -3 +3 @@
 import java.io.IOException;
 import java.io.OutputStream;
-import java.io.Writer;
 import java.net.InetAddress;
 import java.net.UnknownHostException;
@@ -23 +22 @@
 import java.util.concurrent.locks.ReentrantReadWriteLock;
 
+import net.i2p.crypto.SHA256Generator;
 import net.i2p.data.Hash;
 import net.i2p.data.RouterAddress;
@@ -79 +79 @@
     public static final int DEFAULT_MINIMUM_FAST_PEERS = 8;
     /** this is misnamed, it is really the max minimum number. */
-    private static final int DEFAULT_MAXIMUM_FAST_PEERS = 16;
+    private static final int DEFAULT_MAXIMUM_FAST_PEERS = 18;
     private static final int ABSOLUTE_MAX_FAST_PEERS = 60;
 
@@ -94 +94 @@
     /** synchronized against this lock when updating the tier that peers are located in (and when fetching them from a peer) */
     private final ReentrantReadWriteLock _reorganizeLock = new ReentrantReadWriteLock(true);
-    
-    /** incredibly weak PRNG, just used for shuffling peers.  no need to waste the real PRNG on this */
-    private Random _random = new Random();
     
     public ProfileOrganizer(RouterContext context) {
@@ -109 +106 @@
         _failingPeers = new HashMap(16);
         _strictCapacityOrder = new TreeSet(_comp);
-        _thresholdSpeedValue = 0.0d;
-        _thresholdCapacityValue = 0.0d;
-        _thresholdIntegrationValue = 0.0d;
         _persistenceHelper = new ProfilePersistenceHelper(_context);
         
@@ -280 +274 @@
      * @param exclude set of Hashes for routers that we don't want selected
      * @param matches set to store the return value in
+     *
+     */
+    public void selectFastPeers(int howMany, Set<Hash> exclude, Set<Hash> matches) {
+        selectFastPeers(howMany, exclude, matches, 0);
+    }
+
+    /**
+     * Return a set of Hashes for peers that are both fast and reliable.  If an insufficient
+     * number of peers are both fast and reliable, fall back onto high capacity peers, and if that
+     * doesn't contain sufficient peers, fall back onto not failing peers, and even THAT doesn't
+     * have sufficient peers, fall back onto failing peers.
+     *
+     * @param howMany how many peers are desired
+     * @param exclude set of Hashes for routers that we don't want selected
+     * @param matches set to store the return value in
      * @param mask 0-4 Number of bytes to match to determine if peers in the same IP range should
      *             not be in the same tunnel. 0 = disable check; 1 = /8; 2 = /16; 3 = /24; 4 = exact IP match
      *
      */
-    public void selectFastPeers(int howMany, Set<Hash> exclude, Set<Hash> matches) {
-        selectFastPeers(howMany, exclude, matches, 0);
-    }
-
     public void selectFastPeers(int howMany, Set<Hash> exclude, Set<Hash> matches, int mask) {
         getReadLock();
@@ -297 +302 @@
                 _log.info("selectFastPeers("+howMany+"), not enough fast (" + matches.size() + ") going on to highCap");
             selectHighCapacityPeers(howMany, exclude, matches, mask);
+        } else {
+            if (_log.shouldLog(Log.INFO))
+                _log.info("selectFastPeers("+howMany+"), found enough fast (" + matches.size() + ")");
+        }
+        return;
+    }
+    
+    /**
+     * Return a set of Hashes for peers that are both fast and reliable.  If an insufficient
+     * number of peers are both fast and reliable, fall back onto high capacity peers, and if that
+     * doesn't contain sufficient peers, fall back onto not failing peers, and even THAT doesn't
+     * have sufficient peers, fall back onto failing peers.
+     *
+     * @param howMany how many peers are desired
+     * @param exclude set of Hashes for routers that we don't want selected
+     * @param matches set to store the return value in
+     * @param randomKey used for deterministic random partitioning into subtiers
+     * @param subTierMode 0 or 2-7:
+     *<pre>
+     *    0: no partitioning, use entire tier
+     *    2: return only from group 0 or 1
+     *    3: return only from group 2 or 3
+     *    4: return only from group 0
+     *    5: return only from group 1
+     *    6: return only from group 2
+     *    7: return only from group 3
+     *</pre>
+     */
+    public void selectFastPeers(int howMany, Set<Hash> exclude, Set<Hash> matches, Hash randomKey, int subTierMode) {
+        getReadLock();
+        try {
+            if (subTierMode > 0) {
+                int sz = _fastPeers.size();
+                if (sz < 6 || (subTierMode >= 4 && sz < 12))
+                    subTierMode = 0;
+            }
+            if (subTierMode > 0)
+                locked_selectPeers(_fastPeers, howMany, exclude, matches, randomKey, subTierMode);
+            else
+                locked_selectPeers(_fastPeers, howMany, exclude, matches, 2);
+        } finally { releaseReadLock(); }
+        if (matches.size() < howMany) {
+            if (_log.shouldLog(Log.INFO))
+                _log.info("selectFastPeers("+howMany+"), not enough fast (" + matches.size() + ") going on to highCap");
+            selectHighCapacityPeers(howMany, exclude, matches, 2);
         } else {
             if (_log.shouldLog(Log.INFO))
@@ -344 +394 @@
      * Return a set of Hashes for peers that are well integrated into the network.
      *
+     */
+    public void selectWellIntegratedPeers(int howMany, Set<Hash> exclude, Set<Hash> matches) {
+        selectWellIntegratedPeers(howMany, exclude, matches, 0);
+    }
+
+    /**
+     * Return a set of Hashes for peers that are well integrated into the network.
+     *
      * @param mask 0-4 Number of bytes to match to determine if peers in the same IP range should
      *             not be in the same tunnel. 0 = disable check; 1 = /8; 2 = /16; 3 = /24; 4 = exact IP match
      */
-    public void selectWellIntegratedPeers(int howMany, Set<Hash> exclude, Set<Hash> matches) {
-        selectWellIntegratedPeers(howMany, exclude, matches, 0);
-    }
-
     public void selectWellIntegratedPeers(int howMany, Set<Hash> exclude, Set<Hash> matches, int mask) {
         getReadLock();
@@ -1064 +1118 @@
     /** called after locking the reorganizeLock */
     private PeerProfile locked_getProfile(Hash peer) {
-        PeerProfile cur = (PeerProfile)_notFailingPeers.get(peer);
+        PeerProfile cur = _notFailingPeers.get(peer);
         if (cur != null) 
             return cur;
-        cur = (PeerProfile)_failingPeers.get(peer);
+        cur = _failingPeers.get(peer);
         return cur;
     }
@@ -1159 +1213 @@
 
     /** generate an arbitrary unique value for this ip/mask (mask = 1-4) */
-    private Integer maskedIP(byte[] ip, int mask) {
+    private static Integer maskedIP(byte[] ip, int mask) {
         int rv = 0;
         for (int i = 0; i < mask; i++)
@@ -1167 +1221 @@
 
     /** does a contain any of the elements in b? */
-    private boolean containsAny(Set a, Set b) {
+    private static boolean containsAny(Set a, Set b) {
         for (Object o : b) {
             if (a.contains(o))
@@ -1173 +1227 @@
         }
         return false;
+    }
+
+    /**
+     * @param randomKey used for deterministic random partitioning into subtiers
+     * @param subTierMode 2-7:
+     *<pre>
+     *    2: return only from group 0 or 1
+     *    3: return only from group 2 or 3
+     *    4: return only from group 0
+     *    5: return only from group 1
+     *    6: return only from group 2
+     *    7: return only from group 3
+     *</pre>
+     */
+    private void locked_selectPeers(Map<Hash, PeerProfile> peers, int howMany, Set<Hash> toExclude, Set<Hash> matches, Hash randomKey, int subTierMode) {
+        List<Hash> all = new ArrayList(peers.keySet());
+        // use RandomIterator to avoid shuffling the whole thing
+        for (Iterator<Hash> iter = new RandomIterator(all); (matches.size() < howMany) && iter.hasNext(); ) {
+            Hash peer = iter.next();
+            if (toExclude != null && toExclude.contains(peer))
+                continue;
+            if (matches.contains(peer))
+                continue;
+            if (_us.equals(peer))
+                continue;
+            int subTier = getSubTier(peer, randomKey);
+            if (subTierMode >= 4) {
+                if (subTier != (subTierMode & 0x03))
+                    continue;
+            } else {
+                if ((subTier >> 1) != (subTierMode & 0x01))
+                    continue;
+            }
+            boolean ok = isSelectable(peer);
+            if (ok)
+                matches.add(peer);
+            else
+                matches.remove(peer);
+        }
+    }
+    
+    /**
+     *  Implement a random, deterministic split into 4 groups that cannot be predicted by
+     *  others.
+     *  @return 0-3
+     */
+    private static int getSubTier(Hash peer, Hash randomKey) {
+        byte[] data = new byte[Hash.HASH_LENGTH + 4];
+        System.arraycopy(peer.getData(), 0, data, 0, Hash.HASH_LENGTH);
+        System.arraycopy(randomKey.getData(), 0, data, Hash.HASH_LENGTH, 4);
+        Hash rh = SHA256Generator.getInstance().calculateHash(data);
+        return rh.getData()[0] & 0x03;
     }
 
@@ -1289 +1395 @@
     protected int getMinimumFastPeers() {
         int def = Math.min(DEFAULT_MAXIMUM_FAST_PEERS,
-                           (2 *_context.clientManager().listClients().size()) + DEFAULT_MINIMUM_FAST_PEERS - 2);
+                           (6 *_context.clientManager().listClients().size()) + DEFAULT_MINIMUM_FAST_PEERS - 2);
         return _context.getProperty(PROP_MINIMUM_FAST_PEERS, def);
     }

router/java/src/net/i2p/router/tunnel/pool/ClientPeerSelector.java

@@ -22 +22 @@
         if ( (length == 0) && (settings.getLength()+settings.getLengthVariance() > 0) )
             return null;
-        HashSet matches = new HashSet(length);
+
+        List<Hash> rv;
     
         if (length > 0) {
             if (shouldSelectExplicit(settings))
                 return selectExplicit(ctx, settings, length);
+        
+            Set<Hash> exclude = getExclude(ctx, settings.isInbound(), settings.isExploratory());
+            Set<Hash> matches = new HashSet(length);
+            if (length == 1) {
+                ctx.profileOrganizer().selectFastPeers(length, exclude, matches, 0);
+                matches.remove(ctx.routerHash());
+                rv = new ArrayList(matches);
+            } else {
+                // build a tunnel using 4 subtiers.
+                // For a 2-hop tunnel, the first hop comes from subtiers 0-1 and the last from subtiers 2-3.
+                // For a longer tunnels, the first hop comes from subtier 0, the middle from subtiers 2-3, and the last from subtier 1.
+                rv = new ArrayList(length + 1);
+                // OBEP or IB last hop
+                // group 0 or 1 if two hops, otherwise group 0
+                ctx.profileOrganizer().selectFastPeers(1, exclude, matches, settings.getRandomKey(), length == 2 ? 2 : 4);
+                matches.remove(ctx.routerHash());
+                exclude.addAll(matches);
+                rv.addAll(matches);
+                matches.clear();
+                if (length > 2) {
+                    // middle hop(s)
+                    // group 2 or 3
+                    ctx.profileOrganizer().selectFastPeers(length - 2, exclude, matches, settings.getRandomKey(), 3);
+                    matches.remove(ctx.routerHash());
+                    if (matches.size() > 1) {
+                        // order the middle peers for tunnels >= 4 hops
+                        List<Hash> ordered = new ArrayList(matches);
+                        orderPeers(ordered, settings.getRandomKey());
+                        rv.addAll(ordered);
+                    } else {
+                        rv.addAll(matches);
+                    }
+                    exclude.addAll(matches);
+                    matches.clear();
+                }
+                // IBGW or OB first hop
+                // group 2 or 3 if two hops, otherwise group 1
+                ctx.profileOrganizer().selectFastPeers(1, exclude, matches, settings.getRandomKey(), length == 2 ? 3 : 5);
+                matches.remove(ctx.routerHash());
+                rv.addAll(matches);
+            }
+        } else {
+            rv = new ArrayList(1);
         }
         
-        Set exclude = getExclude(ctx, settings.isInbound(), settings.isExploratory());
-        ctx.profileOrganizer().selectFastPeers(length, exclude, matches, settings.getIPRestriction());
-        
-        matches.remove(ctx.routerHash());
-        ArrayList<Hash> rv = new ArrayList(matches);
-        if (rv.size() > 1)
-            orderPeers(rv, settings.getRandomKey());
         if (settings.isInbound())
             rv.add(0, ctx.routerHash());

router/java/src/net/i2p/router/tunnel/pool/TunnelPeerSelector.java

@@ -42 +42 @@
     public abstract List<Hash> selectPeers(RouterContext ctx, TunnelPoolSettings settings);
     
+    /**
+     *  @return randomized number of hops 0-7, not including ourselves
+     */
     protected int getLength(RouterContext ctx, TunnelPoolSettings settings) {
         int length = settings.getLength();
@@ -62 +65 @@
         if (length < 0)
             length = 0;
-        else if (length > 8) // as documented in tunnel.html
-            length = 8;
+        else if (length > 7) // as documented in tunnel.html
+            length = 7;
         /*
         if ( (ctx.tunnelManager().getOutboundTunnelCount() <= 0) ||