制約条件を緩和したルール順序最適化問題の計算複雑さ

HARADA Takashi; TANAKA Ken; MIKAWA Kenji

文献

J-GLOBAL ID：202002227333976087 整理番号：20A0539827

制約条件を緩和したルール順序最適化問題の計算複雑さ

Computational Complexity of Relaxed Optimal Rule Ordering

出版者サイト複写サービスで全文入手 {{ this.onShowCLink("http://jdream3.com/copy/?sid=JGLOBAL&noSystem=1&documentNoArray=20A0539827&COPY=1") }}
高度な検索・分析はJDreamⅢで {{ this.onShowJLink("http://jdream3.com/lp/jglobal/index.html?docNo=20A0539827&from=J-GLOBAL&jstjournalNo=S0532B") }}

著者 (3件)： , ,
資料名：
巻： 119 号： 340(COMP2019 29-44)(Web) ページ： 47-54 (WEB ONLY) 発行年： 2019年12月06日
JST資料番号： S0532B ISSN： 0913-5685 資料種別：会議録 (C)
記事区分：原著論文発行国：日本 (JPN) 言語：英語 (EN)

パケット分類とは,ネットワーク機器に到着するパケットの振る舞いを決定することである.線型探索による分類は,パケットをルールリストの上位のルールから順番に,合致するルールが見つかるまで照合することによって実現される.パケット分類によって生じる遅延はルール数に依存し,ルールの増加に伴い大きな遅延が生じてしまう.この問題を解決するために,パケット分類によって生じる遅延を最小化するようなルールの順序を求める最適化問題(optimal rule ordering,ORO)が研究されてきた.二つの異なるルールが同じパケットに合致するとき,それらのルールの位置を交換するとポリシー違反が起こる可能性があるので,従来のOROではそのようなルールの並び替えを禁止している.けれども,そのようなルールを並び替えてもポリシー違反が起きない場合がある.本稿では,従来のOROでは交換を許されなかったルールを交換できるように制約条件を緩和した最適化問題(relaxed ORO,RORO)を考え,この問題の決定問題版がNP困難であることを証明する.この結果は,最適なパケット分類の難しさとROROに対して発見的解法が必要であることを示唆する.(著者抄録)

, , , , , , , , ,
, ,

オペレーションズリサーチ一般 , 計算機網

引用文献 (8件)：

H. Hamed and E. Al-Shaer, “Dynamic rule-ordering optimization for high-speed firewall filtering,” Proceedings of the 2006 ACM Symposium on Information, Computer and Communications Security, ASIACCS ’06, New York, NY, USA, pp.332-342, ACM, 2006.
E.W. Fulp, “Optimization of network firewall policies using directed acyclic graphs,” In Proc. IEEE Internet Management Conf, extended abstract, 2005.
E.S.M. El-Alfy and S.Z. Selim, “On optimal firewall rule ordering,” 2007 IEEE/ACS International Conference on Computer Systems and Applications, pp.819-824, May 2007.
A. Tapdiya and E. Fulp, “Towards optimal firewall rule ordering utilizing directed acyclical graphs,” Computer Communications and Networks, 2009. ICCCN 2009. Proceedings of 18th Internatonal Conference on, pp.1-6, Aug 2009.
R. Mohan, A. Yazidi, B. Feng, and J. Oommen, “On optimizing firewall performance in dynamic networks by invoking a novel swapping window-based paradigm,” International Journal of Communication Systems, vol.31, no.15, p.e3773, 2018. e3773 dac.3773.

, , , , ,

前のページに戻る