(57)【要約】【課題】メモリの効率的な利用を可能とし、検索対象データのビット列の増大に対処可能とする装置の提供。【解決手段】  所定ビット幅のデジタルビット列の検索対象ビットフィールドのうちの第１のビットフィールドを第１の検索キー１１０とし、第２のビットフィールドを識別子５１０とし、第１の検索キーの各値に対応して配置され、それぞれが前記識別子の値に対応した第２の検索キー４１０を保持するエントリを含む第１の検索テーブル６１０と、第２の検索キーの各値に対応したエントリに、検索対象ビットフィールドに対応した内容を保持する第２の検索テーブル２１０と、を備え、第１の検索キー１１０と識別子５１０を用いて第１の検索テーブル６１０を検索することで取得した第２の検索キー４１０にて、第２検索テーブル２１０の検索が行われる。【選択図】図１
2008244642.tif 000002
【特許請求の範囲】
【請求項１】
所定ビット幅のデジタルビット列の検索対象ビットフィールドのうちの第１のビットフィールドを第１の検索キーとし、第２のビットフィールドを識別子とし、
前記第１の検索キーの各値に対応して配置され、それぞれが前記識別子の値に対応した第２の検索キーを保持するエントリを含む第１の検索テーブルと、
前記第２の検索キーの各値に対応したエントリに、前記検索対象ビットフィールドに対応した内容を保持する第２の検索テーブルと、
を備え、
前記第１の検索キーと前記識別子を用いて前記第１の検索テーブルを検索することで取得した前記第２の検索キーにて、前記第２検索テーブルの検索が行われる、ことを特徴とする検索装置。
【請求項２】
所定ビット幅のデジタルビット列の検索対象ビットフィールドのうちの第１のビットフィールドを第１の検索キーとし、第２のビットフィールドを識別子とし、
前記第１の検索キーに対応するエントリに、前記識別子と第２の検索キーの組と、前記検索対象ビットフィールドに対応した内容とを保持する検索テーブルを備え、
前記検索テーブルにおいて、前記第１の検索キーで検索されたエントリのうち、前記識別子が合致する組の前記第２の検索キーに基づき、前記第２の検索キーに対応する前記検索テーブルのエントリの内容が検索結果とされる、ことを特徴とする検索装置。
【請求項３】
前記第２の検索テーブルのエントリに格納される、前記検索対象ビットフィールドに対応した内容は、前記検索対象ビットフィールドに対応して割り当てられる処理である、ことを特徴とする請求項１記載の検索装置。
【請求項４】
前記第２の検索テーブルのエントリの総数は、割り当てられる処理の数に等しい、ことを特徴とする請求項３記載の検索装置。
【請求項５】
前記識別子をなす第２のビットフィールドが、前記デジタルビット列のＬＳＢ（Ｌｅａｓｔ  Ｓｉｇｎｉｆｉｃａｎｔ  Ｂｉｔ）を少なくとも含み、前記第１の検索キーをなす第１のビットフィールドは、前記第２のビットフィールドに隣接するビット列よりなる、ことを特徴とする請求項１記載の検索装置。
【請求項６】
所定ビット幅のデジタルビット列の検索対象ビットフィールドのうちの第１のビットフィールドを第１の検索キーとし、第２のビットフィールドを識別子とし、
前記第１の検索キーの各値に対応して配置され、それぞれが前記識別子の値に対応した第２の検索キーを保持するエントリを含む第１の検索テーブルを設け、
前記第２の検索キーの各値に対応したエントリに、前記検索対象ビットフィールドに対応した内容を保持する第２の検索テーブルを設け、
前記第１の検索キーと前記識別子を用いて前記第１の検索テーブルを検索することで前記第２の検索キーを取得する工程と、
前記第２の検索キーを用いて前記第２検索テーブルを検索する工程と、
を含む、ことを特徴とする検索方法。
【請求項７】
所定ビット幅のデジタルビット列の検索対象ビットフィールドのうちの第１のビットフィールドを第１の検索キーとし、第２のビットフィールドを識別子とし、
前記第１の検索キーに対応するエントリに、前記識別子と第２の検索キーの組と、前記検索対象ビットフィールドに対応した内容とを保持する検索テーブルを設け、
前記検索テーブルを、前記第１の検索キーで検索する工程と、
前記第１の検索キーで検索されたエントリのうち、前記識別子が合致する組の第２の検索キーに基づき、第２の検索キーに対応する、前記検索テーブルのエントリの内容を検索結果とする工程と、
を含む、ことを特徴とする検索方法。
【請求項８】
所定ビット幅のデジタルビット列の検索対象ビットフィールドのうちの第１のビットフィールドを第１の検索キーとし、第２のビットフィールドを識別子とし、
前記第１の検索キーの各値に対応して配置され、それぞれが前記識別子の値に対応した第２の検索キーを保持するエントリを含む第１の検索テーブルと、
前記第２の検索キーの各値に対応したエントリに、前記検索対象ビットフィールドに対応した内容を保持する第２の検索テーブルと、
を備えたコンピュータに、
前記第１の検索キーと前記識別子とで前記第１の検索テーブルを検索して第２の検索キーを取得する処理と、
前記第２の検索キーにて前記第２検索テーブルを検索する処理と、
を実行させるプログラム。
【請求項９】
所定ビット幅のデジタルビット列の検索対象ビットフィールドのうちの第１のビットフィールドを第１の検索キーとし、第２のビットフィールドを識別子とし、
前記第１の検索キーに対応するエントリに、前記識別子と第２の検索キーの組と、前記検索対象ビットフィールドに対応した内容とを保持する検索テーブルを備えたコンピュータに、
前記検索テーブルを、前記第１の検索キーで検索する処理と、
前記第１の検索キーで検索されたエントリのうち、前記識別子が合致する組の第２の検索キーに基づき、第２の検索キーに対応する、前記検索テーブルのエントリの内容を検索結果とする処理と、
を実行させるプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は検索装置と方法とプログラムに関し、特に検索ビットの増大に対応可能な検索装置と方法とプログラムに関する。
【背景技術】
【０００２】
近年、通信分野におけるデータトラフィックのサービスの細分化に伴い、データ中継器（ルータ、スイッチ等）にトラフィックデータ毎に要求されるサービスを決定する機能が要求されている。
【０００３】
機能の細分化を実現するための情報としては、トラフィックデータに付与された送信元、送信先アドレスであったり、スイッチングに用いられる識別子等、様々なものが用いられるが、いずれも、デジタルビット列の群である。
【０００４】
個々のトラフィックに対する処理を決定するにあたり、アドレス、識別子等のデジタルビット列パタンよりなる検索データと、該検索データに対応する処理とを、１対１に割り当てる手法が、従来より、用いられている。
【０００５】
トラフィックに対する処理の種別の増大に伴い、検索データのビット幅も増大する傾向にあり、検索データに対する処理を決定するためのメモリ（検索テーブル）のアドレス空間は、指数関数的に増大する。
【０００６】
図４は、従来の典型的な検索手法の一例を説明する図である。検索データ３００の任意のビット列を検索範囲（図５では下位４ビット）とし、該検索範囲をそのまま検索キー１００として処理を決定する構成の場合、選択した任意のビット列に対して、２の（ビット列幅）乗の検索テーブル２００のアドレス空間が必要になり、検索範囲のビット幅に対して、指数関数的に膨大な検索テーブル空間が必要になる。なお、図４では、４ビットの検索キー１００に対して、検索テーブル２００のエントリは、２４＝１６個用意され、処理２、処理４、処理５のエントリは重複して設けられている。また、図５は、図４の検索手法の検索ツリーの構成の一例を示す図である。４ビットの検索キーに対応して４段のバイナリツリーから構成され、各リーフ（図４の検索テーブル２００の各エントリ）に処理が割り当てられる。図５のツリーに示すように、ツリー０００１、００１０のリーフでは処理２が重複して割り当てられており、ツリー０１００、０１０１、０１１０のリーフでは処理４が重複して割り当てられており、ツリー０１１１、１０００のリーフでは処理５が重複して割り当てられている。
【０００７】
なお、検索テーブルを多段構成としたものとして、特許文献１には、ルータに他のルータ等から転送されてきたデータ信号の次の転送先を決定する転送先検索装置の構成として、検索テーブルを構成する第一テーブル群が格納された第一記憶部と、検索テーブルを構成する第二テーブルが格納された第二記憶部と、第一テーブル群へのアクセスを制御する第一制御部と、第二テーブルへのアクセスを制御する第二制御部とを備えた構成が開示されている。特許文献１では、ＩＰアドレスを８ビットずつ４つに分割して選られた分割ビット列を、上位から１段目〜４段目第一テーブルのエントリアドレスに対応させ、各第一テーブルには、第二テーブルのエントリを示す第二テーブルポインタのみを設定し、第二テーブルには、次段の第一テーブルを示す第一テーブルポインタ及びホップポインタを設定しておき、各第一テーブルのエントリアドレスをそのままオフセットとして検索し、第一及び第二テーブルポインタにしたがって、第二及び第一テーブルに交互にアクセスして、次の転送先を示すホップポインタを検索する。なお、特許文献１の構成は、複数の第一テーブル群が第一の検索テーブルを構成しており、後述される本発明の構成とは全く相違している。
【０００８】
【特許文献１】特開２０００−３０７６４１号公報
【発明の開示】
【発明が解決しようとする課題】
【０００９】
検索テーブルをメモリで構成する場合、検索対象データのビット列が増えるにつれて、メモリ容量及びメモリ個数も指数関数的に増えていくため、事実上検索対象データのビット列は、使用可能なメモリ容量及び実装可能なメモリ個数によって上限が制約される。しかしながら、実際の処理割り当てについては、検索ビット列のあるエリアをマスクして、複数の処理を一つの処理として決定する場合も多く、必ずしも検索データに対する処理を決定するためのメモリ空間等が２の（検索ビット列幅）乗の空間を必要としない。
【００１０】
したがって、本発明の目的は、増大するメモリ空間の増加に対し効率的にメモリ空間を使用する装置、方法、プログラムを提案することにある。
【課題を解決するための手段】
【００１１】
本願で開示される発明は、前記課題を解決するために、概略以下の構成とされる。
【００１２】
本発明の１つの側面に係る検索装置は、所定ビット幅のデジタルビット列の検索対象ビットフィールドのうちの第１のビットフィールドを第１の検索キーとし、第２のビットフィールドを識別子とし、
前記第１の検索キーの各値に対応して配置され、それぞれが前記識別子の値に対応した第２の検索キーを保持するエントリを含む第１の検索テーブルと、
前記第２の検索キーの各値に対応したエントリに、前記検索対象ビットフィールドに対応した内容を保持する第２の検索テーブルと、
を備え、前記第１の検索キーと前記識別子を用いて前記第１の検索テーブルを検索することで取得した前記第２の検索キーにて、前記第２の検索テーブルの検索が行われる構成としたものである。
【００１３】
本発明の他の側面に係る検索装置は、所定ビット幅のデジタルビット列の検索対象ビットフィールドのうちの第１のビットフィールドを第１の検索キーとし、第２のビットフィールドを識別子とし、
前記第１の検索キーに対応するエントリに、前記識別子と第２の検索キーの組と、前記検索対象ビットフィールドに対応した内容とを保持する検索テーブルを備え、
前記検索テーブルにおいて、前記第１の検索キーで検索されたエントリのうち、前記識別子が合致する組の第２の検索キーに基づき、前記第２の検索キーに対応する前記検索テーブルのエントリの内容が検索結果とされる。
【００１４】
本発明において、前記第２の検索テーブルのエントリに格納される、前記検索対象ビットフィールドに対応した内容は、前記検索対象ビットフィールドに対応して割り当てられる処理である。
【００１５】
本発明において、前記第２の検索テーブルのエントリの総数は、割り当てられる処理の数に等しい。
【００１６】
本発明において、前記識別子をなす第２のビットフィールドが、前記デジタルビット列のＬＳＢ（Ｌｅａｓｔ  Ｓｉｇｎｉｆｉｃａｎｔ  Ｂｉｔ）を少なくとも含み、前記第１の検索キーをなす第１のビットフィールドは、前記第２のビットフィールドに隣接するビット列よりなる。
【００１７】
本発明に係る方法は、所定ビット幅のデジタルビット列の検索対象ビットフィールドのうちの第１のビットフィールドを第１の検索キーとし、第２のビットフィールドを識別子とし、前記第１の検索キーの各値に対応して配置され、それぞれが前記識別子の値に対応した第２の検索キーを保持するエントリを含む第１の検索テーブルを設け、
前記第２の検索キーの各値に対応したエントリに、前記検索対象ビットフィールドに対応した内容を保持する第２の検索テーブルを設け、
前記第１の検索キーと前記識別子を用いて前記第１の検索テーブルを検索することで前記第２の検索キーを取得する工程と、
前記第２の検索キーを用いて前記第２の検索テーブルを検索する工程と、を含む。
【００１８】
本発明の他の側面に係る方法は、所定ビット幅のデジタルビット列の検索対象ビットフィールドのうちの第１のビットフィールドを第１の検索キーとし、第２のビットフィールドを識別子とし、
前記第１の検索キーに対応するエントリに、前記識別子と第２の検索キーの組と、前記検索対象ビットフィールドに対応した内容とを保持する検索テーブルを設け、
前記検索テーブルを、前記第１の検索キーで検索する工程と、
前記第１の検索キーで検索されたエントリのうち、前記識別子が合致する組の第２の検索キーに基づき、第２の検索キーに対応する、前記検索テーブルのエントリの内容を検索結果とする工程と、を含むようにしてもよい。
【００１９】
本発明に係るコンピュータプログラムは、所定ビット幅のデジタルビット列の検索対象ビットフィールドのうちの第１のビットフィールドを第１の検索キーとし、第２のビットフィールドを識別子とし、前記第１の検索キーの各値に対応して配置され、それぞれが前記識別子の値に対応した第２の検索キーを保持するエントリを含む第１の検索テーブルと、
前記第２の検索キーの各値に対応したエントリに、前記検索対象ビットフィールドに対応した内容を保持する第２の検索テーブルと、
を備えたコンピュータに、
前記第１の検索キーと前記識別子とで前記第１の検索テーブルを検索して第２の検索キーを取得する処理と、
前記第２の検索キーにて前記第２の検索テーブルを検索する処理と、
を実行させるプログラムよりなる。
【００２０】
本発明に係るコンピュータプログラムは、所定ビット幅のデジタルビット列の検索対象ビットフィールドのうちの第１のビットフィールドを第１の検索キーとし、第２のビットフィールドを識別子とし、第１の検索キーに対応するエントリに、前記識別子と第２の検索キーの組と、前記検索対象ビットフィールドに対応した内容とを保持する検索テーブルを備えたコンピュータに、
前記検索テーブルを、前記第１の検索キーで検索する処理と、
前記第１の検索キーで検索されたエントリのうち、前記識別子が合致する組の第２の検索キーに基づき、第２の検索キーに対応する、前記検索テーブルのエントリの内容を検索結果とする処理と、を前記コンピュータに実行させるプログラムよりなる。
【発明の効果】
【００２１】
本発明によれば、検索対象ビット列のあるエリアをマスクして複数の処理を一つの処理として決定する場合、従来手法のように、２の（ビット列幅）乗の検索テーブルの空間を使用することなく、検索することができる。この結果、本発明によれば、メモリの効率的な利用を可能とし、検索対象データのビット列を大幅に増やすことができる。
【発明を実施するための最良の形態】
【００２２】
上記した本発明についてさらに詳細に説明すべく添付図面を参照して以下に説明する。図１は、本発明の一実施の形態を説明するための図である。図１を参照すると、検索対象となる検索データ３１０の中の任意のビット列（検索対象ビットフィールド）に対して、第１、第２のビットフィールドを第１、第２の検索範囲とする。なお、図１等では、説明の簡単のため、第１の検索範囲、第２の検索範囲の２つの検索範囲（２つの検索キー）を例に説明するが、本発明はかかる構成に制限されるものでないことは勿論である。
【００２３】
検索データ３１０の第１の検索範囲で指定された第１の検索範囲（下位２ビット目からの３ビット）を第１の検索キー１１０とする。第１の検索キー１１０と、検索データ３１０の第２の検索範囲（最下位ビット）を識別子５１０とし、第１の検索キー１１０の各値に対応して配置され、それぞれが識別子５１０の値（０又は１）に対応した第２の検索キー４１０を保持するエントリを含む第１の検索テーブル６１０と、第２の検索キー４１０の各値に対応したエントリに、検索対象ビットフィールドに対応した処理を保持する第２の検索テーブル２１０と、を備えている。特に制限されないが、第２の検索テーブル２１０の各エントリに格納される処理は、検索データ３１０に対して行われる処理とされる（ただし、処理の振り分け先（アドレス）等であってもよい）。
【００２４】
図１において、検索データ３１０の第１の検索範囲（３ビット）に指定したビット列（”０１０”）を、第１の検索キー１１０（”０１０”）とし、第１の検索キー１１０と第２の検索範囲（ＬＳＢ）から得られるビット列（”１”）を、識別子５１０とした検索テーブル６１０において、第２の検索キー４１０（”００１１”）が検索され、検索データ３１０に対して行われる処理（処理４）が順次検索される。
【００２５】
図１に示すように、第２の検索テーブル２１０は、処理１〜処理８に対応して８個のエントリを保持する。一方、図４に示した従来手法では、処理１〜処理８に対して検索テーブルのエントリ数は１６個とされる。
【００２６】
図２は、本発明の第２の実施の形態を説明する図である。図１の前記実施の形態と相違する点は、検索テーブル６１０の実体を検索テーブル２２０内部に配置したことである。
【００２７】
検索対象となる検索データの中の任意のビット列に対し、第１の検索範囲、第２の検索範囲を指定する。第１の検索範囲（３ビット）に指定したビット列を第１の検索キー１１０（例えば”０１０”）とし、第２の検索範囲（１ビット）を識別子５１０（例えば”１”）とし、第１の検索キー１１０と識別子５１０で検索される、第２の検索キー４１０と検索データに対して行われる処理を配置した検索テーブル２２０を備え、検索テーブル２２０に対して第１の検索キー１１０の値から指定される検索テーブル２２０の内容のうち、実際のデータ処理（処理４）を指定する識別子５１０と第２の検索キー４１０の組合せが検索される（すなわち、検索テーブル２２０の第１の検索キー１１０（”０１０”）に対応する内容のうち識別子５１０（”１”）に対応する第２の検索キー４１０（”００１１”）が検索される）。次に、第２の検索キー４１０の値で指定される検索テーブル２２０の内容のうち実際にデータ処理される内容（第２の検索キー４１０（”００１１”）に対応する処理４）が検索される。
【００２８】
図３は、本発明の検索処理を説明する図である。矢印無しの実線は第１の検索経路、太矢印付の実線は第２の検索経路、実線の矢線は処理の割り当てを示している。例えば第１の検索範囲の３ビット（”０１０”）による第１の検索経路の末端ノードから、識別子（”１”）を第２の検索経路として、処理４の割付が行われる様子が図示されている。なお、第１の検索範囲の３ビット（”０１０”）による第１の検索経路の末端ノードから識別子（”０”）の場合も、同一の第２の検索経路にて、処理４の割付が行われる（第２の検索経路には１と０が付加されている）。
【００２９】
検索対象となるデータの任意のビット列をそのまま検索キーとして処理を決定する従来手法では、選択した任意のビット列に対して２の（ビット列幅）乗の検索テーブルの空間が必要になり、検索ビット列幅に対して、指数関数的に検索テーブル空間が必要になる（図５参照）。すなわち、検索対象データの出現パタンに対して１対１に、前記検索対象データへの処理が決定される場合、２の（ビット列幅）乗の検索テーブルの空間が必要となるが、複数の検索対象データの出現パタンに対して同一の処理を割り当てる場合、２の（ビット列幅）乗の検索テーブルの空間は必要でない。
【００３０】
本発明によれば、複数の検索対象データの出現パタンに対して同一の処理を割り当てる場合に、２の（ビット列幅）乗の検索テーブルの空間を必要としない。また、検索に必要な検索キー、識別子等を従来からある検索テーブル空間に配置することで、実際に処理決定に必要な検索テーブルの実体（メモリ等）自体を変更することなく、効率的に使用することが可能になる。
【００３１】
以上、本発明を上記実施例に即して説明したが、本発明は上記実施例の構成にのみ制限されるものでなく、本発明の範囲内で当業者であればなし得るであろう各種変形、修正を含むことは勿論である。
【図面の簡単な説明】
【００３２】
【図１】本発明の一実施の形態を説明する図である。
【図２】本発明の別の実施の形態を説明する図である。
【図３】本発明の実施の形態における検索結果に基づき処理の割り当て例を模式的に示す図である。
【図４】従来のアドレス検索テーブルの一例を示す図である。
【図５】検索ツリーの一例を示す図である。
【符号の説明】
【００３３】
１００  検索キー
１１０  第１の検索キー
２００  検索テーブル
２１０、２２０  検索テーブル
３００、３１０  検索データ
３１０  検索データ
４１０  第２の検索キー
５１０  識別子
６１０  検索テーブル
【図１】
2008244642.tif 000003
【図２】
2008244642.tif 000004
【図３】
2008244642.tif 000005
【図４】
2008244642.tif 000006
【図５】
2008244642.tif 000007