(57)【特許請求の範囲】
【請求項１】
範囲指定される検索ヒット条件をエントリとしてＣＡＭ（Ｃｏｎｔｅｎｔ−Ａｄｄｒｅｓｓａｂｌｅ  Ｍｅｍｏｒｙ）へ登録し、パケットのヘッダ情報に対応するフロー識別子を前記ＣＡＭのエントリを用いて検索する検索システムであって、
前記範囲指定される検索ヒット条件を、２以上かつポート数未満のエントリに分割して前記ＣＡＭに登録する手段を有することを特徴とする検索システム。
【請求項２】
前記ＣＡＭに登録されるエントリは、該エントリにおける下限のポート番号を表すデータエントリと、該データエントリと共に用いることで該エントリの上限のポート番号を規定するマスクエントリとを格納するようにしたことを特徴とする請求項１記載の検索システム。
【請求項３】
前記ＣＡＭに登録されるエントリは、前記ヘッダ情報のうちの少なくとも送信元アドレスと宛先アドレスと宛先ポートとを格納するようにしたことを特徴とする請求項１または２記載の検索システム。
【請求項４】
範囲指定される検索ヒット条件をエントリとしてＣＡＭ（Ｃｏｎｔｅｎｔ−Ａｄｄｒｅｓｓａｂｌｅ  Ｍｅｍｏｒｙ）へ登録し、パケットのヘッダ情報に対応するフロー識別子を前記ＣＡＭのエントリを用いて検索する検索システムであって、
前記範囲指定される検索ヒット条件を、下限から上限に向かって行う分割と上限から下限に向かって行う分割とを組み合わせることにより、２以上かつポート数未満のエントリに分割し、前記ＣＡＭに登録する手段を有することを特徴とする検索システム。
【請求項５】
パケットのヘッダ情報に対応するフロー識別子をＣＡＭ（Ｃｏｎｔｅｎｔ−Ａｄｄｒｅｓｓａｂｌｅ  Ｍｅｍｏｒｙ）のエントリを用いて検索する検索システムに対し、範囲指定される検索ヒット条件をエントリとしてＣＡＭへ登録する検索条件ＣＡＭ登録方法であって、
前記範囲指定される検索ヒット条件を、２以上かつポート数未満のエントリに分割して前記ＣＡＭに登録するステップを有することを特徴とする検索条件ＣＡＭ登録方法。
【請求項６】
前記ＣＡＭに登録されるエントリは、該エントリにおける下限のポート番号を表すデータエントリと、該データエントリと共に用いることで該エントリの上限のポート番号を規定するマスクエントリとを格納するようにしたことを特徴とする請求項５記載の検索条件ＣＡＭ登録方法。
【請求項７】
前記ＣＡＭに登録されるエントリは、前記ヘッダ情報のうちの少なくとも送信元アドレスと、宛先アドレスと、宛先ポートとを格納するようにしたことを特徴とする請求項５または６記載の検索条件ＣＡＭ登録方法。
【請求項８】
パケットのヘッダ情報に対応するフロー識別子を前記ＣＡＭのエントリを用いて検索する検索システムに対し、範囲指定される検索ヒット条件をエントリとしてＣＡＭ（Ｃｏｎｔｅｎｔ−Ａｄｄｒｅｓｓａｂｌｅ  Ｍｅｍｏｒｙ）へ登録する検索条件ＣＡＭ登録方法であって、
前記範囲指定される検索ヒット条件を、下限から上限に向かって行う分割と上限から下限に向かって行う分割とを組み合わせることにより、２以上かつポート数未満のエントリに分割し、前記ＣＡＭに登録することを特徴とする検索条件ＣＡＭ登録方法。
【請求項９】
パケットのヘッダ情報に対応するフロー識別子を前記ＣＡＭのエントリを用いて検索する検索システムに対し、範囲指定される検索ヒット条件をエントリとしてＣＡＭ（Ｃｏｎｔｅｎｔ−Ａｄｄｒｅｓｓａｂｌｅ  Ｍｅｍｏｒｙ）へ登録する検索条件ＣＡＭ登録方法であって、
前記範囲指定される検索ヒット条件を、下限から上限に向かって行う分割のステップと、上限から下限に向かって行う分割のステップを有し、
前記下限から上限に向かって行う分割のステップにおいては、与えられた下限値をエントリのデータエントリとし、該エントリの下限値の最下位ビットから見て最初に1が表れるまでの全ビットを1に置き換えたものを、該エントリにおける上限値として算出し、該エントリの上限値に対応するマスク値を該エントリのマスクエントリとするエントリを作成してエントリとしてＣＡＭに登録し、前記下限値を該上限値に１加えた値に更新する、下限から上限に向かって行う分割における分割エントリ生成ステップを有し、
前記上限から下限に向かって行う分割のステップにおいては、与えられた上限値をエントリの上限値とし、該エントリの下限値の最下位ビットから見て最初に０が表れるまでの全ビットを１に置き換えたものを、該エントリにおけるデータエントリし、該エントリの上限値に対応するマスク値を該エントリのマスクエントリとするエントリを作成してエントリとしてＣＡＭに登録し、前記上限値を該下限値から１引いた値に更新する、上限から下限に向かって行う分割の分割エントリ生成ステップを有し、
前記下限から上限に向かって行う分割の分割エントリ生成ステップは、該ステップにおいて算出された前記範囲指定で与えられた上限値より大きくなるまで繰り返し実行され、
前記限から下限に向かって行う分割の分割エントリ生成ステップは、該ステップにおいて算出された前記範囲指定で与えられた下限値より小さくなるまで繰り返し実行されることを特徴とする検索条件ＣＡＭ登録方法。
【請求項１０】
パケットのヘッダ情報に対応するフロー識別子をＣＡＭ（Ｃｏｎｔｅｎｔ−Ａｄｄｒｅｓｓａｂｌｅ  Ｍｅｍｏｒｙ）のエントリを用いて検索する検索システムに対し、範囲指定される検索ヒット条件をエントリとしてＣＡＭへ登録する検索条件ＣＡＭ登録方法のプログラムであって、
コンピュータに、前記範囲指定される検索ヒット条件を、２以上かつポート数未満のエントリに分割して前記ＣＡＭに登録するステップを実行させるためのプログラム。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は検索システム及びそれに用いる検索条件ＣＡＭ登録方法並びにそのプログラムに関し、特にルータ装置に用いられるＣＡＭ（Ｃｏｎｔｅｎｔ−Ａｄｄｒｅｓｓａｂｌｅ  Ｍｅｍｏｒｙ）への検索条件の登録方法に関する。
【０００２】
【従来の技術】
近年、ルータ装置においては、転送処理の性能を向上させるために、検索システムにＣＡＭを使用する場合が増えており、ＣＰＵ（中央処理装置）が管理する転送テーブルの一部のエントリをＣＡＭにキャッシュすることで、全体的な処理性能を向上させる処理が行われている。
【０００３】
このようなルータ装置でフィルタリング処理を行う場合、ＣＡＭを用いることで装置全体の負荷が小さくなり、性能が向上すると考えられる。ここで、フィルタリングとは、予め設定された条件（フィルタリング条件）に基いて、受信したパケットを通過させるか、廃棄するか等を決める処理である。
【０００４】
フィルタリング条件としてはＩＰ（Ｉｎｔｅｒｎｅｔ  Ｐｒｏｔｏｃｏｌ）アドレスやＴＣＰ／ＵＤＰ（Ｔｒａｎｓｍｉｓｓｉｏｎ  Ｃｏｎｔｒｏｌ  Ｐｒｏｔｏｃｏｌ／Ｕｓｅｒ  Ｄａｔａｇｒａｍ  Ｐｒｏｔｏｃｏｌ）ポート番号の範囲指定（下限及び上限）が設定されることがある。
【０００５】
【発明が解決しようとする課題】
上述した従来の検索システムでは、フィルタリング条件をキャッシュとしてＣＡＭに登録するため、その範囲に含まれる個々の要素を別々のエントリとしてＣＡＭに登録している。
【０００６】
しかしながら、フィルタリング条件の範囲が広くなると、登録されるべきエントリが増加し、その結果、検索ヒット率が下がり、さらにＣＰＵによる転送テーブルの検索回数及びＣＡＭへの登録回数が増加し、装置全体の性能を低下させてしまうという問題がある。
【０００７】
そこで、本発明の目的は上記の問題点を解消し、検索ヒット条件を少ないエントリ数で登録することができ、検索性能を向上させることができる検索システム及びそれに用いる検索条件ＣＡＭ登録方法並びにそのプログラムを提供することにある。
【０００８】
【課題を解決するための手段】
本発明による検索システムは、範囲指定される検索ヒット条件をエントリとしてＣＡＭ（Ｃｏｎｔｅｎｔ−Ａｄｄｒｅｓｓａｂｌｅ  Ｍｅｍｏｒｙ）へ登録し、パケットのヘッダ情報に対応するフロー識別子を前記ＣＡＭのエントリを用いて検索する検索システムであって、前記範囲指定される検索ヒット条件を、２以上かつポート数未満のエントリに分割して前記ＣＡＭに登録する手段を有することを特徴とする。
【０００９】
本発明による検索条件ＣＡＭ登録方法は、パケットのヘッダ情報に対応するフロー識別子をＣＡＭ（Ｃｏｎｔｅｎｔ−Ａｄｄｒｅｓｓａｂｌｅ  Ｍｅｍｏｒｙ）のエントリを用いて検索する検索システムに対し、範囲指定される検索ヒット条件をエントリとしてＣＡＭへ登録する検索条件ＣＡＭ登録方法であって、前記範囲指定される検索ヒット条件を、２以上かつポート数未満のエントリに分割して前記ＣＡＭに登録するステップを有することを特徴とする。
【００１０】
本発明による検索条件ＣＡＭ登録方法のプログラムは、パケットのヘッダ情報に対応するフロー識別子をＣＡＭ（Ｃｏｎｔｅｎｔ−Ａｄｄｒｅｓｓａｂｌｅ  Ｍｅｍｏｒｙ）のエントリを用いて検索する検索システムに対し、範囲指定される検索ヒット条件をエントリとしてＣＡＭへ登録する検索条件ＣＡＭ登録方法のプログラムであって、コンピュータに、前記範囲指定される検索ヒット条件を、２以上かつポート数未満のエントリに分割して前記ＣＡＭに登録するステップを実行させるためのプログラムであることを特徴とする。
【００１１】
すなわち、本発明の検索条件ＣＡＭ登録方法は、検索ヒット条件に範囲指定エントリをＣＡＭ（Ｃｏｎｔｅｎｔ−Ａｄｄｒｅｓｓａｂｌｅ  Ｍｅｍｏｒｙ）へ登録する際に、ＣＡＭのマスク機能（Ｄｏｎ’ｔ  Ｃａｒｅ機能）［検索ヒット情報の情報をマスク情報にてマスクしてから検索を行うための機能であり、マスクする部分はどのような値でもよい（Ｄｏｎ’ｔ  Ｃａｒｅ）］を上手く使うことによって、少ないエントリ数で、一度にその範囲を含む検索条件を全て登録することが可能となる。
【００１２】
したがって、ＣＡＭのマスク機能を使うことで、その範囲に属する全ての要素の検索ヒット条件を少ないエントリ数で登録することが可能となるので、検索システムの性能を向上させることが可能となる。
【００１３】
【発明の実施の形態】
次に、本発明の一実施例について図面を参照して説明する。図１は本発明の一実施例による検索システムの構成を示すブロック図である。図１において、本発明の一実施例による検索システムはルータ装置における検索システムの構成例を示しており、パケットのヘッダ情報を入力とし、そのパケットが属するフロー識別子を出力するシステムである。
【００１４】
ここで、ヘッダ情報とは受信パケットのヘッダに含まれるＭＡＣ（ＭｅｄｉａＡｃｃｅｓｓ  Ｃｏｎｔｒｏｌ）アドレスやＩＰ（Ｉｎｔｅｒｎｅｔ  Ｐｒｏｔｏｃｏｌ）アドレス、Ｌ４（レイヤ４）ポート番号等の組合わせである。フロー識別子とはそのヘッダ情報を持つパケットに対してルータ装置が行うべき転送処理を特定するための識別子である。
【００１５】
上記の検索システムは検索エンジン１と、ＣＡＭ（Ｃｏｎｔｅｎｔ−Ａｄｄｒｅｓｓａｂｌｅ  Ｍｅｍｏｒｙ）２と、小容量高速メモリ３と、ＣＰＵ（中央処理装置）４と、大容量低速メモリ５と、記録媒体６とから構成されており、検索エンジン１及びＣＰＵ４が実行するプログラムは記録媒体６に格納されている。
【００１６】
検索エンジン１はパケットのヘッダ情報が入力されると、ＣＡＭ２と小容量高速メモリ３とを用いてヘッダ情報に対応するフロー識別子を検索し、検索が成功すると、その検索結果として得られたフロー識別子を出力する。また、検索エンジン１は検索が失敗すると、ＣＰＵ４と大容量低速メモリ５とを用いて再検索を行い、その検索結果として得られたフロー識別子を出力する。
【００１７】
ＣＡＭ２及び小容量高速メモリ３は高速であり、検索キーに対する検索結果を瞬時に出力する。ＣＡＭ２は検索ヒット情報の情報をマスク情報にてマスクしてから検索を行うためのマスク機能（Ｄｏｎ’ｔ  Ｃａｒｅ機能）を持っており、その場合、マスクする部分はどのような値でもよい（Ｄｏｎ’ｔ  Ｃａｒｅ）。
【００１８】
一方、ＣＰＵ４はソフトウェア処理のため、ＣＡＭ２に比べて検索に長い時間を要する。大容量低速メモリ５にはルータ装置（図示せず）が扱う全てのヘッダ情報とフロー識別子との対応が検索エントリとして格納されている。
【００１９】
図２は図１の大容量低速メモリ５に格納される検索エントリの具体例を示す図である。図２において、大容量低速メモリ５の各エントリ＃２１〜＃２４にはヘッダ情報として送信元アドレス［「ＳＡ（Ｓｏｕｒｃｅ  Ａｄｄｒｅｓｓ）＃１」，「ＳＡ＃２」，「ＳＡ＃３」，「ＳＡ＃４」］と、宛先アドレス［「ＤＡ（Ｄｅｓｔｉｎａｔｉｏｎ  Ａｄｄｒｅｓｓ）＃１」，「ＤＡ＃２」，「ＤＡ＃３」，「ＤＡ＃４」］と、宛先ポート（「２０〜１５０」，「５０００〜６０００」，「１００〜２００」，「１００００〜２００００」）とが格納され、それに対応するフロー識別子（「３」，「１」，「５」，「８」）が格納されている。ここで、各エントリ＃２１〜＃２４の宛先ポートは「下限〜上限」のような範囲指定の形式で与えられる点に注意する。
【００２０】
図３は図１のＣＡＭ２及び小容量高速メモリ３に格納される検索エントリの具体例を示す図である。図３において、ＣＡＭ２の各エントリ＃３１〜＃３６には送信元アドレス（３２ビット）のデータ「ＳＡ＃３」及びマスク情報「１１１１・・・１」と、宛先アドレス（３２ビット）のデータ「ＤＡ＃３」及びマスク情報「１１１１・・・１」と、宛先ポート（１６ビット）のデータ「００００００００  ０１１００１００」，「００００００００  ０１１０１０００」，「００００００００  ０１１１００００」，「００００００００  １０００００００」，「００００００００  １１００１０００」，「００００００００  １１００００００」及びマスク情報「１１１１１１１１  １１１１１１００」，「１１１１１１１１  １１１１１０００」，「１１１１１１１１  １１１１００００」，「１１１１１１１１  １０００００００」，「１１１１１１１１  １１１１１１１１」，「１１１１１１１１  １１１１１０００」とが格納され、小容量高速メモリ３の各エントリにはそれに対応してフロー識別子「５］が格納されている。
【００２１】
図４（ａ），（ｂ）は本発明の一実施例で用いられるパケットの構成例を示す図であり、図５は本発明の一実施例による検索システムのアルゴリズムを示すフローチャートである。これら図１〜図５を参照して本発明の一実施例による検索システムの動作について説明する。図５に示すアルゴリズムはＣＰＵ４が記録媒体６のプログラムを実行することで実現される。
【００２２】
ＣＰＵ４は検索エンジン１からヘッダ情報が与えられると、そのヘッダ情報を持つ検索エントリを大容量低速メモリ５から検索し、対応するフロー識別子を検索エンジン１へ出力する。例えば、図４（ａ）に示すパケット＃４１のヘッダ情報がＣＰＵ４に与えられると、大容量低速メモリ５から図２に示すエントリ＃２３を検索し、そのエントリのフロー識別子＝５を検索エンジン１へ出力する。
【００２３】
ＣＰＵ４は大容量低速メモリ５を検索した後、得られた検索エントリのヘッダ情報をＣＡＭ２に登録し、フロー識別子を小容量高速メモリ３へ登録する。この時、図２に示すエントリの宛先ポートのような範囲指定が検索ヒット条件に含まれる場合には、図５に示すアルゴリズムを用いて複数のエントリに分割したものをＣＡＭ２へ登録する。例えば、大容量低速メモリ５から図２に示すエントリ＃２３を検索した時、図３に示すような検索エントリがＣＡＭ２及び小容量高速メモリ３に追加登録される。
【００２４】
ＣＡＭ２は各エントリがデータエントリとマスクエントリとから構成されるターナリＣＡＭであり、各ビットについて“０”、“１”、または“Ｄｏｎ’ｔ  Ｃａｒｅ”のいずれかの値を検索条件として指定することができる。ＣＡＭ２は検索エンジン１から検索キーとしてヘッダ情報が入力されると、そのヘッダ情報に一致するエントリを瞬時に見つけ出し、そのアドレスを小容量高速メモリ３へ受渡す。
【００２５】
小容量高速メモリ３はＣＡＭ２からエントリのアドレスが入力されると、そのアドレスに格納されたフロー識別子を検索エンジン１へ出力する。例えば、ＣＡＭ２及び小容量高速メモリ３に図３に示すようなエントリが格納されており、図４（ａ）に示すパケット＃４１のヘッダ情報が検索エンジン１から与えられた時、ＣＡＭ２はエントリ＃３３を瞬時に見つけ出し、小容量高速メモリ３に格納されたフロー識別子＝５が検索エンジン１へ出力される。ＣＡＭ２及び小容量高速メモリ３に登録されたエントリは、ＣＰＵ４によって最近検索されなくなったものから定期的に削除されるものとする。
【００２６】
図５に示すフローチャートは検索ヒット条件として範囲条件Ａ〜Ｂが与えられた時、ＣＡＭ２へ登録すべき複数のデータエントリＤ［０］，Ｄ［１］，．．．，Ｄ［ｎ−１］、マスクエントリＭ［０］，Ｍ［１］，．．．，Ｍ［ｎ−１］及びエントリ数ｎを求めるアルゴリズムを示す。図５に示すフローチャート中のＡ，Ｂ，Ｄ［ｉ］，Ｍ［ｉ］及びＡ’、Ｂ’は固定長ビット幅の変数であり、計算式中のＯＲ、ＸＯＲ、ＮＯＴはそれぞれビット毎のＯＲ、Ｅｘｃｌｕｓｉｖｅ  ＯＲ、ＮＯＴの論理演算を意味する。
【００２７】
図１に示す検索システムの初期状態として、大容量低速メモリ５には図２に示す検索エントリが格納されており、ＣＡＭ２及び小容量高速メモリ３には有効なエントリが１つも格納されていないものとする。
【００２８】
ルータ装置が図４（ａ）に示すパケット＃４１を受信し、そのヘッダ情報として送信元アドレス＝ＳＡ３、宛先ＩＰアドレス＝ＤＡ３、宛先ポート＝１２１が検索エンジン１に入力されると、検索エンジン１はこれらのヘッダ情報を検索キーとしてＣＡＭ２へ入力する。この時点でＣＡＭ２には対応するエントリが存在しないため、ＣＡＭ２に対する検索は失敗し、検索エンジン１はヘッダ情報をＣＰＵ４へ入力する。
【００２９】
ＣＰＵ４はこのヘッダ情報を検索キーとして大容量低速メモリ５を検索し、図２に示すエントリ＃２３を得る。このエントリ＃２３に含まれるフロー識別子＝５を検索エンジン１へ受渡し、検索エンジン１はこれを本検索システムの出力とする。
【００３０】
この時、ＣＰＵ４は得られた検索エントリ＃２３をＣＡＭ２及び小容量高速メモリ３に登録するが、宛先ポートが［下限〜上限］の範囲条件で与えられているため、図５に示すアルゴリズムを用いて宛先ポートの［下限〜上限］の範囲をマスク情報にてマスクしやすいように分割し、ＣＡＭ２に登録すべき複数のエントリを求める。以下、複数のエントリを求める処理について説明する。
【００３１】
初期値として、エントリ＃２３の範囲条件の下限Ａ＝１００、上限Ｂ＝２００を設定する。最初に登録すべきエントリは、下限をＡ＝１００とし、計算式＃ａ１［Ａ’←Ａ  ＯＲ  （Ａ−１）］によって上限Ａ’＝１０３が得られる。
【００３２】
条件式＃ａ２（Ａ’＞Ｂ）によって、上限Ａ’＝１０３が最終的な上限Ｂ＝２００以下であることを確認し、計算式＃ａ３［Ｄ［ｎ］←Ａ，Ｍ［ｎ］←ＮＯＴ（Ａ  ＸＯＲ  Ａ’）］によってデータエントリＤ［０］＝１００＝００００００００，０１１００１００（２進）と、マスクエントリＭ［０］＝１１１１１１１１，１１１１１１００（２進）とが求まる（図３に示すエントリ＃３１）。このエントリは宛先ポートが１００〜１０３の検索キーにヒットする。
【００３３】
２番目のエントリは計算式＃ａ４（ｎ←ｎ＋１，Ａ←Ａ’＋１）によって下限Ａ＝１０４、計算式＃ａ１によって上限Ａ’＝１１１がそれぞれ得られる。条件式＃ａ２によって上限Ａ’＝１１１が最終的な上限Ｂ＝２００以下であることを確認し、計算式＃ａ３によってデータエントリＤ［１］＝１０４＝００００００００，０１１０１０００（２進）と、マスクエントリＭ［１］＝１１１１１１１１，１１１１１０００（２進）とが求まる（図３に示すエントリ＃３２）。このエントリは宛先ポートが１０４〜１１１の検索キーにヒットする。
【００３４】
３番目のエントリは計算式＃ａ４によって下限Ａ＝１１２、計算式＃ａ１によって上限Ａ’＝１２７がそれぞれ得られる。条件式＃ａ２によって上限Ａ’＝１２７が最終的な上限Ｂ＝２００以下であることを確認し、計算式＃ａ３によってデータエントリＤ［２］＝１１２＝００００００００，０１１１００００（２進）と、マスクエントリＭ［２］＝１１１１１１１１，１１１１００００（２進）とが求まる（図３に示すエントリ＃３３）。このエントリは宛先ポートが１１２〜１２７の検索キーにヒットする。
【００３５】
４番目のエントリは計算式＃ａ４によって下限Ａ＝１２８、計算式＃ａ１によって上限Ａ’＝１９１がそれぞれ得られる。条件式＃ａ２によって上限Ａ’＝１９１が最終的な上限Ｂ＝２００以下であることを確認し、計算式＃ａ３によってデータエントリＤ［３］＝１２８＝００００００００，１０００００００（２進）と、マスクエントリＭ［３］＝１１１１１１１１，１０００００００（２進）とが求まる（図３に示すエントリ＃３４）。このエントリは宛先ポートが１２８〜１９１の検索キーにヒットする。
【００３６】
５番目のエントリは計算式＃ａ４によって下限Ａ＝１９２、計算式＃ａ１によって上限Ａ’＝２５５がそれぞれ得られる。しかしながら、条件式＃ａ２によって上限Ａ’＝２５５が最終的な上限Ｂ＝２００を超えていることが確認されるため、データエントリ及びマスクエントリの計算は行わず、＃ｂ１の処理に移り、残りの宛先ポートが下限Ａ＝１９２から上限Ｂ＝２００の検索キーにヒットするエントリを求める。
【００３７】
５番目のエントリは上限Ｂ＝２００とし、計算式＃ｂ１［Ｂ’←Ｂ  ＡＮＤ  ＮＯＴ（ＮＯＴ（Ｂ）−１）］によって下限Ｂ’＝２００が得られる。条件式＃ｂ２（Ａ＞Ｂ’）によって、下限Ｂ’＝２００がＡ＝１９２以上であることを確認し、計算式＃ｂ３［Ｄ［ｎ］←Ｂ’，Ｍ［ｎ］←ＮＯＴ（Ｂ  ＸＯＲ  Ｂ’）］によってデータエントリＤ［４］＝２００＝００００００００，１１００１０００（２進）と、マスクエントリＭ［４］＝１１１１１１１１，１１１１１１１１（２進）とが求まる（図３に示すエントリ＃３５）。このエントリは宛先ポートが２００の検索キーにヒットする。
【００３８】
６番目のエントリは計算式＃ｂ４（ｎ←ｎ＋１，Ｂ←Ｂ’−１）によって上限Ｂ＝１９９、計算式＃ｂ１によって下限Ｂ’＝１９２がそれぞれ得られる。条件式＃ｂ２によって下限Ｂ’＝１９２がＡ＝１９２以上であることを確認し、計算式＃ｂ３によってデータエントリＤ［５］＝１９２＝００００００００，１１００００００（２進）と、マスクエントリＭ［５］＝１１１１１１１１，１１１１１０００（２進）とが求まる（図３に示すエントリ＃３６）。このエントリは宛先ポートが１９２〜１９９の検索キーにヒットする。
【００３９】
７番目のエントリは計算式＃ｂ４によって上限Ｂ＝１９１，下限Ｂ’＝１２８がそれぞれ得られるが、条件式＃ｂ２によって下限Ｂ’＝１２８がＡ＝１９２未満であるため、ここで処理を終了する。
【００４０】
以上の処理によって、図３に示すＣＡＭ２の宛先ポートフィールドに登録すべきデータエントリＤ［０］，Ｄ［１］，．．．，Ｄ［５］及びマスクエントリＭ［０］，Ｍ［１］，．．．，Ｍ［５］が得られる。ＣＰＵ４はこれらを用いてＣＡＭ２及び小容量高速メモリ３に、図３に示すように、エントリ登録を行い、パケット＃４１に関する処理を終了する。
【００４１】
パケット＃４１に続いてルータ装置が図４（ｂ）に示すパケット＃４２を受信すると、そのヘッダ情報として送信元アドレス＝ＳＡ３、宛先アドレス＝ＤＡ３、宛先ポート＝１５３がそれぞれ検索エンジン１へ入力され、検索エンジン１は検索キーとしてそれをＣＡＭ２へ入力する。
【００４２】
ＣＡＭ２には既に、図３に示すエントリが登録されており、入力されたヘッダ情報はエントリ＃３４にヒットする。検索エンジン１は小容量高速メモリ３から対応するフロー識別子＝５を受取り、それを検索システムの出力とする。
【００４３】
このように、同一の検索エントリに属するパケットを再び受信した時に、ＣＡＭ２及び小容量高速メモリ３に既にエントリが存在するため、ＣＰＵ４と大容量低速メモリ５とによる低速な検索処理を必要とせず、非常に短時間で対応するフロー識別子を得ることができる。
【００４４】
検索ヒット条件に範囲指定が含まれる検索エントリをＣＡＭ２に登録する場合、従来、その範囲に属する個々の要素毎にエントリを登録しているため、ＣＡＭ２に登録するエントリ数が増加し、検索システムの性能の低下につながってしまう。
【００４５】
これに対し、本発明ではＣＡＭ２のマスク機能（Ｄｏｎ’ｔ  Ｃａｒｅ機能）を使うことで、その範囲に属する全ての要素の検索ヒット条件を少ないエントリ数で登録することができ、検索システムの性能を向上させることができる。
【００４６】
上記のように、１つのＣＡＭ２によって多くの検索ヒット条件を登録することができるため、ＣＡＭ２の１つ当たりの検索性能を向上させることができる。また、所望の性能を出すために必要となるＣＡＭ２のエントリ数を少なくすることができるため、コスト及び消費電力を小さくすることができる。
【００４７】
さらに、ＣＡＭ２へのエントリ登録回数が少なくなり、ＣＰＵ４の負荷を小さくすることができる。さらにまた、ＣＡＭ２の検索ヒット率が高くなるため、ＣＰＵ４からＣＡＭ２へのエントリ登録回数が少なくなり、ＣＰＵ４の負荷を小さくすることができる。
【００４８】
上述した本発明の一実施例によるＣＡＭ２への検索条件の登録方法では、特に範囲の上限と下限との差が大きいほど、従来のＣＡＭ２への検索条件の登録方法に比べてその効果が大きくなる。
【００４９】
尚、上記の説明ではヘッダ情報のうち、範囲指定される宛先ポートのみを分割して複数のエントリを求め、それら複数のエントリを一括してＣＡＭ２へ登録する処理について述べたが、ヘッダ情報の送信元アドレスや宛先アドレスも範囲指定される場合には、上記と同様の方法で、ＣＡＭ２へ登録することができる。
【００５０】
【発明の効果】
以上説明したように本発明によれば、範囲指定される検索ヒット条件を含むエントリをＣＡＭへ登録し、パケットのヘッダ情報に対応するフロー識別子を検索する検索システムにおいて、エントリにおける範囲指定される検索ヒット条件を所定アルゴリズムを用いて複数に分割してＣＡＭに登録することによって、検索ヒット条件を少ないエントリ数で登録することができ、検索性能を向上させることができるという効果がある。
【図面の簡単な説明】
【図１】本発明の一実施例による検索システムの構成を示すブロック図である。
【図２】図１の大容量低速メモリに格納される検索エントリの具体例を示す図である。
【図３】図１のＣＡＭ及び小容量高速メモリに格納される検索エントリの具体例を示す図である。
【図４】（ａ），（ｂ）は本発明の一実施例で用いられるパケットの構成例を示す図である。
【図５】本発明の一実施例による検索システムのアルゴリズムを示すフローチャートである。
【符号の説明】
１  検索エンジン
２  ＣＡＭ
３  小容量高速メモリ
４  ＣＰＵ
５  大容量低速メモリ
６  記録媒体
【図１】
0003711895.tif 000002
【図２】
0003711895.tif 000003
【図３】
0003711895.tif 000004
【図４】
0003711895.tif 000005
【図５】
0003711895.tif 000006