  We propose Range-based Ternary Search Tree (RTST), a tree-based approach for
flow-table lookup in SDN network. RTST builds upon flow-tables in SDN switches
to provide a fast lookup among flows. We present a parallel multi-pipeline
architecture for implementing RTST that benefits from high throughput and low
latency. The proposed RTST and architecture achieve a memory efficiency of 1
byte of memory for each byte of flow. We also present a set of techniques to
support dynamic updates. Experimental results show that RTST can be used to
improve the performance of flow-lookup. It achieves a throughput of 670 Million
Packets Per Second (MPPS), for a 1 K 15-tuple flow-table, on a state-of-the-art
FPGA.
