A Packet Classification Method via Cascaded Circular-Run-Based Trie

Takashi HARADA  Yuki ISHIKAWA  Ken TANAKA  Kenji MIKAWA  

Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E102-A   No.9   pp.1171-1178
Publication Date: 2019/09/01
Online ISSN: 1745-1337
DOI: 10.1587/transfun.E102.A.1171
Type of Manuscript: Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
Category: Classification
Keyword: 
packet classification,  trie,  consecutive ones property,  circular ones property,  

Full Text: PDF(1.4MB)>>
Buy this Article




Summary: 
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 [1] 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 [2] show that our method classifies packets in constant time independent of the number of rules.