Changeset 9931112


Ignore:
Timestamp:
Oct 2, 2009 3:14:16 AM (11 years ago)
Author:
zzz <zzz@…>
Branches:
master
Children:
fe3abc7
Parents:
1cd646a
Message:
  • Tunnel IVValidator: Increase size of bloom filter for high-bw routers (≥ 512KBps share bw) to reduce false positive rate. Adds 2MB heap for ≥ 512KBps routers and 6MB for ≥ 1536KBps.
Files:
5 edited

Legend:

Unmodified
Added
Removed
  • core/java/src/net/i2p/util/DecayingBloomFilter.java

    r1cd646a r9931112  
    3838   
    3939    private static final int DEFAULT_M = 23;
     40    private static final int DEFAULT_K = 11;
    4041    private static final boolean ALWAYS_MISS = false;
    4142   
     
    5758    /** @param name just for logging / debugging / stats */
    5859    public DecayingBloomFilter(I2PAppContext context, int durationMs, int entryBytes, String name) {
     60        // this is instantiated in four different places, they may have different
     61        // requirements, but for now use this as a gross method of memory reduction.
     62        // m == 23 => 1MB each BloomSHA1 (4 pairs = 8MB total)
     63        this(context, durationMs, entryBytes, name, context.getProperty("router.decayingBloomFilterM", DEFAULT_M));
     64    }
     65
     66    /** @param m filter size exponent */
     67    public DecayingBloomFilter(I2PAppContext context, int durationMs, int entryBytes, String name, int m) {
    5968        _context = context;
    6069        _log = context.logManager().getLog(DecayingBloomFilter.class);
    6170        _entryBytes = entryBytes;
    6271        _name = name;
    63         // this is instantiated in four different places, they may have different
    64         // requirements, but for now use this as a gross method of memory reduction.
    65         // m == 23 => 1MB each BloomSHA1 (4 pairs = 8MB total)
    66         int m = context.getProperty("router.decayingBloomFilterM", DEFAULT_M);
    67         _current = new BloomSHA1(m, 11); //new BloomSHA1(23, 11);
    68         _previous = new BloomSHA1(m, 11); //new BloomSHA1(23, 11);
     72        int k = DEFAULT_K;
     73        // max is (23,11) or (26,10); see KeySelector for details
     74        if (m > DEFAULT_M)
     75            k--;
     76        _current = new BloomSHA1(m, k);
     77        _previous = new BloomSHA1(m, k);
    6978        _durationMs = durationMs;
    7079        int numExtenders = (32+ (entryBytes-1))/entryBytes - 1;
     
    8493        SimpleTimer.getInstance().addEvent(_decayEvent, _durationMs);
    8594        if (_log.shouldLog(Log.WARN))
    86            _log.warn("New DBF " + name + " m = " + m + " entryBytes = " + entryBytes +
     95           _log.warn("New DBF " + name + " m = " + m + " k = " + k + " entryBytes = " + entryBytes +
    8796                     " numExtenders = " + numExtenders + " cycle (s) = " + (durationMs / 1000));
    8897        // try to get a handle on memory usage vs. false positives
     
    261270   
    262271    /**
     272     *  This filter is used only for participants and OBEPs, not
     273     *  IBGWs, so depending on your assumptions of avg. tunnel length,
     274     *  the performance is somewhat better than the gross share BW
     275     *  would indicate.
     276     *
     277     *  Following stats for m=23, k=11:
    263278     *  Theoretical false positive rate for   16 KBps: 1.17E-21
    264279     *  Theoretical false positive rate for   24 KBps: 9.81E-20
     
    267282     *  Theoretical false positive rate for  512 KBps: 5.32E-6
    268283     *  Theoretical false positive rate for 1024 KBps: 1.48E-3
     284     *  Then it gets bad: 1280 .67%; 1536 2.0%; 1792 4.4%; 2048 8.2%.
     285     *
     286     *  Following stats for m=24, k=10:
     287     *  1280 4.5E-5; 1792 5.6E-4; 2048 0.14%
     288     *
     289     *  Following stats for m=25, k=10:
     290     *  1792 2.4E-6; 4096 0.14%
    269291     */
    270292    public static void main(String args[]) {
  • core/java/src/org/xlattice/crypto/filters/BloomSHA1.java

    r1cd646a r9931112  
    4848    protected final int filterWords;
    4949   
     50/* (24,11) too big - see KeySelector
     51
    5052    public static void main(String args[]) {
    5153        BloomSHA1 b = new BloomSHA1(24, 11);
     
    5658        }
    5759    }
     60*/
    5861   
    5962   
     
    6265     * each hash function is portion of the 160-bit SHA1 hash.   
    6366
    64      * @param m determines number of bits in filter, defaults to 20
    65      * @param k number of hash functions, defaults to 8
     67     * @param m determines number of bits in filter
     68     * @param k number of hash functionsx
     69     *
     70     * See KeySelector for important restriction on max m and k
    6671     */
    6772    public BloomSHA1( int m, int k) {
  • core/java/src/org/xlattice/crypto/filters/KeySelector.java

    r1cd646a r9931112  
    5252     * @param bitOffset array of k bit offsets (offset of flag bit in word)
    5353     * @param wordOffset array of k word offsets (offset of word flag is in)
     54     *
     55     * Note that if k and m are too big, the GenericWordSelector blows up -
     56     * The max for 32-byte keys is m=23 and k=11.
     57     * The precise restriction appears to be:
     58     * ((5k + (k-1)(m-5)) / 8) + 2 < keySizeInBytes
     59     *
     60     * It isn't clear how to fix this.
    5461     */
    5562    public KeySelector (int m, int k, int[] bitOffset, int [] wordOffset) {
     
    122129    /**
    123130     * Extracts the k word offsets from a key.  Suitable for general
    124      * values of m and k.
     131     * values of m and k. See above for formula for max m and k.
    125132     */
    126133    public class GenericWordSelector implements WordSelector {
     
    177184                        bitsToGet -= 8;
    178185                        if (bitsToGet > 0) {
     186                            // AIOOBE here if m and k too big (23,11 is the max)
     187                            // for a 32-byte key - see above
    179188                            wordOffset[j] |=
    180189                                ((0xff & b[curByte + 2]) >> (8 - bitsToGet))
  • router/java/src/net/i2p/router/tunnel/BloomFilterIVValidator.java

    r1cd646a r9931112  
    2626    private static final int HALFLIFE_MS = 10*60*1000;
    2727    private static final int MIN_SHARE_KBPS_TO_USE_BLOOM = 64;
     28    private static final int MIN_SHARE_KBPS_FOR_BIG_BLOOM = 512;
     29    private static final int MIN_SHARE_KBPS_FOR_HUGE_BLOOM = 1536;
    2830
    2931    public BloomFilterIVValidator(RouterContext ctx, int KBps) {
    3032        _context = ctx;
    3133        // Select the filter based on share bandwidth.
    32         // Note that at rates approaching 1MB, we need to do something else,
    33         // as the Bloom filter false positive rates approach 0.1%. FIXME
    34         if (getShareBandwidth(ctx) < MIN_SHARE_KBPS_TO_USE_BLOOM)
     34        // Note that at rates above 512KB, we increase the filter size
     35        // to keep acceptable false positive rates.
     36        // See DBF, BloomSHA1, and KeySelector for details.
     37        if (KBps < MIN_SHARE_KBPS_TO_USE_BLOOM)
    3538            _filter = new DecayingHashSet(ctx, HALFLIFE_MS, 16, "TunnelIVV"); // appx. 4MB max
     39        else if (KBps >= MIN_SHARE_KBPS_FOR_HUGE_BLOOM)
     40            _filter = new DecayingBloomFilter(ctx, HALFLIFE_MS, 16, "TunnelIVV", 25);  // 8MB fixed
     41        else if (KBps >= MIN_SHARE_KBPS_FOR_BIG_BLOOM)
     42            _filter = new DecayingBloomFilter(ctx, HALFLIFE_MS, 16, "TunnelIVV", 24);  // 4MB fixed
    3643        else
    3744            _filter = new DecayingBloomFilter(ctx, HALFLIFE_MS, 16, "TunnelIVV");  // 2MB fixed
     
    4956    }
    5057    public void destroy() { _filter.stopDecaying(); }
    51 
    52     private static int getShareBandwidth(RouterContext ctx) {
    53         int irateKBps = ctx.bandwidthLimiter().getInboundKBytesPerSecond();
    54         int orateKBps = ctx.bandwidthLimiter().getOutboundKBytesPerSecond();
    55         double pct = ctx.router().getSharePercentage();
    56         return (int) (pct * Math.min(irateKBps, orateKBps));
    57     }
    5858}
  • router/java/src/net/i2p/router/tunnel/TunnelDispatcher.java

    r1cd646a r9931112  
    681681
    682682    public void startup() {
    683         // NB: 256 == assume max rate (size adjusted to handle 256 messages per second)
    684         _validator = new BloomFilterIVValidator(_context, 256);
    685     }
     683        // Note that we only use the validator for participants and OBEPs, not IBGWs, so
     684        // this BW estimate will be high by about 33% assuming 2-hop tunnels average
     685        _validator = new BloomFilterIVValidator(_context, getShareBandwidth(_context));
     686    }
     687
     688    private static int getShareBandwidth(RouterContext ctx) {
     689        int irateKBps = ctx.bandwidthLimiter().getInboundKBytesPerSecond();
     690        int orateKBps = ctx.bandwidthLimiter().getOutboundKBytesPerSecond();
     691        double pct = ctx.router().getSharePercentage();
     692        return (int) (pct * Math.min(irateKBps, orateKBps));
     693    }
     694
    686695    public void shutdown() {
    687696        if (_validator != null)
Note: See TracChangeset for help on using the changeset viewer.