Computational Complexity of Allow Rule Ordering and Its Greedy Algorithm

Takashi FUCHINO; Takashi HARADA; Ken TANAKA; Kenji MIKAWA

doi:10.1587/transfun.2022DMP0006

Computational Complexity of Allow Rule Ordering and Its Greedy Algorithm

Takashi FUCHINO, Takashi HARADA, Ken TANAKA, Kenji MIKAWA

Full Text Views

0

Cite this

Summary :

Packet classification is used to determine the behavior of incoming packets in network devices according to defined rules. As it is achieved using a linear search on a classification rule list, a large number of rules will lead to longer communication latency. To solve this, the problem of finding the order of rules minimizing the latency has been studied. Misherghi et al. and Harada et al. have proposed a problem that relaxes to policy-based constraints. In this paper, we show that the Relaxed Optimal Rule Ordering (RORO) for the allowlist is NP-hard, and by reducing from this we show that RORO for the general rule list is NP-hard. We also propose a heuristic algorithm based on the greedy method for an allowlist. Furthermore, we demonstrate the effectiveness of our method using ClassBench, which is a benchmark for packet classification algorithms.

Publication: IEICE TRANSACTIONS on Fundamentals Vol.E106-A No.9 pp.1111-1118

Publication Date: 2023/09/01

Publicized: 2023/03/20

Online ISSN: 1745-1337

DOI: 10.1587/transfun.2022DMP0006

Type of Manuscript: Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)

Category: Algorithms and Data Structures

Authors

Takashi FUCHINO
  Kanagawa University
Takashi HARADA
  Kochi University of Technology
Ken TANAKA
  Kanagawa University
Kenji MIKAWA
  Maebashi Institute of Technology

Keyword

packet classification, dependent rules, rule ordering, NP-hard

Cite this

Copy

Takashi FUCHINO, Takashi HARADA, Ken TANAKA, Kenji MIKAWA, "Computational Complexity of Allow Rule Ordering and Its Greedy Algorithm" in IEICE TRANSACTIONS on Fundamentals, vol. E106-A, no. 9, pp. 1111-1118, September 2023, doi: 10.1587/transfun.2022DMP0006.
Abstract: Packet classification is used to determine the behavior of incoming packets in network devices according to defined rules. As it is achieved using a linear search on a classification rule list, a large number of rules will lead to longer communication latency. To solve this, the problem of finding the order of rules minimizing the latency has been studied. Misherghi et al. and Harada et al. have proposed a problem that relaxes to policy-based constraints. In this paper, we show that the Relaxed Optimal Rule Ordering (RORO) for the allowlist is NP-hard, and by reducing from this we show that RORO for the general rule list is NP-hard. We also propose a heuristic algorithm based on the greedy method for an allowlist. Furthermore, we demonstrate the effectiveness of our method using ClassBench, which is a benchmark for packet classification algorithms.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/transfun.2022DMP0006/_p

Copy

@ARTICLE{e106-a_9_1111,
author={Takashi FUCHINO, Takashi HARADA, Ken TANAKA, Kenji MIKAWA, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Computational Complexity of Allow Rule Ordering and Its Greedy Algorithm},
year={2023},
volume={E106-A},
number={9},
pages={1111-1118},
abstract={Packet classification is used to determine the behavior of incoming packets in network devices according to defined rules. As it is achieved using a linear search on a classification rule list, a large number of rules will lead to longer communication latency. To solve this, the problem of finding the order of rules minimizing the latency has been studied. Misherghi et al. and Harada et al. have proposed a problem that relaxes to policy-based constraints. In this paper, we show that the Relaxed Optimal Rule Ordering (RORO) for the allowlist is NP-hard, and by reducing from this we show that RORO for the general rule list is NP-hard. We also propose a heuristic algorithm based on the greedy method for an allowlist. Furthermore, we demonstrate the effectiveness of our method using ClassBench, which is a benchmark for packet classification algorithms.},
keywords={},
doi={10.1587/transfun.2022DMP0006},
ISSN={1745-1337},
month={September},}

Copy

TY - JOUR
TI - Computational Complexity of Allow Rule Ordering and Its Greedy Algorithm
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 1111
EP - 1118
AU - Takashi FUCHINO
AU - Takashi HARADA
AU - Ken TANAKA
AU - Kenji MIKAWA
PY - 2023
DO - 10.1587/transfun.2022DMP0006
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E106-A
IS - 9
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - September 2023
AB - Packet classification is used to determine the behavior of incoming packets in network devices according to defined rules. As it is achieved using a linear search on a classification rule list, a large number of rules will lead to longer communication latency. To solve this, the problem of finding the order of rules minimizing the latency has been studied. Misherghi et al. and Harada et al. have proposed a problem that relaxes to policy-based constraints. In this paper, we show that the Relaxed Optimal Rule Ordering (RORO) for the allowlist is NP-hard, and by reducing from this we show that RORO for the general rule list is NP-hard. We also propose a heuristic algorithm based on the greedy method for an allowlist. Furthermore, we demonstrate the effectiveness of our method using ClassBench, which is a benchmark for packet classification algorithms.
ER -