(57)【要約】【課題】小容量のメモリで検索処理の実行が可能な検索回路を提供する。【解決手段】ある局面に従う複数のエントリデータが格納される検索テーブルに対して入力された検索キーが一致するか否かを検索する検索回路であって、検索テーブルに対してバイナリサーチを実行する検索処理部を含む。エントリデータは、検索データと、検索データのプレフィックス長データと、検索結果情報とを含む。検索処理部は、バイナリサーチに従って検索テーブルから複数回読み出したエントリデータに含まれる検索データとプレフィックス長データとで規定される検索データ群の１つの検索データと検索キーとが一致するか否かをそれぞれ判断し、複数回の判断結果に基づいて、プレフィックス長データが最大の一致する検索データに対応する検索結果情報を出力する。【選択図】図４
2020201656.tif 000002
【特許請求の範囲】
【請求項１】
複数のエントリデータが格納される検索テーブルに対して入力された検索キーが一致するか否かを検索する検索回路であって、
前記検索テーブルに対してバイナリサーチを実行する検索処理部を含み、
前記エントリデータは、検索データと、前記検索データのプレフィックス長データと、検索結果情報とを含み、
前記検索処理部は、
前記バイナリサーチに従って前記検索テーブルから複数回読み出したエントリデータに含まれる検索データと前記プレフィックス長データとで規定される検索データ群の１つの検索データと前記検索キーとが一致するか否かをそれぞれ判断し、
前記複数回の判断結果に基づいて、前記プレフィックス長データが最大の一致する検索データに対応する検索結果情報を出力する、検索回路。
【請求項２】
前記検索回路は、前記バイナリサーチに従って前記検索テーブルから複数回読み出したエントリデータに含まれる検索データと前記プレフィックス長データとで規定される検索データ群の１つの検索データと前記検索キーとが一致するか否かを判断した結果をそれぞれ格納するための結果格納部をさらに含む、請求項１記載の検索回路。
【請求項３】
複数の検索テーブルが設けられ、
前記検索処理部は、前記複数の検索テーブルに対してバイナリサーチをそれぞれ実行する、請求項１記載の検索回路。
【請求項４】
前記検索処理部は、前記複数の検索テーブルに対して順番に、あるいは並列にバイナリサーチをそれぞれ実行する請求項３記載の検索回路。
【請求項５】
前記検索回路は、前記複数のエントリデータを生成して前記検索テーブルに格納するためのテーブル生成部をさらに含む、請求項１記載の検索回路。
【請求項６】
前記テーブル生成部は、
マスクされるビットを含む検索対象データと、前記検索対象データのプレフィックス長データおよび検索結果情報を含むエントリ候補データを取得するデータ取得部と、
前記データ取得部で取得した前記検索対象データが示す前記検索データ群のうちの１つのデータを前記検索データとして設定する検索データ設定部と、
前記検索データと、前記プレフィックス長データおよび検索結果情報を関連付けて前記エントリデータとして設定するエントリデータ設定部とを含む、請求項５記載の検索回路。
【請求項７】
前記検索データ設定部は、前記データ取得部で取得した前記検索対象データが示す前記検索データ群のうちの下限値のデータを前記検索データとして設定する、請求項６記載の検索回路。
【請求項８】
前記テーブル生成部は、
前記検索対象データが示す前記検索データ群に他の検索データが含まれるか否かを判断し、前記他の検索データが含まれる場合には、別のエントリデータを設定するエントリデータ追加設定部をさらに含む、請求項６記載の検索回路。
【請求項９】
前記エントリデータ追加設定部は、
前記検索対象データが示す前記検索データ群に前記他の検索データが少なくとも１つ以上含まれる場合には、前記他の検索データとの境界値を示すデータを前記検索データとして、前記プレフィックス長データおよび検索結果情報と関連付けて前記別のエントリデータとして設定する、請求項８記載の検索回路。
【請求項１０】
前記エントリデータ設定部は、
前記検索対象データが示す前記検索データ群に他の検索データが含まれるか否かを判断し、前記他の検索データが含まれる場合には、前記検索データと、前記プレフィックス長データおよび検索結果情報とを関連付けて別の検索テーブルの前記エントリデータとして設定する、請求項６記載の検索回路。
【請求項１１】
前記検索データ設定部は、前記データ取得部で取得した前記検索対象データが示す前記検索データ群のうち、前記プレフィックス長データが小さい場合には、前記プレフィックス長データが大きい検索データよりも先に前記検索テーブルから読み出されるデータを前記検索データとして設定する、請求項６記載の検索回路。
【請求項１２】
前記検索データ設定部は、前記バイナリサーチにより前記検索テーブルが格納するエントリデータを指定するアドレスの範囲の中でプレフィックス長データが大きい検索データが格納されるアドレスの範囲に基づいて、プレフィックス長データが小さい検索データが格納されるアドレスを設定する、請求項１１記載の検索回路。
【発明の詳細な説明】
【技術分野】
【０００１】
この開示は、複数のエントリデータが格納される検索テーブルに対して入力された検索キーが一致するか否かを検索する検索回路に関する。
【背景技術】
【０００２】
ＩＰネットワークにおいて、ルーターなどのネットワーク機器は受信したパケットの転送先を決定するため機器内にＦＩＢ(Forwarding Information Base)という宛先ＩＰアドレスと対応するパケットデータの転送先ポートを格納したデータベースを生成している。
【０００３】
ルーターは、パケットを受信するとパケットデータのヘッダー情報に付加されている宛先ＩＰアドレスを検索キーとしてＦＩＢを検索し、その検索結果でパケットの転送先を決定する。
【０００４】
ＦＩＢに格納されているＩＰアドレスは各々Ｐｒｅｆｉｘ長と呼ばれる検索有効ビット長が定義されている。
【０００５】
ＦＩＢの検索では検索キーとなる宛先ＩＰアドレスに一致するテーブルエントリのうち最も有効ビット長が長いエントリを検索結果として出力する。
【０００６】
このような検索方法をＬＰＭ（Longest-Prefix-Match）検索と呼ぶ。ＬＰＭ検索を実施する場合に、ＣＡＭ（内容参照メモリ：Content Addressable Memory）を利用する手法がある。
【０００７】
ＣＡＭを利用した場合、高い検索性能を実現できる反面、ＤＲＡＭやＳＲＡＭなどの汎用メモリと比較すると高価であり、消費電力が大きいという課題がある。
【０００８】
近年ＩＰネットワークの拡大とともにＩＰアドレスの数も増加し、それに比例して対応するＦＩＢ容量も拡大し続けている。そのため高価で消費電力の大きいＣＡＭに大容量のＦＩＢデータベースを格納して検索するのは困難になってきている。
【先行技術文献】
【非特許文献】
【０００９】
【非特許文献１】IP Lookups using Multiway and Multicolumn Search
【発明の概要】
【発明が解決しようとする課題】
【００１０】
一方で、ツリービットマップ（Ｔｒｅｅ−Ｂｉｔ−Ｍａｐ）アルゴリズムなど様々な検索アルゴリズムに基づく検索方法にもとづいて、比較的安価で消費電力の小さいＤＲＡＭやＳＲＡＭなどを使用してＬＰＭ検索を実行する方法が提案されている（非特許文献１）。
【００１１】
しかし、近年ＩＰｖ４アドレスの枯渇問題に起因して、より長いビット長をもつＩＰｖ６アドレスへの移行が始まっているが、検索性能が検索キー長に比例して低下する特徴があるツリービットマップ検索アルゴリズムを使用した方法では検索キー長がＩＰｖ４の３２ビットから１２８ビットとなるＩＰｖ６では性能が低下する問題が発生する。
【００１２】
また、ＬＰＭ検索の検索アルゴリズムとしてツリービットマップアルゴリズム以外にバイナリサーチ（Binary-Search）検索アルゴリズムを使用する方法も提案されている（非特許文献１）。
【００１３】
バイナリサーチ検索アルゴリズムでは検索性能は検索キー長ではなく検索データベースの容量に依存する。
【００１４】
ＩＰｖ６アドレス検索時でもＩＰｖ４アドレス検索時と同等の性能を実現可能だが、一方で検索性能が容量に比例するため、より小容量のメモリでＬＰＭ検索を実現できれば検索性能が向上する。
【００１５】
本開示は、上記の課題を解決するためになされたものであって、小容量のメモリで検索処理の実行が可能な検索回路を提供する。
【００１６】
その他の課題と新規な特徴は、本明細書の記述および添付図面から明らかになるであろう。
【課題を解決するための手段】
【００１７】
ある局面に従う複数のエントリデータが格納される検索テーブルに対して入力された検索キーが一致するか否かを検索する検索回路であって、検索テーブルに対してバイナリサーチを実行する検索処理部を含む。エントリデータは、検索データと、検索データのプレフィックス長データと、検索結果情報とを含む。検索処理部は、バイナリサーチに従って検索テーブルから複数回読み出したエントリデータに含まれる検索データとプレフィックス長データとで規定される検索データ群の１つの検索データと検索キーとが一致するか否かをそれぞれ判断し、複数回の判断結果に基づいて、プレフィックス長データが最大の一致する検索データに対応する検索結果情報を出力する。
【発明の効果】
【００１８】
一実施例によれば、本開示の検索メモリは、小容量のメモリで検索処理の実行が可能である。
【図面の簡単な説明】
【００１９】
【図１】実施形態１に基づく通信機器１の構成を説明する図である。
【図２】比較例として設けられる検索テーブルについて説明する図である。
【図３】比較例として検索テーブル２０１に対する検索処理について説明する図である。
【図４】実施形態１に従う検索回路１０の機能ブロック図である。
【図５】実施形態１に従う検索テーブルの生成について説明する図である。
【図６】実施形態１に従う検索テーブル４０３に対する検索処理について説明する図である。
【図７】実施形態２に従う検索テーブルの生成について説明する図である。
【図８】実施形態２に従う検索テーブルの実装方式について説明する図である。
【図９】実施形態２に従う検索処理の順序について説明するフロー図である。
【図１０】実施形態１に従う別の検索テーブルの生成について説明する図である。
【図１１】実施形態３に従う検索テーブルの生成について説明する図である。
【図１２】実施形態３に従う検索テーブル４０８に対する検索処理について説明する図である。
【発明を実施するための形態】
【００２０】
実施形態について図面を参照しながら詳細に説明する。なお、図中同一または相当部分には同一符号を付し、その説明は繰り返さない。
【００２１】
（実施形態１）
＜通信機器１の全体構成＞
図１は、実施形態１に基づく通信機器１の構成を説明する図である。
【００２２】
図１に示されるように、通信機器１は、スイッチあるいはルータ等の通信装置である。
通信機器１は、インターネットと接続される。パケットデータの転送処理を実行する。
【００２３】
通信機器１は、複数のポート（Ｐｏｒｔ−０〜Ｐｏｒｔ−３）と、スイッチ２と、検索回路１０とを含む。
【００２４】
スイッチ２は、ポートの接続先を切り替える。
本例においては、通信機器１は、パケットデータを受信して、検索回路１０の検索処理により指定されたポートに対して受信したパケットデータを転送する転送処理を実行する場合が示されている。
【００２５】
ここで、検索回路１０は、検索テーブル３０を含み、その検索方法は、ＬＰＭ（Longest-Prefix-Match）検索である。
【００２６】
検索テーブル３０は、複数のエントリデータを格納する。一例として、宛先ＩＰアドレス「３２．４８.０９．００/２４」が転送先ポート（Ｐｏｒｔ−０）と関連付けられて格納されている。また、「３２．４８.１０．００/２３」が転送先ポート（Ｐｏｒｔ−１）と関連付けられて格納されている。「３２．４８.０８．００/２１」が転送先ポート（Ｐｏｒｔ−２）と関連付けられて格納されている。「３２．４８.００．００/１６」が転送先ポート（Ｐｏｒｔ−３）と関連付けられて格納されている。
【００２７】
ここで、検索キーとして、検索ＩＰアドレス「３２．４８.０９．０３」を受信した場合が示されている。
【００２８】
受信した検索キーは、検索テーブル３０に格納されている４つのエントリデータとそれぞれ一致する。
【００２９】
検索回路１０は、検索キーとなる検索ＩＰアドレスに一致するエントリデータのうち最も有効ビット長が長いエントリデータを検索結果として出力する。
【００３０】
本例においては、検索ＩＰアドレスに一致するエントリデータのうち最も有効ビット長が長い２４ビットのプレフィックス（Prefix）長をもつ「３２．４８.０９．００/２４」が検索結果として出力される。
【００３１】
したがって、対応する転送先であるポート（Ｐｏｒｔ−０）へパケットデータを転送して宛先までデータを送付する。
【００３２】
＜比較例に従うバイナリサーチ（Binary-Search）検索アルゴリズム＞
比較例として、従来のバイナリサーチ検索アルゴリズムでＬＰＭ検索を実施する場合について説明する。
【００３３】
上記比較例は、非特許文献１に示される方式である。
図２は、比較例として設けられる検索テーブルについて説明する図である。
【００３４】
図２（Ａ）を参照して、検索テーブル２００は、複数のエントリデータを格納する。
一例として４つのエントリデータを格納する場合が示されている。
【００３５】
エントリデータは、４ビットのデータ長の検索データと、各検索データが検索キーと一致した場合に検索結果として出力する検索結果データとを含む。
【００３６】
検索テーブル２００が、ＦＩＢであれば検索データが宛先ＩＰアドレスに相当し、検索結果が転送先ポートに相当する。
【００３７】
検索テーブル２００のエントリデータは、マスクされるビットを含んでいるため、各々のエントリデータはマスクされたビットに対応する複数の検索キーに一致する。
【００３８】
たとえば、検索テーブル２００に格納されている各エントリデータは各々下記の下限値と上限値を境界値とする検索対象範囲をもっている。
【００３９】
【表１】
2020201656.tif 000003
【００４０】
比較例では、バイナリサーチで、ＬＰＭ検索を実施する。
図２（Ｂ）には、非特許文献１に開示されるバイナリサーチでＬＰＭ検索を実施するための検索テーブル２０１が示されている。
【００４１】
検索テーブル２００の各エントリデータが持つ下限値と上限値とを各々バイナリサーチ（Binary-Search）のデータとして小さい順にソートした検索テーブル２０１を生成する。
【００４２】
したがって、検索テーブル２０１は、検索テーブル２００の倍の８個のエントリデータが格納される。
【００４３】
そして、検索テーブル２０１は、検索結果として検索キーに応じた２つの場合のデータをそれぞれ格納する。
【００４４】
検索結果は、検索キーが格納された検索データと一致した場合（Ｋｅｙ＝Ｄａｔａ）の検索結果データと、検索キーが格納した検索データより大きい場合（Ｋｅｙ＞Ｄａｔａ)の検索結果データとを含む。
【００４５】
図３は、比較例として検索テーブル２０１に対する検索処理について説明する図である。
【００４６】
図３（Ａ）には、検索テーブル２０１が示されており、検索キー「００１０」と、「０１１０」に対する検索処理を実行する場合が示されている。
【００４７】
検索キー「００１０」の場合について説明する。
検索テーブル２０１に対して検索キー「００１０」でもってバイナリサーチ（Ｂｉｎａｒｙ−Ｓｅａｒｃｈ）した場合、テーブルアドレス「１」で検索キーと検索データが一致する（Ｋｅｙ＝Ｄａｔａ）ので検索結果データ「Ｐ０」を出力する。
【００４８】
図３（Ｂ）には、検索過程が示されており、「判定」は検索キー（Ｋｅｙ）が検索データ（Ｄａｔａ）に対して小さい（Ｌｏｗ）か、大きい（Ｈｉｇｈ）かを示す判定結果である。
【００４９】
バイナリサーチは、検索テーブル２０１の中間のテーブルアドレス「４」からスタートする。検索キーが検索データよりも小さい（Ｌｏｗ）と判定した場合は、次のバイナリサーチは図３（Ｂ）に示したような順で下位アドレスを読み出し（Ｒｅａｄ）し、大きい（Ｈｉｇｈ）と判定した場合は上位アドレスを読み出す。
【００５０】
検索キー「０１１０」の場合についても同様に検索を行う。
しかしながら、検索テーブル２０１を検索キー「０１１０」でバイナリサーチした場合、検索キー「０１１０」に一致するテーブルエントリの検索データは存在しない。
【００５１】
このとき、検索結果は、テーブルアドレス「４」と「５」の中間値となる。つまり、エントリデータ「０１０＊」（Ｅｎｔｒｙ１）の上限値とエントリデータ「０＊＊＊」（Ｅｎｔｒｙ３）の上限値の中間値（０１１０）を指し示す。検索過程としては、検索キーは、エントリデータ（Ｅｎｔｒｙ１）の上限値であるテーブルアドレス「４」の検索データより大きい（Ｋｅｙ（０１１０）＞Ｄａｔａ（０１０１））。また、エントリデータ（Ｅｎｔｒｙ３）の上限値であるテーブルアドレス「５」の検索データより小さい（Ｋｅｙ（０１１０）＜Ｄａｔａ（０１１１））。したがって、検索結果はテーブルアドレス「４」と「５」の検索データの中間値となる。
【００５２】
当該比較例では、検索テーブル２０１に、バイナリサーチの検索結果が各検索データの中間値になった場合の検索結果データ２０１−２を設けている。例えば、テーブルアドレス「４」の検索データは図２に示される検索テーブル２００のＥｎｔｒｙ１の上限値（Ｈ１）であり、且つ、検索テーブル２００のＥｎｔｒｙ３の検索対象範囲（Ｌ３〜Ｈ３）に含まれている。したがって、検索キーがＥｎｔｒｙ１の上限値（テーブルアドレス「４」の検索データ（Ｈ１））より大きく、Ｅｎｔｒｙ３の上限値（テーブルアドレス「５」の検索データ（Ｈ３））までの範囲にある場合は、Ｅｎｔｒｙ３にＨｉｔすることになる。そこで検索テーブル２０１は、検索結果データ２０１−２を有し、テーブルアドレス「４」より大きい場合の検索結果としてＥｎｔｒｙ３の検索結果データである「Ｐ３」を格納する。
【００５３】
上述のとおり、検索キー「０１１０」のバイナリサーチにおける検索結果は、テーブルアドレス「４」と「５」の中間値となるため、テーブルアドレス「４」と、テーブルアドレス「４」に隣接するテーブルアドレス「５」とを検索対象範囲とする検索結果としてテーブルアドレス「４」の（Ｋｅｙ＞Ｄａｔａ）の検索結果データ（２０１−２）である「Ｐ３」が判定結果として出力される。
【００５４】
なお、通常のバイナリサーチであれば、検索キーが検索テーブル２０１に格納される検索データと一致しない場合には、検索不一致（Ｍｉｓｓと呼ぶ）となる。
【００５５】
当該方式による検索テーブルの容量について説明する。
検索時に使用されるバイナリサーチを実行するための検索テーブル２０１は、元の検索テーブル２００のエントリデータ１個あたり下限値と上限値との２個の検索データを格納する。
【００５６】
したがって、Ｎ個のエントリデータの検索テーブル２００から検索テーブル２０１を生成するとワーストケースで２Ｎ個のテーブルアドレスが必要となる。
【００５７】
したがって、比較例に従う方式では、Ｎエントリデータの検索テーブルをＬＰＭ検索する場合には２Ｎのメモリ空間を持ったメモリを用意する必要がある。
【００５８】
さらに、検索テーブル２０１の各メモリアドレスには検索結果として出力するデータとして２個のデータを格納する。検索キーが検索データと一致した場合（Ｋｅｙ＝Ｄａｔａ）の検索結果データと、検索キーが検索データより大きい場合（Ｋｅｙ＞Ｄａｔａ)の検索結果データとを格納する。
【００５９】
例えば、検索テーブル２００が１Ｍのエントリデータを持っていた場合、検索結果データとしてＣＡＭと同様にエントリアドレスを出力する場合には、検索結果データには２０ビットが必要となる。したがって、上記方式を採用する場合には、検索結果データとして４０ビットが必要になる。
【００６０】
例えば、検索テーブル２００がＩＰｖ４アドレスをベースとする検索テーブルであり、１Ｍのエントリデータを有する場合に、検索テーブル２００から検索テーブル２０１を生成する場合には、下記のメモリ容量が必要となる。
【００６１】
【表２】
2020201656.tif 000004
【００６２】
表２のようにＬＰＭ検索に使用する検索テーブル２０１は元の検索テーブル２００より２倍以上のメモリ容量を必要とする。
【００６３】
また、メモリアドレス空間もＮから２Ｎに増加するためバイナリサーチを実行したときのメモリアクセス回数も元の検索テーブル２００のエントリ数Ｎの回数と比較すると、メモリアドレス空間が２倍に増加した結果、メモリアクセス回数が１回増える結果となり、高速化できない課題がある。
【００６４】
さらに、検索テーブルを更新する場合には、エントリデータを大小順でソートする必要がある。例えば、Ｎ個のデータをもつ検索テーブルに対して、テーブルの最小位置に新規のエントリデータが追加される場合には、最小アドレス位置に新規のエントリデータを挿入する必要があるため既存のエントリデータをすべて移動させる必要がある。
【００６５】
検索テーブル２０１を構築する場合に、ワーストケースで発生するデータの移動回数はエントリ数に依存し、メモリアドレス空間がＮから２Ｎに増加した場合、検索テーブルを構築する時間も増大する。
【００６６】
したがって、検索テーブルのエントリデータ数の削減が望まされる。
図４は、実施形態１に従う検索回路１０の機能ブロック図である。
【００６７】
図４を参照して、検索回路１０は、処理部２０と、検索テーブル３０とを含む。処理部２０の機能として、本例においてはＣＰＵがアクセス可能なメモリに格納されたプログラムを実行することにより各機能ブロックを実現する。
【００６８】
処理部２０は、検索テーブル３０に対する種々の処理を実行するものであり、検索処理部２２と、結果格納部２４と、テーブル生成部２６とを含む。
【００６９】
検索処理部２２は、検索テーブル３０に対してバイナリサーチ処理を実行する。また、
検索処理部２２は、バイナリサーチ処理に対する結果を結果格納部２４に格納する。
【００７０】
テーブル生成部２６は、元検索テーブルから検索処理部２２のバイナリサーチ処理で使用する検索テーブル３０のエントリデータを生成する。元の検索テーブルは、ユーザが設定してもよいし、検索実行システムがプログラムに基づいて生成されるものであってもよい。
【００７１】
テーブル生成部２６は、データ取得部２６０と、検索データ設定部２６２と、エントリデータ設定部２６４と、エントリデータ追加設定部２６６とを含む。
【００７２】
データ取得部２６０は、元検索テーブルに含まれるエントリ候補データを取得する。
検索データ設定部２６２は、データ取得部２６０で取得したエントリ候補データが検索対象範囲となるデータの中から１つのデータを検索データとして設定する。
【００７３】
エントリデータ設定部２６４は、検索データと、プレフィックス長データとを関連付けて検索テーブル３０のエントリデータとして設定する。
【００７４】
エントリデータ追加設定部２６６は、検索対象データが示す検索データ群に他の検索データが含まれるか否かを判断し、他の検索データが含まれる場合には、別のエントリデータを設定する。
【００７５】
＜検索テーブルの生成について＞
実施形態１に従う検索テーブルに格納するエントリデータは、検索データとプレフィックス（prefix）長データと検索結果情報とを含む。
【００７６】
検索テーブルの各エントリデータが有する検索データとプレフィックス長データとに基づいて、各エントリデータの対象とする検索データ群（検索対象範囲）を計算することが可能である。すなわち、検索データ群の検索データの上限値および下限値を算出することが可能である。例えば、検索データが「０１００」でプレフィックス長が「３」の場合には、元の検索データが「０１０＊」であることが分かる。したがって、検索データの検索対象範囲は上限値が「０１０１」であり下限値が「０１００」であることが分かる。
【００７７】
本例においては、エントリデータに格納する検索データとして、例えば、検索データ群のうちの下限値を設定する場合について説明する。なお、下限値に限られず検索データ群の上限値および下限値の間の任意の値に設定することが可能である。
【００７８】
テーブル生成部２６は、エントリ候補データで構成される元検索テーブルから検索テーブル３０を生成する。
【００７９】
図５は、実施形態１に従う検索テーブルの生成について説明する図である。
図５（Ａ）には、元検索テーブル４００が示されている。
【００８０】
元検索テーブル４００は、エントリアドレス０〜３のそれぞれに検索対象となる複数のエントリ候補データＥｎｔｒｙ０〜３を格納する。本例においては、４つのエントリ候補データが元検索テーブル４００に格納されている。
【００８１】
エントリ候補データは、マスクされるビットを含む検索対象データと、検索対象データが検索キーと一致した場合に検索結果として出力する検索結果データとを含む。
【００８２】
図５（Ｂ）には、実施形態１に従う元検索テーブル４００の検索対象範囲が示されている。
【００８３】
図５（Ｂ）に示されるように、各エントリ候補データの検索対象範囲が示されている。
具体的には、エントリ候補データＥｎｔｒｙ０の検索データ「００１＊」の検索対像範囲と、エントリ候補データＥｎｔｒｙ１の検索データ「０１０＊」の検索対象範囲と、エントリ候補データＥｎｔｒｙ２の検索データ「１１１＊」の検索対象範囲と、エントリ候補データＥｎｔｒｙ３の検索データ「１０＊＊」の検索対象範囲が示されている。
【００８４】
この場合、各エントリ候補データの検索対象範囲は重ならない。すなわち、各エントリ候補データの検索対象範囲は、他のエントリ候補データの検索対象範囲によって分割されない。
【００８５】
図５（Ｃ）は、実施形態１に従う検索テーブル４０１を説明する図である。
検索データ設定部２６２は、元検索テーブル４００の各エントリ候補データの検索対象データの検索対象範囲の下限値を検索テーブル４０１の検索データとする。そして、エントリデータ設定部２６４は、当該検索データと、プレフィックス長データおよび検索結果データとを関連付けたエントリデータを設定する。
【００８６】
そして、エントリデータ設定部２６４は、検索テーブル４０１にそれぞれ検索データ設定部２６２で設定されたエントリデータを格納する。
【００８７】
エントリデータ設定部２６４は、格納したエントリデータのソートを行い、テーブルアドレスが小さい位置に値の小さい検索データを含むエントリデータを格納する。
【００８８】
一例として、テーブルアドレス「０」にエントリ候補データＥｎｔｒｙ０に対応する検索データ「００１０」、プレフィックス長データ「３」、検索結果データ「Ｐ０」が格納される。
【００８９】
一例として、テーブルアドレス「１」にエントリ候補データＥｎｔｒｙ１に対応する検索データ「０１００」、プレフィックス長データ「３」、検索結果データ「Ｐ１」が格納される。
【００９０】
一例として、テーブルアドレス「２」にエントリ候補データＥｎｔｒｙ３に対応する検索データ「１０００」、プレフィックス長データ「２」、検索結果データ「Ｐ３」が格納される。
【００９１】
一例として、テーブルアドレス「３」にエントリ候補データＥｎｔｒｙ２に対応する検索データ「１１１０」、プレフィックス長データ「３」、検索結果データ「Ｐ２」が格納される。
【００９２】
本例においては、各エントリ候補データの検索対象範囲は、他のエントリ候補データの検索対象範囲によって分割されないため新たなエントリデータを追加しない。
【００９３】
次に、エントリ候補データの検索対象範囲が他のエントリ候補データの検索対象範囲によって分割される場合について説明する。
【００９４】
図５（Ｄ）には、元検索テーブル４０２が示されている。
元検索テーブル４０２は、エントリアドレス０〜３のそれぞれに検索対象となる複数のエントリ候補データＥｎｔｒｙ０〜３を格納する。本例においては、４つのエントリ候補データが元検索テーブル４０２に格納されている。
【００９５】
エントリ候補データは、マスクされるビットを含む検索対象データと、検索対象データが検索キーと一致した場合に検索結果として出力する検索結果データとを含む。
【００９６】
図５（Ｅ）には、実施形態１に従う元検索テーブル４０２の検索対象範囲が示されている。
【００９７】
図５（Ｅ）に示されるように、各エントリ候補データの検索対象範囲が示されている。
具体的には、エントリ候補データＥｎｔｒｙ０の検索データ「００１＊」の検索対象範囲と、エントリ候補データＥｎｔｒｙ１の検索データ「０１０＊」の検索対象範囲と、エントリ候補データＥｎｔｒｙ２の検索データ「１０１＊」の検索対象範囲と、エントリ候補データＥｎｔｒｙ３の検索データ「０＊＊＊」の検索対象範囲が示されている。
【００９８】
この場合、エントリ候補データＥｎｔｒｙ３の検索データ「０＊＊＊」の検索対象範囲は、エントリ候補データＥｎｔｒｙ０の検索データ「００１＊」の検索対象範囲と、エントリ候補データＥｎｔｒｙ１の検索データ「０１０＊」の検索対象範囲と重なる場合が示されている。
【００９９】
すなわち、エントリ候補データＥｎｔｒｙ３の検索データ「０＊＊＊」の検索対象範囲は、エントリ候補データＥｎｔｒｙ０の検索データ「００１＊」およびエントリ候補データＥｎｔｒｙ１の検索データ「０１０＊」により分割される。
【０１００】
実施形態１においては、上記のようにエントリ候補データＥｎｔｒｙ３が分割されるためＥｎｔｒｙ３の下限値を検索データ「００００」とするエントリ候補データＥｎｔｒｙ３−０とは別の検索データを含む新たなエントリ候補データＥｎｔｒｙ３−１を追加する。
【０１０１】
エントリデータ追加設定部２６６は、新たなエントリ候補データを追加する。
エントリデータ追加設定部２６６は、エントリ候補データＥｎｔｒｙ３の検索データ「０＊＊＊」の検索対象範囲のうち、エントリ候補データＥｎｔｒｙ０の検索データ「００１＊」およびエントリ候補データＥｎｔｒｙ１の検索データ「０１０＊」の検索対象範囲を除く検索対象範囲のエントリデータＥｎｔｒｙ３−１を追加する。
【０１０２】
この点で、エントリデータ追加設定部２６６は、エントリ候補データＥｎｔｒｙ１の検索対象範囲との境界を示すデータ「０１１０」を検索データとする。
【０１０３】
そして、エントリデータ追加設定部２６６は、当該検索データとプレフィックス長データおよび検索結果データとを関連付けた新たなエントリデータを設定する。
【０１０４】
エントリデータ追加設定部２６６は、検索データ「０１１０」と、プレフィックス長データ「１」および検索結果「Ｐ３」とを関連付けた新たなエントリデータを設定する。
【０１０５】
図５（Ｆ）は、実施形態１に従う検索テーブル４０３を説明する図である。
検索データ設定部２６２は、元検索テーブル４０２の各エントリ候補データの検索対象データの検索対象範囲の下限値を検索テーブル４０３の検索データとする。そして、エントリデータ設定部２６４は、当該検索データと、プレフィックス長データおよび検索結果データとを関連付けたエントリデータを設定する。
【０１０６】
そして、エントリデータ設定部２６４は、検索テーブル４０３にそれぞれ設定したエントリデータを格納する。また、エントリデータ追加設定部２６６は、新たなエントリデータを検索テーブル４０３に格納する。
【０１０７】
エントリデータ設定部２６４は、格納すべきエントリデータのソートを行い、テーブルアドレスが小さい位置に値の小さい検索データを含むエントリデータを格納する。
【０１０８】
実施形態１に従う検索テーブル４０３には、図５（Ｆ）に示されるように、エントリデータを追加した上で、ソートが行われたエントリデータが格納される。
【０１０９】
一例として、テーブルアドレス「０」にエントリ候補データＥｎｔｒｙ３−０に対応する検索データ「００００」、プレフィックス長データ「１」、検索結果データ「Ｐ３」が格納される。
【０１１０】
一例として、テーブルアドレス「１」にエントリ候補データＥｎｔｒｙ０に対応する検索データ「００１０」、プレフィックス長データ「３」、検索結果データ「Ｐ０」が格納される。
【０１１１】
一例として、テーブルアドレス「２」にエントリ候補データＥｎｔｒｙ１に対応する検索データ「０１００」、プレフィックス長データ「３」、検索結果データ「Ｐ１」が格納される。
【０１１２】
一例として、テーブルアドレス「３」にエントリ候補データＥｎｔｒｙ３−１に対応する検索データ「０１１０」、プレフィックス長データ「１」、検索結果データ「Ｐ３」が格納される。
【０１１３】
一例として、テーブルアドレス「４」にエントリ候補データＥｎｔｒｙ２に対応する検索データ「１０１０」、プレフィックス長データ「３」、検索結果データ「Ｐ２」が格納される。
【０１１４】
当該検索テーブルを用いて検索処理部２２によるバイナリサーチが可能となる。
＜実施形態に従うバイナリサーチ（Binary-Search）検索アルゴリズム＞
図６は、実施形態１に従う検索テーブル４０３に対する検索処理について説明する図である。
【０１１５】
検索処理部２２は、検索テーブル４０３にアクセスし、検索処理を実行する。検索処理部２２は、検索過程の情報を結果格納部２４に格納する。
【０１１６】
図６（Ａ）には、検索テーブル４０３が示されている。
ここで、検索処理部２２は、検索キー「００１０」と、検索キー「０１１０」とに対する検索処理を実行する。
【０１１７】
図６（Ｂ）には、結果格納部２４に格納されている検索キー「００１０」に対する検索過程の情報が示されている。
【０１１８】
検索処理部２２は、検索テーブル４０３の中間のテーブルアドレス「２」からサーチを開始する。
【０１１９】
検索処理部２２は、検索テーブル４０３の中間のテーブルアドレス「２」から読み出されたエントリデータの検索データおよびプレフィックス長データに基づいて、当該エントリデータの検索対象範囲の上限値を計算する。一例として上限値「０１０１」が算出される。検索データは、検索対象範囲の下限値が設定されているため検索対象範囲は、「０１００」〜「０１０１」であることが分かる。
【０１２０】
検索処理部２２は、決定した検索対象範囲に基づいて検索キーが含まれるか否かの一致判定処理を実行する。
【０１２１】
本例の場合には、検索処理部２２は、検索キー「００１０」がエントリデータの検索対象範囲に入っていないと判断する。すなわち、検索結果はミス（Miss）となる。
【０１２２】
また、検索処理部２２は、検索データ「０１００」と検索キー「００１０」との大小判定処理を実行する。この比較結果に基づいて次の検索アドレスを決定する。
【０１２３】
検索処理部２２は、大小判定処理により、検索キーが検索データよりも小さい（Ｌｏｗ）場合には、次の検索対象として下位アドレスに対応するエントリデータを読み出す。
【０１２４】
検索処理部２２は、大小判定処理により、検索キーが検索データよりも大きい（Ｈｉｇｈ）場合には次の検索対象として上位アドレスに対応するエントリデータを読み出す。
【０１２５】
このエントリデータでは検索キー「００１０」＜検索データ「０１００」である。したがって、大小判定処理により小さい（Ｌｏｗ）となるので下位アドレスであるテーブルアドレス「０」のデータを読み出す。
【０１２６】
図６（Ｂ）の結果格納部２４には、１回目のメモリアクセスとして、テーブルアドレス「２」を検索アドレスとした場合が示されている。検索データ「０１００」に対して上限値「０１０１」が算出された場合が示されている。また、大小判定処理として小さい（Low）が判定結果として格納されている。また、一致判定処理としてミス（Miss）が格納されている。
【０１２７】
次に、検索処理部２２は、検索テーブル４０３の下位のテーブルアドレス「０」を読み出し、検索キー「００１０」でサーチを実行する。
【０１２８】
検索処理部２２は、上記と同様に読み出されたエントリデータの検索データおよびプレフィックス長データとに基づいて、当該エントリデータの検索対象範囲の上限値を計算する。すなわち、テーブルアドレス「０」のエントリデータの検索対象範囲の上限値「０１１１」が算出される。したがって、当該エントリデータの検索対象範囲は「００００」〜「０１１１」であることが分かる。
【０１２９】
検索処理部２２は、決定した検索対象範囲に基づいて検索キーが含まれるか否かの一致判定処理を実行する。
【０１３０】
本例の場合には、検索処理部２２は、検索キー「００１０」がエントリデータの検索対象範囲に入っていると判断する。すなわち、検索結果は一致（Ｈｉｔ）となる。
【０１３１】
また、検索処理部２２は、検索データ「００００」と検索キー「００１０」との大小判定処理を実行する。この比較結果に基づいて次の検索アドレスを決定する。
【０１３２】
このエントリデータでは、検索キー「００１０」＞検索データ「００００」である。したがって、大小判定処理により大きい（Ｈｉｇｈ）となるので上位アドレス「１」を読み出す。
【０１３３】
図６（Ｂ）の結果格納部２４には、２回目のメモリアクセスとして、テーブルアドレス「０」が検索アドレスとして読み出された場合が示されている。検索データ「００００」に対して上限値「０１１１」が算出された場合が示されている。したがって一致判定処理は一致（Ｈｉｔ）となる。ここで一致判定がＨｉｔのため結果格納部２４に格納されている暫定検索結果はＭｉｓｓからＰ３に更新される。また、大小判定処理として大きい（Ｈｉｇｈ）が判定結果となるため、次のサーチ対象は上位のテーブルアドレスとなる。
【０１３４】
次に、検索処理部２２は、検索テーブル４０３の上位のテーブルアドレス「１」を読み出し、検索キー「００１０」でサーチを実行する。
【０１３５】
検索処理部２２は、上記と同様に、読み出されたエントリデータの検索データおよびプレフィックス長データとに基づいて、読み出されたエントリデータの検索対象範囲の上限値を計算する。テーブルアドレス「１」のエントリデータの検索対象範囲の上限値は、読み出された検索データおよびプレフィックス長データに基づき「００１１」となる。
【０１３６】
検索処理部２２は、決定した検索対象範囲に基づいて検索キーが含まれるか否かの一致判定処理を実行する。
【０１３７】
本例の場合には、検索処理部２２は、検索キー「００１０」がエントリデータの検索対象範囲に入っていると判断する。すなわち、検索結果は一致（Ｈｉｔ）となる。
【０１３８】
この場合、テーブルアドレス「１」が最終アドレスとなるため、検索アドレスを決定するための大小判定処理は実行しない。
【０１３９】
図６（Ｂ）の結果格納部２４には、３回目のメモリアクセスとして、テーブルアドレス「１」が検索アドレスとして読み出された場合が示されている。検索データ「００１０」に対して上限値「００１１」が算出された場合が示されている。また、一致判定処理として一致（Ｈｉｔ）が格納されている。また、暫定検索結果として検索結果データ「Ｐ０」が格納されている。
【０１４０】
ここで、テーブルアドレス「１」のエントリデータのプレフィックス長データは「３」である。一方、結果格納部２４に格納されているテーブルアドレス「０」のエントリデータのプレフィックス長データは「１」である。したがって、検索処理部２２は、結果格納部２４のデータをプレフィックス長が大きい（有効ビット長が長い）ためエントリデータのテーブルアドレス「１」のエントリデータ検索結果データ「Ｐ０」に更新する。一方、プレフィックス長が小さい場合は結果格納部２４に格納される暫定検索結果は更新せず前回の結果を保持する。
【０１４１】
検索処理部２２は、一致判定結果がＨｉｔの場合、結果格納部２４に格納されている前回までの暫定検索結果のプレフィックス長と比較してプレフィックス長が大きい場合に暫定検索結果を更新し続けることで最も大きいプレフィックス長をもつ検索結果が結果格納部２４に保持される。検索処理部２２は、最終アドレスのバイナリサーチ終了時の結果格納部２４に格納された判定結果に基づいて最終的な検索結果データを出力する。
【０１４２】
次に、検索処理部２２は、検索キー「０１１０」に対する検索処理について説明する。
図６（Ｃ）には、結果格納部２４に格納されている検索キー「０１１０」に対する検索過程の情報が示されている。
【０１４３】
検索処理部２２は、上記で説明したように検索テーブル４０３の中間のテーブルアドレス「２」からサーチを開始する。
【０１４４】
図６（Ｃ）の結果格納部２４には、１回目のメモリアクセスとして、テーブルアドレス「２」が検索アドレスとして読み出された場合が示されている。検索データ「０１００」に対して上限値「０１０１」が算出された場合が示されている。また、大小判定処理として大きい（Ｈｉｇｈ）が判定結果として格納されている。また、一致判定処理としてミス（Ｍｉｓｓ）が格納されている。検索処理部２２は、大小判定処理により、検索キーが検索データよりも大きい（Ｈｉｇｈ）場合には次のバイナリサーチは上位アドレスに対応するエントリデータを読み出す。この場合には、上位アドレスであるテーブルアドレス「４」を読み出す。
【０１４５】
図６（Ｃ）の結果格納部２４には、２回目のメモリアクセスとして、テーブルアドレス「４」が検索アドレスとして読み出された場合が示されている。検索データ「１０１０」に対して上限値「１０１１」が算出された場合が示されている。したがって、一致判定処理としてミス（Ｍｉｓｓ）となる。また、大小判定処理として小さい（Ｌｏｗ）が判定結果となる。検索処理部２２は、大小判定処理により、検索キーが検索データよりも小さい（Ｌｏｗ）場合には次のバイナリサーチは下位アドレスに対応するエントリデータを読み出す。この場合には、下位アドレスであるテーブルアドレス「３」を読み出す。
【０１４６】
図６（Ｃ）の結果格納部２４には、３回目のメモリアクセスとして、テーブルアドレス「３」が検索アドレスとして読み出された場合が示されている。検索データ「０１１０」に対して上限値「０１１１」が算出された場合が示されている。したがって一致判定処理として一致（Ｈｉｔ）となる。そのため暫定検索結果は更新され、検索結果データ「Ｐ３」が格納される。
【０１４７】
検索処理部２２は、結果格納部２４に格納された判定結果に基づいて最終的な検索結果データを出力する。
【０１４８】
結果格納部２４には３回目のメモリアクセスでＨｉｔとなったためテーブルアドレス「３」のエントリデータの検索結果データである「Ｐ３」が検索処理部２２から出力される。
【０１４９】
当該方式により、本実施形態１に従う検索テーブルに対するバイナリサーチを用いたＬＰＭ検索を実行することが可能である。
【０１５０】
実施形態１に従う検索テーブルには、検索対象範囲の下限値のみが格納される。したがて、実施形態１に従う検索テーブルのテーブル容量は、従来方式の如く元検索テーブルのエントリ数の２倍にならないためテーブル容量を縮小することが可能である。すなわち、小容量のメモリで検索処理の実行が可能である。また、従来方式の如く検索結果データとして２つのデータを保持する必要がなく、１つの検索結果データのみを保持するためこの点でもテーブル容量を縮小することが可能である。
【０１５１】
また、テーブル容量を縮小することによりメモリアクセス回数も削減することが可能であり、検索処理を高速化させることも可能である。
【０１５２】
さらに、検索テーブルのエントリデータ数の削減によりテーブル構築の時間も短縮することが可能である。
【０１５３】
（実施形態２）
実施形態１に従う検索テーブルの生成において、図５（Ｄ）において各エントリ候補データの検索対象範囲が他のエントリ候補データの検索対象範囲によって分割される場合には、エントリデータを追加する方式について説明した。このため各エントリ候補データの検索対象範囲が他のエントリ候補データの検索対象範囲によって分割されない場合に比べて、エントリデータ数が増加する。
【０１５４】
実施形態２においては、このエントリデータ数の増加を抑制する方式について説明する。
【０１５５】
上記の実施形態１においては、図５（Ｄ）において、エントリ候補データＥｎｔｒｙ３の検索データ「０＊＊＊」の検索対象範囲は、エントリ候補データＥｎｔｒｙ０の検索データ「００１＊」の検索対象範囲と、エントリ候補データＥｎｔｒｙ１の検索データ「０１０＊」の検索対象範囲と重なる場合が示されている。
【０１５６】
すなわち、エントリ候補データＥｎｔｒｙ３の検索データ「０＊＊＊」の検索対象範囲は、エントリ候補データＥｎｔｒｙ０の検索データ「００１＊」およびエントリ候補データＥｎｔｒｙ１の検索データ「０１０＊」により分割される。
【０１５７】
実施形態１においては、エントリ候補データＥｎｔｒｙ３−０の検索データ「００００」とは別の検索データを含む新たなエントリ候補データＥｎｔｒｙ３−１を追加した。
【０１５８】
一方で、エントリ候補データＥｎｔｒｙ３の検索データ「０＊＊＊」を、検索対象範囲が重なるエントリ候補データＥｎｔｒｙ０の検索データ「００１＊」およびエントリ候補データＥｎｔｒｙ１の検索データ「０１０＊」と別にすれば検索対象範囲が分割されない。
【０１５９】
図７は、実施形態２に従う検索テーブルの生成について説明する図である。実施形態２における検索テーブルは、実施形態１と同様にテーブル生成部２６によって生成される。
【０１６０】
図７（Ａ）には、元検索テーブル４０２が示されている。
図７（Ｂ）には、検索テーブル６００，６０１が示されている。
【０１６１】
実施形態２において、検索回路の構成は実施形態１で示した構成と同様であるのでその詳細な説明については省略する。
【０１６２】
テーブル生成部２６は、実施形態１と同様に、エントリ候補データに従って複数の検索テーブルを生成する。
【０１６３】
検索データ設定部２６２は、実施形態１と同様に、各エントリ候補データに基づいてマスクされるビットを含む検索対象データの下限値を検索データとする。
【０１６４】
エントリデータ設定部２６４は、当該検索データと、プレフィックス長データおよび検索結果データとを関連付けたエントリデータを設定する。
【０１６５】
そして、エントリデータ設定部２６４は、検索テーブルにそれぞれ設定したエントリデータを格納する。
【０１６６】
エントリデータ設定部２６４は、検索テーブルにそれぞれ設定したエントリデータを格納する際、検索対象範囲が他のエントリデータによって分割されるか否かを判断し、分割されると判断した場合には、他の検索テーブルにエントリデータを格納する。
【０１６７】
本例の場合には、検索テーブル６００のテーブルアドレス「０」にエントリ候補データＥｎｔｒｙ０に対応する検索データ「００１０」、プレフィックス長データ「３」、検索結果データ「Ｐ０」が格納される。
【０１６８】
また、検索テーブル６００のテーブルアドレス「１」にエントリ候補データＥｎｔｒｙ１に対応する検索データ「０１００」、プレフィックス長データ「３」、検索結果データ「Ｐ１」が格納される。
【０１６９】
また、検索テーブル６００のテーブルアドレス「２」にエントリ候補データＥｎｔｒｙ２に対応する検索データ「１０１０」、プレフィックス長データ「３」、検索結果データ「Ｐ２」が格納される。
【０１７０】
一方で、エントリ候補データＥｎｔｒｙ３の検索データは、当該エントリ候補データＥｎｔｒｙ３と検索対象範囲が重なるエントリ候補データＥｎｔｒｙ０およびＥｎｔｒｙ１の検索データが格納された検索テーブル６００とは異なる検索テーブル６０１に格納される。すなわち、検索テーブル６０１のテーブルアドレス「０」にエントリ候補データＥｎｔｒｙ３に対応する検索データ「００００」、プレフィックス長データ「１」、検索結果データ「Ｐ３」が格納される。
【０１７１】
当該処理により、検索テーブル６００，６０１のそれぞれにおいては、他のエントリデータによってデータの検索対象範囲が分割されない。
【０１７２】
これによりエントリデータ数の増加を抑制することが可能である。
図８は、実施形態２に従う検索テーブルの実装方式について説明する図である。
【０１７３】
図８（Ａ）には、実施形態２に従う検索回路１１が示されている。
検索回路１１は、ＣＰＵ４０とメモリ５０とを含む。
【０１７４】
ＣＰＵ４０は、メモリ５０と協働することにより処理部２０の機能を実行する。
メモリ５０は、検索テーブル６００，６０１を含む。
【０１７５】
処理部２０は、メモリ５０に格納されている検索テーブル６００，６０１にアクセスすることにより上記の検索テーブルに対するバイナリサーチを実行することが可能である。
【０１７６】
図８（Ｂ）には、実施形態２に従う検索回路１２が示されている。
検索回路１２は、ＣＰＵ４０と、メモリ５１，５２とを含む。メモリ５１には、検索テーブル６００が格納されている。また、メモリ５２には、検索テーブル６０１が格納されている。
【０１７７】
処理部２０は、メモリ５１，５２にそれぞれ格納されている検索テーブル６００，６０１にアクセスすることにより上記の検索テーブルに対するバイナリサーチを実行することが可能である。検索回路１１ではメモリ５０に検索テーブル６００，６０１が格納されているため検索テーブル６００，６０１に同時にバイナリサーチを実行することは不可能だが検索回路１２では別々のメモリに格納されているため、検索テーブル６００，６０１に並列にバイナリサーチを実行することが可能となる。そのため検索回路１１と比較して検索性能が向上する。
【０１７８】
図８（Ｃ）には、実施形態２に従う検索回路１３が示されている。
検索回路１３は、ＣＰＵ４０Ａと、メモリ５３とを含む。
【０１７９】
メモリ５３は、検索テーブル６００を含む。
また、ＣＰＵ４０Ａは、キャッシュメモリを内蔵しており、当該キャッシュメモリに検索テーブル６０１を格納する。
【０１８０】
処理部２０は、メモリ５３に格納されている検索テーブル６００にアクセスすることにより上記の検索テーブルに対するバイナリサーチを実行することが可能である。また、処理部２０は、キャッシュメモリに格納されている検索テーブル６０１にアクセスすることにより上記の検索テーブルに対するバイナリサーチを実行することが可能である。
【０１８１】
検索回路１２と同様に検索テーブル６００、６０１を並列に動作させることが可能なため検索動作を高速化させることが可能である。また検索テーブル６０１は検索テーブル６００にくらべて小容量で実装可能なことが期待できるためキャッシュメモリに内蔵することで検索回路１２で必要なメモリ５２を削減できる。
【０１８２】
図９は、実施形態２に従う検索処理の順序について説明するフロー図である。
図９を参照して、処理部２０は、検索テーブル６００に対してバイナリサーチを実行する（ステップＳ２）。
【０１８３】
ステップＳ２において、処理部２０は、検索テーブル６００に対するサーチ処理において、一致判定処理結果が一致（Ｈｉｔ）であった場合（ステップＳ２においてＨｉｔ）には、検索を終了する（ステップＳ８）。そして、処理部２０は、検索テーブル６００における一致（Ｈｉｔ）したエントリデータに対応する検索結果データを出力する。
【０１８４】
一方、ステップＳ２において、処理部２０は、検索テーブル６００に対するサーチ処理において、一致判定処理結果がミス（Ｍｉｓｓ）であった場合（ステップＳ２においてＭｉｓｓ）には、検索テーブル６０１に対してバイナリサーチを実行する（ステップＳ４）。
【０１８５】
ステップＳ４において、処理部２０は、検索テーブル６０１に対するサーチ処理において、一致判定処理結果が一致（Ｈｉｔ）を示す場合（ステップＳ４においてＨｉｔ）には、検索を終了する（ステップＳ１０）。そして、処理部２０は、検索テーブル６０１における一致（Ｈｉｔ）したエントリデータに対応する検索結果データを出力する。
【０１８６】
一方、ステップＳ４において、処理部２０は、検索テーブル６０１に対するサーチ処理において、一致判定処理結果がミス（Ｍｉｓｓ）となった場合（ステップＳ４においてＭｉｓｓ）には、検索を終了する。処理部２０は、検索結果としてミス（Ｍｉｓｓ）を出力する（ステップＳ６）。
【０１８７】
そして、処理を終了する（エンド）。
実施形態２に従う方式は、プリフィックス長データが大きいエントリデータを有する検索テーブルをプリフィックス長データが小さいエントリデータを有する検索テーブルよりも優先して検索処理する。
【０１８８】
当該処理により、検索テーブルを分割したことに起因する検索処理時間の全体的な増加を抑制することが可能である。
【０１８９】
（実施形態３）
上記の実施形態２では、エントリデータの追加を抑制してテーブル容量を縮小する方式について説明した。
【０１９０】
実施形態３においては、実施形態２よりもさらにテーブル容量を縮小する方式について説明する。
【０１９１】
具体的には、検索データの設定値を最適化することにより、エントリデータの増加を回避する。
【０１９２】
図１０は、実施形態１に従う別の検索テーブルの生成について説明する図である。実施形態３における検索テーブルは、実施形態１と同様にテーブル生成部２６によって生成される。
【０１９３】
図１０（Ａ）には、元検索テーブル４０４が示されている。
元検索テーブル４０４は、エントリアドレス０〜４のそれぞれに検索対象となる複数のエントリ候補データＥｎｔｒｙ０〜４を格納する。本例においては、５つのエントリ候補データが元検索テーブル４０４に格納されている。
【０１９４】
エントリ候補データは、マスクされるビットを含む検索対象データと、検索対象データが検索キーと一致した場合に検索結果として出力する検索結果データとを含む。
【０１９５】
ここで、上記で説明したように、エントリ候補データＥｎｔｒｙ４４の検索データ「＊＊＊＊」の検索対象範囲は、エントリ候補データＥｎｔｒｙ０の検索データ「０００＊」の検索対象範囲と、エントリ候補データＥｎｔｒｙ１の検索データ「０１０＊」の検索対象範囲と、エントリ候補データＥｎｔｒｙ２の検索データ「１００＊」の検索対象範囲と、エントリ候補データＥｎｔｒｙ３の検索データ「１１０＊」の検索対象範囲と重なる。
【０１９６】
すなわち、エントリ候補データＥｎｔｒｙ４の検索データ「＊＊＊＊」の検索対象範囲は、エントリ候補データＥｎｔｒｙ０の検索データ「０００＊」、エントリ候補データＥｎｔｒｙ１の検索データ「０１０＊」、エントリ候補データＥｎｔｒｙ２の検索データ「１００＊」、エントリ候補データＥｎｔｒｙ３の検索データ「１１０＊」により分割される。
【０１９７】
これにより、エントリ候補データＥｎｔｒｙ４−０の検索データ「００１０」とは別の検索データを含む新たな複数のエントリ候補データＥｎｔｒｙ４−１〜Ｅｎｔｒｙ４−３を追加する必要がある。
【０１９８】
図１０（Ｂ）は、新たなエントリデータを追加した検索テーブル４０６を説明する図である。
【０１９９】
一例として、テーブルアドレス「０００」にエントリ候補データＥｎｔｒｙ０に対応する検索データ「００００」、プレフィックス長データ「３」、検索結果データ「Ｐ０」が格納される。
【０２００】
一例として、テーブルアドレス「００１」にエントリ候補データＥｎｔｒｙ４−０に対応する検索データ「００１０」、プレフィックス長データ「０」、検索結果データ「Ｐ４」が格納される。
【０２０１】
一例として、テーブルアドレス「０１０」にエントリ候補データＥｎｔｒｙ１に対応する検索データ「０１００」、プレフィックス長データ「３」、検索結果データ「Ｐ１」が格納される。
【０２０２】
一例として、テーブルアドレス「０１１」にエントリ候補データＥｎｔｒｙ４−１に対応する検索データ「０１１０」、プレフィックス長データ「０」、検索結果データ「Ｐ４」が格納される。
【０２０３】
一例として、テーブルアドレス「１００」にエントリ候補データＥｎｔｒｙ２に対応する検索データ「１０００」、プレフィックス長データ「３」、検索結果データ「Ｐ２」が格納される。
【０２０４】
一例として、テーブルアドレス「１０１」にエントリ候補データＥｎｔｒｙ４−２に対応する検索データ「１０１０」、プレフィックス長データ「０」、検索結果データ「Ｐ４」が格納される。
【０２０５】
一例として、テーブルアドレス「１１０」にエントリ候補データＥｎｔｒｙ３に対応する検索データ「１１００」、プレフィックス長データ「３」、検索結果データ「Ｐ３」が格納される。
【０２０６】
一例として、テーブルアドレス「１１１」にエントリ候補データＥｎｔｒｙ４−３に対応する検索データ「１１１０」、プレフィックス長データ「０」、検索結果データ「Ｐ４」が格納される。
【０２０７】
したがって、実施形態１に従う方式においては、エントリデータが３個増加することになる。エントリ候補データＥｎｔｒｙ４が他のエントリ候補データＥｎｔｒｙ１〜３により分割されるために生じたものである。
【０２０８】
一方で、エントリ候補データＥｎｔｒｙ４の検索データを他の検索データよりも優先して検索処理を実行できれば、それによる検索結果データを取得することができるためエントリデータを追加する必要はない。
【０２０９】
この点で、上記の実施形態１において説明した検索データは、検索対象範囲の下限値に設定する場合について説明したが任意の値に設定することが可能である。検索データは検索対象範囲内の任意の値に設定することが可能である。
【０２１０】
したがって、エントリ候補データＥｎｔｒｙ４の検索データを他の検索データよりも優先して検索処理を実行するように調整する。
【０２１１】
次表に示すように、エントリ候補データＥｎｔｒｙ４が包含するプレフィックス長データがエントリ候補データＥｎｔｒｙ４より大きいエントリ候補データに対応する検索データを格納した場合が示されている。
【０２１２】
【表３】
2020201656.tif 000005
【０２１３】
上記表に示されるように、エントリ候補データＥｎｔｒｙ４の検索データが包含するエントリ候補データＥｎｔｒｙ０〜３の検索データがソートされる。
【０２１４】
テーブルアドレスＡｄｄ「０００（Ｍｉｎ）」に対応してエントリ候補データＥｎｔｒｙ０の検索データ「００００」が格納される。また、テーブルアドレスＡｄｄ「０１１（Ｍａｘ）」に対応してエントリ候補データＥｎｔｒｙ３の検索データ「１１００」が格納される。
【０２１５】
したがって、エントリ候補データＥｎｔｒｙ４の検索データの挿入位置の範囲はＥｎｔｒｙ４が増加する分（Ｍａｘ）＋１の範囲となり、「０００（Ｍｉｎ）」から「１００（Ｍａｘ＋１）」のどこかに挿入される。
【０２１６】
ここで、エントリ候補データＥｎｔｒｙ４の検索データがテーブルアドレス「０００〜１００」の中で最初にバイナリサーチが実施される位置にソートされるようにするためには取りうるテーブルアドレスの範囲の中で変化しているアドレスの最上位ビットを1に設定したアドレスにエントリ候補データＥｎｔｒｙ４の検索データを挿入することである。
【０２１７】
この例ではテーブルアドレスａｄｄ［２：０］の中で変化している最上位ビットはアドレスＡｄｄ［２］である。
【０２１８】
したがって、テーブルアドレスＡｄｄ「１００」がエントリ候補データＥｎｔｒｙ４の検索データの挿入位置となる。
【０２１９】
そして、当該挿入位置に検索データを挿入するためにエントリ候補データＥｎｔｒｙ４の検索対象範囲内の検索データの１つである「１１１０」に設定する。
【０２２０】
図１１は、実施形態３に従う検索テーブルの生成について説明する図である。
図１１（Ａ）には、元検索テーブル４０４が示されている。
【０２２１】
元検索テーブル４０４は、エントリアドレス０〜４のそれぞれに従ってエントリデータを生成するための候補となる複数のエントリ候補データＥｎｔｒｙ０〜４を格納する。本例においては、５つのエントリ候補データが元検索テーブル４０４に格納されている。
【０２２２】
エントリ候補データは、マスクされるビットを含む検索対象データと、検索対象データが検索キーと一致した場合に検索結果として出力する検索結果データとを含む。
【０２２３】
ここで、上記で説明したように、エントリ候補データＥｎｔｒｙ４の検索データ「＊＊＊＊」の検索対象範囲は、エントリ候補データＥｎｔｒｙ０の検索データ「０００＊」の検索対象範囲と、エントリ候補データＥｎｔｒｙ１の検索データ「０１０＊」の検索対象範囲と、エントリ候補データＥｎｔｒｙ２の検索データ「１００＊」の検索対象範囲と、エントリ候補データＥｎｔｒｙ３の検索データ「１１０＊」の検索対象範囲と重なる。
【０２２４】
すなわち、エントリ候補データＥｎｔｒｙ４の検索データ「＊＊＊＊」の検索対象範囲は、エントリ候補データＥｎｔｒｙ０の検索データ「０００＊」、エントリ候補データＥｎｔｒｙ１の検索データ「０１０＊」、エントリ候補データＥｎｔｒｙ２の検索データ「１００＊」、エントリ候補データＥｎｔｒｙ３の検索データ「１１０＊」により分割される。
【０２２５】
図１１（Ｂ）は、実施形態３に従う検索テーブル４０８を説明する図である。
具体的には、エントリ候補データＥｎｔｒｙ４が包含するプレフィックス長データがエントリ候補データＥｎｔｒｙ４より大きいエントリ候補データに関して、当該エントリ候補データの検索対象データの下限値を検索データとする。
【０２２６】
一例として、テーブルアドレス「０００」にエントリ候補データＥｎｔｒｙ０に対応する検索データ「００００」、プレフィックス長データ「３」、検索結果データ「Ｐ０」が格納される。
【０２２７】
一例として、テーブルアドレス「００１」にエントリ候補データＥｎｔｒｙ１に対応する検索データ「０１００」、プレフィックス長データ「３」、検索結果データ「Ｐ１」が格納される。
【０２２８】
一例として、テーブルアドレス「０１０」にエントリ候補データＥｎｔｒｙ２に対応する検索データ「１０００」、プレフィックス長データ「３」、検索結果データ「Ｐ２」が格納される。
【０２２９】
一例として、テーブルアドレス「０１１」にエントリ候補データＥｎｔｒｙ３に対応する検索データ「１１００」、プレフィックス長データ「３」、検索結果データ「Ｐ３」が格納される。
【０２３０】
次に、プレフィックス長データが小さいエントリ候補データに関して、当該エントリ候補データの検索対象データＥｎｔｒｙ４のうちの１つを検索データとする。
【０２３１】
本例においては、上記で説明したように、テーブルアドレスＡｄｄ「１００」がエントリ候補データＥｎｔｒｙ４の検索データの挿入位置となるように、検索データを「１１１０」に設定する。
【０２３２】
そして、一例として、テーブルアドレス「１００」にエントリ候補データＥｎｔｒｙ４に対応する検索データ「１１１０」、プレフィックス長データ「０」、検索結果データ「Ｐ４」が格納される。
【０２３３】
当該検索テーブルを用いて検索処理部２２によるバイナリサーチが可能となる。
図１２は、実施形態３に従う検索テーブル４０８に対する検索処理について説明する図である。
【０２３４】
検索処理部２２は、検索テーブル４０８にアクセスし、検索処理を実行する。検索処理部２２は、検索過程の情報を結果格納部２４に格納する。
【０２３５】
図１２（Ａ）には、検索テーブル４０８が示されている。
ここで、検索処理部２２は、検索キー「０１１１」に対する検索処理を実行する。
【０２３６】
図１２（Ｂ）には、結果格納部２４に格納されている検索キー「０１１１」に対する検索過程の情報が示されている。
【０２３７】
検索処理部２２は、検索テーブル４０８の中間のテーブルアドレス「４（「１００」）」からバイナリサーチを開始する。
【０２３８】
結果格納部２４には、１回目のメモリアクセスとして、テーブルアドレス「４」が検索アドレスとして読み出された場合が示されている。検索データ「１１１０」に対して上限値「１１１１」が算出される。これにより検索キーの一致判定結果はHitとなる場合が示されている。そのため、暫定検索結果として検索結果データ「Ｐ４」が格納されている。また、大小判定処理として小さい（Ｌｏｗ）が判定結果として格納されている。検索処理部２２は、大小判定処理により、検索キーが検索データよりも小さい（Ｌｏｗ）場合には次のバイナリサーチは下位アドレスに対応するエントリデータを読み出す。この場合には、下位アドレス「２」を読み出す。
【０２３９】
次に、検索処理部２２は、２回目のメモリアクセスとして、検索テーブル４０８の下位のテーブルアドレス「２（０１０）」を読み出し、検索キー「０１１１」でバイナリサーチする。
【０２４０】
検索処理部２２は、上記と同様に読み出されたエントリデータの検索データおよびプレフィックス長データとに基づいて、検索対象範囲の上限値を計算する。
【０２４１】
検索処理部２２は、決定した検索対象範囲に基づいて検索キーが含まれるか否かの一致判定処理を実行する。
【０２４２】
本例の場合には、検索処理部２２は、検索キー「０１１１」がエントリデータの検索対象範囲に入っていないと判断する。すなわち、検索結果はミス（Ｍｉｓｓ）となる。したがって、検索結果データは更新されない。
【０２４３】
また、検索処理部２２は、検索データ（「１０００」）と検索キー「０１１１」との大小判定処理を実行する。この比較結果に基づいて次の検索アドレスを決定する。
【０２４４】
このエントリデータでは、検索キー（Ｋｅｙ＝０１１１）＜検索データ（「１０００」）である。したがって、大小判定処理により小さい（Ｌｏｗ）となるので下位アドレス「１」を読み出す。
【０２４５】
図１２（Ｂ）の結果格納部２４には、３回目のメモリアクセスとして、テーブルアドレス「１」が検索アドレスとして読み出された場合が示されている。検索データ「０１００」に対して上限値「０１０１」が算出された場合が示されている。また、大小判定処理として大きい（Ｈｉｇｈ）が判定結果として格納されている。また、一致判定処理としてミス（Ｍｉｓｓ）となる。したがって、検索結果データは更新されない。
【０２４６】
検索処理部２２は、結果格納部２４に格納された判定結果に基づいて最終的な検索結果データを出力する。
【０２４７】
検索処理部２２は、格納された検索結果データ「Ｐ４」を出力する。
当該処理により、本実施形態３に従う検索テーブルに対するバイナリサーチを実行することが可能である。
【０２４８】
実施形態３においては、検索データの設定値を最適化することにより、エントリデータの増加を回避することが可能である。
【０２４９】
したがって、実施形態１よりもさらにテーブル容量を縮小することが可能である。
上記においては、検索テーブルのテーブルアドレスとして３ビットのアドレス範囲が設定されている場合について説明したが４ビットのアドレス範囲が設定されている場合であっても同様に適用可能である。
【０２５０】
【表４】
2020201656.tif 000006
【０２５１】
上記表に示されるように、４ビットのアドレス範囲が設定される場合に、変化するアドレスの最上位ビットに従ってエントリデータの挿入位置を設定することが可能である。
【０２５２】
当該位置になるように検索データを設定することにより、プレフィックス長データが小さい検索データを含むエントリデータについて、プレフィックス長データが大きい検索データを含むエントリデータよりも優先して検索処理を実行することが可能である。
【０２５３】
上記の実施形態においては、処理部２０の機能としてＣＰＵにメモリに格納されたプログラムを実行することにより各機能ブロックを実現する構成について説明したが、特にこれに限られず専用回路を設けて各機能ブロックを実現することも可能である。
【０２５４】
以上、本開示を実施形態に基づき具体的に説明したが、本開示は、実施形態に限定されるものではなく、その要旨を逸脱しない範囲で種々変更可能であることはいうまでもない。
【符号の説明】
【０２５５】
１  通信機器、２  スイッチ、１０，１１，１２，１３  検索回路、２０  処理部、２２  検索処理部、２４  結果格納部、２６  テーブル生成部、３０，２００，２０１，４０１，４０２，４０３，４０６，４０８，６００，６０１  検索テーブル、５０，５１，５２，５３  メモリ、２６０  データ取得部、２６２  検索データ設定部、２６４  エントリデータ設定部、２６６  エントリデータ追加設定部。
【図１】
2020201656.tif 000007
【図２】
2020201656.tif 000008
【図３】
2020201656.tif 000009
【図４】
2020201656.tif 000010
【図５】
2020201656.tif 000011
【図６】
2020201656.tif 000012
【図７】
2020201656.tif 000013
【図８】
2020201656.tif 000014
【図９】
2020201656.tif 000015
【図１０】
2020201656.tif 000016
【図１１】
2020201656.tif 000017
【図１２】
2020201656.tif 000018