A funcionalidade de pesquisa está em construção.
A funcionalidade de pesquisa está em construção.

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

Computational Complexity of Allow Rule Ordering and Its Greedy Algorithm Complexidade computacional de permissão de ordenação de regras e seu algoritmo ganancioso

Takashi FUCHINO, Takashi HARADA, Ken TANAKA, Kenji MIKAWA

  • Exibições de texto completo

    0

  • Cite isto

Resumo:

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.

Publicação
IEICE TRANSACTIONS on Fundamentals Vol.E106-A No.9 pp.1111-1118
Data de publicação
2023/09/01
Publicitada
2023/03/20
ISSN online
1745-1337
DOI
10.1587/transfun.2022DMP0006
Tipo de Manuscrito
Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
Categoria
Algoritmos e estruturas de dados

autores

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

Palavra-chave