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

Ding Fong Huang, Chien Chen, Mahadevan Thanavel

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

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%.

Original languageEnglish
Title of host publicationIEEE/IFIP Network Operations and Management Symposium
Subtitle of host publicationCognitive Management in a Cyber World, NOMS 2018
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages1-9
Number of pages9
ISBN (Electronic)9781538634165
DOIs
StatePublished - 6 Jul 2018
Event2018 IEEE/IFIP Network Operations and Management Symposium, NOMS 2018 - Taipei, Taiwan
Duration: 23 Apr 201827 Apr 2018

Publication series

NameIEEE/IFIP Network Operations and Management Symposium: Cognitive Management in a Cyber World, NOMS 2018

Conference

Conference2018 IEEE/IFIP Network Operations and Management Symposium, NOMS 2018
CountryTaiwan
CityTaipei
Period23/04/1827/04/18

Keywords

  • -Tree
  • Bitmap intersection
  • Bloom filter
  • Openflow
  • Packet classification
  • R
  • Software defined networking (SDN)

Fingerprint Dive into the research topics of 'Fast packet classification on OpenFlow switches using multiple R∗-tree based bitmap intersection'. Together they form a unique fingerprint.

  • Cite this

    Huang, D. F., Chen, C., & Thanavel, M. (2018). Fast packet classification on OpenFlow switches using multiple R∗-tree based bitmap intersection. In IEEE/IFIP Network Operations and Management Symposium: Cognitive Management in a Cyber World, NOMS 2018 (pp. 1-9). (IEEE/IFIP Network Operations and Management Symposium: Cognitive Management in a Cyber World, NOMS 2018). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/NOMS.2018.8406227