(57)【要約】【課題】ＰＣＡＰ形式フィルタをパトリシア・ツリーに挿入可能な形式に変換する。【解決手段】プロセッサは、ハードウェア支援型パトリシア・ツリーを用いて回線速度のフィルタ処理を実行する。ＰＣＡＰ形式フィルタは、パトリシア・ツリーに挿入可能な形態に変換される。ＰＣＡＰフィルタ式が構文解析され、積和標準形（ＤＮＦ）に変換される。フィルタの各ＤＮＦ節が、パトリシア・ツリーに挿入される。ＤＮＦ節は、重複についてチェックされ、重複節は可能な場合は組合せられる。【選択図】図１
2012178151.tif 000002
【特許請求の範囲】
【請求項１】
フィルタ式からバイナリ・ツリーを生成する方法であって、
バイナリ論理演算子を蓄積するに適した演算子スタックをメモリ中に定義するステップと、
フィルタ式ツリーのノードへのポインタを保持するのに適した値スタックを上記メモリ中に定義するステップと、
上記フィルタ式の要素は演算子及び値を含むものであるところ、上記フィルタ式を要素毎に構文解析するステップと、
上記フィルタ式中の次の要素が値の場合に、上記値スタックに上記値を加えるステップと、
上記フィルタ式中の次の要素が演算子の場合に、上記次の要素を上記演算子スタック中の一番上の要素と比較し、上記次の要素と上記一番上の要素に基いて、判断表中に定義されたアクションを実行するステップと
を具えるバイナリ・ツリー生成方法。
【請求項２】
フィルタ式を表すバイナリ・ツリーから上記フィルタ式の積和標準形（ＤＮＦ）を生成する方法であって、
上記バイナリ・ツリーのノードから全てのＮＯＴ演算子を除去するステップと、
左サブ・ツリー・スタック（Ｌスタック）、右サブ・ツリー・スタック（Ｒスタック）、左サブ・ツリー・スタックの結果（ＲＬスタック）及び右サブ・ツリー・スタックの結果（ＲＲスタック）に対応する複数のスタックをメモリ中に定義するステップと、
上記バイナリ・ツリーの各ノードを見に行くという、上記バイナリ・ツリーの上記ノードの後順走査を実行するステップと、
もし見に行ったノードがリーフ・ノードであって、もし該リーフ・ノードが左の子なら、上記リーフ・ノードに割当てられた演算を上記Ｌスタックに挿入し、もし上記リーフ・ノードが右の子なら、上記リーフ・ノードに割当てられた演算を上記Ｒスタックに挿入するステップと、
もし見に行ったノードがノン・リーフ・ノードならば、その演算がＯＲ演算又はＡＮＤ演算を含むかどうかに基づいて、上記ノン・リーフ・ノードを処理するステップと
を具えるフィルタ式の積和標準形生成方法。
【請求項３】
フィルタ式を積和標準形に変換するための命令を含むコンピュータ読み出し可能な記録媒体であって、上記命令は、実行するとプロセッサに、
バイナリ論理演算子を蓄積するに適した演算子スタックをメモリ中に定義するステップと、
フィルタ式ツリーのノードへのポインタを保持するのに適した値スタックを上記メモリ中に定義するステップと、
上記フィルタ式の要素は演算子及び値を含むものであるところ、上記フィルタ式を要素毎に構文解析するステップであって、上記フィルタ式中の次の要素の夫々について、
上記フィルタ式中の次の要素が値の場合に、上記値スタックに上記値を加えるステップと、
上記フィルタ式中の次の要素が演算子の場合に、上記次の要素を上記演算子スタック中の一番上の要素と比較し、上記次の要素と上記一番上の要素に基いて、判断表中に定義されたアクションを実行するステップと
完了したバイナリ・ツリーを上記値スタックから除去するステップと、
左サブ・ツリー・スタック（Ｌスタック）、右サブ・ツリー・スタック（Ｒスタック）、左サブ・ツリー・スタックの結果（ＲＬスタック）及び右サブ・ツリー・スタックの結果（ＲＲスタック）に対応する複数のスタックをメモリ中に定義するステップと、
完了した上記バイナリ・ツリーの各ノードを見に行くという、完了した上記バイナリ・ツリーの上記ノードの後順走査を実行するステップであって、上記後順走査中に、
もし見に行ったノードがリーフ・ノードであって、もし該リーフ・ノードが左の子なら、上記リーフ・ノードに割当てられた演算を上記Ｌスタックに挿入し、もし上記リーフ・ノードが右の子なら、上記リーフ・ノードに割当てられた演算を上記Ｒスタックに挿入するステップと、
もし見に行ったノードがノン・リーフ・ノードならば、その演算がＯＲ演算又はＡＮＤ演算を含むかどうかに基づいて、上記ノン・リーフ・ノードを処理してデータをＲＬスタック又はＲＲスタックに移動させるステップと、
上記バイナリ・ツリーのルート・ノードを処理するステップと、
上記ルート・ノードに対応する上記ＲＬスタック又は上記ＲＲスタックから上記フィルタ式の上記積和標準形を除去するステップと、
上記フィルタ式の上記積和標準形から重複するキーを特定するステップと
を含むアクションを実行させることを特徴とするコンピュータ読み出し可能な記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ＰＣＡＰ形式フィルタをパトリシア・ツリーに挿入可能な形式に変換するためのバイナリ・ツリー及び積和標準形（ＤＮＦ）の生成方法に関する。
【背景技術】
【０００２】
パケット・キャプチャ（ＰＣＡＰ）フィルタは、パケット・データ・ネットワークにおいて、流れているデータ・トラフィックの関心のある部分を抽出し、ユーザが更に詳しく調査するために一般に使用されている。このフィルタ形式は、多くの場合、フィルタ仕様が柔軟で点で好ましい。ＰＣＡＰフィルタの実現する場合、典型的には、その式をバークレー・パケット・フィルタ（Berkeley packet filter：ＢＰＦ）の形式に変換する。しかし、１０Ｇｂｐｓ以上のオーダーの高帯域ネットワークをモニタする場合、ＢＰＦに合致したパケットをランダムに取りこぼすことなしに、ＢＰＦを適用することはほとんど不可能である。
【先行技術文献】
【特許文献】
【０００３】
【特許文献１】特開２００７−６８１６２号公報
【発明の概要】
【発明が解決しようとする課題】
【０００４】
今日では、ハードウェア支援型パトリシア・ツリーを用いることで、アプリケーションが回線速度でフィルタ処理を実行可能にする専用プロセッサが存在する。プロセッサのアーキテクチャ自身が、パトリシア・ツリーを回線速度で検索できることを保証している。しかし、ＰＣＡＰ形式フィルタは、変形無しでパトリシア・ツリーに挿入することができない。
【課題を解決するための手段】
【０００５】
本願に開示された方法及びシステムは、ＰＣＡＰ形式フィルタをパトリシア・ツリーに挿入可能な形態にどのように変換するかを開示している。これによれば、ＥＺチップ・テクノロジー社のＮＰ−Ｘシリーズ・プロセッサのような専用ハードウェアで、４０Ｇｂｐｓ程度の速度で無損失フィルタ処理の実行が可能になる。
【０００６】
１つの実施形態では、ＰＣＡＰ形式フィルタのためのフィルタ式（Filter Expression）の構文分析が行われ、積和標準形（ＤＮＦ：Disjunctive Normal Form）へ変換される。ＤＮＦ中のフィルタの論理積節のそれぞれは、パトリシア・ツリーに挿入できる。しかし、ハードウェア支援型パトリシア・ツリーは、考慮すべきある制約がある。第１に、これらツリーをライン速度で検索できるプロセッサは、典型的には、リアセンブリ（Reassembly）を全く行わない。従って、フィルタ処理に利用するフィールドは、典型的には、ＯＳＩ（Open Systems Interconnection）モデルのレイヤ２からレイヤ４においてである。例えば、Ｌ７のプロトコルがよく知られたトランスポート・アドレスを使用するなど、上位レイヤからの情報が、下位レイヤ中の情報から得られる場合には、例外がある。この場合、Ｌ７プロトコルをフィルタ処理に利用しても良い。これは、レイヤ３及びレイヤ４中のトランスポート情報から導くことができるからである。第２に、ツリーに関するエントリは、予め定義しなければならず、このため、このフィルタはパケット中の任意のランダムなバイトには適用できない。第３に、これらツリーのキーには、そのサイズに制限がある（ＮＰ−Ｘシリーズ・プロセッサの場合、３８バイト）。第４に、これらツリーは、検索を実施して複数のエントリにマッチしても、最初にマッチしたものを返す、つまり、重複するフィルタはサポートしない。第３及び第４の制約を克服するには、フィルタ式の特別な操作が必要で、ツリーに挿入可能なフィルタ数が制限される。
【０００７】
本発明の第１概念は、フィルタ式からバイナリ・ツリーを生成する方法であって、
メモリ中にバイナリ論理演算子を記憶するのに適合した演算子スタックを定義するステップと、
フィルタ式ツリーのノードへのポインタを含むのに適合した値スタックを定義するステップと、
演算子と値を有する上記フィルタ式の構文分析を要素毎に行うステップと、
もし上記フィルタ式中の次の要素が値なら、該値を上記値スタックに加えるステップと、
もし上記フィルタ式中の次の要素が演算子なら、上記次の要素を上記演算子スタック中の一番上の要素と比較し、上記次の要素と上記一番上の要素に基づいて判断表（テーブル）に定義された動作を実行するステップとを具えている。
【０００８】
本発明の第２概念は、第１概念の方法であって、上記判断表中に定義された上記動作がシフト機能であって、これにおいて上記次の要素が上記演算子スタックに加えられるものである。
【０００９】
本発明の第３概念は、第１概念の方法であって、上記次の要素が演算子であり、上記判断表中に定義された上記動作が削減機能であって、上記演算子が上記値スタック中の上位２つの値に適用されるものである。
【００１０】
本発明の第４概念は、第３概念の方法であって、更に、上位２つの値に適用される上記演算子に対応する新しい値を上記値スタックに追加するステップを具えている。
【００１１】
本発明の第５概念は、第１概念の方法であって、上記判断表中に定義されるアクションが受け入れ機能であり、更に、上記値スタックから上記バイナリ・ツリーを移動する処理を具えている。
【００１２】
本発明の第６概念は、第５概念の方法であって、上記バイナリ・ツリーを積和標準形に変換するステップを更に具えている。
【００１３】
本発明の第７概念は、第１概念の方法であって、上記演算子が論理積（ＡＮＤ）、論理和（ＯＲ）及び否定（ＮＯＴ）を含んでいる。
【００１４】
本発明の第８概念は、第１概念の方法であって、上記値が関係演算式を表している。
【００１５】
本発明の第９概念は、第１概念の方法であって、上記値が論理演算式及び関係演算式を組み合わせた結果を表している。
【００１６】
本発明の第１０概念は、フィルタ式のバイナリ・ツリー表現からフィルタ式の積和標準形（ＤＮＦ）を生成する方法であって、
上記バイナリ・ツリーのノードから否定（ＮＯＴ）演算を除去するステップと、
左サブ・ツリー・スタック（Ｌスタック）、右サブ・ツリー・スタック（Ｒスタック）、左サブ・ツリー・スタックの結果（ＲＬスタック）、右サブ・ツリー・スタックの結果（ＲＲスタック）に対応するスタックをメモリ中に定義するステップと、
ポスト・オーダーでバイナリ・ツリーの各ノードの横断を実行してバイナリ・ツリーの各ノードを見に行くステップと、
もし見に行ったノードがリーフ・ノードである場合、もし該リーフ・ノードが左の子なら上記リーフ・ノードに割り当てられた演算をＬスタックに挿入し、又は、もし上記リーフ・ノードが右の子なら上記リーフ・ノードに割り当てられた演算を右スタックに挿入するステップと、
もし見に行ったノードがノン・リーフ・ノード（リーフ・ノードでないノード）ならば、上記演算が論理和（ＯＲ）演算又は論理積（ＡＮＤ）演算を含むかにどうかに基いて、上記ノン・リーフ・ノードを処理するステップとを具えている。
【００１７】
本発明の第１１概念は、第１０概念の方法であって、更に、
上記ノン・リーフ・ノードが論理和演算を含み、上記ノン・リーフ・ノードの子ノードがリーフ・ノードの場合、
もし上記ノン・リーフ・ノードが左の子なら、上記Ｒスタック及びＬスタックから全てのノードをＲＬスタックに移動するステップと、
もし上記ノン・リーフ・ノードが右の子なら、上記Ｒスタック及びＬスタックから全てのノードをＲＲスタックに移動するステップとを具えている。
【００１８】
本発明の第１２概念は、第１０概念の方法であって、更に、
上記ノン・リーフ・ノードが論理和演算を含み、上記ノン・リーフ・ノードの子ノードがリーフ・ノードでない場合に、
もし上記ノン・リーフ・ノードが左の子なら、上記ＲＲスタック及びＲＬスタックから全てのノードをＲＬスタックに移動するステップと、
もし上記ノン・リーフ・ノードが右の子なら、上記ＲＲスタック及びＲＬスタックから全てのノードをＲＲスタックに移動するステップとを具えている。
【００１９】
本発明の第１３概念は、第１０概念の方法であって、更に、
上記ノン・リーフ・ノードが論理積演算を含み、上記ノン・リーフ・ノードの子ノードがリーフ・ノードの場合、
上記Ｒスタック中の全てのノードと上記Ｌスタック中の全てのノードを組み合わせて１つの論理積節（conjunctive clause）を生成するステップを具えている。
【００２０】
本発明の第１４概念は、第１３概念の方法であって、更に、
もし上記ノン・リーフ・ノードが左の子なら、１つの論理積節を上記ＲＬスタックに挿入するステップと、
もし上記ノン・リーフ・ノードが右の子なら、１つの論理積節を上記ＲＲスタックに挿入するステップとを具えている。
【００２１】
本発明の第１５概念は、第１０概念の方法であって、更に、
上記バイナリ・ツリーのルート・ノードを処理するステップであって、処理中は上記ルート・ノードを左の子として扱うステップと、
上記フィルタ式の上記積和標準形をＲＦスタックから移動するステップとを具えている。
【００２２】
本発明の第１６概念は、第１０概念の方法であって、更に、フィルタ式の積和標準形から重複するキーを特定するステップを更に具えている。
【００２３】
本発明の第１７概念は、フィルタ式を積和標準形に変換する命令を含むコンピュータで読み出し可能な記録媒体であって、上記命令は、実行するとプロセッサに、
バイナリ論理演算子を蓄積するに適した演算子スタックをメモリ中に定義するステップと、
フィルタ式ツリーのノードへのポインタを保持するのに適した値スタックを上記メモリ中に定義するステップと、
上記フィルタ式の要素は演算子及び値を含むものであるところ、上記フィルタ式を要素毎に構文解析するステップであって、上記フィルタ式中の次の要素の夫々について、
上記フィルタ式中の次の要素が値の場合に、上記値スタックに上記値を加えるステップと、
上記フィルタ式中の次の要素が演算子の場合に、上記次の要素を上記演算子スタック中の一番上の要素と比較し、上記次の要素と上記一番上の要素に基いて、判断表中に定義されたアクションを実行するステップと、
完了したバイナリ・ツリーを上記値スタックから除去するステップと、
左サブ・ツリー・スタック（Ｌスタック）、右サブ・ツリー・スタック（Ｒスタック）、左サブ・ツリー・スタックの結果（ＲＬスタック）及び右サブ・ツリー・スタックの結果（ＲＲスタック）に対応する複数のスタックをメモリ中に定義するステップと、
完了した上記バイナリ・ツリーの各ノードを見に行くという、完了した上記バイナリ・ツリーの上記ノードの後順走査を実行するステップであって、上記後順走査中に、
もし見に行ったノードがリーフ・ノードであって、もし該リーフ・ノードが左の子なら、上記リーフ・ノードに割当てられた演算を上記Ｌスタックに挿入し、もし上記リーフ・ノードが右の子なら、上記リーフ・ノードに割当てられた演算を上記Ｒスタックに挿入するステップと、
もし見に行ったノードがノン・リーフ・ノードならば、その演算がＯＲ演算又はＡＮＤ演算を含むかどうかに基づいて、上記ノン・リーフ・ノードを処理してデータをＲＬスタック又はＲＲスタックに移動させるステップと、
上記バイナリ・ツリーのルート・ノードを処理するステップと、
上記ルート・ノードに対応する上記ＲＬスタック又は上記ＲＲスタックから上記フィルタ式の上記積和標準形を除去するステップと、
上記フィルタ式の上記積和標準形から重複するキーを特定するステップと
を含むアクションを実行させることを特徴とする。
【００２４】
本発明の第１８概念は、第１７概念のコンピュータで読み出し可能な記録媒体であって、
もしノン・リーフ・ノードがＯＲ演算を含み、そのノン・リーフ・ノードの子ノ―ドがリーフ・ノードであって、
もし上記ノン・リーフ・ノードが左の子ならば、上記Ｒスタック及びＬスタックから全てのノードをＲＬスタックに移動するステップ、又は、もし上記ノン・リーフ・ノードが右の子ならば、上記Ｒスタック及びＬスタックから全てのノードをＲＲスタックに移動するステップを有するステップと、
もし上記ノン・リーフ・ノードがＯＲ演算を含み、そのノン・リーフ・ノードの子ノ―ドがリーフ・ノードであって、
もしノン・リーフ・ノードが左の子ならば、上記ＲＲスタック及び上記ＲＬスタックから全てのノードをＲＬスタックに移動するステップ、又は、もしノン・リーフ・ノードが右の子ならば、上記ＲＲスタック及び上記ＲＬスタックから全てのノードをＲＲスタックに移動するステップと、
もし上記ノン・リーフ・ノードがＡＮＤ演算を含み、そのノン・リーフ・ノードの子ノ―ドがリーフ・ノードならば、
上記Ｒスタック中の全てのノードを上記Ｌスタック中の全てのノードを組み合わせて、単一の論理積節を生成するステップと、
もし上記ノン・リーフ・ノードが左の子なら上記単一の論理積節を上記ＲＬスタックに挿入するステップ、又は、もし上記ノン・リーフ・ノードが右の子なら上記単一の論理積節を上記ＲＲスタックに挿入するステップと
を更に具えている。
【００２５】
本発明の第１９概念は、第１７概念のコンピュータで読み出し可能な記録媒体であって、上記完全なバイナリ・ツリーのノードから全てのＮＯＴ演算を除去するステップを更に具えているものである。
【００２６】
本発明の目的、効果及び他の新規な点は、以下の詳細な説明を添付の特許請求の範囲及び図面とともに読むことによって明らかとなろう。
【図面の簡単な説明】
【００２７】
【図１】図１は、通信ネットワーク中のパケットをキャプチャし、フィルタ処理するシステムを描いたハイレベル・ブロック図である。
【図２】図２は、バイナリ・ツリー形態によるフィルタ表現の例である。
【図３】図３は、構文解析判断表を用いてフィルタ・ツリーを生成する処理を描いている。
【発明を実施するための形態】
【００２８】
ここから本発明について、図を参照しながら、詳しく説明する。しかし、本発明は、多くの異なる形態で実現でき、本願に記載した実施形態に限定されると解釈すべきではない。逆に、これら実施形態は、本願における開示を綿密かつ完全なものとし、当業者に対して本発明の完全な範囲を伝えようとするものである。当業者であれば、本発明の種々の実施形態を利用できるであろう。
【００２９】
図１は、通信ネットワーク中のパケットをキャプチャし、フィルタ処理するシステムを描いたハイレベル・ブロック図である。ネットワーク・ノード１０１及び１０２は、インタフェース１０３を介して結合される。データ・パケットのようなネットワーク・トラフィックは、インタフェース１０３を通じてノード１０１及び１０２間を行き来する。フィルタ１０４は、インタフェース１０３からのデータ・パケットを受動的にキャプチャし、そのパケットをモニタリング・デバイス（モニタリング・プローブ）１０５に渡す。モニタリング・デバイス１０５は、例えば、プロトコル・アナライザ、ネットワーク・モニタ、パケット・スニファー（sniffer：探知装置）又はネットワーク・テスタなどと関連するものとしても良い。キャプチャされたデータ・パケットは、ユーザに対して表示したり、ネットワークの問題解決、プロトコル分析、ソフトウェア開発のために利用したりしても良い。
【００３０】
フィルタ１０４は、ＥＺチップ・テクノロジーズ（EZchip Technologies）社製のＮＰ−Ｘシリーズ・プロセッサのようなプロセッサとしても良い。インタフェース１０３上を流れるモニタリング・デバイス１０５に供給すべきデータ・パケットを特定するのに使われるフィルタ式（Filter Expression）を、ユーザが定義しても良い。このフィルタ式は、送信元（ソース）／受信先（ディスティネーション）のアドレス又はポート、仮想ＬＡＮ（Virtual LAN）識別子、ＩＰプロトコル、バ―ジョン又はサービス種別（Type of Service：TOS）などの多数のデータ・パケット・パラメータを含んでいても良い。これらパラメータを、関係演算子又は論理演算子を用いて変数と比較しても良い。しかし、フィルタ１０４の実際の能力は、フィルタ式で要求される要素と合致しないかもしれない。例えば、フィルタ１０４は、関係演算子又は論理演算子の特定のグループを使うように設計されているかもしれない。フィルタ式は、フィルタ１０４で処理できない関係演算子又は論理演算子を全て排除するように修正されなければならない。
【００３１】
フィルタ１０４は、インタフェース１０３からＩＰデータ・パケットをリアルタイムでキャプチャする。このデータ・パケットをリアルタイムで処理するために、フィルタ１０４は、４０Ｇｂｐｓ以上の伝送速度でも動作しなければならない。このような高速でキャプチャしたデータを処理するのには、パトリシア・ツリーを用いることができる。しかし、そのフィルタのハードウェアには、フィルタ式のフォーマットに特定の制限がある。ユーザが用意するフィルタ式は、このフィルタ・ハードウェア及びパトリシア形式に合致するよう改変しなければならない。例えば、実施形態によっては、フィルタ・ハードウェアは、フィルタ項間の論理積（ＡＮＤ）関係だけしかサポートしないかもしれない。ユーザが用意するフィルタ式は、この制限に合致するように変換されなければならない。本願に記載された実施形態は、フィルタ式を分解し、そのフィルタ式をパトリシア・ツリーに適用して、そのフィルタがパケットを取りこぼすことなく伝送速度で動作可能にするアプリケーションに向けたものである。
【００３２】
１つの実施形態では、フィルタ式がバイナリ・ツリー・データ構造に変換され、これは論理演算を表す他のノードへの入力を提供する関係演算を表すリーフ（leaf：葉）ノードを含んでいる。このバイナリ・ツリーは、積和標準形に変換され、この中における関係式は論理積（ＡＮＤ）演算だけである。積和標準形への変換では、オリジナルのフィルタ式から複数のフィルタ・エントリが生成される。複数のフィルタには重複部分があり、これら重複部分において、任意のデータ・パケットは、２つ以上のフィルタと合致することがある。異なるフィルタにおける論理積節（conjunctive clause）の共通部分（intersection）は、特定されて、個別の論理積節としてバイナリ・ツリーに加えなければならない。
【００３３】
フィルタ仕様のサンプル
【００３４】
１つの実施形態では、複数のフィルタが表１のリストに示すパケットのフィールド（Field：領域）をサポートする。これらフィールドは、次の関係演算子をサポートする。即ち、＞（より大きい）、＜（より小さい）、＞＝（以上）、＜＝（以下）、＝＝（等しい）、！＝（等しくない）。また、次の論理演算子もサポートする。即ち、ＡＮＤ（論理積）、ＯＲ（論理和）、ＮＯＴ（論理否定）。１つのインタフェース・カード当たりのフィルタ・インスタンス（instance）の最大数は４であり、１つのフィルタ・インスタンス当たりの項の最小数は３２である。
【００３５】
【表１】
2012178151.tif 000003
【００３６】
ハードウェア支援型パトリシア・ツリー仕様
【００３７】
表２は、ハードウェア支援型パトリシア・ツリーのためのスニファー複合型ツリー・エントリを示す。
【００３８】
【表２】
2012178151.tif 000004
【００３９】
フィルタ文字列を解析し、そのフィルタのバイナリ・ツリー表現を生成する。
【００４０】
１つの実施形態では、フィルタ式は１０個のフィルタ処理フィールドをサポートする。このフィルタ式は、文字列（String）として与えられ、表３に示される特性を有する。フィルタ処理フィールドは、Ｒ０からＲ９として示される。
【００４１】
【表３】
2012178151.tif 000005
【００４２】
このフィルタ式は、関係演算子（＞、＜、＞＝、＜＝、＝＝及び！＝）、２項論理演算子（binary logical operator）ＡＮＤ及びＯＲ、並びに単項論理演算子ＮＯＴをサポートする。加えて、フィルタ式は、カッコ演算子”（”と”）”もサポートする。フィルタ式では、左から右、又は、カッコで示されたものに優先順位がある。関係演算子は、論理演算子よりも優先順位が高く、論理演算子の優先順位はみな同じである。この例では、１つのインタフェース・ボード当たりのフィルタ・インスタンスの最大数は１６であり、１つのフィルタ・インスタンス当たりの演算子の最小数は１６である。
【００４３】
上記で定義されたパラメータを用いて、フィルタ文字列の例を次のように定義しても良い：Ｆ［Ｐ］＝Ｒ０＝＝０ＡＮＤＲ１＝＝０ＡＮＤＲ４＝＝１７ＡＮＤ（Ｒ６＝＝３２３２２４０９９５ＯＲＲ７＝＝３２３２２４０９９５）ＡＮＤ  Ｒ８＝＝９２０１．
【００４４】
なお、本願で提示したフィルタ式は、単に実施代表例に過ぎないことが理解されよう。更に、当業者であれば、同じコンセプトの異なる実施形態を利用可能なことが理解できよう。例えば、表１及び表２のフィルタ表現は、ユーザのアプリケーションに提供が必要とされる形式ではないが、例として提示している。開発者は、そのアプリケーションに従って適切なフィルタの文法（syntax：シンタックス）を定義しなければならない。本願におけるフィルタ文法は、さらに発展させることが可能なオプションである。しかし、実際のアプリケーションでは、フィールド・トークン（Ｒ０からＲ９まで）をストリング（文字列）トークンに入れ替えても良く、これはフィールド表示よりも記述的である。このセクションで説明される制約は、受け入れ可能であって、要求性能に合うようにスニファ・フィルタ処理可能な推奨される制約である。開発者は、要求性能に合う限り、フィルタ・インスタンスの数又は１インスタンス当たりのフィルタ項を増加させるのは自由である。
【００４５】
先に定義したフィルタ・ストリング例のようなフィルタ式を解析することで、そのフィルタを表すバイナリ・ツリーを生成しても良い。図２は、バイナリ・ツリーの代表的な表現である。バイナリ・ツリー２００は、複数のノード２１０〜２１１を含む。１つの実施形態では、バイナリ・ツリーは次の特性を有している。ツリー中のノード２１０〜２１１の夫々は、２つの子を持つ（例えば、２０１〜２０６）か、又は、子を持たないか（例えば、２０７〜２１１）のどちらかである。ツリー中のノードの夫々は、フィルタ・インスタンス中で、否定（ＮＯＴ）演算子以外の関係演算子又は論理演算子に割り当てられる。従って、この実施例では、ツリー中のノードの最大数は１６である。子を持たない全ノード（２０７〜２１１）は、リーフ（葉）ノードと呼ばれ、フィルタ・フィールド（つまり、フィールドＲ０〜Ｒ９）と３２ビット定数の間の関係演算を含む。リーフ・ノードには、入力がない。
【００４６】
２つの子を持つ全ノード（２０１〜２０６）は、２項論理演算（例えば、ＡＮＤやＯＲ）を含んでいる。２項論理演算への複数の入力は、そのノードの子から提供される結果である。各ノードは、最終結果を提供するルート・ノード２０１を除いて、その親ノードへの入力として提供される結果を生成する。全ノードは、そのノードからの最終結果を親ノードへの入力として通過させる前に、無効とするか否かを示す指標を含んでいる。この指標は、否定（ＮＯＴ）演算を表す。各ノードの子へのポインタは、重み付け（Weight：ウェイトＷ）を伴い、これは、そのノードから最も遠いリ―フ・ノードまでの距離を示す。
【００４７】
フィルタ式ツリー・ノードについての構成のサンプル
【００４８】
表４は、ツリー・ノードのフィルタ式を表す構成のサンプル（struct FilterExpNode）を示している。
【００４９】
【表４】
2012178151.tif 000006
【００５０】
他の実施形態では、ノード構造に異なる形式を用いても良い。例えば、ＩＰｖ６をサポートするために、２つの６４ビット定数又は４つの３２ビット定数（ｋ）のどちらかがノード構造中に必要とされる。
【００５１】
以下では、フィルタ式を表すバイナリ・ツリーを生成する処理の概要を説明する。この処理に入力されるのは、被解析対象の式である。
【００５２】
第１に、全ての演算子及びフィルタ変数にコードが定義される。例えば、表５は、演算コードの例を示し、表６はフィルタ式解析アプリケーションで利用されるフィルタ変数コードの例を示す。
【００５３】
【表５】
2012178151.tif 000007
【００５４】
【表６】
2012178151.tif 000008
【００５５】
次に、２つのスタックが定義される。１つは演算子スタック（ＯＰ）で、もう１つは値スタック（Ｖ）である。演算子スタックは、２項論理演算子を保持し、値スタックは、フィルタ式ツリーへのポインタを保持する。最初は、両方のスタックとも空である。
【００５６】
続いて、式を左から右へと、一度に１要素ずつ解析する。「要素」は、値（Value）又は演算子としても良い。上述のように、１つ実施形態としては、有効な演算子が、ＡＮＤ、ＯＲ、ＮＯＴ、”（”及び”）”である。有効な値は、フィルタ・ノード形式における関係式又はフィルタ・ツリー形式における論理及び関係式を組み合わせた結果である。最終結果は、全フィルタ式を表すフィルタ・ツリー形式中の値スタックに収容される。
【００５７】
入力演算子（つまり、フィル式中の次の要素）及びＯＰスタックの一番上の演算子に応じて取るべきアクションを記述するために、２次元判断表が定義される。判断表中にあり得るアクションは、ＳＨＩＦＴ（シフト）、ＲＥＤＵＣＥ（減少）及びＡＣＣＥＰＴ（受け入れ）である。ＳＨＩＦＴについては、フィルタ式からの次の要素がＯＰスタックに加えられる。ＲＥＤＵＣＥについては、１つの演算がスタックから飛び出てきて、ＮＯＴの場合では１つの要素に適用される演算が得られ、ＡＮＤ又はＯＲの場合には、２つの要素に適用される演算が得られる。複数の要素が値スタックから得られる。演算の結果は、値スタックに再挿入される。ＡＣＣＥＰＴについては、最終ツリーが値スタックから除かれる。表７は、１つの実施形態による解析アプリケーションで利用される代表的な判断表を示している。
【００５８】
【表７】
2012178151.tif 000009
【００５９】
”（”演算子が、スタックの一番上に位置し、入力演算子が”）”の場合、押し出し（ポップ：pop）処理で”（”演算子を除去し演算子スタックを減少させる。従って、”）”演算子は、スタック中に挿入されることはない。
【００６０】
式が解析されると、解析ユニットは、演算子（ＡＮＤ、ＯＲ、ＮＯＴ、”）”及び”（”）又は次の形式の値である。
［フィールド］［関係演算子（＞、＜、＞＝、＜＝、＝＝又は！＝）］［定数］
【００６１】
関係演算全体は、値と考えられる。値は、フィルタ式ノードへのポイントの形式で、常に値スタックに詰め込まれる。ノードが値スタックに挿入されるように割り当てられると、表４のフィールドは、次のように初期化される。
pFilterExpNode->not = 0;
pFilterExpNode->operator = code for operation;
pFilterExpNode->pc = 0;
pFilterExpNode->input = code for R0 -> R9, extracted from relational expr.;   
pFilterExpNode->wRight = 0;
pFilterExpNode->wLeft = 0;
pFilterExpNode->k = 32-bit constant extracted from relational expression;
pFilterExpNode->pRight = NULL;
pFilterExpNode->pLeft = NULL; and
pFilterExpNode->pParent = NULL.
【００６２】
スタックが減少したとき、値ノードは次のように組合せられる。
【００６３】
もしＯＰスタック中の演算子がＮＯＴなら、その演算子は押し出され、１つの値ノードが押し出される。値ノードのｎｏｔフィールドが１に設定され、値ノードは値スタックに詰め込まれる。
【００６４】
もしＯＰスタック中の演算子がＡＮＤ又はＯＲなら、その演算子は押し出され（pop）、ノードが割り当てられて、上述のように初期化される。加えて、２つの値ノードが押し出される。一方のノードは、新しいノードの右の子となり、他方の値ノードは新しいノードの左の子となる。子ノードの親ポインタは、その新しいノードを指すように更新されなければならない。最後に、親ノードの重み付け（Ｗ）を調整する必要があり、そして、ポインタが値スタックに詰め込まれる。この重み付けの調整は、次のように行われる。
【００６５】
構文解析アルゴリズムは、演算子スタックが空（ENPTY）となって、最後のフィルタ式に達するまで、上述のようにフィルタ式の全ての要素の処理を続ける。この時点で、フィルタ式ツリーへのポインタを取り出すために、値スタックは押し出される。
【００６６】
図３は、フィルタ・ツリーを生成する構文解析判断表を使うための処理を示している。例えば、構文解析アプリケーションは、次の入力フィルタ・ストリングを用いて、入力式を処理し、対応するフィルタ・ツリーを生成する。
Ｆ＝Ｒ０＝＝０  ＡＮＤ  Ｒ１＝＝０  ＡＮＤ  Ｒ４＝＝１７
【００６７】
ステップ３０１では、演算子（ＯＰ）スタック及び値（Ｖ）スタックは、両方とも空（ENPTY）であり、構文解析アプリケーションは入力ストリングを受ける。取られるアクションは、ＳＨＩＦＴ（シフト）であり、これにおいて、フィルタ式の次（つまり、第１）の要素がＶスタックに追加される。ステップ３０２では、ＯＰスタックはまだ空であるが、Ｖスタックは今や第１フィルタ要素Ｒ＝＝０を保持している。入力は、フィルタ式の残り（つまり、ＡＮＤ  Ｒ１＝＝０  ＡＮＤ  Ｒ４＝＝１７）を保持している。この場合、次のアクションは、演算子（ＡＮＤ）である。このため、ステップ３０３では、ＡＮＤ演算子がＯＰスタックに加えられ、Ｖスタックは第１要素Ｒ＝＝０を保持する。入力は、フィルタ式の残りを保持する。再び、アクションはＳＨＩＦＴであり、フィルタ式の次の要素をスタックに加える。
【００６８】
ステップ３０４では、ＯＰスタックはまだＡＮＤ演算子を保持し、次のフィルタ要素（Ｒ１＝＝０）がＶスタックの一番上に加えられる。入力は、フィルタ式の残りを保持する。取られるアクションは、フィルタ式の次の要素が「ＡＮＤ」演算子なので、ＲＥＤＵＣＥ（削減）である。これは、判断表（表７）と一致している。ＲＥＤＵＣＥ演算では、Ｖスタック中の２つの要素が「押し出され（popped）」ることを必要とし、ＡＮＤ演算がこれら要素に適用される。
【００６９】
ステップ３０５では、ＡＮＤ演算がステップ３０４の後に適用されたので、ＯＰスタックが空である。Ｖスタックは、「（Ｒ１＝＝０  ＡＮＤ  Ｒ２＝＝０）」の式を含み、入力はフィルタ式の残りを含んでいる。判断表によれば、ＯＰスタックが空で、次の要素がＡＮＤ演算子のときの適切なアクションは、ＳＨＩＦＴである。
【００７０】
ステップ３０６では、ＡＮＤ演算子がＯＰスタックに加えられ、Ｖスタックは「（Ｒ１＝＝０  ＡＮＤ  Ｒ２＝＝０）の式を保持し、入力はフィルタ式の残り（Ｒ４＝＝１７）を保持する。アクションは、ＳＨＩＦＴである。ステップ３０７では、フィルタ要素（Ｒ４＝＝１７）がＶスタックに加えられ、これによって入力は空（EMPTY）になる。結果として、そのアクションはＲＥＤＵＣＥ（削減）である。従って、ステップ３０８では、Ｖスタック中の上位２つの要素が「押し出され」て、ＡＮＤ演算子が適用される。得られる最終的なツリー、Ｒ４＝＝７  ＡＮＤ  （Ｒ１＝＝０  ＡＮＤ  Ｒ０＝＝０）は、Ｖスタックから移動して除かれる。
【００７１】
スニファ（Sniffer）フィルタの積和標準形への変換
【００７２】
ハードウェア支援型パトリシア・ツリーのフィルタ処理能力を利用するためには、フィルタ式を積和標準形（ＤＮＦ）に変換しなければならない。１つの実施形態では、スニファ・フィルタが、バイナリ複合ツリー（binary complex tree）に挿入される。バイナリ複合ツリーは、伝統的なバイナリ・パトリシア・ツリーで使われているバイナリ（binary：２分）形式及びターナリ（ternary：３分＝バイナリ＋ワイルドカード）形式に加えて、１エントリにつき、複数の複合ルールを定義可能なツリーである。
【００７３】
複数の複合エントリが、フィールドのシリーズとして複合ツリーに挿入されるが、各フィールドは次のパラメータで定義される。
フィールドのサイズ（単位：ビット）
フィールド種別
フィールド種別に応じた１、２個の値
エンディアン（Endiannes：多バイト・データの配置方式）
【００７４】
フィールド種別は、例えば、次のようなものである。
ノーマル（Normal）：フィールドは、バイナリのキー及びマスクを表す
エニー（Any：任意）：フィールドは、フィールド範囲内の全ての値を表す（ワイルドカード）
イコール（Equals：等価）：フィールド値は、特定の単一の値と等しい
ノン・イコール（Not-equals:等しくない）：フィールドは、特定の単一の値以外の任意の値を表す
レンジ（Range：範囲）：フィールドは、特定範囲内の全ての値を表す
グレーター・ザン（Greater-than：よりも大きい）：フィールドは、特定の境界よりも大きい全ての値を表す
レス・ザン（Less-than：よりも小さい）：フィールドは、特定の境界よりも小さい全ての値を表す
【００７５】
複合ツリーは、通常のバイナリ・パトリシア・ツリーとして定義される。複合エントリを１つ以上のバイナリ・ツリー又はターナリ・ツリーに変換するのに、ＡＰＩを利用しても良い。このため、単一の複合エントリは、複数の単一エントリを生成できる。
【００７６】
１つのバイナリ・ツリー・エントリ中の全てのフィールドは、論理ＡＮＤ演算子で相互に結合される一方、同じツリー内の異なるエントリは、論理ＯＲ演算子で相互に結合される。従って、スニファ・フィルタを複合ツリーに挿入できるようにするためには、フィルタ式をＤＮＦ形式に変換しなければならない。積和標準形は、論理式の正規化であり、論理積（連言）節の論理和（選言）となる。言い換えると、スニファ・フィルタとの関連で言えば、各論理積節は、論理演算子ＡＮＤで結合されるフィールドのグループを表す一方、各論理和節は、論理演算子ＯＲによるゼロ以上の論理積節を結合させるものである。
【００７７】
例えば、図１の例で用いたフィルタ式は、以下に示すようにしてＤＮＦに変換できる。即ち、オリジナルのフィルタ式：F[P] =  R0 = = 0 AND R1 = = 0 AND R4 = = 17 AND (R6 = = 3232240995 OR R7 = = 3232240995) AND R8 = = 9201
は、ＤＮＦ形式では次のように表せる。
F[P] = (R0 = = 0 AND R1 = = 0 AND R4 = = 17 AND R6 = = 3232240995 AND R8 = = 9201) OR (R0 = = 0 AND R1 = = 0 AND R4 = = 17 AND R7 = = 3232240995 AND R8 = = 9201)
【００７８】
フィルタ式をＤＮＦに変換することで得られる全ての論理積節は、個別のエントリとして複合ツリーに挿入できる。上述の例から、単一のスニファ・フィルタは、多数の複合ツリー・エントリを生じさせることができることがわかる。
【００７９】
その他の有益なアナロジー（類推）は、スニファ・フィルタを代数式として考えるというもので、このとき、ＡＮＤ演算子が乗法（掛け算）を表し、ＯＲ演算子が加法（足し算）を表す。既知の乗算の結合則から、次のルールが適用される。
Ａ中の全てのｘ，ｙ，ｚについて：（ｘ＋ｙ）＊ｚ＝ｘ＊ｚ＋ｙ＊ｚ
Ａ中の全てのｘ，ｙ，ｚについて：ｘ＊（ｙ＋ｚ）＝ｘ＊ｙ＋ｘ＊ｚ
Ａ中の全てのｘ，ｙ，ｚについて：ａ＊（ｘ＊ｙ）＝（ａ＊ｘ）＊ｙ＝ｘ＊（ａ＊ｙ）
【００８０】
スニファ・フィルタ式をＤＮＦに変換する出発点は、上述のように句を解析して得られるフィルタのグラフィカル表現である。フィルタのグラフィカル表現から始めて、それに続く更なるステップが行われる。
【００８１】
ツリーから全てのＮＯＴ演算子を除去する。この目的で、ツリーを後順（post-order）で調査する必要がある。この形式のツリー調査により、各ノードの親ノードが処理される前に、各ノードを処理することができる。バイナリ・ツリーを後順で走査するため、次の動作が各ノードで繰り返し実行される：左サブ・ツリーを走査し、右サブ・ツリーを走査し、そして、ルートに行く。ＮＯＴ演算子ビットの設定があるノードが見つかると、表８のルールを適用することによって、そのノード自身に加えて、そのノードの両方のサブ・ツリーを無効にする。
【００８２】
【表８】
2012178151.tif 000010
【００８３】
次の疑似コードは、ＮＯＴ演算子をツリーから除去する処理を示している。
RemoveNotFromTree(pFilterExpNode, negate)
{
if(!pFilterExpNode)
return;
if(pFIlterExpNode->pRight==NULL)
{
if(pFilterExpNode->not==1 || negate==1)
{
pFilterExpNode->not=0;
// Convert opCode using TABLE 8
NegateOpCode(pFilterExpNode);
}
return;
}
RemoveNotFromTree(pFilterExpNode->pLeft, negate);
RemoveNotFromTree(pFilterExpNode->pRight, negate);
if(pFilterExpNode->not==1 || negate==1)
{
negate = 1; 
pFilterExpNode->not = 0;
// Convert opCode using TABLE 8
NegateOpCode(pFilterExpNode); 
RemoveNotFromTree(pFilterExpNode->pLeft, negate);
RemoveNotFromTree(pFilterExpNode->pRight, negate);
negate = 0;
}
}
【００８４】
全てのＮＯＴ演算子の除去されたら、フィルタ・ツリーは、複合ツリー・エントリを表す全ての論理積節を得るために利用できる。次のアルゴリズムが使用される。
【００８５】
ステップ１：４つのリンクされたリストを定義する：Ｌ（左サブ・ツリー）、Ｒ（右サブ・ツリー）、ＲＬ（左サブ・ツリーの結果）及びＲＲ（右サブ・ツリーの結果）。これら４つのリンクされたリストは、ツリーが走査されたときに、得られる論理積節を蓄積するために使われる。リンクされたリスト中の各ノードは、次の情報を保有する。
【００８６】
複合ツリー演算子に基づいて：
enum ComplexEntryOp
{
Any = 0,
Equals,
NotEquals,
Range,
GreaterThan,
LessThan,
MAX_COMPLEX_ENTRY_OP
};
【００８７】
表１に基づき、順番は、複合ツリー・エントリ中のフィールドの順番に従う。
enum ComplexEntryFields
{
PhysicalPort = 0,
L2Type,
Vlan1,
Vlan2,
IpVersion,
IpProtocol,
IpTos,
SourceIp,
DestinationIp,
SourcePort,
DestinationPort,
MAX_COMPLEX_ENTRY_FIELDS
};
【００８８】
複合エントリ中の１つの項（Term）は、次のように表現される：
struct ComplexEntryTerm
{
ComplexEntryOp    operator;
unsigned int        value1[4];
unsigned int        value2[4];
};
【００８９】
複合エントリ中のＡＮＤ演算で結合された全ての項は、次のように表現される：
struct ComplexEntryNode
{
ComplexEntryTerm          terms[MAX_COMPLEX_ENTRY_FIELDS];
ComplexEntryNode * pNext;
ComplexEntryNode * pPrev;
};
【００９０】
ステップ２：後順ツリー調査は、概して次のように実行される：
【００９１】
１）もしリーフ・ノードが処理されたら、演算を含む複合ツリー・エントリ・ノードを、もしそのノードが左サブ・ツリー中にあるならＬに割り当ててＬに挿入し、もしそのノードが右サブ・ツリー中にあるならＲに割り当ててＲに挿入する。
【００９２】
２）もしノン・リーフ・ノード（リーフ・ノードでないノード）が処理されたら：
Ａ）もしそのノードがＯＲ演算を含み、且つその子ノードがリーフ・ノードの場合に、もしそのノードが左の子ならば、全てのノードをＲ及びＬからＲＬに移動し、もしそのノードが右の子ならば、全てのノードをＲ及びＬからＲＲに移動する。
Ｂ）もしそのノードがＯＲ演算を含み、且つその子ノードがリーフ・ノードでない場合に、もしそのノードが左の子ならば、全てのノードをＲＲ及びＲＬからＲＬに移動し、もしそのノードが右の子ならば、全てのノードをＲＲ及びＲＬからＲＲに移動する。
Ｃ）もしそのノードがＡＮＤ演算を含み、且つその子ノードがリーフ・ノードの場合には、Ｒ中の全てのノードをＬ中の全てのノードと組み合わせて１つの論理積節を生成しなければならない。
得られる全エントリは、もしそのノードが右の子ならＲＲに挿入しなければならず、もしそのノードが左の子ならＲＬに挿入しなければならない。付加的な一時的リストが、この目的のために必要となる。
【００９３】
３）ルート・ノードが処理されたら、得られる全ノードは、フィルタ式をＤＮＦで含んでいる。このアルゴリズムの目的には、ルート・ノードを左の子と考えることができ、これは、ＲＬが得られる全ノードを含むことを意味する
【００９４】
次の疑似コードは、ＤＮＦを生成する処理を説明している：
ComplexEntryList L, R, RL, RR;
ComputeOrOfComplexEntryLists( pL1, pL2)
{
// Move all nodes from pL2 to pL1
InsertComplexEntryList( pL1, pL2);
}
ComputeAndOfComplexEntryLists( pL1, pL2)
{
ComplexEntryList T;
ComplexEntryNode *pI, *pJ;
for(pI=CEListGetFirst(pL1); pI!=NULL; pI=CEListGetNext(pL1, pI))
for(pJ=CEListGetFirst(pL2); pJ!=NULL; pJ=CEListGetNext(pL2, pJ))
{
ComplexEntryNode * pNode;
pNode = ComputeAndOfTerms( pI, pJ);
InsertComplexEntryNode( T, pNode);
}
ResetComplexEntryList(pL1);
ResetComplexEntryList(pL2);
// Move all nodes from T to pL1
InsertComplexEntryList( pL1, T);
}
GenerateDNFForTree(pFilterExpNode)
{
ComplexEntryList *pL, *pR;
if(!pFilterExpNode)
return;
// Leaf node processing
if(pFIlterExpNode->pRight==NULL)
{
ComplexEntryNode * pNode;
// Allocate complex entry node and initialize node with
// relational operation in pFilterExpNode.
pNode = AllocComplexEntryNode(pFilterExpNode);
// Left child
if(pFilterExpNode->pParent->pLeft==pFilterExpNode)
InsertComplexEntryNode( L, pNode);
// Right child
else
InsertComplexEntryNode(R, pNode);
return;
}
GenerateDNFForTree(pFilterExpNode->pLeft);
GenerateDNFForTree(pFilterExpNode->pRight);
// Non-leaf node processing
if(pFilterExpNode->pLeft->pLeft==NULL)
// Left node is leaf
pL = &L;
else
// Left node is not leaf
pL = &RL;
if(pFilterExpNode->pRight->pLeft==NULL)
// Right node is leaf
pR = &R;
else
// Right node is not leaf
pR = &RR;
if(pFilterExpNode->op==OR)
{
// OR processing
// Left child
if(pParent==NULL ||
pFilterExpNode->pParent->pLeft==pFilterExpNode)
ComputeOrOfComplexEntryLists( pL, pR);
// Right child
else
ComputeOrOfComplexEntryLists( pR, pL);
}
else
{
// AND processing
// Left child
if(pParent==NULL || 
pFilterExpNode->pParent->pLeft==pFilterExpNode)
ComputeAndOfComplexEntryLists( pL, pR);
// Right child
else
ComputeAndOfComplexEntryLists( pR, pL);
}
}
【００９５】
構文解析プログラム（parser）の結果は、フィルタのＤＮＦ表現である。
【００９６】
ＤＮＦ式の後処理
【００９７】
この時点で、フィルタ式はＤＮＦである。しかし、次の理由から、これをパトリシア・ツリーに挿入できない。第１に、複合ツリー・エントリのキー部分は、フィールドの所定のグループを有し、各フィールドは１度だけ現れ、１つの関係演算及び値とのみ結合できる。第２に、パトリシア・ツリーは、重複するエントリをサポートしない。第３に、ハードウェア支援型パトリシア・ツリーは、キー及び得られるサイズに制限がある。ＮＰ−３型の場合、最大キー・サイズは３８バイトであり、得られる最大サイズは９６バイトである。ＩＰｖ６のアドレス・サイズのため、ＩＰアドレス及びトランスポート・ポート以上のものをフィルタ処理するときには、キー・サイズの制限は、２８バイト・キー・サイズを超えたところで起こる可能性が高い。
【００９８】
複合ツリー・エントリは、フィールドの予め定めたグループを有している。各フィールドは、エントリ中で１回しか現れず、上述の形式（レンジ、ワイルドカードなど）のどれでも取り得る。一度、ＤＮＦ式が得られれば、論理積節の中には、異なる種別の値で同じフィールドを有するものもあるかもしれない。論理積節中に同じフィールドが１回以上現れると、有効な式の場合もあるし、不適当な式の場合もある。一般的なルールとして、もし論理積節が不適当、つまり、矛盾があると判断されると、その論理積節は無視されて、警告メッセージがユーザに送られる。
【００９９】
表９及び表１０は、同じフィールドを有する複数の関係演算が、これらが同じ論理積節の一部として存在しているときに、どのように解釈されるかを説明している。
【０１００】
【表９】
2012178151.tif 000011
【０１０１】
【表１０】
2012178151.tif 000012
【０１０２】
図９及び図１０に記載した変換は、各論理積節に適用しなければならず、このとき、各フィールドは１回以上現れて、各フィールドを単一のレンジ（範囲）として解釈することはできない。変換表は、論理積節の一部としてＯＲ演算を含む式を生成するとき、この節が追加の論理積節を生成することになる。新しい論理積節は、変換後に、ＯＲ演算を含む論理積節から導かなければいけない。これは、次の例で説明される：
オリジナルの論理積節
F = A != 5 AND A!= 7 AND A<8 AND B==10 - 
変換が適用された後の式
F = [(A < 5) OR  (A == 6)  OR  (A > 7)] AND A<8 AND B==10
F = [(A<5 AND A<8) OR (A==6 AND A<8) OR (A>7 AND A<8)] AND B==10 
F = [A<5 OR A==6] AND B==10
２つの別々の論理積節を有する最終的な式
F = (A<5 AND B==10) OR (A==6 AND B==10) 
【０１０３】
全ての論理積節の全ての項は、フィルタの重複解消を容易にするために、１つ以上の値のレンジ（範囲）として表現されなければならない。これを実現するため、表１１に記載された変換を適用しなければならない。
【０１０４】
【表１１】
2012178151.tif 000013
【０１０５】
注意書き：
１）この変換は、全てのフィルタ処理フィールドが、実際上、正の整数であるために可能である。
２）関係演算子「！＝」の変換のために、論理演算子ＯＲが再度現れることがあるため、表１０の次の段落に記載されたアルゴリズムを、式に再度適用しなければならない。
【０１０６】
先の箇条書きに記載した変換が適用されたら、フィルタ式が、別の論理積節で完全に表現された論理積節を含まないことを確認しなければならない。この場合、式から「サブ・セット」を完全に除去しなければならない。これは、サブ・セットが冗長と考えられるからである。
keys = { A, B, C, D }と仮定し、任意のｘについてAx ∈ A,  Bx ∈ B, Cx ∈ C, Dx ∈ Dとし、Ｆをフィルタ式とすると、
F = X OR Y  及び
X = [Ai,Aj] * [Bi,Bj] * [Ci,Cj] * [Di,Dj]]  及び
Y = [Ak,Al] * [Bk,Bl] * [Ck,Cl] * [Dk,Dl]
[Ai,Aj]が[Ak,Al]のサブ・セットであり、[Bi,Bj]が[Bk,Bl]のサブ・セットであり、[Ci,Cj]が[Ck,Cl]がサブ・セットであり、[Di,Dj]が[Dk,Dl]のサブ・セットである場合のみ、ＸはＹのサブ・セットと考えられる。もしＸがＹのサブ・セットなら、フィルタＦで生成される結果に影響を与えることなく、Ｘを式から除去可能である。
【０１０７】
ＤＮＦ式を複合ツリーに挿入
【０１０８】
この時点で、次のどれか１つに当てはまらない限り、フィルタをパトリシアにそのまま挿入することも可能ではある。
１）フィルタ・キーのサイズが、ツリーでサポートされる最大サイズを超える。又は、
２）異なる２ユーザが２つの異なるフィルタでネットワークをスヌープ（パケットをモニタ）している場合、１つ以上のフィルタ式を完全に分離されたフィルタに挿入しなければならない。
これら両条件はかなり良くあることなので、次の箇条書きで、これら問題にどのように取り組むべきか説明する。
【０１０９】
もしキーの合計サイズが、パトリシア・ツリーでサポートされる最大サイズ（ＮＰ３型の場合、３８バイト）を超える場合、２つの別々のツリーをフィルタ処理に使用できる。そうするためには、フィルタ式を重複しない論理積節だけを含む等価な式に変換しなければならない。言い換えると、
keys = { A, B, C, D }と仮定し、任意のｘについてAx ∈ A,  Bx ∈ B, Cx ∈ C, Dx ∈ Dとし、Ｘ及びＹが論理積節とすると：
X = [Ai,Aj] * [Bi,Bj] * [Ci,Cj] * [Di,Dj]]
Y = [Ak,Al] * [Bk,Bl] * [Ck,Cl] * [Dk,Dl]
[Ai,Aj]が[Ak,Al]と重複し、[Bi,Bj]が[Bk,Bl]と重複し、[Ci,Cj]が[Ck,Cl]と重複し、[Di,Dj]が[Dk,Dl]と重複する場合のみ、ＸとＹが重複すると考えられる。
【０１１０】
フィルタ式をＤＮＦ形式で２つの別々のツリーに挿入可能にするために、式を次の基準に合致する等価な形に変形しなければならない：
フィルタ式ＦがＤＮＦ形式であると仮定して、このとき
F = sum(Pi), for i= 0 to n, and 
Pi = [Ak,Al] * [Bk,Bl] * [Ck,Cl] * [Dk,Dl]
そして、Ｆ中の論理積節が、Ｆ中の他のどの論理積節とも重複しない。
【０１１１】
フィルタを分離できるようにするには、項情報をツリーに挿入しなければならない。これは、各フィルタ式で許される項の数を制限する。例えば、結果が９６バイトを含むＮＰ３型の場合、８個の異なるフィルタ・インスタンスをサポートするため、項の数は８８以下でなければならない。もし１６個の異なるフィルタ・インスタンスをサポートするなら、１つのフィルタ式当たりの項の数は半分に減少する。同様に、もし４フィルタ・インスタンスをスポートするなら、１つのフィルタ式当たりの項の数は２倍となる。
【０１１２】
フィルタを論理積節の重複のないＤＮＦ式に変形したら、次のセクションで説明するように、フィルタを複合ツリーに挿入できる。
【０１１３】
フィルタをＦ０とすると、
F0 = P1 + P2
Keys = { A, B, C, D } ここで任意のｘについてAx ∈ A,  Bx ∈ B, Cx ∈ C, Dx ∈ D
すると、
P1 = [Ai,Aj] * [Bi,Bj] * [Ci,Cj] * [Di,Dj]  及び
P2 = [Ak,Al] * [Bk,Bl] * [Ck,Cl] * [Dk,Dl]
【０１１４】
各論理積節Ｐｉには、式内で固有の識別子（ＩＤ）が与えられ、このＩＤは０とｎの間である。この式の場合、論理積節のＩＤはＰ０とＰ１である。加えて、式それ自身がシステム・ワイド固有ＩＤを有する。有効な値は、０とｍの間であり、ここでｍは典型的には小さな数である。
【０１１５】
Ａ及びＢがツリー１（Ｔ１）に所属し、Ｃ及びＤがツリー２（Ｔ２）に所属すると仮定する。Ｔ１中の各エントリは、次のものを含んでいる。
Ａ Ｂ 結果
[Ai,Aj]  [Bi,Bj]  F0,P1
[Ak,Al]  [Bk,Bl]  F0,P2
Ｔ２中の各エントリは、次のものを含んでいる。
Ｃ Ｄ 結果
[Ci,Cj]  [Di,Dj]  F0,P1 
[Ck,Cl]  [Dk,Dl]  F0,P2 
【０１１６】
Ｔ１の結果をＲ１、Ｔ２の結果をＲ２として、最終結果Ｒを次のように計算する：
R = R1 & R2
もしR != 0 なら、一致している。
【０１１７】
表１２は、Ｔ１及びＴ２について、あり得る結果を含んでいる。
【０１１８】
【表１２】
2012178151.tif 000014
【０１１９】
重複する論理積節を解消する
【０１２０】
重複する論理積節は、次のようにして解消できる。論理積節Ｐ１及びＰ２が異なるフィルタから得られると仮定する。このとき、
P1 = [Ai,Aj] * [Bi,Bj] * [Ci,Cj] * [Di,Dj]とし、結果= F1P1 (フィルタ１、論理積節１)
P2 = [Ak,Al] * [Bk,Bl] * [Ck,Cl] * [Dk,Dl] とし、結果= F2P2 (フィルタ２、論理積節１)
Ｐ１とＰ２の共通部分（intersection）を別々の論理積節としてＴ１及びＴ２に挿入できるように、共通部分を求めなければならない。共通部分は、Ｐ１及びＰ２の両方に関する結果情報を含んでいる。
【０１２１】
次のアルゴリズムを重複論理積節の解消に利用できる。
【０１２２】
１）[Ai,Aj]及び[Ak,Al]間の共通部分を決定する。
Aj = Ak + 2及びAi < Akと仮定する
[Ai,Aj]及び[Ak,Al]間の共通部分＝[Ak,Ak+2]と計算する
共通部分を用いて[Ai,Al]を表す重複のないグループを生成する：[Ai,Ak-1]、 [Ak,Ak+2]及び [Ak+3,Al]
以下を生成する
P1 = P11 or P12及び
P2 = P21 or P22  ここで
P11 = [Ai,Ak-1] * [Bi,Bj] * [Ci,Cj] * [Di,Dj]、結果F1P1
P12 = [Ak,Ak+2] * [Bi,Bj] * [Ci,Cj] * [Di,Dj]、結果F1P1
P21 = [Ak,Ak+2] * [Bk,Bl] * [Ck,Cl] * [Dk,Dl]、結果F2P1
P22 = [Ak+3,Al] * [Bk,Bl] * [Ck,Cl] * [Dk,Dl]、結果F2P1
【０１２３】
２）[Bi,Bj]及び[Bk,Bl]で同じ処理を繰り返す。
Bj = Bk + 2及びBi < Bkと仮定する
[Bi,Bj]及び [Bk,Bl]間の共通部分 = [Bk,Bk+2]と計算する
共通部分を用いた[Bi,Bl]を表す重複のないグループ：[Bi,Bk-1]、[Bk,Bk+2]及び[Bk+3,Bl]
以下を生成する
P1 = P111 or P112 or P121 or P122及び
P2 = P211 or P212 or P221 or P222、ここで
P111 = [Ai,Ak-1] * [Bi,Bk-1] * [Ci,Cj] * [Di,Dj]、結果F1P1
P112 = [Ai,Ak-1] * [Bk,Bk+2] * [Ci,Cj] * [Di,Dj]、結果F1P1
P121 = [Ak,Ak+2] * [Bi,Bk-1] * [Ci,Cj] * [Di,Dj]、結果F1P1
P122 = [Ak,Ak+2] * [Bk,Bk+2] * [Ci,Cj] * [Di,Dj]、結果F1P1
P211 = [Ak,Ak+2] * [Bk,Bk+2] * [Ck,Cl] * [Dk,Dl]、結果F2P1
P212 = [Ak,Ak+2] * [Bk+3,Bl] * [Ck,Cl] * [Dk,Dl]、結果F2P1
P221 = [Ak+3,Al] * [Bk,Bk+2] * [Ck,Cl] * [Dk,Dl]、結果F2P1
P222 = [Ak+3,Al] * [Bk+3,Bl] * [Ck,Cl] * [Dk,Dl]、結果F2P1
【０１２４】
３）[Ci,Cj]及び[Ck,Cl] で同じ処理を繰り返す。
Cj = Ck + 2及びCi < Ckと仮定する
[Ci,Cj]及び[Ck,Cl]間の共通部分 = [Ck,Ck+2]と計算する
共通部分を用いた[Ci,Cl]を表す重複のないグループ：[Ci,Ck-1], [Ck,Ck+2]及び[Ck+3,Cl]
以下を生成する
P1 = P1111 or P1112 or P1121 or P1122 or P1211 or P1212 or P1221 or P1222及び
P2 = P2111 or P2112 or P2121 or P2122 or P2211 or P2212 or P2221 or P2222  ここで
P1111 = [Ai,Ak-1] * [Bi,Bk-1] * [Ci,Ck-1] * [Di,Dj]、結果F1P1
P1112 = [Ai,Ak-1] * [Bi,Bk-1] * [Ck,Ck+2] * [Di,Dj]、結果F1P1
P1121 = [Ai,Ak-1] * [Bk,Bk+2] * [Ci,Ck-1] * [Di,Dj]、結果F1P1
P1122 = [Ai,Ak-1] * [Bk,Bk+2] * [Ck,Ck+2] * [Di,Dj]、結果F1P1
P1211 = [Ak,Ak+2] * [Bi,Bk-1] * [Ci,Ck-1] * [Di,Dj]、結果F1P1
P1212 = [Ak,Ak+2] * [Bi,Bk-1] * [Ck,Ck+2] * [Di,Dj]、結果F1P1
P1221 = [Ak,Ak+2] * [Bk,Bk+2] * [Ci,Ck-1] * [Di,Dj]、結果F1P1
P1222 = [Ak,Ak+2] * [Bk,Bk+2] * [Ck,Ck+2] * [Di,Dj]、結果F1P1
P2111 = [Ak,Ak+2] * [Bk,Bk+2] * [Ck,Ck+2] * [Dk,Dl]、結果F2P1
P2112 = [Ak,Ak+2] * [Bk,Bk+2] * [Ck+3,Cl] * [Dk,Dl]、結果F2P1
P2121 = [Ak,Ak+2] * [Bk+3,Bl] * [Ck,Ck+2] * [Dk,Dl]、結果F2P1
P2122 = [Ak,Ak+2] * [Bk+3,Bl] * [Ck+3,Cl] * [Dk,Dl]、結果F2P1
P2211 = [Ak+3,Al] * [Bk,Bk+2] * [Ck,Ck+2] * [Dk,Dl]、結果F2P1
P2212 = [Ak+3,Al] * [Bk,Bk+2] * [Ck+3,Cl] * [Dk,Dl]、結果F2P1
P2221 = [Ak+3,Al] * [Bk+3,Bl] * [Ck,Ck+2] * [Dk,Dl]、結果F2P1
P2222 = [Ak+3,Al] * [Bk+3,Bl] * [Ck+3,Cl] * [Dk,Dl]、結果F2P1
【０１２５】
４）[Di,Dj]及び [Dk,Dl]で同じ処理を繰り返す。
Dj = Dk + 2及びDi < Dkと仮定する。
[Di,Dj]及び[Dk,Dl]間の共通部分 = [Dk,Dk+2]と計算する
共通部分を用いた[Di,Dl]を表す重複のないグループ：[Di,Dk-1], [Dk,Dk+2]及び[Dk+3,Dl]
以下を生成する
P1 = P11111 or P11112 or P11121 or P11122 or P11211 or P11212 or P11221 or P11222 or
P12111 or P12112 or P12121 or P12122 or P12211 or P12212 or P12221 or P12222及び
P2 = P21111 or P21112 or P21121 or P21122 or P21211 or P21212 or P21221 or P21222 or P22111 or P22112 or P22121 or P22122 or P22211 or P22212 or P22221 or P22222  ここで
P11111 = [Ai,Ak-1] * [Bi,Bk-1] * [Ci,Ck-1] * [Di,Dk-1]、結果F1P1
P11112 = [Ai,Ak-1] * [Bi,Bk-1] * [Ci,Ck-1] * [Dk,Dk+2]、結果F1P1
P11121 = [Ai,Ak-1] * [Bi,Bk-1] * [Ck,Ck+2] * [Di,Dk-1]、結果F1P1
P11122 = [Ai,Ak-1] * [Bi,Bk-1] * [Ck,Ck+2] * [Dk,Dk+2]、結果F1P1
P11211 = [Ai,Ak-1] * [Bk,Bk+2] * [Ci,Ck-1] * [Di,Dk-1]、結果F1P1
P11212 = [Ai,Ak-1] * [Bk,Bk+2] * [Ci,Ck-1] * [Dk,Dk+2]、結果F1P1
P11221 = [Ai,Ak-1] * [Bk,Bk+2] * [Ck,Ck+2] * [Di,Dk-1]、結果F1P1
P11222 = [Ai,Ak-1] * [Bk,Bk+2] * [Ck,Ck+2] * [Dk,Dk+2]、結果F1P1
P12111 = [Ak,Ak+2] * [Bi,Bk-1] * [Ci,Ck-1] * [Di,Dk-1]、結果F1P1
P12112 = [Ak,Ak+2] * [Bi,Bk-1] * [Ci,Ck-1] * [Dk,Dk+2]、結果F1P1
P12121 = [Ak,Ak+2] * [Bi,Bk-1] * [Ck,Ck+2] * [Di,Dk-1]、結果F1P1
P12122 = [Ak,Ak+2] * [Bi,Bk-1] * [Ck,Ck+2] * [Dk,Dk+2]、結果F1P1
P12211 = [Ak,Ak+2] * [Bk,Bk+2] * [Ci,Ck-1] * [Di,Dk-1]、結果F1P1
P12212 = [Ak,Ak+2] * [Bk,Bk+2] * [Ci,Ck-1] * [Dk,Dk+2]、結果F1P1
P12221 = [Ak,Ak+2] * [Bk,Bk+2] * [Ck,Ck+2] * [Di,Dk-1]、結果F1P1
P12222 = [Ak,Ak+2] * [Bk,Bk+2] * [Ck,Ck+2] * [Dk,Dk+2]、結果F1P1
P21111 = [Ak,Ak+2] * [Bk,Bk+2] * [Ck,Ck+2] * [Dk,Dk+2]、結果F2P1
P21112 = [Ak,Ak+2] * [Bk,Bk+2] * [Ck,Ck+2] * [Dk+3,Dl]、結果F2P1
P21121 = [Ak,Ak+2] * [Bk,Bk+2] * [Ck+3,Cl] * [Dk,Dk+2]、結果F2P1
P21122 = [Ak,Ak+2] * [Bk,Bk+2] * [Ck+3,Cl] * [Dk+3,Dl]、結果F2P1
P21211 = [Ak,Ak+2] * [Bk+3,Bl] * [Ck,Ck+2] * [Dk,Dk+2]、結果F2P1
P21212 = [Ak,Ak+2] * [Bk+3,Bl] * [Ck,Ck+2] * [Dk+3,Dl]、結果F2P1
P21221 = [Ak,Ak+2] * [Bk+3,Bl] * [Ck+3,Cl] * [Dk,Dk+2]、結果F2P1
P21222 = [Ak,Ak+2] * [Bk+3,Bl] * [Ck+3,Cl] * [Dk+3,Dl]、結果F2P1
P22111 = [Ak+3,Al] * [Bk,Bk+2] * [Ck,Ck+2] * [Dk,Dk+2]、結果F2P1
P22112 = [Ak+3,Al] * [Bk,Bk+2] * [Ck,Ck+2] * [Dk+3,Dl]、結果F2P1
P22121 = [Ak+3,Al] * [Bk,Bk+2] * [Ck+3,Cl] * [Dk,Dk+2]、結果F2P1
P22122 = [Ak+3,Al] * [Bk,Bk+2] * [Ck+3,Cl] * [Dk+3,Dl]、結果F2P1
P22211 = [Ak+3,Al] * [Bk+3,Bl] * [Ck,Ck+2] * [Dk,Dk+2]、結果F2P1
P22212 = [Ak+3,Al] * [Bk+3,Bl] * [Ck,Ck+2] * [Dk+3,Dl]、結果F2P1
P22221 = [Ak+3,Al] * [Bk+3,Bl] * [Ck+3,Cl] * [Dk,Dk+2]、結果F2P1
P22222 = [Ak+3,Al] * [Bk+3,Bl] * [Ck+3,Cl] * [Dk+3,Dl]、結果F2P1
【０１２６】
５）Ｐ１及びＰ２間の共通部分を特定する。この共通部分は、Ｐ１及びＰ２の両方に存在する論理積節である。この例では、P12222及びP21111が同一なので、これらが共通部分を表し、よってこれらの結果を組み合わせることができる。
以下を生成する
P3 = P12222、結果F1P1 F2P1
P1-P3 = P11111 or P11112 or P11121 or P11122 or P11211 or P11212 or P11221 or P11222 or P12111 or P12112 or P12121 or P12122 or P12211 or P12212 or P12221 及び
P2-P3 = P21112 or P21121 or P21122 or P21211 or P21212 or P21221 or P21222 or P22111 or P22112 or P22121 or P22122 or P22211 or P22212 or P22221 or P22222  ここで
P11111 = [Ai,Ak-1] * [Bi,Bk-1] * [Ci,Ck-1] * [Di,Dk-1]、結果F1P1
P11112 = [Ai,Ak-1] * [Bi,Bk-1] * [Ci,Ck-1] * [Dk,Dk+2]、結果F1P1
P11121 = [Ai,Ak-1] * [Bi,Bk-1] * [Ck,Ck+2] * [Di,Dk-1]、結果F1P1
P11122 = [Ai,Ak-1] * [Bi,Bk-1] * [Ck,Ck+2] * [Dk,Dk+2]、結果F1P1
P11211 = [Ai,Ak-1] * [Bk,Bk+2] * [Ci,Ck-1] * [Di,Dk-1]、結果F1P1
P11212 = [Ai,Ak-1] * [Bk,Bk+2] * [Ci,Ck-1] * [Dk,Dk+2]、結果F1P1
P11221 = [Ai,Ak-1] * [Bk,Bk+2] * [Ck,Ck+2] * [Di,Dk-1]、結果F1P1
P11222 = [Ai,Ak-1] * [Bk,Bk+2] * [Ck,Ck+2] * [Dk,Dk+2]、結果F1P1
P12111 = [Ak,Ak+2] * [Bi,Bk-1] * [Ci,Ck-1] * [Di,Dk-1]、結果F1P1
P12112 = [Ak,Ak+2] * [Bi,Bk-1] * [Ci,Ck-1] * [Dk,Dk+2]、結果F1P1
P12121 = [Ak,Ak+2] * [Bi,Bk-1] * [Ck,Ck+2] * [Di,Dk-1]、結果F1P1
P12122 = [Ak,Ak+2] * [Bi,Bk-1] * [Ck,Ck+2] * [Dk,Dk+2]、結果F1P1
P12211 = [Ak,Ak+2] * [Bk,Bk+2] * [Ci,Ck-1] * [Di,Dk-1]、結果F1P1
P12212 = [Ak,Ak+2] * [Bk,Bk+2] * [Ci,Ck-1] * [Dk,Dk+2]、結果F1P1
P12221 = [Ak,Ak+2] * [Bk,Bk+2] * [Ck,Ck+2] * [Di,Dk-1]、結果F1P1
P12222 = [Ak,Ak+2] * [Bk,Bk+2] * [Ck,Ck+2] * [Dk,Dk+2]、結果F1P1 F2P1
P21112 = [Ak,Ak+2] * [Bk,Bk+2] * [Ck,Ck+2] * [Dk+3,Dl]、結果F2P1
P21121 = [Ak,Ak+2] * [Bk,Bk+2] * [Ck+3,Cl] * [Dk,Dk+2]、結果F2P1
P21122 = [Ak,Ak+2] * [Bk,Bk+2] * [Ck+3,Cl] * [Dk+3,Dl]、結果F2P1
P21211 = [Ak,Ak+2] * [Bk+3,Bl] * [Ck,Ck+2] * [Dk,Dk+2]、結果F2P1
P21212 = [Ak,Ak+2] * [Bk+3,Bl] * [Ck,Ck+2] * [Dk+3,Dl]、結果F2P1
P21221 = [Ak,Ak+2] * [Bk+3,Bl] * [Ck+3,Cl] * [Dk,Dk+2]、結果F2P1
P21222 = [Ak,Ak+2] * [Bk+3,Bl] * [Ck+3,Cl] * [Dk+3,Dl]、結果F2P1
P22111 = [Ak+3,Al] * [Bk,Bk+2] * [Ck,Ck+2] * [Dk,Dk+2]、結果F2P1
P22112 = [Ak+3,Al] * [Bk,Bk+2] * [Ck,Ck+2] * [Dk+3,Dl]、結果F2P1
P22121 = [Ak+3,Al] * [Bk,Bk+2] * [Ck+3,Cl] * [Dk,Dk+2]、結果F2P1
P22122 = [Ak+3,Al] * [Bk,Bk+2] * [Ck+3,Cl] * [Dk+3,Dl]、結果F2P1
P22211 = [Ak+3,Al] * [Bk+3,Bl] * [Ck,Ck+2] * [Dk,Dk+2]、結果F2P1
P22212 = [Ak+3,Al] * [Bk+3,Bl] * [Ck,Ck+2] * [Dk+3,Dl]、結果F2P1
P22221 = [Ak+3,Al] * [Bk+3,Bl] * [Ck+3,Cl] * [Dk,Dk+2]、結果F2P1
P22222 = [Ak+3,Al] * [Bk+3,Bl] * [Ck+3,Cl] * [Dk+3,Dl]、結果F2P1
【０１２７】
６）共通部分が特定され、オリジナルの論理積節から除去されたら、拡張された論理積節を可能な限り減少させなければならない。キー拡張[Di,Dj]及び [Dk,Dl]の最後のグループから始めて、重複について全ての論理積節をチェックし、可能であれば組み合わせる。
以下を生成する
P3 = P12222、結果F1P1 F2P1及び
P1-P3 = P1111 or P1112 or P1121 or P1122 or P1211 or P1212 or P1221 or P12221及び
P2-P3 = P21112 or P2112 or P2121 or P2122 or P2211 or P2212 or P2221 or P2222  ここで
P1111 = [Ai,Ak-1] * [Bi,Bk-1] * [Ci,Ck-1] * [Di,Dk+2]、結果F1P1
P1112 = [Ai,Ak-1] * [Bi,Bk-1] * [Ck,Ck+2] * [Di,Dk+2]、結果F1P1
P1121 = [Ai,Ak-1] * [Bk,Bk+2] * [Ci,Ck-1] * [Di,Dk+2]、結果F1P1
P1122 = [Ai,Ak-1] * [Bk,Bk+2] * [Ck,Ck+2] * [Di,Dk+2]、結果F1P1
P1211 = [Ak,Ak+2] * [Bi,Bk-1] * [Ci,Ck-1] * [Di,Dk+2]、結果F1P1
P1212 = [Ak,Ak+2] * [Bi,Bk-1] * [Ck,Ck+2] * [Di,Dk+2]、結果F1P1
P1221 = [Ak,Ak+2] * [Bk,Bk+2] * [Ci,Ck-1] * [Di,Dk+2]、結果F1P1
P12221 = [Ak,Ak+2] * [Bk,Bk+2] * [Ck,Ck+2] * [Di,Dk-1]、結果F1P1
P12222 = [Ak,Ak+2] * [Bk,Bk+2] * [Ck,Ck+2] * [Dk,Dk+2]、結果F1P1 F2P1
P21112 = [Ak,Ak+2] * [Bk,Bk+2] * [Ck,Ck+2] * [Dk+3,Dl]、結果F2P1
P2112 = [Ak,Ak+2] * [Bk,Bk+2] * [Ck+3,Cl] * [Dk,Dl]、結果F2P1
P2121 = [Ak,Ak+2] * [Bk+3,Bl] * [Ck,Ck+2] * [Dk,Dl]、結果F2P1
P2122 = [Ak,Ak+2] * [Bk+3,Bl] * [Ck+3,Cl] * [Dk,Dl]、結果F2P1
P2211 = [Ak+3,Al] * [Bk,Bk+2] * [Ck,Ck+2] * [Dk,Dl]、結果F2P1
P2212 = [Ak+3,Al] * [Bk,Bk+2] * [Ck+3,Cl] * [Dk,Dl]、結果F2P1
P2221 = [Ak+3,Al] * [Bk+3,Bl] * [Ck,Ck+2] * [Dk,Dl]、結果F2P1
P2222 = [Ak+3,Al] * [Bk+3,Bl] * [Ck+3,Cl] * [Dk,Dl]、結果F2P1
【０１２８】
７）キー拡張[Ci,Cj] 及び [Ck,Cl]の次のグループについて、処理を続ける。重複について全ての論理積節をチェックし、可能であれば組み合わせる。
以下を生成する。
P3 = P12222、結果F1P1 F2P1及び
P1-P3 = P111 or P112 or P121 or P1221 or P12221及び
P2-P3 = P21112 or P2112 or P212 or P221 or P222  ここで
P111 = [Ai,Ak-1] * [Bi,Bk-1] * [Ci,Ck+2] * [Di,Dk+2]、結果F1P1
P112 = [Ai,Ak-1] * [Bk,Bk+2] * [Ci,Ck+2] * [Di,Dk+2]、結果F1P1
P121 = [Ak,Ak+2] * [Bi,Bk-1] * [Ci,Ck+2] * [Di,Dk+2]、結果F1P1
P1221 = [Ak,Ak+2] * [Bk,Bk+2] * [Ci,Ck-1] * [Di,Dk+2]、結果F1P1
P12221 = [Ak,Ak+2] * [Bk,Bk+2] * [Ck,Ck+2] * [Di,Dk-1]、結果F1P1
P12222 = [Ak,Ak+2] * [Bk,Bk+2] * [Ck,Ck+2] * [Dk,Dk+2]、結果F1P1 F2P1
P21112 = [Ak,Ak+2] * [Bk,Bk+2] * [Ck,Ck+2] * [Dk+3,Dl]、結果F2P1
P2112 = [Ak,Ak+2] * [Bk,Bk+2] * [Ck+3,Cl] * [Dk,Dl]、結果F2P1
P212 = [Ak,Ak+2] * [Bk+3,Bl] * [Ck,Cl] * [Dk,Dl]、結果F2P1
P221 = [Ak+3,Al] * [Bk,Bk+2] * [Ck,Cl] * [Dk,Dl]、結果F2P1
P222 = [Ak+3,Al] * [Bk+3,Bl] * [Ck,Cl] * [Dk,Dl]、結果F2P1
【０１２９】
８）キー拡張[Bi,Bj]及び [Bk,Bl]の次のグループについて、処理を続ける。重複について全ての論理積節をチェックし、可能であれば組み合わせる。
以下を生成する。
P3 = P12222、結果F1P1 F2P1、
P1-P3 = P11 or P121 or P1221 or P12221及び
P2-P3 = P21112 or P2112 or P212 or P22  ここで
P11 = [Ai,Ak-1] * [Bi,Bk+2] * [Ci,Ck+2] * [Di,Dk+2]、結果F1P1
P121 = [Ak,Ak+2] * [Bi,Bk-1] * [Ci,Ck+2] * [Di,Dk+2]、結果F1P1
P1221 = [Ak,Ak+2] * [Bk,Bk+2] * [Ci,Ck-1] * [Di,Dk+2]、結果F1P1
P12221 = [Ak,Ak+2] * [Bk,Bk+2] * [Ck,Ck+2] * [Di,Dk-1]、結果F1P1
P12222 = [Ak,Ak+2] * [Bk,Bk+2] * [Ck,Ck+2] * [Dk,Dk+2]、結果F1P1 F2P1
P21112 = [Ak,Ak+2] * [Bk,Bk+2] * [Ck,Ck+2] * [Dk+3,Dl]、結果F2P1
P2112 = [Ak,Ak+2] * [Bk,Bk+2] * [Ck+3,Cl] * [Dk,Dl]、結果F2P1
P212 = [Ak,Ak+2] * [Bk+3,Bl] * [Ck,Cl] * [Dk,Dl]、結果F2P1
P22 = [Ak+3,Al] * [Bk,Bl] * [Ck,Cl] * [Dk,Dl]、結果F2P1
【０１３０】
９）キー拡張[Ai,Aj]及び [Ak,Al].の次のグループについて、処理を続ける。重複について全ての論理積節をチェックし、可能であれば組み合わせる。この時点で、複数の式をこれ以上組み合わせることはできない。
【０１３１】
１０）最終の式：
P1-P3 = P11 or P121 or P1221 or P12221
P2-P3 = P21112 or P2112 or P212 or P22
P3 = P12222、結果F1P1 F2P1
P11 = [Ai,Ak-1] * [Bi,Bk+2] * [Ci,Ck+2] * [Di,Dk+2]、結果F1P1
P121 = [Ak,Ak+2] * [Bi,Bk-1] * [Ci,Ck+2] * [Di,Dk+2]、結果F1P1
P1221 = [Ak,Ak+2] * [Bk,Bk+2] * [Ci,Ck-1] * [Di,Dk+2]、結果F1P1
P12221 = [Ak,Ak+2] * [Bk,Bk+2] * [Ck,Ck+2] * [Di,Dk-1]、結果F1P1
P12222 = [Ak,Ak+2] * [Bk,Bk+2] * [Ck,Ck+2] * [Dk,Dk+2]、結果F1P1 F2P1
P21112 = [Ak,Ak+2] * [Bk,Bk+2] * [Ck,Ck+2] * [Dk+3,Dl]、結果F2P1
P2112 = [Ak,Ak+2] * [Bk,Bk+2] * [Ck+3,Cl] * [Dk,Dl]、結果F2P1
P212 = [Ak,Ak+2] * [Bk+3,Bl] * [Ck,Cl] * [Dk,Dl]、結果F2P1
P22 = [Ak+3,Al] * [Bk,Bl] * [Ck,Cl] * [Dk,Dl]、結果F2P1
【０１３２】
コンセプトの立証
【０１３３】
コンセプトの立証として、次の証明ができる。
P1 = [Ai,Aj] * [Bi,Bj] * [Ci,Cj] * [Di,Dj]とすると、結果= F1P1 (フィルタ１, 論理積節１)
P2 = [Ak,Al] * [Bk,Bl] * [Ck,Cl] * [Dk,Dl] とすると、結果= F2P1 (フィルタ２, 論理積節１)
が次に等しい。
P1-P3 = P11 or P121 or P1221 or P12221、結果F1P1 (フィルタ１, 論理積節１)
P2-P3 = P21112 or P2112 or P212 or P22、結果F2P1 (フィルタ２, 論理積節１)
P3 = P12222、結果F1P1 F2P1 (フィルタ１ 論理積節１ 及びフィルタ２ 論理積節１)
【０１３４】
Aj = Ak + 2
Bj = Bk + 2
Cj = Ck + 2
Dj = Dk + 2
とおくと、
P11 = [Ai,Ak-1] * [Bi,Bk+2] * [Ci,Ck+2] * [Di,Dk+2]、結果F1P1
P121 = [Ak,Ak+2] * [Bi,Bk-1] * [Ci,Ck+2] * [Di,Dk+2]、結果F1P1
P1221 = [Ak,Ak+2] * [Bk,Bk+2] * [Ci,Ck-1] * [Di,Dk+2]、結果F1P1
P12221 = [Ak,Ak+2] * [Bk,Bk+2] * [Ck,Ck+2] * [Di,Dk-1]、結果F1P1
P12222 = [Ak,Ak+2] * [Bk,Bk+2] * [Ck,Ck+2] * [Dk,Dk+2]、結果F1P1 F2P1
P21112 = [Ak,Ak+2] * [Bk,Bk+2] * [Ck,Ck+2] * [Dk+3,Dl]、結果F2P1
P2112 = [Ak,Ak+2] * [Bk,Bk+2] * [Ck+3,Cl] * [Dk,Dl]、結果F2P1
P212 = [Ak,Ak+2] * [Bk+2,Bl] * [Ck,Cl] * [Dk,Dl]、結果F2P1
P22 = [Ak+3,Al] * [Bk,Bl] * [Ck,Cl] * [Dk,Dl]、結果F2P1
【０１３５】
１）P1 = (P1-P3) + P3を証明する。
[Ai,Aj] * [Bi,Bj] * [Ci,Cj] * [Di,Dj]、結果F1P1 =
P11 = [Ai,Aj-3] * [Bi,Bj] * [Ci,Cj] * [Di,Dj]、結果F1P1
P121 = [Aj-2,Aj] * [Bi,Bj-3] * [Ci,Cj] * [Di,Dj]、結果F1P1
P1221 = [Aj-2,Aj] * [Bj-2,Bj] * [Ci,Cj-3] * [Di,Dj]、結果F1P1
P12221 = [Aj-2,Aj] * [Bj-2,Bj] * [Cj-2,j] * [Di,Dj-3]、結果F1P1
P3 = P12222 = [Ak,Ak+2] * [Bk,Bk+2] * [Ck,Ck+2] * [Dk,Dk+2]、結果F1P1
【０１３６】
次の通りとする。
Aj = Ak + 2
Bj = Bk + 2
Cj = Ck + 2
Dj = Dk + 2
P3 = P12222 = [Aj-2,Aj] * [Bj-2,Bj] * [Cj-2,Cj] * [Dj-2,Dj]、結果F1P1
【０１３７】
[Di,Dj]から始めて、上述と同じ削減アルゴリズムを適用する：
P11 = [Ai,Aj-3] * [Bi,Bj] * [Ci,Cj] * [Di,Dj]、結果F1P1
P121 = [Aj-2,Aj] * [Bi,Bj-3] * [Ci,Cj] * [Di,Dj]、結果F1P1
P1221 = [Aj-2,Aj] * [Bj-2,Bj] * [Ci,Cj-3] * [Di,Dj]、結果F1P1
P1222 = [Aj-2,Aj] * [Bj-2,Bj] * [Cj-2,j] * [Di,Dj]、結果F1P1
【０１３８】
[Ci,Cj]について続ける：
P11 = [Ai,Aj-3] * [Bi,Bj] * [Ci,Cj] * [Di,Dj]、結果F1P1
P121 = [Aj-2,Aj] * [Bi,Bj-3] * [Ci,Cj] * [Di,Dj]、結果F1P1
P122 = [Aj-2,Aj] * [Bj-2,Bj] * [Ci,Cj] * [Di,Dj]、結果F1P1
【０１３９】
[Bi,Bj]について続ける：
P11 = [Ai,Aj-3] * [Bi,Bj] * [Ci,Cj] * [Di,Dj]、結果F1P1
P12 = [Aj-2,Aj] * [Bi,Bj] * [Ci,Cj] * [Di,Dj]、結果F1P1
【０１４０】
[Ai,Aj]で終える：
P1 = [Ai,Aj] * [Bi,Bj] * [Ci,Cj] * [Di,Dj]、結果F1P1
【０１４１】
２）P2 = (P2-P3) + P3を証明する。
P2 = [Ak,Al] * [Bk,Bl] * [Ck,Cl] * [Dk,Dl]、結果F2P1 =
P3 = P21111 = [Ak,Ak+2] * [Bk,Bk+2] * [Ck,Ck+2] * [Dk,Dk+2]、結果F2P1
P21112 = [Ak,Ak+2] * [Bk,Bk+2] * [Ck,Ck+2] * [Dk+3,Dl]、結果F2P1
P2112 = [Ak,Ak+2] * [Bk,Bk+2] * [Ck+3,Cl] * [Dk,Dl]、結果F2P1
P212 = [Ak,Ak+2] * [Bk+3,Bl] * [Ck,Cl] * [Dk,Dl]、結果F2P1
P22 = [Ak+3,Al] * [Bk,Bl] * [Ck,Cl] * [Dk,Dl]、結果F2P1
【０１４２】
[Dk,Dl]から始めて、上述と同じ削減アルゴリズムを適用する：
P2111 = [Ak,Ak+2] * [Bk,Bk+2] * [Ck,Ck+2] * [Dk,Dl]、結果F2P1
P2112 = [Ak,Ak+2] * [Bk,Bk+2] * [Ck+3,Cl] * [Dk,Dl]、結果F2P1
P212 = [Ak,Ak+2] * [Bk+3,Bl] * [Ck,Cl] * [Dk,Dl]、結果F2P1
P22 = [Ak+3,Al] * [Bk,Bl] * [Ck,Cl] * [Dk,Dl]、結果F2P1
【０１４３】
[Ck,Cl]について続ける：
P211 = [Ak,Ak+2] * [Bk,Bk+2] * [Ck,Cl] * [Dk,Dl]、結果F2P1
P212 = [Ak,Ak+2] * [Bk+3,Bl] * [Ck,Cl] * [Dk,Dl]、結果F2P1
P22 = [Ak+3,Al] * [Bk,Bl] * [Ck,Cl] * [Dk,Dl]、結果F2P1
【０１４４】
[Bk,Bl] について続ける：
P21 = [Ak,Ak+2] * [Bk,Bl] * [Ck,Cl] * [Dk,Dl]、結果F2P1
P22 = [Ak+3,Al] * [Bk,Bl] * [Ck,Cl] * [Dk,Dl]、結果F2P1
【０１４５】
[Ak,Al]で終える:
P2 = [Ak,Al] * [Bk,Bl] * [Ck,Cl] * [Dk,Dl]、結果F2P1
【０１４６】
当業者であれば、上述の説明及び関連図面に示した本発明の技術的な利点を有する発明の多数の変形及び他の実施形態を思いつくであろう。従って、本発明は、開示した特定の実施形態に限定されないことが理解されよう。本願では特定の用語を用いたが、一般的で説明的な意味で用いたもので、限定を意味するものではない。
【符号の説明】
【０１４７】
１０１  ノード１
１０２  ノード２
１０３  インタフェース
１０４  フィルタ
１０５  モニタリング・デバイス
２００  バイナリ・ツリー
２０１〜２１１  ノード
【図１】
2012178151.tif 000015
【図２】
2012178151.tif 000016
【図３】
2012178151.tif 000017
【外国語明細書】
2012178151.tif 000018
2012178151.tif 000019
2012178151.tif 000020
2012178151.tif 000021
2012178151.tif 000022
2012178151.tif 000023
2012178151.tif 000024
2012178151.tif 000025
2012178151.tif 000026
2012178151.tif 000027
2012178151.tif 000028
2012178151.tif 000029
2012178151.tif 000030
2012178151.tif 000031
2012178151.tif 000032
2012178151.tif 000033
2012178151.tif 000034
2012178151.tif 000035
2012178151.tif 000036
2012178151.tif 000037
2012178151.tif 000038
2012178151.tif 000039
2012178151.tif 000040
2012178151.tif 000041
2012178151.tif 000042
2012178151.tif 000043
2012178151.tif 000044
2012178151.tif 000045
2012178151.tif 000046
2012178151.tif 000047
2012178151.tif 000048
2012178151.tif 000049
2012178151.tif 000050
2012178151.tif 000051
2012178151.tif 000052
2012178151.tif 000053
2012178151.tif 000054
2012178151.tif 000055
2012178151.tif 000056
2012178151.tif 000057
2012178151.tif 000058