Changeset f965466


Ignore:
Timestamp:
May 11, 2011 2:40:55 PM (9 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:
5 edited

Legend:

Unmodified
Added
Removed
  • history.txt

    r5ce06d02 rf965466  
     12011-05-11 zzz
     2    * Use partitions of fast tier for various hops of client tunnels
     3
    142011-05-06 zzz
    25    * Tunnels and profiles:
  • router/java/src/net/i2p/router/RouterVersion.java

    r5ce06d02 rf965466  
    1919    public final static String ID = "Monotone";
    2020    public final static String VERSION = CoreVersion.VERSION;
    21     public final static long BUILD = 2;
     21    public final static long BUILD = 3;
    2222
    2323    /** for example "-test" */
  • router/java/src/net/i2p/router/peermanager/ProfileOrganizer.java

    r5ce06d02 rf965466  
    33import java.io.IOException;
    44import java.io.OutputStream;
    5 import java.io.Writer;
    65import java.net.InetAddress;
    76import java.net.UnknownHostException;
     
    2322import java.util.concurrent.locks.ReentrantReadWriteLock;
    2423
     24import net.i2p.crypto.SHA256Generator;
    2525import net.i2p.data.Hash;
    2626import net.i2p.data.RouterAddress;
     
    7979    public static final int DEFAULT_MINIMUM_FAST_PEERS = 8;
    8080    /** this is misnamed, it is really the max minimum number. */
    81     private static final int DEFAULT_MAXIMUM_FAST_PEERS = 16;
     81    private static final int DEFAULT_MAXIMUM_FAST_PEERS = 18;
    8282    private static final int ABSOLUTE_MAX_FAST_PEERS = 60;
    8383
     
    9494    /** synchronized against this lock when updating the tier that peers are located in (and when fetching them from a peer) */
    9595    private final ReentrantReadWriteLock _reorganizeLock = new ReentrantReadWriteLock(true);
    96    
    97     /** incredibly weak PRNG, just used for shuffling peers.  no need to waste the real PRNG on this */
    98     private Random _random = new Random();
    9996   
    10097    public ProfileOrganizer(RouterContext context) {
     
    109106        _failingPeers = new HashMap(16);
    110107        _strictCapacityOrder = new TreeSet(_comp);
    111         _thresholdSpeedValue = 0.0d;
    112         _thresholdCapacityValue = 0.0d;
    113         _thresholdIntegrationValue = 0.0d;
    114108        _persistenceHelper = new ProfilePersistenceHelper(_context);
    115109       
     
    280274     * @param exclude set of Hashes for routers that we don't want selected
    281275     * @param matches set to store the return value in
     276     *
     277     */
     278    public void selectFastPeers(int howMany, Set<Hash> exclude, Set<Hash> matches) {
     279        selectFastPeers(howMany, exclude, matches, 0);
     280    }
     281
     282    /**
     283     * Return a set of Hashes for peers that are both fast and reliable.  If an insufficient
     284     * number of peers are both fast and reliable, fall back onto high capacity peers, and if that
     285     * doesn't contain sufficient peers, fall back onto not failing peers, and even THAT doesn't
     286     * have sufficient peers, fall back onto failing peers.
     287     *
     288     * @param howMany how many peers are desired
     289     * @param exclude set of Hashes for routers that we don't want selected
     290     * @param matches set to store the return value in
    282291     * @param mask 0-4 Number of bytes to match to determine if peers in the same IP range should
    283292     *             not be in the same tunnel. 0 = disable check; 1 = /8; 2 = /16; 3 = /24; 4 = exact IP match
    284293     *
    285294     */
    286     public void selectFastPeers(int howMany, Set<Hash> exclude, Set<Hash> matches) {
    287         selectFastPeers(howMany, exclude, matches, 0);
    288     }
    289 
    290295    public void selectFastPeers(int howMany, Set<Hash> exclude, Set<Hash> matches, int mask) {
    291296        getReadLock();
     
    297302                _log.info("selectFastPeers("+howMany+"), not enough fast (" + matches.size() + ") going on to highCap");
    298303            selectHighCapacityPeers(howMany, exclude, matches, mask);
     304        } else {
     305            if (_log.shouldLog(Log.INFO))
     306                _log.info("selectFastPeers("+howMany+"), found enough fast (" + matches.size() + ")");
     307        }
     308        return;
     309    }
     310   
     311    /**
     312     * Return a set of Hashes for peers that are both fast and reliable.  If an insufficient
     313     * number of peers are both fast and reliable, fall back onto high capacity peers, and if that
     314     * doesn't contain sufficient peers, fall back onto not failing peers, and even THAT doesn't
     315     * have sufficient peers, fall back onto failing peers.
     316     *
     317     * @param howMany how many peers are desired
     318     * @param exclude set of Hashes for routers that we don't want selected
     319     * @param matches set to store the return value in
     320     * @param randomKey used for deterministic random partitioning into subtiers
     321     * @param subTierMode 0 or 2-7:
     322     *<pre>
     323     *    0: no partitioning, use entire tier
     324     *    2: return only from group 0 or 1
     325     *    3: return only from group 2 or 3
     326     *    4: return only from group 0
     327     *    5: return only from group 1
     328     *    6: return only from group 2
     329     *    7: return only from group 3
     330     *</pre>
     331     */
     332    public void selectFastPeers(int howMany, Set<Hash> exclude, Set<Hash> matches, Hash randomKey, int subTierMode) {
     333        getReadLock();
     334        try {
     335            if (subTierMode > 0) {
     336                int sz = _fastPeers.size();
     337                if (sz < 6 || (subTierMode >= 4 && sz < 12))
     338                    subTierMode = 0;
     339            }
     340            if (subTierMode > 0)
     341                locked_selectPeers(_fastPeers, howMany, exclude, matches, randomKey, subTierMode);
     342            else
     343                locked_selectPeers(_fastPeers, howMany, exclude, matches, 2);
     344        } finally { releaseReadLock(); }
     345        if (matches.size() < howMany) {
     346            if (_log.shouldLog(Log.INFO))
     347                _log.info("selectFastPeers("+howMany+"), not enough fast (" + matches.size() + ") going on to highCap");
     348            selectHighCapacityPeers(howMany, exclude, matches, 2);
    299349        } else {
    300350            if (_log.shouldLog(Log.INFO))
     
    344394     * Return a set of Hashes for peers that are well integrated into the network.
    345395     *
     396     */
     397    public void selectWellIntegratedPeers(int howMany, Set<Hash> exclude, Set<Hash> matches) {
     398        selectWellIntegratedPeers(howMany, exclude, matches, 0);
     399    }
     400
     401    /**
     402     * Return a set of Hashes for peers that are well integrated into the network.
     403     *
    346404     * @param mask 0-4 Number of bytes to match to determine if peers in the same IP range should
    347405     *             not be in the same tunnel. 0 = disable check; 1 = /8; 2 = /16; 3 = /24; 4 = exact IP match
    348406     */
    349     public void selectWellIntegratedPeers(int howMany, Set<Hash> exclude, Set<Hash> matches) {
    350         selectWellIntegratedPeers(howMany, exclude, matches, 0);
    351     }
    352 
    353407    public void selectWellIntegratedPeers(int howMany, Set<Hash> exclude, Set<Hash> matches, int mask) {
    354408        getReadLock();
     
    10641118    /** called after locking the reorganizeLock */
    10651119    private PeerProfile locked_getProfile(Hash peer) {
    1066         PeerProfile cur = (PeerProfile)_notFailingPeers.get(peer);
     1120        PeerProfile cur = _notFailingPeers.get(peer);
    10671121        if (cur != null)
    10681122            return cur;
    1069         cur = (PeerProfile)_failingPeers.get(peer);
     1123        cur = _failingPeers.get(peer);
    10701124        return cur;
    10711125    }
     
    11591213
    11601214    /** generate an arbitrary unique value for this ip/mask (mask = 1-4) */
    1161     private Integer maskedIP(byte[] ip, int mask) {
     1215    private static Integer maskedIP(byte[] ip, int mask) {
    11621216        int rv = 0;
    11631217        for (int i = 0; i < mask; i++)
     
    11671221
    11681222    /** does a contain any of the elements in b? */
    1169     private boolean containsAny(Set a, Set b) {
     1223    private static boolean containsAny(Set a, Set b) {
    11701224        for (Object o : b) {
    11711225            if (a.contains(o))
     
    11731227        }
    11741228        return false;
     1229    }
     1230
     1231    /**
     1232     * @param randomKey used for deterministic random partitioning into subtiers
     1233     * @param subTierMode 2-7:
     1234     *<pre>
     1235     *    2: return only from group 0 or 1
     1236     *    3: return only from group 2 or 3
     1237     *    4: return only from group 0
     1238     *    5: return only from group 1
     1239     *    6: return only from group 2
     1240     *    7: return only from group 3
     1241     *</pre>
     1242     */
     1243    private void locked_selectPeers(Map<Hash, PeerProfile> peers, int howMany, Set<Hash> toExclude, Set<Hash> matches, Hash randomKey, int subTierMode) {
     1244        List<Hash> all = new ArrayList(peers.keySet());
     1245        // use RandomIterator to avoid shuffling the whole thing
     1246        for (Iterator<Hash> iter = new RandomIterator(all); (matches.size() < howMany) && iter.hasNext(); ) {
     1247            Hash peer = iter.next();
     1248            if (toExclude != null && toExclude.contains(peer))
     1249                continue;
     1250            if (matches.contains(peer))
     1251                continue;
     1252            if (_us.equals(peer))
     1253                continue;
     1254            int subTier = getSubTier(peer, randomKey);
     1255            if (subTierMode >= 4) {
     1256                if (subTier != (subTierMode & 0x03))
     1257                    continue;
     1258            } else {
     1259                if ((subTier >> 1) != (subTierMode & 0x01))
     1260                    continue;
     1261            }
     1262            boolean ok = isSelectable(peer);
     1263            if (ok)
     1264                matches.add(peer);
     1265            else
     1266                matches.remove(peer);
     1267        }
     1268    }
     1269   
     1270    /**
     1271     *  Implement a random, deterministic split into 4 groups that cannot be predicted by
     1272     *  others.
     1273     *  @return 0-3
     1274     */
     1275    private static int getSubTier(Hash peer, Hash randomKey) {
     1276        byte[] data = new byte[Hash.HASH_LENGTH + 4];
     1277        System.arraycopy(peer.getData(), 0, data, 0, Hash.HASH_LENGTH);
     1278        System.arraycopy(randomKey.getData(), 0, data, Hash.HASH_LENGTH, 4);
     1279        Hash rh = SHA256Generator.getInstance().calculateHash(data);
     1280        return rh.getData()[0] & 0x03;
    11751281    }
    11761282
     
    12891395    protected int getMinimumFastPeers() {
    12901396        int def = Math.min(DEFAULT_MAXIMUM_FAST_PEERS,
    1291                            (2 *_context.clientManager().listClients().size()) + DEFAULT_MINIMUM_FAST_PEERS - 2);
     1397                           (6 *_context.clientManager().listClients().size()) + DEFAULT_MINIMUM_FAST_PEERS - 2);
    12921398        return _context.getProperty(PROP_MINIMUM_FAST_PEERS, def);
    12931399    }
  • router/java/src/net/i2p/router/tunnel/pool/ClientPeerSelector.java

    r5ce06d02 rf965466  
    2222        if ( (length == 0) && (settings.getLength()+settings.getLengthVariance() > 0) )
    2323            return null;
    24         HashSet matches = new HashSet(length);
     24
     25        List<Hash> rv;
    2526   
    2627        if (length > 0) {
    2728            if (shouldSelectExplicit(settings))
    2829                return selectExplicit(ctx, settings, length);
     30       
     31            Set<Hash> exclude = getExclude(ctx, settings.isInbound(), settings.isExploratory());
     32            Set<Hash> matches = new HashSet(length);
     33            if (length == 1) {
     34                ctx.profileOrganizer().selectFastPeers(length, exclude, matches, 0);
     35                matches.remove(ctx.routerHash());
     36                rv = new ArrayList(matches);
     37            } else {
     38                // build a tunnel using 4 subtiers.
     39                // For a 2-hop tunnel, the first hop comes from subtiers 0-1 and the last from subtiers 2-3.
     40                // For a longer tunnels, the first hop comes from subtier 0, the middle from subtiers 2-3, and the last from subtier 1.
     41                rv = new ArrayList(length + 1);
     42                // OBEP or IB last hop
     43                // group 0 or 1 if two hops, otherwise group 0
     44                ctx.profileOrganizer().selectFastPeers(1, exclude, matches, settings.getRandomKey(), length == 2 ? 2 : 4);
     45                matches.remove(ctx.routerHash());
     46                exclude.addAll(matches);
     47                rv.addAll(matches);
     48                matches.clear();
     49                if (length > 2) {
     50                    // middle hop(s)
     51                    // group 2 or 3
     52                    ctx.profileOrganizer().selectFastPeers(length - 2, exclude, matches, settings.getRandomKey(), 3);
     53                    matches.remove(ctx.routerHash());
     54                    if (matches.size() > 1) {
     55                        // order the middle peers for tunnels >= 4 hops
     56                        List<Hash> ordered = new ArrayList(matches);
     57                        orderPeers(ordered, settings.getRandomKey());
     58                        rv.addAll(ordered);
     59                    } else {
     60                        rv.addAll(matches);
     61                    }
     62                    exclude.addAll(matches);
     63                    matches.clear();
     64                }
     65                // IBGW or OB first hop
     66                // group 2 or 3 if two hops, otherwise group 1
     67                ctx.profileOrganizer().selectFastPeers(1, exclude, matches, settings.getRandomKey(), length == 2 ? 3 : 5);
     68                matches.remove(ctx.routerHash());
     69                rv.addAll(matches);
     70            }
     71        } else {
     72            rv = new ArrayList(1);
    2973        }
    3074       
    31         Set exclude = getExclude(ctx, settings.isInbound(), settings.isExploratory());
    32         ctx.profileOrganizer().selectFastPeers(length, exclude, matches, settings.getIPRestriction());
    33        
    34         matches.remove(ctx.routerHash());
    35         ArrayList<Hash> rv = new ArrayList(matches);
    36         if (rv.size() > 1)
    37             orderPeers(rv, settings.getRandomKey());
    3875        if (settings.isInbound())
    3976            rv.add(0, ctx.routerHash());
  • router/java/src/net/i2p/router/tunnel/pool/TunnelPeerSelector.java

    r5ce06d02 rf965466  
    4242    public abstract List<Hash> selectPeers(RouterContext ctx, TunnelPoolSettings settings);
    4343   
     44    /**
     45     *  @return randomized number of hops 0-7, not including ourselves
     46     */
    4447    protected int getLength(RouterContext ctx, TunnelPoolSettings settings) {
    4548        int length = settings.getLength();
     
    6265        if (length < 0)
    6366            length = 0;
    64         else if (length > 8) // as documented in tunnel.html
    65             length = 8;
     67        else if (length > 7) // as documented in tunnel.html
     68            length = 7;
    6669        /*
    6770        if ( (ctx.tunnelManager().getOutboundTunnelCount() <= 0) ||
Note: See TracChangeset for help on using the changeset viewer.