Overview | Package | Class | Use | Tree | Deprecated | Index | Help
PREV CLASS NEXT CLASS | FRAMES NO FRAMES
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD

## net.i2p.util
Class DecayingBloomFilter

    java.lang.Object
      net.i2p.util.DecayingBloomFilter

Direct Known Subclasses:
  DecayingHashSet

    public class DecayingBloomFilter

extends Object

Series of bloom filters which decay over time, allowing their continual use for time sensitive data. This has a fixed size (currently 1MB per decay period, using two periods overall), allowing this to pump through hundreds of entries per second with virtually no false positive rate. Down the line, this may be refactored to allow tighter control of the size necessary for the contained bloom filters, but a fixed 2MB overhead isn't that bad. NOTE: At 1MBps, the tunnel IVV will see an unacceptable false positive rate of almost 0.1% with the current m and k values; however using DHS instead will use 30MB. Further analysis and tweaking for the tunnel IVV may be required.

Field Summary
`protected I2PAppContext` | `_context`
`protected long` | `_currentDuplicates`
`protected SimpleTimer.TimedEvent` | `_decayEvent`
`protected int` | `_durationMs`
`protected int` | `_entryBytes`
`protected boolean` | `_keepDecaying`
`protected Log` | `_log`
`protected String` | `_name` just for logging

Constructor Summary
`` | `DecayingBloomFilter(I2PAppContext context, int durationMs, int entryBytes)` Create a bloom filter that will decay its entries over time.
`` | `DecayingBloomFilter(I2PAppContext context, int durationMs, int entryBytes, String name)`
`` | `DecayingBloomFilter(I2PAppContext context, int durationMs, int entryBytes, String name, int m)`
`protected` | `DecayingBloomFilter(int durationMs, int entryBytes, String name, I2PAppContext context)` only for extension by DHS

Method Summary
`boolean` | `add(byte[] entry)`
`boolean` | `add(byte[] entry, int off, int len)`
`boolean` | `add(long entry)`
`void` | `clear()`
`long` | `getCurrentDuplicateCount()`
`double` | `getFalsePositiveRate()`
`int` | `getInsertedCount()`
`boolean` | `isKnown(long entry)`
`static void` | `main(String[] args)` This filter is used only for participants and OBEPs, not IBGWs, so depending on your assumptions of avg.
`void` | `stopDecaying()`

Methods inherited from class java.lang.Object
`clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait`

Field Detail

### _context

    protected final I2PAppContext _context

### _log

    protected final Log _log

### _durationMs

    protected final int _durationMs

### _entryBytes

    protected final int _entryBytes

### _currentDuplicates

    protected long _currentDuplicates

### _keepDecaying

    protected volatile boolean _keepDecaying

### _decayEvent

    protected SimpleTimer.TimedEvent _decayEvent

### _name

    protected final String _name

  just for logging

Constructor Detail

### DecayingBloomFilter

    protected DecayingBloomFilter(int durationMs,
                                  int entryBytes,
                                  String name,
                                  I2PAppContext context)

  only for extension by DHS

### DecayingBloomFilter

    public DecayingBloomFilter(I2PAppContext context,
                               int durationMs,
                               int entryBytes)

  Create a bloom filter that will decay its entries over time.

  Parameters:
    `durationMs` - entries last for at least this long, but no more than twice this long
    `entryBytes` - how large are the entries to be added? if this is less than 32 bytes, the entries added will be expanded by concatenating their XORing against with sufficient random values.

### DecayingBloomFilter

    public DecayingBloomFilter(I2PAppContext context,
                               int durationMs,
                               int entryBytes,
                               String name)

Parameters:
  `name` - just for logging / debugging / stats

### DecayingBloomFilter

    public DecayingBloomFilter(I2PAppContext context,
                               int durationMs,
                               int entryBytes,
                               String name,
                               int m)

Parameters:
  `m` - filter size exponent

Method Detail

### getCurrentDuplicateCount

    public long getCurrentDuplicateCount()

### getInsertedCount

    public int getInsertedCount()

### getFalsePositiveRate

    public double getFalsePositiveRate()

### add

    public boolean add(byte[] entry)

  Returns:
    true if the entry added is a duplicate

### add

    public boolean add(byte[] entry,
                       int off,
                       int len)

  Returns:
    true if the entry added is a duplicate

### add

    public boolean add(long entry)

  Returns:
    true if the entry added is a duplicate. the number of low order bits used is determined by the entryBytes parameter used on creation of the filter.

### isKnown

    public boolean isKnown(long entry)

  Returns:
    true if the entry is already known. this does NOT add the entry however.

### clear

    public void clear()

### stopDecaying

    public void stopDecaying()

### main

    public static void main(String[] args)

  This filter is used only for participants and OBEPs, not IBGWs, so depending on your assumptions of avg. tunnel length, the performance is somewhat better than the gross share BW would indicate. Following stats for m=23, k=11: Theoretical false positive rate for 16 KBps: 1.17E-21 Theoretical false positive rate for 24 KBps: 9.81E-20 Theoretical false positive rate for 32 KBps: 2.24E-18 Theoretical false positive rate for 256 KBps: 7.45E-9 Theoretical false positive rate for 512 KBps: 5.32E-6 Theoretical false positive rate for 1024 KBps: 1.48E-3 Then it gets bad: 1280 .67%; 1536 2.0%; 1792 4.4%; 2048 8.2%. Following stats for m=24, k=10: 1280 4.5E-5; 1792 5.6E-4; 2048 0.14% Following stats for m=25, k=10: 1792 2.4E-6; 4096 0.14%

Overview | Package | Class | Use | Tree | Deprecated | Index | Help
PREV CLASS NEXT CLASS | FRAMES NO FRAMES
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD