The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice
The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice
A classificação de pacotes é usada para determinar o comportamento dos pacotes recebidos em dispositivos de rede de acordo com regras definidas. Como isso é conseguido através de uma pesquisa linear em uma lista de regras de classificação, um grande número de regras levará a uma latência de comunicação mais longa. Para resolver isso, foi estudado o problema de encontrar a ordem das regras que minimizam a latência. Misherghi et al. e Harada et al. propuseram um problema que relaxa com restrições baseadas em políticas. Neste artigo, mostramos que a ordem de regras ótimas relaxadas (RORO) para a lista de permissões é NP-difícil, e reduzindo isso mostramos que RORO para a lista de regras gerais é NP-duro. Também propomos um algoritmo heurístico baseado no método guloso para uma lista de permissões. Além disso, demonstramos a eficácia do nosso método usando ClassBench, que é uma referência para algoritmos de classificação de pacotes.
Takashi FUCHINO
Kanagawa University
Takashi HARADA
Kochi University of Technology
Ken TANAKA
Kanagawa University
Kenji MIKAWA
Maebashi Institute of Technology
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.
Copiar
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
Copiar
@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},}
Copiar
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 -