(57)【特許請求の範囲】
【請求項１】
コンピュータ・システム内で複数のフィルタ規則を試験するための方法であって、
前記複数のフィルタ規則がキーとともに使用され、前記複数のフィルタ規則のそれぞれが複数のビットを使用して記述可能で、前記複数のビットが少なくとも１つのバイナリ値、少なくとも１つのワイルドカード、および少なくとも１つの境界記号を含むことが可能で、前記複数のフィルタ規則の内のフィルタ規則の前記少なくとも１つのバイナリ値がゼロまたは１であることが可能で、前記複数のビットが前記キーの部分に対応し、
（ａ）前記複数のビットの部分に対して前記キーを試験することにより、前記キーがマッチすることができる前記複数のフィルタ規則の部分を選択するステップであって、前記複数のビットの前記部分の第１ビットが、前記複数のフィルタ規則に対する前記少なくとも１つのバイナリ記号の第１最大数を有し、前記複数のビットの前記部分の各後続ビットが、複数の残りのビットに対する前記少なくとも１つのバイナリ記号の第２最大数を有し、かつ前記複数のビットの前記部分の中の先行するビットの試験に基づいて選択されるステップと、
（ｂ）前記複数の規則の前記部分を前記キーに対して試験するステップとを含み、
前記選択するステップ（ａ）は、（ａ１）決定ツリーおよび複数のビットの部分を使用して、キーがマッチすることができる、前記複数のフィルタ規則の前記部分を選択するステップを有し、さらに、
前記決定ツリーが複数のノードおよび複数のリーフを含み、前記複数のフィルタ規則の前記部分が、前記複数のリーフの少なくとも１つのリーフ上にあり、前記複数のノードの第１ノードが、前記複数のフィルタ規則のそれぞれに対する前記複数のビットの前記第１ビットに対応し、前記第１ビットが前記複数のフィルタ規則に対する前記少なくとも１つのバイナリ記号の第１最大数を有し、前記複数のノードの各後続ノードが、前記複数のフィルタ規則のそれぞれに対する第２の複数の残りのビットの中の１ビットに対応し、前記ビットが、前記複数の残りのビットに対する前記少なくとも１つのバイナリ記号の第２最大数を有する、方法。
【請求項２】
さらに、（ｃ）決定ツリーを提供するステップを含み、
前記決定ツリーを提供するステップが、
（ｃ１）複数の行および複数の列を有する第１行列を提供するステップであって、前記複数の行のそれぞれが、前記複数のフィルタ規則の中の１つのフィルタ規則に対応し、前記複数の列のそれぞれが、前記複数のフィルタ規則に対する前記複数のビットのなかの１つのビットに対応するステップと、
（ｃ２）前記複数のビットのなかの前記第１ビットを使用して、前記複数のノードの第１ノードを提供するステップであって、前記第１ビットが、前記複数のフィルタ規則に対する前記少なくとも１つのバイナリ記号の前記第１最大数を有する前記第１行列の中の１つの列に対応するステップと、
（ｃ３）第２行列を前記第１行列に基づいて提供するステップであって、前記第２行列は、前記列内のバイナリ記号がゼロである場合には前記列内の前記バイナリ記号に対するワイルドカードを含め、行に対する前記列内のバイナリ記号が１である場合には前記第１行列のなかの前記行を除外するステップと、
（ｃ４）第３行列を前記第１行列に基づいて提供するステップであって、前記第３行列は、前記列内のバイナリ記号が１である場合には前記列内の前記バイナリ記号に対するワイルドカードを含め、行に対する前記列内のバイナリ記号がゼロである場合には前記第１行列のなかの前記行を除外するステップと、
（ｃ５）前記複数のノードが提供されるまで、前記第２行列および第３行列のそれぞれに対して、ステップ（ｃ２）ないし（ｃ４）を繰り返すステップと
を含む、請求項１に記載の方法。
【請求項３】
前記第１行列を提供するステップ（ｃ１）が、（ｃ１ｉ）前記複数のフィルタ規則のそれぞれの優先順位に基づいて、前記複数のフィルタ規則にランク付けするステップをさらに含む請求項２に記載の方法。
【請求項４】
前記第１行列を提供するステップ（ｃ１）が、（ｃ１ｉ）前記複数のフィルタ規則のそれぞれのタイプに基づいて、前記複数のフィルタ規則にランク付けするステップをさらに含む請求項２に記載の方法。
【請求項５】
前記第１行列を提供するステップ（ｃ１）が、（ｃ１ｉ）前記複数のフィルタ規則のそれぞれのタイプおよび前記複数のフィルタ規則のそれぞれの優先順位に基づいて、前記複数のフィルタ規則にランク付けするステップをさらに含む請求項２に記載の方法。
【請求項６】
前記第１行列、第２行列、および第３行列が、同一タイプを有する一対の複製行を有することができ、前記一対の複製行の第１行がより高い優先順位を有し、前記一対の複製行の第２行がより低い優先順位を有し、前記一対の複製行のどちらの行も境界記号を有さず、前記第１行列、第２行列、および第３行列が、前記第２行を除去することによってさらに提供される請求項２に記載の方法。
【請求項７】
前記キーがさらに複数のフィールドを含み、かつ前記複数のフィルタ規則のそれぞれに対する前記複数のビットが、前記複数のフィールドのなかの１つのフィールドに対応する請求項１に記載の方法。
【請求項８】
前記複数のフィルタ規則が、前記複数のフィールドの残りのフィールドに対応する第２番目の複数のビットによってさらに記述され、
（ｃ）前記第２番目の複数のビットの部分を使用して、前記複数のフィールドの前記残りのフィールドに対して、前記ステップ（ａ）および（ｂ）を繰り返すステップをさらに含む請求項７に記載の方法。
【請求項９】
前記決定ツリーが、前記複数のノードのなかの少なくとも１つの特定のノードからの、少なくとも１つのサブツリーの少なくとも開始ノードに対する少なくとも１つのポインタを含み、これによって、前記少なくとも１つのサブツリーを、単一ノードより多くのノードでも使用できるようにする請求項２に記載の方法。
【請求項１０】
前記複数のフィルタ規則が、複数のタイプのものである請求項１に記載の方法。
【請求項１１】
コンピュータ・システム内で複数のフィルタ規則を試験するための決定ツリーを提供するための方法であって、前記決定ツリーが複数のノードおよび複数のリーフを含み、前記複数のフィルタ規則がキーとともに使用され、前記複数のフィルタ規則のそれぞれが、複数のビットを使用して記述可能であり、前記複数のビットが、少なくとも１つのバイナリ値、少なくとも１つのワイルドカード、および少なくとも１つの境界記号を含むことができ、前記複数のフィルタ規則のなかの１つのフィルタ規則の前記少なくとも１つのバイナリ値が、ゼロまたは１であることが可能で、前記複数のビットが前記キーの部分に対応し、
（ａ）複数の行および複数の列を有する第１行列を提供するステップであって、前記複数の行のそれぞれが、前記複数のフィルタ規則のなかの１つのフィルタ規則に対応し、前記複数の列のそれぞれが、前記複数のフィルタ規則に対する前記複数のビットのなかの１つのビットに対応するステップと、
（ｂ）前記複数のビットのなかの第１ビットを使用して、前記複数のノードの第１ノードを提供するステップであって、前記第１ビットが、前記複数のフィルタ規則に対する前記少なくとも１つのバイナリ記号の第１最大数を有する前記第１行列のなかの１つの列に対応するステップと、
（ｃ）第２行列を前記第１行列に基づいて提供するステップであって、前記第２行列は、前記列内のバイナリ記号がゼロである場合には前記列内の前記バイナリ記号に対するワイルドカードを含め、行に対する前記列内のバイナリ記号が１である場合には、前記第１行列のなかの前記行を除外するステップと、
（ｄ）第３行列を前記第１行列に基づいて提供するステップであって、前記第３行列は、前記列内のバイナリ記号が１である場合には前記列内の前記バイナリ記号に対するワイルドカードを含め、行に対する前記列内のバイナリ記号がゼロである場合には、前記第１行列のなかの前記行を除外するステップと、
（ｅ）前記複数のノードが提供されるまで、前記第２行列および前記第３行列のそれぞれに対して、前記ステップ（ｂ）ないし（ｄ）を繰り返すステップとを含む方法。
【請求項１２】
前記第１行列を提供するステップ（ａ）が、（ａ１）複数のフィルタ規則のそれぞれの優先順位に基づいて、前記複数のフィルタ規則にランク付けするステップをさらに含む請求項１１に記載の方法。
【請求項１３】
前記第１行列を提供するステップ（ａ）が、（ａ２）前記複数のフィルタ規則のそれぞれのタイプに基づいて、前記複数のフィルタ規則にランク付けするステップをさらに含む請求項１１に記載の方法。
【請求項１４】
前記第１行列を提供するステップ（ａ）が、（ａ３）前記複数のフィルタ規則のそれぞれのタイプおよび前記複数のフィルタ規則のそれぞれの優先順位に基づいて、前記複数のフィルタ規則にランク付けするステップをさらに含む請求項１１に記載の方法。
【請求項１５】
前記第１行列、第２行列、および第３行列が、同一タイプを有する一対の複製行を有することができ、前記一対の複製行の第１行がより高い優先順位を有し、前記一対の複製行の第２行がより低い優先順位を有し、前記一対の複製行のどちらの行も境界記号を有さず、前記第１行列、第２行列、および第３行列が、前記第２行を除去することによってさらに提供される請求項１１に記載の方法。
【請求項１６】
前記キーがさらに複数のフィールドを含み、かつ前記複数のフィルタ規則のそれぞれに対する前記複数のビットが、前記複数のフィールドのなかの１つのフィールドに対応する請求項１２に記載の方法。
【請求項１７】
前記複数のフィルタ規則が、前記複数のフィールドの残りのフィールドに対応する第２番目の複数のビットによってさらに記述される方法であって、かつ
（ｆ）前記第２番目の複数のビットの部分を使用して、前記複数のフィールドの前記残りのフィールドに対して、前記ステップ（ａ）ないし（ｅ）を繰り返し、これによって前記複数のフィールドに対する複数の決定ツリーを提供するステップをさらに含む請求項１６に記載の方法。
【請求項１８】
（ｆ）少なくとも１つの別のサブツリーの少なくとも開始ノードに向かう、少なくとも１つの特定のサブツリーの少なくとも１つの特定のノードからの少なくとも１つのポインタで、前記少なくとも１つの特定のサブツリーを置換え、これによって前記少なくとも１つの別のサブツリーを、前記少なくとも１つの特定のサブツリーの代わりに使用できるようにするステップをさらに含む請求項１１に記載の方法。
【請求項１９】
コンピュータ・システム内で複数のフィルタ規則を試験するためのプログラムを含むコンピュータ可読媒体であって、
前記複数のフィルタ規則がキーとともに使用され、前記複数のフィルタ規則のそれぞれが複数のビットを使用して記述可能で、前記複数のビットが少なくとも１つのバイナリ値、少なくとも１つのワイルドカード、および少なくとも１つの境界記号を含むことが可能で、前記複数のフィルタ規則の１つのフィルタ規則の前記少なくとも１つのバイナリ値がゼロまたは１であり、前記複数のビットが前記キーの部分に対応し、
前記プログラムが、
（ａ）前記複数のビットの部分に対して前記キーを試験することにより、前記キーがマッチすることができる前記複数のフィルタ規則の部分を選択する命令であって、前記複数のビットの前記部分の第１ビットが前記複数のフィルタ規則に対する前記少なくとも１つのバイナリ記号の第１最大数を有し、前記複数のビットの前記部分の各後続ビットが、複数の残りのビットに対する前記少なくとも１つのバイナリ記号の第２最大数を有し、かつ前記複数のビットの前記部分の中の先行するビットの試験に基づいて選択される命令と、
（ｂ）前記複数の規則の前記部分を前記キーに対して試験する命令とを含み、
選択する前記命令（ａ）が、
（ａ１）決定ツリーおよび前記複数のビットの前記部分を使用して、キーがマッチすることができる、複数のフィルタ規則の前記部分を選択する命令であって、前記決定ツリーが複数のノードおよび複数のリーフを含み、前記複数のフィルタ規則の前記部分が前記複数のリーフの少なくとも１つのリーフ上にあり、前記複数のノードの第１ノードが、前記複数のフィルタ規則のそれぞれに対する前記複数のビットの前記第１ビットに対応し、前記第１ビットが前記複数のフィルタ規則に対する前記少なくとも１つのバイナリ記号の第１最大数を有し、前記複数のノードの各後続ノードが、前記複数のフィルタ規則のそれぞれに対する第２番目の複数の残りのビットの中の１ビットに対応し、前記ビットが、前記複数の残りのビットに対する前記少なくとも１つのバイナリ記号の第２最大数を有する命令をさらに含む、コンピュータ可読媒体。
【請求項２０】
前記プログラムが、
（ｃ）決定ツリーを提供する
命令をさらに含み、前記決定ツリーを提供する命令が、
（ｃ１）複数の行および複数の列を有する第１行列を提供する命令であって、前記複数の行のそれぞれが、前記複数のフィルタ規則のなかの１つのフィルタ規則に対応し、前記複数の列のそれぞれが、前記複数のフィルタ規則に対する前記複数のビットのなかの１つのビットに対応する命令と、
（ｃ２）前記複数のビットのなかの前記第１ビットを使用して、前記複数のノードの第１ノードを提供する命令であって、前記第１ビットが、前記複数のフィルタ規則に対する前記少なくとも１つのバイナリ記号の前記第１最大数を有する前記第１行列のなかの１つの列に対応する命令と、
（ｃ３）第２行列を前記第１行列に基づいて提供する命令であって、前記第２行列は、前記列内のバイナリ記号がゼロである場合には前記列内の前記バイナリ記号に対するワイルドカードを含め、行に対する前記列内のバイナリ記号が１である場合には、前記第１行列のなかの前記行を除外する命令と、
（ｃ４）第３行列を前記第１行列に基づいて提供する命令であって、前記第３行列は、前記列内のバイナリ記号が１である場合には前記列内の前記バイナリ記号に対するワイルドカードを含め、行に対する前記列内のバイナリ記号がゼロである場合には、前記第１行列のなかの前記行を除外する命令と、
（ｃ５）前記複数のノードが提供されるまで、前記第２行列および第３行列のそれぞれに対して、命令（ｃ２）ないし（ｃ４）を繰り返す命令とを含む請求項１９に記載のコンピュータ可読媒体。
【請求項２１】
前記第１行列を提供する命令（ｃ１）が、
（ｃ１ｉ）前記複数のフィルタ規則のそれぞれの優先順位に基づいて、前記複数のフィルタ規則にランク付けする命令をさらに含む請求項２０に記載のコンピュータ可読媒体。
【請求項２２】
前記第１行列を提供する命令（ｃ１）が、
（ｃ１ｉ）前記複数のフィルタ規則のそれぞれのタイプに基づいて、前記複数のフィルタ規則にランク付けする命令をさらに含む請求項２０に記載のコンピュータ可読媒体。
【請求項２３】
前記第１行列を提供する命令（ｃ１）が、
（ｃ１ｉ）前記複数のフィルタ規則のそれぞれのタイプおよび前記複数のフィルタ規則のそれぞれの優先順位に基づいて、前記複数のフィルタ規則にランク付けする命令をさらに含む請求項２０に記載のコンピュータ可読媒体。
【請求項２４】
前記決定ツリーが、前記複数のノードのなかの少なくとも１つの特定のノードからの、少なくとも１つのサブツリーの少なくとも開始ノードに対する少なくとも１つのポインタを含み、これによって、前記少なくとも１つのサブツリーを、単一ノードより多くのノードでも使用できるようにする請求項２０に記載のコンピュータ可読媒体。
【請求項２５】
コンピュータ・システム内で複数のフィルタ規則を試験するための決定ツリーを提供するためのプログラムを含むコンピュータ可読媒体であって、前記決定ツリーが複数のノードおよび複数のリーフを含み、前記複数のフィルタ規則がキーとともに使用され、前記複数のフィルタ規則のそれぞれが、複数のビットを使用して記述可能であり、前記複数のビットが、少なくとも１つのバイナリ値、少なくとも１つのワイルドカード、および少なくとも１つの境界記号を含むことができ、前記複数のフィルタ規則のなかの１つのフィルタ規則の前記少なくとも１つのバイナリ値が、ゼロまたは１であることが可能で、前記複数のビットが前記キーの部分に対応し、
前記プログラムが、
（ａ）複数の行および複数の列を有する第１行列を提供する命令であって、前記複数の行のそれぞれが、前記複数のフィルタ規則のなかの１つのフィルタ規則に対応し、前記複数の列のそれぞれが、前記複数のフィルタ規則に対する前記複数のビットのなかの１つのビットに対応する命令と、
（ｂ）前記複数のビットのなかの第１ビットを使用して前記複数のノードの第１ノードを提供する命令であって、前記第１ビットが、前記複数のフィルタ規則に対する前記少なくとも１つのバイナリ記号の第１最大数を有する第１行列のなかの１つの列に対応する命令と、
（ｃ）第２行列を前記第１行列に基づいて提供する命令であって、前記第２行列は、前記列内のバイナリ記号がゼロである場合には前記列内の前記バイナリ記号に対するワイルドカードを含め、行に対する前記列内のバイナリ記号が１である場合には、前記第１行列のなかの前記行を除外する、命令と、
（ｄ）第３行列を前記第１行列に基づいて提供する命令であって、前記第３行列は、前記列内のバイナリ記号が１である場合には前記列内の前記バイナリ記号に対するワイルドカードを含め、行に対する前記列内のバイナリ記号がゼロである場合には、前記第１行列のなかの前記行を除外する命令と、
（ｅ）前記複数のノードが提供されるまで、前記第２行列および第３行列のそれぞれに対して、前記ステップ（ｂ）ないし（ｄ）を繰り返す命令とを含む媒体。
【請求項２６】
コンピュータ・システム内で複数のフィルタ規則を試験するためのシステムであって、
前記複数のフィルタ規則がキーとともに使用され、前記複数のフィルタ規則のそれぞれが複数のビットを使用して記述可能で、前記複数のビットが少なくとも１つのバイナリ値、少なくとも１つのワイルドカード、および少なくとも１つの境界記号を含むことが可能で、前記複数のフィルタ規則の前記少なくとも１つのバイナリ値がゼロまたは１であり、前記複数のビットが前記キーの部分に対応し、
データを伝送し、受信するための複数のホストと、
前記複数のビットの部分に対して前記キーを試験することによって、キーがマッチすることができる前記複数のフィルタ規則の部分を選択するための交換器であって、前記複数のビットの部分の第１ビットが前記複数のフィルタ規則に対する前記少なくとも１つのバイナリ記号の第１最大数を有し、前記複数のビットの前記部分の各後続ビットが、複数の残りのビットに対する前記少なくとも１つのバイナリ記号の第２最大数を有し、かつ前記複数のビットの前記部分の中の先行するビットの試験に基づき、前記複数の規則の前記部分を前記キーに対して試験するために選択される交換器とを含み、
前記交換器が決定ツリーを含み、
前記決定ツリーは複数のノードおよび複数のリーフを含み、前記複数のフィルタ規則の前記部分が前記複数のリーフの少なくとも１つのリーフ上にあり、前記複数のノードの第１ノードが、前記複数のフィルタ規則のそれぞれに対する前記複数のビットの前記第１ビットに対応し、前記第１ビットが前記複数のフィルタ規則に対する前記少なくとも１つのバイナリ記号の第１最大数を有し、前記複数のノードの各後続ノードが、前記複数のフィルタ規則のそれぞれに対する第２番目の複数の残りのビットの中の１ビットに対応し、前記ビットが、前記複数の残りのビットに対する前記少なくとも１つのバイナリ記号の第２最大数を有する、システム。
【請求項２７】
前記決定ツリーを提供するための制御ポイントをさらに含み、前記決定ツリーの提供が、複数の行および複数の列を有する第１行列を提供するステップであって、前記複数の行のそれぞれが、前記複数のフィルタ規則のなかの１つのフィルタ規則に対応し、前記複数の列のそれぞれが、前記複数のフィルタ規則に対する前記複数のビットのなかの１つのビットに対応するステップと、前記複数のビットの前記第１ビットを使用して前記複数のノードの第１ノードを提供するステップであって、前記第１ビットが、前記複数のフィルタ規則に対する前記少なくとも１つのバイナリ記号の前記第１最大数を有する前記第１行列のなかの１つの列に対応するステップと、第２行列を前記第１行列に基づいて提供するステップであって、前記第２行列は、前記列内のバイナリ記号がゼロである場合、前記列内の前記バイナリ記号に対してワイルドカードを含め、行に対する前記列内のバイナリ記号が１である場合、前記第１行列の前記行を除外するステップと、第３行列を前記第１行列に基づいて提供するステップであって、前記第３行列は、前記列内のバイナリ記号が１である場合、前記列内の前記バイナリ記号に対してワイルドカードを含め、行に対する前記列内のバイナリ記号がゼロである場合、前記第１行列の前記行を除外するステップと、前記決定ツリー上で前記複数の規則の前記部分を分離することができるまで、前記第２行列および第３行列に対して、前記列を選択するステップ、ノードを提供するステップ、前記第２行列を提供するステップ、および前記第３行列を提供するステップを繰り返すステップとによって行われる、請求項２６に記載のシステム。
【請求項２８】
前記複数のフィルタ規則のそれぞれの優先順位に基づいて、前記複数のフィルタ規則にランク付けすることによって、前記第１行列が提供される請求項２７に記載のシステム。
【請求項２９】
前記複数のフィルタ規則のそれぞれのタイプに基づいて、前記複数のフィルタ規則にランク付けすることによって、前記第１行列が提供される請求項２７に記載のシステム。
【請求項３０】
前記複数のフィルタ規則のそれぞれのタイプおよび前記複数のフィルタ規則のそれぞれの優先順位に基づいて、前記複数のフィルタ規則にランク付けすることによって、前記第１行列が提供される請求項２７に記載のシステム。
【請求項３１】
前記第１行列、第２行列、および第３行列が、同一タイプを有する一対の複製行を有することができ、前記一対の複製行の第１行がより高い優先順位を有し、前記一対の複製行の第２行がより低い優先順位を有し、前記一対の複製行のどちらの行も境界記号を有さず、前記第１行列、第２行列、および第３行列が、前記第２行を除去することによってさらに提供される請求項２７に記載のシステム。
【請求項３２】
前記キーがさらに複数のフィールドを含み、かつ前記複数のフィルタ規則のそれぞれに対する前記複数のビットが、前記複数のフィールドのなかの１つのフィールドに対応する請求項２６に記載のシステム。
【請求項３３】
前記複数のフィルタ規則が、前記複数のフィールドの残りのフィールドに対応する第２番目の複数のビットによってさらに記述され、かつ交換器が、前記複数のフィルタ規則の部分を選択すること、ならびに、前記第２番目の複数のビットの部分を使用して、前記複数のフィールドの前記残りのフィールドに対して、前記複数のフィルタ規則の前記部分を試験することを繰り返す、請求項３２に記載のシステム。
【請求項３４】
前記決定ツリーが、前記複数のノードのなかの少なくとも１つの特定のノードからの、少なくとも１つのサブツリーの少なくとも開始ノードに対する少なくとも１つのポインタを含み、これによって、前記少なくとも１つのサブツリーを、単一ノードより多くのノードで使用できるようにする請求項２７に記載のシステム。
【請求項３５】
前記複数のフィルタ規則が、複数のタイプのものであり得る請求項２６に記載のシステム。
【請求項３６】
コンピュータ・システム内で複数のフィルタ規則を試験するためのシステムであって、前記複数のフィルタ規則がキーとともに使用され、前記複数のフィルタ規則のそれぞれが複数のビットを使用して記述可能で、前記複数のビットが少なくとも１つのバイナリ値、少なくとも１つのワイルドカード、および少なくとも１つの境界記号を含むことが可能で、前記複数のフィルタ規則の１つのフィルタ規則の前記少なくとも１つのバイナリ値がゼロまたは１であり、前記複数のビットが前記キーの部分に対応し、
データを伝送し、受信するための複数のホストと、
決定ツリーを提供するための制御ポイントと、
前記複数のホストおよび前記複数のフィルタ規則を試験するための前記制御ポイントに結合された論理とを含み、
前記論理が、複数のノードおよび複数のリーフを有する決定ツリーを含み、
前記決定ツリーの提供が、複数の行および複数の列を有する第１行列を提供するステップであって、前記複数の行のそれぞれが、前記複数のフィルタ規則のなかの１つのフィルタ規則に対応し、前記複数の列のそれぞれが、前記複数のフィルタ規則に対する前記複数のビットのなかの１つのビットに対応するステップと、前記複数のビットの第１ビットを使用して前記複数のノードの第１ノードを提供するステップであって、前記第１ビットが前記複数のフィルタ規則に対する前記少なくとも１つのバイナリ記号の第１最大数を有する前記第１行列のなかの１つの列に対応するステップと、第２行列を前記第１行列に基づいて提供するステップであって、前記第２行列は、前記列内のバイナリ記号がゼロである場合、前記列内の前記バイナリ記号に対してワイルドカードを含め、行に対する前記列内のバイナリ記号が１である場合、前記第１行列の前記行を除外するステップと、第３行列を前記第１行列に基づいて提供するステップであって、前記第３行列は、前記列内のバイナリ記号が１である場合、前記列内の前記バイナリ記号に対してワイルドカードを含め、行に対する前記列内のバイナリ記号がゼロである場合、前記第１行列の前記行を除外するステップと、前記第２行列および第３行列に対して、前記列を選択するステップ、第２行列を提供するステップ、および第３行列を提供するステップを繰り返して、前記決定ツリーに対して複数の残りのノードを提供するステップとによって行われるシステム。
【請求項３７】
前記複数のフィルタ規則のそれぞれの優先順位に基づいて、前記複数のフィルタ規則にランク付けすることによって、前記第１行列が提供される請求項３６に記載のシステム。
【請求項３８】
前記複数のフィルタ規則のそれぞれのタイプに基づいて、前記複数のフィルタ規則にランク付けすることによって、前記第１行列が提供される請求項３６に記載のシステム。
【請求項３９】
前記複数のフィルタ規則のそれぞれのタイプおよび前記複数のフィルタ規則のそれぞれの優先順位に基づいて、前記複数のフィルタ規則にランク付けすることによって、前記第１行列が提供される請求項３６に記載のシステム。
【請求項４０】
前記キーがさらに複数のフィールドを含み、かつ前記複数のフィルタ規則のそれぞれに対する前記複数のビットが、前記複数のフィールドのなかの１つのフィールドに対応する請求項３６に記載のシステム。
【請求項４１】
前記第１行列、第２行列、および第３行列が、同一タイプを有する一対の複製行を有することができ、前記一対の複製行の第１行がより高い優先順位を有し、前記一対の複製行の第２行がより低い優先順位を有し、前記一対の複製行のどちらの行も境界記号を有さず、前記第１行列、第２行列、および第３行列が、前記第２行を除去することによってさらに提供される請求項３６に記載のシステム。
【請求項４２】
決定ツリーが、少なくとも１つの別のサブツリーの少なくとも開始ノードに向かう、少なくとも１つの特定のサブツリーの少なくとも１つの特定のノードからの少なくとも１つのポインタで、前記少なくとも１つの特定のサブツリーを置換えることによって形成され、これによって前記少なくとも１つの別のサブツリーを、前記少なくとも１つの特定のサブツリーの代わりに使用できるようにする請求項３６に記載のシステム。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、コンピュータ・システムに関するものであり、より詳細には、より効率的にフィルタ規則を試験するための方法およびシステムに関する。
【０００２】
【従来の技術】
図１は、インターネット３０に接続することができる従来のネットワーク１０および２０を描いている。各ネットワーク１０および２０は、ホスト１２、１４、１６、および２２、２４をそれぞれ含んでおり、交換器１８および２６もそれぞれ含んでおり、１７、１９、２８などの１つまたは複数のサーバをそれぞれ含み得る。さらに、各ネットワーク１０および２０は、インターネット３０に対する１つまたは複数のゲートウェイ１３および２５をそれぞれ含み得る。明示的に示していないものには、ルータ、ならびにネットワーク１０および２０を介するトラフィックを同様に制御することができ、交換器１８および２６によってそれぞれ本質的に描かれていると考えられることになるネットワーク１０および２０の他の部分、ならびにネットワーク１０および２０全般がある。
【０００３】
ネットワーク１０または２０などのネットワーク内で通信を制御するために、フィルタ規則が使用される。通常、フィルタ規則は、ネットワークの交換器によって使用される。フィルタ規則は、様々なサービスを提供するために、ネットワークを介して伝送されているパケットを試験する。フィルタ規則は、ネットワークに不正侵入しようとする試みを確実に阻止することができるように、外部ソースからネットワークに入ってくるパケットを試験することができる。例えば、ネットワーク１０に入ってくるインターネット３０からのトラフィックには、許可のないソースからのパケットに対して確実にエントランスを拒否するために、試験を行うことができる。同様に、ネットワークの一部分からのパケットが、ネットワークの別の部分にアクセスするのを防止することができる。例えばいくつかのホスト１２、１４、または１６からのパケットが、サーバ１７またはサーバ１９のいずれかにアクセスするのを防止することができる。ホストがサーバにコンタクトしようとしたという事実もまた、ネットワーク所有者が適切な行動をとることができるように、記録することができる。フィルタ規則はまた、パケットの優先順位に基づいてトラフィックを伝送するのに使用することができる。例えば、ホスト１２などの特定のホストからのパケットを、たとえホスト１４または１６からのパケットがドロップされ得るときでも、そのパケットがより高い優先順位を有しているという理由で、伝送することが可能である。フィルタ規則はまた、たとえ確立されているセッションからのトラフィックが伝送されるにしても、輻輳がひどいときには、新しいセッションが開始されるのを決して許可しないようにするために使用することができる。他の機能もフィルタ規則に基づいて果すことが可能である。フィルタ規則はまた、フィルタ規則に関する優先順位に基づいてインターアクトすることが可能である。例えば、第１フィルタ規則が、ほとんどのケースに対処するデフォルトのフィルタ規則であり得る。第２フィルタ規則は、第１フィルタ規則に対する例外であり得る。通常、第２フィルタ規則は、パケットが第１フィルタ規則と第２フィルタ規則の両方を満たす場合には、確実に第２フィルタ規則が制御を行うように、第１フィルタ規則よりも高い優先順位を有することになる。
【０００４】
フィルタ規則は、フィルタ規則が特定のパケットに対して動作するかどうか判別するために、キーを試験する。通常、使用されるキーは、パケットのインターネット・プロトコル（ＩＰ）５タプルである。通常、ＩＰ５タプルは５つの関与のフィールドを含み、これは、ソース・アドレス、宛先アドレス、ソース・ポート、宛先ポート、およびプロトコルである。通常、これらのフィールドはそれぞれ、３２ビット、３２ビット、１６ビット、１６ビット、８ビットである。したがって、ＩＰ５タプルの関与の部分の長さは、通常、１０４ビットである。通常、フィルタ規則はその機能を果すために、これらの１０４ビット、および場合によってはそれより多くのビットを使用する。例えば、ソース・アドレスおよび宛先アドレスに基づいて、フィルタ規則は、特定のホストからのパケットが特定の宛先アドレスに到着することが許されるかどうかを決定する。
【０００５】
さらに、キーはしばしば、ＩＰ５タプルのフィールド以外の追加のビットを含んでいる。例えば、セッションを開始するＴＣＰ  ＳＹＮ（セッションの開始）パケットは、既存のセッションに対するＴＣＰパケットとは別様に特徴付けることが可能である。この特徴づけは、ＩＰ５タプルのものに追加したビットを使用することによって達することができる。追加のビットは、ネットワークを介するトラフィックを管理するフィルタ規則によって使用され得る。例えば、ネットワークが輻輳しているとき、フィルタ規則は、既存のセッションに対するＴＣＰパケットを伝送しながらも、予防としてＴＣＰ  ＳＹＮパケットをドロップすることができる。これらの動作は、ネットワークが動作し続けることを可能にし、かつ輻輳を抑えるのに役立つ。ただし、この機能を実行するためには、フィルタ規則は、ＳＹＮパケット、またはパケットを開始パケットとして特徴付ける追加のビット、または既存のセッションからのパケットを使用する。したがって、通常、フィルタ規則は、パケットのＩＰ５タプルの少なくともいくつかのフィールドを含み、追加のビットを含み得るキーを使用して動作する。
【０００６】
ネットワーク１０などのネットワーク上のトラフィックを管理するため、通常、複数のフィルタ規則が使用される。さらに、異なるタイプのフィルタ規則が使用され得る。フィルタ規則のタイプは、キーがフィルタ規則にマッチした場合にフィルタ規則が取り得るタイプの動作によって決定される。例えば、１つのタイプの動作は、許可または拒否であり得る。このキーに基づいて、こうしたフィルタ規則は、ネットワークの一部分に特定のパケットのアクセスを許可するか、あるいは拒否するかを決定する。別のタイプの動作は、サービスの品質であり得る。例えば、ネットワークは、５つのレベルのサービスを提供することが可能である。キーがこのタイプのフィルタ規則にマッチしたとき、パケットに対するサービスの品質が、５つの可能なレベルのサービスのうちの１つであると決定される。さらに別のタイプのフィルタ規則は、特定のパケットにタグを付けるまたはタグを付けないことであり得る。したがって、パケットに対するキーがこのタイプのフィルタ規則にマッチするかどうかに基づき、拡張されたキー内またはパケット５タプル内で１ビットを設定することが可能である。各タイプのフィルタ規則内で、異なるフィルタ規則が異なる優先順位を有していることも可能である。したがって、キーが特定のタイプの１つのフィルタ規則にマッチする場合、行われるべき動作は、マッチしたフィルタ規則の優先順位に基づいて決定することができる。
【０００７】
フィルタ規則のそれぞれはそのタイプに関わらず、通常、キーを試験するために、２つの基準のうちの１つを使用する。１つのカテゴリのフィルタ規則は、厳密なマッチを使用する。フィルタ規則は、パケットに対するキーまたはキーのフィールドが、そのフィルタ規則のための基準に厳密にマッチした場合に、そのパケットに対して動作する。厳密なマッチが存在しない場合には、フィルタ規則は呼び出されない。こうしたフィルタ規則は、それに対してキーを試験することが比較的、容易である。
【０００８】
第２のカテゴリのフィルタ規則は、それに対してキーが試験される１つまたは複数の範囲の値を使用する。こうしたフィルタ規則のための１つの基準は、通常、キーのフィールドに対する値の範囲である。例えば、キーがＩＰ５タプルを使用する場合、フィルタ規則のための基準は、通常、ＩＰ５タプルの５つのフィールドのうちの、１つまたは複数に対する値の範囲を含む。フィールドのそれぞれに対する値は、フィールド内のビットを２進数に変換することによって決定される。例えば、３２ビットのソース・アドレス・フィールドは、ゼロ（２進数の３２ビットすべてが０である）と４０億超（２進数の３２ビットすべてが１である）の間の整数に変換することができる。フィルタ規則は、着信するパケットのためのキーが、適切なフィールドに対する範囲内にある値を有するかどうか判別することによって試験される。
【０００９】
特定のフィルタ規則は、キーの各フィールドに対する厳密なマッチを使用する、キーの各フィールドに対する範囲を使用する、またはこの２つの何らかの組合せを使用することができる。フィルタ規則は、キーが、各フィールドに対するフィルタ規則の基準に適合するかどうか判別することによって試験される。フィルタ規則がフィールドに対する基準として値の範囲を使用する場合、キーの対応するフィールドが値のその範囲内にフィットするかどうか判別することによって、フィルタ規則のその部分が試験される。フィルタ規則が、フィールドに対する厳密なマッチを要求する場合、キーの対応するフィールドがそのフィルタ規則の値に厳密にマッチするかどうか判別することによって、フィルタ規則のその部分が試験される。
【００１０】
システム内で使用される１セットのフィルタ規則は、間隔ベースのフィルタ規則を含むことが可能であり、異なる優先順位を有する複数タイプのフィルタ規則を含み得る。当技術分野の専門家には、こうした１セットのフィルタ規則を試験するのが困難なことは、容易に理解されよう。通常、セット内の各フィルタ規則が、キーに対して試験される。フィルタ規則はまた、通常、フィルタ規則の優先順位に基づいて順番に試験される。さらに、各タイプのフィルタ規則が試験される。こうした多数のフィルタ規則を明示的に試験することには、高いコストおよび長い時間がかかり得る。さらに、間隔ベースのフィルタ規則は、キーのフィールドがそのフィールドに対する値の対応する範囲内にあるかどうか判別することによって、特定のキーに対して試験される。フィールドに対する値の範囲は、極めて大きいものであり得る。値のこの範囲に対してキーを明示的に試験するためには、比較的、大量のメモリを消費する構造を構築しなければならない。さらに、こうした試験はしばしば、完了するまでに比較的、大量の時間を必要とする。したがって、こうしたフィルタ規則には、時間とメモリの両方の点で高いコストがかかる。したがって、異なるタイプを有することが可能であり、異なる優先順位を有することが可能で、間隔ベースのものであり得る多数のフィルタ規則を試験することには、高いコストがかかる。
【００１１】
【発明が解決しようとする課題】
したがって、必要とされているのは、異なるタイプのものであることが可能であり、基準として値の範囲を使用するフィルタ規則を試験するためのシステムおよび方法である。本発明は、こうした必要性に対応する。
【００１２】
【課題を解決するための手段】
本発明は、コンピュータ・システム内の複数のフィルタ規則を試験するための方法およびシステムを提供する。複数のフィルタ規則は、キーとともに使用される。複数のフィルタ規則のそれぞれは、キーの部分に対応する複数のビットを使用して記述することが可能である。複数のビットは、少なくとも１つのバイナリ値、少なくとも１つのワイルドカード、および少なくとも１つの境界記号を含み得る。この少なくとも１つのバイナリ値は、ゼロまたは１であり得る。この方法およびシステムは、キーの部分を複数のビットの部分に対して試験し、キーを複数のフィルタ規則の部分に対して明示的に試験することによって、複数のフィルタ規則の、キーがマッチすることができる部分を選択することを含む。複数のビットのこの部分の第１ビットは、複数のフィルタ規則に対する少なくとも１つのバイナリ記号の第１最大数を有する。複数のビットのこの部分の各後続ビットは、複数の残りのビットに対する少なくとも１つのバイナリ記号の第２最大数を有しており、前のビットの試験に基づいて選択される。好ましくは、複数のビットのこの部分は、複数のビットの第２部分に対応するノードを含む決定ツリーを使用して試験される。
【００１３】
本明細書で開示されるシステムおよび方法により、本発明は、フィルタ規則の試験を提供し、より詳細には、異なるタイプのフィルタ規則の、より少ない情報しか必要とせず、その実装がより早く、より簡単な試験を提供する。
【００１４】
【発明の実施の形態】
本発明は、コンピュータ・システム内での改良に関する。下記の説明は、当技術分野の専門家が本発明を作成し、使用することができるようにするために提示し、特許出願およびその要件という文脈で提供するものである。好ましい実施形態に対する様々な変更は、当技術分野の専門家には容易に明らかとなるものであり、本明細書の一般的な原理は、他の実施形態にも適用することが可能である。したがって、本発明は、示される実施形態に限定されるべきものではなく、これには、本明細書に記載する原理およびフィーチャと一致するもっとも広い範囲が与えられるべきである。
【００１５】
図１に描かれるネットワーク１０および２０のようなコンピュータ・ネットワークは、トラフィックの流れを制御するのにフィルタ規則を使用する。パケットに対するキーがフィルタ規則内に入るかどうかに基づいて、フィルタ規則は、何らかの動作が行われることを要求することができる。行われる動作のタイプは、フィルタ規則のタイプに依存する。例えば、パケットは、ドロップされる、ネットワーク１０または２０の特定の部分へのアクセスを拒否される、例えばインターネット３０へのゲートウェイを介する外部へのアクセスを拒否される、または所定の品質のサービスを有するということが可能である。これらの動作は、フィルタ規則のタイプを決定する。異なるタイプを有することに加えて、フィルタ規則は、異なる優先順位を有することが可能である。キーが同一タイプの２つのフィルタ規則にマッチしたとき、より高い優先順位のフィルタ規則が実行される。
【００１６】
また、フィルタ規則はしばしば、値の範囲に基づく。キーの部分、つまりフィールドを、整数に変換することができる。例えば、通常、使用されるキーは、パケットに対するＩＰ５タプル内のビットで構成されている。通常、ＩＰ５タプルは、ＩＰおよびＴＣＰのヘッダから次の５つのフィールドを含む。ソース・アドレス（３２ビット）、宛先アドレス（３２ビット）、ソース・ポート（１６ビット）、宛先ポート（１６ビット）、およびプロトコル（８ビット）である。各フィールドは、２進数を表すものと考えることができる。フィルタ規則は、パケットを試験して、１つまたは複数のフィールドが値の範囲内に入るかどうか判別することができる。例えば、通常、２進数１０２４または２０４８より下のソース・アドレスは、特定の機能のためにシステム管理者によって予約されている。したがって、フィルタ規則は、ソース・アドレス・フィールドを試験して、関与の数が１０２４であるとき、そのアドレスが２進数０００００００００００００００００００００１００００００００００より上であるかどうか判別することができる。こうしたフィルタ規則に対する範囲は、１０２４から可能な最大数まで、または２０４８から可能な最大数までになる。したがって、範囲は、フィルタ規則が比較的、柔軟で、幅広いケースをカバーすることを可能にする。ただし、フィルタ規則はまた、単一の２進数によって表され得る厳密なマッチを要求することも可能である。したがって、こうしたフィルタ規則は、キーの部分がこの２進数に厳密にマッチするかどうかを判別する。
【００１７】
通常、フィルタ規則は、各フィルタ規則の各フィールドに対する範囲に、各キーを比較することによって試験される。フィルタ規則は、通常、一番高いものから一番低いものへと、優先順位の順番で試験される。さらに、すべての適切な動作が確実に行われるようにするため、異なるタイプのフィルタ規則が試験される。キーがすべての適切な範囲内に入るとき、フィルタ規則は、キーがそれに対応するパケットに関して、何らかの動作が行われることを要求することができる。ただし、キーが、矛盾する実行すべき動作（「許可」および「拒否」など）を有する２つのフィルタ規則内に入るとき、より高い優先順位のフィルタ規則が実行されることに留意されたい。
【００１８】
各フィルタ規則に対してキーを試験することは、異なるタイプおよび異なる優先順位のフィルタ規則が機能できるようにするのではあるが、当技術分野の専門家には、この方法は時間かかり、コストが高いことが容易に理解されよう。相当な時間を消費する、試験されるべき異なるタイプの多数のフィルタ規則が存在していることが可能である。また、フィルタ規則のいくつか、またはすべてが、特定の１つのまたは複数のフィールドに対して広い範囲の値を使用することが可能である。こうした広い範囲を明示的に試験することは、遅いものになることがあり得る。したがって、フィルタ規則の従来の試験には、長い時間がかかる。
【００１９】
本発明は、コンピュータ・システム内の複数のフィルタ規則を試験するための方法およびシステムを提供する。複数のフィルタ規則は、キーとともに使用される。複数のフィルタ規則のそれぞれは、キーの部分に対応する複数の記号を使用して記述することが可能である。複数のビットは、少なくとも１つのバイナリ値、少なくとも１つのワイルドカード、および少なくとも１つの境界記号を含み得る。この少なくとも１つのバイナリ値は、ゼロまたは１であり得る。この方法およびシステムは、キーの部分を複数のビットの部分に対して試験し、キーを複数のフィルタ規則の部分に対して明示的に試験することによって、複数のフィルタ規則の、キーがマッチする部分を選択することを含む。複数のビットのこの部分の第１ビットは、複数のフィルタ規則に対する少なくとも１つのバイナリ記号の第１最大数を有する。複数のビットのこの部分の各後続ビットは、複数の残りのビットに対する少なくとも１つのバイナリ記号の第２最大数を有しており、前のビットの試験に基づいて選択される。好ましくは、複数のビットのこの部分は、複数のビットの第２部分に対応するノードを含む決定ツリーを使用して試験される。
【００２０】
本発明は、特定の範囲を有し、特定のタイプのものである特定のセットのフィルタ規則に関して説明されることになる。ただし、当技術分野の専門家には、この方法およびシステムが、他の範囲を使用する他のフィルタ規則に対しても効果的に動作することが容易に理解されよう。また、本発明は、単一数によって表されるフィルタ規則の文脈で説明されることになる。ただし、当技術分野の専門家には、この方法およびシステムが、複数のフィールドに対する数によって表されるフィルタ規則に対しても、同様に機能することが容易に理解されよう。こうした場合、本発明は、各フィールドに対する各数に対して動作することができる。また、当技術分野の専門家には、この方法およびシステムが、厳密なマッチと値の範囲の組合せを使用するフィルタ規則に対しても効果的に動作することが容易に理解されよう。さらに、ネットワーク上のトラフィックを制御する交換器の文脈で説明されてはいるが、本発明は、フィルタ規則が使用される他の環境内でも機能することが可能である。
【００２１】
本発明による方法およびシステムをより詳細に示すため、それとともに本発明を使用することができる、好ましい実施形態のネットワーク２０’および１０’を描いている図２を次に参照する。ネットワーク１０’および２０’は、図１で描かれたネットワーク１０および２０と実質的に同じである。ただし、制御ポイント１５および２７が一緒に示されている。好ましくは、制御ポイント１５および２７は、交換器１８’および２６’と結合された汎用コンピュータである。好ましくは、制御ポイント１５および２７は、下記で記載のとおり、フィルタ規則を試験する上で使用されることになる行列、およびビットの選択に関係する機能を実行する。好ましくは、交換器１８’および２６’は、下記に記載のとおり、ソフトウェア管理される決定ツリー（図２で図示せず）を含み、この決定ツリーを使用して、キーが１つまたは複数のフィルタ規則にマッチするかどうか判別する。
【００２２】
本発明をより詳細に説明するため、本発明によりフィルタ規則を試験するための方法１００の実施形態を描いている、図３を参照する。好ましくは、方法１００は、異なるタイプを有することが可能で、キーを試験するための基準として値の範囲を使用することができるフィルタ規則とともに使用される。フィルタ規則は、キーの１つまたは複数のフィールドに対する値の範囲を使用することができる。例えば、ＩＰ５タプルがキーとして使用されている場合、フィルタ規則は、ソース・アドレス、宛先アドレス、ソース・ポート、宛先ポート、およびプロトコルのフィールドのうちの１つまたは複数に対する値の範囲を使用することが可能である。キーの各フィールドは、ｎをフィールドの数として、ｎ次元空間での異なる次元と見なすことができる。したがって、フィルタ規則は、１つまたは複数の次元に対する値の範囲を使用することができる。
【００２３】
したがって、各フィルタ規則は、特定の１つまたは複数のフィールド内の数によって記述することが可能である。この数は、好ましくは、バイナリ記号（例えば、０または１）、ワイルドカード（＊）、または境界記号（ｂ）であるビット数を含む。バイナリ記号は、フィルタ規則に対するビットが特定のバイナリ値であり、キー内で対応するビットが同じ特定の数でなければならないことを示す。例えば、ゼロが、フィルタ規則の特定のビットに対するバイナリ記号であり得る。これは、フィルタ規則にマッチするためには、キーのこのビットもまた、ゼロでなければならないことを示す。ワイルドカードは、フィルタ規則のビットがゼロまたは１のいずれかであり得ることを示す。例えば、フィルタ規則は、［２５６，５１１］の範囲を有していることが可能である。こうしたフィルタ規則は、バイナリ記号（複数のゼロおよび複数の１）ならびにワイルドカードを有する単一の２進数によって表すことができる。こうしたフィルタ規則を表している２進数は、０００００００００００００００００００００００１＊＊＊＊＊＊＊＊である。これは、こうしたフィルタ規則に対する範囲の最下位の８ビットが、ゼロまたは１のいずれかであり得るからである。したがって、キーは、フィルタ規則と厳密に同一の最上位の２４ビットを有していなければならないが、フィルタ規則にマッチするためには、その最下位のビットとしてどのような２進数を有することも可能である。境界記号は、特定のフィルタ規則に対する範囲の境界が不規則であることを示す。例えば、別のフィルタ規則が、［６，５３］の範囲を有していることが可能である。低い方のエンドポイントを表している２進数が０００００１１０で、高い方のエンドポイントを表している２進数が００１１０１０１である。こうしたフィルタ規則は、００００００００と００１１１１１１の間にあるすべての値がその範囲内では含まれていないので、数００ｂｂｂｂｂｂで表すことができる。フィルタ規則を表している数の最後の５ビットは、単にエンドポイント間で変わらないので、こうした表示が使用される。
【００２４】
好ましい実施形態では、方法１００は、本発明の譲受人に譲渡された同時係属の米国特許出願第      号に記載される方法の後で使用される。本出願人は、前記同時係属の特許出願を参照によって本明細書に組込む。前記同時係属の出願では、フィルタ規則は、好ましくは決定ツリーを使用して、１つまたは複数のフィルタ規則のグループに分離される。前記同時係属の出願に記載の方法およびシステムは、いくつかの関係するメトリックのうちの１つを使用する決定ツリーを提供する。そうすることによって、前記同時係属の出願で選択ビットと呼ばれるあるビットが、試験のために選択される。前記同時係属の出願に記載のアルゴリズムは、「選択ビット」アルゴリズムと呼ばれる。
【００２５】
選択ビット・アルゴリズムでは、通常、フィルタ規則は、ネットワーク管理者などのシステムのユーザによって提供される。システム内で使用されるすべてのフィルタ規則は、好ましくは、行列の行を形成するように、選択ビット・アルゴリズムによって配置される。上述したように、フィルタ規則は、多数のビットで記述できる。したがって、行列の列は、フィルタ規則のそれぞれに対する１ビットを含む。行列の列は、４つの変数、ａ０、ａ１、ａ＊、ａｂによって記述することができる。変数ａ０は、列内で出現するゼロの数である。変数ａ１は、列内で出現する１の数である。変数ａ＊は、列内で出現するワイルドカードの数である。変数ａｂは、列内で出現する境界記号の数である。選択ビット・アルゴリズムは、１つまたは複数の列が、ゼロと１の両方を含んでいる限り使用される。
【００２６】
好ましくは、選択ビット・アルゴリズムは、最少の数の境界記号およびワイルドカードを有し、同一数に近いゼロおよび１を有している行を選択しようとする。Ｎ個のフィルタ規則が存在すると想定すると、好ましくは、選択ビット・アルゴリズムは、ａ＊およびａｂを有する列が最小限に抑えられ、ａ０およびａ１が可能な限りＮ／２に近くなることを求める。例えば、好ましくは、選択ビット・アルゴリズムは、列を選択するのに、数量（ａ０−Ｎ／２）２＋（ａ１−Ｎ／２）２＋（ａ＊＋ａｂ）２を最小限に抑える。選択された列は、試験され得るビットである選択ビットに対応する。好ましくは、キーがフィルタ規則のいくつかにマッチするかどうかチェックするのに、このビットを決定ツリーで使用する。選択された列に基づいて、２つの部分行列が形成される。１つの部分行列は、選択された列内にゼロを有さない元の行列（フィルタ規則）の列を含む。第２部分行列は、選択された列内に１を有さない元の行列（フィルタ規則）の列を含む。選択ビット・アルゴリズムは、次に、残りの部分行列に適用される。このアルゴリズムに基づいて、後続ビットが選択される。選択ビット・アルゴリズムは、部分行列内の列がゼロと１の両方を含んでいる限り、適用され続けることが可能である。部分行列内のどの列もゼロと１の両方を含まなくなったとき、選択ビット・アルゴリズムは、もはや適用されない。
【００２７】
選択ビット・アルゴリズムを使用して選択されたビットは、決定ツリーを構築するの使用される。決定ツリーの特定のノード連鎖は、選択ビット・アルゴリズムを使用して選択されたいくらかの数のビットを含み、キーがマッチすることができる１つまたは複数のフィルタ規則に対応するリーフに終端する。したがって、決定ツリーは、特定のパケットに対するキーがマッチすることのできる１つまたは複数のフィルタ規則を分離するのに使用することができる。
【００２８】
選択ビット・アルゴリズムは、意図する目的のためにはうまく機能するのではあるが、選択ビット・アルゴリズムを使用して得られた決定ツリーは、ある種のフィルタ規則の間での区別を行わない。詳細には、選択ビット・アルゴリズムは、ゼロと１の両方を有する列を有していないフィルタ規則のセット内のフィルタ規則の間での区別を行わない。したがって、特定のシステム内で使用されるフィルタ規則のすべてがこの基準に適合するとき、選択ビット・アルゴリズムは、必要な試験の量を削減することに成功しない。同様に、この基準に適合する多数のフィルタ規則が、選択ビット・アルゴリズムの適用の後に残っている場合、フィルタ規則の間でさらに区別を行うのに、選択ビット・アルゴリズムは使用されない。
【００２９】
また、方法１００は、好ましくは、図２に描かれる交換器１８’または２６’を使用して実行される。図３を再び参照すると、好ましくは、方法１００は、もはや選択ビット・アルゴリズムが適用されない、または複数のフィルタ規則に適用することができないときに開始する。したがって、図３に描かれる方法１００は、好ましくは、まだ区別されるべき、またはユーザによって提供されるフィルタ規則が、そのフィルタ規則で形成される行列には、ゼロと１の両方を含んだ列が無いようになっているときに開始する。ただし、それでもフィルタ規則は、バイナリ記号（例えば、０または１）、ワイルドカード（＊）、および境界記号（ｂ）の何らかの組合せを使用して記述することができる。また、好ましい実施形態では、方法１００は、比較的、多数の区別されるべきフィルタ規則が存在するときに使用される。例えば、方法１００は、選択ビット・アルゴリズムを使用して区別することができるいくつかのフィルタ規則が存在するときに使用することができるが、区別されるべきフィルタ規則が、２つ３つしか存在しないときには使用されない可能性があり、その場合は、フィルタ規則は、好ましくは、明示的に試験される。したがって、この場合、フィルタ規則は、優先順位の順番で試験されて、キーがフィルタ規則の基準に厳密にマッチするかどうか判別することになる。
【００３０】
ステップ１０２を介して、キーがマッチすることができる複数のフィルタ規則の部分が選択される。したがって、ステップ１０２は、好ましくは、キーがマッチすることのできる可能性のあるフィルタ規則の数を狭める。キーの部分を使用して、ステップ１０２で複数のフィルタ規則のその部分が選択される。したがって、ステップ１０２は、フィルタ規則の対応するビットに対して、キーのいくつかのビットを試験する。キーの特定のビットの試験結果により、キーの別のビットとフィルタ規則の対応するビットが互いに対して再び試験される。この処理は、キーが、複数のフィルタ規則の何らかの部分にマッチすることが判別されるまで続く。キーがそれに対して試験されるビットはまた、キーをそれに対して試験することが望まれる複数のフィルタ規則のプロパティに基づいて決定される。好ましくは、キーの部分がそれに対して試験され得るビットは、複数のフィルタ規則を記述している数の中の特定のビットとして出現する、バイナリ記号（ゼロおよび１）の数、ワイルドカードの数、および境界記号の数に基づいて決定される。例えば、キーの１ビットがそれに対して試験される第１ビットは、フィルタ規則がそれに対して最少の数のワイルドカードおよび境界記号を有しているビットであり得る。したがって、第１ビットはまた、最大の数のバイナリ記号を有するビットであり得る。キーがそれに対して試験される後続ビットは、それに対してフィルタ規則の残りの何らかの部分が、最少の数のワイルドカードおよび境界記号を有する、残りのビットのうちの１ビットに基づき、また前のビットの試験結果に基づいて決定される。好ましい実施形態では、ステップ１０２でのキーの対応するビットに対するフィルタ規則の特定ビットの試験は、好ましくはハードウェア支援またはコプロセッサ常駐のバイナリ決定ツリーである決定ツリーを使用して決定される。
【００３１】
複数の規則の部分が決定されれば、ステップ１０４を介して、複数のフィルタ規則のその部分の各キーに対して、キーを明示的に試験することができる。したがって、キーがマッチする可能性があるフィルタ規則が、ステップ１０２で狭められる。キーは次に、ステップ１０４を介して、複数のフィルタ規則のその部分に対して明示的に試験される。したがって、キーがマッチすることができるフィルタ規則が、明示的に決定され得る。
【００３２】
したがって、キーがマッチすることができるフィルタ規則の数は、ステップ１０２を使用して相当に狭めることができる。それに対してキーがステップ１０４で明示的に試験されるフィルタ規則の数は、相当に削減することができる。この結果、特定のパケットに対するキーを試験する上で、消費される時間が少なくなる。さらに、方法１００は、バイナリ記号、境界記号、ワイルドカードの文脈で説明されるフィルタ規則の文脈で説明してきたが、当技術分野の専門家には、フィルタ規則の特定の１つのフィールドを、ビットの前記組合せで記述できることが容易に理解されよう。したがって、方法１００は、ＩＰ５タプル・パケットのソース・アドレスなど、キーの単一フィールドに対して複数のフィルタ規則を試験するために使用することができる。方法１００は、キーおよびフィルタ規則の他のフィールドに対して繰り返すことが可能である。
【００３３】
前述のとおり、方法１００は、好ましくは、交換器１８’または２６’上に常駐する決定ツリーを使用して達せられる。決定ツリーは、複数のノードおよび複数のリーフを有する。このツリーのノードは、好ましくは、前述のフィルタ規則のビットである。このツリーの各リーフは、複数の規則の部分を含む。ステップ１０２で実際に試験されるビットおよびそのビットがそれに対して試験されるフィルタ規則により、異なるリールに到達して、複数の規則のその部分が決定され得る。
【００３４】
図４は、方法１００でキーを試験するために使用され得るフィルタ規則のビットを決定するための方法１１０の、一実施形態を描いている。したがって、方法１１０もまた、決定ツリーが使用される場合、その決定ツリーのノードを決定することができる。方法１１０は、好ましくは、制御ポイント１５または２７によって実行される。方法１１０の説明の最後まで、低い優先順位のどの規則も、そのドメインとして、高い優先順位の規則に適合するキーの中に含まれる１セットのキーを有していないと想定されている。もしそれが許されるとしたならば、より低い優先順位の規則は参照されないことになり、これは論理的誤りである。
【００３５】
複数のフィルタ規則に対する第１行列が、ステップ１１２を介して提供される。前述のとおり、複数のフィルタ規則は、好ましくは、選択ビット・アルゴリズムがその間での区別を行わない規則である。したがって、複数のフィルタ規則は、ユーザによって提供されるフィルタ規則のすべて、またはユーザによって提供されるフィルタ規則の何らかのサブセットであり得る。複数のフィルタ規則が、ユーザによって提供されるフィルタ規則のサブセットである場合には、そのフィルタ規則は、選択ビット・アルゴリズムを使用して形成された決定ツリーのリーフ上に存在することが可能なものであり得る。したがって、方法１１０を使用して提供される決定ツリーは、別個の決定ツリーである、または選択ビット・アルゴリズムを使用して形成された決定ツリーの拡張であると考えることできる。複数のフィルタ規則は、ステップ１１２で行列の行として提供される。行列の列はしたがって、フィルタ規則を記述するビットに対応する。行列の行は、好ましくは、バイナリ記号、境界記号、およびワイルドカードの何らかの組合せを含む。行列の列は、好ましくは、バイナリ記号、境界記号、およびワイルドカードの何らかの組合せを含む。ただし、行列の列は、ゼロまたは１のいずれかを含み得るが、その両方を含むことはできない。ステップ１１２もまた、好ましくは、フィルタ規則のタイプおよびフィルタ規則の優先順位に基づいてフィルタ規則を配置することを含む。前述のとおり、フィルタ規則のタイプは、キーがフィルタ規則にマッチした場合に行われる動作に依存する。
【００３６】
次に、ステップ１１４を介して、行列の列が選択される。選択された列は、キーを試験するのに使用することができるビットを決定する。ステップ１１４で選択された列は、何らかのメトリックに従って、最少の数の境界記号およびワイルドカードを有する、または最大の数のバイナリ記号を有する列である。こうした列が複数存在する場合、最低の指数、つまり最少の最下位のビットを有する列が、好ましくは、選択される。ステップ１１６を介して、選択された列に対応するビットが、試験での使用のために提供される。好ましい実施形態では、このビットは、交換器１８’または２６’に提供される。好ましくは、ステップ１１６で、このビットは、構築されている決定ツリーの適切な位置にも配置される。
【００３７】
ステップ１１８を介して、行列から２つの部分行列が提供される。この２つの部分行列は、各フィルタ規則が選択された列内で有する入力に基づいて提供される。第１部分行列は、選択された列内でゼロを有するフィルタ規則に対する選択された列内で、ワイルドカードを含んでいる。第１部分行列は、選択された列内で１を有するフィルタ規則を含まない。第１部分行列は、選択された列内でワイルドカードまたは境界記号を有する、変更されていないフィルタ規則を含む。したがって、第１部分行列は、好ましくは、ノードに対応するビットがゼロであるか、その可能性がある場合に辿られる、ノードからの分岐に対するビットを提供するために使用される。第２部分行列は、選択された列内で１を有するフィルタ規則に対する選択された列内で、ワイルドカードを含んでいる。第２部分行列は、選択された列内でゼロを有するフィルタ規則を含まない。第２部分行列は、選択された列内でワイルドカードまたは境界記号を有する、変更されていないフィルタ規則を含む。さらに、第１行列および第２行列から、複製行を除去することができる。同一動作タイプのより高い優先順位のフィルタ規則の複製である、より低い優先順位を有するフィルタは、どちらのフィルタ規則もそのなかに境界記号を有さない場合、除去することができる。したがって、第２行列は、好ましくは、ノードに対応するビットが１であるか、その可能性がある場合、ノードからの分岐に対するビットを提供するために使用される。
【００３８】
次に、列を選択するステップ（ステップ１１４）、ビットを提供するステップ（ステップ１１６）、および部分行列を生成するステップ（ステップ１１８）が、ステップ１２０を介して、前に生成されている部分行列に対して繰り返される。ステップ１２０は、生成された部分行列内でバイナリ記号、すなわちゼロまたは１を有する列が無くなるまで、ステップ１１４、１１６、１１８を繰り返す。したがって、ステップ１１４、１１６、１１８は、方法１００を使用して複数の規則の部分を分離するのに役立ち得るビットのすべてが見つかるまで、繰り返される。
【００３９】
方法１１０を使用して、それに対してキーを試験するのに使用することができるビットが決定される。好ましい実施形態では、方法１１０の結果は、パケットに対するキーのいくつかのビットを試験するのに使用することができるバイナリ決定ツリーである。また、好ましい実施形態では、方法１１０の結果は、パケットに対するキーのいくつかのビットを試験するのに使用することができるバイナリ決定ツリーである。この結果、方法１００を使用して、フィルタ規則を試験するのに必要とされる時間を相当に短縮することができる。さらに、方法１１０が制御ポイント１５または２７によって実行されるとき、交換器１８’または２６’がパケットの迅速な試験を実行し、その一方で、制御ポイント１５または２７は、行列に関するより複雑で、より遅い計算を実行する。
【００４０】
方法１００に関して述べたとおり、バイナリ記号、境界記号、およびワイルドカードの組合せによって記述されるフィルタ規則の文脈で、方法１１０を説明してきた。ただし、当技術分野の専門家には、ビットの前述の組合せによってフィルタ規則の特定のフィールドを記述できることが、容易に理解されよう。したがって、方法１１０を使用して、ＩＰ５タプル・パケットのソース・アドレスなどの、キーの単一フィールドを試験するのに使用するためのビットを決定することができる。また、キーおよびフィルタ規則の他のフィールドに対して方法１１０を繰り返すこともできる。
【００４１】
図５および６は、本発明による、決定ツリーを提供するための方法１１０’の好ましい実施形態のより詳細な図面を描いている。方法１１０’は、方法１１０と実質的に同じである。したがって、方法１１０’は、好ましくは、方法１１０と同じフィルタ規則とともに使用される。方法１００に関して述べたとおり、バイナリ記号、境界記号、およびワイルドカードの組合せによって記述されるフィルタ規則の文脈で、方法１１０’を説明してきたのではあるが、当技術分野の専門家には、ビットの前述の組合せによってフィルタ規則の特定のフィールドを記述できることが、容易に理解されよう。したがって、方法１１０’を使用して、パケットに対するＩＰ５タプルのソース・アドレスなど、キーの単一フィールドを試験するのに使用するためのビットを決定することができる。また、キーおよびフィルタ規則の他のフィールドに対して方法１１０’を繰り返すこともできる。
【００４２】
フィルタ規則はステップ１１１を介して、タイプに基づき、ブロックとして配置される。フィルタ規則タイプは、キーがフィルタ規則にマッチしたときに行われる動作によって決定される。例えば、パケットにアクセスを許可または拒否する動作を行うすべてのフィルタ規則を、１つのブロック内に配置することができる。サービスの品質に関わるすべてのフィルタ規則は、別のブロック内に配置される。各ブロック内のフィルタ規則は、ステップ１１３を介して、より高い優先順位からより低い優先順位へと、その優先順位に基づいて配列される。したがって、より高い優先順位のフィルタ規則は、フィルタ規則を含むブロック内でより高く配置される。したがって、ステップ１１１および１１３は、図４で描かれた方法１１０内のステップ１１２の機能を実行する。
【００４３】
図５および６を再び参照すると、ステップ１１４’を介して、行列のなかの１列が次に選択される。ステップ１１４’は、図４のステップ１１４と実質的に同一である。図５および６を再び参照すると、ステップ１１４’で選択された列が、キーを試験するのに使用することができるビットを決定している。ステップ１１４’で選択された列は、最少の数の境界記号およびワイルドカードを有する、または最大の数のバイナリ記号を有する列である。複数の列が、同じ最少の数の境界記号およびワイルドカードを有する場合には、最も低いインデックスを有する列がステップ１１４’で選択される。
【００４４】
選択された列に対応するビットが、ステップ１１６’を介して、決定ツリーでの使用のために提供される。好ましい実施形態では、このビットは、交換器１８’または２６’に提供される。ステップ１１６’が最初に実行されるとき、複数のフィルタ規則に対して使用される、決定ツリーのための第１ノードが提供される。後続のノードに対して提供される後続のビットは、そこから列が選択される部分行列に依存する。好ましくは、下記に述べる、第１部分行列からの１ビットが、ノードの一方の側に提供され、下記に述べる、第２部分行列からの１ビットが、ノードの反対側に提供される。後続のノードに対する後続のビットが、前のノードの相対する側に提供される。
【００４５】
ステップ１１８’を介して、行列から２つの部分行列が提供される。この２つの部分行列は、各規則が選択された列内で有する入力に基づいて提供される。第１部分行列は、選択された列内でゼロを有するフィルタ規則に対する選択された列内で、ワイルドカードを含む。第１部分行列は、選択された列内で１を有するフィルタ規則を含まない。第１部分行列は、選択された列内でワイルドカードまたは境界記号を有する、変更されていないフィルタ規則を含む。したがって、第１部分行列は、好ましくは、ノードに対応するキー内のビットがゼロである場合に辿られる、ノードからの分岐に対するビットを提供するのに使用される。第２部分行列は、選択された列内で１を有するフィルタ規則に対する選択された列内で、ワイルドカードを含む。第２部分行列は、選択された列内でゼロを有するフィルタ規則を含まない。第２部分行列は、選択された列内でワイルドカードまたは境界記号を有する、変更されていないフィルタ規則を含む。したがって、第２部分行列は、好ましくは、ノードに対応するキー内のビットが非ゼロである場合に辿られる、ノードからの分岐に対するビットを提供するのに使用される。
【００４６】
より低い優先順位を有する、同一タイプの行に対応するいくつかの複製行は、存在する場合には、ステップ１１９を介して、第１行列および第２行列から除去される。ステップ１１９は、より高い優先順位のフィルタ規則の複製であるより低い優先順位を有するフィルタを、どちらのフィルタ規則もそのなかに境界記号を有さず、かつ両方のフィルタ規則が同一ブロック（タイプ）内にある場合、除去する。この除去は、２つの規則が同一で、前記の基準に適合する場合、より高い優先順位の規則が常に支配することになるので、可能である。
【００４７】
次に、列を選択するステップ（ステップ１１４’）、ビットを提供するステップ（ステップ１１６’）、部分行列を生成するステップ（ステップ１１８’）、および複製列を削除するステップ（ステップ１１９）が、ステップ１２０’を介して、前に生成された部分行列に対して繰り返される。ステップ１２０’は、生成された部分行列内でバイナリ記号、すなわち、ゼロまたは１を有する列が無くなるまで、ステップ１１４’、１１６’、１１８’、１１９を繰り返す。好ましい実施形態では、第１部分行列内で選択された列に対応する１ビットが、ステップ１１６’を使用して、現行のノードからの左分岐上で提供される。同様に、第２部分行列から選択された列に対応する１ビットが、ステップ１１６’を使用して、現行のノードからの右分岐上で提供される。このように、ステップ１２０’を使用して、決定ツリーを完成することができる。
【００４８】
ステップ１２０’で決定ツリーが完成すると、この決定ツリーはさらに最適化される。決定ツリーのなかの、どの複製のサブツリーもステップ１２２を介して探し出され、ポインタで置換えられる。したがって、ステップ１２２で複製のサブツリーが除去されて、単一コピーのサブツリーだけが残される。複製のサブツリーの代わりに、複製のサブツリーに分岐するはずであった前のノードから、ポインタが提供される。このポインタは、前のノードから、単一コピーのサブツリーに対する開始ノードであるノードにポイントする。このようにして、決定ツリーのサイズが小さくされる。
【００４９】
このように、方法１１０’を使用して、望みのバイナリ決定ツリーを提供することができる。方法１１０’を使用して、それに対してキーを試験するのに使用することができるビットが決定されて、望みの決定ツリーが構築される。したがって、方法１１０’の結果は、パケットに対するキーのいくつかのビットを試験するのに使用することができるバイナリ決定ツリーである。この結果、方法１００を使用して、フィルタ規則を試験するのに必要となる時間を相当に短縮することが可能である。さらに、複製のサブツリーが除去されるので、決定ツリーを形成する上で、空間が節約される。したがって、時間が節約されるだけでなく、決定ツリーのための格納コストも削減される。さらに、制御ポイント１５または２７によって方法１１０’が実行されるとき、交換器１８’または２６’がパケットの迅速な試験を実行し、その一方で、制御ポイント１５または２７が、行列に関わるより複雑な、より遅い計算を実行する。
【００５０】
方法１００、１１０、１１０’をより完全に説明するために、下記の例を使用する。この例は、下記の表１に示されていないビットを試験することにより、他のいくつかのサーチ・アルゴリズムを使い果たして、８つの規則を残して他のすべてが除去された後に、生じる可能性があるものである。残っている８つの規則は、Ｒ０ないしＲ７であると想定する。動作タイプにより、また、優先順位の最も高い方から最も低い方にリストされたこれらの規則が、表１に記載されている。
【００５１】
【表１】
0003588332.tif 000002
【００５２】
このように、この例のフィルタ規則は、６ビット数を使用して記述することができる。したがって、使用することができるキーの部分は６ビットを含んでいる。例えば、キーが異なる複数のフィールドを有する場合には、そのキーの１つのフィールドは６ビットであり、規則Ｒ０ないしＲ７が、そのフィールドに対して、表１のなかに記載される範囲を有している。また、許可／拒否およびサービスの品質という、表１に示される２つの動作タイプも存在する。
【００５３】
方法１１０または１１０’を使用して、決定ツリーを構築することができる。こうしたツリーを提供するために、規則Ｒ０ないしＲ７に対する行列が提供される。フィルタ規則Ｒ０ないしＲ７に対する行列は、これらのフィルタ規則のそれぞれに対して、ビットｘ０ないしｘ５を含むことになる。提供される行列Ｍは、下記のとおりである。
【数１】
0003588332.tif 000003
【００５４】
見ての通り、行列Ｍのどの列も、ゼロと１の両方は有していない。したがって、フィルタ規則Ｒ０ないしＲ７は、方法１００、１１０、１１０’を使用するための好ましい基準に適合する。どの列に対して、ワイルドカードと境界記号の数の合計が最小であるか決定することによって、行列Ｍから１つの列が選択される。ビットｘ２およびｘ５に対応する列が、４という最少の数のワイルドカードおよび境界記号を有している。ｘ２に対応する列に対するインデックス数の方が低いので、ｘ２が第１列として選択される。したがって、テストされる第１ビットおよび２進木の第１ノードは、ｘ２に対応する。
【００５５】
次に、Ｍから第１行列および第２行列が導出される。第１行列Ｍ０が、ステップ１１８および１１８’に記載のとおり提供される。第１行列Ｍ０は、下記のとおりである。
【数２】
0003588332.tif 000004
【００５６】
Ｍ０内のどの行も、より高い優先順位を有する、同一ブロック内の行の複製ではないことに留意されたい。したがって、どの行もＭ０から削除されない。第２行列Ｍ１もまた、ステップ１１８および１１８’で記載のとおり、提供される。第２行列は下記のとおりである。
【数３】
0003588332.tif 000005
【００５７】
第２行列Ｍ１内で全く境界記号を有さない複製行は存在しない。したがって、Ｍ１からどの行も削除されない。第１行列Ｍ０は、構築される決定ツリーの好ましい実施形態での第１ノードからの左分岐を決定するために使用される。この左分岐は、第１ノードで試験されるビットがゼロである場合に辿られる分岐である。第２行列Ｍ１は、構築される決定ツリーの好ましい実施形態での第１ノードからの右分岐を決定するために使用される。この右分岐は、試験されるビットが非ゼロである場合に辿られる。
【００５８】
次に、ステップ１１４ないし１２０または１１４’ないし１２０’が、第１部分行列Ｍ０および第２部分行列Ｍ１に対して繰り返される。Ｍ０から選択される列は、最小の数のワイルドカードおよび境界記号を有するのがこの列であるため、ビットｘ５に対応する。ステップ１１８がＭ０に対して繰り返されるとき、２つのさらなる部分行列がＭ０から生成される。ｘ５＝０に対する第１部分行列Ｍ００が、ｘ５に対応するノードの左側に分岐するノードを決定するために使用され、これはｘ５がゼロであるときに生じる。ｘ５＝１に対する第２部分行列Ｍ０１は、ｘ５に対応するノードの右側に分岐するノードを決定し、これはｘ５がゼロでない場合に生じる。同様に、Ｍ１から選択された列は、ビットｘ１に対応する。これら２つの部分行列は、下記のとおりである。
【数４】
0003588332.tif 000006
【００５９】
この処理は、ツリーの左分岐全体（Ｍ０を第１部分行列として使用して、ｘ２＝０とする）で、生成された部分行列内でゼロまたは１を含む列が無くなるまで続けられる。ツリーのＭ０側を辿ると、Ｍ００に対して、選択される列はｘ０である。ｘ０＝０およびｘ０＝１に対してＭ００から得られる部分行列はそれぞれ、Ｍ０００およびＭ００１である。これらの部分行列は下記のとおりである。
【数５】
0003588332.tif 000007
【００６０】
Ｍ０００から、列ｘ１が選択された後に得られる２つの部分行列は、ゼロおよび１に等しいｘ１に対してそれぞれ、Ｍ００００およびＭ０００１である。これらの部分行列は、下記のとおりである。
【数６】
0003588332.tif 000008
【００６１】
列Ｒ１およびＲ７は、これらがそれぞれＲ０およびＲ６の複製であり、かつ「ｂ」フィールドを有さないため、Ｍ０００１から削除されたことに留意されたい。
【００６２】
部分行列Ｍ００００から列ｘ３が選択される。というのは、これが最も少ないワイルドカードまたは境界記号を有する、最低インデックスの列だからである。ゼロおよび１に等しいｘ３に対してそれぞれ、部分行列Ｍ０００００およびＭ００００１が生成される。これらの部分行列は、下記のとおりである。
【数７】
0003588332.tif 000009
【００６３】
Ｍ００１に対して選択される列は、列ｘ３である。ゼロおよび１に等しいｘ３に対する部分行列はそれぞれ、Ｍ００１０およびＭ００１１である。これらの部分行列Ｍ００１０およびＭ００１１は、下記のとおりである。
【数８】
0003588332.tif 000010
【００６４】
ステップ１１８が繰り返されるとき、Ｍ１から２つのさらなる部分行列Ｍ１０およびＭ１１が生成される。第１部分行列Ｍ１０は、ｘ１に対応するノードの左側に分岐するノードを決定するために使用され、これはｘ１がゼロであるときに生じる。第２部分行列Ｍ１１は、ｘ１に対応するノードの右側に分岐するノードを決定し、これはｘ１がゼロでないときに生じる。これら２つの部分行列は、下記のとおりである。
【数９】
0003588332.tif 000011
【００６５】
この処理は、生成された部分行列のすべての列が、ワイルドカードまたは境界記号のいずれかになるまで繰り返される。したがって、試験をするのに使用することができるビットを決定することができる。
【００６６】
図７は、方法１１０および１１０’に従って生成され、方法１００を実行するのに使用することができるツリー２００を描いている。ツリー２００は、分岐２０２を介して、選択ビット・アルゴリズムを使用して生成されたツリーに結合することができる。別法では、ツリー２００は、独立していることも可能である。ツリー２００を使用して、方法１００を実行することができる。例えば、特定のパケットに対するキーの値が１０１００１であると想定する。明示的にこのキーを試験することにより、キーが規則Ｒ３およびＲ７だけにマッチ可能であると決定することができる。２進木２００および方法１００を使用して、同一の結論に迅速に達することができる。各ノードで最も少ない数のワイルドカードおよび境界記号を有するビットが、決定ツリー２００が形成されたときに前に決定されている。したがって、ツリー２００の適切なノードでこのビットを試験することにより、方法１００が実行されることになる。試験されるべき第１ビットは、ビットｘ２である。ビットｘ２またはキーはゼロである。したがって、ノード２０４でこのキーについてビットｘ２を試験することは、左分岐２０５が辿られるべきことを示す。ノード２０６で、このキーについて１であるビットｘ５を試験することは、右分岐２０７が辿られるべきことを示す。ノード２０８で、１である、キーのビットｘ０を試験することは、右分岐２０９が辿られるべきことを示す。これは結果としてリーフ２１０に導かれて、キー１０１００１がＲ３およびＲ７だけにマッチ可能であることを示す。この結論は、キーの３つのビットだけの値を試験し、方法１００を使用することによって達せられる。したがって、２進木２００と併せた方法１００は、キーがマッチすることができるフィルタ規則を迅速かつ容易に決定することができる。次いで、キーをこれらのフィルタ規則に対して明示的に試験できる。
【００６７】
方法１１０’のために、ステップ１２２を使用して決定ツリー２００をさらに最適化することも可能である。図８は、そのように最適化されている決定ツリー２００’を描いている。図７を参照すると、ノード２１４および２２６で開始するサブツリーが、ノード２４０および２５０にあるサブツリーによってそれぞれ複製されている。したがって、ノード２１４および２１６ならびにリーフ２１８、２２０、２２２は、ノード２４０および２４４ならびにリーフ２４２、２４６、２４８のコピーである。ノード２２６、２２８、２３０およびリーフ２３２、２３４、２３６、２３８は、ノード２５０、２５２、２５４およびリーフ２５６、２５８、２６０、２６２のコピーである。
【００６８】
再び図８を参照すると、ノード２１４および２２６で開始するこれらのサブツリーが除去されている。その代わりに、ポインタ２３９および２４９が提供されている。ポインタ２３９および２４９は、前のノード２３２’および２２４’からそれぞれ、ノード２４０’および２５０’にポイントする。したがって、決定ツリー２００’を実装する上で、さらなる空間が節約される。ツリー２００’内では、すべての複製サブツリーが置換えられているのではあるが、ポインタまたは同様のツールで、サブツリーのいくつかだけを置換える、あるいはどれも置換えないというのも自由にできることに留意されたい。ただし、より多くの数の複製サブツリーを置換えることによって、より多くの空間が節約される。
【００６９】
したがって、方法１００、１１０、１１０’を使用して、決定ツリーを提供することができ、フィルタ規則、特に異なる動作タイプを有するものを容易かつ迅速に試験することができる。さらに、決定ツリー自体、その決定ツリーの冗長な部分によって占められる空間を削減することによって、改良することが可能である。したがって、ネットワーク１０’および２０’のパケットの伝送を円滑にすることができる。
【００７０】
値の範囲を使用する、フィルタ規則を試験するための方法およびシステムを開示してきた。本発明によって書かれたソフトウェアは、メモリ、ＣＤ−ＲＯＭ、ディスケット６０など、何らかの形態のコンピュータ可読媒体に記憶される、またはネットワーク上で伝送されて、プロセッサによって実行されることになる。本発明を示される実施形態に応じて説明してきたが、当技術分野の専門家には、それらの実施形態にはバリエーションが存在し得て、そうしたバリエーションも本発明の趣旨および範囲の中に入ることが、容易に理解されよう。したがって、添付の請求項の趣旨および範囲を逸脱せずに、当技術分野の専門家によって多くの改変が行われ得る。
【００７１】
まとめとして、本発明の構成に関して以下の事項を開示する。
【００７２】
（１）コンピュータ・システム内で複数のフィルタ規則を試験するための方法であって、前記複数のフィルタ規則がキーとともに使用され、前記複数のフィルタ規則のそれぞれが複数のビットを使用して記述可能で、前記複数のビットが少なくとも１つのバイナリ値、少なくとも１つのワイルドカード、および少なくとも１つの境界記号を含むことが可能で、前記複数のフィルタ規則の内のフィルタ規則の前記少なくとも１つのバイナリ値がゼロまたは１であることが可能で、前記複数のビットが前記キーの部分に対応し、
（ａ）前記複数のビットの部分に対して前記キーを試験することにより、前記キーがマッチすることができる前記複数のフィルタ規則の部分を選択するステップであって、前記複数のビットの前記部分の第１ビットが、前記複数のフィルタ規則に対する前記少なくとも１つのバイナリ記号の第１最大数を有し、前記複数のビットの前記部分の各後続ビットが、複数の残りのビットに対する前記少なくとも１つのバイナリ記号の第２最大数を有し、かつ前記複数のビットの前記部分の中の先行するビットの試験に基づいて選択されるステップと、
（ｂ）前記複数の規則の前記部分を前記キーに対して試験するステップ
とを含む方法。
（２）前記選択するステップ（ａ）が、（ａ１）決定ツリーおよび複数のビットの部分を使用して、キーがマッチすることができる、前記複数のフィルタ規則の前記部分を選択するステップをさらに含む方法であって、
前記決定ツリーが複数のノードおよび複数のリーフを含み、前記複数のフィルタ規則の前記部分が、前記複数のリーフの少なくとも１つのリーフ上にあり、前記複数のノードの第１ノードが、前記複数のフィルタ規則のそれぞれに対する前記複数のビットの前記第１ビットに対応し、前記第１ビットが前記複数のフィルタ規則に対する前記少なくとも１つのバイナリ記号の第１最大数を有し、前記複数のノードの各後続ノードが、前記複数のフィルタ規則のそれぞれに対する第２の複数の残りのビットの中の１ビットに対応し、前記ビットが、前記複数の残りのビットに対する前記少なくとも１つのバイナリ記号の第２最大数を有する上記（１）に記載の方法。
（３）さらに、
（ｃ）決定ツリーを提供するステップ
を含み、
前記決定ツリーを提供するステップが、
（ｃ１）複数の行および複数の列を有する第１行列を提供するステップであって、前記複数の行のそれぞれが、前記複数のフィルタ規則の中の１つのフィルタ規則に対応し、前記複数の列のそれぞれが、前記複数のフィルタ規則に対する前記複数のビットのなかの１つのビットに対応するステップと、
（ｃ２）前記複数のビットのなかの前記第１ビットを使用して、前記複数のノードの第１ノードを提供するステップであって、前記第１ビットが、前記複数のフィルタ規則に対する前記少なくとも１つのバイナリ記号の前記第１最大数を有する前記第１行列の中の１つの列に対応するステップと、
（ｃ３）第２行列を前記第１行列に基づいて提供するステップであって、前記第２行列は、前記列内の入力がゼロである場合には前記列内の前記入力に対するワイルドカードを含め、行に対する前記列内の入力が１である場合には前記第１行列のなかの前記行を除外するステップと、
（ｃ４）第３行列を前記第１行列に基づいて提供するステップであって、前記第３行列は、前記列内の入力が１である場合には前記列内の前記入力に対するワイルドカードを含め、行に対する前記列内の入力がゼロである場合には前記第１行列のなかの前記行を除外するステップと、
（ｃ５）前記複数のノードが提供されるまで、前記第２行列および第３行列のそれぞれに対して、ステップ（ｃ２）ないし（ｃ４）を繰り返すステップと
を含む、上記（２）に記載の方法。
（４）前記第１行列を提供するステップ（ｃ１）が、（ｃ１ｉ）前記複数のフィルタ規則のそれぞれの優先順位に基づいて、前記複数のフィルタ規則にランク付けするステップをさらに含む上記（３）に記載の方法。
（５）前記第１行列を提供するステップ（ｃ１）が、（ｃ１ｉ）前記複数のフィルタ規則のそれぞれのタイプに基づいて、前記複数のフィルタ規則にランク付けするステップをさらに含む上記（３）に記載の方法。
（６）前記第１行列を提供するステップ（ｃ１）が、（ｃ１ｉ）前記複数のフィルタ規則のそれぞれのタイプおよび前記複数のフィルタ規則のそれぞれの優先順位に基づいて、前記複数のフィルタ規則にランク付けするステップをさらに含む上記（３）に記載の方法。
（７）前記第１行列、第２行列、および第３行列が、同一タイプを有する一対の複製行を有することができ、前記一対の複製行の第１行がより高い優先順位を有し、前記一対の複製行の第２行がより低い優先順位を有し、前記一対の複製行のどちらの行も境界記号を有さず、前記第１行列、第２行列、および第３行列が、前記第２行を除去することによってさらに提供される上記（３）に記載の方法。
（８）前記キーがさらに複数のフィールドを含み、かつ前記複数のフィルタ規則のそれぞれに対する前記複数のビットが、前記複数のフィールドのなかの１つのフィールドに対応する上記（１）に記載の方法。
（９）前記複数のフィルタ規則が、前記複数のフィールドの残りのフィールドに対応する第２番目の複数のビットによってさらに記述され、
（ｃ）前記第２番目の複数のビットの部分を使用して、前記複数のフィールドの前記残りのフィールドに対して、前記ステップ（ａ）および（ｂ）を繰り返すステップをさらに含む上記（８）に記載の方法。
（１０）前記決定ツリーが、前記複数のノードのなかの少なくとも１つの特定のノードからの、少なくとも１つのサブツリーの少なくとも開始ノードに対する少なくとも１つのポインタを含み、これによって、前記少なくとも１つのサブツリーを、単一ノードより多くのノードでも使用できるようにする上記（３）に記載の方法。
（１１）前記複数のフィルタ規則が、複数のタイプのものである上記（１）に記載の方法。
（１２）コンピュータ・システム内で複数のフィルタ規則を試験するための決定ツリーを提供するための方法であって、前記決定ツリーが複数のノードおよび複数のリーフを含み、前記複数のフィルタ規則がキーとともに使用され、前記複数のフィルタ規則のそれぞれが、複数のビットを使用して記述可能であり、前記複数のビットが、少なくとも１つのバイナリ値、少なくとも１つのワイルドカード、および少なくとも１つの境界記号を含むことができ、前記複数のフィルタ規則のなかの１つのフィルタ規則の前記少なくとも１つのバイナリ値が、ゼロまたは１であることが可能で、前記複数のビットが前記キーの部分に対応し、
（ａ）複数の行および複数の列を有する第１行列を提供するステップであって、前記複数の行のそれぞれが、前記複数のフィルタ規則のなかの１つのフィルタ規則に対応し、前記複数の列のそれぞれが、前記複数のフィルタ規則に対する前記複数のビットのなかの１つのビットに対応するステップと、
（ｂ）前記複数のビットのなかの第１ビットを使用して、前記複数のノードの第１ノードを提供するステップであって、前記第１ビットが、前記複数のフィルタ規則に対する前記少なくとも１つのバイナリ記号の第１最大数を有する前記第１行列のなかの１つの列に対応するステップと、
（ｃ）第２行列を前記第１行列に基づいて提供するステップであって、前記第２行列は、前記列内の入力がゼロである場合には前記列内の前記入力に対するワイルドカードを含め、行に対する前記列内の入力が１である場合には、前記第１行列のなかの前記行を除外するステップと、
（ｄ）第３行列を前記第１行列に基づいて提供するステップであって、前記第３行列は、前記列内の入力が１である場合には前記列内の前記入力に対するワイルドカードを含め、行に対する前記列内の入力がゼロである場合には、前記第１行列のなかの前記行を除外するステップと、
（ｅ）前記複数のノードが提供されるまで、前記第２行列および前記第３行列のそれぞれに対して、前記ステップ（ｂ）ないし（ｄ）を繰り返すステップとを含む方法。
（１３）前記第１行列を提供するステップ（ａ）が、（ａ１）複数のフィルタ規則のそれぞれの優先順位に基づいて、前記複数のフィルタ規則にランク付けするステップをさらに含む上記（１２）に記載の方法。
（１４）前記第１行列を提供するステップ（ａ）が、（ａ２）前記複数のフィルタ規則のそれぞれのタイプに基づいて、前記複数のフィルタ規則にランク付けするステップをさらに含む上記（１２）に記載の方法。
（１５）前記第１行列を提供するステップ（ａ）が、（ａ３）前記複数のフィルタ規則のそれぞれのタイプおよび前記複数のフィルタ規則のそれぞれの優先順位に基づいて、前記複数のフィルタ規則にランク付けするステップをさらに含む上記（１２）に記載の方法。
（１６）前記第１行列、第２行列、および第３行列が、同一タイプを有する一対の複製行を有することができ、前記一対の複製行の第１行がより高い優先順位を有し、前記一対の複製行の第２行がより低い優先順位を有し、前記一対の複製行のどちらの行も境界記号を有さず、前記第１行列、第２行列、および第３行列が、前記第２行を除去することによってさらに提供される上記（１２）に記載の方法。
（１７）前記キーがさらに複数のフィールドを含み、かつ前記複数のフィルタ規則のそれぞれに対する前記複数のビットが、前記複数のフィールドのなかの１つのフィールドに対応する上記（１３）に記載の方法。
（１８）前記複数のフィルタ規則が、前記複数のフィールドの残りのフィールドに対応する第２番目の複数のビットによってさらに記述される方法であって、かつ
（ｆ）前記第２番目の複数のビットの部分を使用して、前記複数のフィールドの前記残りのフィールドに対して、前記ステップ（ａ）ないし（ｅ）を繰り返し、これによって前記複数のフィールドに対する複数の決定ツリーを提供するステップをさらに含む上記（１７）に記載の方法。
（１９）（ｆ）少なくとも１つの別のサブツリーの少なくとも開始ノードに向かう、少なくとも１つの特定のサブツリーの少なくとも１つの特定のノードからの少なくとも１つのポインタで、前記少なくとも１つの特定のサブツリーを置換え、これによって前記少なくとも１つの別のサブツリーを、前記少なくとも１つの特定のサブツリーの代わりに使用できるようにするステップをさらに含む上記（１２）に記載の方法。
（２０）コンピュータ・システム内で複数のフィルタ規則を試験するためのプログラムを含むコンピュータ可読媒体であって、前記複数のフィルタ規則がキーとともに使用され、前記複数のフィルタ規則のそれぞれが複数のビットを使用して記述可能で、前記複数のビットが少なくとも１つのバイナリ値、少なくとも１つのワイルドカード、および少なくとも１つの境界記号を含むことが可能で、前記複数のフィルタ規則の１つのフィルタ規則の前記少なくとも１つのバイナリ値がゼロまたは１であり、前記複数のビットが前記キーの部分に対応し、
前記プログラムが、
（ａ）前記複数のビットの部分に対して前記キーを試験することにより、前記キーがマッチすることができる前記複数のフィルタ規則の部分を選択する命令であって、前記複数のビットの前記部分の第１ビットが前記複数のフィルタ規則に対する前記少なくとも１つのバイナリ記号の第１最大数を有し、前記複数のビットの前記部分の各後続ビットが、複数の残りのビットに対する前記少なくとも１つのバイナリ記号の第２最大数を有し、かつ前記複数のビットの前記部分の中の先行するビットの試験に基づいて選択される命令と、
（ｂ）前記複数の規則の前記部分を前記キーに対して試験する命令とを含む媒体。
（２１）選択する前記命令（ａ）が、
（ａ１）決定ツリーおよび前記複数のビットの前記部分を使用して、キーがマッチすることができる、複数のフィルタ規則の前記部分を選択する命令であって、前記決定ツリーが複数のノードおよび複数のリーフを含み、前記複数のフィルタ規則の前記部分が前記複数のリーフの少なくとも１つのリーフ上にあり、前記複数のノードの第１ノードが、前記複数のフィルタ規則のそれぞれに対する前記複数のビットの前記第１ビットに対応し、前記第１ビットが前記複数のフィルタ規則に対する前記少なくとも１つのバイナリ記号の第１最大数を有し、前記複数のノードの各後続ノードが、前記複数のフィルタ規則のそれぞれに対する第２番目の複数の残りのビットの中の１ビットに対応し、前記ビットが、前記複数の残りのビットに対する前記少なくとも１つのバイナリ記号の第２最大数を有する命令をさらに含む上記（２０）に記載のコンピュータ可読媒体。
（２２）前記プログラムが、
（ｃ）決定ツリーを提供する
命令をさらに含み、前記決定ツリーを提供する命令が、
（ｃ１）複数の行および複数の列を有する第１行列を提供する命令であって、前記複数の行のそれぞれが、前記複数のフィルタ規則のなかの１つのフィルタ規則に対応し、前記複数の列のそれぞれが、前記複数のフィルタ規則に対する前記複数のビットのなかの１つのビットに対応する命令と、
（ｃ２）前記複数のビットのなかの前記第１ビットを使用して、前記複数のノードの第１ノードを提供する命令であって、前記第１ビットが、前記複数のフィルタ規則に対する前記少なくとも１つのバイナリ記号の前記第１最大数を有する前記第１行列のなかの１つの列に対応する命令と、
（ｃ３）第２行列を前記第１行列に基づいて提供する命令であって、前記第２行列は、前記列内の入力がゼロである場合には前記列内の前記入力に対するワイルドカードを含め、行に対する前記列内の入力が１である場合には、前記第１行列のなかの前記行を除外する命令と、
（ｃ４）第３行列を前記第１行列に基づいて提供する命令であって、前記第３行列は、前記列内の入力が１である場合には前記列内の前記入力に対するワイルドカードを含め、行に対する前記列内の入力がゼロである場合には、前記第１行列のなかの前記行を除外する命令と、
（ｃ５）前記複数のノードが提供されるまで、前記第２行列および第３行列のそれぞれに対して、命令（ｃ２）ないし（ｃ４）を繰り返す命令とを含む上記（２１）に記載のコンピュータ可読媒体。
（２３）前記第１行列を提供する命令（ｃ１）が、
（ｃ１ｉ）前記複数のフィルタ規則のそれぞれの優先順位に基づいて、前記複数のフィルタ規則にランク付けする命令をさらに含む上記（２２）に記載のコンピュータ可読媒体。
（２４）前記第１行列を提供する命令（ｃ１）が、
（ｃ１ｉ）前記複数のフィルタ規則のそれぞれのタイプに基づいて、前記複数のフィルタ規則にランク付けする命令をさらに含む上記（２２）に記載のコンピュータ可読媒体。
（２５）前記第１行列を提供する命令（ｃ１）が、
（ｃ１ｉ）前記複数のフィルタ規則のそれぞれのタイプおよび前記複数のフィルタ規則のそれぞれの優先順位に基づいて、前記複数のフィルタ規則にランク付けする命令をさらに含む上記（２２）に記載のコンピュータ可読媒体。
（２６）前記決定ツリーが、前記複数のノードのなかの少なくとも１つの特定のノードからの、少なくとも１つのサブツリーの少なくとも開始ノードに対する少なくとも１つのポインタを含み、これによって、前記少なくとも１つのサブツリーを、単一ノードより多くのノードでも使用できるようにする上記（２２）に記載のコンピュータ可読媒体。
（２７）コンピュータ・システム内で複数のフィルタ規則を試験するための決定ツリーを提供するためのプログラムを含むコンピュータ可読媒体であって、前記決定ツリーが複数のノードおよび複数のリーフを含み、前記複数のフィルタ規則がキーとともに使用され、前記複数のフィルタ規則のそれぞれが、複数のビットを使用して記述可能であり、前記複数のビットが、少なくとも１つのバイナリ値、少なくとも１つのワイルドカード、および少なくとも１つの境界記号を含むことができ、前記複数のフィルタ規則のなかの１つのフィルタ規則の前記少なくとも１つのバイナリ値が、ゼロまたは１であることが可能で、前記複数のビットが前記キーの部分に対応し、
前記プログラムが、
（ａ）複数の行および複数の列を有する第１行列を提供する命令であって、前記複数の行のそれぞれが、前記複数のフィルタ規則のなかの１つのフィルタ規則に対応し、前記複数の列のそれぞれが、前記複数のフィルタ規則に対する前記複数のビットのなかの１つのビットに対応する命令と、
（ｂ）前記複数のビットのなかの第１ビットを使用して前記複数のノードの第１ノードを提供する命令であって、前記第１ビットが、前記複数のフィルタ規則に対する前記少なくとも１つのバイナリ記号の第１最大数を有する第１行列のなかの１つの列に対応する命令と、
（ｃ）第２行列を前記第１行列に基づいて提供する命令であって、前記第２行列は、前記列内の入力がゼロである場合には前記列内の前記入力に対するワイルドカードを含め、行に対する前記列内の入力が１である場合には、前記第１行列のなかの前記行を除外する、命令と、
（ｄ）第３行列を前記第１行列に基づいて提供する命令であって、前記第３行列は、前記列内の入力が１である場合には前記列内の前記入力に対するワイルドカードを含め、行に対する前記列内の入力がゼロである場合には、前記第１行列のなかの前記行を除外する命令と、
（ｅ）前記複数のノードが提供されるまで、前記第２行列および第３行列のそれぞれに対して、前記ステップ（ｂ）ないし（ｄ）を繰り返す命令とを含む媒体。
（２８）コンピュータ・システム内で複数のフィルタ規則を試験するためのシステムであって、前記複数のフィルタ規則がキーとともに使用され、前記複数のフィルタ規則のそれぞれが複数のビットを使用して記述可能で、前記複数のビットが少なくとも１つのバイナリ値、少なくとも１つのワイルドカード、および少なくとも１つの境界記号を含むことが可能で、前記複数のフィルタ規則の前記少なくとも１つのバイナリ値がゼロまたは１であり、前記複数のビットが前記キーの部分に対応し、
データを伝送し、受信するための複数のホストと、
前記複数のビットの部分に対して前記キーを試験することによって、キーがマッチすることができる前記複数のフィルタ規則の部分を選択するための交換器であって、前記複数のビットの部分の第１ビットが前記複数のフィルタ規則に対する前記少なくとも１つのバイナリ記号の第１最大数を有し、前記複数のビットの前記部分の各後続ビットが、複数の残りのビットに対する前記少なくとも１つのバイナリ記号の第２最大数を有し、かつ前記複数のビットの前記部分の中の先行するビットの試験に基づき、前記複数の規則の前記部分を前記キーに対して試験するために選択される交換器と
を含むシステム。
（２９）前記交換器が決定ツリーを含み、
前記決定ツリーは複数のノードおよび複数のリーフを含み、前記複数のフィルタ規則の前記部分が前記複数のリーフの少なくとも１つのリーフ上にあり、前記複数のノードの第１ノードが、前記複数のフィルタ規則のそれぞれに対する前記複数のビットの前記第１ビットに対応し、前記第１ビットが前記複数のフィルタ規則に対する前記少なくとも１つのバイナリ記号の第１最大数を有し、前記複数のノードの各後続ノードが、前記複数のフィルタ規則のそれぞれに対する第２番目の複数の残りのビットの中の１ビットに対応し、前記ビットが、前記複数の残りのビットに対する前記少なくとも１つのバイナリ記号の第２最大数を有する、上記（２８）に記載のシステム。
（３０）前記決定ツリーを提供するための制御ポイントをさらに含み、前記決定ツリーの提供が、複数の行および複数の列を有する第１行列を提供するステップであって、前記複数の行のそれぞれが、前記複数のフィルタ規則のなかの１つのフィルタ規則に対応し、前記複数の列のそれぞれが、前記複数のフィルタ規則に対する前記複数のビットのなかの１つのビットに対応するステップと、前記複数のビットの前記第１ビットを使用して前記複数のノードの第１ノードを提供するステップであって、前記第１ビットが、前記複数のフィルタ規則に対する前記少なくとも１つのバイナリ記号の前記第１最大数を有する前記第１行列のなかの１つの列に対応するステップと、第２行列を前記第１行列に基づいて提供するステップであって、前記第２行列は、前記列内の入力がゼロである場合、前記列内の前記入力に対してワイルドカードを含め、行に対する前記列内の入力が１である場合、前記第１行列の前記行を除外するステップと、第３行列を前記第１行列に基づいて提供するステップであって、前記第３行列は、前記列内の入力が１である場合、前記列内の前記入力に対してワイルドカードを含め、行に対する前記列内の入力がゼロである場合、前記第１行列の前記行を除外するステップと、前記決定ツリー上で前記複数の規則の前記部分を分離することができるまで、前記第２行列および第３行列に対して、前記列を選択するステップ、ノードを提供するステップ、前記第２行列を提供するステップ、および前記第３行列を提供するステップを繰り返すステップとによって行われる、上記（２９）に記載のシステム。
（３１）前記複数のフィルタ規則のそれぞれの優先順位に基づいて、前記複数のフィルタ規則にランク付けすることによって、前記第１行列が提供される上記（３０）に記載のシステム。
（３２）前記複数のフィルタ規則のそれぞれのタイプに基づいて、前記複数のフィルタ規則にランク付けすることによって、前記第１行列が提供される上記（３０）に記載のシステム。
（３３）前記複数のフィルタ規則のそれぞれのタイプおよび前記複数のフィルタ規則のそれぞれの優先順位に基づいて、前記複数のフィルタ規則にランク付けすることによって、前記第１行列が提供される上記（３０）に記載のシステム。
（３４）前記第１行列、第２行列、および第３行列が、同一タイプを有する一対の複製行を有することができ、前記一対の複製行の第１行がより高い優先順位を有し、前記一対の複製行の第２行がより低い優先順位を有し、前記一対の複製行のどちらの行も境界記号を有さず、前記第１行列、第２行列、および第３行列が、前記第２行を除去することによってさらに提供される上記（３０）に記載のシステム。
（３５）前記キーがさらに複数のフィールドを含み、かつ前記複数のフィルタ規則のそれぞれに対する前記複数のビットが、前記複数のフィールドのなかの１つのフィールドに対応する上記（２８）に記載のシステム。
（３６）前記複数のフィルタ規則が、前記複数のフィールドの残りのフィールドに対応する第２番目の複数のビットによってさらに記述され、かつ交換器が、前記複数のフィルタ規則の部分を選択すること、ならびに、前記第２番目の複数のビットの部分を使用して、前記複数のフィールドの前記残りのフィールドに対して、前記複数のフィルタ規則の前記部分を試験することを繰り返す、上記（３５）に記載のシステム。
（３７）前記決定ツリーが、前記複数のノードのなかの少なくとも１つの特定のノードからの、少なくとも１つのサブツリーの少なくとも開始ノードに対する少なくとも１つのポインタを含み、これによって、前記少なくとも１つのサブツリーを、単一ノードより多くのノードで使用できるようにする上記（３０）に記載のシステム。
（３８）前記複数のフィルタ規則が、複数のタイプのものであり得る上記（２９）に記載のシステム。
（３９）コンピュータ・システム内で複数のフィルタ規則を試験するためのシステムであって、前記複数のフィルタ規則がキーとともに使用され、前記複数のフィルタ規則のそれぞれが複数のビットを使用して記述可能で、前記複数のビットが少なくとも１つのバイナリ値、少なくとも１つのワイルドカード、および少なくとも１つの境界記号を含むことが可能で、前記複数のフィルタ規則の１つのフィルタ規則の前記少なくとも１つのバイナリ値がゼロまたは１であり、前記複数のビットが前記キーの部分に対応し、
データを伝送し、受信するための複数のホストと、
決定ツリーを提供するための制御ポイントと、
前記複数のホストおよび前記複数のフィルタ規則を試験するための前記制御ポイントに結合された論理とを含み、
前記論理が、複数のノードおよび複数のリーフを有する決定ツリーを含み、
前記決定ツリーの提供が、複数の行および複数の列を有する第１行列を提供するステップであって、前記複数の行のそれぞれが、前記複数のフィルタ規則のなかの１つのフィルタ規則に対応し、前記複数の列のそれぞれが、前記複数のフィルタ規則に対する前記複数のビットのなかの１つのビットに対応するステップと、前記複数のビットの第１ビットを使用して前記複数のノードの第１ノードを提供するステップであって、前記第１ビットが前記複数のフィルタ規則に対する前記少なくとも１つのバイナリ記号の第１最大数を有する前記第１行列のなかの１つの列に対応するステップと、第２行列を前記第１行列に基づいて提供するステップであって、前記第２行列は、前記列内の入力がゼロである場合、前記列内の前記入力に対してワイルドカードを含め、行に対する前記列内の入力が１である場合、前記第１行列の前記行を除外するステップと、第３行列を前記第１行列に基づいて提供するステップであって、前記第３行列は、前記列内の入力が１である場合、前記列内の前記入力に対してワイルドカードを含め、行に対する前記列内の入力がゼロである場合、前記第１行列の前記行を除外するステップと、前記第２行列および第３行列に対して、前記列を選択するステップ、第２行列を提供するステップ、および第３行列を提供するステップを繰り返して、前記決定ツリーに対して複数の残りのノードを提供するステップとによって行われるシステム。
（４０）前記複数のフィルタ規則のそれぞれの優先順位に基づいて、前記複数のフィルタ規則にランク付けすることによって、前記第１行列が提供される上記（３９）に記載のシステム。
（４１）前記複数のフィルタ規則のそれぞれのタイプに基づいて、前記複数のフィルタ規則にランク付けすることによって、前記第１行列が提供される上記（３９）に記載のシステム。
（４２）前記複数のフィルタ規則のそれぞれのタイプおよび前記複数のフィルタ規則のそれぞれの優先順位に基づいて、前記複数のフィルタ規則にランク付けすることによって、前記第１行列が提供される上記（３９）に記載のシステム。
（４３）前記キーがさらに複数のフィールドを含み、かつ前記複数のフィルタ規則のそれぞれに対する前記複数のビットが、前記複数のフィールドのなかの１つのフィールドに対応する上記（３９）に記載のシステム。
（４４）前記第１行列、第２行列、および第３行列が、同一タイプを有する一対の複製行を有することができ、前記一対の複製行の第１行がより高い優先順位を有し、前記一対の複製行の第２行がより低い優先順位を有し、前記一対の複製行のどちらの行も境界記号を有さず、前記第１行列、第２行列、および第３行列が、前記第２行を除去することによってさらに提供される上記（３９）に記載のシステム。
（４５）決定ツリーが、少なくとも１つの別のサブツリーの少なくとも開始ノードに向かう、少なくとも１つの特定のサブツリーの少なくとも１つの特定のノードからの少なくとも１つのポインタで、前記少なくとも１つの特定のサブツリーを置換えることによって形成され、これによって前記少なくとも１つの別のサブツリーを、前記少なくとも１つの特定のサブツリーの代わりに使用できるようにする上記（３９）に記載のシステム。
【図面の簡単な説明】
【図１】従来のネットワークの図である。
【図２】そこで本発明を使用することができるネットワークの図である。
【図３】本発明による、異なるタイプを有するフィルタ規則を試験するための方法のハイレベルの流れ図である。
【図４】本発明による決定ツリーを提供するための方法のより詳細な流れ図である。
【図５】本発明による決定ツリーを提供するための方法のより詳細な流れ図である。
【図６】本発明による決定ツリーを提供するための方法のより詳細な流れ図である。
【図７】本発明による特定の決定ツリーの一部分の例を示す図である。
【図８】本発明の好ましい実施形態による特定の決定ツリーの一部分の例を示す図である。
【図９】本コンピュータ・プログラムをその上に記録することができるディスケットの例を示す図である。
【符号の説明】
１０  ネットワーク
１０’  ネットワーク
１２  ホスト
１２’  ホスト
１４  ホスト
１４’  ホスト
１６  ホスト
１６’  ホスト
１３  ゲートウェイ
１３’  ゲートウェイ
１５  制御ポイント
１７  サーバ
１７’  サーバ
１８  交換器
１８’  交換器
１９  サーバ
１９’  サーバ
２０  ネットワーク
２０’  ネットワーク
２２  ホスト
２２’  ホスト
２４  ホスト
２４’  ホスト
２５  ゲートウェイ
２５’  ゲートウェイ
２６  交換器
２６’  交換器
２７  制御ポイント
２８  サーバ
２８’  サーバ
３０  インターネット
３０’  インターネット
【図１】
0003588332.tif 000012
【図２】
0003588332.tif 000013
【図３】
0003588332.tif 000014
【図４】
0003588332.tif 000015
【図５】
0003588332.tif 000016
【図６】
0003588332.tif 000017
【図７】
0003588332.tif 000018
【図８】
0003588332.tif 000019
【図９】
0003588332.tif 000020