A Method for Computing the Number of Packets Matching a Filtering Rule

Takashi HARADA  Ken TANAKA  Kenji MIKAWA  

D - Abstracts of IEICE TRANSACTIONS on Information and Systems (Japanese Edition)   Vol.J101-D   No.3   pp.522-529
Publication Date: 2018/03/01
Online ISSN: 1881-0225
Type of Manuscript: Special Section PAPER (Special Section on Student Research)
packet filtering,  optimizing rule ordering,  MTZDD,  weights of rules,  

Full Text(in Japanese): PDF(585.2KB)
>>Buy this Article

A filtering policy is denoted as a filtering rule list and is achieved by linear search of the rule list. Various methods of optimizing the rule ordering have been developed. However in the optimizing methods, assignments of the weight are inappropriate. In this paper, we prove that the problem of computing the number of packets that match a filtering rule is #P-complete and propose two methods. One uses the Multi-terminal Zero-suppressed Binary Decision Diagrams (MTZDDs) and the other runs in polynomial time in the number of rules for prefix rules.