(57)【要約】  本発明は、パケット分類決定木を確立するための方法および装置を提供する。前記方法の一例示によると、分類ルールセットの非テンプレートディメンションに基づいて、前記分類ルールセットに対して決定木を作成し、第１タイプ決定木を生成し、前記分類ルールセットのテンプレートディメンションに基づいて、前記第１タイプ決定木における葉ノードのそれぞれに対して決定木を作成し、第２タイプ決定木を生成し、前記第１タイプ決定木における互いに同パターンサブルールセットとなる複数の葉ノードを同一の第２タイプ決定木に関連付けさせる。前記互いに同パターンサブルールセットとなる複数の葉ノードは、前記複数の葉ノードのそれぞれに含まれる分類ルールのセットが互いに同パターンサブルールセットとなることを意味する。
2020532241.tif 000002
【特許請求の範囲】
【請求項１】
パケット分類決定木確立方法であって、
分類ルールセットの非テンプレートディメンションに基づいて、前記分類ルールセットに対して決定木を作成し、第１タイプ決定木を生成することと、
前記分類ルールセットのテンプレートディメンションに基づいて、前記第１タイプ決定木における葉ノードのそれぞれに対して決定木を作成し、第２タイプ決定木を生成することと、
前記第１タイプ決定木における互いに同パターンサブルールセットとなる複数の葉ノードを同一の第２タイプ決定木に関連付けさせることと、を含み、
前記互いに同パターンサブルールセットとなる複数の葉ノードは、前記複数の葉ノードのそれぞれに含まれる分類ルールのセットが互いに同パターンサブルールセットとなることを意味することを特徴とするパケット分類決定木確立方法。
【請求項２】
前記非テンプレートディメンションに基づいて、前記分類ルールセットに対して決定木を作成することは、
前記非テンプレートディメンションおよび対応する値が前記分類ルールセットにおける分類ルールにマッチングしないとき、分類ルールにマッチングしない葉ノードに含まれる分類ルールをホールフィリングルールとして設定することを含み、
前記ホールフィリングルールの優先度は、前記分類ルールセットにおける各分類ルールの優先度より低いことを特徴とする請求項１に記載のパケット分類決定木確立方法。
【請求項３】
互いに同パターンサブルールセットとなる複数の分類ルールサブセットを含む葉ノードが前記第１タイプ決定木に存在するとき、前記葉ノードに含まれる低優先度の分類ルールサブセットを削除することを更に含むことを特徴とする請求項１に記載のパケット分類決定木確立方法。
【請求項４】
前記第１タイプ決定木における互いに同パターンサブルールセットとなる複数の葉ノードを同一の第２タイプ決定木に関連付けさせることは、
前記複数の葉ノードに含まれる互いに同パターンサブルールセットとなる複数の分類ルールサブセットを同一の同パターンサブルールセット群に区分することと、
前記複数の葉ノードの各葉ノードに対して、当該葉ノードと、当該同パターンサブルールセット群の識別子、および、当該葉ノードに含まれる分類ルールサブセットの、当該同パターンサブルールセット群におけるインデックスとの間のマッピング関係を確立することと、
前記複数の葉ノードのそれぞれに対応する前記第２タイプ決定木を１つの第２タイプ決定木として合併することと、を含み、
前記合併された第２タイプ決定木の葉ノードは、当該同パターンサブルールセット群における各分類ルールを含むことを特徴とする請求項１に記載のパケット分類決定木確立方法。
【請求項５】
前記第１タイプ決定木を検索することにより、分類すべきパケットに対応する、前記第１タイプ決定木における第１対象葉ノードを特定することと、
前記第１対象葉ノードに記憶される同パターンサブルールセット群の識別子に基づいて対象第２タイプ決定木を特定することと、
前記対象第２タイプ決定木を検索することにより、前記分類すべきパケットに対応する、前記対象第２タイプ決定木における第２対象葉ノードを特定することと、
前記第１対象葉ノードに記憶される同パターンサブルールセット群におけるインデックスに基づいて、対応する分類ルールを前記第２対象葉ノードから検索することと、
当該検索された分類ルールを前記分類すべきパケットにマッチングする分類ルールとして特定することと、を更に含むことを特徴とする請求項４に記載のパケット分類決定木確立方法。
【請求項６】
パケット分類決定木確立装置であって、
分類ルールセットの非テンプレートディメンションに基づいて、前記分類ルールセットに対して決定木を作成し、第１タイプ決定木を生成するための第１決定木作成手段と、
前記分類ルールセットのテンプレートディメンションに基づいて、前記第１タイプ決定木における葉ノードのそれぞれに対して決定木を作成し、第２タイプ決定木を生成するための第２決定木作成と、
前記第１タイプ決定木における互いに同パターンサブルールセットとなる複数の葉ノードを同一の第２タイプ決定木に関連付けさせるための多重化手段と、を備え、
前記互いに同パターンサブルールセットとなる複数の葉ノードは、前記複数の葉ノードのそれぞれに含まれる分類ルールのセットが互いに同パターンサブルールセットとなることを意味することを特徴とするパケット分類決定木確立装置。
【請求項７】
前記第１決定木作成手段は、更に、
前記非テンプレートディメンションおよび対応する値が前記分類ルールセットにおける分類ルールにマッチングしないとき、分類ルールにマッチングしない葉ノードに含まれる分類ルールをホールフィリングルールとして設定し、
前記ホールフィリングルールの優先度は、前記分類ルールセットにおける各分類ルールの優先度より低いことを特徴とする請求項６に記載のパケット分類決定木確立装置。
【請求項８】
前記第２決定木作成は、更に、
互いに同パターンサブルールセットとなる複数の分類ルールサブセットを含む葉ノードが前記第１タイプ決定木に存在するとき、前記葉ノードに含まれる低優先度の分類ルールサブセットを削除することを特徴とする請求項６に記載のパケット分類決定木確立装置。
【請求項９】
前記多重化手段は、更に、
前記複数の葉ノードに含まれる互いに同パターンサブルールセットとなる複数の分類ルールサブセットを同一の同パターンサブルールセット群に区分し、
前記複数の葉ノードの各葉ノードに対して、当該葉ノードと、当該同パターンサブルールセット群の識別子、および、当該葉ノードに含まれる分類ルールサブセットの、当該同パターンサブルールセット群におけるインデックスとの間のマッピング関係を確立し、
前記複数の葉ノードのそれぞれに対応する前記第２タイプ決定木を１つの第２タイプ決定木として合併し、
前記合併された第２タイプ決定木の葉ノードは、当該同パターンサブルールセット群における各分類ルールを含むことを特徴とする請求項６に記載のパケット分類決定木確立装置。
【請求項１０】
前記パケット分類決定木確立装置は、検索手段を更に備え、
前記検索手段は、
前記第１タイプ決定木を検索することにより、分類すべきパケットに対応する、前記第１タイプ決定木における第１対象葉ノードを特定し、
前記第１対象葉ノードに記憶される同パターンサブルールセット群の識別子に基づいて対象第２タイプ決定木を特定し、
前記対象第２タイプ決定木を検索することにより、前記分類すべきパケットに対応する、前記対象第２タイプ決定木における第２対象葉ノードを特定し、
前記第１対象葉ノードに記憶される同パターンサブルールセット群におけるインデックスに基づいて、対応する分類ルールを前記第２対象葉ノードから検索し、
当該検索された分類ルールを前記分類すべきパケットにマッチングする分類ルールとして特定することを特徴とする請求項９に記載のパケット分類決定木確立装置。
【請求項１１】
パケット分類決定木確立装置であって、
プロセッサと、
機械可読記憶媒体と、を備え、
前記機械可読記憶媒体には、前記プロセッサによって実行され得る機械実行可能な指令が記憶され、
前記プロセッサは、前記機械実行可能な指令により、
分類ルールセットの非テンプレートディメンションに基づいて、前記分類ルールセットに対して決定木を作成し、第１タイプ決定木を生成することと、
前記分類ルールセットのテンプレートディメンションに基づいて、前記第１タイプ決定木における葉ノードのそれぞれに対して決定木を作成し、第２タイプ決定木を生成することと、
前記第１タイプ決定木における互いに同パターンサブルールセットとなる複数の葉ノードを同一の第２タイプ決定木に関連付けさせることと、を実行させ、
前記互いに同パターンサブルールセットとなる複数の葉ノードは、前記複数の葉ノードのそれぞれに含まれる分類ルールのセットが互いに同パターンサブルールセットとなることを意味することを特徴とするパケット分類決定木確立装置。
【請求項１２】
前記プロセッサは、更に、前記機械実行可能な指令により、
前記非テンプレートディメンションおよび対応する値が前記分類ルールセットにおける分類ルールにマッチングしないとき、分類ルールにマッチングしない葉ノードに含まれる分類ルールをホールフィリングルールとして設定することを実行させ、
前記ホールフィリングルールの優先度は、前記分類ルールセットにおける各分類ルールの優先度より低いことを特徴とする請求項１１に記載のパケット分類決定木確立装置。
【請求項１３】
前記プロセッサは、更に、前記機械実行可能な指令により、
互いに同パターンサブルールセットとなる複数の分類ルールサブセットを含む葉ノードが前記第１タイプ決定木に存在するとき、前記葉ノードに含まれる低優先度の分類ルールサブセットを削除することを実行させることを特徴とする請求項１１に記載のパケット分類決定木確立装置。
【請求項１４】
前記プロセッサは、更に、前記機械実行可能な指令により、
前記複数の葉ノードに含まれる互いに同パターンサブルールセットとなる複数の分類ルールサブセットを同一の同パターンサブルールセット群に区分することと、
前記複数の葉ノードの各葉ノードに対して、当該葉ノードと、当該同パターンサブルールセット群の識別子、および、当該葉ノードに含まれる分類ルールサブセットの、当該同パターンサブルールセット群におけるインデックスとの間のマッピング関係を確立することと、
前記複数の葉ノードのそれぞれに対応する前記第２タイプ決定木を１つの第２タイプ決定木として合併することと、を実行させ、
前記合併された第２タイプ決定木の葉ノードは、当該同パターンサブルールセット群における各分類ルールを含むことを特徴とする請求項１１に記載のパケット分類決定木確立装置。
【請求項１５】
前記プロセッサは、更に、前記機械実行可能な指令により、
前記第１タイプ決定木を検索することにより、分類すべきパケットに対応する、前記第１タイプ決定木における第１対象葉ノードを特定することと、
前記第１対象葉ノードに記憶される同パターンサブルールセット群の識別子に基づいて対象第２タイプ決定木を特定することと、
前記対象第２タイプ決定木を検索することにより、前記分類すべきパケットに対応する、前記対象第２タイプ決定木における第２対象葉ノードを特定することと、
前記第１対象葉ノードに記憶される同パターンサブルールセット群におけるインデックスに基づいて、対応する分類ルールを前記第２対象葉ノードから検索することと、
当該検索された分類ルールを前記分類すべきパケットにマッチングする分類ルールとして特定することと、を実行させることを特徴とする請求項１４に記載のパケット分類決定木確立装置。
【請求項１６】
前記パケット分類決定木確立装置は、フィールドプログラマブルゲートアレイを更に備え、
前記プロセッサは、更に、前記機械実行可能な指令により、前記第１タイプ決定木および前記第２タイプ決定木を前記フィールドプログラマブルゲートアレイに配布し、前記フィールドプログラマブルゲートアレイに決定木検索処理を実行させることを特徴とする請求項１５に記載のパケット分類決定木確立装置。
【発明の詳細な説明】
【背景技術】
【０００１】
関連出願の相互引用
本願は、出願日が２０１７年８月３１日であり、出願番号が２０１７１０７７１８９９．０であり、発明名称が「パケット分類決定木確立方法および装置」である中国特許出願の優先権を主張し、当該出願の全文が引用により本願に組み込まれる。
【０００２】
パケット分類とは、パケットのヘッダにおける各異なるフィールドの値に基づいて、予め配置された分類ルールを検索し、それにマッチングする最高優先度の分類ルールを取得し、当該分類ルールで配置された操作を実行することを指す。多数のネットワーク機器から与えられるアクセス制御、トラフィック制御、負荷分散または侵入検出等のような機能は、何れもパケット分類を使用する必要がある。
【０００３】
決定木に基づくマルチドメイン分割アルゴリズムは、典型的なパケット分類方法であり、その基本思想として、全多次元空間をサブ空間に再帰的に分割する。再帰が終了する条件は、現在のサブ空間に含まれる全てのルールが各ディメンションにおいてこのサブ空間を完全に充填することである。この過程から１つの決定木が取得できる。この決定木に基づいて、分類すべきパケットのそれぞれを検索することにより、パケットにマッチングする分類ルールを取得する。
【０００４】
実践から分かるように、決定木におけるノードが多いほど、決定木によって占用される記憶空間も多くなる。しかし、ネットワーク機器の記憶空間は、限られている。決定木のノード数が多すぎると、パケット分類アルゴリズムがサポートする分類ルールセットの規模は、制限される。したがって、如何にして決定木の検索効率に影響せずに決定木のノード数を減少するかは、解決すべき技術問題となっている。
【図面の簡単な説明】
【０００５】
【図１】本発明の実施例に係るパケット分類決定木確立方法のフローの模式図である。
【図２Ａ】本発明の実施例に係るパケット分類の原理構造の模式図である。
【図２Ｂ】本発明の実施例に係るＴｒｅｅＢｕｉｌｄｅｒの反復手段の原理模式図である。
【図３Ａ】本発明の実施例に係る決定木の模式図である。
【図３Ｂ】本発明の実施例に係る決定木の模式図である。
【図３Ｃ】本発明の実施例に係る決定木の模式図である。
【図３Ｄ】本発明の実施例に係る決定木の模式図である。
【図３Ｅ】本発明の実施例に係る決定木の模式図である。
【図４】本発明の実施例に係るパケット分類の検索パスの模式図である。
【図５】本発明の実施例に係るパケット分類決定木確立装置のハードウェア構造の模式図である。
【図６】本発明の実施例に係るパケット分類決定木確立制御論理の機能構成図である。
【発明を実施するための形態】
【０００６】
本発明の実施例における技術案がより明瞭に当業者に理解されるように、以下では、まず、本発明の実施例の技術案に係る一部の概念を簡単に説明する。
【０００７】
分類ルールセットは、複数の分類ルールを含む。１つの分類ルールは、ディメンション情報、優先度を含む。
【０００８】
各ディメンション情報は、１つの取り得る値の範囲で表される。分類ルールにマッチングした後、マッチング結果を戻す必要がある。優先度は、複数のルールがマッチング条件を満たすとき、どのルールのマッチング結果を戻すかを決定するために用いられる。本発明の実施例では、最も優先度の高い分類ルールのマッチング結果を戻すことを例とする。分類ルールセットのフォーマットは、表１に示されてもよい。表１の分類ルールセットは、ｒ０−ｒ８の合計９つの分類ルールを含む。
【０００９】
【表１】
2020532241.tif 000003
【００１０】
ｓｉｐ（ソースＩＰアドレス）、ｄｉｐ（宛先ＩＰアドレス）、ｓｐｏｒｔ（ソースポート番号）、ｄｐｏｒｔ（宛先ポート番号）、ｐｒｏｔ（プロトコルタイプ）、ｖｌａｎ（Ｖｉｒｔｕａｌ Ｌｏｃａｌ Ａｒｅａ Ｎｅｔｗｏｒｋ、仮想ローカルエリアネットワーク）およびｓｙｓｐｏｒｔ（システムポート）は、表１に示す分類ルールのディメンション情報である。ディメンション情報ｐｒｏｔは、ｔｃｐ（Ｔｒａｎｓｍｉｓｓｉｏｎ Ｃｏｎｔｒｏｌ Ｐｒｏｔｏｃｏｌ、伝送制御プロトコル）またはｕｄｐ（Ｕｓｅｒ Ｄａｔａｇｒａｍ Ｐｒｏｔｏｃｏｌ、ユーザデータグラムプロトコル等を含んでもよいが、それらに限定されない。あるディメンション情報の値が「*」であるとき、当該ディメンション情報の値が当該ディメンションの取り得る値の範囲内の任意値であってもいいことを意味する。例えば、ディメンション情報ｄｐｏｒｔについて、その取り得る値の範囲は、「０〜（２１６−１）」である。
【００１１】
分類ルールテンプレートは、テンプレートアイテムのセットである。１つの分類ルールテンプレートは、１つまたは複数のテンプレートアイテムを含む。
【００１２】
テンプレートアイテムは、１つまたは複数のディメンション情報を含む。３つのテンプレートアイテムを含む分類ルールテンプレートのフォーマットは、表２に示されてもよい。
【００１３】
【表２】
2020532241.tif 000004
【００１４】
テンプレートディメンションは、テンプレートアイテムに含まれるディメンションである。例えば、表１と表２を例とすると、表２に示すテンプレートアイテムは、分類ルールにおける５つのテンプレートディメンションを含み、それらは、それぞれｓｉｐ、ｄｉｐ、ｓｐｏｒｔ、ｄｐｏｒｔとｐｒｏｔである。
【００１５】
非テンプレートディメンションは、分類ルールにおけるテンプレートディメンション以外のディメンションである。例えば、同様に表１と表２を例とすると、表１に示す分類ルールは、２つの非テンプレートディメンションを含み、それらは、それぞれｖｌａｎとｓｙｓｐｏｒｔを含む。
【００１６】
テンプレートインスタンス化とは、分類ルールテンプレートを１つまたは複数の非テンプレートディメンションに用いることで、１つまたは複数の分類ルールを得ることを指す。
【００１７】
例えば、表２に示す分類ルールテンプレートを非テンプレートディメンションｓｙｓｐｏｒｔ＝０ｘ２００に用いると、表１に示す分類ルールセットにおける分類ルールｒ０、ｒ１とｒ２を得ることができる。この３つの分類ルールのテンプレートディメンションｓｉｐ、ｄｉｐ、ｓｐｏｒｔ、ｄｐｏｒｔとｐｒｏｔの値は、それぞれ表２に示す分類ルールテンプレートにおける対応するテンプレートディメンションの値に対応しており、非テンプレートディメンションｓｙｓｐｏｒｔの値は、何れも０ｘ２００である。
【００１８】
テンプレートインスタンス化は、複数の非テンプレートディメンションを指定してインスタンス化を行ってもよい。例えば、表２に示す分類ルールテンプレートを非テンプレートディメンションｖｌａｎ＝[１０,２０）とｓｙｓｐｏｒｔ＝０ｘ３００に用いると、表１に示す分類ルールセットにおける分類ルールｒ３、ｒ４とｒ５を得ることができる。
【００１９】
ただし、{ｒ０、ｒ１、ｒ２}、{ｒ３、ｒ４、ｒ５}および{ｒ６、ｒ７、ｒ８}は、表１に示す分類ルールセットにおける分類ルールサブセットと呼ばれてもよい。
【００２０】
ホールフィリングルール（ｆｂ_ｒｕｌｅ）とは、全てのディメンションの値が何れも「*」である分類ルールを指す。ホールフィリングルールは、最も優先度が低い分類ルールである。換言すれば、分類ルールセットに含まれる各分類ルールの優先度は、何れもホールフィリングルールの優先度より高い。
【００２１】
同パターンサブルールセット（Ｓａｍｅ Ｐａｔｔｅｒｎ Ｓｕｂ Ｒｕｌｅｓｅｔ、ＳＰＳＲと略称）とは、１つの分類ルールテンプレートを複数の異なる非テンプレートディメンションに用いて得られた複数の分類ルールサブセットが互いに同パターンサブルールセットとなることを指す。１つの分類ルールテンプレートを複数の異なる非テンプレートディメンションに用いることは、異なる非テンプレートディメンションに応じるインスタンス化と呼ばれてもよい。
【００２２】
例えば、表１に示す分類ルールセットでは、分類ルールサブセット{ｒ０、ｒ１、ｒ２}、{ｒ３、ｒ４、ｒ５}と{ｒ６、ｒ７、ｒ８}は、互いに同パターンサブルールセットとなる。ホールフィリングルールとその自身は、互いに同パターンサブルールセットとなる。
【００２３】
同パターンサブルールセット群（ＳＰＳＲ_Ｇｒｏｕｐ）は、互いに同パターンサブルールセットとなる複数の分類ルールサブセットを含む。
【００２４】
ホールフィリングルールに対応する同パターンサブルールセット群は、ホールフィリングルールという分類ルールのみを含む。
【００２５】
本発明の実施例の上記目的、特徴およびメリットがより明瞭になるように、以下に図面を組み合わせて本発明の実施例における技術案を更に詳細に説明する。
【００２６】
図１は、本発明の実施例に係るパケット分類決定木確立方法のフローの模式図である。当該パケット分類決定木確立方法は、ネットワーク機器に用いられてもよい。当該ネットワーク機器は、スイッチ、ルータ等を含んでもよいが、それらに限定されるものではない。図１に示すように、当該パケット分類決定木確立方法は、以下のステップを含む。
【００２７】
ステップ１０１では、分類ルールセットの非テンプレートディメンションに基づいて、分類ルールセットに対して決定木を作成し、第１タイプ決定木を生成する。当該第１タイプ決定木は、分類ルールセットの、非テンプレートディメンションに対応する決定木である。
【００２８】
本発明の実施例では、分類ルールセットは、ある固定の分類ルールセットを特に指すことなく、パケット分類を行うための何れかの分類ルールセットであってもよい。後は繰り返し説明しない。
【００２９】
本発明の実施例では、分類ルールセットに対応するパケット分類決定木を作成する必要が生じるとき、分類ルールセットの非テンプレートディメンションに基づいて、分類ルールセットに対して決定木を先に作成し、分類ルールセットの、非テンプレートディメンションに対応する決定木（本文では、第１タイプ決定木、または、非テンプレートディメンション決定木と呼ばれる）を生成する必要がある。
【００３０】
理解の便宜上、以下では、第１タイプ決定木を非テンプレートディメンション決定木と呼ばれて説明を行う。
【００３１】
本発明の実施例では、ネットワーク機器が分類ルールセットに対して決定木を作成することは、空間分割に基づく方式が採用され得る。
【００３２】
ただし、ネットワーク機器が分類ルールセットの非テンプレートディメンションに基づいて、分類ルールセットに対して決定木を作成する具体的な実施は、下文に実例を組み合わせて説明する。ここで繰り返し説明しない。
【００３３】
説明すべきことは、本発明の実施例において、ネットワーク機器が分類ルールセットの非テンプレートディメンションに基づいて、分類ルールセットに対して決定木を作成するとき、選択されたディメンションおよび値が分類ルールセットにおける分類ルールにマッチングしない場合、ネットワーク機器は、分類ルールにマッチングしない葉ノードに含まれる分類ルールをホールフィリングルールとして設定する。空間分割で得られたサブ空間にホールフィリングルールのみが含有され、他の如何なる分類ルールも含有されていないときは、終了条件が満たされる。
【００３４】
ステップ１０２では、分類ルールセットのテンプレートディメンションに基づいて第１タイプ決定木の各葉ノードに対して決定木を作成し、第２タイプ決定木を生成する。ただし、当該第２タイプ決定木は、第１タイプ決定木の葉ノードの、テンプレートディメンションに対応する決定木である。
【００３５】
本発明の実施例では、非テンプレートディメンション決定木は、非テンプレートディメンションのみに基づいて、分類ルールセットにおける各分類ルールについて空間分割を行ったため、非テンプレートディメンション決定木の各葉ノードは、まだ空間分割が完成されておらず、テンプレートディメンションに応じて更に空間分割を行う必要もある。
【００３６】
それ相応に、ネットワーク機器は、分類ルールセットに対応する非テンプレートディメンション決定木を確立した後、更に分類ルールセットのテンプレートディメンションに基づいて、非テンプレートディメンション決定木の各葉ノードに対して空間分割を行い、非テンプレートディメンション決定木の各葉ノードの、テンプレートディメンションに対応する決定木（本文では、第２タイプ決定木、またはテンプレートディメンション決定木と呼ばれる）を取得する必要もある。
【００３７】
理解の便宜上、以下では、第２タイプ決定木をテンプレートディメンション決定木と呼ばれて説明を行う。
【００３８】
テンプレートディメンション決定木が非テンプレートディメンション決定木の葉ノードについて空間分割を行ったものであるため、当該テンプレートディメンション決定木は、非テンプレートディメンション決定木のサブ木と呼ばれてもよい。
【００３９】
ネットワーク機器は、分類ルールセットのテンプレートディメンションに基づいて、非テンプレートディメンション決定木の葉ノードに対して決定木を作成する具体的な実施は、下文に実例を組み合わせて説明を行うため、ここで繰り返し説明しない。
【００４０】
説明すべきことは、本発明の実施例では、ホールフィリングルールの各ディメンションの値が何れも「*」であり、即ち、各ディメンションの取り得る値の範囲内の任意値であり得るため、テンプレートディメンションに基づいて、ホールフィリングルールに対して空間分割を行って得られるものは、相変わらずホールフィリングルールである。それ相応に、非テンプレートディメンション決定木に含まれる分類ルールがホールフィリングルールである葉ノードに対して、テンプレートディメンションに基づいて、空間分割を行って得られるテンプレートディメンション決定木は、相変わらずホールフィリングルールである。
【００４１】
ステップ１０３では、第１タイプ決定木における互いに同パターンサブルールセットとなる複数の葉ノードを同一の第２タイプ決定木に関連付けさせる。
【００４２】
本発明の実施例では、互いに同パターンサブルールセットとなる複数の分類ルールサブセットに含まれるテンプレートディメンションの値は、同じである。このように、同一のアルゴリズムを使用してテンプレートディメンションに基づいて、互いに同パターンサブルールセットとなる複数の分類ルールサブセットに対して決定木を確立する際、得られる複数のテンプレートディメンション決定木の木構造は、同じであり、単に葉ノードが異なる。したがって、互いに同パターンサブルールセットとなる複数の分類ルールサブセットに対応するテンプレートディメンション決定木は、同一のテンプレートディメンション決定木として多重化することができる。
【００４３】
それ相応に、ネットワーク機器は、非テンプレートディメンション決定木の各葉ノードに対応するテンプレートディメンション決定木を確立した後、確立されたテンプレートディメンション決定木に対して多重化を行うことができる。このように、非テンプレートディメンション決定木における互いに同パターンサブルールセットとなる複数の葉ノードを同一のテンプレートディメンション決定木に関連させ、テンプレートディメンション決定木の数を減し、さらに分類ルールセットに対応する決定木のノード数も減す。互いに同パターンサブルールセットとなる複数の葉ノードとは、前記複数の葉ノードのそれぞれに対応する分類ルールサブセットが互いに同パターンサブルールセットとなることを意味する。葉ノードに対応する分類ルールサブセットとは、当該葉ノードに含まれる分類ルールのセットを指す。分類ルールセットに対応する決定木は、非テンプレートディメンション決定木およびテンプレートディメンション決定木を含む。
【００４４】
１つの好適な実施形態では、上記第１タイプ決定木における互いに同パターンサブルールセットとなる複数の葉ノードを同一の第２タイプ決定木に関連付けさせることは、互いに同パターンサブルールセットとなる複数の異なる分類ルールサブセットを同一の同パターンサブルールセット群に区分することと、第１タイプ決定木における互いに同パターンサブルールセットとなる複数の葉ノードのそれぞれと、対応する分類ルールサブセットの所属する同パターンサブルールセット群の識別子、および、当該分類ルールサブセットの、当該同パターンサブルールセット群におけるインデックスとの間のマッピング関係を確立することと、第１タイプ決定木における互いに同パターンサブルールセットとなる複数の葉ノードのそれぞれに対応する第２タイプ決定木を、同一の第２タイプ決定木として合併することとを含んでもよい。これにより、合併して得られる当該第２タイプ決定木の葉ノードは、同パターンサブルールセット群における各インデックスに対応する分類ルールサブセットを含む。葉ノードに対応する分類ルールサブセットは、当該葉ノードに含まれる分類ルールのセットである。
【００４５】
当該実施形態では、同一の分類ルールテンプレートを異なる非テンプレートディメンションに応じてインスタンス化して得られた複数の分類ルールサブセットは、互いに同パターンサブルールセットとなり、互いに同パターンサブルールセットとなる複数の分類ルールサブセットは、同パターンサブルールセット群を構成する。
【００４６】
表１に示す分類ルールセットを例とすると、分類ルールサブセット{ｒ０、ｒ１、ｒ２}は、表２に示す分類ルールテンプレートを非テンプレートディメンションｓｙｓｐｏｒｔ＝０ｘ２００に用いて得られたものであり、分類ルールサブセット{ｒ３、ｒ４、ｒ５}は、表２に示す分類ルールテンプレートを非テンプレートディメンションｖｌａｎ＝[１０,２０）およびｓｙｓｐｏｒｔ＝０ｘ３００に用いて得られたものであり、分類ルールサブセット{ｒ６、ｒ７、ｒ８}は、表２に示す分類ルールテンプレートを非テンプレートディメンションｖｌａｎ＝３０に用いて得られたものである。したがって、分類ルールサブセット{ｒ０、ｒ１、ｒ２}、{ｒ３、ｒ４、ｒ５}と{ｒ６、ｒ７、ｒ８}は、互いに同パターンサブルールセットとなりつつ、１つの同パターンサブルールセット群を構成する。
【００４７】
当該実施形態では、同パターンサブルールセット群における各分類ルールサブセットに対して、当該分類ルールサブセットの、当該同パターンサブルールセットにおけるインデックスを設定する。このように、同パターンサブルールセット群の識別子（例えば、同パターンサブルールセット群の名称）と当該同パターンサブルールセット群におけるインデックスとに基づいて、対応する分類ルールサブセットを特定することができる。
【００４８】
例えば、分類ルールサブセット{ｒ０、ｒ１、ｒ２}、{ｒ３、ｒ４、ｒ５}と{ｒ６、ｒ７、ｒ８}が同パターンサブルールセット群ｓｐｓｒｇ１（当該同パターンサブルールセット群の識別子がｓｐｓｒｇ１である）に属し、且つ分類ルールサブセット{ｒ０、ｒ１、ｒ２}、{ｒ３、ｒ４、ｒ５}と{ｒ６、ｒ７、ｒ８}の、同パターンサブルールセット群ｓｐｓｒｇ１におけるインデックスがそれぞれ０、１と２であるとすれば、分類ルールサブセット{ｒ０、ｒ１、ｒ２}は、同パターンサブルールセット群ｓｐｓｒｇ１におけるインデックス０にマッピングでき、分類ルールサブセット{ｒ３、ｒ４、ｒ５}は、同パターンサブルールセット群ｓｐｓｒｇ１におけるインデックス１にマッピングでき、分類ルールサブセット{ｒ６、ｒ７、ｒ８}は、ｓｐｓｒｇ１におけるインデックス２にマッピングできる。
【００４９】
当該実施形態では、ネットワーク機器は、各分類ルールサブセットの所属する同パターンサブルールセット群、および、各分類ルールサブセットの、同パターンサブルールセット群におけるインデックスを特定した後、非テンプレートディメンション決定木における互いに同パターンサブルールセットとなる葉ノードと、対応する分類ルールサブセットの所属する同パターンサブルールセット群の識別子、および、当該分類ルールサブセットの、当該同パターンサブルールセット群におけるインデックスとの間のマッピング関係を確立する。例えば、互いに同パターンサブルールセットとなる複数の葉ノードにおける各葉ノード、当該該葉ノードに、当該葉ノードに対応する分類ルールサブセットの所属する同パターンサブルールセット群の識別子と、当該対応する分類ルールサブセットの、当該同パターンサブルールセット群におけるインデックスとを記憶する。
【００５０】
上記例に基づいて、詳細に言えば、分類ルールサブセット{ｒ０、ｒ１、ｒ２}に対応する葉ノードを例とすると、当該葉ノードと、分類ルールサブセット{ｒ０、ｒ１、ｒ２}の所属する同パターンサブルールセット群の識別子ｓｐｓｒｇ１、および、分類ルールサブセット{ｒ０、ｒ１、ｒ２}の、当該同パターンサブルールセット群におけるインデックス０との間のマッピング関係を確立し、当該葉ノードに、分類ルールサブセット{ｒ０、ｒ１、ｒ２}の所属する同パターンサブルールセット群の識別子ｓｐｓｒｇ１、および、分類ルールサブセット{ｒ０、ｒ１、ｒ２}の当該同パターンサブルールセット群ｓｐｓｒｇ１におけるインデックス０を記憶してもよい。
【００５１】
ネットワーク機器は、同一の同パターンサブルールセット群における複数の分類ルールサブセットのそれぞれに対応するテンプレートディメンション決定木を１つのテンプレートディメンション決定木として合併してもよく、且つ合併後のテンプレートディメンション決定木の各葉ノードは、当該同パターンサブルールセット群における各インデックスに対応する分類ルールサブセットを含んでもよい。
【００５２】
本発明の実施例では、互いに同パターンサブルールセットとなる複数の分類ルールサブセットのそれぞれに対応するテンプレートディメンション決定木の構造は、同じであり、単に葉ノードが異なる。このように、互いに同パターンサブルールセットとなる複数の葉ノードが非テンプレートディメンション決定木の葉ノードに存在するとき、当該葉ノードに対応するテンプレートディメンション決定木における各葉ノードが、同一テンプレートアイテムを異なる非テンプレートディメンションに応じてインスタンス化して得られた複数の分類ルールを含むが、当該複数の分類ルールのうち、最も優先度が高い分類ルールのみが有効になる。したがって、非テンプレートディメンション決定木の葉ノードのうち、互いに同パターンサブルールセットとなる複数の分類ルールサブセットを含む葉ノードに対して、ネットワーク機器は、当該葉ノードに含まれる低優先度の分類ルールサブセットを削除してもよい。
【００５３】
本発明の実施例では、ネットワーク機器は、分類ルールセットに対応する決定木（非テンプレートディメンション決定木とテンプレートディメンション決定木とによって構成される）を確立した後、分類すべきパケットを受信すると、先に当該分類すべきパケットに基づいて分類ルールセットに対応する非テンプレートディメンション決定木を検索することで、当該分類すべきパケットに対応する非テンプレートディメンション決定木における葉ノード（本文では、第１対象葉ノードと呼ばれる）を特定し、当該第１対象葉ノードに記憶される同パターンサブルールセット群（本文では、対象同パターンサブルールセット群と呼ばれる）の識別子、および、分類ルールサブセット（本文では、対象分類ルールサブセットと呼ばれる）の、当該対象同パターンサブルールセット群におけるインデックス（本文では、対象インデックスと呼ばれる）を取得する。
【００５４】
その後、ネットワーク機器は、分類すべきパケットに基づいて当該対象同パターンサブルールセット群に対応するテンプレートディメンション決定木（本文では、対象テンプレートディメンション決定木と呼ばれる）を検索することで、当該分類すべきパケットに対応する対象テンプレートディメンション決定木における葉ノード（本文では、第２対象葉ノードと呼ばれる）を特定する。
【００５５】
最後に、ネットワーク機器は、第２対象葉ノードに含まれる、対象インデックスに対応する分類ルールを、分類すべきパケットにマッチングする分類ルールとして特定する。
【００５６】
本発明の実施例に係る技術案がより明瞭に当業者に理解されるように、以下では、具体的な実例を組み合わせて本発明の実施例に係る技術案を説明する。
【００５７】
図２Ａは、本発明の実施例に係るパケット分類の原理構造の模式図である。図２Ａに示すように、ＣＰＵ（Ｃｅｎｔｅｒ Ｐｒｏｃｅｓｓ Ｕｎｉｔ、中央処理装置）２１０は、決定木作成手段（Ｔｒｅｅ Ｂｕｉｌｄｅｒ）２１１により、入力された分類ルールセットを決定木にコンパイルし、ＦＰＧＡ（Ｆｉｅｌｄ Ｐｒｏｇｒａｍｍａｂｌｅ Ｇａｔｅ Ａｒｒａｙ、フィールドプログラマブルゲートアレイ）２２０へ配信する。ＦＰＧＡ ２２０は、パケットを受信すると、検索エンジン（Ｌｏｏｋｕｐ Ｅｎｇｉｎｅ）２２１を介して、分類ルールセットに対応する決定木を検索し、マッチングする分類ルールを特定する。
【００５８】
ただし、決定木作成手段２１１は、反復の方式で決定木の確立を実施可能であり、そのコアが、ディメンション及び値（Ｄｉｍ & Ｖａｌｕｅ、Ｄ&Ｖ簡称）に基づく１つのヒューリスティックセレクタ２１１−１である。ただし、当該ヒューリスティックセレクタは、１つのルールセット（Ｒｕｌｅ Ｓｅｔ、ＲＳと略称）を入力し、２つのルールサブセットと１つの決定木ノード（Ｄｅｃｉｓｉｏｎ Ｔｒｅｅ Ｎｏｄｅ、ＤＴ Ｎｏｄｅと略称）を出力する。当該ヒューリスティックセレクタは、入力されたルールセットに基づき、ヒューリスティックアルゴリズムを利用して、入力されたディメンションリスト（Ｄｉｍ Ｌｉｓｔ）から１つのディメンションおよび値を選択し、その後、入力されたルールセットを、選択されたディメンションおよび値に応じて２つのサブセットに分割する。ルールに対応するディメンションの取り得る値の範囲が選択された値より小さい場合に、当該ルールを左サブセットに区分し、ルールに対応するディメンションの取り得る値の範囲が選択された値より大きい場合に、当該ルールを右サブセットに区分し、ルールに対応するディメンションの取り得る値の範囲が選択された値をカバーする場合に、当該ルールを２つに分けて、小さい部分を左サブセットへ区分し、大きい部分を右サブセットへ区分する。このように、選択されたディメンションと値を１つの決定木ノードとすることで、ルールセットに対する１回の空間分割を完成する。同時に、得られた２つのルールサブセットについて、分類ルールサブセットがそれ以上分割できないまで、引き続き上記操作を繰り返して実行する。決定木作成手段２１１における反復手段の原理模式図は、図２Ｂに示されてもよい。
【００５９】
図２Ａと図２Ｂに基づくと、本発明の実施例に係るパケット分類決定木確立案の実施フローは、下記のようになっている。
【００６０】
表２に示す分類ルールテンプレート、および、表１に示す分類ルールセットを例とする。分類ルールセットの非テンプレートディメンションは、ｖｌａｎとｓｙｓｐｏｒｔを含み、テンプレートディメンションは、ｓｉｐ、ｄｉｐ、ｓｐｏｒｔ、ｄｐｏｒｔおよびｐｒｏｔを含む。
【００６１】
非テンプレートディメンションｖｌａｎとｓｙｓｐｏｒｔに基づいて表１に示す分類ルールセットに対して決定木を作成することで、当該分類ルールセットに対応する非テンプレートディメンション決定木を取得する。当該非テンプレートディメンション決定木の構造模式図は、図３Ａに示されてもよい。
【００６２】
図３Ａに示す非テンプレートディメンション決定木の葉ノードのうち、非矩形ボックスの葉ノードが何れも１つのみのホールフィリングルールを含む一方、矩形ボックスの葉ノードが複数の分類ルールを含む。
【００６３】
テンプレートディメンションｓｉｐ、ｄｉｐ、ｓｐｏｒｔ、ｄｐｏｒｔおよびｐｒｏｔに基づいて、図３Ａに示す非テンプレートディメンション決定木の各葉ノードに対して決定木を作成することで、非テンプレートディメンション決定木の各葉ノードに対応するテンプレートディメンション決定木を取得する。
【００６４】
ただし、テンプレートディメンションに基づいて、１つのみのホールフィリングルールを含む葉ノードに対して決定木を作成して得られたテンプレートディメンション決定木は、１つのみのノードを含み、且つ当該ノードは、ホールフィリングルールのみを含む。
【００６５】
分類ルールｒ０、ｒ１とｒ２を含む葉ノードについて、テンプレートディメンションに基づいて、当該葉ノードに対して決定木を作成して得られたテンプレートディメンション決定木の模式図は、図３Ｂに示されてもよい。
【００６６】
分類ルールｒ３、ｒ４とｒ５を含む葉ノードについて、テンプレートディメンションに基づいて、当該葉ノードに対して決定木を作成して得られたテンプレートディメンション決定木の模式図は、図３Ｃに示されてもよい。
【００６７】
図３Ｂと図３Ｃから分かるように、分類ルールサブセット{ｒ０、ｒ１、ｒ２}が表２に示す分類ルールテンプレートを非テンプレートディメンションｓｙｓｐｏｒｔ＝０ｘ２００に応じてインスタンス化して得られたものであり、分類ルールサブセット{ｒ３、ｒ４、ｒ５}が同一の表２に示す分類ルールテンプレートを非テンプレートディメンションｓｙｓｐｏｒｔ＝０ｘ３００およびｖｌａｎ＝[１０, ２０）に応じてインスタンス化して得られたものであり、分類ルールサブセット{ｒ０、ｒ１、ｒ２}と{ｒ３、ｒ４、ｒ５}が互いに同パターンサブルールセットとなるため、それに対応するテンプレートディメンション決定木の木構造は、同じであり、単に葉ノードが異なる。図３Ｂと図３Ｃに示すテンプレートディメンション決定木において、同じ位置における葉ノードが、それぞれ同一のテンプレートアイテムを異なる非テンプレートディメンションに応じてインスタンス化して得られた分類ルールである。
【００６８】
同様に、分類ルールサブセット{ｒ６、ｒ７、ｒ８}が同一の表２に示す分類ルールテンプレートを非テンプレートディメンションｖｌａｎ＝３０に用いて得られたものであるため、分類ルールｒ６、ｒ７とｒ８を含む葉ノードに対応するテンプレートディメンション決定木の構造も、図３Ｂと図３Ｃに示すテンプレートディメンション決定木と同じであり、且つ同じ位置における葉ノードも、同じテンプレートアイテムのインスタンス化によって得られたものである。
【００６９】
なお、図３Ａに示す非テンプレートディメンション決定木における、分類ルールｒ０、ｒ１、ｒ２、ｒ６、ｒ７およびｒ８を含む葉ノードについて、{ｒ０、ｒ１、ｒ２}と{ｒ６、ｒ７、ｒ８}が互いに同パターンサブルールセットとなるため、テンプレートディメンションに基づいて、当該葉ノードに対して決定木を作成して得られたテンプレートディメンション決定木における、ホールフィリングルールを含まない葉ノードは、何れも２つの分類ルールを含み、且つこの２つのルールは、同一テンプレートアイテムを異なる非テンプレートディメンションに応じてインスタンス化して得られたものである。具体的に、例えば、分類ルールｒ０とｒ６は、表２に示すテンプレートアイテムｍｅ０を異なる非テンプレートディメンションに応じてインスタンス化して得られたものであり、分類ルールｒ１とｒ７は、表２に示すテンプレートアイテムｍｅ１を異なる非テンプレートディメンションに応じてインスタンス化して得られたものであり、分類ルールｒ５とｒ８は、表２に示すテンプレートアイテムｍｅ２を異なる非テンプレートディメンションに応じてインスタンス化して得られたものである。パケットが複数の分類ルールを含む葉ノードにマッチングしたとき、返信されたマッチング結果は、優先度の高い分類ルールである。したがって、互いに同パターンサブルールセットとなる複数の分類ルールサブセットを含む葉ノードについて、互いに同パターンサブルールセットとなる複数の分類ルールサブセットのうち、優先度の高い分類ルールサブセットのみを保留すればよく、優先度の低い分類ルールサブセットをフィルタリングにより除去する。つまり、分類ルールサブセット{ｒ０、ｒ１、ｒ２}のみを保留し、分類ルールサブセット{ｒ６、ｒ７、ｒ８}を削除する。さらに、当該葉ノードに対応するテンプレートディメンション決定木の構造模式図も、図３Ｂに示される。
【００７０】
また、ホールフィリングルールに対応する同パターンサブルールセット群の識別子がｓｐｓｒｇ０であり、ホールフィリングルールの、同パターンサブルールセット群ｓｐｓｒｇ０におけるインデックスが０であるとすれば、分類ルールサブセット{ｒ０、ｒ１、ｒ２}、{ｒ３、ｒ４、ｒ５}と{ｒ６、ｒ７、ｒ８}とに対応する同パターンサブルールセット群の識別子は、ｓｐｓｒｇ１となり、且つ、分類ルールサブセット{ｒ０、ｒ１、ｒ２}、{ｒ３、ｒ４、ｒ５}と{ｒ６、ｒ７、ｒ８}の、同パターンサブルールセット群ｓｐｓｒｇ１におけるインデックスは、それぞれ０、１および２となる。
【００７１】
図３Ａに示す非テンプレートディメンション決定木における、互いに同パターンサブルールセットとなる複数の葉ノードにおける各葉ノードに対して、当該葉ノードと、当該葉ノードに対応する分類ルールサブセットの所属する同パターンサブルールセット群の識別子、および、当該分類ルールサブセットの当該同パターンサブルールセット群におけるインデックスとの間のマッピング関係を確立する。ただし、処理後の非テンプレートディメンション決定木の模式図は、図３Ｄに示されてもよい。
【００７２】
互いに同パターンサブルールセットとなる複数の葉ノードのそれぞれに対応するテンプレートディメンション決定木を同一のテンプレートディメンション決定木として合併する。ただし、合併して得られたテンプレートディメンション決定木における葉ノードは、同パターンサブルールセット群における各インデックスに対応する分類ルールを含む。
【００７３】
ただし、ホールフィリングルールに対応する同パターンサブルールセット群がホールフィリングルールという分類ルールのみを含むため、ホールフィリングルールに対応するテンプレートディメンション決定木は、１つのみの葉ノードを含み、且つ当該葉ノードは、当該ホールフィリングルールを直接記録してもよい。
【００７４】
最終的に生成された表１に示す分類ルールセットに対応する決定木の構造は、図３Ｅに示すように、非テンプレートディメンション決定木３１０と、テンプレートディメンション決定木３２０とを備えてもよい。
【００７５】
以下では、実例を組み合わせてパケット分類の具体的な処理フローについて簡単に説明する。
【００７６】
当該実施例では、パケット１とパケット２とにおける各フィールドの値がそれぞれ表３に示される。
【００７７】
【表３】
2020532241.tif 000005
【００７８】
パケット１の検索パスは、図４における実線二重矢印に示すように、ヒットしたテンプレートディメンション決定木３２０における葉ノードに３つの分類ルールであるｒ２、ｒ５とｒ８が含まれる。その通過した非テンプレートディメンション決定木３１０の葉ノードにおけるインデックスが０（図示では、ｓｐｓｒ:０）であるため、パケット１は、最終的に分類ルールｒ２にヒットする。
【００７９】
パケット２の検索パスは、図４における点線二重矢印に示すように、ヒットしたテンプレートディメンション決定木３２０における葉ノードに３つの分類ルールであるｒ０、ｒ３とｒ６が含まれる。その通過した非テンプレートディメンション決定木３１０の葉ノードにおけるインデックスが２（図示では、ｓｐｓｒ:２）であるため、パケット２は、最終的に分類ルールｒ６にヒットする。
【００８０】
上述から分かるように、本発明の実施例に係る技術案では、分類ルールセットの非テンプレートディメンションに基づいて、分類ルールセットに対して決定木を作成して第１タイプ決定木を生成し、分類ルールセットのテンプレートディメンションに基づいて、第１タイプ決定木における各葉ノードに対して決定木を作成して第２タイプ決定木を生成し、さらに第１タイプ決定木における互いに同パターンサブルールセットとなる複数の葉ノードを同一の第２タイプ決定木に関連付けさせることにより、テンプレートディメンションの木作成の繰り返しおよび決定木の規模が有効に低減可能できるため、サポートされる分類ルールセットの規模が増大でき、さらにネットワーク機器の記憶空間利用率およびパケット分類処理能力が向上できる。
【００８１】
以上は、本発明に係る方法を記述した。以下では、本発明に係る装置を記述する。
図５は、本発明の実施例に係るパケット分類決定木確立装置のハードウェア構造の模式図である。当該パケット分類決定木確立装置は、プロセッサ５０１と、機械実行可能な指令が記憶される機械可読記憶媒体５０２とを備える。プロセッサ５０１と機械可読記憶媒体５０２とは、システムバス５０３を介して互いに通信できる。また、プロセッサ５０１は、機械可読記憶媒体５０２におけるパケット分類決定木確立制御論理に対応する機械実行可能な指令を読み取って実行することにより、上述したパケット分類決定木確立方法を実施することができる。
【００８２】
本文で言及される機械可読記憶媒体５０２は、如何なる電気的なもの、磁気的なもの、光学的なものまたは他の物理的記憶装置であってもよく、情報（例えば、実行可能な指令、データ等）を含むか記憶可能である。例えば、機械可読記憶媒体は、揮発性メモリ、不揮発性メモリまたは類似する記憶媒体であってもよい。具体的に、機械可読記憶媒体は、ＲＡＭ（Ｒａｄｏｍ Ａｃｃｅｓｓ Ｍｅｍｏｒｙ、ランダムアクセスメモリ）、フラッシュメモリ、記憶ドライバ（例えば、ハードディスクドライバ）、ソリッド・ステート・ディスク、如何なるタイプの記憶ディスク（例えば、光ディスク等）、または、それらの組み合わせであってもよい。
【００８３】
１つの好適な実施形態では、上記パケット分類決定木確立装置は、ＦＰＧＡ（図示せず）を更に備えてもよく、それ相応に、プロセッサ５０１は、決定木確立を完了した後、確立された決定木をＦＰＧＡへ配布して、ＦＰＧＡに決定木検索処理を実行させる。
【００８４】
図６に示すように、機能上に区分すると、上記パケット分類決定木確立制御論理は、第１決定木作成手段６０１、第２決定木作成６０２と多重化手段６０３を含んでもよい。
【００８５】
第１決定木作成手段６０１は、分類ルールセットの非テンプレートディメンションに基づいて、前記分類ルールセットに対して決定木を作成し、第１タイプ決定木を生成する。前記第１タイプ決定木は、前記分類ルールセットの、前記非テンプレートディメンションに対応する決定木である。
【００８６】
第２決定木作成６０２は、前記分類ルールセットのテンプレートディメンションに基づいて、前記第１タイプ決定木における葉ノードのそれぞれに対して決定木を作成し、第２タイプ決定木を生成する。前記第２タイプ決定木は、前記第１タイプ決定木の葉ノードの、前記テンプレートディメンションに対応する決定木である。
【００８７】
多重化手段６０３は、前記第１タイプ決定木における互いに同パターンサブルールセットとなる複数の葉ノードを同一の第２タイプ決定木に関連付けさせる。互いに同パターンサブルールセットとなる複数の葉ノードのそれぞれに含まれる分類ルールのセットは、互いに同パターンサブルールセットとなる。
【００８８】
前記第１決定木作成手段６０１は、更に、前記非テンプレートディメンションおよび対応する値が前記分類ルールセットにおける分類ルールにマッチングしないとき、分類ルールにマッチングしない葉ノードに含まれる分類ルールをホールフィリングルールとして設定する。前記ホールフィリングルールの優先度は、前記分類ルールセットにおける全ての分類ルールの優先度より低い。
【００８９】
前記第２決定木作成６０２は、更に、互いに同パターンサブルールセットとなる複数の分類ルールサブセットを含む葉ノードが前記第１タイプ決定木に存在するとき、当該葉ノードに含まれる低優先度の分類ルールサブセットを削除する。
【００９０】
前記多重化手段６０３は、更に、互いに同パターンサブルールセットとなる複数の分類ルールサブセットを同一の同パターンサブルールセット群に区分し、前記第１タイプ決定木における互いに同パターンサブルールセットとなる複数の葉ノードの各葉ノードと、対応する分類ルールサブセットの所属する同パターンサブルールセット群の識別子、および、当該分類ルールサブセットの、当該同パターンサブルールセット群におけるインデックスとの間のマッピング関係を確立し、前記第１タイプ決定木における互いに同パターンサブルールセットとなる複数の葉ノードに対応する第２タイプ決定木を同一の第２タイプ決定木として合併する。合併された第２タイプ決定木の葉ノードは、当該同パターンサブルールセット群における各インデックスに対応する分類ルールを含む。
【００９１】
上記パケット分類決定木確立制御論理は、検索手段６０４を更に備えてもよい。検索手段６０４は、分類すべきパケットを受信すると、前記分類すべきパケットに基づいて前記分類ルールセットに対応する第１タイプ決定木を検索することにより、前記分類すべきパケットに対応する、前記第１タイプ決定木における第１対象葉ノードを特定し、前記第１対象葉ノードに記憶される同パターンサブルールセット群の識別子に基づいて対象第２タイプ決定木を特定し、前記分類すべきパケットに基づいて前記対象第２タイプ決定木を検索することにより、前記分類すべきパケットに対応する前記第２タイプ決定木における第２対象葉ノードを特定し、前記第１対象葉ノードに記憶される同パターンサブルールセット群におけるインデックスに基づいて対応する分類ルールを前記第２対象葉ノードから検索し、当該分類ルールを前記分類すべきパケットにマッチングする分類ルールとして特定する。
【００９２】
説明すべきことは、本文に、第１と第２等のような関係用語は、単に１つの実体や操作を別の実体や操作と区分させるために用いられ、これらの実体や操作の間になんらかの実際的な関係や順番が存在するとは必ずしも要求やヒントすることではない。また、用語「含む」、「備える」またはほかの何れかの同義語が非排他的含有をカバーすることを意図する。このように、一シリーズの要素を有する手順、方法、物品または機器は、それらの要素を有するだけではなく、明確に挙げられていない他の要素も有し、またはこのような手順、方法、物品または機器に固有の要素も有する。更なる制限がない限り、語句「１つの…を含む」で限定される要素は、前記要素を有する手順、方法、物品または機器に他の同じ要素を更に有することをあえて排除しない。
【００９３】
上述したのは、本発明の好適な実施例に過ぎず、本発明を制限するためのものではない。本発明の精神及び原則内でなされた如何なる変更、均等物による置換、改良等も、本発明の保護範囲内に含まれる。
【図１】
2020532241.tif 000006
【図２Ａ】
2020532241.tif 000007
【図２Ｂ】
2020532241.tif 000008
【図３Ａ】
2020532241.tif 000009
【図３Ｂ】
2020532241.tif 000010
【図３Ｃ】
2020532241.tif 000011
【図３Ｄ】
2020532241.tif 000012
【図３Ｅ】
2020532241.tif 000013
【図４】
2020532241.tif 000014
【図５】
2020532241.tif 000015
【図６】
2020532241.tif 000016
【国際調査報告】
2020532241.tif 000017
2020532241.tif 000018
2020532241.tif 000019
2020532241.tif 000020