[back to the index page]


フィルタ弁別関数の部分計算に基づく実時間パケット分類器

高橋直久

naohisa@core.ecl.net

NTT未来ねっと研究所


概要

ルーティングテーブルの探索,ファイアウォールでのフィルタリング,ユーザ要求や価格 に応じたきめ細かいサービスの提供などでは,パケットのヘッダを分析し分類する機能が 用いられている.本稿では,ヘッダ長をnバイトとすると,分類規則を定めたルール (フィルタと呼ぶ)の数によらず最悪で2n回のメモリ参照と簡単な演算によりパケットを 分類できる手法を提案する.この手法では,パケット分類問題を計算幾何学の多次元ポイ ントロケーション問題としてモデル化し,n次元問題をn-1次元問題に簡約化するフィルタ 弁別関数を導入している.また,フィルタ弁別関数の部分計算と4種類の最適化手法を用 いることにより,超高速ネットワークにおいて,比較的小容量のメモリを用いて実時間で パケットを分類可能な計算機構を実現している.この機構は,シストリックアレイとして 構成することにより,1回のメモリ参照ごとに次々とパケットを分類することが可能であ る.評価実験では,この機構は,約41,500エントリのルーティーングテーブルの最長プレ フィクス検索の場合に408KBのメモリで平均メモリ参照3.9回,ヘッダ長14バイト,フィル タ数10,000のフィルタリングの場合に,708KBのメモリで平均メモリ参照16.8回で,1パ ケットを分類できることが分かった.

[PS file]

[PDF file]