Run-Based Trie Involving the Structure of Arbitrary Bitmask Rules

Access this Article



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 <i>et al.</i> 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 <i>run-based trie</i> based on the hierarchical trie, but extended to deal with arbitrary bitmask rules. Our proposed algorithm achieves <i>O</i>((<i>dW</i>)<sup>2</sup>) query time and <i>O</i>(<i>N<sup>dW</sup></i>) space complexity with <i>N</i> rules of length <i>dW</i>. 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

    The Institute of Electronics, Information and Communication Engineers


Page Top