JPH1070570A - パケット処理装置 - Google Patents
パケット処理装置Info
- Publication number
- JPH1070570A JPH1070570A JP22523996A JP22523996A JPH1070570A JP H1070570 A JPH1070570 A JP H1070570A JP 22523996 A JP22523996 A JP 22523996A JP 22523996 A JP22523996 A JP 22523996A JP H1070570 A JPH1070570 A JP H1070570A
- Authority
- JP
- Japan
- Prior art keywords
- packet
- access control
- comparison
- unit
- control program
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Granted
Links
Landscapes
- Computer And Data Communications (AREA)
- Data Exchanges In Wide-Area Networks (AREA)
Abstract
(57)【要約】
【課題】 行数の多いアクセス制御プログラムを与えら
れた場合にも、高速、かつ、効果的な、パケットフィル
タ処理が可能なパケット処理装置の提供。 【解決手段】 パケットフィルタ部２に、逐次的解釈
が、必要なアクセス制御プログラムの依存関係を解析
し、経路条件に基づき、並列に解釈可能なアクセス制御
規則からなる中間コード４に変換し、中間コード４のパ
ケット条件に含まれる同一な比較パラメータ、あるい
は、包含関係を持つ比較パラメータを検出して、これを
簡単化するアクセス制御プログラム並列化コンパイラ部
３と、該中間コード４に基づいて、パケットの転送、ま
たは、廃棄を決定する、パケットフィルタ実行部５を有
する。
れた場合にも、高速、かつ、効果的な、パケットフィル
タ処理が可能なパケット処理装置の提供。 【解決手段】 パケットフィルタ部２に、逐次的解釈
が、必要なアクセス制御プログラムの依存関係を解析
し、経路条件に基づき、並列に解釈可能なアクセス制御
規則からなる中間コード４に変換し、中間コード４のパ
ケット条件に含まれる同一な比較パラメータ、あるい
は、包含関係を持つ比較パラメータを検出して、これを
簡単化するアクセス制御プログラム並列化コンパイラ部
３と、該中間コード４に基づいて、パケットの転送、ま
たは、廃棄を決定する、パケットフィルタ実行部５を有
する。
Description
【０００１】
【発明の属する技術分野】本発明は、通信システムのパ
ケット通信システムに関し、特に、パケットルータ処理
の中で、計算機ネットワーク管理者が定義するアクセス
制御プログラムに基づいて、パケットデータの転送、あ
るいは、廃棄を決定するパケット処理装置に関するもの
である。
ケット通信システムに関し、特に、パケットルータ処理
の中で、計算機ネットワーク管理者が定義するアクセス
制御プログラムに基づいて、パケットデータの転送、あ
るいは、廃棄を決定するパケット処理装置に関するもの
である。
【０００２】
【従来の技術】図８は、従来のパケットルータ処理装置
の構成例である［W.R.Cheswick and S.M.Bellovin,“Fi
rewalls and Internet Security",ADDISON-WESLEY PUBL
ISHINGCOMPANY］．回線対応部８1、８2、８3は、通信回
線からのパケットを受信、あるいは、通信回線へパケッ
トを送信する。アクセス制御プログラム１は、計算機ネ
ットワークの管理者が記述し、パケットルータ処理装置
が転送すべきパケット、および、転送せずに廃棄すべき
パケットを指定するプログラムである。パケットフィル
タ部２１は、受信したパケットのヘッダ部分を解析し、
アクセス制御プログラム１に従って、パケットの転送あ
るいは廃棄を決定する。
の構成例である［W.R.Cheswick and S.M.Bellovin,“Fi
rewalls and Internet Security",ADDISON-WESLEY PUBL
ISHINGCOMPANY］．回線対応部８1、８2、８3は、通信回
線からのパケットを受信、あるいは、通信回線へパケッ
トを送信する。アクセス制御プログラム１は、計算機ネ
ットワークの管理者が記述し、パケットルータ処理装置
が転送すべきパケット、および、転送せずに廃棄すべき
パケットを指定するプログラムである。パケットフィル
タ部２１は、受信したパケットのヘッダ部分を解析し、
アクセス制御プログラム１に従って、パケットの転送あ
るいは廃棄を決定する。
【０００３】ルートテーブル検索部２２は、経路情報を
格納した経路情報テーブル２３を持ち、受信したパケッ
トのヘッダ部分を解析し、経路情報テーブルに基づいて
パケットを送出する回線対応部を決定する。
格納した経路情報テーブル２３を持ち、受信したパケッ
トのヘッダ部分を解析し、経路情報テーブルに基づいて
パケットを送出する回線対応部を決定する。
【０００４】図２はアクセス制御プログラムの一例であ
る。アクセス制御プログラム１は複数行記述されたアク
セス制御規則からなる。アクセス制御規則は、パケット
条件１1とルータ動作１2の対で構成する。パケット条件
は、複数の比較パラメータ１ 3からなり、比較パラメー
タ１3には、プロトコル種類、始点アドレス、始点ポー
ト番号、終点アドレス、終点ポート番号およびＡＣＫビ
ット［D.E.Comer, “Internetworking With TCP/IP, Vo
l.I", 1991. Prentice Hall.］の６種類があり、全ての
パターンと一致するワイルドカード“＊”も記述可能で
ある。ルータ動作は、パケット条件と一致したパケット
の処理方法であり、パケットの転送を許可する“転送”
とパケットを転送せずに廃棄する“廃棄”の２種類の値
をとり得る。
る。アクセス制御プログラム１は複数行記述されたアク
セス制御規則からなる。アクセス制御規則は、パケット
条件１1とルータ動作１2の対で構成する。パケット条件
は、複数の比較パラメータ１ 3からなり、比較パラメー
タ１3には、プロトコル種類、始点アドレス、始点ポー
ト番号、終点アドレス、終点ポート番号およびＡＣＫビ
ット［D.E.Comer, “Internetworking With TCP/IP, Vo
l.I", 1991. Prentice Hall.］の６種類があり、全ての
パターンと一致するワイルドカード“＊”も記述可能で
ある。ルータ動作は、パケット条件と一致したパケット
の処理方法であり、パケットの転送を許可する“転送”
とパケットを転送せずに廃棄する“廃棄”の２種類の値
をとり得る。
【０００５】従来のパケットルータ処理装置におけるパ
ケットデータの転送処理は以下の如く行なわれる。
ケットデータの転送処理は以下の如く行なわれる。
【０００６】１．回線対応部８1（例）で通信回線上の
パケットを受信し、そのパケットのヘッダ部分を抽出す
る。パケットヘッダ部分には、アクセス制御プログラム
と比較するプロトコル種類、始点アドレス、始点ポート
番号、終点アドレス、終点ポート番号、および、ＡＣＫ
ビットが格納されている。
パケットを受信し、そのパケットのヘッダ部分を抽出す
る。パケットヘッダ部分には、アクセス制御プログラム
と比較するプロトコル種類、始点アドレス、始点ポート
番号、終点アドレス、終点ポート番号、および、ＡＣＫ
ビットが格納されている。
【０００７】２．ルートテーブル検索部２２は、回線対
応部８で抽出したパケットヘッダ部分に格納されている
終点アドレスをキーとして経路情報格納テーブル２３を
検索し、パケットを送出する回線対応部８3（例）を決
定する。
応部８で抽出したパケットヘッダ部分に格納されている
終点アドレスをキーとして経路情報格納テーブル２３を
検索し、パケットを送出する回線対応部８3（例）を決
定する。
【０００８】３．パケットフィルタ部２１は、アクセス
制御プログラム１を上の行から順に、上記パケットヘッ
ダ部分との比較を行なう。すなわち、アクセス制御プロ
グラムのｉ行目のアクセス制御規則のパケット条件１1
をＰi 、ルータ動作をＡi 、Ｐi を構成する６種類の比
較パラメータを各々ｐi1，ｐi2，ｐi3，ｐi4，ｐi5，ｐ
i6とすると、パケットフィルタ部は次のように逐次的に
アクセス制御プログラム１を解釈する。
制御プログラム１を上の行から順に、上記パケットヘッ
ダ部分との比較を行なう。すなわち、アクセス制御プロ
グラムのｉ行目のアクセス制御規則のパケット条件１1
をＰi 、ルータ動作をＡi 、Ｐi を構成する６種類の比
較パラメータを各々ｐi1，ｐi2，ｐi3，ｐi4，ｐi5，ｐ
i6とすると、パケットフィルタ部は次のように逐次的に
アクセス制御プログラム１を解釈する。
【０００９】
【数１】 ４．パケット処理装置はパケットフィルタ部２１から得
られたルータ動作１2が“転送”の場合には、ルートテ
ーブル検索部２２から得られた回線対応部８3にパケッ
トを転送し、通信回線上に送信する。パケットフィルタ
部から得られたルータ動作が“廃棄”の場合には、パケ
ットを廃棄する。
られたルータ動作１2が“転送”の場合には、ルートテ
ーブル検索部２２から得られた回線対応部８3にパケッ
トを転送し、通信回線上に送信する。パケットフィルタ
部から得られたルータ動作が“廃棄”の場合には、パケ
ットを廃棄する。
【００１０】
【発明が解決しようとする課題】上記従来技術ではパケ
ットフィルタ処理において、アクセス制御プログラムを
逐次的に解釈するため、下記の如き問題がある。 問題１ アクセス制御プログラムの行数に比例してパケ
ットフィルタ処理の時間が増加する。パケットフィルタ
処理が終了するまでパケット転送が遅延することから、
アクセス制御プログラムの行数の増加に従って、ルータ
のパケット転送能力が低下する。 問題２ パケット条件は比較パラメータのＡＮＤ条件で
あるため、ＯＲ条件は複数行のアクセス制御規則を用い
て記述する。これらのアクセス制御規則は、ＯＲ条件と
なる部分の比較パラメータのみが異なる記述となる。こ
のようなアクセス制御規則を持つアクセス制御プログラ
ムを、単純に逐次的に解釈すると、パケットフィルタ処
理部は同じ比較演算を複数回行なってしまう。 問題３ アクセス制御プログラムのｉ行目のパケット条
件Ｐi とｊ行目のパケット条件Ｐj （ただしｉ＜ｊ）に
おいて、Ｐj と一致するパケットの集合がＰi と一致す
るパケットの集合の部分集合の場合、実行不能経路（Ｉ
ＦＰ：InfeasiblePath［直井、高橋、“経路依存フロフ
ラグを用いたInfeasible Path 検出法"、電子情報通信
学会論文誌、D-1,No.8．pp 429-439, 1993］）が存在す
ることになる。この場合、ｊ行目のルータ動作Ａj は決
して実行されないにも関わらず、パケットフィルタ処理
部はパケット条件Ｐj とパケットヘッダの比較を行なっ
てしまう。
ットフィルタ処理において、アクセス制御プログラムを
逐次的に解釈するため、下記の如き問題がある。 問題１ アクセス制御プログラムの行数に比例してパケ
ットフィルタ処理の時間が増加する。パケットフィルタ
処理が終了するまでパケット転送が遅延することから、
アクセス制御プログラムの行数の増加に従って、ルータ
のパケット転送能力が低下する。 問題２ パケット条件は比較パラメータのＡＮＤ条件で
あるため、ＯＲ条件は複数行のアクセス制御規則を用い
て記述する。これらのアクセス制御規則は、ＯＲ条件と
なる部分の比較パラメータのみが異なる記述となる。こ
のようなアクセス制御規則を持つアクセス制御プログラ
ムを、単純に逐次的に解釈すると、パケットフィルタ処
理部は同じ比較演算を複数回行なってしまう。 問題３ アクセス制御プログラムのｉ行目のパケット条
件Ｐi とｊ行目のパケット条件Ｐj （ただしｉ＜ｊ）に
おいて、Ｐj と一致するパケットの集合がＰi と一致す
るパケットの集合の部分集合の場合、実行不能経路（Ｉ
ＦＰ：InfeasiblePath［直井、高橋、“経路依存フロフ
ラグを用いたInfeasible Path 検出法"、電子情報通信
学会論文誌、D-1,No.8．pp 429-439, 1993］）が存在す
ることになる。この場合、ｊ行目のルータ動作Ａj は決
して実行されないにも関わらず、パケットフィルタ処理
部はパケット条件Ｐj とパケットヘッダの比較を行なっ
てしまう。
【００１１】本発明の目的は、従来技術のパケットフィ
ルタ処理では、逐次的な解釈が必要なアクセス制御プロ
グラムを、単純に逐次的に解釈するために、アクセス制
御プログラムの行数に比例してフィルタ処理時間が増加
し、ルータのパケット転送能力が低下する点と、計算機
ネットワーク管理者が複数行のアクセス制御規則を用い
てＯＲ条件のアクセス制御規則を記述した場合に、パケ
ットフィルタ装置が同じ比較を複数回行なってしまう
点、および、アクセス制御プログラムに実行不能経路が
存在する場合に無駄な比較演算を行なってしまう点を解
決し、行数の大きなアクセス制御プログラムを与えられ
た場合にも、高速かつ効率的なパケットフィルタ処理が
可能なパケット処理装置を提供することにある。
ルタ処理では、逐次的な解釈が必要なアクセス制御プロ
グラムを、単純に逐次的に解釈するために、アクセス制
御プログラムの行数に比例してフィルタ処理時間が増加
し、ルータのパケット転送能力が低下する点と、計算機
ネットワーク管理者が複数行のアクセス制御規則を用い
てＯＲ条件のアクセス制御規則を記述した場合に、パケ
ットフィルタ装置が同じ比較を複数回行なってしまう
点、および、アクセス制御プログラムに実行不能経路が
存在する場合に無駄な比較演算を行なってしまう点を解
決し、行数の大きなアクセス制御プログラムを与えられ
た場合にも、高速かつ効率的なパケットフィルタ処理が
可能なパケット処理装置を提供することにある。
【００１２】
【課題を解決するための手段】本発明のパケット処理装
置におけるパケットフィルタ部２は、アクセス制御プロ
グラム並列化コンパイラ部（以下、ＡＣＰ並列化コンパ
イラ部と略す）３と、パケットフィルタ実行部５を有す
る。
置におけるパケットフィルタ部２は、アクセス制御プロ
グラム並列化コンパイラ部（以下、ＡＣＰ並列化コンパ
イラ部と略す）３と、パケットフィルタ実行部５を有す
る。
【００１３】ＡＣＰ並列化コンパイラ部３は、逐次的な
解釈が必要なアクセス制御プログラム１の依存関係を解
析し、経路条件に基づいて並列に解釈可能なアクセス制
御規則からなる中間コード４に変換する手段と、中間コ
ード４を比較パラメータの数に従って分割する手段と、
中間コード４のパケット条件に含まれる複数個の同一な
比較パラメータあるいは包含関係を持つ比較パラメータ
を検出して、これを簡単化する手段と、簡単化により比
較パラメータが空集合となるアクセス制御規則を中間コ
ード４から削除する手段を有する。
解釈が必要なアクセス制御プログラム１の依存関係を解
析し、経路条件に基づいて並列に解釈可能なアクセス制
御規則からなる中間コード４に変換する手段と、中間コ
ード４を比較パラメータの数に従って分割する手段と、
中間コード４のパケット条件に含まれる複数個の同一な
比較パラメータあるいは包含関係を持つ比較パラメータ
を検出して、これを簡単化する手段と、簡単化により比
較パラメータが空集合となるアクセス制御規則を中間コ
ード４から削除する手段を有する。
【００１４】パケットフィルタ実行部５は、通信回線か
ら受信したデータパケットのヘッダ部分を解析し、ＡＣ
Ｐ並列化コンパイラ部３が生成した中間コード４に基づ
いて、パケットの転送、あるいは、廃棄を決定する手段
を有する。
ら受信したデータパケットのヘッダ部分を解析し、ＡＣ
Ｐ並列化コンパイラ部３が生成した中間コード４に基づ
いて、パケットの転送、あるいは、廃棄を決定する手段
を有する。
【００１５】上記の構成により、パケットフィルタ処理
時間がアクセス制御プログラム１の行数に比例せず、ア
クセス制御プログラム１に含まれる複数個の比較パラメ
ータの共通部分とパケットヘッダ部分との比較を一回に
抑えることができ、アクセス制御プログラム１の実行不
能経路を検出し、実行不能経路に対応するパケット条件
とパケットヘッダ部分の比較を回避できる。
時間がアクセス制御プログラム１の行数に比例せず、ア
クセス制御プログラム１に含まれる複数個の比較パラメ
ータの共通部分とパケットヘッダ部分との比較を一回に
抑えることができ、アクセス制御プログラム１の実行不
能経路を検出し、実行不能経路に対応するパケット条件
とパケットヘッダ部分の比較を回避できる。
【００１６】
【発明の実施の形態】次に、本発明の実施の形態に付い
て図面を参照して説明する。
て図面を参照して説明する。
【００１７】図１は本発明のパケット処理装置の第１の
実施例のシステム構成図である。本発明のパケット処理
装置は図１に示すように、ＡＣＰ並列化コンパイラ部２
では、アクセス制御プログラムのｉ行目のアクセス制御
規則を、経路条件［３］ＰＣi を用いて次のように記述
することで、全てのアクセス制御規則を並列に実行可能
な中間コード４に変換する。
実施例のシステム構成図である。本発明のパケット処理
装置は図１に示すように、ＡＣＰ並列化コンパイラ部２
では、アクセス制御プログラムのｉ行目のアクセス制御
規則を、経路条件［３］ＰＣi を用いて次のように記述
することで、全てのアクセス制御規則を並列に実行可能
な中間コード４に変換する。
【００１８】
【数２】 また、請求項６に基づく処理では、上記ＡＣＰ並列化コ
ンパイラ３の出力を解釈し、逐次的に実行可能な、図４
に示す本発明の第２の実施例の逐次実行コード１０を生
成する中間コードスケジューラ部９と、逐次実行コード
１０を解釈し、パケットヘッダ部分と比較し、パケット
の転送、あるいは、廃棄を決定する逐次型パケットフィ
ルタ実行部１１で、パケットフィルタ実行部５を実現す
る。
ンパイラ３の出力を解釈し、逐次的に実行可能な、図４
に示す本発明の第２の実施例の逐次実行コード１０を生
成する中間コードスケジューラ部９と、逐次実行コード
１０を解釈し、パケットヘッダ部分と比較し、パケット
の転送、あるいは、廃棄を決定する逐次型パケットフィ
ルタ実行部１１で、パケットフィルタ実行部５を実現す
る。
【００１９】また、請求項７に基づく処理では、中間コ
ード４を解釈して、並列に実行可能な並列実行コードを
生成する、図６に示す本発明の第３の実施例の並列実行
コード生成部１２と、並列実行コードを解釈してパケッ
トヘッダ部分と比較し、パケットの転送あるいは廃棄を
決定する並列型パケットフィルタ実行部１４により、パ
ケットフィルタ実行部５を実現する。
ード４を解釈して、並列に実行可能な並列実行コードを
生成する、図６に示す本発明の第３の実施例の並列実行
コード生成部１２と、並列実行コードを解釈してパケッ
トヘッダ部分と比較し、パケットの転送あるいは廃棄を
決定する並列型パケットフィルタ実行部１４により、パ
ケットフィルタ実行部５を実現する。
【００２０】また、請求項８に基づく処理では、直近の
パケットフィルタ処理において、パケットヘッダ部分と
一致した並列実行コードのアクセス制御規則へのポイン
タを保存するキャッシュポインタを、請求項７に加えた
構成とし、パケットフィルタ処理において、キャッシュ
ポインタが示すアクセス制御規則を優先して選択し、パ
ケットヘッダ部分との比較を行なう。
パケットフィルタ処理において、パケットヘッダ部分と
一致した並列実行コードのアクセス制御規則へのポイン
タを保存するキャッシュポインタを、請求項７に加えた
構成とし、パケットフィルタ処理において、キャッシュ
ポインタが示すアクセス制御規則を優先して選択し、パ
ケットヘッダ部分との比較を行なう。
【００２１】以下、本発明の実施例を図面に基づいて詳
細に説明する。図１は、本発明のパケット処理装置の第
１の実施例のシステム構成図である。
細に説明する。図１は、本発明のパケット処理装置の第
１の実施例のシステム構成図である。
【００２２】このパケット処理装置は、ＡＣＰ並列化コ
ンパイラ部３とパケットフィルタ実行部５で構成するパ
ケットフィルタ部２を有し、ＡＣＰ並列化コンパイラ部
３は、パケット処理装置の起動時に、アクセス制御プロ
グラム１を読み込み、上述の経路条件に従って、並列に
解釈可能な中間コード４を生成する。この時、ＡＣＰ並
列化コンパイラ３は、次の手法を用いて生成する中間コ
ード４を最適化する。生成する中間コード４は、互いに
依存関係を持たない複数行のアクセス制御規則からな
り、アクセス制御規則はパケット条件とルータ動作の対
応で構成する。
ンパイラ部３とパケットフィルタ実行部５で構成するパ
ケットフィルタ部２を有し、ＡＣＰ並列化コンパイラ部
３は、パケット処理装置の起動時に、アクセス制御プロ
グラム１を読み込み、上述の経路条件に従って、並列に
解釈可能な中間コード４を生成する。この時、ＡＣＰ並
列化コンパイラ３は、次の手法を用いて生成する中間コ
ード４を最適化する。生成する中間コード４は、互いに
依存関係を持たない複数行のアクセス制御規則からな
り、アクセス制御規則はパケット条件とルータ動作の対
応で構成する。
【００２３】− 中間コード４のアクセス制御規則を、
比較パラメータの数に従って分割する。アクセス制御プ
ログラム１のｉ行目のパケット条件をＰi 、ルータ動作
をＡ i 、Ｐi を構成する６種類の比較パラメータを
ｐij、Ｐi から生成する中間コードのアクセス制御規則
の集合を｛ＰＣi ｝とすると、ＡＣＰ並列化コンパイラ
は次のように中間コードを生成する。
比較パラメータの数に従って分割する。アクセス制御プ
ログラム１のｉ行目のパケット条件をＰi 、ルータ動作
をＡ i 、Ｐi を構成する６種類の比較パラメータを
ｐij、Ｐi から生成する中間コードのアクセス制御規則
の集合を｛ＰＣi ｝とすると、ＡＣＰ並列化コンパイラ
は次のように中間コードを生成する。
【００２４】
【数３】 ・中間コード４のパケット条件に、条件と一致するパケ
ットが同一となる複数の比較パラメータ、あるいは、条
件と一致するパケットが部分集合となる２つの比較パラ
メータを生成した場合、すなわちα＝β、あるいは、α
がβの真部分集合が成立する比較パラメータα∩βを生
成した場合には、これらの比較パラメータを集合の間の
演算を用いて簡単化する。
ットが同一となる複数の比較パラメータ、あるいは、条
件と一致するパケットが部分集合となる２つの比較パラ
メータを生成した場合、すなわちα＝β、あるいは、α
がβの真部分集合が成立する比較パラメータα∩βを生
成した場合には、これらの比較パラメータを集合の間の
演算を用いて簡単化する。
【００２５】例１：tcp ∩tcp →tcp ，ここで、 tcp
(Transmission Control Protocol) 例２：11.22.*.* ∩ 11.22.33.44→11.22.33.44 ・α∩β＝０が成立する比較パラメータαとβを生成し
た場合には、これらの比較パラメータを持つアクセス制
御規則を中間コード４から削除する。
(Transmission Control Protocol) 例２：11.22.*.* ∩ 11.22.33.44→11.22.33.44 ・α∩β＝０が成立する比較パラメータαとβを生成し
た場合には、これらの比較パラメータを持つアクセス制
御規則を中間コード４から削除する。
【００２６】図３はＡＣＰ並列化コンパイラ３が生成す
る中間コード４の一例である。図は、図２で例示したア
クセス制御プログラムを入力した場合にＡＣＰ並列化コ
ンパイラ３が生成する中間コードである。中間コード４
はアクセス制御プログラムと同様に複数行のアクセス制
御規則からなるが、アクセス制御規則が互いに依存関係
を持たず、任意の順序でパケットヘッダ部分と比較可能
な点がアクセス制御プログラム１と異なる。中間コード
４のアクセス制御規則は、プロトコル種類、始点アドレ
ス、始点ポート番号、終点アドレス、終点ポート番号お
よびＡＣＫビットの６種類の比較パラメータからなるパ
ケット条件と、ルータ動作とで構成する。比較パラメー
タには全てのパターンと一致するワイルドカード“＊”
も記述可能である。ルータ動作は、パケット条件と一致
したパケットの処理方法であり、パケットの転送を許可
する“転送”とパケットを転送せずに廃棄する“廃棄”
の２種類の値をとり得る。
る中間コード４の一例である。図は、図２で例示したア
クセス制御プログラムを入力した場合にＡＣＰ並列化コ
ンパイラ３が生成する中間コードである。中間コード４
はアクセス制御プログラムと同様に複数行のアクセス制
御規則からなるが、アクセス制御規則が互いに依存関係
を持たず、任意の順序でパケットヘッダ部分と比較可能
な点がアクセス制御プログラム１と異なる。中間コード
４のアクセス制御規則は、プロトコル種類、始点アドレ
ス、始点ポート番号、終点アドレス、終点ポート番号お
よびＡＣＫビットの６種類の比較パラメータからなるパ
ケット条件と、ルータ動作とで構成する。比較パラメー
タには全てのパターンと一致するワイルドカード“＊”
も記述可能である。ルータ動作は、パケット条件と一致
したパケットの処理方法であり、パケットの転送を許可
する“転送”とパケットを転送せずに廃棄する“廃棄”
の２種類の値をとり得る。
【００２７】図４は本発明のパケット処理装置の第２の
実施例の単一のＣＰＵのみ使用可能な場合のパケットフ
ィルタ実行部５の一部の一構成を示す図である。中間コ
ードスケジューラ９は中間コード４を解釈し、逐次的に
実行可能な逐次実行コード１０を生成する。逐次型パケ
ットフィルタ実行部１１は逐次実行コード１０を解釈
し、パケットヘッダ部分と比較し、パケットの転送ある
いは廃棄を決定する。
実施例の単一のＣＰＵのみ使用可能な場合のパケットフ
ィルタ実行部５の一部の一構成を示す図である。中間コ
ードスケジューラ９は中間コード４を解釈し、逐次的に
実行可能な逐次実行コード１０を生成する。逐次型パケ
ットフィルタ実行部１１は逐次実行コード１０を解釈
し、パケットヘッダ部分と比較し、パケットの転送ある
いは廃棄を決定する。
【００２８】中間コードスケジューラ部９は、中間コー
ド４が任意の順序で実行可能であることから、中間コー
ド４を解釈して木構造となるように比較パラメータとパ
ケットヘッダ部分の比較順序を決定し、逐次実行コード
１０を生成する。木構造において、ノードは一つの比較
パラメータを示し、枝は比較パラメータとパケットヘッ
ダ部分との比較結果に従って、次に比較すべきノードへ
のポインタである。
ド４が任意の順序で実行可能であることから、中間コー
ド４を解釈して木構造となるように比較パラメータとパ
ケットヘッダ部分の比較順序を決定し、逐次実行コード
１０を生成する。木構造において、ノードは一つの比較
パラメータを示し、枝は比較パラメータとパケットヘッ
ダ部分との比較結果に従って、次に比較すべきノードへ
のポインタである。
【００２９】比較パラメータとパケットヘッダとの比較
結果は、比較パラメータがプロトコル種類とＡＣＫビッ
トの場合には、“比較パラメータとパケットヘッダの値
が等しい”、および、“比較パラメータとパケットヘッ
ダの値が等しくない”の２種類があり、始点アドレス、
始点ポート番号、終点アドレス、および、終点ポート番
号の場合には、“比較パラメータとパケットヘッダの値
が等しい”、“比較パラメータよりパケットヘッダの値
が小さい”、または、“比較パラメータよりパケットヘ
ッダの値が大きい”の３種類がある。木構造の葉はルー
タ動作を表す。この時、中間コードスケジューラ９は、
比較パラメータの種類別に階層化するとともに、各アク
セス制御規則で共通する比較パラメータを抽出して、こ
れらが木の同一パスとなるように構築することで、生成
する逐次実行コードの木の高さを小さく抑える。図５は
中間コードスケジューラ９が生成する逐次実行コード１
０の一例である。図３で例示した中間コードを入力した
場合に中間コードスケジューラ９が生成する逐次実行コ
ードである。
結果は、比較パラメータがプロトコル種類とＡＣＫビッ
トの場合には、“比較パラメータとパケットヘッダの値
が等しい”、および、“比較パラメータとパケットヘッ
ダの値が等しくない”の２種類があり、始点アドレス、
始点ポート番号、終点アドレス、および、終点ポート番
号の場合には、“比較パラメータとパケットヘッダの値
が等しい”、“比較パラメータよりパケットヘッダの値
が小さい”、または、“比較パラメータよりパケットヘ
ッダの値が大きい”の３種類がある。木構造の葉はルー
タ動作を表す。この時、中間コードスケジューラ９は、
比較パラメータの種類別に階層化するとともに、各アク
セス制御規則で共通する比較パラメータを抽出して、こ
れらが木の同一パスとなるように構築することで、生成
する逐次実行コードの木の高さを小さく抑える。図５は
中間コードスケジューラ９が生成する逐次実行コード１
０の一例である。図３で例示した中間コードを入力した
場合に中間コードスケジューラ９が生成する逐次実行コ
ードである。
【００３０】図５に示す逐次実行コードは、木構造にお
いて、プロトコル種類、ＡＣＫビット、終点アドレス、
終点ポートの順序で比較が行われるように、比較パラメ
ータの種類別に階層化している。プロトコル種類の比較
層では、パケットのヘッダ部分が含むプロトコル種類が
ＴＣＰであるかどうかを比較し、ＴＣＰの場合にはＡＣ
Ｋビットの比較へ移り、ＴＣＰでない場合には、ルータ
の通過を禁止してパケットの廃棄を指示する葉へ移る。
同様に、ＡＣＫビットの比較層では、パケットのは域を
指示する葉へ移る。同様に、ＡＣＫビットの比較層で
は、パケットのヘッダ部分が含むＡＣＫビットの内容が
establishedである場合とestablishedでない場合につい
て、次に比較すべきノードを指し示している。終点アド
レスの比較層と終点ポート番号の比較層では、それぞれ
パケットのヘッダ部分が含む終点アドレスと終点ポート
番号に関する比較パラメータを示している。
いて、プロトコル種類、ＡＣＫビット、終点アドレス、
終点ポートの順序で比較が行われるように、比較パラメ
ータの種類別に階層化している。プロトコル種類の比較
層では、パケットのヘッダ部分が含むプロトコル種類が
ＴＣＰであるかどうかを比較し、ＴＣＰの場合にはＡＣ
Ｋビットの比較へ移り、ＴＣＰでない場合には、ルータ
の通過を禁止してパケットの廃棄を指示する葉へ移る。
同様に、ＡＣＫビットの比較層では、パケットのは域を
指示する葉へ移る。同様に、ＡＣＫビットの比較層で
は、パケットのヘッダ部分が含むＡＣＫビットの内容が
establishedである場合とestablishedでない場合につい
て、次に比較すべきノードを指し示している。終点アド
レスの比較層と終点ポート番号の比較層では、それぞれ
パケットのヘッダ部分が含む終点アドレスと終点ポート
番号に関する比較パラメータを示している。
【００３１】パケットのヘッダ部分と各ノードの比較パ
ラメータを比較し、パケットのヘッダ部分がノードより
小さい場合には”＜”で示される枝、パケットのヘッダ
部分とノードの比較パラメータが等しい場合には”＞”
で示される枝、パケットのヘッダ部分がノードの比較パ
ラメータより大きい場合には”＞”で示される枝が、そ
れぞれ、次に比較するノードを示している。また、葉の
値”Ｐ”は、パケットの通過を許可し、パケットの転送
を指示しており、葉の値”Ｄ”は、パケットの通過を禁
止し、パケットの廃棄を指示している。
ラメータを比較し、パケットのヘッダ部分がノードより
小さい場合には”＜”で示される枝、パケットのヘッダ
部分とノードの比較パラメータが等しい場合には”＞”
で示される枝、パケットのヘッダ部分がノードの比較パ
ラメータより大きい場合には”＞”で示される枝が、そ
れぞれ、次に比較するノードを示している。また、葉の
値”Ｐ”は、パケットの通過を許可し、パケットの転送
を指示しており、葉の値”Ｄ”は、パケットの通過を禁
止し、パケットの廃棄を指示している。
【００３２】逐次型パケットフィルタ実行部１１は逐次
実行コード１０を読み込み、逐次実行コード１０の根の
ノードから順に、木構造に沿ってパケットヘッダとの比
較を行ない、到達した葉の値に従ってパケットの転送、
あるいは、廃棄を決定する。すなわち、逐次型パケット
フィルタ実行部でのパケットフィルタ処理時間は、中間
コードスケジューラにより生成された逐次実行コードの
木の高さに依存する。
実行コード１０を読み込み、逐次実行コード１０の根の
ノードから順に、木構造に沿ってパケットヘッダとの比
較を行ない、到達した葉の値に従ってパケットの転送、
あるいは、廃棄を決定する。すなわち、逐次型パケット
フィルタ実行部でのパケットフィルタ処理時間は、中間
コードスケジューラにより生成された逐次実行コードの
木の高さに依存する。
【００３３】逐次型パケットフィルタ実行部１４の動作
について以下に述べる。
について以下に述べる。
【００３４】１．逐次実行コードを読み込む。
【００３５】２．回線対応部で抽出したパケットヘッダ
部分を受け取る。
部分を受け取る。
【００３６】パケットヘッダ部分には、プロトコル種
類、始点アドレス、始点ポート番号、終点アドレス、終
点ポート番号、および、ＡＣＫビットが格納されてい
る。
類、始点アドレス、始点ポート番号、終点アドレス、終
点ポート番号、および、ＡＣＫビットが格納されてい
る。
【００３７】３．逐次実行コードの根のノードを読み出
す。
す。
【００３８】４．読み出したのがノードの場合は５へ行
く。また、読み出したのが葉の場合は７へ行く。
く。また、読み出したのが葉の場合は７へ行く。
【００３９】５．ノードが示す比較パラメータについ
て、ノードが示す値とパケットヘッダの値を比較する。
この時、ノードの比較パラメータと、パケットヘッダと
の比較結果には、比較パラメータがプロトコル種類とＡ
ＣＫビットの場合には、“ 比較パラメータとパケット
ヘッダの値が等しい”、および、“比較パラメータ と
パケットヘッダの値が等しくない”の２種類があり、始
点アドレス、始点ポ ート番号、”終点アドレス、およ
び、終点ポート番号の場合には、“比較パラメータとパ
ケットヘッダの値が等しい”、“比較パラメータよりパ
ケット ヘッダの値が小さい”、または、“比較パラメ
ータよりパケットヘッダの値が 大きい”の３種類があ
る。
て、ノードが示す値とパケットヘッダの値を比較する。
この時、ノードの比較パラメータと、パケットヘッダと
の比較結果には、比較パラメータがプロトコル種類とＡ
ＣＫビットの場合には、“ 比較パラメータとパケット
ヘッダの値が等しい”、および、“比較パラメータ と
パケットヘッダの値が等しくない”の２種類があり、始
点アドレス、始点ポ ート番号、”終点アドレス、およ
び、終点ポート番号の場合には、“比較パラメータとパ
ケットヘッダの値が等しい”、“比較パラメータよりパ
ケット ヘッダの値が小さい”、または、“比較パラメ
ータよりパケットヘッダの値が 大きい”の３種類があ
る。
【００４０】６．比較結果に従って、ノードから伸びる
枝を選択し、枝が指し示している次に比較すべきノー
ド、または、葉を読み出す。４へ行く。
枝を選択し、枝が指し示している次に比較すべきノー
ド、または、葉を読み出す。４へ行く。
【００４１】７．葉が示すルータ動作がルータの通過を
許可している場合は、パケットの転送を行う。葉が示す
ルータ動作がルータの通過を禁止している場合には、パ
ケットの廃棄を行う。
許可している場合は、パケットの転送を行う。葉が示す
ルータ動作がルータの通過を禁止している場合には、パ
ケットの廃棄を行う。
【００４２】図６は本発明のパケット処理装置の第３の
実施例のパケットフィルタ部の一部で、有限個のＣＰＵ
資源が使用可能な場合のパケットフィルタ実行部５の構
成を示す図である。並列実行コード生成部１２は、中間
コード４を解釈して、並列に実行可能な並列実行コード
１３を生成する。並列型パケットフィルタ実行部１４は
並列実行コード１３を解釈し、パケットヘッダ部分と比
較し、パケットの転送あるいは廃棄を決定する。
実施例のパケットフィルタ部の一部で、有限個のＣＰＵ
資源が使用可能な場合のパケットフィルタ実行部５の構
成を示す図である。並列実行コード生成部１２は、中間
コード４を解釈して、並列に実行可能な並列実行コード
１３を生成する。並列型パケットフィルタ実行部１４は
並列実行コード１３を解釈し、パケットヘッダ部分と比
較し、パケットの転送あるいは廃棄を決定する。
【００４３】並列実行コード生成部１２は中間コード４
を解釈して、中間コード４と、比較パラメータとパケッ
トヘッダ部分の比較結果を各ＣＰＵが共有するための比
較結果ビットと、アクセス制御規則とパケットへッダ部
分が一致しないことを示す不成立ビットと、これらを結
ぶポインタとで構成する並列実行コード１３を生成す
る。
を解釈して、中間コード４と、比較パラメータとパケッ
トヘッダ部分の比較結果を各ＣＰＵが共有するための比
較結果ビットと、アクセス制御規則とパケットへッダ部
分が一致しないことを示す不成立ビットと、これらを結
ぶポインタとで構成する並列実行コード１３を生成す
る。
【００４４】図７は並列実行コードの一例である。並列
実行コード生成部１２は、中間コード４から比較パラメ
ータの共通部分を抽出し、図７に示したように、比較パ
ラメータの共通部分毎に比較結果ビットを用意し、ポイ
ンタを作成する。図７に示した２つのアクセス制御規則
では、プロトコル種類と終点アドレスの比較パラメータ
が、各々”ＴＣＰ”、”＝１１．２２＊．＊”で共通し
ていることから、各々の比較パラメータが共有する比較
結果ビットを用意し、ポインタを張っている。
実行コード生成部１２は、中間コード４から比較パラメ
ータの共通部分を抽出し、図７に示したように、比較パ
ラメータの共通部分毎に比較結果ビットを用意し、ポイ
ンタを作成する。図７に示した２つのアクセス制御規則
では、プロトコル種類と終点アドレスの比較パラメータ
が、各々”ＴＣＰ”、”＝１１．２２＊．＊”で共通し
ていることから、各々の比較パラメータが共有する比較
結果ビットを用意し、ポインタを張っている。
【００４５】比較結果ビットは、比較パラメータとパケ
ットヘッダ部分の比較が未実行であることを示す“ＮＯ
ＮＥ”、比較パラメータとパケットヘッダ部分が一致し
たことを示す“ＴＲＵＥ”、比較パラメータとパケット
ヘッダ部分が不一致であることを示す“ＦＡＬＳＥ”の
３つの値をとる。
ットヘッダ部分の比較が未実行であることを示す“ＮＯ
ＮＥ”、比較パラメータとパケットヘッダ部分が一致し
たことを示す“ＴＲＵＥ”、比較パラメータとパケット
ヘッダ部分が不一致であることを示す“ＦＡＬＳＥ”の
３つの値をとる。
【００４６】また、並列実行コード生成部１２は、アク
セス制御規則毎に不成立ビットを用意し、図７に示した
ように、比較結果ビットから不成立ビットへのポインタ
を作成する。図７に示した２つのアクセス制御規則で
は、プロトコル種類と終点アドレスの比較パラメータが
比較結果ビットを共有しているので、比較結果ビットか
ら、これらアクセス制御規則の不成立ビットへポインタ
を張っている。
セス制御規則毎に不成立ビットを用意し、図７に示した
ように、比較結果ビットから不成立ビットへのポインタ
を作成する。図７に示した２つのアクセス制御規則で
は、プロトコル種類と終点アドレスの比較パラメータが
比較結果ビットを共有しているので、比較結果ビットか
ら、これらアクセス制御規則の不成立ビットへポインタ
を張っている。
【００４７】不成立ビットは、アクセス制御規則とパケ
ットヘッダ部分の比較結果が不明であり、かつ、いずれ
のＣＰＵもアクセス制御規則とパケットヘッダ部分の比
較を行なっていないことを示す“ＮＯＮＥ”と、アクセ
ス制御規則とパケットヘッダ部分の比較結果は不明だ
が、あるＣＰＵがアクセス制御規則とパケットヘッダ部
分の比較を行なっていることを示す“ＡＣＴＩＶＥ”
と、アクセス制御規則とパケットヘッダ部分の比較結果
が不一致であることを示す“ＦＡＬＳＥ”の３種類の値
をとる。
ットヘッダ部分の比較結果が不明であり、かつ、いずれ
のＣＰＵもアクセス制御規則とパケットヘッダ部分の比
較を行なっていないことを示す“ＮＯＮＥ”と、アクセ
ス制御規則とパケットヘッダ部分の比較結果は不明だ
が、あるＣＰＵがアクセス制御規則とパケットヘッダ部
分の比較を行なっていることを示す“ＡＣＴＩＶＥ”
と、アクセス制御規則とパケットヘッダ部分の比較結果
が不一致であることを示す“ＦＡＬＳＥ”の３種類の値
をとる。
【００４８】並列型パケットフィルタ実行部１４は、有
限個のＣＰＵと共有メモリ１５をシステムバス１８で接
続した構成をとる。各ＣＰＵは共有メモリ１５に格納さ
れた任意のデータの読み出し、書き込みが可能である。
図６に示すように、共有メモリ１５には、並列実行コー
ド生成部１２が出力した並列実行コード１３と、並列実
行コード１３のアクセス制御規則を指し示すキャッシュ
ポインタを格納する。
限個のＣＰＵと共有メモリ１５をシステムバス１８で接
続した構成をとる。各ＣＰＵは共有メモリ１５に格納さ
れた任意のデータの読み出し、書き込みが可能である。
図６に示すように、共有メモリ１５には、並列実行コー
ド生成部１２が出力した並列実行コード１３と、並列実
行コード１３のアクセス制御規則を指し示すキャッシュ
ポインタを格納する。
【００４９】並列型パケットフィルタ実行部１４におけ
る各ＣＰＵのパケットフィルタ処理動作を以下に具体的
に説明する。パケットフィルタ処理に先立ち、全ての不
成立ビットと全ての比較結果ビットは“ＮＯＮＥ”に初
期化する。
る各ＣＰＵのパケットフィルタ処理動作を以下に具体的
に説明する。パケットフィルタ処理に先立ち、全ての不
成立ビットと全ての比較結果ビットは“ＮＯＮＥ”に初
期化する。
【００５０】１．キャッシュポインタが指し示すアクセ
ス制御規則の不成立ビットの値が“ＮＯＮＥ”の場合に
は、そのアクセス制御規則を読み出し、不成立ビットの
値が“ＡＣＴＩＶＥ”、あるいは、“ＦＡＬＳＥ”の場
合には、不成立ビットが“ＮＯＮＥ”であるアクセス制
御規則を動的に選択して、読み出す。
ス制御規則の不成立ビットの値が“ＮＯＮＥ”の場合に
は、そのアクセス制御規則を読み出し、不成立ビットの
値が“ＡＣＴＩＶＥ”、あるいは、“ＦＡＬＳＥ”の場
合には、不成立ビットが“ＮＯＮＥ”であるアクセス制
御規則を動的に選択して、読み出す。
【００５１】２．読み出したアクセス制御規則の不成立
ビットに“ＡＣＴＩＶＥ”を書き込む。
ビットに“ＡＣＴＩＶＥ”を書き込む。
【００５２】３．読み出したアクセス制御規則のパケッ
ト条件を構成する６種類の比較パラメータについて、順
番に選択し、受信したパケットのヘッダ部分と比較す
る。全ての比較パラメータとの比較結果を得るまで、下
記４から１０を繰り返す。
ト条件を構成する６種類の比較パラメータについて、順
番に選択し、受信したパケットのヘッダ部分と比較す
る。全ての比較パラメータとの比較結果を得るまで、下
記４から１０を繰り返す。
【００５３】４．比較パラメータが比較結果ビットを持
つ場合には比較結果ビットの値を調べる。比較結果ビッ
トの値が“ＦＡＬＳＥ”の場合は５へ、“ＴＲＵＥ”の
場合は６へ、“ＮＯＮＥ”の場合は７へ行く。比較パラ
メータが比較結果ビットを持たない場合には７へ行く。
つ場合には比較結果ビットの値を調べる。比較結果ビッ
トの値が“ＦＡＬＳＥ”の場合は５へ、“ＴＲＵＥ”の
場合は６へ、“ＮＯＮＥ”の場合は７へ行く。比較パラ
メータが比較結果ビットを持たない場合には７へ行く。
【００５４】５．現在選択中のアクセス制御規則は、受
信パケットのヘッダ部分と不一致であるので、新たなア
クセス制御規則を選択するために、１へ戻る。
信パケットのヘッダ部分と不一致であるので、新たなア
クセス制御規則を選択するために、１へ戻る。
【００５５】６．この比較パラメータは、パケットヘッ
ダ部分と一致することが明確なので、比較を行なわず、
次なる比較パラメータを選択し、４へ戻る。
ダ部分と一致することが明確なので、比較を行なわず、
次なる比較パラメータを選択し、４へ戻る。
【００５６】７．比較パラメータと受信パケットのヘッ
ダ部分との比較を行なう。比較結果が不一致の場合には
８へ、一致した場合には９へ行く。
ダ部分との比較を行なう。比較結果が不一致の場合には
８へ、一致した場合には９へ行く。
【００５７】８．比較パラメータが比較結果ビットを持
つ場合には、比較結果ビットに“ＦＡＬＳＥ”を書き込
み、比較結果ビットが指し示す全ての不成立ビットに
“ＦＡＬＳＥ”を書き込む。そして、現在選択中のアク
セス制御規則は、受信パケットのヘッダ部分と一致しな
いので、新たなアクセス制御規則を選択するために、１
へ戻る。
つ場合には、比較結果ビットに“ＦＡＬＳＥ”を書き込
み、比較結果ビットが指し示す全ての不成立ビットに
“ＦＡＬＳＥ”を書き込む。そして、現在選択中のアク
セス制御規則は、受信パケットのヘッダ部分と一致しな
いので、新たなアクセス制御規則を選択するために、１
へ戻る。
【００５８】９．比較パラメータが比較結果ビットを持
つ場合には、比較結果ビットに“ＴＲＵＥ”を書き込
む。そして、次なる比較パラメータを選択し、４へ戻
る。
つ場合には、比較結果ビットに“ＴＲＵＥ”を書き込
む。そして、次なる比較パラメータを選択し、４へ戻
る。
【００５９】１０．選択したアクセス制御規則の全ての
比較パラメータが受信パケットのヘッダ部分と一致する
まで、１から１０を繰り返す。
比較パラメータが受信パケットのヘッダ部分と一致する
まで、１から１０を繰り返す。
【００６０】１１．選択したアクセス制御規則の全ての
比較パラメータが、パケットのヘッダ部分と一致したこ
とから、選択したアクセス制御規則のルータ動作の値に
従って、パケットの転送、あるいは、廃棄を行なう。
比較パラメータが、パケットのヘッダ部分と一致したこ
とから、選択したアクセス制御規則のルータ動作の値に
従って、パケットの転送、あるいは、廃棄を行なう。
【００６１】１２．選択したアクセス制御規則を指し示
すよう、キャッシュポインタを書き換える。
すよう、キャッシュポインタを書き換える。
【００６２】
【発明の効果】以上説明したように、本発明では、逐次
的な解釈が必要なアクセス制御プログラムの依存関係を
解析し、並列に解釈可能な中間コードに変換することに
より、任意の順序でアクセス制御規則とパケットヘッダ
部分との比較が可能となる。これにより、逐次実行型パ
ケットフィルタ実行部では、パケットフィルタ処理時間
が木構造の高さに依存する逐次実行コードが生成可能と
なり、また、並列型パケットフィルタ実行部では、複数
個のＣＰＵが並列にパケットフィルタ処理を行なうこと
が可能となる。よって、従来のパケットフィルタ処理技
術において、パケットフィルタ処理時間がアクセス制御
プログラムの行数に比例する問題が解消できるという効
果がある。
的な解釈が必要なアクセス制御プログラムの依存関係を
解析し、並列に解釈可能な中間コードに変換することに
より、任意の順序でアクセス制御規則とパケットヘッダ
部分との比較が可能となる。これにより、逐次実行型パ
ケットフィルタ実行部では、パケットフィルタ処理時間
が木構造の高さに依存する逐次実行コードが生成可能と
なり、また、並列型パケットフィルタ実行部では、複数
個のＣＰＵが並列にパケットフィルタ処理を行なうこと
が可能となる。よって、従来のパケットフィルタ処理技
術において、パケットフィルタ処理時間がアクセス制御
プログラムの行数に比例する問題が解消できるという効
果がある。
【００６３】また、ＡＣＰ並列化コンパイラが中間コー
ドを生成する際に、比較パラメータの簡単化を行なうと
ともに、単一ＣＰＵ環境では中間コードスケジューラ部
が中間コードで共通する比較パラメータを抽出し、これ
らが木構造の同一パスとなるよう逐次実行コードを構築
し、あるいは、有限個のＣＰＵ環境では並列実行コード
生成部が中間コードで共通する比較パラメータを抽出
し、パケットヘッダ部分との比較結果を各ＣＰＵが共有
できるように並列実行コードを生成することにより、従
来のパケットフィルタ処理技術において、アクセス制御
プログラムに同一の値を持つ複数のアクセス制御規則が
記述された場合に同じ比較演算を複数回行なってしまう
問題が解消できる効果がある。
ドを生成する際に、比較パラメータの簡単化を行なうと
ともに、単一ＣＰＵ環境では中間コードスケジューラ部
が中間コードで共通する比較パラメータを抽出し、これ
らが木構造の同一パスとなるよう逐次実行コードを構築
し、あるいは、有限個のＣＰＵ環境では並列実行コード
生成部が中間コードで共通する比較パラメータを抽出
し、パケットヘッダ部分との比較結果を各ＣＰＵが共有
できるように並列実行コードを生成することにより、従
来のパケットフィルタ処理技術において、アクセス制御
プログラムに同一の値を持つ複数のアクセス制御規則が
記述された場合に同じ比較演算を複数回行なってしまう
問題が解消できる効果がある。
【００６４】また、ＡＣＰ並列化コンパイラが比較パラ
メータの簡単化を行なう際、パケット条件が空集合とな
るアクセス制御規則を中間コードから削除することによ
り、従来のパケットフィルタ処理技術において、実行不
能経路のパケット条件を比較してしまう問題が解消でき
る。
メータの簡単化を行なう際、パケット条件が空集合とな
るアクセス制御規則を中間コードから削除することによ
り、従来のパケットフィルタ処理技術において、実行不
能経路のパケット条件を比較してしまう問題が解消でき
る。
【００６５】これらの結果に基づき、本発明によれば、
アクセス制御プログラムの行数がパケットフィルタ処理
能力、さらには、パケットルータ処理装置のパケット転
送能力に影響を及ぼさない、高速かつ効率的なパケット
フィルタ処理装置が実現可能となるという効果がある。
アクセス制御プログラムの行数がパケットフィルタ処理
能力、さらには、パケットルータ処理装置のパケット転
送能力に影響を及ぼさない、高速かつ効率的なパケット
フィルタ処理装置が実現可能となるという効果がある。
【図１】本発明のパケット処理装置の第１の実施例のシ
ステム構成図である。
ステム構成図である。
【図２】アクセス制御プログラムの一例である。
【図３】ＡＣＰ並列化コンパイラが生成する中間コード
の一例である。
の一例である。
【図４】本発明のパケット処理装置の第２の実施例で、
単一ＣＰＵによるパケットフィルタ実行部の一構成例で
ある。
単一ＣＰＵによるパケットフィルタ実行部の一構成例で
ある。
【図５】中間コードスケジューラが生成する逐次実行コ
ードの一例である。
ードの一例である。
【図６】本発明のパケット処理装置の第３の実施例で、
有限個のＣＰＵによるパケットフィルタ部の一構成例で
ある。
有限個のＣＰＵによるパケットフィルタ部の一構成例で
ある。
【図７】並列実行コード生成部により生成した並列実行
コードの一例である。
コードの一例である。
【図８】従来のパケットルータ処理装置の一構成例であ
る。
る。
１ アクセス制御プログラム １1 パケット条件 １2 ルータ動作 １3 比較パラメータ ２ パケットフィルタ部 ３ アクセス制御プログラム並列化コンパイラ部 ４ 中間コード ５ パケットフィルタ実行部 ６ ルートテーブル検索部 ７ 経路情報格納テーブル ８、８1、８2、８3 回線対応部 ９ 中間コードスケジューラ部 １０ 逐次実行コード １１ 逐次型パケットフィルタ実行部 １２ 並列実行コード生成部 １３ 並列実行コード １４ 並列型パケットフィルタ実行部 １５ 共有メモリ １６ 並列実行コード格納テーブル １７ キャッシュテーブル １８ システムバス ２１ パケットフィルタ部 ２２ ルートテーブル検索部 ２３ 経路情報格納テーブル
───────────────────────────────────────────────────── フロントページの続き (72)発明者 小倉 毅 東京都新宿区西新宿三丁目19番２号 日本 電信電話株式会社内
Claims (8)
- 【請求項１】 複数種類の比較パラメータからなるパケ
ット条件、および、パケット条件に一致したパケットの
転送、あるいは、廃棄を定義する複数行のアクセス制御
規則からなるアクセス制御プログラムを入力し、該アク
セス制御プログラムに従ってパケットのヘッダを解析
し、パケットの転送、または、廃棄を決定するパケット
フィルタ部と、経路情報を検索して、転送パケットの回
線を決定するルートテーブル検索部を有するパケット処
理装置において、 前記パケットフィルタ部がアクセス制御プログラムコン
パイラ部とパケットフィルタ実行部とからなり、 アクセス制御プログラムコンパイラ部は、アクセス制御
プログラムを変換して中間コードを生成する手段を有
し、 パケットフィルタ実行部は、前記中間コードを解釈し
て、通信回線から受信したパケットのヘッダ部分と比較
し、比較結果に従ってパケットの転送あるいは廃棄を決
定する手段を有することを特徴とするパケット処理装
置。 - 【請求項２】 前記アクセス制御プログラムが逐次的な
解釈が必要な依存関係を持つ複数行のアクセス制御規則
からなり、 前記アクセス制御プログラムコンパイラ部が、アクセス
制御プログラムの依存関係を解釈し、経路条件に基づい
て並列に解釈可能なアクセス制御規則からなる中間コー
ドに変換する手段を有する、アクセス制御プログラム並
列化コンパイラ部である請求項１記載のパケット処理装
置。 - 【請求項３】 前記アクセス制御プログラム並列化コン
パイラ部が、比較パラメータの数に従って中間コードを
分割し生成する請求項２記載のパケット処理装置。 - 【請求項４】 前記アクセス制御プログラム並列化コン
パイラ部が、アクセス制御プログラムを変換した結果か
ら、条件と一致するパケットが同一となる複数の比較パ
ラメータ、または、条件と一致するパケットが部分集合
となる２つの比較パラメータを検出し、これらの比較パ
ラメータを集合の間の演算を用いて簡単化する機能を有
する請求項２または３に記載のパケット処理装置。 - 【請求項５】 前記アクセス制御プログラム並列化コン
パイラ部が、比較パラメータの簡単化によりパケット条
件が空集合となるアクセス制御規則を中間コードから削
除する機能を有する請求項４記載のパケット処理装置。 - 【請求項６】 前記パケットフィルタ部が、入力された
複数のアクセス制御規則を解釈してパケットヘッダ部分
とパケット条件との比較順序を決定する手段と、比較パ
ラメータを示すノードと、ノードが示す比較パラメータ
とパケットヘッダ部分の比較結果に従って、次に比較す
べきノードを示す枝と、パケット条件に一致したパケッ
トの転送、あるいは、廃棄を示す葉で構成する木構造の
逐次実行コードを生成する、中間コードスケジューラ部
を有し、 かつ、前記パケットフィルタ実行部が、中間コードスケ
ジューラ部が生成した逐次実行コードを解釈し、通信回
線から受信したデータパケットのヘッダ部分を解析し、
中間コードスケジューラ部が生成した木構造の逐次実行
コードの根のノードから順にパケットヘッダ部分との比
較を行ない、到達した葉の値に従ってパケットの転送あ
るいは廃棄を決定する、逐次型パケットフィルタ実行部
である請求項１記載のパケット処理装置。 - 【請求項７】 前記パケットフィルタ部が、入力された
複数のアクセス制御規則から各アクセス制御規則の共通
する比較パラメータを抽出する手段と、入力された複数
のアクセス制御規則に共通する比較パラメータとパケッ
トヘッダ部分との比較結果を各ＣＰＵが共有するための
比較結果ビットと、各アクセス制御規則にアクセス制御
規則とパケットヘッダ部分の比較結果を保持するための
不成立ビットを加えて並列実行コードを生成する、並列
実行コード生成部を有し、 かつ、パケットフィルタ実行部が、有限個のＣＰＵを有
し、並列実行コード生成部が出力した並列実行コードを
解釈し、不成立ビットの値に基づいて未実行ノアクセス
制御規則を動的に選択する手段と、選択したアクセス制
御規則とパケットヘッダ部分との比較を行い、パケット
の転送、あるいは、廃棄を決定する手段と、比較結果ビ
ットを持つ比較パラメータとパケットヘッダ部分の比較
結果に従って比較結果ビットを書き換える手段を有す
る、並列型パケットフィルタ実行部である請求項１記載
のパケット処理装置。 - 【請求項８】 前記アクセス制御規則を選択的に指し示
すキャッシュポインタを有し、前記並列型パケットフィ
ルタ実行部が、直近の並列実行コードとパケットヘッダ
部分を比較し、パケット条件が一致したアクセス制御規
則へのポインタをキャッシュポインタとして保存する手
段と、未実行のアクセス制御規則を動的に選択する際に
キャッシュポインタが指し示すアクセス制御規則を優先
的に選択する手段を有する請求項７記載のパケット処理
装置。
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP22523996A JP3219186B2 (ja) | 1996-08-27 | 1996-08-27 | パケット処理装置 |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP22523996A JP3219186B2 (ja) | 1996-08-27 | 1996-08-27 | パケット処理装置 |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| JPH1070570A true JPH1070570A (ja) | 1998-03-10 |
| JP3219186B2 JP3219186B2 (ja) | 2001-10-15 |
Family
ID=16826184
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP22523996A Expired - Fee Related JP3219186B2 (ja) | 1996-08-27 | 1996-08-27 | パケット処理装置 |
Country Status (1)
| Country | Link |
|---|---|
| JP (1) | JP3219186B2 (ja) |
Cited By (3)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JP2000209263A (ja) * | 1999-01-11 | 2000-07-28 | Sanyo Electric Co Ltd | デジタル放送受信機におけるｔｓデ―タフィルタリング回路 |
| JP2001134225A (ja) * | 1999-08-26 | 2001-05-18 | Toppan Printing Co Ltd | 広告提供装置及び広告提供装置用の記憶媒体、展示具、表示パネル、表示ケース |
| US6301669B2 (en) * | 1998-08-17 | 2001-10-09 | International Business Machines Corporation | System and method for very fast IP packet filtering |
Citations (4)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JPH06350608A (ja) * | 1993-06-07 | 1994-12-22 | Sumitomo Electric Ind Ltd | ネットワーク用中継装置 |
| JPH0746244A (ja) * | 1993-07-28 | 1995-02-14 | Nippon Telegr & Teleph Corp <Ntt> | 光ａｔｍ交換機 |
| JPH0844642A (ja) * | 1993-12-15 | 1996-02-16 | Checkpoint Software Technol Ltd | コンピュータネットワークの制御方法及び保安システム |
| JPH09135271A (ja) * | 1995-11-08 | 1997-05-20 | Fujitsu Ltd | 中継装置 |
-
1996
- 1996-08-27 JP JP22523996A patent/JP3219186B2/ja not_active Expired - Fee Related
Patent Citations (4)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JPH06350608A (ja) * | 1993-06-07 | 1994-12-22 | Sumitomo Electric Ind Ltd | ネットワーク用中継装置 |
| JPH0746244A (ja) * | 1993-07-28 | 1995-02-14 | Nippon Telegr & Teleph Corp <Ntt> | 光ａｔｍ交換機 |
| JPH0844642A (ja) * | 1993-12-15 | 1996-02-16 | Checkpoint Software Technol Ltd | コンピュータネットワークの制御方法及び保安システム |
| JPH09135271A (ja) * | 1995-11-08 | 1997-05-20 | Fujitsu Ltd | 中継装置 |
Cited By (3)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US6301669B2 (en) * | 1998-08-17 | 2001-10-09 | International Business Machines Corporation | System and method for very fast IP packet filtering |
| JP2000209263A (ja) * | 1999-01-11 | 2000-07-28 | Sanyo Electric Co Ltd | デジタル放送受信機におけるｔｓデ―タフィルタリング回路 |
| JP2001134225A (ja) * | 1999-08-26 | 2001-05-18 | Toppan Printing Co Ltd | 広告提供装置及び広告提供装置用の記憶媒体、展示具、表示パネル、表示ケース |
Also Published As
| Publication number | Publication date |
|---|---|
| JP3219186B2 (ja) | 2001-10-15 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| CN112558948B (zh) | 一种海量流量下报文识别的方法和装置 | |
| US6651096B1 (en) | Method and apparatus for organizing, storing and evaluating access control lists | |
| US8819217B2 (en) | Intelligent graph walking | |
| CN103312615B (zh) | 使用可变数量前缀的最长前缀匹配搜索 | |
| US7246102B2 (en) | Method of improving the lookup performance of three-type knowledge base searches | |
| US7949683B2 (en) | Method and apparatus for traversing a compressed deterministic finite automata (DFA) graph | |
| JP3651589B2 (ja) | ネットワーク・プロセッサ用の完全一致（ｆｍ）サーチ・アルゴリズムの実装 | |
| CA2469874C (en) | Routing and forwarding table management for network processor architectures | |
| US8176300B2 (en) | Method and apparatus for content based searching | |
| US20040100956A1 (en) | Packet search device, packet processing search method used for the same, and program for the same | |
| US8751655B2 (en) | Collective acceleration unit tree structure | |
| CN104243344B (zh) | 一种有效数据包捕获方法及请求重定向服务器 | |
| US20030110208A1 (en) | Processing data across packet boundaries | |
| EP1010304A4 (en) | APPARATUS AND METHOD FOR ROUTING DATA PACKETS THROUGH A COMMUNICATIONS NETWORK | |
| CN104426909A (zh) | 为具有高级特征的正则表达式图样生成非确定有限自动机(nfa)图形 | |
| US20080186974A1 (en) | System and method to process data packets in a network using stateful decision trees | |
| US7937495B2 (en) | System and method for modifying data transferred from a source to a destination | |
| US5881241A (en) | System for transmitting data packet after matching data packet's routing pattern with predetermined data routes stored in a route table | |
| KR102014741B1 (ko) | Fpga 기반 고속 스노트 룰과 야라 룰 매칭 방법 | |
| JP3219186B2 (ja) | パケット処理装置 | |
| US12513116B2 (en) | GOTO action in network traffic policies | |
| US11128602B2 (en) | Efficient matching of feature-rich security policy with dynamic content using user group matching | |
| Kang et al. | Verikube: Automatic and efficient verification for container network policies | |
| KR100864889B1 (ko) | Ｔｃｐ 상태 기반 패킷 필터 장치 및 그 방법 | |
| CN104714995A (zh) | 用于遍历为具有高级特征的正则表达式图样生成的非确定有限自动机(nfa)的系统和方法 |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20080810 Year of fee payment: 7 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20080810 Year of fee payment: 7 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20090810 Year of fee payment: 8 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20090810 Year of fee payment: 8 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20100810 Year of fee payment: 9 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20100810 Year of fee payment: 9 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20110810 Year of fee payment: 10 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20120810 Year of fee payment: 11 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20130810 Year of fee payment: 12 |
|
| LAPS | Cancellation because of no payment of annual fees |