(57)【特許請求の範囲】
【請求項１】
パトリシアツリーを構成するノードのアドレスと、このアドレスに対応するエントリーデータの着目ビット位置に関する情報と、この着目ビット位置に対応するエントリーデータの取り得る値に対する行き先ノードまたは終端点の情報とが記録されたパトリシアツリー接続テーブルを備え、
前記着目ビット位置は、パトリシアツリーの始点から下流に向かう段毎に順次先頭ビットから１ビットずつ下位ビットに移行し、
前記テーブルにおけるパトリシアツリーの始点から下流に向かうｋ（ｋは自然数）段目までのノード毎に順次その着目ビットの値にしたがってエントリーデータの行き先ノードまたは終端点を検索する第一検索手段と、
前記テーブルにおける（ｋ＋１）段目以降の複数のサブツリー毎に、そのサブツリーの始点から下流に向かうノード毎に順次その着目ビットの値にしたがってエントリーデータの行き先ノードまたは終端点をそれぞれ並行して検索する複数の第二検索手段と、
この第二検索手段の複数の検索結果の中から前記第一検索手段の検索結果に基づきいずれか一つを最終的な最長一致検索結果として選択する手段と
を備えたことを特徴とする最長一致検索回路。
【請求項２】
パトリシアツリーを構成するノードのアドレスと、このアドレスに対応するエントリーデータの着目ビット位置に関する情報と、この着目ビット位置に対応するエントリーデータの取り得る値に対する行き先ノードまたは終端点の情報とが記録されたパトリシアツリー接続テーブルを備え、
前記着目ビット位置は、パトリシアツリーの始点から下流に向かう段毎に順次先頭ビットから１ビットずつ下位ビットに移行し、
前記テーブルにおけるパトリシアツリーの始点から下流に向かうｋ段目までのノード毎に順次その着目ビットの値にしたがって複数のエントリーデータの行き先ノードまたは終端点を並行して検索する複数の第三検索手段が設けられ、
前記テーブルにおける（ｋ＋１）段目以降の複数のサブツリー毎に、そのサブツリーの始点から下流に向かうノード毎に順次その着目ビットの値にしたがってエントリーデータの行き先ノードまたは終端点をそれぞれ並行して検索する複数の第四検索手段が設けられ、
複数の前記第三検索手段の検索結果に基づき前記第三検索手段から出力されるエントリーデータをその行き先ノードに振り分けあるいは前記第三検索手段により検索された終端点を最長一致検索結果出力に振り分ける手段が設けられ、
前記第四検索手段は、前記振り分ける手段により行き先ノードに振り分けられたエントリーデータについて前記サブツリーの始点から下流に向かうノード毎に順次その着目ビットの値にしたがって終端点を検索する手段を備えた
ことを特徴とする最長一致検索回路。
【請求項３】
前記振り分ける手段により振り分けられたエントリーデータを一時蓄積する手段が設けられ、この一時蓄積する手段は、一つのノードに対して複数のエントリーデータが蓄積されたときには、蓄積されたエントリーデータを一つずつ当該ノードにエントリーする手段を備えた請求項２記載の最長一致検索回路。
【請求項４】
情報処理装置にインストールすることにより、その情報処理装置に、最長一致検索回路に相応する機能として、
パトリシアツリーを構成するノードのアドレスと、このアドレスに対応するエントリーデータの着目ビット位置に関する情報と、この着目ビット位置に対応するエントリーデータの取り得る値に対する行き先ノードまたは終端点の情報とが記録されたパトリシアツリー接続テーブルに相応する機能を実現させ、
前記着目ビット位置は、パトリシアツリーの始点から下流に向かう段毎に順次先頭ビットから１ビットずつ下位ビットに移行し、
前記テーブルにおけるパトリシアツリーの始点から下流に向かうｋ段目までのノード毎に順次その着目ビットの値にしたがってエントリーデータの行き先ノードまたは終端点を検索する第一検索機能と、
前記テーブルにおける（ｋ＋１）段目以降の複数のサブツリー毎に、そのサブツリーの始点から下流に向かうノード毎に順次その着目ビットの値にしたがってエントリーデータの行き先ノードまたは終端点をそれぞれ並行して検索する複数の第二検索機能と、
この第二検索機能の複数の検索結果の中から前記第一検索機能の検索結果に基づきいずれか一つを最終的な最長一致検索結果として選択する機能と
を実現させる
ことを特徴とするプログラム。
【請求項５】
情報処理装置にインストールすることにより、その情報処理装置に、最長一致検索回路に相応する機能として、
パトリシアツリーを構成するノードのアドレスと、このアドレスに対応するエントリーデータの着目ビット位置に関する情報と、
この着目ビット位置に対応するエントリーデータの取り得る値に対する行き先ノードまたは終端点の情報とが記録されたパトリシアツリー接続テーブルに相応する機能を実現させ、
前記着目ビット位置は、パトリシアツリーの始点から下流に向かう段毎に順次先頭ビットから１ビットずつ下位ビットに移行し、
前記テーブルにおけるパトリシアツリーの始点から下流に向かうｋ段目までのノード毎に順次その着目ビットの値にしたがって複数のエントリーデータの行き先ノードまたは終端点を並行して検索する複数の第三検索機能を実現させ、
前記テーブルにおける（ｋ＋１）段目以降の複数のサブツリー毎に、そのサブツリーの始点から下流に向かうノード毎に順次その着目ビットの値にしたがってエントリーデータの行き先ノードまたは終端点をそれぞれ並行して検索する複数の第四検索機能を実現させ、
複数の前記第三検索機能の検索結果に基づき前記第三検索機能から出力されるエントリーデータをその行き先ノードに振り分けあるいは前記第三検索機能により検索された終端点を最長一致検索結果出力に振り分ける機能を実現させ、
前記第四検索機能として、この振り分ける機能により行き先ノードに振り分けられたエントリーデータについて前記サブツリーの始点から下流に向かうノード毎に順次その着目ビットの値にしたがって終端点を検索する機能を実現させる
ことを特徴とするプログラム。
【請求項６】
前記振り分ける機能により振り分けられたエントリーデータを一時蓄積する機能を実現させ、
この一時蓄積する機能として、一つのノードに対して複数のエントリーデータが蓄積されたときには、蓄積されたエントリーデータを一つずつ当該ノードにエントリーする機能を実現させる
請求項５記載のプログラム。
【請求項７】
請求項４ないし６のいずれかに記載のプログラムが記録された前記情報処理装置読み取り可能な記録媒体。
【請求項８】
パトリシアツリーを構成するノードのアドレスと、このアドレスに対応するエントリーデータの着目ビット位置に関する情報と、この着目ビット位置に対応するエントリーデータの取り得る値に対する行き先ノードまたは終端点の情報とをパトリシアツリー接続テーブルとして記録し、
前記着目ビット位置は、パトリシアツリーの始点から下流に向かう段毎に順次先頭ビットから１ビットずつ下位ビットに移行し、
前記テーブルにおけるパトリシアツリーの始点から下流に向かうｋ段目までのノード毎に順次その着目ビットの値にしたがってエントリーデータの行き先ノードまたは終端点を第一検索として検索し、
前記テーブルにおける（ｋ＋１）段目以降の複数のサブツリー毎に、そのサブツリーの始点から下流に向かうノード毎に順次その着目ビットの値にしたがってエントリーデータの行き先ノードまたは終端点をそれぞれ第二検索として並行して検索し、
この第二検索による複数の検索結果の中から前記第一検索による検索結果に基づきいずれか一つを最終的な最長一致検索結果として選択する
ことを特徴とする最長一致検索方法。
【請求項９】
パトリシアツリーを構成するノードのアドレスと、このアドレスに対応するエントリーデータの着目ビット位置に関する情報と、この着目ビット位置に対応するエントリーデータの取り得る値に対する行き先ノードまたは終端点の情報とをパトリシアツリー接続テーブルとして記録し、
前記着目ビット位置は、パトリシアツリーの始点から下流に向かう段毎に順次先頭ビットから１ビットずつ下位ビットに移行し、
前記テーブルにおけるパトリシアツリーの始点から下流に向かうｋ段目までのノード毎に順次その着目ビットの値にしたがってエントリーデータの行き先ノードまたは終端点を検索する第三検索を複数のエントリーデータについて並行に行い、
前記テーブルにおける（ｋ＋１）段目以降の複数のサブツリー毎に、そのサブツリーの始点から下流に向かうノード毎に順次その着目ビットの値にしたがってエントリーデータの行き先ノードまたは終端点をそれぞれ第四検索として並行して検索し、
前記第三検索による検索結果に基づき前記第三検索により出力されるエントリーデータをその行き先ノードに振り分けあるいは前記第三検索により検索された終端点を最長一致検索結果出力に振り分け、
前記第四検索では、この振り分けにより行き先ノードに振り分けられたエントリーデータについて前記サブツリーの始点から下流に向かうノード毎に順次その着目ビットの値にしたがって終端点を検索する
ことを特徴とする最長一致検索方法。
【請求項１０】
前記振り分けにより振り分けられたエントリーデータを一時蓄積し、一つのノードに対して複数のエントリーデータが蓄積されたときには、蓄積されたエントリーデータを一つずつ当該ノードにエントリーする請求項９記載の最長一致検索方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、パトリシアツリーを用いたデータ検索に利用する。特に、ルーティングテーブル検索システムに利用するに適する。
【０００２】
【従来の技術】
従来のルーティングテーブル検索システム等に用いられるパトリシアツリーの構成を図９に示す。パトリシアツリーを用いた最長一致検索は、エントリーデータの数字のうち、できるだけ長いビットが一致するものを検索し、その条件で次のルータ（ＮＨＲ）向けの出力ポートやその他の優先制御等を行う。それらＮＨＲ等の情報は図１０のメモリに格納されている。
【０００３】
図９の例ではエントリーデータのうち、例えば０００１であれば＃ａ４というアドレス情報を格納したメモリの＃ａ４の内容を読み４番ポートへ出力する。一方、エントリーデータで００１０の場合は、上から同様にツリーを検索し、１ビット目が０、２ビット目が０、３ビット目が１で、終端点を見つけ＃ａ２という値を得て、ＮＨＲは２となる。
【０００４】
従来、パトリシアツリーを用いた検索方法の実現例としては、ＣＡＭ（連想メモリ）を用いたものがある。図１１に示すように、ＣＡＭは、格納されているデータの上位（上の方のアドレス）が優先で、上からサーチして、一致した場所で止まり、その内容を読出すものである。
【０００５】
【発明が解決しようとする課題】
このように、ＣＡＭによりパトリシアツリーを用いた検索方法を実現して、先に説明した最長一致検索を行うことができるが、ＣＡＭの容量には限界があり、大規模にはできない。また、原理的にアドレスを同時に多く探すので、非常に大きな消費電力を要し、かつ高価であるため、経済的ではない。
【０００６】
本発明は、このような背景に行われたものであって、大規模なパトリシアツリーを用いた検索方法を高速かつ経済的に実現することができる最長一致検索回路および方法およびプログラムおよび記録媒体を提供することを目的とする。
【０００７】
【課題を解決するための手段】
本発明は、パトリシアツリーの構造をＲＡＭ等のメモリを用いたテーブルに記録できる形に置き換えることを第一の特徴とする。
【０００８】
すなわち、パトリシアツリーを構成するノードのアドレスと、このアドレスに対応するエントリーデータの着目ビット位置に関する情報と、この着目ビット位置に対応するエントリーデータの取り得る値に対する行き先ノードまたは終端点の情報とをパトリシアツリー接続テーブルとして記録することを特徴とする。前記着目ビット位置は、パトリシアツリーの始点から下流に向かう段毎に順次先頭ビットから１ビットずつ下位ビットに移行する。これにより、大規模なパトリシアツリーであってもＲＡＭ等の安価なメモリを用いて記録することができるので経済的である。
【０００９】
このようにＲＡＭ等のメモリを用いたパトリシアツリー接続テーブルを用いて最長一致検索を行うための構成を本発明の第二の特徴とする。本発明では、前記テーブルにおけるパトリシアツリーの始点から下流に向かうノード毎に順次その着目ビットの値にしたがってエントリーデータの行き先ノードまたは終端点を検索するので、ツリー構造の末端まで到達する以前に終端点にヒットすれば、その時点で検索を終了することができるため、最長一致検索を高速に行うことができることを特徴とする。
【００１０】
すなわち、本発明の第一の観点は、パトリシアツリーを構成するノードのアドレスと、このアドレスに対応するエントリーデータの着目ビット位置に関する情報と、この着目ビット位置に対応するエントリーデータの取り得る値に対する行き先ノードまたは終端点の情報とが記録されたパトリシアツリー接続テーブルを備え、前記着目ビット位置は、パトリシアツリーの始点から下流に向かう段毎に順次先頭ビットから１ビットずつ下位ビットに移行し、前記テーブルにおけるパトリシアツリーの始点から下流に向かうノード毎に順次その着目ビットの値にしたがってエントリーデータの行き先ノードまたは終端点を検索する手段を備えたことを特徴とする最長一致検索回路である。
【００１１】
さらに、高速化を図る構成として、前記テーブルにおけるパトリシアツリーの始点から下流に向かうノードの着目ビット毎にエントリーデータの行き先ノードまたは終端点をそれぞれ並行して検索する手段を複数備え、この検索する手段は、自己の検索結果が終端点を示すときにはその検索結果をエントリーデータの最長一致検索結果として出力し、自己の検索結果が次段のノードのアドレスを示すときには、エントリーデータを着目ビット位置が自己よりも一つ下位の次段の検索する手段に引き渡す手段を備えることもできる。
【００１２】
これによれば、パトリシアツリーの各段に相当する部分が並列処理を行っているので、一つのエントリーデータの検索結果が出るまで次のエントリーデータのエントリーを待つことなく、連続的に複数のエントリーデータをエントリーさせることができるため、高速処理を行うことができる。
【００１３】
他の高速化を図る構成として、前記テーブルにおけるパトリシアツリーの始点から下流に向かうｋ（ｋは自然数）段目までのノード毎に順次その着目ビットの値にしたがってエントリーデータの行き先ノードまたは終端点を検索する第一検索手段と、前記テーブルにおける（ｋ＋１）段目以降の複数のサブツリー毎に、そのサブツリーの始点から下流に向かうノード毎に順次その着目ビットの値にしたがってエントリーデータの行き先ノードまたは終端点をそれぞれ並行して検索する複数の第二検索手段と、この第二検索手段の複数の検索結果の中から前記第一検索手段の検索結果に基づきいずれか一つを最終的な最長一致検索結果として選択する手段とを備えることもできる。
【００１４】
これによれば、パトリシアツリーを適当なところから上下に分割し、上部分は上部分で最長一致検索を実行し、下部分は下部分で最長一致検索を実行する。このとき、上部分は、パトリシアツリーの始点から検索を開始するので、エントリーデータに対する検索結果は一つに定まるが、下部分は、複数のサブツリーに分かれており、それぞれのサブツリー毎に検索を開始するので、エントリーデータに対する検索結果も複数存在する。このようにして上部分と下部分とでそれぞれ検索結果が定まった時点で、上部分の検索結果に基づき下部分の複数の検索結果のいずれか一つを最終的な検索結果として選択する。このようにして、一つのパトリシアツリーを上下に分割し、並列処理を行うことができるので、検索時間を高速化することができる。
【００１５】
他の高速化を図る構成として、前記テーブルにおけるパトリシアツリーの始点から下流に向かうｋ段目までのノード毎に順次その着目ビットの値にしたがって複数のエントリーデータの行き先ノードまたは終端点を並行して検索する複数の第三検索手段が設けられ、前記テーブルにおける（ｋ＋１）段目以降の複数のサブツリー毎に、そのサブツリーの始点から下流に向かうノード毎に順次その着目ビットの値にしたがってエントリーデータの行き先ノードまたは終端点をそれぞれ並行して検索する複数の第四検索手段が設けられ、複数の前記第三検索手段の検索結果に基づき前記第三検索手段から出力されるエントリーデータをその行き先ノードに振り分けるあるいは前記第三検索手段により検索された終端点を最長一致検索結果出力に振り分ける手段が設けられ、前記第四検索手段は、この振り分ける手段により振り分けられたエントリーデータについて前記サブツリーの始点から下流に向かうノード毎に順次その着目ビットの値にしたがって終端点を検索する手段を備えることもできる。
【００１６】
これは、複数のパトリシアツリーを用いて同時に複数のエントリーデータを並列処理することにより高速化を図るという発想に基づく構成であるが、本発明では、パトリシアツリーを適当なところから上下に分割し、上部分は複製を複数用意するが、下部分は一つのツリーを共用することにより、メモリ量を低く抑えることを特徴とする。すなわち、複数の上部分で複数のエントリーデータを並列処理し、それぞれの検索結果が出た時点で、エントリーデータを一つの下部分のそれぞれの行き先ノードに振り分ける。このとき、下部分の同じノードに複数のエントリーデータがほぼ同時に振り分けられる場合を想定し、前記振り分ける手段により振り分けられたエントリーデータを一時蓄積する手段が設けられ、この一時蓄積する手段は、一つのノードに対して複数のエントリーデータが蓄積されたときには、蓄積されたエントリーデータを一つずつ当該ノードにエントリーする手段を備えることが望ましい。
【００１７】
これにより、複数のパトリシアツリーの全体を用意する場合と比較して低いメモリ量により複数のエントリーデータを並列処理し、最長一致検索を高速に行うことができる。
【００１８】
本発明の第二の観点は、情報処理装置にインストールすることにより、その情報処理装置に、最長一致検索回路に相応する機能として、パトリシアツリーを構成するノードのアドレスと、このアドレスに対応するエントリーデータの着目ビット位置に関する情報と、この着目ビット位置に対応するエントリーデータの取り得る値に対する行き先ノードまたは終端点の情報とが記録されたパトリシアツリー接続テーブルに相応する機能を実現させ、前記着目ビット位置は、パトリシアツリーの始点から下流に向かう段毎に順次先頭ビットから１ビットずつ下位ビットに移行し、前記テーブルにおけるパトリシアツリーの始点から下流に向かうノード毎に順次その着目ビットの値にしたがってエントリーデータの行き先ノードまたは終端点を検索する機能を実現させることを特徴とするプログラムである。
【００１９】
あるいは、前記テーブルにおけるパトリシアツリーの始点から下流に向かうノードの着目ビット毎にエントリーデータの行き先ノードまたは終端点をそれぞれ並行して検索する機能を複数実現させ、この検索する機能として、自己の検索結果が終端点を示すときにはその検索結果をエントリーデータの最長一致検索結果として出力し、自己の検索結果が次段のノードのアドレスを示すときには、エントリーデータを着目ビット位置が自己よりも一つ下位の次段の検索する手段に引き渡す機能を実現させることを特徴とするプログラムである。
【００２０】
あるいは、前記テーブルにおけるパトリシアツリーの始点から下流に向かうｋ段目までのノード毎に順次その着目ビットの値にしたがってエントリーデータの行き先ノードまたは終端点を検索する第一検索機能と、前記テーブルにおける（ｋ＋１）段目以降の複数のサブツリー毎に、そのサブツリーの始点から下流に向かうノード毎に順次その着目ビットの値にしたがってエントリーデータの行き先ノードまたは終端点をそれぞれ並行して検索する複数の第二検索機能と、この第二検索機能の複数の検索結果の中から前記第一検索機能の検索結果に基づきいずれか一つを最終的な最長一致検索結果として選択する機能とを実現させることを特徴とするプログラムである。
【００２１】
あるいは、前記テーブルにおけるパトリシアツリーの始点から下流に向かうｋ段目までのノード毎に順次その着目ビットの値にしたがって複数のエントリーデータの行き先ノードまたは終端点を並行して検索する複数の第三検索機能を実現させ、前記テーブルにおける（ｋ＋１）段目以降の複数のサブツリー毎に、そのサブツリーの始点から下流に向かうノード毎に順次その着目ビットの値にしたがってエントリーデータの行き先ノードまたは終端点をそれぞれ並行して検索する複数の第四検索機能を実現させ、複数の前記第三検索機能の検索結果に基づき前記第三検索機能から出力されるエントリーデータをその行き先ノードに振り分けるあるいは前記第三検索機能により検索された終端点を最長一致検索結果出力に振り分ける機能を実現させ、前記第四検索機能として、この振り分ける機能により振り分けられたエントリーデータについて前記サブツリーの始点から下流に向かうノード毎に順次その着目ビットの値にしたがって終端点を検索する機能を実現させることを特徴とするプログラムである。
【００２２】
さらに、前記振り分ける機能により振り分けられたエントリーデータを一時蓄積する機能を実現させ、この一時蓄積する機能として、一つのノードに対して複数のエントリーデータが蓄積されたときには、蓄積されたエントリーデータを一つずつ当該ノードにエントリーする機能を実現させることが望ましい。
【００２３】
本発明の第三の観点は、本発明のプログラムが記録された前記情報処理装置読み取り可能な記録媒体である。本発明のプログラムは本発明の記録媒体に記録されることにより、前記情報処理装置は、この記録媒体を用いて本発明のプログラムをインストールすることができる。あるいは、本発明のプログラムを保持するサーバからネットワークを介して直接前記情報処理装置に本発明のプログラムをインストールすることもできる。
【００２４】
これにより、コンピュータ装置等の情報処理装置により、大規模なパトリシアツリーを用いた検索方法を高速かつ経済的に実現することができる最長一致検索回路を実現することができる。
【００２５】
本発明の第四の観点は、パトリシアツリーを構成するノードのアドレスと、このアドレスに対応するエントリーデータの着目ビット位置に関する情報と、この着目ビット位置に対応するエントリーデータの取り得る値に対する行き先ノードまたは終端点の情報とをパトリシアツリー接続テーブルとして記録し、前記着目ビット位置は、パトリシアツリーの始点から下流に向かう段毎に順次先頭ビットから１ビットずつ下位ビットに移行し、前記テーブルにおけるパトリシアツリーの始点から下流に向かうノード毎に順次その着目ビットの値にしたがってエントリーデータの行き先ノードまたは終端点を検索することを特徴とする最長一致検索方法である。
【００２６】
あるいは、前記テーブルにおけるパトリシアツリーの始点から下流に向かうノードの着目ビット毎にエントリーデータの行き先ノードまたは終端点をそれぞれ並行して検索し、このときに、検索結果が終端点を示すときにはその検索結果をエントリーデータの最長一致検索結果として出力し、検索結果が次段のノードのアドレスを示すときには、エントリーデータを着目ビット位置が当該検索よりも一つ下位の検索にかけることを特徴とする最長一致検索方法である。
【００２７】
あるいは、前記テーブルにおけるパトリシアツリーの始点から下流に向かうｋ段目までのノード毎に順次その着目ビットの値にしたがってエントリーデータの行き先ノードまたは終端点を第一検索として検索し、前記テーブルにおける（ｋ＋１）段目以降の複数のサブツリー毎に、そのサブツリーの始点から下流に向かうノード毎に順次その着目ビットの値にしたがってエントリーデータの行き先ノードまたは終端点をそれぞれ第二検索として並行して検索し、この第二検索による複数の検索結果の中から前記第一検索による検索結果に基づきいずれか一つを最終的な最長一致検索結果として選択することを特徴とする最長一致検索方法である。
【００２８】
あるいは、前記テーブルにおけるパトリシアツリーの始点から下流に向かうｋ段目までのノード毎に順次その着目ビットの値にしたがってエントリーデータの行き先ノードまたは終端点を検索する第三検索を複数のエントリーデータについて並行に行い、前記テーブルにおける（ｋ＋１）段目以降の複数のサブツリー毎に、そのサブツリーの始点から下流に向かうノード毎に順次その着目ビットの値にしたがってエントリーデータの行き先ノードまたは終端点をそれぞれ第四検索として並行して検索し、前記第三検索による検索結果に基づき前記第三検索により出力されるエントリーデータをその行き先ノードに振り分けるあるいは前記第三検索により検索された終端点を最長一致検索結果出力に振り分け、前記第四検索では、この振り分けにより振り分けられたエントリーデータについて前記サブツリーの始点から下流に向かうノード毎に順次その着目ビットの値にしたがって終端点を検索することを特徴とする最長一致検索方法である。
【００２９】
このとき、前記振り分けにより振り分けられたエントリーデータを一時蓄積し、一つのノードに対して複数のエントリーデータが蓄積されたときには、蓄積されたエントリーデータを一つずつ当該ノードにエントリーすることが望ましい。
【００３０】
【発明の実施の形態】
（第一実施例）
本発明第一実施例を図１ないし図４を参照して説明する。図１は第一実施例の構成図である。図２は本実施例で用いるパトリシアツリーを示す図である。図３は本実施例で用いるパトリシアツリー接続テーブルを示す図である。図４は第一実施例の最長一致検索回路の動作を示すフローチャートである。
【００３１】
第一実施例は、図３に示すように、パトリシアツリーを構成するノードのアドレス（ノードアドレス）と、このアドレスに対応するエントリーデータの着目ビット位置に関する情報（マスク）と、この着目ビット位置に対応するエントリーデータの取り得る値（“０”、“１”）に対する行き先ノードまたは終端点の情報とが記録されたパトリシアツリー接続テーブルＴを図１に示すテーブル部Ｍに備え、前記着目ビット位置は、パトリシアツリーの始点から下流に向かう段毎に順次先頭ビットから１ビットずつ下位ビットに移行し、パトリシアツリー接続テーブルＴにおけるパトリシアツリーの始点から下流に向かうノード毎に順次その着目ビットの値にしたがってエントリーデータの行き先ノードまたは終端点を検索する処理部Ｐを備えたことを特徴とする最長一致検索回路である。
【００３２】
すなわち、第一実施例の最長一致検索回路は、ＲＡＭから構成されたテーブル部Ｍと、処理部Ｐとから構成されている。理解をしやすくするために、図２に従来例と同じパトリシアツリーにノードアドレスを〇数字で記載する。アドレス情報テーブルは従来例の図１０と共通である。図３に図２のパトリシアツリーの検索データを示すパトリシアツリー接続テーブルＴの内容を示す。また、図４は、処理部Ｐの動作をフローチャートで示してある。
【００３３】
図１〜図４を参照して第一実施例の最長一致検索回路の動作を説明する。サーチするエントリーデータは、処理部Ｐで上位ビットからマスクがかけられ、パトリシアツリーのデータ（接続および結果）のテーブルであるパトリシアツリー接続テーブルＴから、データを一つ取り出し、そこで、マスクされた残りのデータが“０”か“１”で、次のツリーの接続へ飛ぶ。終端点にあたるところでは、アドレス情報を格納したメモリのアドレスが呼び出され、そのパトリシアツリー接続テーブルＴをさらに読むことによりＮＨＲのポートを読み出せる。もちろん、このＮＨＲ自身を終端点に格納することも可能である。例えは、図３の＃ａ１の代わりにＮＨＲ７を格納してもよい。
【００３４】
図４のフローチャートを説明する。スタートは、ノードアドレス＃０であり、これはパトリシアツリー（図２）の一番上のツリーのブランチに当たる。マスク処理は、＿＊＊＊であるので、エントリーデータの１ビット目のデータで“０”もしくは、“１”を判断して、“０”ならばノードアドレス１、“１”ならばノードアドレス２が次のノードアドレスであり、（ｎｉにあたる）そのアドレスへ飛ぶため、再びノードアドレス１もしくはノードアドレス２のアドレスのデータをリードする。
【００３５】
このリードしたデータは、再びマスク処理され、２ビット目のデータを基に、同様に“０”、“１”の判断で、次のツリーの接続データへ飛ぶ。“０”、“１”のデータが終端点ならば、＃ａｉつまりＮＨＲが格納されているメモリのアドレスが出る。
【００３６】
このような構成であるため、ＲＡＭにより構成されるパトリシアツリーの格納データは、極めて大規模でかつ、拡張性が高い。またＣＡＭを必要としていないので、低消費電力でかつ経済的である。
【００３７】
（第二実施例）
本発明第二実施例を図５を参照して説明する。第二実施例は、図５に示すように、パトリシアツリー接続テーブルＴにおけるパトリシアツリーの始点から下流に向かうノードの着目ビット毎にエントリーデータの行き先ノードまたは終端点をそれぞれ並行して検索する処理部Ｐ１〜Ｐ４を複数備え、この処理部Ｐｉ（ｉは１〜４のいずれか）は、自己の検索結果が終端点を示すときにはその検索結果をエントリーデータの最長一致検索結果として出力し、自己の検索結果が次段のノードのアドレスを示すときには、エントリーデータを着目ビット位置が自己よりも一つ下位の次段の処理部Ｐ（ｉ＋１）に引き渡すことを特徴とする最長一致検索回路である。図５ではテーブル部Ｍの図示は省略したが、処理部Ｐ１〜Ｐ４はテーブル部Ｍを参照して処理を実行する。
【００３８】
第一実施例では、１つのエントリーデータを最長一致させるのに４クロック必要としている。一方、第二実施例では、マスクビット毎にパイプライン化して、１ビット処理して、終端点にヒットしたら結果部Ｒへ、さらに下位ビットをサーチする必要があれば、次ノードアドレスと一緒に次段のパイプラインにデータを引き渡す。次段へデータを引き渡したら、次のエントリーデータが上位から挿入され、パンプライン処理を行う。
【００３９】
すなわち、パトリシアツリーの各段に相当する部分が並列処理を行っているので、一つのエントリーデータの検索結果が出るまで次のエントリーデータのエントリーを待つことなく、連続的に複数のエントリーデータをエントリーさせることができるため、高速処理を行うことができる。
【００４０】
（第三実施例）
本発明第三実施例を図６および図７を参照して説明する。第三実施例は、図６および図７に示すように、パトリシアツリー接続テーブルＴにおけるパトリシアツリーの始点から下流に向かう２段目までのノード毎に順次その着目ビットの値にしたがってエントリーデータの行き先ノードまたは終端点を検索する処理部Ｐ１１と、パトリシアツリー接続テーブルＴにおける３段目以降の複数のサブツリー＃１〜＃３毎に、そのサブツリー＃１〜＃３の始点から下流に向かうノード毎に順次その着目ビットの値にしたがってエントリーデータの行き先ノードまたは終端点をそれぞれ並行して検索する複数の処理部Ｐ２１、Ｐ２２、Ｐ２３と、このＰ２１、Ｐ２２、Ｐ２３の複数の検索結果の中から処理部Ｐ１１の検索結果に基づきいずれか一つを最終的な最長一致検索結果として選択する結果部Ｒ１〜Ｒ３および結果処理部ＲＣとを備えたことを特徴とする最長一致検索回路である。図６ではテーブル部Ｍの図示は省略したが、処理部Ｐ１１、Ｐ２１〜Ｐ２３はテーブル部Ｍを参照して処理を実行する。
【００４１】
図６の構成では、３〜４ｂｉｔ目のエントリーデータの検索を先行的に行い、１〜２ｂｉｔ目の検索結果から、３〜４ｂｉｔ目の答えの１つを選ぶ。もしくは、１〜２ｂｉｔで終端した処理を行うものである。本図を用いて動作を説明する。
【００４２】
エントリーデータは、１〜２ｂｉｔ目のサーチ処理および３〜４ｂｉｔ目のサーチ処理をパラレルに行っている。３〜４ｂｉｔ目は、上位２ビットの値は不明であるが、下位２ビットで、例では、３並列にサーチしている。結果はノードアドレス３、４、５それぞれで出てくるが上位２ｂｉｔの結果でノードのノードアドレス３、４、５のいずれに飛んだ、もしくは、２ｂｉｔでみつかったことにより、結果処理部ＲＣで、適当なものが選択される。このことにより、パイプラインがビット数だけかかり、高速処理はできるが遅延時間が大きい第二実施例と比べ、より高速に処理できる。
【００４３】
すなわち、パトリシアツリーを適当なところから上下に分割し、上部分は上部分で最長一致検索を実行し、下部分は下部分で最長一致検索を実行する。このとき、上部分は、パトリシアツリーの始点から検索を開始するので、エントリーデータに対する検索結果は一つに定まるが、下部分は、複数のサブツリー＃１〜＃３に分かれており、それぞれのサブツリー＃１〜＃３毎に検索を開始するので、エントリーデータに対する検索結果も複数存在する。このようにして上部分と下部分とでそれぞれ検索結果が定まった時点で、上部分の検索結果に基づき下部分の複数の検索結果のいずれか一つを最終的な検索結果として選択する。このようにして、一つのパトリシアツリーを上下に分割し、並列処理を行うことができるので、検索時間を高速化することができる。
【００４４】
（第四実施例）
本発明第四実施例を図８を参照して説明する。第四実施例は、図８に示すように、パトリシアツリー接続テーブルＴにおけるパトリシアツリーの始点から下流に向かう２段目までのノード毎に順次その着目ビットの値にしたがって複数のエントリーデータの行き先ノードまたは終端点を並行して検索する複数の処理部Ｐ３１〜Ｐ３３が設けられ、パトリシアツリー接続テーブルＴにおける３段目以降の複数のサブツリー毎に、そのサブツリーの始点から下流に向かうノード毎に順次その着目ビットの値にしたがってエントリーデータの行き先ノードまたは終端点をそれぞれ並行して検索する複数の処理部Ｐ４１〜Ｐ４３が設けられ、複数の処理部Ｐ３１〜Ｐ３３の検索結果に基づき処理部Ｐ３１〜Ｐ３３から出力されるエントリーデータをその行き先ノードに振り分けるあるいは処理部Ｐ３１〜Ｐ３３により検索された終端点を最長一致検索結果出力に振り分ける振り分け部Ｄが設けられ、処理部Ｐ４１〜Ｐ４３は、この振り分け部Ｄにより振り分けられたエントリーデータについて前記サブツリーの始点から下流に向かうノード毎に順次その着目ビットの値にしたがって終端点を検索することを特徴とする最長一致検索回路である。
【００４５】
また、振り分け部Ｄにより振り分けられたエントリーデータを一時蓄積する待ち合わせ部Ｂ１〜Ｂ３が設けられ、この待ち合わせ部Ｂ１〜Ｂ３は、一つのノードに対して複数のエントリーデータが蓄積されたときには、蓄積されたエントリーデータを一つずつ当該ノードにエントリーする。
【００４６】
第四実施例では、上位１〜２ｂｉｔは、３つのエントリーデータをほぼ同時に並列に処理する。その結果が３〜４ｂｉｔのノードでノードアドレス３、４、５のいずれかになる場合と、終了する場合があるのは、第三実施例と同様である。ノードアドレス３等に複数のデータが競合するので、待ち合わせ部Ｂ１〜Ｂ３を配置してある。このような構成のため、３つのエントリーデータを同時に処理でき、高速性が向上する。
【００４７】
すなわち、第四実施例は、複数のパトリシアツリーを用いて同時に複数のエントリーデータを並列処理することにより高速化を図るという発想に基づく構成であるが、第四実施例では、パトリシアツリーを適当なところから上下に分割し、上部分は複製を複数用意するが、下部分は一つのツリーを共用することにより、メモリ量を低く抑えることを特徴とする。すなわち、複数の上部分で複数のエントリーデータを並列処理し、それぞれの検索結果が出た時点で、エントリーデータを一つの下部分のそれぞれの行き先ノードに振り分ける。このとき、下部分の同じノードに複数のエントリーデータがほぼ同時に振り分けられる場合を想定し、振り分け部Ｄにより振り分けられたエントリーデータを一時蓄積する待ち合わせ部Ｂ１〜Ｂ３が設けられ、この待ち合わせ部Ｂ１〜Ｂ３は、一つのノードに対して複数のエントリーデータが蓄積されたときには、蓄積されたエントリーデータを一つずつ当該ノードにエントリーする。
【００４８】
これにより、複数のパトリシアツリーの全体を用意する場合と比較して低いメモリ量により複数のエントリーデータを並列処理し、最長一致検索を高速に行うことができる。
【００４９】
（第五実施例）
本実施例の最長一致検索回路は、情報処理装置としてのコンピュータ装置により実現することができる。すなわち、コンピュータ装置にインストールすることにより、そのコンピュータ装置に、図１に示す第一実施例の最長一致検索回路に相応する機能として、パトリシアツリーを構成するノードのアドレスと、このアドレスに対応するエントリーデータの着目ビット位置に関する情報と、この着目ビット位置に対応するエントリーデータの取り得る値に対する行き先ノードまたは終端点の情報とが記録されたパトリシアツリー接続テーブルＴに相応する機能を実現させ、前記着目ビット位置は、パトリシアツリーの始点から下流に向かう段毎に順次先頭ビットから１ビットずつ下位ビットに移行し、パトリシアツリー接続テーブルＴにおけるパトリシアツリーの始点から下流に向かうノード毎に順次その着目ビットの値にしたがってエントリーデータの行き先ノードまたは終端点を検索する処理部Ｐに相応する機能を実現させるプログラムをコンピュータ装置にインストールすることにより、そのコンピュータ装置を第一実施例の最長一致検索回路に相応する回路とすることができる。
【００５０】
あるいは、コンピュータ装置にインストールすることにより、そのコンピュータ装置に、図５に示す第二実施例の最長一致検索回路に相応する機能として、パトリシアツリー接続テーブルＴにおけるパトリシアツリーの始点から下流に向かうノードの着目ビット毎にエントリーデータの行き先ノードまたは終端点をそれぞれ並行して検索する処理部Ｐ１〜Ｐ４に相応する機能を複数実現させ、この検索する機能として、自己の検索結果が終端点を示すときにはその検索結果をエントリーデータの最長一致検索結果として出力し、自己の検索結果が次段のノードのアドレスを示すときには、エントリーデータを着目ビット位置が自己よりも一つ下位の次段の検索する手段に引き渡す機能を実現させるプログラムをコンピュータ装置にインストールすることにより、そのコンピュータ装置を第二実施例の最長一致検索回路に相応する回路とすることができる。
【００５１】
あるいは、コンピュータ装置にインストールすることにより、そのコンピュータ装置に、図６に示す第三実施例の最長一致検索回路に相応する機能として、パトリシアツリー接続テーブルＴにおけるパトリシアツリーの始点から下流に向かうｋ段目までのノード毎に順次その着目ビットの値にしたがってエントリーデータの行き先ノードまたは終端点を検索する処理部Ｐ１１に相応する第一検索機能と、パトリシアツリー接続テーブルＴにおける（ｋ＋１）段目以降の複数のサブツリー毎に、そのサブツリーの始点から下流に向かうノード毎に順次その着目ビットの値にしたがってエントリーデータの行き先ノードまたは終端点をそれぞれ並行して検索する複数の処理部Ｐ２１〜Ｐ２３に相応する第二検索機能と、この第二検索機能の複数の検索結果の中から前記第一検索機能の検索結果に基づきいずれか一つを最終的な最長一致検索結果として選択する結果処理部ＲＣに相応する機能とを実現させるプログラムをコンピュータ装置にインストールすることにより、そのコンピュータ装置を第三実施例の最長一致検索回路に相応する回路とすることができる。
【００５２】
あるいは、コンピュータ装置にインストールすることにより、そのコンピュータ装置に、図８に示す第四実施例の最長一致検索回路に相応する機能として、パトリシアツリー接続テーブルＴにおけるパトリシアツリーの始点から下流に向かうｋ段目までのノード毎に順次その着目ビットの値にしたがって複数のエントリーデータの行き先ノードまたは終端点を並行して検索する複数の処理部Ｐ３１〜Ｐ３３に相応する第一検索機能を実現させ、パトリシアツリー接続テーブルＴにおける（ｋ＋１）段目以降の複数のサブツリー毎に、そのサブツリーの始点から下流に向かうノード毎に順次その着目ビットの値にしたがってエントリーデータの行き先ノードまたは終端点をそれぞれ並行して検索する複数の処理部Ｐ４１〜Ｐ４３に相応する第二検索機能を実現させ、複数の前記第一検索機能の検索結果に基づき前記第一検索機能から出力されるエントリーデータをその行き先ノードに振り分けるあるいは前記第一検索機能により検索された終端点を最長一致検索結果出力に振り分ける振り分け部Ｄに相応する機能を実現させ、前記第二検索機能として、この振り分ける機能により振り分けられたエントリーデータについて前記サブツリーの始点から下流に向かうノード毎に順次その着目ビットの値にしたがって終端点を検索する機能を実現させるプログラムをコンピュータ装置にインストールすることにより、そのコンピュータ装置を第四実施例の最長一致検索回路に相応する回路とすることができる。
【００５３】
さらに、第四実施例では、コンピュータ装置にインストールすることにより、そのコンピュータ装置に、振り分け部Ｄに相応する機能により振り分けられたエントリーデータを一時蓄積する待ち合わせ部Ｂ１〜Ｂ３に相応する機能を実現させ、この一時蓄積する機能として、一つのノードに対して複数のエントリーデータが蓄積されたときには、蓄積されたエントリーデータを一つずつ当該ノードにエントリーする機能を実現させる。
【００５４】
本実施例のプログラムは本実施例の記録媒体に記録されることにより、コンピュータ装置は、この記録媒体を用いて本実施例のプログラムをインストールすることができる。あるいは、本実施例のプログラムを保持するサーバからネットワークを介して直接コンピュータ装置に本実施例のプログラムをインストールすることもできる。
【００５５】
これにより、コンピュータ装置により、大規模なパトリシアツリーを用いた検索方法を高速かつ経済的に実現することができる最長一致検索回路を実現することができる。
【００５６】
【発明の効果】
以上説明したように、本発明によれば、大規模なパトリシアツリーを用いた検索方法を高速かつ経済的に実現することができる。
【図面の簡単な説明】
【図１】第一実施例の最長一致検索回路の構成図。
【図２】本実施例で用いるパトリシアツリーを示す図。
【図３】本実施例で用いるパトリシアツリー接続テーブルを示す図。
【図４】第一実施例の最長一致検索回路の動作を示すフローチャート。
【図５】第二実施例の最長一致検索回路の構成図。
【図６】第三実施例の最長一致検索回路の構成図。
【図７】パトリシアツリーを上下に分割した状態を示す図。
【図８】第四実施例の最長一致検索回路の構成図。
【図９】パトリシアツリーの例を示す図。
【図１０】アドレステーブルの例を示す図。
【図１１】ＣＡＭの構成を示す図。
【符号の説明】
Ｂ１〜Ｂ３  待ち合わせ部
Ｄ  振り分け部
Ｍ  テーブル部
Ｔ  パトリシアツリー接続テーブル
Ｐ、Ｐ１〜Ｐ４、Ｐ１１、Ｐ２１〜Ｐ２３、Ｐ３１〜Ｐ３３、Ｐ４１〜Ｐ４３  処理部
Ｒ、Ｒ１〜Ｒ３  結果部
ＲＣ  結果処理部
＃１〜＃３  サブツリー
【図１】
0003691018.tif 000002
【図２】
0003691018.tif 000003
【図３】
0003691018.tif 000004
【図４】
0003691018.tif 000005
【図５】
0003691018.tif 000006
【図６】
0003691018.tif 000007
【図７】
0003691018.tif 000008
【図８】
0003691018.tif 000009
【図９】
0003691018.tif 000010
【図１０】
0003691018.tif 000011
【図１１】
0003691018.tif 000012