(57)【要約】  チャネルスプリッティング構成において、ルールの組によって定義された複数チャネルの定義に関する曖昧さのチェックを実現する方法である。この方法は、ルールのそれぞれにマークを関連付ける段階と；それぞれのサブルールが、ＡＮＤ、等価、否定というブール演算子のみから選択された１つ又は複数の演算子を有するように、それぞれのルールをサブルールに分割する段階であって、同一のサブルール内において、いくつかの数のこれらの演算子が使用されており、親ルールは、ＯＲブール演算子を使用してサブルールを組み合わせることによって表現可能であり、それぞれのサブルールは、個々の親ルールに関連付けられたマークと関連付けられる段階と；を含んでいる。
2005510958.tif 000002
【特許請求の範囲】
【請求項１】
チャネルスプリッティング構成において複数チャネルの定義に関する曖昧さのチェックを実現する方法であって、これらのチャネルは、前記構成内に内蔵されているルールの組によって定義されている方法において、
複数の親ルールのそれぞれにマークを関連付ける段階と、
それぞれのサブルールが、ＡＮＤ、等価、否定というブール演算子のみから選択された１つ又は複数の演算子を有するように、それぞれのルールをサブルールに分割する段階であって、同一のサブルール内において、いくつかの数のこれらの演算子が使用されており、前記親ルールは、ＯＲブール演算子を使用してサブルールを組み合わせることによって表現可能であり、それぞれのサブルールは、前記個々の親ルールに関連付けられた前記マークと関連付けられる段階と、
を含む方法。
【請求項２】
チャネルスプリッティング構成において複数チャネルの定義に関する曖昧さのチェックを実現する方法であって、これらのチャネルは、前記構成内に内蔵されているルールの組によって定義されている方法において、
複数の親ルールのそれぞれにマークを関連付ける段階と、
それぞれのサブルールが、ＡＮＤ、等価、否定というブール演算子のみから選択された１つ又は複数の演算子を有するように、それぞれのルールをサブルールに分割する段階であって、同一のサブルール内において、いくつかの数のこれらの演算子が使用されており、前記親ルールは、ＯＲブール演算子を使用してサブルールを組み合わせることによって表現可能であり、それぞれのサブルールは、前記個々の親ルールに関連付けられた前記マークと関連付けられる段階と、
前記サブルールのそれぞれをデータ構造に入力する段階であって、前記構造は、分岐構成を有しており、それぞれの節点は、サブルールの等価又は不等条項であり、節点間のそれぞれのリンクは、サブルールからのＡＮＤ演算子であり、節点には、前記構造におけるそれらの位置によって、サブルールの条項を構成するすべての節点を検討することによってのみ到達可能であり、これらの節点も、当該サブルールと関連付けられた前記マークを格納している段階と、
それぞれのサブルールからパケットを生成する段階であって、前記パケットは、該パケットが当該サブルールの要件を満足させるように設定されたパラメータを有しており、その他のすべての可能なパラメータは、有意ではないことを示す値に設定されている段階と、
それぞれのパケットに前記データ構造を検討させる段階であって、前記パケット内の前記パラメータの値がサブルール条項の条件を満足する場合にのみ、当該節点からのリンクの検討を継続し、前記節点がマークを格納していると共に、前記パケットが前記節点内の前記サブルール条項の前記条件を満足させる場合に、前記マークが前記パケットと関連付けられ、この結果、マークと関連付けられたルール間における曖昧さを示すことができる複数の前記マークをパケットが有する結果となった場合に、これらのルールが前記曖昧さを除去するべく再指定されるか、或いは、これらのルールに異なる優先順位が割り当てられるように構成されている段階と、
を含む方法。
【請求項３】
所与のルールから生成された前記パケットによる前記構造の検討が完了した後に、前記データ構造から前記ルールを除去する段階を更に含む請求項２記載のチャネルスプリッティング構成内に内蔵されたルールの組の曖昧さのチェックを実現する方法。
【請求項４】
前記ルールから生成されたパケットが前記データ構造を検討する順序を重み付け係数を使用することによって選択する段階を更に含み、前記重み付け係数は、条件の和であり、それぞれの条件は、前記ルールのパラメータに関連付けられたマスクのビット反転により生成され、選択された係数によって除算される数である請求項３記載の方法。
【請求項５】
前項までの請求項中のいずれか一項記載の方法によって、動作のルールのチェックが既に完了しているパケットスイッチングシステム用のトラフィックスプリッティング構成。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、パケットスイッチング構成におけるトラフィックスプリッタの整合性チェックに関するものである。
【背景技術】
【０００２】
トラフィックスプリッタは、パケットスイッチングシステムにおいて周知である。これらは、到来するパケットのフローを論理的なチャネルに分割するために使用される。チャネルとは、論理的なエンドポイント間における情報フローのことであり、それぞれのチャネルは、パケットの１つ又は複数のパラメータ値に関するルールによって定義されている。チャネルを識別するべく使用可能な代表的なパラメータとしては、発信元アドレス、宛先アドレス、発信元ポート、宛先ポート、及びプロトコルが挙げられるが、その他のものも使用することができる。トラフィックスプリッタは、ファイヤウォール又はＱｏＳ保証構成などのパケットスイッチングシステムのサブシステムにおいて使用可能である。
【０００３】
大部分のトラフィックスプリッタにおいては、マッチングが検出されるまで、到来パケットがルールを順番に検討する。このマッチングルールにより、チャネルが定義されている。通常、１つのルールが、別のルールの実行を妨害するかどうかに関するチェックは行われていない。例えば、ルール１が、宛先アドレス１０．１２８．０．１に向かうものをマッチングパケットと規定し、ルール２が、宛先ポート８０に向かうものをマッチングパケットと規定している場合に、宛先アドレス１０．１２８．０．１及び宛先ポート８０に向かうパケットは、ルール１にマッチングし、ルール２には、到達しないことになる。多数のルールを有する複雑なシステムにおいては、これがユーザーの意図するところではない場合がある。ユーザーに対してこの状況を通知すると共に、ユーザーがこれらのルールの優先順序を明示的に選定できるようになれば、有利であろう。
【０００４】
この構成の更なる欠点は、ルールの検討順序が有意であるかどうかを知ることができず、従って、すべてのケースにおいて、その順序を保持しなければならないことである。この結果、先進的な数学的ツールを使用してチャネルに対するパケットの割当効率を向上させる可能性が大幅に制限されている。
【発明の開示】
【発明が解決しようとする課題】
【０００５】
トラフィックスプリッティングルールの組のチェックを実現すると共に、曖昧なユーザーを可能にする方法及び手段を提供するか、或いは、少なくとも有用な選択肢を提供ことが本発明の目的である。
【課題を解決するための手段】
【０００６】
本発明の一形態は、チャネルスプリッティング構成における複数チャネルの定義に関する曖昧さのチェックを実現する方法であり、これらのチャネルは、この構成内に内蔵されたルールの組によって定義されており、この方法は、複数の親ルールのそれぞれにマークを関連付ける段階と；それぞれのサブルールが、ＡＮＤ、等価、又は否定というブール演算子からのみ選択された１つ又は複数の演算子を有するように、それぞれのルールをサブルールに分割する段階であって、同一のサブルール内には、いくつかの数のこれらの演算子が使用されており、親ルールは、ＯＲブール演算子を使用してサブルールを組み合わせることによって表現可能であり、それぞれのサブルールは、個々の親ルールに関連付けられたマークと関連付けられる段階と；を含んでいる。
【０００７】
本発明の更なる形態は、チャネルスプリッティング構成における複数チャネルの定義に関する曖昧さのチェックを実現する方法であって、これらのチャネルは、この構成内に内蔵されたルールの組によって定義されており、この方法は、複数の親ルールのそれぞれにマークを関連付ける段階と；それぞれのサブルールが、ＡＮＤ、等価、又は否定というブール演算子からのみ選択された１つ又は複数の演算子を有するように、それぞれのルールをサブルールに分割する段階であって、同一のサブルール内には、いくつかの数のこれらの演算子が使用されており、親ルールは、ＯＲブール演算子を使用してサブルールを組み合わせることによって表現可能であり、それぞれのサブルールは、個々の親ルールに関連付けられたマークと関連付けられる段階と；サブルールのそれぞれをデータ構造に入力する段階であって、この構造は、分岐構成を有しており、それぞれの節点は、サブルールの等価又は不等条項であり、節点間のそれぞれのリンクは、サブルールからのＡＮＤ演算子であり、節点には、構造内におけるそれらの位置によって、サブルールの条項を構成するすべての節点を検討することによってのみ到達可能であり、これらの節点も、そのサブルールに関連付けられたマークを格納している段階と；それぞれのサブルールからパケットを生成する段階であって、このパケットは、このパケットがそのサブルールの要件を満足させるように設定されたパラメータを有しており、すべてのその他の可能なパラメータは、有意ではないことを示す値に設定されている段階と；それぞれのパケットに、このデータ構造を検討させる段階であって、パケット内のパラメータの値がサブルールの条項の条件を満足させる場合にのみ、当該節点からのリンクの検討を継続し、節点がマークを格納していると共に、そのパケットが、その節点内のサブルールの条項の条件を満足させる場合に、そのマークがそのパケットと関連付けられ、この結果、マークと関連付けられたルール間における曖昧さを示すことができる複数のマークをパケットが有する結果になった場合に、曖昧さを除去するべくこれらのルールを再指定するか、或いは、異なる優先順位を割り当てることができるように構成されている段階と、を含んでいる。
【０００８】
好ましくは、この方法は、所与のルールから生成されたパケットによる構造の検討が完了した後に、そのルールをデータ構造から除去する段階を更に含んでいる。
【０００９】
好ましくは、この方法は、ルールから生成されたパケットによってデータ構造を検討する順序を重み付け係数を使用して選択する段階を更に含んでおり、この重み付け係数は、条件の和であり、それぞれの条件は、そのルールのパラメータに関連付けられたマスクのビット反転によって生成され、選択された係数によって除算することによって生成される数である。
【００１０】
好ましくは、本発明は、パケットスイッチングシステム用のトラフィックスプリッティング構成の形態を取ることができ、この場合に、動作のルールによって定義されたその論理に対しては、既に前述の方法によるチェックが完了している。
【発明を実施するための最良の形態】
【００１１】
以下、本発明を十分に理解できるように、添付の図面に示されている好適な実施例との関連で、本発明について説明する。
【００１２】
通常のシステムは、それぞれのルールにおけるパラメータの様々な設定に基づいてトラフィックをパケットの論理的なフロー（チャネルと呼ばれるもの）に分割する一連のルールを有している。例えば、ルール１は、トラフィックを分割することにより、宛先アドレス１０．１２８．０．１０に向かうすべてのものをチャネル１に向かわせることができ、ルール２は、トラフィックを分割することにより、発信元アドレス１０．１２８．０．５５から到来したすべてのものをチャネル２に向かわせることができる。これは、トラフィックスプリッティングルールにおける矛盾を強調する例である。即ち、発信元アドレス１０．１２８．０．５５から到来し、宛先アドレス１０．１２８．０．１０に向かうパケットがシステムに入った場合に、システムがパケットをチャネル１又はチャネル２のいずれに配置するべく選定したとしても、等しく正しいということになってしまうのである。これは、解決を要する矛盾を示している。これを解決するには、ルールを設定するユーザーが、優先順位を選択してルールと関連付けるか、或いは、これらの矛盾状態を解消するべくルールを書き直すことになる。
【００１３】
この整合性チェックは、次のように進められる。即ち、まず、それぞれのルールに対して、マークを決定する。例えば、前述のルール１に、マーク１を付与し、ルール２に対しては、マーク２を付与する。次いで、データ構造内に挿入できるように、整合性を有するフォーマットにルールを分割する。それぞれのサブルールは、データ構造における１つの節点を形成することになる。
【００１４】
次いで、それぞれのサブルールから、パラメータとマスクからなるパケットを生成する（これらのパラメータ及びマスクは、その定義されたサブルールに含まれているもののみであり、そのサブルールを満足させる値によって定義されている）。次いで、それぞれのパケットにデータ構造を通過させ、データ構造内において、そのパケットとマッチングする節点に遭遇するたびに、そのパケット内の組の内部に、その節点に固有のマークが配置されることになる。そして、このプロセスの終了時点において、マークの組の内部に複数のマークをパケットが格納している場合には、その組の中の対応するルールの間に矛盾が存在しているということであり、ユーザーに対して、この事実が通知される。
【００１５】
次いで、このパラメータ及びマークからなるパケットを生成する元となったルールが、システムから除去され、このプロセスが、次のルールについて反復される。尚、このルールを除去する順序は、存在し得るすべての矛盾の完全な検索をシステムが実行できる速度に影響を与えることになるが、単純な発見的な方法を判定することにより、アルゴリズムの複雑さに影響を与えることなく、このプロセスを加速することができる。
【００１６】
パケットがトラフィックスプリッティングシステムに入る際に、パケットは、そのパケットが属するチャネルを判定するのに使用可能ないくつかの異なるパラメータを有している。この例としては、発信元アドレス、宛先アドレス、発信元ポート、宛先ポート、及びプロトコルが挙げられるが、本システムは、これらにのみ限定されるものではない。それぞれのパケットはチェックされ、向かうべきチャネルを判定するトラフィックスプリッティングルールにマッチングするかどうかが確認される。そして、パケットが、２つのルールとマッチングした場合には、矛盾が存在しているということであり、ユーザー又はシステムの管理者は、矛盾を解消するべくルールを変更するか、或いは、ルールに対して優先順位を付与することができる。
【００１７】
一例として、次の例を検討してみよう。
【００１８】
チャネルＡのルール：宛先アドレス＝１０．１２８．０．１＆＆宛先ポート＝８０
チャネルＢのルール：宛先ポート＝８０
【００１９】
これは、アドレス１０．１２８．０．１及び宛先ポート８０宛てのパケットがシステム内に到来した場合に、矛盾を呈することになる。チャネルＡのルールとチャネルＢのルールの両方にマッチングしてしまうのである。このため、システム管理者又はユーザーは、ルールの少なくとも１つに対して優位を指定し、矛盾が存在する場合に、他方よりもそのルールを優先して選択するべきである旨を指定する必要がある。
【００２０】
本システムは、ルールが解決不能な矛盾を有している場合（例えば、ルール：宛先アドレス＝１０．１２８．０．１＆＆宛先アドレス＝１０．１２８．０．２）、優先順位なしに指定された２つのルールが矛盾している場合、或いは、同一の優先順位で指定された２つのルールが矛盾している場合に、ユーザーの介入を促すべく警告を発する。
【００２１】
ルールに対して適用可能な演算子は、次のとおりである。
【００２２】
ａ＝＝ｂ（等価）
ａ！＝ｂ（不等）
ａ＆＆ｂ又はａ∧ｂ（論理積）
ａ‖ｂ又はａ∨ｂ（論理和）
！ａ又は¬ａ（否定）
（）（グループ化）
【００２３】
一例として、次のルールを検討してみよう。
【００２４】
（宛先アドレス＝＝１０．１２８．０．１／２５５．２５５．２５５．２５５＆＆発信元アドレス！＝１０．１２８．０．１０／２５５．２５５．２５５．２５５）‖
！（（宛先ポート＝＝８０）＆＆（発信元ポート＝＝５０））
【００２５】
このルールは、「宛先アドレスが、１０．１２８．０．１（マスク２５５．２５５．２５５．２５５）と等しく、且つ発信元アドレスが、１０．１２８．０．１０（マスク２５５．２５５．２５５．２５５）と等しくないか、或いは、宛先ポートが８０と等しくないか、又は発信元ポートが５０と等しくない場合に、そのパケットをマッチングさせる」と規定している。
【００２６】
システム内のそれぞれのルールは、固有のマークを有している。これは、それぞれのルールに対して、固有の整数の識別子を付与することを単に意味している。優先順位を有しているルールは、別の優先順位を有する別のルールと矛盾することがないため、優先順位が割り当てられているルールは、後のために記憶しておく。
【００２７】
この段階で、ルールの迅速な検討を可能にするデータ構造に容易にフィットできるように、それぞれのルールを小さなルールに分割する必要がある。次のルールを検討してみよう。
【００２８】
ルール１：（（Ａ１＝Ｗ１／ＷＭ１＆＆Ａ２＝＝Ｗ２／ＷＭ２＆＆…）＆＆！（Ｂ１＝＝Ｘ１／ＸＭ１＆＆Ｂ２＝＝Ｘ２／ＸＭ２＆＆…））‖（（Ｃ１＝＝Ｙ１／ＹＭ１＆＆Ｃ２＝＝Ｙ２／ＹＭ２＆＆…）＆＆！（Ｄ１＝＝Ｚ１／ＺＭ１＆＆Ｄ２＝＝Ｚ２／ＺＭ２＆＆…）‖…
【００２９】
これを値１によってマーキングする場合には、このスーパールールを次のように別個のサブルールに分割可能であり、これらのサブルールのそれぞれは、そのサブルールが真であると検出された場合に、そのパケットを値１によってマーキングする。
【００３０】
ルール１ａ：（Ａ１＝＝Ｗ１／ＷＭ１＆＆Ａ２＝＝Ｗ２／ＷＭ２＆＆…）＆＆！（Ｂ１＝＝Ｘ１／ＸＭ１＆＆Ｂ２＝＝Ｘ２／ＸＭ２＆＆…）−値１によるマーク
ルール１ｂ：（Ｃ１＝＝Ｙ１／ＹＭ１＆＆Ｃ２＝＝Ｙ２／ＹＭ２＆＆…）＆＆！（Ｄ１＝＝Ｚ１／ＺＭ１＆＆Ｄ２＝＝Ｚ２／ＺＭ２＆＆…）−値１によるマーク
【００３１】
この結果、システムに入って値１によってマーキングされたすべてのパケットには、ルール１が適用されている（それが、ルール１ａ、ルール１ｂ、…によってマーキングされたかどうかは無関係である）。
【００３２】
正式には、サブルールのフォーマットは、次のとおりである。
【００３３】
Ｆ∧（サブ）＝（ａ1＝ｂ1）∧（ａ2＝ｂ2）∧…∧¬（（ａn＝ｂn）∧（ａn+1＝ｂn+1）∧…）
【００３４】
スーパールールのフォーマットは、次のとおりである。
【００３５】
Ｆ∨（スーパー）＝Ｆ∧（サブ1）∨Ｆ∧（サブ2）∨…∨Ｆ∧（サブn）
【００３６】
前述の演算を使用するすべての等式を、次の再帰的に適用されたブール代数のルールを使用し、このフォーマットに変換することができる。
【００３７】
Ｆ（ａ）∧（Ｆ（ｂ）∨Ｆ（ｃ））⇔（Ｆ（ａ）∧Ｆ（ｂ））∨（Ｆ（ａ）∧Ｆ（ｃ））
Ｆ（ａ）∨（Ｆ（ｂ）∧Ｆ（ｃ））⇔（Ｆ（ａ）∨Ｆ（ｂ））∧（Ｆ（ａ）∨Ｆ（ｃ））
¬（Ｆ（ａ）∨Ｆ（ｂ））⇔¬Ｆ（ａ）∧¬Ｆ（ｂ）
¬（Ｆ（ａ）∧Ｆ（ｂ））⇔¬Ｆ（ａ）∨¬Ｆ（ｂ）
（Ｆ（ａ）∨Ｆ（ａ））⇔Ｆ（ａ）
ａ1！＝ａ2⇔¬ａ1＝ａ2
【００３８】
すべてのルールの記述が完了すれば、それらをデータ構造に入力する。図６には、擬似コードにより、このデータ構造が示されている。
【００３９】
図６を参照すれば、マークとは、パケットがルールにマッチングした場合に、そのパケットに付与されるマークのことであり、ｎｅｘｔＭａｒｋｓは、マスクとｎｅｘｔ−ｍａｒｋｅｒへのポインタに対するそれらの関連マップのリストを格納している。マスクは、マップを経る前に、パラメータとＡＮＤ演算される２値ストリングであり、ｎｏｔＥｑｕａｌは、パケットがルールにマッチングするかどうかを判定する前に、発生しないことを確かめるためにチェックする必要のあるルールのリストである。マーク値が検出された際には、このリストを検討し、どのパラメータもマッチングしないことを確認する。そして、マッチングが検出された場合には、そのパケットは、マーキングすることができない。
【００４０】
例示を目的として、パケットが、分類に使用可能な２つのパラメータのみを有しているとしよう（宛先アドレス及び発信元アドレスであり、いずれも３２ビットである）。
【００４１】
以下に、ルールの組の一例を示している。すべてのアドレスは、４ビットの２値で指定されていると仮定する。アドレスとマスクは、「アドレス／マスク」というフォーマットの形態で指定される。
【００４２】
ルール１：宛先アドレス＝１１００／１１１１＆＆発信元アドレス＝１１０１／１１１１−マーク１
ルール２：宛先アドレス＝１１１０／１１１０＆＆発信元アドレス＝１０１０／１１１１−マーク２
ルール３：宛先アドレス＝１０００／１１００＆＆発信元アドレス＝１０１１／１１１１−マーク３
ルール４：宛先アドレス＝１１００／１１１１＆＆発信元アドレス＝１０１０／１１１１−マーク４
ルール５：宛先アドレス＝１１００／１１１０＆＆発信元アドレス＝１１０１／１１１１−マーク５
ルール６：宛先アドレス＝１００１／１１１１
【００４３】
見ればわかるとおり、ルール１とルール５は矛盾しており、宛先アドレス＝１１００及び発信元アドレス１１０１を有するパケットがシステム内に到来すると、両方のルールにマッチングしてしまう。
【００４４】
図２は、図５の擬似コード片によって記述されているデータ構造を表している。
【００４５】
１０１は、Ｔｏｐｌｅｖｅｌの要素である。１０１は、マスク及び関連マップのリスト内における第１の要素である。１１８は、リスト内の次のポインタであり、１０７は、リスト内の次の要素である。１１９は、要素のマップにおける第１のリンクを表している。１０２のタイプは、ＤｅｓｔｉｎａｔｉｏｎＡｄｄｒｅｓｓである。１１００に等しい宛先アドレスを有するパケットがシステム内に入ると、この要素を訪問することになる。これは、又、マスク及び関連マップのリストを同様に格納している。このリスト内における第１要素は１０４である。１０３も、タイプは、ＤｅｓｔｉｎａｔｉｏｎＡｄｄｒｅｓｓである。パケットが検討の際に、このノードを訪問すると、そのパケットのマークの組に６のマークが付加されることになる。１０５は、１０４と関連付けられたマップの第１要素である。このタイプは、ＳｏｕｒｃｅＡｄｄｒｅｓｓである。この節点を訪問するすべてのパケットには、１のマークが付加されることになる。１０６も、タイプは、ＳｏｕｒｃｅＡｄｄｒｅｓｓであり、この節点を訪問するすべてのパケットには、４が付加されることになる。１０７は、ＴｏｐＬｅｖｅｌにおけるマスク及び関連マップのリスト内における第２の要素である。これは、１１１０のマスクにおいてマッチングする要素のマップを格納している。１０８のタイプは、ＤｅｓｔｉｎａｔｉｏｎＡｄｄｒｅｓｓである。これは、マスクが１１１０であるため、ＤｅｓｔｉｎａｔｉｏｎＡｄｄｒｅｓｓ１１１０及び１１１１を有するパケットの訪問を受けることになる。１０９も、タイプはＤｅｓｔｉｎａｔｉｏｎＡｄｄｒｅｓｓであり、ＤｅｓｔｉｎａｔｉｏｎＡｄｄｒｅｓｓ１１００及び１１０１を有するパケットの訪問を受けることになる。１１０は、ＤｅｓｔｉｎａｔｉｏｎＡｄｄｒｅｓｓ要素１０８に関連するマスク及びマップのリスト内における第１要素である。１１１のタイプは、ＳｏｕｒｃｅＡｄｄｒｅｓｓであり、パケットを値２によってマーキングする。これは、ＤｅｓｔｉｎａｔｉｏｎＡｄｄｒｅｓｓが１１１０又は１１１１であり、ＳｏｕｒｃｅＡｄｄｒｅｓｓが１０１０である場合に、発生することになる。１１２は、ＤｅｓｔｉｎａｔｉｏｎＡｄｄｒｅｓｓ要素１０９と関連するマスク及びマップのリスト内における第１要素である。１１３は、タイプがＳｏｕｒｃｅＡｄｄｒｅｓｓであり、パケットを値５によってマーキングする。これは、ＤｅｓｔｉｎａｔｉｏｎＡｄｄｒｅｓｓが１１００又は１１０１であり、ＳｏｕｒｃｅＡｄｄｒｅｓｓが１１０１の場合に、発生することになる。１１４は、ＴｏｐＬｅｖｅｌと関連するマスク及びマップのリスト内における最後の要素である。１１５のタイプは、ＤｅｓｔｉｎａｔｉｏｎＡｄｄｒｅｓｓである。１１６は、１１５と関連するマスク及びマップのリスト内における第１の要素であり、１１７は、タイプがＳｏｕｒｃｅＡｄｄｒｅｓｓであって、訪問を受けた際に、パケットを値３によってマーキングすることになる。
【００４６】
この図２に示されているデータ構造を検討して、その他のルールと矛盾するかどうかを判定可能なパケットをそれぞれのルールごとに生成する。このパケットは、前述のデータ構造内において使用されているそれぞれのパラメータの情報を格納することになる。この例においては、それぞれのパケットは、次のものを必要としている。
【００４７】
宛先アドレス及びマスク
発信元アドレス及びマスク
【００４８】
通常、パラメータの数に制限は存在していない。
【００４９】
次いで、それぞれのパケットが、システム内を通過し、ヒットしたマークを有するそれぞれのノードごとに、マーキングされることになる。矛盾が存在していない場合には、パケットは、１つの番号だけ（当該ルール自体のマーク値）を有することになる。一方、矛盾が存在している場合には、パケットは、複数のマークを有することになり、これらのマークのすべてが互いに矛盾している。尚、マークに異なる優先順位が関連付けられている場合には、それらは矛盾しているとは見なされない。このパケットによるシステムの検討が完了した後に、当該パケットを生成したルールを除去することができるが、これは、その他のすべてのルールの文脈において、当該ルールが既に考慮されているためである。
【００５０】
図６には、ＴｏｐＬｅｖｅｌから始まる検討アルゴリズムが示されている。
【００５１】
ルールの検討順序を正しく設定することが有用である。図６に示されている検討アルゴリズムには、２つのセクションが存在しており、１つは、要素を線形で検討するものであり、もう１つは、要素を対数的に（マップを通じて）検討するものである。従って、線形検索の量を最小化するべく、パケットがシステムを通過する順序を選択することが有用である。データ構造を構築した順序が存在しているため、まず、そのデータ構造における高次の要素の線形検索を除去するべきである。これを実行するには、重み付け関数を使用し、どのルールを検討し除去するべきかを分類する。
【００５２】
まず、データ構造を構築した順序を判定する。前述の例においては、次のように順序を選定している。
【００５３】
宛先アドレス
発信元アドレス
【００５４】
システム内において、ｐ１〜ｐｎが異なるパラメータ（例えば、発信元アドレス及び宛先アドレス）を表し、データ構造は、ｐ１〜ｐｎの順番に（前述の例においては、ＴｏｐＬｅｖｅｌ→ＤｅｓｔｉｎａｔｉｏｎＡｄｄｒｅｓｓ→ＳｏｕｒｃｅＡｄｄｒｅｓｓの順番になっている）構築されていると仮定する。それぞれのｐ１〜ｐｎには、１つのマスクが関連付けられており、これをｍ１〜ｍｎと呼ぶことにする。マスクは、最上位ビットの１から始まり、最下位ビットに向かって連続する１から構成されていると仮定しよう。例えば、次の２つのマスクは有効である（マスクの幅は、４ビットと仮定する）。
【００５５】
１１００
１１１０
【００５６】
しかしながら、次のマスクは有効ではない。
【００５７】
１０１０
１１０１
【００５８】
ＤｅｓｔｉｎａｔｉｏｎＡｄｄｒｅｓｓのｎｅｘｔＭａｒｋｓ＿ｌｉｓｔ内に次のマスクを有しているとしよう。
【００５９】
１１１１−マップ内に６つの要素
１１１０−マップ内に３つの要素
１１００−マップ内に２つの要素
００００−マップ内に１つの要素
【００６０】
目標とするところは、チェックアルゴリズムの線形検索成分を極小化することである。１１１０、１１００、及び００００と関連するマップ内の要素から、検索対象のパケットを選定すれば、１１１０＆１１１１！＝１１１１、１１００＆１１１１！＝１１１１、及び００００＆１１１１！＝１１１１であるため、それらは、すべて、リストの１１１１部分におけるマップに対する線形検索の実行を必要とすることになろう（即ち、ｃｏｍｍｏｎＭａｓｋ！＝ＬｉｓｔＭａｓｋであり、アルゴリズムの線形部分が検討される）。これは、望ましくない。
【００６１】
この代わりに、リストの１１１１部分からパケットを選定すれば、６つのパケットが、すべて、マップ検索法を使用することになり、システムから除去されることになる。次いで、１１１０パケットを使用した場合には、１１１１ルールが既に除去された状態にあるため、線形検索の必要性は依然として存在しない。即ち、パケットの順序に対して十分な配慮を加えることにより、検索アルゴリズムの線形部分を使用する必要性がなくなるのである。本発明者らの目的は、実行する線形検索の数が最も少ないシステムを提供することであり、これを実行するための簡単な方法の１つが、ｍ１〜ｍｎに基づいて重みを算出することである。実行する線形検索の数を極小化するという観点において、重みが低いほど、システムからパケットを除去するのに有用である。この重みは、次の関数を使用して算出することができる。
【００６２】
重み＝＝〜ｍ１／ｗ１＋〜ｍ２／ｗ２＋…＋〜ｍｎ／ｗｍ
【００６３】
ここで、ｗ１〜ｗｎは、通常、昇順であり、システムにおける線形検索の数を極小化するべく選定される。従って、マスク値が大きいほど、即ち、マスクの設定ビット数が大きいほど、返される重みが小さくなり、それが選択され除去される可能性が大きくなることがわかる。一般に、データ構造ツリーにおける上部レイヤは、ツリーの階層構造における下のものに比べて頻繁に検索されるため、最初に除去することが有利であり、ｐ１に関連付けられているマスクの重み係数は、大きなものにする。
【００６４】
ｗ１を１、ｗ２を１０となるように選定すると、６つのルールについて、次の重みが得られる。
【００６５】
ルール１：重み＝００００＋００００＝０
ルール２：重み＝０００１＋００００＝１
ルール３：重み＝００１１＋００００＝３
ルール４：重み＝００００＋００００＝０
ルール５：重み＝０００１＋００００＝１
ルール６：重み＝００００＋００００＝０
【００６６】
従って、パケットの検討順序は、次のようになる。
【００６７】
ルール１、ルール４、ルール６、ルール２、ルール５、ルール３
【００６８】
次に、これらのパケットにシステムを通過させ、どのような矛盾が存在しているかを判定する。そして、これらの矛盾をユーザーに対して提示し、これに対して、ユーザーが、ルールを書き直すか、或いは、ルールに優先順位を設定して、その矛盾を回避することになる。これを実行するためのメカニズムについては、既に提示済みであり、従って、ここでは、様々なルールについて、システムを通過するパケットを調査し、矛盾を検出してみよう。以下、システムを通過するルール１及びルール４について調査し、システムの動作方法について示すこととする。
【００６９】
まず、ルール１から始めるが、これは、（宛先アドレス＝１１００マスク１１１１、発信元アドレス＝１１０１マスク１１１１）というパケットを有している。
【００７０】
図２において、位置１０１から開始する。宛先アドレスマスクとリストマスクの積は、リストマスクと等しく（１１１１＆１１１１＝＝１１１１）、従って、位置１０１に関連付けられたマップのマップ検索法を使用することができる。この結果、位置１０２に移動することになる。そして、これを辿って、位置１０４に進む。発信元アドレスマスクとリストマスクの積は、リストマスクと等しく（１１１１＆１１１１＝＝１１１１）、従って、マップ検索法を使用することができる。この結果、位置１０５に移動し、パケットが値１によってマーキングされる。この段階で、ツリーのこの分岐はすべて終了している。従って、次に、位置１０７に移動する。宛先アドレスマスクとリストマスクの積は、リストマスクと等しいため（１１１１＆１１１０＝＝１１１０）、この場合にも、マップ検討法を使用することができる。この結果、位置１０９に移動する。そして、これを辿って、位置１１２に進む。発信元アドレスマスクとリストマスクの積は、リストマスクと等しいため（１１１１＆１１１１＝１１１１）、マップ検討法を使用することができる。この結果、位置１１３に移動し、パケットが値５によってマーキングされることになる。この段階で、ツリーのこの部分はすべて終了しているため、位置１１４に移動する。宛先アドレスマスクとリストマスクの積は、リストマスクと等しいため（１１１１＆１１００＝１１００）、我々は、この場合にも、マップ検討法を使用することができる。これ以上のマッチングは存在していない。
【００７１】
このパケットには、１と５の両方によってマーキングされているため、ルール１及び５が矛盾していると判断することが可能であり、ユーザーに対して、これを報告することになる。
【００７２】
この結果、システムからこのルールが除去され、図３が得られる。
【００７３】
２０４と２０６の間の要素（以前の図２における１０５）が存在していないことに留意されたい。この段階では、ルール１が既に除去されており、続いて、ルール４のパケットにシステムを通過させることができる。このパケットは、次の形態で構成されている。
【００７４】
（宛先アドレス＝１１００マスク１１１１、発信元アドレス＝１０１０マスク１１１１）
【００７５】
図３において、位置２０１から開始する。宛先マスクとリストマスクの積は、リストマスクと等しく（１１１１＆１１１１＝＝１１１１）、従って、位置１に関連付けられたマップのマップ検索法を使用することができる。この結果、位置２０２に移動することになる。そして、これを辿って、位置２０４に進む。発信元アドレスマスクとリストマスクの積は、リストマスクに等しく（１１１１＆１１１１＝＝１１１１）、従って、マップ検索法を使用することができる。この結果、位置２０６に移動し、パケットが値４によってマーキングされることになる。この段階で、ツリーのこの分岐はすべて終了している。従って、位置２０７に進む。宛先マスクとリストマスクの積は、リストマスクに等しく（１１１１＆１１１０＝＝１１１０）、従って、この場合にも、マップ検討法を使用することができる。この結果、位置２０９に移動することになる。そして、これを辿って、位置２１２に進む。宛先アドレスマスクとリストマスクの積は、リストマスクに等しく（１１１１＆１１１１＝１１１１）、従って、マップ検討法を使用することができる。これ以上のマッチングは存在しておらず、ツリーのこの部分はすべて終了している。従って、この段階で、位置２１４に移動する。宛先アドレスマスクとリストマスクの積は、リストマスクに等しく（１１１１＆１１００＝１１００）、従って、この場合にも、マップ検討法を使用することができる。これ以上のマッチングは存在していない。１つのマッチングを検出しただけであるため、ルール４とその他のルールの間には、矛盾は存在していない。次いで、図４に示されているように、システムからルール４が除去される。尚、位置２０５及び２０６における要素がなくなっているため、位置２０４及び２０２における要素も除去可能であることに留意されたい。
【００７６】
続いて、その他のルールについても同一の方式で処理される。これらを同様に処理することにより、チェックアルゴリズムの線形部分を実行する必要がなく、且つ、矛盾がルール１と５の間にのみ存在していることが判明する。
【図面の簡単な説明】
【００７７】
【図１】トラフィックをパケットの様々な論理フロー（チャネル）に分割することを必要とするシステムの概略システム図を示している。
【図２】データ構造内においてトラフィックを分割するルールの組の一例を示している。
【図３】図２と同一のルールの例を示しているが、ルールの中の１つが除去されている。
【図４】図３と同一のルールの例を示しているが、ルールの中の１つが除去されている。
【図５】ルールを配置するデータ構造の擬似コードによる記述例を示している。
【図６】データ構造検討アルゴリズムの擬似コードによる記述例を示している。
【図１】
2005510958.tif 000003
【図２】
2005510958.tif 000004
【図３】
2005510958.tif 000005
【図４】
2005510958.tif 000006
【図５】
2005510958.tif 000007
【図６】
2005510958.tif 000008
【国際調査報告】
2005510958.tif 000009
2005510958.tif 000010
2005510958.tif 000011