JP2000270021A - パケット分類装置 - Google Patents
パケット分類装置Info
- Publication number
- JP2000270021A JP2000270021A JP7132599A JP7132599A JP2000270021A JP 2000270021 A JP2000270021 A JP 2000270021A JP 7132599 A JP7132599 A JP 7132599A JP 7132599 A JP7132599 A JP 7132599A JP 2000270021 A JP2000270021 A JP 2000270021A
- Authority
- JP
- Japan
- Prior art keywords
- key
- function
- value
- packet
- expansion table
- 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
- Data Exchanges In Wide-Area Networks (AREA)
Abstract
(57)【要約】
【課題】 探索処理時間がルール数に依存せず、ルール
の条件に対して最長プレフィクス照合及び領域照合を用
いる場合においても、比較的少ないハードウェアによ
り、探索処理を高速に行うことができるパケット分類装
置を提供する。 【解決手段】 キーフィールドが満たすべき条件を定め
たルールの集合であるルールセットからパケットが全て
の条件を満たすルールを見つけ出すためのパケット分類
装置において、予めルールセットをドメイン記述子及び
展開表に変換するコンパイル機能、並びに、パケットの
キーの値及びドメイン記述子の値によって定まるアドレ
スに位置する展開表のエントリーの値によって次のキー
の位置及びドメイン記述子のアドレスを決定する探索機
能を具え、該探索機能が受信パケットのキーの値に従っ
て前記コンパイル機能が生成したデータを辿る。
の条件に対して最長プレフィクス照合及び領域照合を用
いる場合においても、比較的少ないハードウェアによ
り、探索処理を高速に行うことができるパケット分類装
置を提供する。 【解決手段】 キーフィールドが満たすべき条件を定め
たルールの集合であるルールセットからパケットが全て
の条件を満たすルールを見つけ出すためのパケット分類
装置において、予めルールセットをドメイン記述子及び
展開表に変換するコンパイル機能、並びに、パケットの
キーの値及びドメイン記述子の値によって定まるアドレ
スに位置する展開表のエントリーの値によって次のキー
の位置及びドメイン記述子のアドレスを決定する探索機
能を具え、該探索機能が受信パケットのキーの値に従っ
て前記コンパイル機能が生成したデータを辿る。
Description
【０００１】
【発明の属する技術分野】本発明は、受信パケットの一
部であるキーフィールドを調べてその内容に従って対応
するデータを選択するシステムのためのパケット分類装
置に関するものであり、更に詳しくは、キーフィールド
が満たすべき条件を定めたルールの集合であるルールセ
ットからパケットが全ての条件を満たすルールを見つけ
出すためのパケット分類装置に関するものである。
部であるキーフィールドを調べてその内容に従って対応
するデータを選択するシステムのためのパケット分類装
置に関するものであり、更に詳しくは、キーフィールド
が満たすべき条件を定めたルールの集合であるルールセ
ットからパケットが全ての条件を満たすルールを見つけ
出すためのパケット分類装置に関するものである。
【０００２】
【従来の技術】パケット分類装置には、一般的に大別す
ると、探索すべきデータを作成するためのコンパイル処
理機能及び探索処理機能が具えられている。従来のパケ
ット分類装置としてアクセス制御リストを用いるパケッ
トフィルタリングのためのパケット分類装置を例とし
て、これらの処理機能を説明する。
ると、探索すべきデータを作成するためのコンパイル処
理機能及び探索処理機能が具えられている。従来のパケ
ット分類装置としてアクセス制御リストを用いるパケッ
トフィルタリングのためのパケット分類装置を例とし
て、これらの処理機能を説明する。
【０００３】先ず、コンパイル処理機能では、アクセス
制御リスト（ＡＣＬ）を内部表現に変換して図10のよう
なデータ即ちＡＣＬ内部表現を作成する。ここでＡＣＬ
は、各キーの値が満たすべき条件、及び、それらを満た
すパケットを通過させるか棄却するかを指定するアクシ
ョンの組を定めるルールの系列である。ＡＣＬ内部表現
の各行がＡＣＬの１つのルールに対応する。送信先アド
レス、送信元アドレス、送信先ポート番号、送信元ポー
ト番号、プロトコルフィールド、ＴＣＰフラグ等のフィ
ールドをキーとして用いる。
制御リスト（ＡＣＬ）を内部表現に変換して図10のよう
なデータ即ちＡＣＬ内部表現を作成する。ここでＡＣＬ
は、各キーの値が満たすべき条件、及び、それらを満た
すパケットを通過させるか棄却するかを指定するアクシ
ョンの組を定めるルールの系列である。ＡＣＬ内部表現
の各行がＡＣＬの１つのルールに対応する。送信先アド
レス、送信元アドレス、送信先ポート番号、送信元ポー
ト番号、プロトコルフィールド、ＴＣＰフラグ等のフィ
ールドをキーとして用いる。
【０００４】ルールでは、完全一致照合、プレフィクス
照合及び領域照合のような照合方法を用いて各キーに対
する条件を指定する。完全一致照合では、条件がキーの
値ｕで表され、受信パケットのキーの値がｕの場合に照
合に成功する。プレフィクス照合では、条件がキーのプ
レフィクス値ｖとプレフィクス長plの対v/plで表され、
受信パケットのキーの値の上記plビットがｖの場合に照
合に成功する。例えば送信先アドレスに対するプレフィ
クス照合では、条件123.45.67/24は、送信先アドレスの
上位24ビットが123.45.67 であるパケットと照合に成功
する。また、ＡＣＬにおいて複数のルールが照合に成功
した場合に、プレフィクス長が最長のルールを選択して
照合結果とする方法を最長プレフィクス照合という。ま
た、領域照合では、条件がキーの値の対の集合
｛〔ｗ11，ｗ12〕，〔ｗ21，ｗ22〕,...,〔ｗn1，
ｗn2〕｝で表され、キーの値ｋがｗi1≧ｋ≧ｗi2なるｉ
が存在する場合に照合に成功する。例えば送信先ポート
番号の領域照合では、フィルタの述語｛〔10，30〕，
〔50，60〕｝は、受信パケットの送信先ポート番号ｐが
10≧ｐ≧30又は50≧ｐ≧60の場合に照合に成功する。
照合及び領域照合のような照合方法を用いて各キーに対
する条件を指定する。完全一致照合では、条件がキーの
値ｕで表され、受信パケットのキーの値がｕの場合に照
合に成功する。プレフィクス照合では、条件がキーのプ
レフィクス値ｖとプレフィクス長plの対v/plで表され、
受信パケットのキーの値の上記plビットがｖの場合に照
合に成功する。例えば送信先アドレスに対するプレフィ
クス照合では、条件123.45.67/24は、送信先アドレスの
上位24ビットが123.45.67 であるパケットと照合に成功
する。また、ＡＣＬにおいて複数のルールが照合に成功
した場合に、プレフィクス長が最長のルールを選択して
照合結果とする方法を最長プレフィクス照合という。ま
た、領域照合では、条件がキーの値の対の集合
｛〔ｗ11，ｗ12〕，〔ｗ21，ｗ22〕,...,〔ｗn1，
ｗn2〕｝で表され、キーの値ｋがｗi1≧ｋ≧ｗi2なるｉ
が存在する場合に照合に成功する。例えば送信先ポート
番号の領域照合では、フィルタの述語｛〔10，30〕，
〔50，60〕｝は、受信パケットの送信先ポート番号ｐが
10≧ｐ≧30又は50≧ｐ≧60の場合に照合に成功する。
【０００５】一般的に、採用する照合方法をルールのキ
ー毎に予め定めておく。図10において、ｄは送信先アド
レス、ｓは送信元アドレス、d-p は送信先ポート番号、
s-pは送信元ポート番号、ｐはプロトコルフィールド、T
CP はＴＣＰフラグであり、アクションについては、１
は通過を、０は棄却を、それぞれ指示するアクションを
表す。図の左側の１〜ｍはルールの番号を表し、図の右
側の矢印は探索の順番を表す。ルール１では、送信先ア
ドレスが1.2.3.4 、送信元アドレスが1.2.5.8、送信先
ポート番号が10以上40以下、送信元ポート番号が80、プ
ロトコルフィールドが10、ＴＣＰフラグが１の時に、パ
ケットの通過を許可することを示す。
ー毎に予め定めておく。図10において、ｄは送信先アド
レス、ｓは送信元アドレス、d-p は送信先ポート番号、
s-pは送信元ポート番号、ｐはプロトコルフィールド、T
CP はＴＣＰフラグであり、アクションについては、１
は通過を、０は棄却を、それぞれ指示するアクションを
表す。図の左側の１〜ｍはルールの番号を表し、図の右
側の矢印は探索の順番を表す。ルール１では、送信先ア
ドレスが1.2.3.4 、送信元アドレスが1.2.5.8、送信先
ポート番号が10以上40以下、送信元ポート番号が80、プ
ロトコルフィールドが10、ＴＣＰフラグが１の時に、パ
ケットの通過を許可することを示す。
【０００６】次に、探索処理では、図10の矢印で示すよ
うに、受信パケットが与えられるとＡＣＬ内部表現の上
から順番にルールを調べ、各キーに応じた照合方法によ
りパケットのキーの値を調べて、全てのキーが照合に成
功するルールが見出された場合に、アクションの記述に
従ってそのパケットを通過させるか棄却するかを決定す
る。
うに、受信パケットが与えられるとＡＣＬ内部表現の上
から順番にルールを調べ、各キーに応じた照合方法によ
りパケットのキーの値を調べて、全てのキーが照合に成
功するルールが見出された場合に、アクションの記述に
従ってそのパケットを通過させるか棄却するかを決定す
る。
【０００７】これらの従来のパケット分類装置において
は、第１に、ＡＣＬを上から順番に調べるのでルール数
が多くなると探索処理の時間が長くなることがある。最
悪の場合、全ルールを調べるための時間を要することと
なる。このため、探索処理時間を短縮するために、探索
処理をハードウェア化する方法が提案されているが、ル
ール数に依存して探索処理時間が長くなるという問題点
は残されている。この問題点を解決するため、ルーティ
ングテーブルを用いるパケット分類が提案されている。
この分類ではパトリシア木等のディジタル探索木を用い
る方法がある。ここで、代表的なディジタル探索木であ
るパトリシア木を例として説明する。
は、第１に、ＡＣＬを上から順番に調べるのでルール数
が多くなると探索処理の時間が長くなることがある。最
悪の場合、全ルールを調べるための時間を要することと
なる。このため、探索処理時間を短縮するために、探索
処理をハードウェア化する方法が提案されているが、ル
ール数に依存して探索処理時間が長くなるという問題点
は残されている。この問題点を解決するため、ルーティ
ングテーブルを用いるパケット分類が提案されている。
この分類ではパトリシア木等のディジタル探索木を用い
る方法がある。ここで、代表的なディジタル探索木であ
るパトリシア木を例として説明する。
【０００８】先ず、ディジタル探索木で保持対象となる
見出しとしてＡ〜Ｚ及びnullの２７種類を考え、それぞ
れの符号の２進数表示を 00001〜11010 及び00000 とす
る。この符号の２進数表示では、最も左側のビットをビ
ット０とし、以下右側へ順にビット１，２，３，４とす
る。図11は、null,A,C,E,G,H,I,N,P,R,S,Tの１２個の見
出しが存在するパトリシア木である。図で大きい丸印は
節点、小さい丸印は葉、節点間又は節点と葉との間を結
ぶ線は枝を示す。節点又は葉の丸印の上側に記された数
値は節点又は葉を識別するための番号を表し、節点の丸
印の中に書かれた数値は検査ビット位置（その節点で調
べる探索キーの桁）を表し、葉の丸印の下側に記された
記号は、その葉の見出しを表す。節点０はディジタル探
索木の根であり、根を指している矩形はヘッドである。
パトリシア木では、探索キーが与えられた場合、探索木
の根から順に枝に沿って節点を辿り、探索キーに対して
検査ビット位置のビットが０の時は左側の節点に下が
り、そのビットが１の時は右側の節点に下がる。この操
作を繰り返すと、その探索キーに等しい見出しの葉が探
索木に存在する場合にはその葉に到達することができ
る。例えばＨを探索するには、Ｈの符号01000 を探索キ
ーとして用い、木の根の節点から順に節点が指示する検
査ビット位置の探索キーのビットの値を調べて節点を辿
って行けばよい。この場合、最初の節点で探索キーのビ
ット０を調べると０であるので左下の節点に行く。次の
節点でビット１を調べると１であるので右下の節点に行
く。このように、節点０，１，４，９の順に辿ってそれ
ぞれの探索キーのビット０，１，２，４を調べて行く
と、見出しＨの葉に至ることが分かる。
見出しとしてＡ〜Ｚ及びnullの２７種類を考え、それぞ
れの符号の２進数表示を 00001〜11010 及び00000 とす
る。この符号の２進数表示では、最も左側のビットをビ
ット０とし、以下右側へ順にビット１，２，３，４とす
る。図11は、null,A,C,E,G,H,I,N,P,R,S,Tの１２個の見
出しが存在するパトリシア木である。図で大きい丸印は
節点、小さい丸印は葉、節点間又は節点と葉との間を結
ぶ線は枝を示す。節点又は葉の丸印の上側に記された数
値は節点又は葉を識別するための番号を表し、節点の丸
印の中に書かれた数値は検査ビット位置（その節点で調
べる探索キーの桁）を表し、葉の丸印の下側に記された
記号は、その葉の見出しを表す。節点０はディジタル探
索木の根であり、根を指している矩形はヘッドである。
パトリシア木では、探索キーが与えられた場合、探索木
の根から順に枝に沿って節点を辿り、探索キーに対して
検査ビット位置のビットが０の時は左側の節点に下が
り、そのビットが１の時は右側の節点に下がる。この操
作を繰り返すと、その探索キーに等しい見出しの葉が探
索木に存在する場合にはその葉に到達することができ
る。例えばＨを探索するには、Ｈの符号01000 を探索キ
ーとして用い、木の根の節点から順に節点が指示する検
査ビット位置の探索キーのビットの値を調べて節点を辿
って行けばよい。この場合、最初の節点で探索キーのビ
ット０を調べると０であるので左下の節点に行く。次の
節点でビット１を調べると１であるので右下の節点に行
く。このように、節点０，１，４，９の順に辿ってそれ
ぞれの探索キーのビット０，１，２，４を調べて行く
と、見出しＨの葉に至ることが分かる。
【０００９】コンパイル処理でルールセットが図11のパ
トリシア木に変換されると、探索処理は以下のように行
われる。即ち、図11において、探索キーがＩ（符号0100
1)の葉を探索する場合、探索キーのビット０，１，２が
それぞれ０，１，０なので節点０，１，４の順に辿り、
節点９に到達する。節点９で探索キーのビット４を調べ
ると１なので葉18に到達する。葉18の見出しはＩで探索
キーと等しいので、求めるべき葉に到達したことが分か
る。この時、到達した葉の見出しが探索キーと等しくな
い場合は、探索したい葉がこのディジタル探索木に存在
しないことが判明する。
トリシア木に変換されると、探索処理は以下のように行
われる。即ち、図11において、探索キーがＩ（符号0100
1)の葉を探索する場合、探索キーのビット０，１，２が
それぞれ０，１，０なので節点０，１，４の順に辿り、
節点９に到達する。節点９で探索キーのビット４を調べ
ると１なので葉18に到達する。葉18の見出しはＩで探索
キーと等しいので、求めるべき葉に到達したことが分か
る。この時、到達した葉の見出しが探索キーと等しくな
い場合は、探索したい葉がこのディジタル探索木に存在
しないことが判明する。
【００１０】この方法では、探索処理時間がルール数に
依存しないので、前記の探索処理時間が長くなるという
問題は解決しているが、なお、ルールの条件として最長
プレフィクス照合を用いる場合にバックトラック或いは
ポインター操作が生じるため探索時間が長くなること、
ルールの条件として領域照合を用いる場合にパトリシア
木等のディジタル探索木をそのまま用いることができな
いこと、等の問題点がある。前者の問題点を解決するた
め、連想メモリーを用いる方法が提案されているが、こ
れは前記の後者の問題点を解決していないのに加え、更
に、ハードウェア量が多くなるため、ルール数が多い場
合に適用が困難であるという問題点がある。
依存しないので、前記の探索処理時間が長くなるという
問題は解決しているが、なお、ルールの条件として最長
プレフィクス照合を用いる場合にバックトラック或いは
ポインター操作が生じるため探索時間が長くなること、
ルールの条件として領域照合を用いる場合にパトリシア
木等のディジタル探索木をそのまま用いることができな
いこと、等の問題点がある。前者の問題点を解決するた
め、連想メモリーを用いる方法が提案されているが、こ
れは前記の後者の問題点を解決していないのに加え、更
に、ハードウェア量が多くなるため、ルール数が多い場
合に適用が困難であるという問題点がある。
【００１１】
【発明が解決しようとする課題】本発明の目的は、上述
の事情に鑑み、探索処理時間がルール数に依存せず、ル
ールの条件に対して最長プレフィクス照合及び領域照合
を用いる場合においても、比較的少ないハードウェアに
より、探索処理を高速に行うことができるパケット分類
装置を提供することにある。
の事情に鑑み、探索処理時間がルール数に依存せず、ル
ールの条件に対して最長プレフィクス照合及び領域照合
を用いる場合においても、比較的少ないハードウェアに
より、探索処理を高速に行うことができるパケット分類
装置を提供することにある。
【００１２】
【課題を解決するための手段】本発明の上記の目的は、
前述のようなパケット分類装置において、予めルールセ
ットをドメイン記述子及び展開表に変換するコンパイル
機能、並びに、パケットのキーの値及びドメイン記述子
の値によって定まるアドレスに位置する展開表のエント
リーの値によって次のキーの位置及びドメイン記述子の
アドレスを決定する探索機能を有し、該探索機能が受信
パケットのキーの値に従って前記コンパイル機能が生成
したデータを辿ることを特徴とするパケット分類装置に
よって達成される。
前述のようなパケット分類装置において、予めルールセ
ットをドメイン記述子及び展開表に変換するコンパイル
機能、並びに、パケットのキーの値及びドメイン記述子
の値によって定まるアドレスに位置する展開表のエント
リーの値によって次のキーの位置及びドメイン記述子の
アドレスを決定する探索機能を有し、該探索機能が受信
パケットのキーの値に従って前記コンパイル機能が生成
したデータを辿ることを特徴とするパケット分類装置に
よって達成される。
【００１３】本発明において、ドメイン記述子とは、キ
ーの値の定義域全体に対して、キーの値と展開表のエン
トリーとの対応付けを定めるデータである。また、展開
表とは、前記エントリーに対応するキーの値が条件を満
たさないルールを除外したルールセットに対して探索す
る時に用いるドメイン記述子のアドレスをエントリーす
る表である。
ーの値の定義域全体に対して、キーの値と展開表のエン
トリーとの対応付けを定めるデータである。また、展開
表とは、前記エントリーに対応するキーの値が条件を満
たさないルールを除外したルールセットに対して探索す
る時に用いるドメイン記述子のアドレスをエントリーす
る表である。
【００１４】このような本発明のパケット分類装置にお
いては、コンパイル機能が、キーの長さが長い場合に分
割し、短い場合に連結することにより、キーを固定長に
変換する機能を具えることができる。
いては、コンパイル機能が、キーの長さが長い場合に分
割し、短い場合に連結することにより、キーを固定長に
変換する機能を具えることができる。
【００１５】また、コンパイル機能が、キーの全ての値
について、対応する展開表のエントリーの識別子を保持
するドメイン記述子を生成する機能を具え、探索機能
が、キーの値に基づいてドメイン記述子から展開表のエ
ントリーのアドレスを求める機能を具えることができ
る。
について、対応する展開表のエントリーの識別子を保持
するドメイン記述子を生成する機能を具え、探索機能
が、キーの値に基づいてドメイン記述子から展開表のエ
ントリーのアドレスを求める機能を具えることができ
る。
【００１６】また、コンパイル機能が、キーの値を一定
間隔のグループに分け、各グループについて最小のキー
に対応する展開表のエントリーの識別子の値と展開表の
エントリーが変化するか否かを表すビットマップデータ
とのデータ対を保持するドメイン記述子を生成する機能
を具え、探索機能が、キーの値に基づいてドメイン記述
子のデータ対を解釈して展開表のエントリーのアドレス
を求める機能を具えることができる。
間隔のグループに分け、各グループについて最小のキー
に対応する展開表のエントリーの識別子の値と展開表の
エントリーが変化するか否かを表すビットマップデータ
とのデータ対を保持するドメイン記述子を生成する機能
を具え、探索機能が、キーの値に基づいてドメイン記述
子のデータ対を解釈して展開表のエントリーのアドレス
を求める機能を具えることができる。
【００１７】また、コンパイル機能が、展開表のエント
リーが少ない場合に、展開表のエントリーが変化するキ
ーの値からなるドメイン記述子を生成する機能を具え、
探索機能が、パケットのキーの値とドメイン記述子に保
持されているキーの値とを比較して展開表のエントリー
のアドレスを求める機能を具えることができる。
リーが少ない場合に、展開表のエントリーが変化するキ
ーの値からなるドメイン記述子を生成する機能を具え、
探索機能が、パケットのキーの値とドメイン記述子に保
持されているキーの値とを比較して展開表のエントリー
のアドレスを求める機能を具えることができる。
【００１８】また、コンパイル機能が、ルールセットか
らパケットが全ての条件を満たす可能性のないルールを
除外してできるルールセットが同一の場合は、同一ドメ
イン記述子にまとめた展開表を生成する機能を具え、探
索機能が、パケットのキー及び展開表を用いて次のキー
の位置及びドメイン記述子のアドレスを決定する機能を
具えることができる。
らパケットが全ての条件を満たす可能性のないルールを
除外してできるルールセットが同一の場合は、同一ドメ
イン記述子にまとめた展開表を生成する機能を具え、探
索機能が、パケットのキー及び展開表を用いて次のキー
の位置及びドメイン記述子のアドレスを決定する機能を
具えることができる。
【００１９】また、コンパイル機能が、展開表のエント
リー数が１の時に、そのエントリーの値を前段の展開表
のエントリーの値として保持させ、その展開表及びドメ
イン記述子を除外する機能を具え、探索機能が、パケッ
トのキーの値と展開表を用いて次のキーの位置及びドメ
イン記述子のアドレスを決定する機能を具えることがで
きる。
リー数が１の時に、そのエントリーの値を前段の展開表
のエントリーの値として保持させ、その展開表及びドメ
イン記述子を除外する機能を具え、探索機能が、パケッ
トのキーの値と展開表を用いて次のキーの位置及びドメ
イン記述子のアドレスを決定する機能を具えることがで
きる。
【００２０】このような本発明を適用することができる
具体的なシステムとしては、ルータ等の通信装置でのル
ーティングテーブルの検索、ファイアウォールでのフィ
ルタリング、ＱｏＳ制御、ＩＰスイッチングにおけるフ
ロー検出等がある。ルーティングテーブルの検索では、
キーは送信先アドレスフィールドであり、ルールは送信
先アドレス、ネットマスク及び転送先リンクの組であ
る。ルールではネットマスクにより送信先アドレスのプ
レフィクスを指定する。ルータ等の通信装置では、ルー
ルセットをルーティングテーブルとして保持し、受信パ
ケットの送信先アドレスフィールドのプレフィクスがル
ールの送信先アドレスのプレフィクスと等しいルールを
探し出し、複数のルールが該当する場合にはネットマス
クの最大のルールが選択され、そのルールの転送先リン
クに当該パケットを転送する。
具体的なシステムとしては、ルータ等の通信装置でのル
ーティングテーブルの検索、ファイアウォールでのフィ
ルタリング、ＱｏＳ制御、ＩＰスイッチングにおけるフ
ロー検出等がある。ルーティングテーブルの検索では、
キーは送信先アドレスフィールドであり、ルールは送信
先アドレス、ネットマスク及び転送先リンクの組であ
る。ルールではネットマスクにより送信先アドレスのプ
レフィクスを指定する。ルータ等の通信装置では、ルー
ルセットをルーティングテーブルとして保持し、受信パ
ケットの送信先アドレスフィールドのプレフィクスがル
ールの送信先アドレスのプレフィクスと等しいルールを
探し出し、複数のルールが該当する場合にはネットマス
クの最大のルールが選択され、そのルールの転送先リン
クに当該パケットを転送する。
【００２１】ファイアウォールでのフィルタリングで
は、送信先アドレス、送信元アドレス、送信先ポート番
号、送信元ポート番号、プロトコルフィールド、ＴＣＰ
フラグ等のフィールドをキーとして用いる。ルールで
は、各キーに対応する条件の指定及びパケットが全ての
条件を満たした場合に通過すべきか廃棄すべきかの指定
を行う。ファイアウォールでは、ルールセットをアクセ
ス制御リストとして保持し、受信パケットのキーが全て
の条件を満たすルールを探し出し、そのルールの指定に
従って当該パケットを通過させるか廃棄するかを決定す
る。
は、送信先アドレス、送信元アドレス、送信先ポート番
号、送信元ポート番号、プロトコルフィールド、ＴＣＰ
フラグ等のフィールドをキーとして用いる。ルールで
は、各キーに対応する条件の指定及びパケットが全ての
条件を満たした場合に通過すべきか廃棄すべきかの指定
を行う。ファイアウォールでは、ルールセットをアクセ
ス制御リストとして保持し、受信パケットのキーが全て
の条件を満たすルールを探し出し、そのルールの指定に
従って当該パケットを通過させるか廃棄するかを決定す
る。
【００２２】ＱｏＳ制御及びＩＰスイッチングにおける
フロー検出では、パケットの送信元アドレス及び送信先
アドレスをキーとして用いる。ルールでは、各キーの満
たすべき条件、全ての条件が満たされた場合に当該パケ
ットに割付けるべきネットワーク資源に関する情報を指
定する。受信パケットのキーが全ての条件を満たすルー
ルを探し出し、そのルールの指定に従って当該パケット
にネットワーク資源を割付ける。
フロー検出では、パケットの送信元アドレス及び送信先
アドレスをキーとして用いる。ルールでは、各キーの満
たすべき条件、全ての条件が満たされた場合に当該パケ
ットに割付けるべきネットワーク資源に関する情報を指
定する。受信パケットのキーが全ての条件を満たすルー
ルを探し出し、そのルールの指定に従って当該パケット
にネットワーク資源を割付ける。
【００２３】
【発明の実施の形態】〔実施例１〕次に、本発明のパケ
ット分類装置の実施例を説明する。この実施例において
は、コンパイル機能がルールセットを予めドメイン記述
子と展開表に変換し、探索機能が、パケットのキーの値
及びドメイン記述子の値によって定まるアドレスの展開
表のエントリーのデータを読出し、そのデータの値によ
り次のキーの位置及びドメイン記述子のアドレスを決定
し、受信パケットのキーの値に従ってコンパイル機能が
生成したデータを辿り、結果データを出力する。これに
より、各キーが満たすべき条件とそれら全てを満たすパ
ケットに対するアクションとの組を定めたルールセット
及びパケットが与えられた時に、ルールセットから全て
の条件を満たすルールを見付け出すことができる。
ット分類装置の実施例を説明する。この実施例において
は、コンパイル機能がルールセットを予めドメイン記述
子と展開表に変換し、探索機能が、パケットのキーの値
及びドメイン記述子の値によって定まるアドレスの展開
表のエントリーのデータを読出し、そのデータの値によ
り次のキーの位置及びドメイン記述子のアドレスを決定
し、受信パケットのキーの値に従ってコンパイル機能が
生成したデータを辿り、結果データを出力する。これに
より、各キーが満たすべき条件とそれら全てを満たすパ
ケットに対するアクションとの組を定めたルールセット
及びパケットが与えられた時に、ルールセットから全て
の条件を満たすルールを見付け出すことができる。
【００２４】 ルールセットＲ＝｛ｒ1,ｒ2 ｝として ｒ1 ：ｐ1,0 〔ｘ0 ≧２〕 ｐ1,1 〔ｘ1 ＝６〕 ａ1 ｒ2 ：ｐ2,0 〔３≦ｘ0 ≦５〕 ｐ2,1 〔ｘ1 ≧５〕 ａ2 を例として、ドメイン記述子及び展開表の作成法を説明
する。ここで、ｐj,i はｒj の第ｉ述語（ルールｒj の
第ｉ番目のキーに対応する述語）であり、ｘk は第ｋ番
目のキーの値、ａj はルールｒj のアクションである。
する。ここで、ｐj,i はｒj の第ｉ述語（ルールｒj の
第ｉ番目のキーに対応する述語）であり、ｘk は第ｋ番
目のキーの値、ａj はルールｒj のアクションである。
【００２５】ドメイン記述子及び展開表は、ルールセッ
トＲに対して或るキーの値ｘi に対する条件が真となる
ルール集合を返す関数sieve(R,i,ｘi ) の部分計算によ
って与えられる。例えば、関数sieve(R,0,ｘ0)＝sieve
(｛r1,r2 ｝,0, ｘ0)は
トＲに対して或るキーの値ｘi に対する条件が真となる
ルール集合を返す関数sieve(R,i,ｘi ) の部分計算によ
って与えられる。例えば、関数sieve(R,0,ｘ0)＝sieve
(｛r1,r2 ｝,0, ｘ0)は
【数１】 のように表される。この式は、各行の()内の条件が成立
する場合に結果としてその行の集合が返されることを意
味する。この関数sieve(R,0,ｘ0)の部分計算とは、ｘ0
の値が分かる前に上記計算を可能な限り進めておき、ｘ
0 の値を用いなければできない残りの計算を簡単にして
おくことを意味する。以下では、部分計算の結果を sie
veR,0(ｘ0)と表すこととする。
する場合に結果としてその行の集合が返されることを意
味する。この関数sieve(R,0,ｘ0)の部分計算とは、ｘ0
の値が分かる前に上記計算を可能な限り進めておき、ｘ
0 の値を用いなければできない残りの計算を簡単にして
おくことを意味する。以下では、部分計算の結果を sie
veR,0(ｘ0)と表すこととする。
【００２６】以下では、キーの長さが３ビットの場合に
ついて関数sieve(R,0,ｘ0)の部分計算を例示する。この
場合、ｘ0 のドメイン（定義域）Ｄ0 はＤ0 ＝｛0,...,
7｝である。図１はドメイン記述子の構成例を示す図で
ある。Ｄ0 は、ｐ1,0 の取り得る値（Ｔ又はＦ）に従っ
て、図に示すように、２つのインターバルＩ0 1,0及びＩ
1 1,0に分割することができる。同様にｐ2,0 に従うと、
図に示すように、３つのインターバルＩ0 2,0、Ｉ1 2,0及
びＩ2 2,0に分割することができる。図において、ｘ0 の
ドメインを全てのインターバルの境界によって分割する
と、４つのサブドメインＤ0 0＝｛0, 1｝、Ｄ1 0＝
｛２｝、Ｄ2 0＝｛3,4,5 ｝、Ｄ3 0＝｛6, 7｝ができる。
各サブドメインにおけるｐ1,0 及びｐ2,0 の値を調べる
と、ｘ0 の値がそのサブドメイン内にある場合に、ｘ1
の値にかかわらずパケットがマッチしないことが明らか
なルールが分かる。例えば、Ｄ0 0ではｐ1,0 及びｐ2,0
がいずれもＦであるので、ｘ1 の値にかかわらず、ルー
ルｒ1 及びｒ2 はいずれもマッチしない。図１のサブド
メインルールセットは、このようなルールを除外したル
ールの集合である。
ついて関数sieve(R,0,ｘ0)の部分計算を例示する。この
場合、ｘ0 のドメイン（定義域）Ｄ0 はＤ0 ＝｛0,...,
7｝である。図１はドメイン記述子の構成例を示す図で
ある。Ｄ0 は、ｐ1,0 の取り得る値（Ｔ又はＦ）に従っ
て、図に示すように、２つのインターバルＩ0 1,0及びＩ
1 1,0に分割することができる。同様にｐ2,0 に従うと、
図に示すように、３つのインターバルＩ0 2,0、Ｉ1 2,0及
びＩ2 2,0に分割することができる。図において、ｘ0 の
ドメインを全てのインターバルの境界によって分割する
と、４つのサブドメインＤ0 0＝｛0, 1｝、Ｄ1 0＝
｛２｝、Ｄ2 0＝｛3,4,5 ｝、Ｄ3 0＝｛6, 7｝ができる。
各サブドメインにおけるｐ1,0 及びｐ2,0 の値を調べる
と、ｘ0 の値がそのサブドメイン内にある場合に、ｘ1
の値にかかわらずパケットがマッチしないことが明らか
なルールが分かる。例えば、Ｄ0 0ではｐ1,0 及びｐ2,0
がいずれもＦであるので、ｘ1 の値にかかわらず、ルー
ルｒ1 及びｒ2 はいずれもマッチしない。図１のサブド
メインルールセットは、このようなルールを除外したル
ールの集合である。
【００２７】また、ドメイン記述子は、キーの値からサ
ブドメイン識別子を与えるデータであり、図１に示すよ
うに、サブドメイン識別子の系列を与える。即ち、図の
ベクトル〔0,0,1,2,2,2,3 〕がドメイン記述子となり、
例えば第３要素（このベクトルは第０要素から始まるの
で第４番目の要素）の値２がキーの値３に対するサブド
メイン識別子である。
ブドメイン識別子を与えるデータであり、図１に示すよ
うに、サブドメイン識別子の系列を与える。即ち、図の
ベクトル〔0,0,1,2,2,2,3 〕がドメイン記述子となり、
例えば第３要素（このベクトルは第０要素から始まるの
で第４番目の要素）の値２がキーの値３に対するサブド
メイン識別子である。
【００２８】 図１から部分計算Ｒ0 ＝ sieve｛r1, r2｝,0(x0) は
【数２】 のようになる。
【００２９】この式のＲ0 は、キーの取り得る値に対し
て、ルールセットＲからパケットが全ての条件を満たす
可能性のないルールを除外してできるルールの集合を与
えている。展開表は、各集合に対応するドメイン記述子
のアドレスをエントリーとする表であるので、各集合に
ついて関数sieve(R0,1,x1)の部分計算を上記と同様に行
ってできるドメイン記述子のアドレスを並べた表を作成
すると展開表が得られる。これにより、コンパイル処理
では、図２に示すデータを作成する。このデータは sie
ve展開木と呼ばれる。図２の各ブロックにおいて、最初
の行はドメイン記述子であり、２行目以降は展開表であ
る。
て、ルールセットＲからパケットが全ての条件を満たす
可能性のないルールを除外してできるルールの集合を与
えている。展開表は、各集合に対応するドメイン記述子
のアドレスをエントリーとする表であるので、各集合に
ついて関数sieve(R0,1,x1)の部分計算を上記と同様に行
ってできるドメイン記述子のアドレスを並べた表を作成
すると展開表が得られる。これにより、コンパイル処理
では、図２に示すデータを作成する。このデータは sie
ve展開木と呼ばれる。図２の各ブロックにおいて、最初
の行はドメイン記述子であり、２行目以降は展開表であ
る。
【００３０】探索処理では、先ず受信パケットのキー０
の値に従って部分計算 sieve｛r1,r2｝,0(x0)のドメイ
ン記述子を読出す。図２の sieve｛r1, r2｝,0(x0)のブ
ロックにおいて、例えば、キー０の値が２の時、ドメイ
ン記述子の第２番目（最も右側が第０番目なので右から
３番目）の値である１をサブドメイン識別子として読出
す。次に、展開表の第１番目（最も上が０番目なので上
から２番目）の値として sieve｛r1｝,1(x1)へのポイン
ターを読出す。更に、受信パケットのキー１の値に従っ
て sieve｛r1｝,1(x1)のドメイン識別子を読出し、その
値に従って展開表を読出す。今、キー１の値が６である
とすると、サブドメイン識別子は１なので、展開表の第
１番目を読出しｒ1 へのポインターを得る。即ち、受信
パケットのキー０及び１の値がそれぞれ２及び６の場
合、このパケットはルールｒ1 にマッチするパケットで
あることを通知する。このようにキーの数（上の例の場
合は２）に相当する回数だけドメイン記述子及び展開表
のエントリーを読出すことにより、照合に成功するルー
ルを得ることができる。
の値に従って部分計算 sieve｛r1,r2｝,0(x0)のドメイ
ン記述子を読出す。図２の sieve｛r1, r2｝,0(x0)のブ
ロックにおいて、例えば、キー０の値が２の時、ドメイ
ン記述子の第２番目（最も右側が第０番目なので右から
３番目）の値である１をサブドメイン識別子として読出
す。次に、展開表の第１番目（最も上が０番目なので上
から２番目）の値として sieve｛r1｝,1(x1)へのポイン
ターを読出す。更に、受信パケットのキー１の値に従っ
て sieve｛r1｝,1(x1)のドメイン識別子を読出し、その
値に従って展開表を読出す。今、キー１の値が６である
とすると、サブドメイン識別子は１なので、展開表の第
１番目を読出しｒ1 へのポインターを得る。即ち、受信
パケットのキー０及び１の値がそれぞれ２及び６の場
合、このパケットはルールｒ1 にマッチするパケットで
あることを通知する。このようにキーの数（上の例の場
合は２）に相当する回数だけドメイン記述子及び展開表
のエントリーを読出すことにより、照合に成功するルー
ルを得ることができる。
【００３１】〔実施例２〕他のコンパイル処理において
は、キーを８ビットの固定長の連続するビット列とす
る。この場合、パケットフィールド長が８ビットでない
場合には各フィールドに対する条件をキーの条件に変換
してできるルールを用いる。このとき、必要である場合
には、フィールドを結合し又は分割してキーの述語に変
換する。フィールドを複数のキーに分割する時には、１
つのルールが複数になる場合もある。以下にフラグビッ
ト、多バイトフィールド及び多倍長プレフィクスの各フ
ィールドについての結合及び分割の例を示す。
は、キーを８ビットの固定長の連続するビット列とす
る。この場合、パケットフィールド長が８ビットでない
場合には各フィールドに対する条件をキーの条件に変換
してできるルールを用いる。このとき、必要である場合
には、フィールドを結合し又は分割してキーの述語に変
換する。フィールドを複数のキーに分割する時には、１
つのルールが複数になる場合もある。以下にフラグビッ
ト、多バイトフィールド及び多倍長プレフィクスの各フ
ィールドについての結合及び分割の例を示す。
【００３２】フラグビットの場合、同一バイト長の複数
のビットをまとめて１つのキーにする。例えば、 ｒ1 ：ｐ1,1 〔ｘ1 ＝１〕 ｐ1,2 〔ｘ2 ＝０〕 ａ1 を ｒ1'：ｐ1',1〔ｘ1'＝(10)2 〕 ａ1 とする。ここで、ｘ1'のビット０はｘ2 、ビット１はｘ
1 である。
のビットをまとめて１つのキーにする。例えば、 ｒ1 ：ｐ1,1 〔ｘ1 ＝１〕 ｐ1,2 〔ｘ2 ＝０〕 ａ1 を ｒ1'：ｐ1',1〔ｘ1'＝(10)2 〕 ａ1 とする。ここで、ｘ1'のビット０はｘ2 、ビット１はｘ
1 である。
【００３３】多バイトフィールドの場合、複数のキーに
分割する。例えば、 ｒ1 ：ｐ1,1 〔ｘ1 ＞300 〕 ａ1 を ｒ1'：ｐ1',1〔ｘ1'＝１〕 ｐ1',2〔ｘ1"＞44〕 ａ1 ｒ1"：ｐ1",1〔ｘ1'＞１〕 ｐ1",2〔ｘ1"≧０〕 ａ1 とする。ここで、ｘ1 は２バイトデータであって、ｘ1'
はｘ1 の上位１バイト、ｘ1"は下位１バイトである。
分割する。例えば、 ｒ1 ：ｐ1,1 〔ｘ1 ＞300 〕 ａ1 を ｒ1'：ｐ1',1〔ｘ1'＝１〕 ｐ1',2〔ｘ1"＞44〕 ａ1 ｒ1"：ｐ1",1〔ｘ1'＞１〕 ｐ1",2〔ｘ1"≧０〕 ａ1 とする。ここで、ｘ1 は２バイトデータであって、ｘ1'
はｘ1 の上位１バイト、ｘ1"は下位１バイトである。
【００３４】多倍長プレフィクスの場合、複数のキーに
分割し、不等式で表す。例えば、 ｒ1 ：ｐ1,1 〔ｘ1 ＝(112＊)16 〕 ａ1 を ｒ1'：ｐ1',1〔ｘ1'＝(11)16〕 ｐ1',2〔(20)16≦ｘ1"≦(2f)16〕 ａ1 とする。ここで、＊はワイルドカードであり、ｘ1 は２
バイトデータであって、ｘ1'はｘ1 の上位１バイト、ｘ
1"は下位１バイトである。
分割し、不等式で表す。例えば、 ｒ1 ：ｐ1,1 〔ｘ1 ＝(112＊)16 〕 ａ1 を ｒ1'：ｐ1',1〔ｘ1'＝(11)16〕 ｐ1',2〔(20)16≦ｘ1"≦(2f)16〕 ａ1 とする。ここで、＊はワイルドカードであり、ｘ1 は２
バイトデータであって、ｘ1'はｘ1 の上位１バイト、ｘ
1"は下位１バイトである。
【００３５】〔実施例３〕更に他のコンパイル処理にお
いては、図３に示す構造のデータを作成する。図では、
キーの値を８ビット、メモリーの１語を32ビットとして
いる。探索処理では、図に示すように、キーの上位６ビ
ットの値によってドメイン記述子のメモリー語を指定
し、キーの下位２ビットの値によってその語内の位置を
指定する。このように、キーの値によって指定されて得
られる８ビットのデータがサブドメインの識別子にな
り、展開表のエントリーの位置を指定する。展開表のエ
ントリーは、次のドメイン記述子のアドレス又はルール
のアクションの情報の格納アドレスを保持する。
いては、図３に示す構造のデータを作成する。図では、
キーの値を８ビット、メモリーの１語を32ビットとして
いる。探索処理では、図に示すように、キーの上位６ビ
ットの値によってドメイン記述子のメモリー語を指定
し、キーの下位２ビットの値によってその語内の位置を
指定する。このように、キーの値によって指定されて得
られる８ビットのデータがサブドメインの識別子にな
り、展開表のエントリーの位置を指定する。展開表のエ
ントリーは、次のドメイン記述子のアドレス又はルール
のアクションの情報の格納アドレスを保持する。
【００３６】〔実施例４〕更に他のコンパイル処理にお
いては、図４に示す構造のデータを作成する。このデー
タは、ドメイン記述子として、図１の例のように、サブ
ドメイン識別子の値のベクトル〔0,0,1,2,2,2,3,3 〕を
保持していなくても、インターバルの境界を表す。即
ち、サブドメイン識別子が変化した場合は１でそうでは
ない場合は０のビット列〔0,0,1,1,0,0,1,0 〕を保持し
ておれば、サブドメイン識別子を求めることができるこ
とに基づいている。即ち、上記ビット列において、ビッ
ト０から各ビットまでの１の数からそのビットに対応す
るサブドメイン識別子が得られる。
いては、図４に示す構造のデータを作成する。このデー
タは、ドメイン記述子として、図１の例のように、サブ
ドメイン識別子の値のベクトル〔0,0,1,2,2,2,3,3 〕を
保持していなくても、インターバルの境界を表す。即
ち、サブドメイン識別子が変化した場合は１でそうでは
ない場合は０のビット列〔0,0,1,1,0,0,1,0 〕を保持し
ておれば、サブドメイン識別子を求めることができるこ
とに基づいている。即ち、上記ビット列において、ビッ
ト０から各ビットまでの１の数からそのビットに対応す
るサブドメイン識別子が得られる。
【００３７】図４は、32ビット語のメモリーにおいて、
１回の参照でサブドメイン識別子が得られるように構成
したデータ構造を示す。このドメイン記述子では、上記
ビット列を８ビットずつ分割してできるビットマップと
その先頭ビットのサブドメイン識別子の値を表すオフセ
ットとの対を用いている。この場合には、キーの上位４
ビットでドメイン記述子内の１語を選択し、ビット４が
１のときは上半語、０のときは下半語のオフセット及び
ビットマップを選択する。キーの下位３ビットでビット
マップのビット位置を選択する。ビットマップのビット
０から選択ビットまでにある１の数にオフセットを加え
た値がサブドメイン識別子になる。このデータ構造を用
いる場合には、ドメイン記述子のメモリーサイズは64バ
イトであり、図３の場合に比べて１／４になる。
１回の参照でサブドメイン識別子が得られるように構成
したデータ構造を示す。このドメイン記述子では、上記
ビット列を８ビットずつ分割してできるビットマップと
その先頭ビットのサブドメイン識別子の値を表すオフセ
ットとの対を用いている。この場合には、キーの上位４
ビットでドメイン記述子内の１語を選択し、ビット４が
１のときは上半語、０のときは下半語のオフセット及び
ビットマップを選択する。キーの下位３ビットでビット
マップのビット位置を選択する。ビットマップのビット
０から選択ビットまでにある１の数にオフセットを加え
た値がサブドメイン識別子になる。このデータ構造を用
いる場合には、ドメイン記述子のメモリーサイズは64バ
イトであり、図３の場合に比べて１／４になる。
【００３８】〔実施例５〕更に他のコンパイル処理にお
いては、図５に示す構造のデータを作成する。このデー
タは、サブドメイン数が４以下の場合に適用可能なイン
デックス形式のドメイン記述子のデータ構造である。こ
の場合には、サブドメインの境界を与えるキーの値を保
持する。探索処理では、キーの値を各境界の値と比較し
て、どの境界の間にあるかを求めることにより、サブド
メイン識別子が得られる。
いては、図５に示す構造のデータを作成する。このデー
タは、サブドメイン数が４以下の場合に適用可能なイン
デックス形式のドメイン記述子のデータ構造である。こ
の場合には、サブドメインの境界を与えるキーの値を保
持する。探索処理では、キーの値を各境界の値と比較し
て、どの境界の間にあるかを求めることにより、サブド
メイン識別子が得られる。
【００３９】〔実施例６〕更に他のコンパイル処理にお
いては、サブドメインの数に従って図４又は図５に示す
構造のデータを作成する。更に、展開表のエントリー内
に、次のドメイン識別子のデータが図４の形式か図５の
形式かを示すフラグデータを保持させる。探索処理で
は、このフラグデータに従ってドメイン記述子のデータ
形式を判別し、前記実施例４又は実施例５の探索処理を
切替える。
いては、サブドメインの数に従って図４又は図５に示す
構造のデータを作成する。更に、展開表のエントリー内
に、次のドメイン識別子のデータが図４の形式か図５の
形式かを示すフラグデータを保持させる。探索処理で
は、このフラグデータに従ってドメイン記述子のデータ
形式を判別し、前記実施例４又は実施例５の探索処理を
切替える。
【００４０】〔実施例７〕更に他のコンパイル処理にお
いては、ドメイン識別子及び展開表（両者を合わせてsi
eve と呼ぶ）を作成する際に、図６に示すように、次段
のsieve を共有させたデータを作成する。即ち、図１の
例でも存在するように、サブドメインが異なっても次段
のsieve の入力となるルールセットが等しい場合があ
る。コンパイル処理において、このようなサブドメイン
を検出し、展開表のエントリーの内容を同一にする。
いては、ドメイン識別子及び展開表（両者を合わせてsi
eve と呼ぶ）を作成する際に、図６に示すように、次段
のsieve を共有させたデータを作成する。即ち、図１の
例でも存在するように、サブドメインが異なっても次段
のsieve の入力となるルールセットが等しい場合があ
る。コンパイル処理において、このようなサブドメイン
を検出し、展開表のエントリーの内容を同一にする。
【００４１】〔実施例８〕更に他のコンパイル処理にお
いては、図７に示すように、展開表のエントリー数が１
であるようなsieve を除外して、そのエントリーの値を
前段の展開表のエントリーの値として保持させるデータ
を作成する。
いては、図７に示すように、展開表のエントリー数が１
であるようなsieve を除外して、そのエントリーの値を
前段の展開表のエントリーの値として保持させるデータ
を作成する。
【００４２】〔実施例９〕更に他のコンパイル処理にお
いては、図８に示す命令語をエントリーとする展開表を
作成する。探索処理では、プロセッサを、図９のように
一次元アレイ状に並べて動作させる。各プロセッサは、
図に示すように、キーの値と命令語を入力とし、次段の
プロセッサに対する命令語を出力とする。この命令語は
展開表のエントリーである。
いては、図８に示す命令語をエントリーとする展開表を
作成する。探索処理では、プロセッサを、図９のように
一次元アレイ状に並べて動作させる。各プロセッサは、
図に示すように、キーの値と命令語を入力とし、次段の
プロセッサに対する命令語を出力とする。この命令語は
展開表のエントリーである。
【００４３】これらのプロセッサは以下のような手続に
従って動作する。 (1) ドメイン記述子の型、ドメイン記述子の格納アドレ
ス、キーの位置の指定、プロセッサの指定及び探索の終
了等を示すデータからなる命令語を外部から受信する。 (2) 命令語からドメイン記述子の型、ドメイン記述子の
格納アドレス、及びキーの位置の指定のフィールドを取
出す。 (3) キーの位置で指定されたキーの値を受取り、これを
ｘk とする。 (4) ドメイン記述子の型に従ってｘk に対応するドメイ
ン記述子の値（サブドメイン識別子の値）を読出す。こ
の時、ドメイン記述子の先頭アドレスは、命令語のアド
レスのフィールドによって与えられる。 (5) サブドメイン識別子の値に従って展開表のエントリ
ー（次の命令語）を読出す。 (6) 次の命令語のターミネータ又はプロセッサの位置が
１の時、次の命令語を出力して命令語の実行を終了し、
(1) に戻る。そうではない時、(2) に戻る。
従って動作する。 (1) ドメイン記述子の型、ドメイン記述子の格納アドレ
ス、キーの位置の指定、プロセッサの指定及び探索の終
了等を示すデータからなる命令語を外部から受信する。 (2) 命令語からドメイン記述子の型、ドメイン記述子の
格納アドレス、及びキーの位置の指定のフィールドを取
出す。 (3) キーの位置で指定されたキーの値を受取り、これを
ｘk とする。 (4) ドメイン記述子の型に従ってｘk に対応するドメイ
ン記述子の値（サブドメイン識別子の値）を読出す。こ
の時、ドメイン記述子の先頭アドレスは、命令語のアド
レスのフィールドによって与えられる。 (5) サブドメイン識別子の値に従って展開表のエントリ
ー（次の命令語）を読出す。 (6) 次の命令語のターミネータ又はプロセッサの位置が
１の時、次の命令語を出力して命令語の実行を終了し、
(1) に戻る。そうではない時、(2) に戻る。
【００４４】これらのプロセッサは、ローカルメモリー
としてドメイン記述子及び展開表を格納するチャンクメ
モリーを持つ。ドメイン記述子及び展開表のメモリーを
分割してドメイン記述子及び展開表のメモリーアクセス
をパイプライン化すると、プロセッサは１回のメモリー
アクセス毎に出力できるようになる。
としてドメイン記述子及び展開表を格納するチャンクメ
モリーを持つ。ドメイン記述子及び展開表のメモリーを
分割してドメイン記述子及び展開表のメモリーアクセス
をパイプライン化すると、プロセッサは１回のメモリー
アクセス毎に出力できるようになる。
【００４５】プロセッサをキーの数だけ並べる場合は、
各プロセッサにそれぞれ１つのキーに対応するsieve の
実行を割付ける。コンパイラがプロセッサ位置の値を常
に１にセットしておくと、プロセッサは、上記手順(6)
で必ず手順(1) に戻るループを構成する。このとき、先
頭のプロセッサに sieve展開木の根のsieve のアドレス
を持つ命令語を入力すると、各プロセッサはそれぞれ１
つのキーを用いてsieve を実行し、最終段のプロセッサ
がルール識別子（パケットが実行可能の場合）又は０
（パケットが実行不可能の場合）をアドレスフィールド
に持つ命令語を出力する。図９に示すように、連続して
到着するパケットのキーの値を次々にプロセッサに与
え、先頭のプロセッサにパケット到着毎に命令語を与え
ると、システム全体では１sieve の実行時間の間隔でシ
ストリック動作をする。更に、プロセッサを２段のパイ
プラインで構成すると、１メモリーアクセスの時間間隔
でシストリック動作をさせることができる。
各プロセッサにそれぞれ１つのキーに対応するsieve の
実行を割付ける。コンパイラがプロセッサ位置の値を常
に１にセットしておくと、プロセッサは、上記手順(6)
で必ず手順(1) に戻るループを構成する。このとき、先
頭のプロセッサに sieve展開木の根のsieve のアドレス
を持つ命令語を入力すると、各プロセッサはそれぞれ１
つのキーを用いてsieve を実行し、最終段のプロセッサ
がルール識別子（パケットが実行可能の場合）又は０
（パケットが実行不可能の場合）をアドレスフィールド
に持つ命令語を出力する。図９に示すように、連続して
到着するパケットのキーの値を次々にプロセッサに与
え、先頭のプロセッサにパケット到着毎に命令語を与え
ると、システム全体では１sieve の実行時間の間隔でシ
ストリック動作をする。更に、プロセッサを２段のパイ
プラインで構成すると、１メモリーアクセスの時間間隔
でシストリック動作をさせることができる。
【００４６】プロセッサの命令語は、図８に示すよう
に、キーの位置及びプロセッサの位置を指定するフィー
ルドを具えているので、処理すべきキーの位置が異なる
複数のsieve を同一プロセッサに割付けることが可能で
ある。プロセッサの数又は各プロセッサのメモリー容量
が充分ではない場合には、次のような割付け法を採るこ
とができる。即ち、プロセッサの数をｐ、 sieve展開木
の根から葉に至るバス上のsieve の数をｓとし、ｐ＜ｓ
とすると、この場合には、根から順にｓ／ｐより大きい
最小の整数値に等しい個数のsieve を同じプロセッサに
割付けて行けばプロセッサ当たりの割付けsieve 数が平
均化される。
に、キーの位置及びプロセッサの位置を指定するフィー
ルドを具えているので、処理すべきキーの位置が異なる
複数のsieve を同一プロセッサに割付けることが可能で
ある。プロセッサの数又は各プロセッサのメモリー容量
が充分ではない場合には、次のような割付け法を採るこ
とができる。即ち、プロセッサの数をｐ、 sieve展開木
の根から葉に至るバス上のsieve の数をｓとし、ｐ＜ｓ
とすると、この場合には、根から順にｓ／ｐより大きい
最小の整数値に等しい個数のsieve を同じプロセッサに
割付けて行けばプロセッサ当たりの割付けsieve 数が平
均化される。
【００４７】メモリーが各プロセッサに分散されている
ため、システム全体として sieve展開木の全チャンクデ
ータを保持できるメモリー容量がある場合でも、上記の
ような割付けをしようとする時に特定のプロセッサにお
いてメモリー不足のため割付けられないsieve が発生す
ることがある。このような場合には、実行時間を犠牲に
してそのsieve を他のプロセッサに割付けることができ
る。
ため、システム全体として sieve展開木の全チャンクデ
ータを保持できるメモリー容量がある場合でも、上記の
ような割付けをしようとする時に特定のプロセッサにお
いてメモリー不足のため割付けられないsieve が発生す
ることがある。このような場合には、実行時間を犠牲に
してそのsieve を他のプロセッサに割付けることができ
る。
【００４８】
【発明の効果】上記のとおり、本発明によれば、以下の
効果を得ることができる。即ち、探索処理においてＡＣ
Ｌを上から順番に調べる代わりにキーフィールドに対応
するドメイン識別子と展開表との組(sieve) を順番に調
べるので、調べるべきsieve の数はルールの数に依存し
ないため、ルールの数が多くなっても探索処理の時間が
長くなることはない。また、最長プレフィクス照合に従
う条件をルールに用いる場合でも、sieve を順番に調べ
るだけでよいため、バックトラックが生じたり又は余分
なポインターが生じたりして探索時間が長くなることは
ない。領域照合の場合でも、sieve を順番に調べるだけ
でよいため、そのままで用いることができる。従って、
本発明によれば、少ないハードウェア量で、ルールの数
が多い場合にも適用できるパケット分類装置を実現する
ことができる。
効果を得ることができる。即ち、探索処理においてＡＣ
Ｌを上から順番に調べる代わりにキーフィールドに対応
するドメイン識別子と展開表との組(sieve) を順番に調
べるので、調べるべきsieve の数はルールの数に依存し
ないため、ルールの数が多くなっても探索処理の時間が
長くなることはない。また、最長プレフィクス照合に従
う条件をルールに用いる場合でも、sieve を順番に調べ
るだけでよいため、バックトラックが生じたり又は余分
なポインターが生じたりして探索時間が長くなることは
ない。領域照合の場合でも、sieve を順番に調べるだけ
でよいため、そのままで用いることができる。従って、
本発明によれば、少ないハードウェア量で、ルールの数
が多い場合にも適用できるパケット分類装置を実現する
ことができる。
【図１】 実施例１におけるドメイン記述子の構成例の
細部を示す図である。
細部を示す図である。
【図２】 実施例１におけるドメイン記述子と展開表の
構成例を示す図である。
構成例を示す図である。
【図３】 実施例３におけるドメイン記述子と展開表の
構成例を示す図である。
構成例を示す図である。
【図４】 実施例４におけるドメイン記述子と展開表の
構成例を示す図である。
構成例を示す図である。
【図５】 実施例５におけるドメイン記述子の構成例を
示す図である。
示す図である。
【図６】 実施例７におけるドメイン記述子と展開表の
組の系列の構成例を示す図である。
組の系列の構成例を示す図である。
【図７】 実施例８におけるドメイン記述子と展開表の
組の系列の構成例を示す図である。
組の系列の構成例を示す図である。
【図８】 実施例９における命令語の構成例を示す図で
ある。
ある。
【図９】 実施例９におけるプロセッサアレイの構成例
を示す図である。
を示す図である。
【図１０】 従来のアクセス制御リストの例を示す図で
ある。
ある。
【図１１】 従来のパトリシア木の例を示す図である。
ｒ ルール Ｒ ルールセット ｐ ルールの述語 ｘ キーの値 Ｉ インターバル Ｄ ドメイン ＤＤ ドメイン記述子 ＵＴ 展開表
Claims (9)
- 【請求項１】 キーフィールドが満たすべき条件を定め
たルールの集合であるルールセットからパケットが全て
の条件を満たすルールを見つけ出すためのパケット分類
装置において、予めルールセットをドメイン記述子及び
展開表に変換するコンパイル機能、並びに、パケットの
キーの値及びドメイン記述子の値によって定まるアドレ
スに位置する展開表のエントリーの値によって次のキー
の位置及びドメイン記述子のアドレスを決定する探索機
能を具え、該探索機能が受信パケットのキーの値に従っ
て前記コンパイル機能が生成したデータを辿ることを特
徴とするパケット分類装置。 - 【請求項２】 コンパイル機能が、キーの長さが長い場
合に分割し、短い場合に連結することにより、キーを固
定長に変換する機能を具えることを特徴とする請求項１
に記載のパケット分類装置。 - 【請求項３】 コンパイル機能が、キーの全ての値につ
いて、対応する展開表のエントリーの識別子を保持する
ドメイン記述子を生成する機能を具え、探索機能が、キ
ーの値に基づいてドメイン記述子から展開表のエントリ
ーのアドレスを求める機能を具えることを特徴とする請
求項１又は２に記載のパケット分類装置。 - 【請求項４】 コンパイル機能が、キーの値を一定間隔
のグループに分け、各グループについて最小のキーに対
応する展開表のエントリーの識別子の値と展開表のエン
トリーが変化するか否かを表すビットマップデータとの
データ対を保持するドメイン記述子を生成する機能を具
え、探索機能が、キーの値に基づいてドメイン記述子の
データ対を解釈して展開表のエントリーのアドレスを求
める機能を具えることを特徴とする請求項１又は２に記
載のパケット分類装置。 - 【請求項５】 コンパイル機能が、展開表のエントリー
が少ない場合に、展開表のエントリーが変化するキーの
値からなるドメイン記述子を生成する機能を具え、探索
機能が、パケットのキーの値とドメイン記述子に保持さ
れているキーの値とを比較して展開表のエントリーのア
ドレスを求める機能を具えることを特徴とする請求項１
又は２に記載のパケット分類装置。 - 【請求項６】 コンパイル機能が請求項４に記載のコン
パイル機能及び請求項５に記載のコンパイル機能を具
え、サブドメインの数に従っていずれかに機能し、探索
機能が前記いずれかに機能に対応して展開表のエントリ
ーのアドレスを求める機能を具えることを特徴とする請
求項１又は２に記載のパケット分類装置。 - 【請求項７】 コンパイル機能が、ルールセットからパ
ケットが全ての条件を満たす可能性のないルールを除外
してできるルールセットが同一の場合は、同一ドメイン
記述子にまとめた展開表を生成する機能を具え、探索機
能が、パケットのキー及び展開表を用いて次のキーの位
置及びドメイン記述子のアドレスを決定する機能を具え
ることを特徴とする請求項１乃至６のいずれか１項に記
載のパケット分類装置。 - 【請求項８】 コンパイル機能が、展開表のエントリー
数が１の時に、そのエントリーの値を前段の展開表のエ
ントリーの値として保持させ、その展開表及びドメイン
記述子を除外する機能を具え、探索機能が、パケットの
キーの値と展開表を用いて次のキーの位置及びドメイン
記述子のアドレスを決定する機能を具えることを特徴と
する請求項１乃至７のいずれか１項に記載のパケット分
類装置。 - 【請求項９】 探索機能が、ドメイン記述子の型、ドメ
イン記述子の格納アドレス、キーの位置の指定、プロセ
ッサの指定及び探索の終了等を示すデータからなる命令
語を解釈実行する機能を具えることを特徴とする請求項
１乃至７のいずれか１項に記載のパケット分類装置。
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP07132599A JP3443356B2 (ja) | 1999-03-17 | 1999-03-17 | パケット分類装置 |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP07132599A JP3443356B2 (ja) | 1999-03-17 | 1999-03-17 | パケット分類装置 |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| JP2000270021A true JP2000270021A (ja) | 2000-09-29 |
| JP3443356B2 JP3443356B2 (ja) | 2003-09-02 |
Family
ID=13457304
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP07132599A Expired - Fee Related JP3443356B2 (ja) | 1999-03-17 | 1999-03-17 | パケット分類装置 |
Country Status (1)
| Country | Link |
|---|---|
| JP (1) | JP3443356B2 (ja) |
Cited By (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN100337441C (zh) * | 2003-04-30 | 2007-09-12 | 华为技术有限公司 | 转发数据包的查表方法 |
-
1999
- 1999-03-17 JP JP07132599A patent/JP3443356B2/ja not_active Expired - Fee Related
Cited By (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN100337441C (zh) * | 2003-04-30 | 2007-09-12 | 华为技术有限公司 | 转发数据包的查表方法 |
Also Published As
| Publication number | Publication date |
|---|---|
| JP3443356B2 (ja) | 2003-09-02 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| US10496680B2 (en) | High-performance bloom filter array | |
| US9984144B2 (en) | Efficient lookup of TCAM-like rules in RAM | |
| KR100477391B1 (ko) | 네트워크 프로세서용 완전 정합（ｆｍ） 검색 알고리즘 구현 | |
| Kumar et al. | Advanced algorithms for fast and scalable deep packet inspection | |
| JP4452183B2 (ja) | プログラマブル状態マシンのデータ構造を作成して入力単語連鎖を構文解析する方法、プログラマブル状態マシンのデータ構造を使用して入力単語連鎖に対応する結果として得られた値を検索する方法、ワイヤスピードのディープ・パケット処理を行う方法、ディープ・パケット処理のための装置、チップ埋め込み装置、およびプログラミング・コード命令を含むコンピュータ・プログラム（ディープ・パケット処理のための方法および装置） | |
| EP1623347B1 (en) | Comparison tree data structures and lookup operations | |
| JP3485262B2 (ja) | データ・パケットを分類する方法および手段 | |
| US6775737B1 (en) | Method and apparatus for allocating and using range identifiers as input values to content-addressable memories | |
| US7984038B2 (en) | Longest prefix match (LPM) algorithm implementation for a network processor | |
| US6792423B1 (en) | Hybrid longest prefix match and fixed match searches | |
| US20050083937A1 (en) | IP address lookup method using pipeline binary tree, hardware architecture, and recording medium | |
| KR100933916B1 (ko) | 분류자 확인을 위한 장치 및 방법 | |
| US20040230583A1 (en) | Comparison tree data structures of particular use in performing lookup operations | |
| US20080046423A1 (en) | Method and system for multi-character multi-pattern pattern matching | |
| US6484170B2 (en) | Generating searchable data entries and applications therefore | |
| Meiners et al. | Hardware based packet classification for high speed internet routers | |
| JP3443356B2 (ja) | パケット分類装置 | |
| KR100662254B1 (ko) | 라우팅 시스템에서의 패킷 분류 장치 및 이를 위한 룰 구축 방법 | |
| US11929837B2 (en) | Rule compilation schemes for fast packet classification | |
| US20070255676A1 (en) | Methods and apparatus for performing tree-based processing using multi-level memory storage | |
| CN107819887A (zh) | 网段冲突的检测方法及装置 | |
| JP4726310B2 (ja) | 情報検索装置、情報検索用マルチプロセッサおよびルータ | |
| JP4151217B2 (ja) | データグラム転送装置 | |
| US20190207958A1 (en) | Multi-pattern policy detection system and method | |
| CN119363659B (zh) | 前缀树的构建方法、路由条目查找方法、装置及电子设备 |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20090620 Year of fee payment: 6 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20090620 Year of fee payment: 6 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20100620 Year of fee payment: 7 |
|
| LAPS | Cancellation because of no payment of annual fees |