フィルタリングルールに合致するパケット数の算出法

原田 崇司  田中 賢  三河 賢治  

誌名
電子情報通信学会論文誌 D   Vol.J101-D   No.3   pp.522-529
発行日: 2018/03/01
Online ISSN: 1881-0225
DOI: 10.14923/transinfj.2017PDP0019
論文種別: 特集論文 (学生論文特集)
専門分野: 情報ネットワーク
キーワード: 
パケットフィルタリング,  ルール順序最適化,  MTZDD,  フィルタリングルールの重み,  

本文: PDF(585.2KB)
>>論文を購入


あらまし: 
パケットフィルタリングはネットワーク機器上で行われるパケット分類処理の一つである.フィルタリングはポリシーを表すフィルタリングルールのリストを線型探索することで行われる.パケットとルールの比較回数が増加するとフィルタリングを行う際に通信の遅延が生じる.この遅延を最小化する問題はルール順序最適化問題として形式化され,これまで多くの発見的解法が提案されてきた.従来の研究ではルールの重みが与えられたときの最適なルール順序を求めてきたが,その際ルールの並び替えに伴うルールの重みの変化を考慮していない.この問題を最適化問題として扱うためには,ルールの重みの変化を厳密に求められるようパケットの頻度分布を想定し,並び替え後のルールの重みを求める必要がある.本論文では,このルールの重み算出問題がパケットの頻度分布に一様性を仮定したとき#P-completeであることを示す.そしてMTZDDを用いたルール重み算出法を提案する.更に,プレフィックスルールのルールリストに対して時間計算量がO(nw)のルール重み算出法を提案する.提案手法は通信の遅延減少を目的とした最適化アルゴリズム全般の性能向上に寄与する.