Simulated Annealing Method for Relaxed Optimal Rule Ordering

Takashi HARADA  Ken TANAKA  Kenji MIKAWA  

IEICE TRANSACTIONS on Information and Systems   Vol.E103-D   No.3   pp.509-515
Publication Date: 2020/03/01
Online ISSN: 1745-1361
DOI: 10.1587/transinf.2019FCP0006
Type of Manuscript: Special Section PAPER (Special Section on Foundations of Computer Science — Frontiers of Theory of Computation and Algorithm —)
packet classification,  relaxed optimal rule ordering,  NP-hard,  simulated annealing,  zero-suppressed binary decision diagram,  

Full Text: PDF(544.4KB)>>
Buy this Article

Recent years have witnessed a rapid increase in cyber-attacks through unauthorized accesses and DDoS attacks. Since packet classification is a fundamental technique to prevent such illegal communications, it has gained considerable attention. Packet classification is achieved with a linear search on a classification rule list that represents the packet classification policy. As such, a large number of rules can result in serious communication latency. To decrease this latency, the problem is formalized as optimal rule ordering (ORO). In most cases, this problem aims to find the order of rules that minimizes latency while satisfying the dependency relation of the rules, where rules ri and rj are dependent if there is a packet that matches both ri and rj and their actions applied to packets are different. However, there is a case in which although the ordering violates the dependency relation, the ordering satisfies the packet classification policy. Since such an ordering can decrease the latency compared to an ordering under the constraint of the dependency relation, we have introduced a new model, called relaxed optimal rule ordering (RORO). In general, it is difficult to determine whether an ordering satisfies the classification policy, even when it violates the dependency relation, because this problem contains unsatisfiability. However, using a zero-suppressed binary decision diagram (ZDD), we can determine it in a reasonable amount of time. In this paper, we present a simulated annealing method for RORO which interchanges rules by determining whether rules ri and rj can be interchanged in terms of policy violation using the ZDD. The experimental results show that our method decreases latency more than other heuristics.