For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
A Packet Classification Method via Cascaded Circular-Run-Based Trie
Takashi HARADA Yuki ISHIKAWA Ken TANAKA Kenji MIKAWA
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 2019/09/01
Online ISSN: 1745-1337
Type of Manuscript: Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
packet classification, trie, consecutive ones property, circular ones property,
Full Text: PDF(1.4MB)>>
The packet classification problem to determine the behavior of incoming packets at the network devices. The processing latency of packet classification by linear search is proportional to the number of classification rules. To limit the latency caused by classification to a certain level, we should develop a classification algorithm that classifies packets in a time independent of the number of classification rules. Arbitrary (including noncontiguous) bitmask rules are efficiently expressive for controlling higher layer communication, achiving access control lists, Quality of Service and so on. In this paper, we propose a classification algorithm based on run-based trie  according to arbitrary bitmask rules. The space complexity of proposed algorithm is in linear in the size of a rule list. The time complexity except for construction of that can be regarded as constant which is independent the number of rules. Experimental results using a packet classification algorithm benchmark  show that our method classifies packets in constant time independent of the number of rules.