loop detection using Bloom filters

[marten-seemann]

This might be a crazy idea: Loop detection could be implemented using a Bloom filter.

Over a certain period of time, the proxy would insert every packet it forwards into a bloom filter. How big would this filter need to be? Let's say you want to insert all packets seen within a time frame of 5s at a speed of 10 Gbps (assuming an MTU of ~1400). At a false positive rate of 1e-6 (rejecting 1 packet in a million), you'd need ~120 MB: https://hur.st/bloomfilter/?n=35M&p=1.0E-6&m=&k=.

This would allow the proxy to detect all loops with an RTT of less than 5s. This period can be extended by either enlarging the size of the bloom filter, or by keeping the N most recent bloom filters around.

Proxies could also get a bit more advanced in their detection logic. For example, they could decide to only drop duplicate packets once the rate of duplicates surpasses a certain threshold (there's no harm in forwarding a few looped packets, as long as the volume is low enough).

[martinduke]

Interesting idea!

But doesn't the packet transform make it hard to detect duplicate packets?