(57)【要約】【課題】パケット中の任意の比較ワード数のデータ検索に対して同じ回路を用いることが出来、安価で高速なパケット情報検索装置を実現する。【解決手段】パケットを格納するパケット格納ＲＡＭ１−１と、２分探索木を格納する２分探索木格納ＲＡＭ１−２と、パケット格納ＲＡＭ用の第１のポインタ回路１−３と、２分探索木格納ＲＡＭ用の第２のポインタ回路１−５と、パケット格納ＲＡＭのリードデータを格納する比較ワードレジスタ１−８と、２分探索木格納ＲＡＭから読み出したデータを格納する被比較ワードレジスタ１−９と、比較器１−１０と、２分探索木格納ＲＡＭ用のポインタを選択するセレクタ１−１２と、検索データのワード数を参照して装置の逐次動作を制御するシーケンス制御部１−１３とを備える。【選択図】  図１
2004320280.tif 000002
【特許請求の範囲】
【請求項１】
パケット中のＩＰアドレス等の情報を検索キーとして予め構築された２分探索木を検索するパケット情報検索装置において、
個々のパケットデータを格納するパケット格納ＲＡＭと、
ＩＰアドレス等検索すべきデータが登録されたノードで構成される２分探索木を格納する２分探索木格納ＲＡＭと、
前記パケット格納ＲＡＭ中のデータ格納場所を示すポインタレジスタとその制御回路からなる第１のポインタ回路と、
前記２分探索木格納ＲＡＭ中のデータ格納場所を示す複数のポインタレジスタから構成されるポインタレジスタファイルとその制御回路からなる第２のポインタ回路と、
前記パケット格納ＲＡＭから読み出したデータを格納する比較ワードレジスタと、
前記２分探索木格納ＲＡＭから読み出したデータを格納する被比較ワードレジスタと、
前記比較ワードレジスタと前記被比較ワードレジスタの内容を比較する比較器と、
前記比較器による比較結果に基づき前記第２のポインタ回路中のポインタレジスタファイルのどれを使って前記２分探索木格納ＲＡＭ中のデータを読み出すかを決めるセレクタと、
検索キーのビット幅が前記比較器のビット幅の何倍であるかを示すワード数を参照して装置の逐次動作を制御するシーケンス制御部とを備えることを特徴とするパケット情報検索装置。
【請求項２】
請求項１に記載のパケット情報検索装置において、
前記第２のポインタ回路の制御回路は、前記２分探索木格納ＲＡＭからの出力に各々一定のオフセット値を加えて前記第２のポインタ回路中のポインタレジスタファイルを構成する各ポインタレジスタに設定する機能と、このポインタレジスタファイル中の一つのポインタレジスタをインクリメントする加算機能とを有し、
前記第１のポインタ回路の制御回路は、この第１のポインタ回路中のポインタレジスタをインクリメントする加算機能を有することを特徴とするパケット情報検索装置。
【請求項３】
パケット中のＩＰアドレス等の情報を検索キーとして予め構築された２分探索木を検索するパケット情報検索装置において、
個々のパケットデータを格納するパケット格納ＲＡＭと、
ＩＰアドレス等検索すべきデータが登録されたノードで構成される２分探索木を格納する２分探索木格納ＲＡＭと、
前記パケット格納ＲＡＭ中のデータ格納場所を示すポインタレジスタとその制御回路からなる第１のポインタ回路と、
前記２分探索木格納ＲＡＭ中のデータ格納場所を示すポインタレジスタとその制御回路からなる第２のポインタ回路と、
前記パケット格納ＲＡＭから読み出したデータを格納する比較ワードレジスタと、
前記２分探索木格納ＲＡＭから読み出したデータを格納する被比較ワードレジスタと、
前記比較ワードレジスタと前記被比較ワードレジスタの内容を比較する比較器と、
２分探索木左子ノードの先頭番地を格納する左子ノードポインタ値レジスタと、
２分探索木右子ノードの先頭番地を格納する右子ノードポインタ値レジスタと、
前記比較器による比較結果に基づき前記左子ノードポインタ値レジスタと前記右子ノードポインタ値レジスタのいずれの値を前記第２のポインタ回路中のポインタレジスタに設定するかを決めるセレクタと、
検索キーのビット幅が前記比較器のビット幅の何倍であるかを示すワード数を参照して装置の逐次動作を制御するシーケンス制御部とを備えることを特徴とするパケット情報検索装置。
【請求項４】
パケット中のＩＰアドレス等の情報を検索キーとして予め構築された２分探索木を検索するパケット情報検索装置において、
個々のパケットデータを格納するパケット格納ＲＡＭと、
ＩＰアドレス等検索すべきデータが登録されたノードで構成される２分探索木を格納する２分探索木格納ＲＡＭと、
前記パケット格納ＲＡＭ中のデータ格納場所を示すポインタレジスタとその制御回路からなる第１のポインタ回路と、
前記２分探索木格納ＲＡＭ中のデータ格納場所を示すポインタレジスタとその制御回路からなる第２のポインタ回路と、
前記パケット格納ＲＡＭから読み出したデータを格納する比較ワードレジスタと、
前記２分探索木格納ＲＡＭから読み出したデータを格納する被比較ワードレジスタと、
前記比較ワードレジスタと前記被比較ワードレジスタの内容を比較する比較器と、
２分探索木左子ノードの先頭番地または２分探索木右子ノードの先頭番地を格納する子ノードポインタ値一時保存レジスタと、
前記比較器による比較結果に基づき前記子ノードポインタ値一時保存レジスタと前記２分探索木格納ＲＡＭから読み出したデータのいずれの値を第２のポインタ回路中のポインタレジスタに設定するかを決めるセレクタと、
検索キーのビット幅が前記比較器のビット幅の何倍であるかを示すワード数を参照して装置の逐次動作を制御するシーケンス制御部とを備えることを特徴とするパケット情報検索装置。
【請求項５】
２分探索木の探索深さをカウントする２分探索木探索深さカウンタを有する請求項１から請求項４までのいずれかに記載のパケット情報検索装置と、
予め探索深さの最大値を設定する最大探索深さレジスタと、
前記２分探索木探索深さカウンタの値と前記最大探索深さレジスタの値を比較する比較器と、
前記比較器による比較の結果、前記２分探索木探索深さカウンタの値が前記最大探索深さレジスタの値よりも大きくなったときにプロセッサに通知する手段とを備えることを特徴とするパケット処理装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、ＩＰ（Ｉｎｔｅｒｎｅｔ  Ｐｒｏｔｏｃｏｌ）通信経路の検索、ＩＰアドレスフィルタ検索、ポート番号検索等、ＩＰパケットの情報を２分探索木で構成された登録テーブルから検索する装置を有するパケット処理システムにかかわり、より詳しくはパケット情報検索装置およびパケット処理装置に関する。
【０００２】
【従来の技術】
ＩＰネットワーク分野におけるパケット処理装置においては、ＩＰアドレス、ポート番号等のパケットヘッダ情報を検索キーとしてテーブル検索する機能が重要である。例えばルータにおけるＩＰアドレス経路検索、パケットアドレスフィルタリング、ポート番号フィルタリング、ＩＰアドレス・ポート番号変換、ＭＡＣアドレス解決等がその代表例である。ルータ等ＩＰネットワークにおける処理は、ソフトウェアで実装する場合と、ハードウェアで実装する場合がある。
【０００３】
従来、ハードウェアで実装するのは、社内ＬＡＮや基幹系ネットワーク用機器等、機能が単純でデータ転送速度が大きく、必ずしも絶対的な低価格化を要求されない業務用途の機器が中心であった。このため、連想メモリ等の比較的高価な部品を使ったり、Ｔｒｉｅアルゴリズムのような特殊なハードウェアが必要になる手法を使ったりしている（例えば、非特許文献１参照。）。一方、家庭用機器の場合は、一つの機器で多機能を実現する必要があることや、あまり大きなデータ転送速度が要求されないことから、ソフトウェアで構成されていた。
【０００４】
ところが、最近、一般家庭のブロードバンド化に伴って高速データ転送が必要となり、高価なプロセッサを使わないと十分なソフトウェア処理速度が得られなくなって来た。しかしながら、業務用途の機器で使われるハードウェアによる処理手法を用いると、特殊な部品が必要であったり、他の処理とのハードウェアの共用性、柔軟性が無く、多機能を要求される家庭用機器に対しては、大幅なコストアップの要因になっていた。このため、最近、高価な部品を使わないハードウェア化を前提とした技術が出始めている（例えば、特許文献１参照。）。特許文献１では、連想メモリのような高価な部品を使用せず、また、Ｔｒｉｅアルゴリズムのような特殊な回路を使用していない。
【０００５】
【特許文献１】
特開２００１−６０９６９号公報（第４−７頁、第１−３図）
【非特許文献１】
ラディア・パールマン、“インターネットコネクションズ第２版”、３５８−３７３項、翔泳社
【０００６】
【発明が解決しようとする課題】
しかしながら、特許文献１の場合、ＩＰアドレスの経路検索に用途を特化しているため、ＩＰｖ６（Ｉｎｔｅｒｎｅｔ  Ｐｒｏｔｏｃｏｌ  Ｖｅｒｓｉｏｎ  ６：アドレス長１２８ビット）のようにＩＰアドレスのビット幅が変わった場合の対処の仕方に関しては記載されていない。さらに、アドレス・ポート変換のようにＩＰアドレスとポート番号を合わせて検索する必要がある場合や、パケットフィルタ等ビット幅が異なる検索キーを用いた検索を行う場合には、同一回路をそのまま適用することが出来ない欠点がある。
【０００７】
このように従来技術では、安価に高性能な検索が出来かつ種々のビット幅の検索に対してそのまま同じ回路を適用出来る検索装置を実現出来なかった。
【０００８】
本発明は、このような事情に鑑みて創作したものであり、これらの課題を解決し、ＩＰｖ４、ＩＰｖ６、アドレス・ポート変換等、任意の比較ワード数のデータ検索に対して同じ回路で対応出来るパケット情報検索装置、パケット処理装置を提供することを目的とする。
【０００９】
【課題を解決するための手段】
上記の課題を解決するために、本発明は次のような手段を講じる。
【００１０】
第１の解決手段として、パケット中のＩＰアドレス等の情報を検索キーとして予め構築された２分探索木を検索するパケット情報検索装置において、本発明は、それぞれ次のような機能を有する複数の構成要素、パケット格納ＲＡＭ、２分探索木格納ＲＡＭ、前記パケット格納ＲＡＭの前段の第１のポインタ回路、前記２分探索木格納ＲＡＭの前段の第２のポインタ回路、前記パケット格納ＲＡＭの後段の比較ワードレジスタ、前記２分探索木格納ＲＡＭの後段の被比較ワードレジスタ、前記比較ワードレジスタおよび前記被比較ワードレジスタの後段の比較器、前記第２のポインタ回路と前記２分探索木格納ＲＡＭとの間にあり前記比較器による比較結果で動作するセレクタおよび全体の制御を行うシーケンス制御部を備えた構成としている。すなわち、前記のパケット格納ＲＡＭは、個々のパケットデータを格納するものであり、前記の２分探索木格納ＲＡＭは、ＩＰアドレス等検索すべきデータが登録されたノードで構成される２分探索木を格納するものである。前記の第１のポインタ回路は、前記パケット格納ＲＡＭ中のデータ格納場所を示すポインタレジスタとその制御回路からなるものであり、前記の第２のポインタ回路は、前記２分探索木格納ＲＡＭ中のデータ格納場所を示す複数のポインタレジスタから構成されるポインタレジスタファイルとその制御回路からなるものである。前記の比較ワードレジスタは、前記パケット格納ＲＡＭから読み出したデータを格納するものであり、前記の被比較ワードレジスタは、前記２分探索木格納ＲＡＭから読み出したデータを格納するものである。前記の比較器は、前記比較ワードレジスタと前記被比較ワードレジスタの内容を比較するものである。前記のセレクタは、前記比較器による比較結果に基づき前記第２のポインタ回路中のポインタレジスタファイルのどれを使って前記２分探索木格納ＲＡＭ中のデータを読み出すかを決めるものである。前記のシーケンス制御部は、検索キーのビット幅が前記比較器のビット幅の何倍であるかを示すワード数を参照して装置の逐次動作を制御するものである。
【００１１】
上記の構成による作用は次のとおりである。第１のポインタ回路のポインタレジスタがパケット格納ＲＡＭの場所を指定すると、その場所のパケットデータが比較ワードレジスタに読み出される。また、第２のポインタ回路のポインタレジスタが２分探索木格納ＲＡＭの場所を指定すると、その場所のデータ（パケットデータに対する比較データ）が被比較ワードレジスタに読み出される。比較器は、比較ワードレジスタのデータと被比較ワードレジスタのデータを比較し、一致不一致の関係や不一致の場合の大小関係を示す比較結果をセレクタとシーケンス制御部に与える。セレクタは、比較結果に基づいて第２のポインタ回路中の対応するポインタレジスタを選択し、２分探索木格納ＲＡＭにつなぐ。上記を繰り返すことにより、２分探索木のノードを順次に辿るようにしてパケットデータを検索する。繰り返しは、シーケンス制御部が管理するワード数の分だけ行われる。
【００１２】
上記の構成によれば、シーケンス制御部でワード数を設定し、設定したワード数に基づいて２分探索木でのパケットデータ探索の繰り返し回数を制御するので、任意の比較ワード数のデータ検索に対して同じ回路を用いることが出来る。したがって、ＩＰｖ４、ＩＰｖ６、アドレス・ポート変換等に一つの回路で対応出来る。また、パケットデータの検索だけではなく、マイコンバスのビット幅やＤＳＰの演算器のビット幅を総合的に考慮し共通化した上で、比較器やデータメモリのビット幅を決定することが可能となり、回路部品の共有化、装置の最適化を可能にする。
【００１３】
上記の構成において好ましい態様として、次のような構成を挙げることができる。すなわち、前記第２のポインタ回路の制御回路が、前記２分探索木格納ＲＡＭからの出力に各々一定のオフセット値を加えて前記第２のポインタ回路中のポインタレジスタファイルを構成する各ポインタレジスタに設定する機能と、このポインタレジスタファイル中の一つのポインタレジスタをインクリメントする加算機能とを有していることである。加えて、前記第１のポインタ回路の制御回路が、この第１のポインタ回路中のポインタレジスタをインクリメントする加算機能を有していることである。
【００１４】
この構成による作用は次のとおりである。２分探索木格納ＲＡＭにおける２分探索木は、ルートノードから左子ノード・右子ノードに分岐し、左子ノードからさらに左子ノード・右子ノードに分岐し、右子ノードからさらに左子ノード・右子ノードに分岐する。ワード単位で現在のノードにおける比較データがパケットデータと不一致のときは前記比較結果が不一致を示し、一致する候補を探索すべく、第２のポインタ回路の制御回路は２分探索木格納ＲＡＭの出力にオフセット値を加えて各ポインタレジスタに設定する。一方、セレクタは、不一致を示す比較結果に応じて左子ノード、右子ノードのいずれかに進むべく、第２のポインタ回路中の対応するポインタレジスタを選択し、２分探索木格納ＲＡＭにつなぐ。上記のサイクルで、比較データがパケットデータと一致するようになる。前記比較結果が一致を示すときは、シーケンス制御部は、次のワード単位の比較に進むべく、第１のポインタ回路および第２のポインタ回路を制御する。このとき、第１のポインタ回路、第２のポインタ回路の制御回路はそれぞれのポインタレジスタをインクリメントする。上記のサイクルを比較ワード数の分だけ繰り返す。以上により、同じ回路を用いて、任意の比較ワード数のデータ検索を効果的に遂行することが可能となる。
【００１５】
第２の解決手段として、本発明によるパケット情報検索装置は、上記第１の解決手段において、第２のポインタ回路について、複数のポインタレジスタから構成されるポインタレジスタファイルとその制御回路からなる第１の解決手段の場合の第２のポインタ回路に代えて、前記２分探索木格納ＲＡＭ中のデータ格納場所を示すポインタレジスタとその制御回路からなる第２のポインタ回路を備え、かつ、２分探索木左子ノードの先頭番地を格納する左子ノードポインタ値レジスタと、２分探索木右子ノードの先頭番地を格納する右子ノードポインタ値レジスタとを備えた構成としている。さらに、セレクタについて、前記比較器による比較結果に基づき前記第２のポインタ回路中のポインタレジスタファイルのどれを使って前記２分探索木格納ＲＡＭ中のデータを読み出すかを決めるセレクタに代えて、前記比較器による比較結果に基づき前記左子ノードポインタ値レジスタと前記右子ノードポインタ値レジスタのいずれの値を前記第２のポインタ回路中のポインタレジスタに設定するかを決めるセレクタを備えた構成としている。
【００１６】
すなわち、第２の解決手段として、本発明によるパケット情報検索装置は、パケット中のＩＰアドレス等の情報を検索キーとして予め構築された２分探索木を検索するパケット情報検索装置において、個々のパケットデータを格納するパケット格納ＲＡＭと、ＩＰアドレス等検索すべきデータが登録されたノードで構成される２分探索木を格納する２分探索木格納ＲＡＭと、前記パケット格納ＲＡＭ中のデータ格納場所を示すポインタレジスタとその制御回路からなる第１のポインタ回路と、前記２分探索木格納ＲＡＭ中のデータ格納場所を示すポインタレジスタとその制御回路からなる第２のポインタ回路と、前記パケット格納ＲＡＭから読み出したデータを格納する比較ワードレジスタと、前記２分探索木格納ＲＡＭから読み出したデータを格納する被比較ワードレジスタと、前記比較ワードレジスタと前記被比較ワードレジスタの内容を比較する比較器と、２分探索木左子ノードの先頭番地を格納する左子ノードポインタ値レジスタと、２分探索木右子ノードの先頭番地を格納する右子ノードポインタ値レジスタと、前記比較器による比較結果に基づき前記左子ノードポインタ値レジスタと前記右子ノードポインタ値レジスタのいずれの値を前記第２のポインタ回路中のポインタレジスタに設定するかを決めるセレクタと、検索キーのビット幅が前記比較器のビット幅の何倍であるかを示すワード数を参照して装置の逐次動作を制御するシーケンス制御部とを備えた構成としている。
【００１７】
この構成による作用は次のとおりである。第１のポインタ回路のポインタレジスタがパケット格納ＲＡＭの場所を指定すると、その場所のパケットデータが比較ワードレジスタに読み出される。また、第２のポインタ回路のポインタレジスタが２分探索木格納ＲＡＭの場所を指定して、その場所のデータ（パケットデータに対する比較データ）が被比較ワードレジスタに読み出されるとともに、２分探索木左子ノードの先頭番地が左子ノードポインタ値レジスタに格納され、２分探索木右子ノードの先頭番地が右子ノードポインタ値レジスタに格納される。比較器は、比較ワードレジスタのデータと被比較ワードレジスタのデータを比較し、一致不一致の関係や不一致の場合の大小関係を示す比較結果をセレクタとシーケンス制御部に与える。セレクタは、比較結果に基づいて左子ノードポインタ値レジスタ、右子ノードポインタ値レジスタのいずれかを選択し、次の子ノードの探索のためにポインタレジスタを進める。上記を繰り返すことにより、２分探索木のノードを順次に辿るようにしてパケットデータを検索する。繰り返しは、シーケンス制御部が管理するワード数の分だけ行われる。
【００１８】
上記の構成によれば、シーケンス制御部でワード数を設定し、設定したワード数に基づいて２分探索木でのパケットデータ探索の繰り返し回数を制御するので、任意の比較ワード数のデータ検索に対して同じ回路を用いることが出来る。したがって、ＩＰｖ４、ＩＰｖ６、アドレス・ポート変換等に一つの回路で対応出来る。また、パケットデータの検索だけではなく、マイコンバスのビット幅やＤＳＰの演算器のビット幅を総合的に考慮し共通化した上で、比較器やデータメモリのビット幅を決定することが可能となり、回路部品の共有化、装置の最適化を可能にする。
【００１９】
第３の解決手段として、本発明によるパケット情報検索装置は、上記第２の解決手段において、前記左子ノードポインタ値レジスタおよび前記右子ノードポインタ値レジスタに代えて、２分探索木左子ノードの先頭番地または２分探索木右子ノードの先頭番地を格納する子ノードポインタ値一時保存レジスタを備え、かつ、前記セレクタとして、前記比較器による比較結果に基づき前記子ノードポインタ値一時保存レジスタと前記２分探索木格納ＲＡＭから読み出したデータのいずれの値を第２のポインタ回路中のポインタレジスタに設定するかを決めるセレクタを備えた構成としている。
【００２０】
すなわち、第３の解決手段として、本発明によるパケット情報検索装置は、パケット中のＩＰアドレス等の情報を検索キーとして予め構築された２分探索木を検索するパケット情報検索装置において、個々のパケットデータを格納するパケット格納ＲＡＭと、ＩＰアドレス等検索すべきデータが登録されたノードで構成される２分探索木を格納する２分探索木格納ＲＡＭと、前記パケット格納ＲＡＭ中のデータ格納場所を示すポインタレジスタとその制御回路からなる第１のポインタ回路と、前記２分探索木格納ＲＡＭ中のデータ格納場所を示すポインタレジスタとその制御回路からなる第２のポインタ回路と、前記パケット格納ＲＡＭから読み出したデータを格納する比較ワードレジスタと、前記２分探索木格納ＲＡＭから読み出したデータを格納する被比較ワードレジスタと、前記比較ワードレジスタと前記被比較ワードレジスタの内容を比較する比較器と、２分探索木左子ノードの先頭番地または２分探索木右子ノードの先頭番地を格納する子ノードポインタ値一時保存レジスタと、前記比較器による比較結果に基づき前記子ノードポインタ値一時保存レジスタと前記２分探索木格納ＲＡＭから読み出したデータのいずれの値を第２のポインタ回路中のポインタレジスタに設定するかを決めるセレクタと、検索キーのビット幅が前記比較器のビット幅の何倍であるかを示すワード数を参照して装置の逐次動作を制御するシーケンス制御部とを備えた構成としている。
【００２１】
この構成による作用は次のとおりである。第１のポインタ回路のポインタレジスタがパケット格納ＲＡＭの場所を指定すると、その場所のパケットデータが比較ワードレジスタに読み出される。また、第２のポインタ回路のポインタレジスタが２分探索木格納ＲＡＭの場所を指定して、その場所のデータ（パケットデータに対する比較データ）が被比較ワードレジスタに読み出されるとともに、２分探索木左子ノードまたは２分探索木右子ノードの先頭番地が子ノードポインタ値一時保存レジスタに格納される。比較器は、比較ワードレジスタのデータと被比較ワードレジスタのデータを比較し、一致不一致の関係や不一致の場合の大小関係を示す比較結果をセレクタとシーケンス制御部に与える。セレクタは、比較結果に基づいて子ノードポインタ値一時保存レジスタ、２分探索木格納ＲＡＭのいずれかを選択し、次の子ノードの探索のためにポインタレジスタを進める。上記を繰り返すことにより、２分探索木のノードを順次に辿るようにしてパケットデータを検索する。繰り返しは、シーケンス制御部が管理するワード数の分だけ行われる。
【００２２】
上記の構成によれば、シーケンス制御部でワード数を設定し、設定したワード数に基づいて２分探索木でのパケットデータ探索の繰り返し回数を制御するので、任意の比較ワード数のデータ検索に対して同じ回路を用いることが出来る。したがって、ＩＰｖ４、ＩＰｖ６、アドレス・ポート変換等に一つの回路で対応出来る。また、パケットデータの検索だけではなく、マイコンバスのビット幅やＤＳＰの演算器のビット幅を総合的に考慮し共通化した上で、比較器やデータメモリのビット幅を決定することが可能となり、回路部品の共有化、装置の最適化を可能にする。
【００２３】
上記のパケット情報検索装置のレベルの各発明は、パケット処理装置において、次のように展開することが可能である。本発明によるパケット処理装置は、上記の第１、第２または第３の解決手段におけるパケット情報検索装置とプロセッサからなるものであって、さらに、２分探索木の探索深さをカウントする２分探索木探索深さカウンタを有するものであり、加えて、予め探索深さの最大値を設定する最大探索深さレジスタと、前記２分探索木探索深さカウンタの値と前記最大探索深さレジスタの値を比較する比較器と、前記比較器による比較の結果、前記２分探索木探索深さカウンタの値が前記最大探索深さレジスタの値よりも大きくなったときにプロセッサに通知する手段とを備えた構成としている。
【００２４】
この構成による作用は次のとおりである。２分探索木探索深さカウンタの値が最大探索深さレジスタの設定値を超えた場合、プロセッサは、２分探索木格納ＲＡＭ内の２分探索木の深さが最大探索深さレジスタの設定値（最大値）以下になるように、２分探索木格納ＲＡＭにおいて２分探索木の構造を変更し、２分探索木のノードを追加する。２分探索木の構造が不適切になった場合のみ、プロセッサのソフトウェアで２分探索木の構造を変更するため、プロセッサにほとんど負荷をかけることなく、２分探索木のノードの追加が可能になり、効率が良いパケット処理装置を実現出来る。
【００２５】
【発明の実施の形態】
以下、本発明の実施の形態について図面を参照して説明する。
【００２６】
（実施の形態１）
図１は本発明の実施の形態１（請求項１相当）におけるパケット情報検索装置の構成を示すブロック図である。
【００２７】
図１において、１−１は受信したパケットを格納するパケット格納ＲＡＭである。１−２は２分探索木を格納する２分探索木格納ＲＡＭである。１−３は第１のポインタ回路であり、パケット格納ＲＡＭ１−１中のデータ格納場所を示すポインタレジスタ１−４とその制御回路から構成される。１−５は第２のポインタ回路であり、２分探索木格納ＲＡＭ１−２中のデータ格納場所を示す複数のポインタレジスタから構成されるポインタレジスタファイル１−６とその制御回路、およびバスＢから入力されるデータを更新してポインタレジスタファイル１−６に設定する更新回路１−７から構成される。
【００２８】
図２は２分探索木格納ＲＡＭ１−２に格納されている２分探索木の一例を示す。
【００２９】
図２において、２−１〜２−６は２分探索木を構成するノードであり、各々がポインタｐＬｅｆｔ、ｐＲｉｇｈｔで接続されている。これらのノード間には、
｜ノードＢ｜＜｜ノードＡ｜＜｜ノードＣ｜
｜ノードＤ｜＜｜ノードＢ｜＜｜ノードＥ｜
｜ノードＣ｜＜｜ノードＦ｜
のように、常に左側の子ノードが親ノードよりも大きさが小さく、右側の子ノードが親ノードよりも大きさが大きくなるように構成される（常に左側の子ノードが親ノードよりも大きさが大きく、右側の子ノードが親ノードよりも大きさが小さくなるように２分探索木を構成することもあるが、本説明では理解を容易にするため、常に左側の子ノードが親ノードよりも大きさが小さく、右側の子ノードが親ノードよりも大きさが大きいとして説明する）。さらに、ノードＣ、ノードＤ、ノードＥ、ノードＦ等左右の子ノードの一方あるいは両方を持たない場合は、子ノードが無いことを示すために、ｐＬｅｆｔあるいはｐＲｉｇｈｔをＮＵＬＬに設定する。
【００３０】
図３はパケット格納ＲＡＭ１−１の内容を示す。図３に示すように、パケット中の特定範囲のデータを一定のビット幅（ワード）毎に分割したワードデータ列Ｄａｔａ０〜Ｄａｔａ（ｎ−１）を含む。ポインタレジスタ１−４は、Ｄａｔａ０〜Ｄａｔａ（ｎ−１）を適宜指し示す。
【００３１】
２分探索木格納ＲＡＭ１−２は、パケット中のデータＤａｔａ０〜Ｄａｔａ（ｎ−１）を検索キーとしてノードを検索するためのデータ構造を保持する。その内容は図４に示すように２分探索木のノードデータを単位として構成され、ノードデータには子ノードへのポインタｐＬｅｆｔ、ｐＲｉｇｈｔ、パケットデータと比較されるデータＣｏｍｐ０〜Ｃｏｍｐ（ｎ−１）を含む。Ｃｏｍｐ０〜Ｃｏｍｐ（ｎ−１）は、パケット中のデータと同様のビット幅に分割されたワードデータ列である。ポインタレジスタファイル１−６は、ノードデータ内の各データの位置を指し示す。ここで、先に述べた図２の２分探索木の各ノードの大小関係は、Ｃｏｍｐ０〜Ｃｏｍｐ（ｎ−１）を上位桁から順に並べた数値の大小関係に対応する。
【００３２】
パケットデータＤａｔａ０〜Ｄａｔａ（ｎ−１）の検索手法は、２分探索木のルートノードを検索開始ノードとし、Ｄａｔａ０〜Ｄａｔａ（ｎ−１）を上位桁から順に並べた数値を各ノードのＣｏｍｐ０〜Ｃｏｍｐ（ｎ−１）を上位桁から順に並べた数値と比較し、パケットデータの数値がノードデータの数値と等しければ、そのノードを一致ノードとして検索を終了し、パケットデータの数値がノードデータの数値よりも小さければ左子ノードを検索し、大きければ右子ノードを検索し、以降、一致ノードが見つかり検索を終了するか、次に採用する子ノードへのポインタがＮＵＬＬとなり、一致ノード無しで検索を終了するまで、次々に子ノードを辿り検索を実行する手順をとる。
【００３３】
図１に戻って、１−８はパケット格納ＲＡＭ１−１から読み出したデータを保持する比較ワードレジスタであり、１−９は２分探索木格納ＲＡＭ１−２から読み出したデータを保持する被比較ワードレジスタである。比較器１−１０は比較ワードレジスタ１−８の値を被比較ワードレジスタ１−９の値と比較し、比較結果判定回路１−１１を経由して一致、不一致信号をポインタレジスタファイルの出力側のセレクタ１−１２およびシーケンス制御部１−１３に与える。セレクタ１−１２は、ワードデータ列の比較中はワードデータ列を指すポインタレジスタを選択し、次の子ノードに検索を進める際には比較結果パケットの数値がノードの数値よりも小さければｐＬｅｆｔを指すレジスタを選択し、大きければｐＲｉｇｈｔを指すレジスタを選択する。
【００３４】
シーケンス制御部１−１３は比較ワード数レジスタ１−１４を持ち、比較ワード列をワード単位に比較するよう回路全体の制御を行う。図３、図４の例では比較ワード数＝ｎである。さらに、シーケンス制御部１−１３は、パケットの数値がノードの数値と等しい場合、そのときのノードが検索一致ノードであるとして探索結果ノードへのポインタ格納レジスタ１−１５に一致ノードを指し示すポインタ値を設定して検索を終了し、また、セレクタ１−１２の出力が次の検索子ノードを指しかつＮＵＬＬである場合、一致ノード無しとして検索を終了するよう回路全体の制御を行う。
【００３５】
以上の構成により、予め構成された図２の２分探索木に対して入力したパケットデータが登録されているかどうかをルートノードから順に検索することが出来る。この構成により、任意の比較ワード数のデータ検索に対して同じ回路を用いることが出来るため、ＩＰｖ４、ＩＰｖ６、アドレス・ポート変換等に一つの回路で対応出来る。また、パケットデータの検索だけではなく、マイコンバスのビット幅やＤＳＰの演算器のビット幅を総合的に考慮し共通化した上で、比較器やデータメモリのビット幅を決定出来ることになり、回路部品の共有化、装置の最適化を可能にする。
【００３６】
（実施の形態２）
図５は本発明の実施の形態２（請求項２相当）におけるポインタ制御回路のブロック図である。
【００３７】
図５において、５−２〜５−５はポインタレジスタであり、図１のレジスタファイル１−６に相当する。５−６、５−７、５−８はバスＢから入力されるデータに一定のオフセット値を加える加算器である。５−９はレジスタＰ２の値に１を加える加算器であり、５−１０はバスＢからのデータと加算器５−９の出力を選択するセレクタである。また、１−１２はセレクタ、１−２は２分探索木格納ＲＡＭ、１−１５は探索結果ノードへのポインタ格納レジスタである。
【００３８】
図６は実施の形態２において２分探索木格納ＲＡＭ１−２内のデータ構造とポインタレジスタの関係を示す。図７は実施の形態２においてパケット格納ＲＡＭ内のデータ構造とポインタレジスタの関係を示す。
【００３９】
２分探索中、バスＢから来る次の子ノードを指し示すポインタ値に対して加算器５−６，５−７，５−８でオフセットが加わり、ポインタレジスタＰ０，Ｐ１，Ｐ２には図６で示すように各々ノード中のｐＲｉｇｈｔの位置、ｐＬｅｆｔの位置、Ｃｏｍｐ０の位置が設定される。さらに、ポインタレジスタＰ２は、加算器５−９で加算されＣｏｍｐ０の位置からＣｏｍｐ（ｎ−１）の位置まで逐次変化する。
【００４０】
また、図７は実施の形態２の第１のポインタ回路１−４を示し、ポインタレジスタ１−４は、ポインタレジスタＰ２の変化に同期して、その値が初期値Ｄａｔａ０の位置からＤａｔａ（ｎ−１）の位置まで変化する。７−１は１加算器、７−２はセレクタである。
【００４１】
その他の構成については実施の形態１の場合と同様であるので、説明を省略する。
【００４２】
次に、上記のように構成されたパケット情報検索装置の動作を図８のフローチャートに基づいて説明する。
【００４３】
まず、ステップＳ８−１で第２のポインタ回路１−５におけるポインタレジスタファイルＢのポインタレジスタＰ０〜Ｐ３が各々ルートノードの中の対応するデータを指し示すように初期設定する。
【００４４】
ステップＳ８−２で第１のポインタ回路１−３におけるポインタレジスタＡがパケットデータ中の比較先頭ワード（Ｄａｔａ０）を指すように設定する。
【００４５】
ステップＳ８−３でワード数カウンタＮに比較ワード数レジスタ１−１４の値を設定する。
【００４６】
ステップＳ８−４でパケット格納ＲＡＭ１−１から読み出したワードデータと２分探索木格納ＲＡＭ１−２から読み出したワードデータを比較し、等しければステップＳ８−５でＮを１減算し、ステップＳ８−６に進む。
【００４７】
ステップＳ８−６ではＮが０かどうか判断し、０であればステップＳ８−７でそのときのノードを指し示すポインタレジスタＰ３の値を探索結果ノードへのポインタ格納レジスタ５−１２に一致ノードとして保存し、検索を終了する。
【００４８】
ステップＳ８−６でＮが正の場合はステップＳ８−８に進み、ポインタレジスタＡを１ワード分進め、ステップＳ８−９でポインタレジスタＰ２を１ワード分進め、ステップＳ８−４に進む。
【００４９】
ステップＳ８−４でパケット格納ＲＡＭ１−１から読み出したワードデータが２分探索木格納ＲＡＭ１−２から読み出したワードデータよりも小さければ、ステップＳ８−１０へ進む。
【００５０】
ステップＳ８−１０で左子ノードが無ければ（Ｐ０がＮＵＬＬであれば）、一致ノード無しとして検索を終了し、左子ノードがあればステップＳ８−１１でポインタレジスタＰ０の値を２分探索木格納ＲＡＭ１−２に与え、データを読み出してバスＢ経由でポインタレジスタファイルＢを更新する。
【００５１】
ステップＳ８−４でパケット格納ＲＡＭ１−１から読み出したワードデータが２分探索木格納ＲＡＭ１−２から読み出したワードデータよりも大きければ、ステップＳ８−１２へ進む。
【００５２】
ステップＳ８−１２で右子ノードが無ければ（Ｐ１がＮＵＬＬであれば）、一致ノード無しとして検索を終了し、右子ノードがあれば、ステップＳ８−１３でポインタレジスタＰ１の値を２分探索木格納ＲＡＭ１−２に与え、データを読み出してバスＢ経由でポインタレジスタファイルＢを更新する。
【００５３】
（実施の形態３）
図９は本発明の実施の形態３（請求項３相当）におけるパケット情報検索装置の構成を示すブロック図である。
【００５４】
図９において、９−１は受信したパケットを格納するパケット格納ＲＡＭである。９−２は２分探索木を格納する２分探索木格納ＲＡＭである。９−３は第１のポインタ回路であり、パケット格納ＲＡＭ９−１中のデータ格納場所を示すポインタレジスタ９−４とその制御回路から構成される。９−５は第２のポインタ回路であり、２分探索木格納ＲＡＭ９−２中のデータ格納場所を示すポインタレジスタ９−６とその制御回路から構成される。２分探索木格納ＲＡＭ９−２に格納されている２分探索木の一例は実施の形態１の場合と同様に図２で示される。パケット格納ＲＡＭ９−１の内容は実施の形態１の場合と同様に図３に示される。２分探索木格納ＲＡＭ９−２は、パケット中のデータＤａｔａ０〜Ｄａｔａ（ｎ−１）を検索キーとしてノードを検索するためのデータ構造を保持する。その内容は図１０に示すようにノードデータを単位として構成され、ノードデータには子ノードへのポインタｐＬｅｆｔ、ｐＲｉｇｈｔ、パケットデータと比較されるデータＣｏｍｐ０〜Ｃｏｍｐ（ｎ−１）が順に並んでいる。Ｃｏｍｐ０〜Ｃｏｍｐ（ｎ−１）は、パケット中のデータと同様のビット幅に分割されたワードデータ列である。ポインタレジスタ９−６は、ノードデータ内の各データの位置を指し示す。ここで、先に述べた図２の２分探索木の各ノードの大小関係は、Ｃｏｍｐ０〜Ｃｏｍｐ（ｎ−１）を上位桁から順に並べた数値の大小関係に対応する。パケットデータＤａｔａ０〜Ｄａｔａ（ｎ−１）の検索手法は、２分探索木のルートノードを検索開始ノードとし、Ｄａｔａ０〜Ｄａｔａ（ｎ−１）を上位桁から順に並べた数値を各ノードのＣｏｍｐ０〜Ｃｏｍｐ（ｎ−１）を上位桁から順に並べた数値と比較し、パケットデータの数値がノードデータの数値と等しければ、そのノードを一致ノードとして検索を終了し、パケットデータの数値がノードデータの数値よりも小さければ左子ノードを検索し、大きければ右子ノードを検索し、以降、一致ノードが見つかり検索を終了するか、次に採用する子ノードへのポインタがＮＵＬＬとなり、一致ノード無しで検索を終了するまで、次々に子ノードを辿り検索を実行する手順をとる。
【００５５】
図９に戻って、９−７はパケット格納ＲＡＭ９−１から読み出したデータを保持する比較ワードレジスタであり、９−８は２分探索木格納ＲＡＭ９−２から読み出したデータを保持する被比較ワードレジスタである。９−９は２分探索木格納ＲＡＭ９−２から読み出した左子ノードへのポインタの値を設定する左子ノードポインタ値レジスタであり、９−１０は２分探索木格納ＲＡＭ９−２から読み出した右子ノードへのポインタの値を設定する右子ノードポインタ値レジスタである。比較器９−１１は比較ワードレジスタ９−７の値を被比較ワードレジスタ９−８の値と比較し、比較結果判定回路９−１２を経由して一致、不一致信号を左右子ノードへのポインタ値レジスタ９−９，９−１０の出力セレクタ９−１３およびシーケンス制御部９−１４に与える。セレクタ９−１３は、比較結果パケットの数値がノードの数値よりも小さければ左子ノードポインタ値レジスタ９−９を選択し、大きければ右子ノードポインタ値レジスタ９−１０を選択する。シーケンス制御部９−１４は比較ワード数レジスタ９−１５を持ち、比較ワード列をワード単位に比較するよう回路全体の制御を行う。図１０の例では比較ワード数＝ｎである。さらに、シーケンス制御部９−１４は、パケットの数値がノードの数値と等しい場合、そのときのノードが検索一致ノードであるとして探索結果ノードへのポインタ格納レジスタ９−１６に一致ノードを指し示すポインタ値を設定して検索を終了し、また、セレクタ９−１３の出力がＮＵＬＬである場合、一致ノード無しとして検索を終了するよう回路全体の制御を行う。
【００５６】
以上の構成により、予め構成された図２の２分探索木に対して入力したパケットデータが登録されているかどうかをルートノードから順に検索することが出来る。
【００５７】
次に、上記のように構成されたパケット情報検索装置の動作を図１１のフローチャートに基づいて説明する。
【００５８】
まず、ステップＳ１１−１で第２のポインタ回路９−５におけるポインタレジスタＢがルートノードの右子ノードポインタ格納場所を指すように初期設定する。
【００５９】
ステップＳ１１−２で第１のポインタ回路９−３におけるポインタレジスタＡがパケットデータ中の比較先頭ワード（Ｄａｔａ０）を指すように設定する。
【００６０】
ステップＳ１１−３で２分探索木格納ＲＡＭ９−２から左子ノードへのポインタ値を読み出し、左子ノードポインタ値レジスタ９−９に設定した後、ポインタレジスタＢの値を探索結果ノードへのポインタ格納レジスタ９−１６に保存し、ポインタレジスタＢに１加算して右子ノードへのポインタ値を読み出し、右子ノードポインタ値レジスタ９−１０に設定し、さらにポインタレジスタＢに１加算してポインタレジスタＢを被比較データの先頭ワード（Ｃｏｍｐ０）を指すように設定する。
【００６１】
次にステップＳ１１−４でワード数カウンタＮに比較ワード数レジスタ９−１５の値を設定する。
【００６２】
ステップＳ１１−５でパケット格納ＲＡＭ９−１から読み出したワードデータと２分探索木格納ＲＡＭ９−２から読み出したワードデータを比較し、等しければステップＳ１１−６でＮを１減算し、ステップＳ１１−７に進む。
【００６３】
ステップＳ１１−７ではＮが０かどうか判断し、０であればステップＳ１１−８でそのときの探索結果ノードへのポインタ格納レジスタ９−１６の値を保存し、検索を終了する。
【００６４】
ステップＳ１１−７でＮが正の場合はステップＳ１１−９に進み、ポインタレジスタＡを１ワード分進め、ステップＳ１１−１０でポインタレジスタＢを１ワード分進め、ステップＳ１１−５に進む。
【００６５】
ステップＳ１１−５でパケット格納ＲＡＭ９−１から読み出したワードデータが２分探索木格納ＲＡＭ９−２から読み出したワードデータよりも小さければ、ステップＳ１１−１１で次の子ノードへのポインタとして左子ノードポインタ値レジスタ９−９を選択し、パケット格納ＲＡＭ９−１から読み出したワードデータが２分探索木格納ＲＡＭ１−２から読み出したワードデータよりも大きければ、ステップＳ１１−１２で次の子ノードへのポインタとして右子ノードポインタ値レジスタ９−１０を選択する。
【００６６】
ステップＳ１１−１３で子ノードが無ければ（次の子ノードへのポインタがＮＵＬＬであれば）、一致ノード無しとして検索を終了し、子ノードがあればステップＳ１１−１４でポインタレジスタＢに次の子ノードへのポインタ値を設定し、ステップＳ１１−２に戻る。
【００６７】
（実施の形態４）
図１２は本発明の実施の形態４（請求項４相当）におけるパケット情報検索装置の構成を示すブロック図である。
【００６８】
図９の実施の形態３と比較して、左子ノードポインタ値レジスタ９−９、右子ノードポインタ値レジスタ９−１０のいずれか一方を省略した場合と同一である。２分探索木格納ＲＡＭ１２−２のノードのデータ構造が図１０の場合、子ノードへのポインタ一時保存レジスタ１２−９には左子ノードへのポインタ値が書き込まれる。セレクタ１２−１２では子ノードへのポインタ一時保存レジスタ１２−９の出力と２分探索木格納ＲＡＭ１２−２から読み出した右子ノードへのポインタ値が選択される。Ｓその他の動作については、実施の形態３の場合と同じである。
【００６９】
（実施の形態５）
図１３は実施の形態５（請求項５相当）におけるパケット処理装置の構成を示すブロック図である。
【００７０】
図１３において、１３−１は２分探索木探索深さカウンタ１３−３を有する実施の形態１ないし４のいずれかのパケット情報検索装置であり、１３−２はその中の２分探索木格納ＲＡＭである。プロセッサ１３−４は予め最大探索深さレジスタ１３−５に２分探索木の探索深さの最大値を設定しておく。
【００７１】
パケット情報検索中、パケット処理装置の２分探索木探索深さカウンタ１３−３と最大探索深さレジスタ１３−５の設定値を比較器１３−６で比較し、比較結果をプロセッサ１３−４に通知する。２分探索木探索深さカウンタ１３−３の値が最大探索深さレジスタ１３−５の設定値を超えた場合、プロセッサ１３−４は、２分探索木格納ＲＡＭ１３−２内の２分探索木の深さを、最大探索深さレジスタ１３−５の設定値（最大値）以下にすることが可能かどうか検査し、可能であれば、２分探索木の深さが最大探索深さレジスタ１３−５の設定値（最大値）以下になるように、２分探索木格納ＲＡＭ１−２において２分探索木の構造を変更する。すなわち、２分探索木のノードを追加する。
【００７２】
以上のように、２分探索木の構造が不適切になった場合のみ、プロセッサのソフトウェアで２分探索木の構造を変更するため、プロセッサにほとんど負荷をかけることなく、２分探索木のノードの追加が可能になり、効率が良いパケット処理装置を実現出来る。
【００７３】
【発明の効果】
以上説明したように本発明によれば、パケット中の任意の比較ワード数のデータ検索に対して同じ回路を用いることが出来るため、ＩＰｖ４、ＩＰｖ６、アドレス・ポート変換等に一つの回路で対応出来るパケット情報検索装置を実現出来る。また、パケットデータの検索だけではなく、マイコンバスのビット幅やＤＳＰの演算器のビット幅を総合的に考慮し共通化した上で、比較器やデータメモリのビット幅を決定出来ることになり、回路部品の共有化、装置の最適化を可能にする。さらには、効率が良い高性能なパケット処理装置を安価に実現出来る。
【図面の簡単な説明】
【図１】本発明の実施の形態１におけるパケット情報検索装置の構成を示すブロック図
【図２】本発明の実施の形態１におけるパケット情報検索装置において取り扱う２分探索木の構造を示すブロック図
【図３】本発明の実施の形態１におけるパケット情報検索装置においてパケット格納ＲＡＭ内のデータ構造とポインタレジスタの関係を示すブロック図
【図４】本発明の実施の形態１におけるパケット情報検索装置において２分探索木格納ＲＡＭ内のデータ構造とポインタレジスタの関係を示すブロック図
【図５】本発明の実施の形態２におけるパケット情報検索装置において２分探索木格納ＲＡＭ内を指すポインタレジスタ回路の構成を示すブロック図
【図６】本発明の実施の形態２におけるパケット情報検索装置において２分探索木格納ＲＡＭ内のデータ構造とポインタレジスタの関係を示すブロック図
【図７】本発明の実施の形態２におけるパケット情報検索装置においてパケット格納ＲＡＭ内のデータ構造とポインタレジスタの関係を示すブロック図
【図８】本発明の実施の形態１、実施の形態２におけるパケット情報検索装置の動作を示すフローチャート
【図９】本発明の実施の形態３におけるパケット情報検索装置の構成を示すブロック図
【図１０】本発明の実施の形態３におけるパケット情報検索装置において２分探索木格納ＲＡＭ内のデータ構造とポインタレジスタの関係を示すブロック図
【図１１】本発明の実施の形態３におけるパケット情報検索装置の動作を示すフローチャート
【図１２】本発明の実施の形態４におけるパケット情報検索装置の構成を示すブロック図
【図１３】本発明の実施の形態５におけるパケット処理装置の構成を示すブロック図
【符号の説明】
１−１，９−１，１２−１  パケット格納ＲＡＭ
１−２，９−２，１２−２，１３−２  ２分探索木格納ＲＡＭ
１−３，９−３，１２−３  第１のポインタ回路
１−４，５−２，５−３，５−４，５−５，９−４，９−６，１２−４，１２−６  ポインタレジスタ
１−５，９−５，１２−５  第２のポインタ回路
１−６  ポインタレジスタファイル
１−７  更新回路
１−８，９−７，１２−７  比較ワードレジスタ
１−９，９−８，１２−８  被比較ワードレジスタ
１−１０，９−１１，１２−１０，１３−６  比較器
１−１１，９−１２，１２−１１  比較結果判定回路
１−１２，５−１０，７−２，９−１３，１０−２，１２−１２  セレクタ
１−１３，９−１４，１２−１３  シーケンス制御部
１−１４，９−１５，１２−１４  比較ワード数レジスタ
１−１５，９−１６，１２−１５  探索結果ノードへのポインタ格納レジスタ
２−１  ルートノード
２−２，２−３，２−４，２−５，２−６  ノード
５−６，５−７，５−８  オフセット付加器
５−９，７−１，１０−１  １加算器
９−９，９−１０，１２−９  子ノードポインタ値レジスタ
１３−１  パケット情報検索装置
１３−３  ２分探索木探索深さカウンタ
１３−４  プロセッサ
１３−５  最大探索深さレジスタ
【図１】
2004320280.tif 000003
【図２】
2004320280.tif 000004
【図３】
2004320280.tif 000005
【図４】
2004320280.tif 000006
【図５】
2004320280.tif 000007
【図６】
2004320280.tif 000008
【図７】
2004320280.tif 000009
【図８】
2004320280.tif 000010
【図９】
2004320280.tif 000011
【図１０】
2004320280.tif 000012
【図１１】
2004320280.tif 000013
【図１２】
2004320280.tif 000014
【図１３】
2004320280.tif 000015