Fast packet classification on OpenFlow switches using multiple R*-tree based bitmap intersection

In order to accomplish a stringent speed requirement for processing internet services such as Access Control List (ACL), Quality of Service (QoS), firewalls, etc., software based OpenFlow switches must have a fast packet classification capability. Even for hardware based OpenFlow switches, a limited size of Ternary Content Addressable Memory (TCAM) in the switch could be only enough for a forwarding table. Therefore, ACL, firewall tables, etc. need to be implemented by using the memory of the switch CPU. However, it has become a great challenge to build extremely effectively for next-generation software based packet classification that supports higher throughput and larger flow entries in OpenFlow switch. This paper first exploits a fast packet classification algorithm that forms a R*-Tree based Bitmap Intersection and secondly discusses an enhanced R*-Tree based Bitmap Intersection by using Bloom Filter and Multiple R*-Tree. The evaluation results show that the performance of the algorithm in OpenFlow switches is 4.42 times of Bitmap Intersection and 5.16 times of R*-Tree algorithm and consumes only 300 KB of memory space, which is much less than that of other methods. Finally, the use of multiple R*-Trees has further improved memory usage by about 30%.