A fast flow table engine for Open vSwitch with high performance on both lookups and updates

To support fast rule updates in SDN, the Open vSwitch uses a variant of Tuple Space Search (TSS) for flow table lookups, which is less efficient than decision trees on packet classifications. In this poster, we present our latest work on building fast flow table engine in Open vSwitch, which achieves high-speed table lookups and fast rule updates simultaneously. By mapping rules into tree nodes dynamically, a very limited TSS-assisted balanced trees can be generated without the trouble of rule replications. Preliminary experimental results show that using ClassBench, our work has comparable update performance to the TSS algorithm in Open vSwitch, while achieving almost an order-of-magnitude improvement on lookup performance over TSS on average.