TabTree: A TSS-assisted bit-selecting tree scheme for packet classification with balanced rule mapping

Wenjun Li, Tong Yang, Yeim Kuan Chang, Tao Li, Hui Li

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

1 Citation (Scopus)

Abstract

To support fast rule updates in SDN, the Open vSwitch implements Priority Sorting Tuple Space Search (PSTSS) for its packet classifications. Although it has good performance on rule updates, it has a performance concern on table lookups. In contrast, decision tree methods are being actively investigated for high throughput, but they are not able to support fast updates because of rule replications. CutSplit, the state-of-the-art decision tree scheme, provides a novel rule update mechanism by avoiding tree reconstructions. However, its average update time is still two orders of magnitude larger than PSTSS. Meanwhile, existing decision trees are not only unbalanced but also depth unbounded, making them difficult to be optimized on FPGA. In this paper, we present a new decision tree scheme called TabTree, which achieves high performance on both lookups and updates. By mapping rules into tree nodes dynamically, a very limited number of balanced trees with bounded depths can be generated without the trouble of rule replications. Experimental results show that, TabTree has comparable update performance to PSTSS, but it outperforms PSTSS significantly in terms of number of memory accesses for packet classification. Additionally, TabTree is more practical for implementations on FPGA.

Original languageEnglish
Title of host publication2019 ACM/IEEE Symposium on Architectures for Networking and Communications Systems, ANCS 2019
PublisherInstitute of Electrical and Electronics Engineers Inc.
ISBN (Electronic)9781728143873
DOIs
Publication statusPublished - 2019 Sep
Event2019 ACM/IEEE Symposium on Architectures for Networking and Communications Systems, ANCS 2019 - Cambridge, United Kingdom
Duration: 2019 Sep 242019 Sep 25

Publication series

Name2019 ACM/IEEE Symposium on Architectures for Networking and Communications Systems, ANCS 2019

Conference

Conference2019 ACM/IEEE Symposium on Architectures for Networking and Communications Systems, ANCS 2019
CountryUnited Kingdom
CityCambridge
Period19-09-2419-09-25

All Science Journal Classification (ASJC) codes

  • Computer Networks and Communications
  • Hardware and Architecture
  • Software

Fingerprint Dive into the research topics of 'TabTree: A TSS-assisted bit-selecting tree scheme for packet classification with balanced rule mapping'. Together they form a unique fingerprint.

  • Cite this

    Li, W., Yang, T., Chang, Y. K., Li, T., & Li, H. (2019). TabTree: A TSS-assisted bit-selecting tree scheme for packet classification with balanced rule mapping. In 2019 ACM/IEEE Symposium on Architectures for Networking and Communications Systems, ANCS 2019 [8901884] (2019 ACM/IEEE Symposium on Architectures for Networking and Communications Systems, ANCS 2019). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/ANCS.2019.8901884