(57)【特許請求の範囲】
【請求項１】
マスクデータ、検索ＩＰアドレス、第１ポインタ、第２ポインタ、および前記検索ＩＰアドレスと入力した「相手ＩＰアドレス」の比較の結果が一致したときに出力されるデータである情報データの組を１つのデータ群とし、複数の該データ群からなるデータテーブルが格納されたデータ記憶手段（１〜４）と、
入力した前記「相手ＩＰアドレス」を一時的に保持する第１レジスタ（６）と、
前記データ記憶手段（１〜４）において現在アクセスしているデータ群を指示するアドレスを保持する第２レジスタ（５）と、
前記データ記憶手段（１〜４）における現在アクセスされているデータ群の前記検索ＩＰアドレス、前記第１ポインタ、前記第２ポインタ、および前記情報データをそれぞれ一時的に保持する第３〜第６レジスタ（８〜１１）と、
前記第１レジスタ（６）から前記「相手ＩＰアドレス」を受けて前記アクセスされているデータ群のマスクデータに応じてマスク処理を行うマスク処理器（７）と、
該マスク処理器（７）から出力されるマスク処理された前記「相手ＩＰアドレス」と前記第３レジスタ（８）の内容との大小および一致関係を判定する比較器（１２）と、
該比較器（１２）の比較により一方が他方より大きいと判定した場合に前記第４レジスタ（９）の内容を、小さいと判定した場合に前記第５レジスタ（１０）の内容を、前記第２レジスタ（５）に出力して、前記データ記憶手段（１〜４）をアクセスするアドレスを更新するセレクタ（１３）と、
を有し、前記比較器（１２）の比較結果が一致と判定された場合に前記第６レジスタ（１１）の内容を検索データとして出力することを特徴とするデータ検索回路。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、外部から入力された項目をキーとして、データ記憶手段に予め格納した複数のデータ群からなるデータテーブルの内から一致する項目を含むデータ群を検索し、該検索したデータ群の中の特定のデータを読み出すデータ検索回路に係り、特にインターネットプロトコル（ＩＰ）のためのルーティング処理などで用いられるベストマッチ処理を高速に行うような回路に好適なデータ検索回路に関するものである。
【０００２】
【従来の技術】
複数の入出力ポートをもつＩＰルーティング処理装置（ルータ）を用いてＩＰルーティング処理を行うには、入力ポートに到着したパケットのヘッダ情報から３２ビットの「相手ＩＰアドレス」を検出し、その「相手ＩＰアドレス」に対応した出力ポートにそのパケットを送出する必要がある。
【０００３】
このとき、どの出力ポートにパケットを送出するかを決定する必要があるが、これは、ルータ内にあるルーティングテーブルを「相手ＩＰアドレス」をキーとして検索し、一致したデータ群に設定されている出力ポートを選択することによって行う。
【０００４】
この検索処理には、ベストマッチ方式が採用されている。このベストマッチ処理は、まず、ルーティングテーブル内のＩＰアドレスと、そのＩＰアドレスごとに一対一対応で別途用意されているネットマスク情報により「相手ＩＰアドレス」の一部（例えば下位）のビットをマッチングの対象から除外した内容（マスキング処理した内容）とを比較処理する。この際、複数候補がマッチしたときは、マスクの長さ（ビット幅）が最も短いものを最優先候補として採用する。
【０００５】
【発明が解決しようとする課題】
ところが、このベストマッチ処理は、ルーティング処理の主要部分であるにもかかわらず、従来ではＣＰＵを使用してソフトウエアで処理していたため、ルータ自体のスループットを向上させる上で問題であった。すなわち、従来では、前回の検索で得た先のデータ群に一致するＩＰアドレスがなかったとき、次に検索すべき別のデータ群を指定するポインタ（次アドレス）を、ソフトウエア計算により得る必要があり、時間がかかっていた。
【０００６】
本発明の目的は、上記したベストマッチ処理をはじめ、検索キーの一部を１回の検索ごとに別個の情報でマスクする必要のあるようなデータ検索処理を高速に行うことができるようにしたデータ検索回路を提供することである。
【０００７】
（削除）
【０００８】
（削除）
【０００９】
【課題を解決するための手段】
本発明のデータ検索回路は、マスクデータ、検索ＩＰアドレス、第１ポインタ、第２ポインタ、および前記検索ＩＰアドレスと入力した「相手ＩＰアドレス」の比較の結果が一致したときに出力されるデータである情報データの組を１つのデータ群とし、複数の該データ群からなるデータテーブルが格納されたデータ記憶手段（１〜４）と、入力した前記「相手ＩＰアドレス」を一時的に保持する第１レジスタ（６）と、前記データ記憶手段（１〜４）において現在アクセスしているデータ群を指示するアドレスを保持する第２レジスタ（５）と、前記データ記憶手段（１〜４）における現在アクセスされているデータ群の前記検索ＩＰアドレス、前記第１ポインタ、前記第２ポインタ、および前記情報データをそれぞれ一時的に保持する第３〜第６レジスタ（８〜１１）と、前記第１レジスタ（６）から前記「相手ＩＰアドレス」を受けて前記アクセスされているデータ群のマスクデータに応じてマスク処理を行うマスク処理器（７）と、該マスク処理器（７）から出力されるマスク処理された前記「相手ＩＰアドレス」と前記第３レジスタ（８）の内容との大小および一致関係を判定する比較器（１２）と、該比較器（１２）の比較により一方が他方より大きいと判定した場合に前記第４レジスタ（９）の内容を、小さいと判定した場合に前記第５レジスタ（１０）の内容を、前記第２レジスタ（５）に出力して、前記データ記憶手段（１〜４）をアクセスするアドレスを更新するセレクタ（１３）と、を有し、前記比較器（１２）の比較結果が一致と判定された場合に前記第６レジスタ（１１）の内容を検索データとして出力するように構成した。
【００１０】
【発明の実施の形態】
図１は本発明の１つの実施の形態のデータ検索回路の構成を示す図であり、ＩＰのルーティング処理におけるベストマッチ処理を行うための回路である。１〜４はＳＲＡＭで構成され、検索対象がテーブル（ルーティングテーブル）として格納されたメモリ回路（データ記憶手段）であり、これらは全てアドレス用のレジスタ５によってアドレッシングされる。
【００１１】
まず、メモリ回路１には入力する「相手ＩＰアドレス」用のマスクデータが、メモリ回路２には入力する「相手ＩＰアドレス」（ただし、マスク処理済み）と比較されるＩＰアドレスが、メモリ回路３にはその比較の結果が不一致だったときに次に検索すべきデータ群のアドレスを示すポインタが、メモリ回路４には比較の結果が一致したとき読み出す情報（例えば、当該パケットを次に送るべきルータのＩＰアドレス等）が、それぞれ格納されている。
【００１２】
これらのマスクデータ、ＩＰアドレス、ポインタ、および情報は、その１組で１つのアドレスをもつデータ群を構成し、該データ群の複数個が個々の異なったアドレスで、メモリ回路１〜４にルーティングテーブルとして格納されている。なお、メモリ回路３に格納されたポインタは、「ｌｅｆｔ」と「ｒｉｇｈｔ  」という２つのアドレスデータである。
【００１３】
６は入力する「相手ＩＰアドレス」を格納するレジスタ、７はその「相手ＩＰアドレス」の特定のビットに対してメモリ回路１から読み出したマスクデータでマスク処理を行うマスク処理器、８はメモリ回路２から読み出した「検索ＩＰアドレス」を格納するレジスタ、９はメモリ回路３から読み出したポインタ「ｌｅｆｔ」を格納するレジスタ、１０はメモリ回路３から読み出したポインタ「ｒｉｇｈｔ  」を格納するレジスタ、１１はメモリ回路４から読み出した情報を格納するレジスタである。
【００１４】
１２はマスク処理器７でマスク処理した「相手ＩＰアドレス」とレジスタ８に格納した「検索ＩＰアドレス」を比較する比較器であって、一致／不一致を判断し、さらに不一致の場合には入力された２つのデータを０以上の整数とみなし、「相手ＩＰアドレス」が「検索ＩＰアドレス」よりも大きいとき「０」を、その反対のとき「１」を出力する。
【００１５】
１３は比較器１２の比較結果が不一致とき、その不一致内容によってレジスタ９のデータ又はレジスタ１０のデータを選択して出力するセレクタ、１４は初期に「相手ＩＰアドレス」に応じて入力する「入力先頭アドレス」を選択し、その後にセレクタ１３の出力データを選択するセレクタ、１５はセレクタ１３から出力するポインタが「アドレス０番地」を示すとき「一致データなし」の信号を出力する終了判断器である。
【００１６】
次に動作を説明する。まず、レジスタ６に「相手ＩＰアドレス」を格納し、またその「相手ＩＰアドレス」に対応した「入力先頭アドレス」をレジスタ５に、セレクタ１４を介して格納する。このセレクタ１４は、レジスタ５への格納が完了した後に、次の処理のためにセレクタ１３からデータ（ポインタ）を入力するよう設定される。
【００１７】
次に、レジスタ５に格納された「入力先頭アドレス」によって、メモリ回路１〜４のマスクデータ、ＩＰアドレス、ポインタ「ｌｅｆｔ，ｒｉｇｈｔ  」、情報が読み出され、それぞれマスク処理器７、レジスタ８、９、１０、１１に格納される。ここで、レジスタ６の「相手ＩＰアドレス」は、マスク処理器７においてマスク処理され、比較器１２の一方の入力となる。
【００１８】
この比較器１２では、マスク処理器７から出力する「相手ＩＰアドレス」とレジスタ８から出力する「検索ＩＰアドレス」とを比較し、両者が一致するときは、レジスタ１１に対して、そこに格納された情報を検索結果として出力するよう指示する。
【００１９】
しかし、「相手ＩＰアドレス」が「検索ＩＰアドレス」よりも大きいときはセレクタ１３でレジスタ９を選択し、そこに格納されているポインタ「ｌｅｆｔ」をセレクタ１４を介してレジスタ５に格納して、そのポインタ「ｌｅｆｔ」の内容でメモリ回路１〜４に対して新たなアドレッシングを行い再検索する。また、逆に、「相手ＩＰアドレス」が「検索ＩＰアドレス」よりも小さいときはセレクタ１３でレジスタ１０を選択し、そこに格納されているポインタ「ｒｉｇｈｔ  」をセレクタ１４を介してレジスタ５に格納して、そのポインタ「ｒｉｇｈｔ  」の内容で新たなアドレッシングを行い再検索する。
【００２０】
このようにして、比較器１２から一致信号がでるまで、比較処理と検索が繰り返される。しかし、セレクタ１３から出るポインタ「ｌｅｆｔ」、「ｒｉｇｈｔ  」が「アドレス０番地」を示したときには、終了判断器１５により、「一致データなし」の信号を外部に出力し、処理を中断する。
【００２１】
以上から、ポインタが予めメモリ回路３に登録されているので、従来のようにソフトウエア計算等によりポインタを生成する手段が必要がなく、検索処理の速度を高速化できる。また、ハードウエア的にポインタ生成回路を設けると、通常では加算器等のように全体の処理速度を低下させる回路を必要とするが、それも必要ないため処理速度が更に向上する。
【００２２】
図２は、図１におけるメモリ回路１〜４へのデータの格納の一形式を示した図である。これは、図２の上側に示したような２分木方式でデータを格納する際のデータ格納形式を模式的に表したものである。ＡからＩまで９個のデータを図２の下側のようにテーブルに格納することにより、図１の回路での２分木探索処理が実現できる。この際、マスクの小さいものからＡ，Ｂ，Ｃ，．．．．，Ｉの順に格納しておくと、その順に比較処理が実効されるため、図１の回路を使用してベストマッチ処理が実現できる。
【００２３】
図３は、図１のメモリ回路１〜４へのデータの格納の別の形式を示した図である。図３の右側に示すように「ｌｅｆｔ」，「ｒｉｇｈｔ  」に同じ値のポインタを格納すると、左側に示したようなデータ検索の構造となり、これを図１の回路に適用すると、ＡからＩに向かって順次線形探索を行うことができる。
【００２４】
以上のように、本実施の形態では、メモリ回路３に格納するポインタの値を適宜設定／変更することにより、２分木方式の探索、あるいは線形方式の探索が実現でき、その他の方式の探索も可能となり、検索回路を変更する必要がない。
【００２５】
【発明の効果】
以上から本発明によれば、先の検索で得た先のデータ群に一致する項目がなかったとき次に検索すべき別のデータ群を指定するポインタを、前記先のデータ群の内に持たせたので、次回の検索のためのポインタ計算を行うことなくそれを参照することで次の検索用のポインタを得ることができ、ＩＰルーティング処理のベストマッチ処理に適用しても、その処理を高速化でき、スループットを向上させることができる。
【００２６】
また、データ記憶手段に格納するポインタのデータ構造を変更するのみでデータ検索順序を実質的に変更できるため、回路を一旦構成した後であってもその回路を変更することなく、データの特性に合った方式の検索を容易に実現できるという利点がある。
【００２７】
さらに、レジスタ等の単純な回路構成とデータ記憶手段を用いるのみで、ベストマッチ処理をはじめ、検索キーの一部を１回の検索ごとに別個の情報でマスクする必要のあるデータ検索処理を実行するデータ検索回路が実現できるという利点もある。
【図面の簡単な説明】
【図１】本発明の１つの実施の形態のデータ検索回路の構成を示す機能ブロック図である。
【図２】２分木方式の検索を実現するときのデータテーブルの構成の説明図である。
【図３】線形方式の検索を実現するときのデータテーブルの構成の説明図である。
【図１】
0003558151.tif 000002
【図２】
0003558151.tif 000003
【図３】
0003558151.tif 000004