SnabbCo/snabbswitch — pull request #333 by alexandergall (2014-12-04 14:13:08+00:00)
Title: Learning bridge based on Bloom filter

This change set provides two variants of multiport bridges with split-horizon semantics. The first variant is a simple "flooding" bridge that replicates a packet on all outpbound ports.

So far, Snabb Switch is missing an efficient way (without unnecessary copying of buffers) to replicate ("clone") a packet. I suggested a "copy-on-write" method some time ago in the thread https://groups.google.com/d/msg/snabb-devel/b6CFaGTu-Y8/jqSaZ2lpIL4J but didn't get any feedback. I propose the same thing again here.

The second variant implements MAC-learning based on a Bloom filter to limit packet replication. The Bloom filter uses an implementation of the "Murmur3" class of hash functions. I've chosen this method because it's fairly simple and has nice scaling properties (insertion and lookup is of O(1) with respect to the number of objects already in the filter).

A fundamental property of a Bloom filter is the existence of false-positives when checking whether an object is contained in the filter. This can lead to unnecessary packet replication, but the maximum false-positive rate can be configured. The formula to calculate the size and number of "rounds" for a filter is in the comment at the top of lib.bloom_filter. For example, a filter that shall contain at most 1000 objects with a false-positive rate of at most 0.001 takes 2KiB of memory and requires 12 rounds.

I've spent some time making sure that this stuff performs well. Here are some ballpark figures for the amount of CPU cycles for various operations on 6-byte values (i.e. a MAC address).

One pass of the hash function requires about 25 cycles. Bloom filter operations directly on MAC addresses require two passes of the hash function plus between 10 and 15 cycles per round. All together, the amount of CPU cycles per packet for an n-port learning bridge using a Bloom filter with k cycles is roughly given by

100 + k*(35 + n*10)

Thats a fixed amount of 100+k*35 plus a per-port cost of k*n*10 cycles. For example, a 4-port bridge with k=12 will require about 1000 cycles. This limits the throughput to about 1Mpps on a core running at 2GHz. And remember, this overhead is independent of the number of learned MAC addresses :)