Bloom filter based acceleration scheme for flow table lookup in SDN switches
Flow table lookup is a well-known bottleneck in software-defined network switches. Associative lookup is the fastest but most costly method. On the other hand, an approximate flow classification based on Bloom filters has an outstanding cost-benefit ratio but comes with a downside of false-positive results. Therefore, we propose a new flow table lookup scheme based on Bloom filters and RAM, which offers a good compromise between cost and performance. We solve the problem of false positives of primary Bloom filters by verifying the results and, if necessary, by linearly searching the contents of secondary RAM. Also, we provide a practical implementation in the FPGA-based SDN switch and experimentally show that the proposed solution can achieve better performance than the classic linear search at the low cost typical of Bloom filters.