IEICE TRANSACTIONS on Fundamentals
Computational Complexity of Allow Rule Ordering and Its Greedy Algorithm
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
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
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 -
English
