Run-Based Trie Involving the Structure of Arbitrary Bitmask Rules

• MIKAWA Kenji

  Center for Academic Information Service, Niigata University

• TANAKA Ken

  Faculty of Science, Kanagawa University

抄録

Packet classification is a fundamental task in the control of network traffic, protection from cyber threats. Most layer 3 and higher network devices have a packet classification capability that determines whether to permit or discard incoming packets by comparing their headers with a set of rules. Although linear search is an intuitive implementation of packet classification, it is very inefficient. Srinivasan et al. proposed a novel lookup scheme using a hierarchical trie instead of linear search, which realizes faster packet classification with time complexity proportional to rule length rather than the number of rules. However, the hierarchical trie and its various improved algorithms allow only single prefix rules to be processed. Since it is necessary for layer 4 and higher packet classifications to deal with arbitrary bitmask rules in the hierarchical trie, we propose a run-based trie based on the hierarchical trie, but extended to deal with arbitrary bitmask rules. Our proposed algorithm achieves O((dW)²) query time and O(N^dW) space complexity with N rules of length dW. The query time of our novel alrorithm doesn't depend on the number of rules. It solves the latency problem caused by increase of the rules in firewalls.

収録刊行物

• IEICE Transactions on Information and Systems

  IEICE Transactions on Information and Systems E98.D (6), 1206-1212, 2015

  一般社団法人 電子情報通信学会

キーワード

• packet classification
• hierarchical trie
• decision tree
• arbitrary bitmask
• theoretical analysis

詳細情報

• CRID: 1390282679355204864
• NII論文ID: 130005072406
• DOI: 10.1587/transinf.2013edp7087
• ISSN: 17451361
• ISSN: 09168532
• Web Site: https://www.jstage.jst.go.jp/article/transinf/E98.D/6/E98.D_2013EDP7087/_pdf
• 本文言語コード: en
• データソース種別:
  • JaLC
  • Crossref
  • CiNii Articles
  • KAKEN
• 抄録ライセンスフラグ: 使用不可