(57)【要約】  廉価な従来のメモリ部品を利用して、正確で予測可能な高速検索を実行できるコンテンツ・ベース情報検索アーキテクチャーがここに開示される。
2007524946.tif 000002
【特許請求の範囲】
【請求項１】
入力値を受け取り、該入力値から複数のハッシュされた値を生成するハッシング・モジュールと、
複数の符号化された値を格納する第１の表であって、前記入力値から生成された各ハッシュされた値は、符号化された値の前記表内の位置に対応する、第１の表と、
複数の検索値を格納する第２の表と、
検索集合内の複数の関連する入力値を格納する第３の表であって、そのような入力値のそれぞれは前記第２の表中の検索値と関連する、第３の表と
を有し、
前記第１の表は、入力値から生成された前記ハッシュされた値から得られた前記符号化された値が、出力値が何らかの単一の符号化された値から回復できないように、また、前記出力値が前記第２の表中の検索値と前記第３の表中の関連する入力値を選択するように、前記出力値を符号化するように構成され、それによって、前記入力値が前記第３の表中の前記関連する入力値と同じであれば、前記入力値が前記検索集合内に存在すると確認する、
コンテンツ・ベースの情報検索アーキテクチャー。
【請求項２】
前記出力値が、複数の前記符号化された値を、ビット毎の排他的論理和演算を行うことによって結合することによって回復されるように、前記第１の表中の前記符号化された値が前記出力値を符号化する、請求項１記載の情報検索アーキテクチャー。
【請求項３】
前記検索値は前記第２の表中の固有のアドレスに格納され、符号化された値の前記第１の表は、前記複数の符号化された値によって符号化された前記出力値が前記第２の表中のアドレスであるように構成されている、請求項１記載の情報検索アーキテクチャー。
【請求項４】
前記第１の表は、前記第２の表が前記第１の表より小さいサイズを有するように、また、前記第１の表の幅が少なくとも
【数１】
2007524946.tif 000145
（ここで、
【数２】
2007524946.tif 000146
は検索値の数）であるように構成されている、請求項１記載の情報検索アーキテクチャー。
【請求項５】
前記第１の表は複数のバンクに分割され、各バンクは前記ハッシング・モジュールによって生成された複数のハッシュされた値の１つと関連する、請求項１記載の情報検索アーキテクチャー。
【請求項６】
前記ハッシング・モジュールと前記第１の表は、前記第２および第３の表から異なる段階にパイプライン方式で接続されている、請求項１記載の情報検索アーキテクチャー。
【請求項７】
入力値を受け取り、前記入力値が入力値のフィルターリングされた集合のメンバーではない場合にのみ、前記入力値を前記ハッシング・モジュールへ転送するフィルターリング・モジュールをさらに有する、請求項１記載の情報検索アーキテクチャー。
【請求項８】
入力値の前記フィルターリングされた集合は、入力値の前記検索集合のメンバーであると認識されない入力値である、請求項７記載の情報検索アーキテクチャー。
【請求項１０】
入力値の前記フィルターリングされた集合は、符号化された値の前記第１の表の構築を容易にするように選択された入力値である、請求項７記載の情報検索アーキテクチャー。
【請求項１１】
入力値の前記フィルターリングされた集合は、前記ハッシング・モジュールが前記１つの入力値から複数のハッシュ値を生成するときに、前記１つの入力値から生成された前記ハッシュされた値が符号化された値の前記第１の表中の１つの単集合の位置には対応しないように、少なくとも１つの入力値を有する、請求項１０記載の情報検索アーキテクチャー。
【請求項１２】
少なくとも１つの入力値が、前記ハッシング・モジュールに次に転送される他の入力値に前記フィルターリング・モジュールによって再配置される、請求項７記載の情報検索アーキテクチャー。
【請求項１３】
前記第３の表中の前記関連する入力値が前記１つの入力値と同一ではないために、前記検索集合内に存在しないと認識された少なくとも１つの入力値が、前記フィルターリング・モジュールによって使用された入力値の前記フィルターリングされた集合に追加される、請求項７記載の情報検索アーキテクチャー。
【請求項１４】
前記第１の表は前記第２の表と前記第３の表中に索引付けを行うために使用され、前記第３の表はフィルターリングを行うために使用される、請求項１記載の情報検索アーキテクチャー。
【請求項１５】
パケット・ヘッダ中の情報に対して検索を行うための少なくとも１つのフィルターを有するネットワーク・ルーターであって、前記フィルターは、
前記パケット・ヘッダ中の前記情報を受け取り、前記パケット・ヘッダ中の前記情報から複数のハッシュされた値を生成するハッシング・モジュールと、
複数の符号化された値を格納する第１の表であって、前記パケット・ヘッダ中の前記情報から生成された各ハッシュされた値は符号化された値の前記第１の表中の位置に対応し、前記第１の表は、前記パケット・ヘッダ中の前記情報から得られた前記符号化された値が、出力値が任意の単一の符号化された値から回復できないように、また、前記出力値が前記パケット・ヘッダに対する転送情報を選択するために使用されるように、前記出力値を符号化するように構成されている、第１の表と
をさらに有する、ネットワーク・ルーター。
【請求項１６】
複数の前記符号化された値を、ビット毎の排他的論理和演算を行うことによって結合することによって前記出力値が回復されるように、前記第１の表中の複数の前記符号化された値が前記出力値を符号化する、請求項１５記載のネットワーク・ルーター。
【請求項１７】
前記パケット・ヘッダ中の前記情報が予め指定された長さのプレフイックスである、請求項１５記載のネットワーク・ルーター。
【請求項１８】
異なる予め指定された長さのプレフイックスに対して１つまたは複数の追加のフィルターをさらに有し、各フィルターが並列に検索を行う、請求項１７記載のネットワーク・ルーター。
【請求項１９】
各フィルターに対してアップデート・フィルターをさらに有し、前記アップデート・フィルターは、オフラインで更新可能であり、前記フィルター中の前記第１の表と交換可能である前記第１の表のバージョンを有する、請求項１８記載のネットワーク・ルーター。
【請求項２０】
各フィルターからの結果を受け取り、最長のプレフイックスを処理する前記フィルターからの前記結果にもとづいて転送情報を選択するプライオリティ・エンコーダをさらに有する、請求項１８記載のネットワーク・ルーター。
【請求項２１】
前記第１の表が複数のバンクに分割されており、各バンクが前記ハッシング・モジュールによって生成された前記複数のハッシュされた値の１つに関連する、請求項１５記載のネットワーク・ルーター。
【請求項２２】
前記ハッシング・モジュールと前記第１の表が、異なる段階にパイプライン方式で接続されている、請求項１５記載のネットワーク・ルーター。
【請求項２３】
前記パケット・ヘッダ中の前記プレフイックスを受け取り、前記プレフイックスがプレフイックスのフィルターリングされた集合のメンバーではない場合にのみ、前記プレフイックスを前記ハッシング・モジュールへ転送するフィルターリング・モジュールをさらに有する、請求項１７記載のネットワーク・ルーター。
【請求項２４】
プレフイックスの前記フィルターリングされた集合は、プレフイックスの検索集合のメンバーであると認識されないプレフイックスである、請求項２３記載のネットワーク・ルーター。
【請求項２５】
プレフイックスの前記フィルターリングされた集合は、符号化された値の前記第１の表の構築を容易にするように選択されたプレフイックスである、請求項２３記載のネットワーク・ルーター。
【請求項２６】
プレフイックスの前記フィルターリングされた集合は、前記ハッシング・モジュールが前記１つのプレフイックスから複数のハッシュされた値を生成するときに、前記１つのプレフイックスから生成された前記ハッシュされた値が符号化された値の前記第１の表中の１つの単集合の位置には対応しないように、少なくとも１つのプレフイックスを有する、請求項２５記載のネットワーク・ルーター。
【請求項２７】
少なくとも１つのプレフイックスが、前記ハッシング・モジュールに次に転送される他のプレフイックスに前記フィルターリング・モジュールによって再配置される、請求項２３記載のネットワーク・ルーター。
【請求項２８】
前記転送情報を各プレフイックスと関連する転送値として格納する第２の表をさらに有する、請求項２０記載のネットワーク・ルーター。
【請求項２９】
各フィルターが関連する第２の表を有する、請求項２８記載のネットワーク・ルーター。
【請求項３０】
前記プライオリティ・エンコーダが、最長のプレフイックスを処理するフィルターを選択し、次に前記複数のフィルターによって共有される第２の表から前記転送情報を検索する、請求項２８記載のネットワーク・ルーター。
【請求項３１】
複数の関連するプレフイックスを検索集合中に格納する第３の表をさらに有し、このような関連するプレフイックスの各々は前記第２の表中の転送値と関連し、前記出力値は前記第２の表中の転送値および前記第３の表から関連するプレフイックスを選択し、それによって、前記パケット・ヘッダ中の前記プレフイックスが前記第３の表中の前記関連するプレフイックスと同じであれば、前記パケット・ヘッダ中の前記プレフイックスが前記検索集合内に存在すると確認する、請求項２８記載のネットワーク・ルーター。
【請求項３２】
前記フィルターの中の前記第１の表は、前記第２の表が前記第１の表より小さいサイズを有するように、また、前記第１の表の幅が少なくとも
【数３】
2007524946.tif 000147
（ここで、
【数４】
2007524946.tif 000148
は転送値の数である）であるように、構成されている、請求項３１記載のネットワーク・ルーター。
【請求項３３】
前記パケット・ヘッダ中の前記プレフイックスを受け取り、前記プレフイックスがプレフイックスのフィルターリングされた集合のメンバーではない場合にのみ、前記プレフイックスを前記ハッシング・モジュールへ転送するフィルターリング・モジュールをさらに有し、前記第３の表中の前記関連するプレフイックスが１つの入力値と同じではないために前記検索集合内に存在しないと認識された前記少なくとも１つのプレフイックスが、前記フィルターリング・モジュールによって使用された、プレフイックスの前記フィルターリングされた集合に追加される、フィルターリング・モジュールをさらに有する、請求項３１記載のネットワーク・ルーター。
【請求項３４】
入力値を受け取り、前記入力値から複数のハッシュされた値を生成するハッシング・モジュールと、
複数の符号化された値を格納する表であって、前記入力値から生成された各ハッシュされた値は符号化された値の前記表中の位置に対応し、前記表は複数のバンクに分割され、各バンクは、前記ハッシング・モジュールによって生成された前記複数のハッシュされた値の１つと関連し、前記表は、出力値が任意の単一の符号化された値から回復できないように、前記入力値から得られた前記符号化された値が前記出力値を符号化するように構成されている、表と
を有するコンテンツ・ベースの情報検索アーキテクチャー。
【請求項３５】
複数の前記符号化された値を、ビット毎の排他的論理和演算を行うことによって結合することによって前記出力値が回復されるように、前記符号化された値が前記出力値を符号化する、請求項３４記載の情報検索アーキテクチャー。
【請求項３６】
前記表がマルチポートではないメモリに格納されている、請求項３４記載の情報検索アーキテクチャー。
【請求項３７】
入力値を受け取り、前記入力値から複数のハッシュされた値を生成するハッシング・ユニットと、
符号化された値の表を格納するメモリ・ユニットであって、前記入力値から生成された各ハッシュされた値が符号化された値の前記表中の位置に対応するメモリ・ユニットと、
前記符号化された値から出力値を回復する論理ユニットであって、前記入力値から得られた前記符号化された値が、前記出力値が任意の単一の符号化された値から回復できないように前記出力値を符号化し、前記ハッシング・ユニット、前記メモリ・ユニット、および前記論理ユニットが異なる段階にパイプライン方式で接続されている、論理ユニットと
を有するコンテンツ・ベースの情報検索アーキテクチャー。
【請求項３８】
複数の前記符号化された値を、ビット毎の排他的論理和演算を行うことによって結合することによって前記出力値が回復されるように、前記符号化された値が前記出力値を符号化する、請求項３７記載の情報検索アーキテクチャー。
【請求項３９】
検索集合中の入力値に対するコンテンツ・ベースの検索の問い合わせのための検索アーキテクチャーを有する、改良されたコンテンツ・ベースの情報検索アーキテクチャーにおいて、
前記検索アーキテクチャーに接続されたスピルオーバー・テーブルであって、入力値の１つまたは複数のエントリを有し、前記スピルオーバー・テーブル中の前記入力値は前記スピルオーバー・テーブルによって処理されるスピルオーバー・テーブルを有することを特徴とする、改良されたコンテンツ・ベースの情報検索アーキテクチャー。
【請求項４０】
前記スピルオーバー・テーブル中の少なくとも１つの入力値が、前記検索アーキテクチャーに渡される他の入力値の中に配置される、請求項３９記載の改良された情報検索アーキテクチャー。
【請求項４１】
前記スピルオーバー・テーブル中の前記入力値が、前記検索アーキテクチャーが、前記値に対してコンテンツ・ベースの検索問い合わせを処理するためにセットアップされないような値である、請求項３９記載の改良された情報検索アーキテクチャー。
【請求項４２】
前記スピルオーバー・テーブル中の前記入力値が、前記入力値の１つに対してコンテンツ・ベースの検索問い合わせを行うならば、前記検索アーキテクチャーが正しくない結果を生成するような値である、請求項３９記載の改良された情報検索アーキテクチャー。
【請求項４３】
入力値を受け取り、前記入力値が入力値のフィルターリングされた集合のメンバーではない場合にのみ、前記入力値を転送するフィルターリング・モジュールと、
前記転送された入力値を受け取り、前記転送された入力値から複数のハッシュされた値を生成するハッシング・モジュールと、
複数の符号化された値を格納する表であって、前記転送された入力値から生成された各ハッシュされた値は符号化された値の前記表中の位置に対応し、前記表は、出力値が任意の単一の符号化された値から回復できないように、前記転送された入力値から得られた前記符号化された値が前記出力値を符号化するように構成されている、複数の符号化された値を格納する表と
を有するコンテンツベースの情報検索アーキテクチャー。
【請求項４４】
入力値の前記フィルターリングされた集合は、符号化された値の前記表中の符号化された関連する出力値を有する入力値の検索集合のメンバーであると認識されない入力値である、請求項４３記載の情報検索アーキテクチャー。
【請求項４５】
入力値の前記フィルターリングされた集合は、符号化された値の前記表の構成を容易にするように選択された入力値である、請求項４３記載の情報検索アーキテクチャー。
【請求項４６】
入力値の前記フィルターリングされた集合は、前記ハッシング・モジュールが１つの入力値から複数のハッシュされた値を生成するとき、前記１つの入力値から生成された前記ハッシュされた値が符号化された値の前記表中の１つの単集合の位置には対応しないように、前記少なくとも１つの入力値を有する、請求項４５記載の情報検索アーキテクチャー。
【請求項４７】
少なくとも１つの入力値が、前記ハッシング・モジュールに次に転送される他の入力値の中に前記フィルターリング・モジュールによって再配置される、請求項４３記載の情報検索アーキテクチャー。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、高速な情報検索アーキテクチャーに関する。
【０００２】
本実用特許出願は、「低コストかつ高速の連想記憶装置」（INEXPENSIVE AND FAST CONTENT ADDRESASABLE MEMORY）と題し、その内容は参照によって本明細書に含まれる、２００４年２月５日出願の米国仮特許出願第６０／５４１，９８３号の正式出願であり、その利益を主張する。
【背景技術】
【０００３】
アドレスを使用して問い合わせを受ける従来のメモリに対して、連想記憶装置（ＣＡＭ）はデータを使用して問い合わせを受ける装置である。ＣＡＭは、データが存在するか否かを調べるのに、そのコンテンツを検索し、データが存在すれば、該データと関連する情報を出力する。このような記憶装置は、高速な検索が要求されるインターネット・ルーター、プロセッサ・キャッシュ、データベース、および他の状況で用いられる。多くの商用ルーターは、問い合わせがすべてのエントリと一致するかを並行して調べる専用のメモリ・デバイスである３進ＣＡＭ（ＴＣＡＭ）と呼ばれるＣＡＭデバイスを使用している。ＴＣＡＭは従来のＳＲＡＭあるいはＤＲＡＭよりも高価である。ＴＣＡＭはビット当たり約１６個のトランジスタを使用して作られる。したがって、ビット当たり約６個のトランジスタを有するＳＲＡＭよりも、およそ２倍から３倍密度が低い。ＴＣＡＭは、かなりのキャパシタンスを伴う長い「一致ライン」を有し、その結果、その電力キャパシタンスが大きくなり、さらに重要なことに、その速度は相対的に遅くなる。しかし、現在の商用技術では効率的に検索を行うために従来のＳＲＡＭを使用する実行可能な技術がないので、ＴＣＡＭはルーター製造業者にとって依然として魅力的な部品である。
【０００４】
連想記憶装置のように効率的に動作する多種多様な公知のデータ構造が存在し、それぞれ固有の相対的な利点と欠点を有する。たとえば、トライ・ベースの方法は各プレフイックスに対して２値のトライを作成し、２進トライは２種類のノード、すなわち、分岐ノードと要素ノードを有するツリーある。残念ながら、トライ・ベースの方法の拡張性とメモリ利用度は共にアドレス長の関数であり、これはＩＰｖ６のような長いアドレスで使用する場合には不利である。二分決定グラフのような他のデータ構造は、それらが固有の従属性を有し、大容量のメモリとアドレス長に拡張が容易ではないために、ハードウェアで合理的に実現できない。フィールド・プログラマブル・ゲートアレイ（ＦＰＧＡ）ベースの方法は、連想記憶装置を実現するために、メモリおよび適合性のある論理ブロック・リソースを使用する。これらの方法は、素早いプロトタイピングには良いが、大きなプレフイックスの高速処理の良い候補ではない。最近、ブルーム・フィルターがネットワーク・ルーターに対して提案されており、このブルーム・フィルターは、誤ポジティブ率（false positive rate）の小さいメンバーシップ問い合わせをサポートする公知のデータ構造である。 Dharmapurikar S, K.P., Taylor, D. E.の「ブルーム・フィルターを使用する最長プレフイックス・マッチング」(Longest Prefix Matching Using Bloom Filters)、Proceedings of the 2003 Conference on Applications, Technologies, Architectures, and Protocols for Computer Communications、２００３年８月、を参照されたい。別個のブルーム・フィルターとハッシュ・テーブルが個々のプレフイックス長のそれぞれに対して維持され、入力問い合わせが、すべてのブルーム・フィルターにおいてメンバーシップをチェックされる。結果としてポジティブなメンバーシップになる任意のブルーム・フィルターは、そのプレフイックス長に対応するハッシュ・テーブルに入力問い合わせを転送する。この方法の欠点として、複数のハッシュ・テーブルが結果的に衝突し、したがって、予想できない性能が生じることがあることである。さらに、複数のハッシュ・テーブルは、最長プレフイックス・マッチングを行うために、プレフイックス長の降順に順次問い合わせされる。他の方法は、所与の数のプレフイックスに対して準最適な深度を有するバイナリ探索ツリーを作ることであり、その結果最悪の場合の検索時間に限界があり決定的（deterministic）ある。 P. Gupta、B. Prabhakar、および S. Boyd、の「最悪の場合の性能に限界がある準最適なルーティング検索」(Near-Optimal Routing Lookups with Bounded Worst Case Performance)、Proc. Infocom、Vol. 3、pp.1184-92、２０００年３月、を参照されたい。残念ながら、この方法は異なるプレフイックスに対して確率に依存している。
【発明の開示】
【発明が解決しようとする課題】
【０００５】
したがって、既存の連想記憶装置の構造よりも高速、廉価、かつ拡張容易な他の構造に対する必要性が存在する。ＳＲＡＭあるいはＤＲＡＭのような従来のメモリを利用できる実用的なコンテンツ・ベースの情報検索メカニズムに対する必要性も存在する。
【課題を解決するための手段】
【０００６】
従来の低価格なメモリ部品を利用しつつ、一定の問い合わせ時間で高速な検索を実現できるコンテンツ・ベースの情報検索アーキテクチャーがここに開示される。本発明の実施態様によれば、本アーキテクチャーは、ハッシング・モジュール、符号化された値の第１の表、検索値の第２の表、および関連する入力値の第３の表を有する。入力値は、第１の表中の符号化された値の位置に対応している複数のハッシュされた値を生成するために何回もハッシュされる。入力値から得られた符号化された値は、出力値が任意の単一の符号化された値から回復できないように、出力値を符号化する。たとえば、符号化された値は、出力値を生成するために、ビット毎の排他的論理和（ＸＯＲ）演算を使用して複数の値を結合することによって、符号化できる。出力値は、第２の表中の検索値と第３の表中の関連する入力値を選択するよう働きをする。符号化された値の表は、出力値が第２および第３の表中のアドレスであるように構成することができる。第３の表中の関連する入力値が入力値と同じであれば、入力値は検索集合の一部であり、選択された検索値は入力値に対応する。第３の表中の関連する入力値が入力値と同じでなければ、入力値は検索集合の中には存在しない。第３の表はフィルターリングを行うために使用可能であり、符号化された値の第１の表は第２および第３の表中に索引付けを行うために使用される。第３の表は省略可能であるが、誤ポジティブの可能性がある。
【０００７】
本発明の他の態様の他の実施態様によれば、前記表群は、各バンクがハッシング・モジュールによって生成された複数のハッシュされた値の１つと関連する複数のバンクに分割できる。これは有利なことに、アクセス速度を改善し、マルチポート・メモリの必要性を不要にする。さらに、情報検索アーキテクチャーの異なる部分、たとえば、ハッシング・モジュールと符号化された値の表は、異なる段階にパイプライン方式で接続可能であり、その結果、従来のランダム・アクセス・メモリ・チップを使用した実現を可能にする。本アーキテクチャーはストリーム・ベースのデータ・フローを使用することが可能であり、深いパイプライン方式によって非常に高いスループットを実現することができる。
【０００８】
本発明の他の実施態様によれば、検索値の表と、関連する入力値の表は符号化された値の表より小さくすることが可能であり、その結果、
【０００９】
【数１】
2007524946.tif 000003
【００１０】
を検索値の数として、数符号化された表の幅は少なくとも
【００１１】
【数２】
2007524946.tif 000004
【００１２】
である。これは有利なことに、表に使われるメモリを減らす。符号化された値の表は、検索値の表に対する順次アドレス生成を使用して構成されるのが好ましい。
【００１３】
本発明の他の実施態様によれば、入力値をハッシンク・モジュールに渡す前に、入力値に対してプレフィルターリングを行うフィルターリング・モジュールを設けることができる。フィルターリング・モジュールは、入力値が入力値の何らかのフィルターリングされた集合のメンバーではない場合にのみ、入力値をハッシング・モジュールに転送する。たとえば、限定されるものではないが、入力値のフィルターリングされた集合は、検索集合のメンバーではないと認識される入力値とすることができる。これは、情報検索アーキテクチャーの中の表が、入力値が検索集合の一部である場合にのみアクセスされるので、大幅な電力削減につながることができる。たとえば、入力値が第３の表を使用することによって検索集合の一部ではないと認識されるとき、入力値のフィルターリングされた集合に値を加えることができる。フィルターリング・モジュールは他の目的のためにも使用できる。たとえば、フィルターリング・モジュールは、一定の入力値を、ハッシング・モジュールに転送される他のより有利な値の中に再配置するように構成できる。入力値のフィルターリングされた集合は、符号化された値の第１の表の構築を容易にするように選択できる。たとえば、入力値が最後に、符号化された値の第１の表中の１つの単集合の位置にも対応しない複数のハッシュされた値を生成すると、これは表の再構築を複雑にすることがある。この値を入力値のフィルターリングされた集合に加え、その値をスピルオーバー(spillover)・テーブルで別に処理するのが有利なことがある。
【００１４】
本発明の他の実施態様によれば、スピルオーバー・テーブルは、アーキテクチャーによって処理されるべきでないのが好ましい入力値を処理するように、情報検索アーキテクチャーと結合することが可能である。たとえば、スピルオーバー・テーブルは、アーキテクチャーの設定を困難にする、あるいは誤ポジティブのようにアーキテクチャーに対する困難の原因となる入力値のエントリを有する恐れがことがある。面倒な入力値は、スピルオーバー・テーブルによって、情報検索アーキテクチャーにとってもっと容易に処理できる値に再配置することができる。誤ポジティブをもたらす値のような、情報検索アーキテクチャーによって問題であると判別された値は、スピルオーバー・テーブルに帰還し、電力節減のために遮断することが可能である。
【００１５】
本アーキテクチャーの１つの有利な用途はネットワーク・ルーターである。ネットワーク・ルーターは、パケット・ヘッダに対して最長のプレフイックス・マッチングを行える複数のフィルターを実現するこのようなアーキテクチャーを使用して容易に構築することができる。ここで、入力値は予め指定された長さのプレフイックスであり、検索値は転送情報である。有利な構造は、並列に動作する各プレフイックス長に対して１つずつ、複数のフィルターを使用することである。これらフィルターのいくつかが一致を示す場合には、最長のプレフイックス一致を示すフィルターから転送情報を選択するために、プライオリティ・エンコーダを使用することができる。これらフィルターは対で実現でき、この場合、アップデート・フィルターは、オフラインで更新し、検索を行っているフィルターと交換可能である。
【００１６】
ここに開示した、コンテンツ・ベースの情報検索アーキテクチャーは、ハードウェアあるいはソフトウェアあるいは両者の有利な組み合わせで容易に実現できる。インプリメンテーションは有利なことに、埋込みメモリを使用する単一チップの解決法、あるいは外付けのＳＲＡＭ／ＤＲＡＭを使用するマルチチップの解決法で具体化できる。上述したアーキテクチャーは、関連する技術に対して多くの重要な利点を有する。上述のように、本構造はＳＲＡＭあるいはＤＲＡＭのような標準の廉価なメモリ部品を使用することが可能であり、その結果製造が容易である。本構造は、ハードウェア依存性のないストリーミング・データを使用し、また、高スループットを得るために深いパイプライン方式で接続可能であるから、高速が可能である。さらに、本構造は等価なＴＣＡＭ部品よりも消費電力が著しく少ない。本発明の以上のまたは他の利点は、以下の詳細な説明と添付図面を参照することによって当業者にとって明白であろう。
【発明を実施するための最良の形態】
【００１７】
図１は、本発明の一実施形態によるコンテンツ・ベース情報検索アーキテクチャーを示す図である。図１に示すように、入力値１０１が本アーキテクチャーによって受信され、処理される。入力値１０１の処理にもとづいて出力されるものは、表１２０から検索された検索値１０２、あるいは、入力値１０１が検索集合（lookup set）のメンバーではないとの信号１０３、１０４のいずれかである。
【００１８】
図１には、３つの表１１０、１２０、１７０があり、その構造と動作をここにおいてより詳細に説明する。図１の各表は同数のエントリを有するが、ここにさらに説明し、また本発明の他の実施形態によるように、各表は異なる数のエントリを有することもできる。表１２０は、ここではルックアップ・テーブルと呼ばれ、それぞれが検索値を格納する複数のエントリを有する。たとえばルーターの用途の場合には、検索値は異なるデスティネーション・アドレス・プレフイックスと組み合わされた次ホップ情報であってよい。表１７０は、ここでは誤ポジティブ表（あるいはフィルターリング・テーブル）と呼ばれ、表１２０の検索値に対応する入力値を格納する複数のエントリを有する。表１１０は、ここでは「符号化」表と呼ばれる。符号化表１１０は、以下により詳細に説明するように、特定の予め定義された検索集合内のすべての有効な入力値と、ルックアップ・テーブル１２０内の固有の位置との間に１対１のマッピングが存在するように構成される。
【００１９】
入力値１０１と関連する値１０２を検索するために、入力値１０１は、
【００２０】
【数３】
2007524946.tif 000005
【００２１】
個の異なる値を生成するように、１３０において
【００２２】
【数４】
2007524946.tif 000006
【００２３】
回ハッシュされる。ハッシュ１３０は、任意の有利なハッシュ関数を使用して実現可能である。たとえば、そして限定することなく、良好な疑似ランダム行動を有する非常に有効なハッシュを得るために、循環シフト、ＸＯＲ、およびＡＤＤの組み合わせが使用できる。
【００２４】
【数５】
2007524946.tif 000007
【００２５】
個の異なるハッシュ値、
【００２６】
【数６】
2007524946.tif 000008
【００２７】
は、それぞれ符号化表１１０内の位置を指している。各
【００２８】
【数７】
2007524946.tif 000009
【００２９】
は間隔
【００３０】
【数８】
2007524946.tif 000010
【００３１】
内にあり、ここで
【００３２】
【数９】
2007524946.tif 000011
【００３３】
は符号化表１１０およびルックアップ・テーブル１２０内のエントリの数である。符号化表１１０内の各エントリは、値
【００３４】
【数１０】
2007524946.tif 000012
【００３５】
を格納している。
【００３６】
【数１１】
2007524946.tif 000013
【００３７】
個のハッシュ値によって選択された値
【００３８】
【数１２】
2007524946.tif 000014
【００３９】
は、次式の値を得るために、１４０においてビットごとに排他的論理和演算される。
【００４０】
【数１３】
2007524946.tif 000015
【００４１】
この値は、入力値１０１が検索集合の一部であるか否かを調べるために、および／または、ルックアップ・テーブル１２０内の入力値１０１と関連する検索値を選択するために使用できる。これを図１に示す。図１において、この値は１５０において調べることができる。この値は、
【００４２】
【数１４】
2007524946.tif 000016
【００４３】
個のハッシュ関数の１つのインデックス、たとえば
【００４４】
【数１５】
2007524946.tif 000017
【００４５】
を表し、インデックス
【００４６】
【数１６】
2007524946.tif 000018
【００４７】
がハッシュ関数の数より大きいか否かを判定することによってチェックされる。もしそうであれば、入力
【００４８】
【数１７】
2007524946.tif 000019
【００４９】
はルックアップ・テーブルに格納されている集合のメンバーではなく、したがって、表には存在せず、信号１０３が生成される。他方、インデックス
【００５０】
【数１８】
2007524946.tif 000020
【００５１】
が有効なインデックスを指していれば、
【００５２】
【数１９】
2007524946.tif 000021
【００５３】
が
【００５４】
【数２０】
2007524946.tif 000022
【００５５】
でハッシュされるとき、インデックス
【００５６】
【数２１】
2007524946.tif 000023
【００５７】
は
【００５８】
【数２２】
2007524946.tif 000024
【００５９】
が格納される第２の表１２０の中にアドレス
【００６０】
【数２３】
2007524946.tif 000025
【００６１】
を生成する。ルックアップ・テーブル１２０内のアドレス
【００６２】
【数２４】
2007524946.tif 000026
【００６３】
は、１６０において正しいハッシュ関数の出力を選択するために、該インデックスを使用することによって得られる。次に、ルックアップ・テーブル１２０内のアドレス
【００６４】
【数２５】
2007524946.tif 000027
【００６５】
は、入力値
【００６６】
【数２６】
2007524946.tif 000028
【００６７】
と組み合わされた検索値
【００６８】
【数２７】
2007524946.tif 000029
【００６９】
を検索するために、使用することができる。
【００７０】
しかし、以下に説明するように、入力値１０１が検索集合の一部ではないのに、１５０におけるチェックに合格する確率が少しある。したがって、ルックアップ・テーブル１２０と同数のエントリを有することができる第３の表１７０が備えられている。符号化表１１０がセツトアツプされると、検索集合内の実際の入力値を表１７０に格納できる。入力値
【００７１】
【数２８】
2007524946.tif 000030
【００７２】
の場合、
【００７３】
【数２９】
2007524946.tif 000031
【００７４】
に対応するハッシュ関数インデックスを符号化表１１０中に符号化でき、検索情報
【００７５】
【数３０】
2007524946.tif 000032
【００７６】
はルックアップ・テーブル１２０のアドレス
【００７７】
【数３１】
2007524946.tif 000033
【００７８】
に格納でき、
【００７９】
【数３２】
2007524946.tif 000034
【００８０】
自身は表１７０のアドレス
【００８１】
【数３３】
2007524946.tif 000035
【００８２】
に格納できる。ヘッダ
【００８３】
【数３４】
2007524946.tif 000036
【００８４】
に対する検索がルックアップ・テーブル１２０の中に有効なポインタを生成すれば、
【００８５】
【数３５】
2007524946.tif 000037
【００８６】
は１８０において表１７０に格納された実際の関連する入力値と比較される。
【００８７】
【数３６】
2007524946.tif 000038
【００８８】
が異なっていれば、検索は誤ポジティブであり、信号１０４が生成される。
【００８９】
領域
【００９０】
【数３７】
2007524946.tif 000039
【００９１】
と範囲
【００９２】
【数３８】
2007524946.tif 000040
【００９３】
が所与のものとすると、図１に示す構造は、
【００９４】
【数３９】
2007524946.tif 000041
【００９５】
の任意の要素
【００９６】
【数４０】
2007524946.tif 000042
【００９７】
についての問合せが
【００９８】
【数４１】
2007524946.tif 000043
【００９９】
の検索値をもたらすように、任意の関数を符号化する
【０１００】
【数４２】
2007524946.tif 000044
【０１０１】
働きをする。領域
【０１０２】
【数４３】
2007524946.tif 000045
【０１０３】
内にない任意の
【０１０４】
【数４４】
2007524946.tif 000046
【０１０５】
は、誤ポジティブなしとフラグを付けられる。
【０１０６】
符号化表１１０の構築は、多くの異なる方法で進行することができる。入力値
【０１０７】
【数４５】
2007524946.tif 000047
【０１０８】
と、関連するインデックス値
【０１０９】
【数４６】
2007524946.tif 000048
【０１１０】
を所与のものとすれば、
【０１１１】
【数４７】
2007524946.tif 000049
【０１１２】
に対する下記の式は符号化表１１０の値に対する線形の制約条件を定めている。入力値の集合と、関連するインデックスは線形の制約条件の系（system of linear constraints）を定め、これらの線形の制約条件は、線形の制約条件を解く文献で公知の多くの方法の任意のものを使用して解くことが可能である。あるいは、非常に高い確率で動作する下記の非常に高速な方法を使用できる。符号化表１１０は、検索集合内のすべての要素
【０１１３】
【数４８】
2007524946.tif 000050
【０１１４】
とルックアップ・テーブル１２０内の固有のインデックス
【０１１５】
【数４９】
2007524946.tif 000051
【０１１６】
の間に１対１のマッピングが存在するように、構築される。このマッチング値
【０１１７】
【数５０】
2007524946.tif 000052
【０１１８】
は、ハッシング
【０１１９】
【数５１】
2007524946.tif 000053
【０１２０】
によって生成されたハッシュされた位置
【０１２１】
【数５２】
2007524946.tif 000054
【０１２２】
の１つであることが必要である。表エントリの任意の設定が所与のものとすれば、
【０１２３】
【数５３】
2007524946.tif 000055
【０１２４】
に関連する線形の制約条件は、次式を設定することによって満たすことが可能である。
【０１２５】
【数５４】
2007524946.tif 000056
【０１２６】
しかし、
【０１２７】
【数５５】
2007524946.tif 000057
【０１２８】
の符号化表１１内のエントリを変えると、制約条件が既に満たされている異なる入力値に対する線形の制約条件の違反を起こすことがある。これを避けるために、入力要素の集合に対して順序付けが計算されるべきである。この順序付けは、他の入力値
【０１２９】
【数５６】
2007524946.tif 000058
【０１３０】
が順序において
【０１３１】
【数５７】
2007524946.tif 000059
【０１３２】
より先行していれば
【０１３３】
【数５８】
2007524946.tif 000060
【０１３４】
に関連するハッシュ値のいずれもが
【０１３５】
【数５９】
2007524946.tif 000061
【０１３６】
と等しくないという性質を有している。このようなマッチングと順序付けが所与のものとすれば、順序に従う入力要素に対する線形の制約条件は満たされることになる。さらに、各々の
【０１３７】
【数６０】
2007524946.tif 000062
【０１３８】
に対する制約条件は、既に満たされている制約条件を破ることなく
【０１３９】
【数６１】
2007524946.tif 000063
【０１４０】
を修正することによってのみ満たされることになる。この処理の終了時に、線形の制約条件は全て満たされることになる。
【０１４１】
順序付けと
【０１４２】
【数６２】
2007524946.tif 000064
【０１４３】
は、以下のように計算することができる。
【０１４４】
【数６３】
2007524946.tif 000065
【０１４５】
を入力要素の集合であるとする。符号化表内の位置
【０１４６】
【数６４】
2007524946.tif 000066
【０１４７】
は、それが
【０１４８】
【数６５】
2007524946.tif 000067
【０１４９】
の中の正確に１つの
【０１５０】
【数６６】
2007524946.tif 000068
【０１５１】
に対するハッシュされた位置であれば、
【０１５２】
【数６７】
2007524946.tif 000069
【０１５３】
に対して単集合の位置であると言える。
【０１５４】
【数６８】
2007524946.tif 000070
【０１５５】
は、ハッシュされた位置が
【０１５６】
【数６９】
2007524946.tif 000071
【０１５７】
に対する単集合位置を含む
【０１５８】
【数７０】
2007524946.tif 000072
【０１５９】
内の
【０１６０】
【数７１】
2007524946.tif 000073
【０１６１】
からなる
【０１６２】
【数７２】
2007524946.tif 000074
【０１６３】
と、ハッシュされた位置が
【０１６４】
【数７３】
2007524946.tif 000075
【０１６５】
に対する単集合位置を含まない
【０１６６】
【数７４】
2007524946.tif 000076
【０１６７】
内の
【０１６８】
【数７５】
2007524946.tif 000077
【０１６９】
からなる
【０１７０】
【数７６】
2007524946.tif 000078
【０１７１】
の、２つの部分に分割することができる。
【０１７２】
【数７７】
2007524946.tif 000079
【０１７３】
内の各
【０１７４】
【数７８】
2007524946.tif 000080
【０１７５】
に対して、
【０１７６】
【数７９】
2007524946.tif 000081
【０１７７】
は単集合位置の１つであると設定される。
【０１７８】
【数８０】
2007524946.tif 000082
【０１７９】
内の各入力値は、
【０１８０】
【数８１】
2007524946.tif 000083
【０１８１】
内のすべての入力値の後であるように順序付けられる。
【０１８２】
【数８２】
2007524946.tif 000084
【０１８３】
内の順序付けは任意でよい。次に、
【０１８４】
【数８３】
2007524946.tif 000085
【０１８５】
に対するマッチングと順序付けは、再帰的に確認することができる。したがって、
【０１８６】
【数８４】
2007524946.tif 000086
【０１８７】
は
【０１８８】
【数８５】
2007524946.tif 000087
【０１８９】
の２つの集合に分割できる。
【０１９０】
【数８６】
2007524946.tif 000088
【０１９１】
はハッシュされた位置が
【０１９２】
【数８７】
2007524946.tif 000089
【０１９３】
に対する単集合位置を含む
【０１９４】
【数８８】
2007524946.tif 000090
【０１９５】
内の
【０１９６】
【数８９】
2007524946.tif 000091
【０１９７】
からなり、
【０１９８】
【数９０】
2007524946.tif 000092
【０１９９】
は
【０２００】
【数９１】
2007524946.tif 000093
【０２０１】
の残りの要素からなる。
【０２０２】
【数９２】
2007524946.tif 000094
【０２０３】
に対して単集合位置ではない位置が、
【０２０４】
【数９３】
2007524946.tif 000095
【０２０５】
に対しては単集合位置である場合があることに留意すべきである。
【０２０６】
【数９４】
2007524946.tif 000096
【０２０７】
内のすべての入力値
【０２０８】
【数９５】
2007524946.tif 000097
【０２０９】
にマッチング値
【０２１０】
【数９６】
2007524946.tif 000098
【０２１１】
が与えられるまで、処理は続く。もしも処理の早い段階で、単集合位置にハッシュする要素が確認されなければ、処理は失敗したと見なされる。しかし、符号化表が十分に大きければ、このようなマッチングと順序付けが存在し、処理によって高い確率で確認されるであろう。実際、符号化表の大きさは、何らかの初期サイズ、たとえば、入力値の数のある一定の倍数に設定可能である。マッチングが確認されなければ、マッチングが確認されるまで、表のサイズを繰り返し大きくしてもよい。実際、これは、所与のメモリ・チップの異なる部分を割り当てることによって行われる。ハッシュされた位置の間の偶然の一致のために、十分に大きいサイズの表でも処理が失敗する可能性が僅かに存在する。この場合、使用されたハッシュ関数を変更することが可能である。シード（seed）を有するハッシュ関数を使用することができる。値を検索するには、符号化表の構築の間に使用したハッシュ関数と同じハッシュ関数を使用しなければならないことに留意されたい。
【０２１２】
上記のすべての方法が失敗すれば、いくつかの入力値を抜かしてもよい。具体的にいうと、２つ入力ポインタを有する表
【０２１３】
【数９７】
2007524946.tif 000099
【０２１４】
内のエントリをチェックでき、入力ポインタの原因である要素の１つは要素の集合から除去できる。これは、
【０２１５】
【数９８】
2007524946.tif 000100
【０２１６】
をある
【０２１７】
【数９９】
2007524946.tif 000101
【０２１８】
に対する
【０２１９】
【数１００】
2007524946.tif 000102
【０２２０】
にし、その結果、セツトアツプ手順の収束の機会を増大させる。これは、利用可能なメモリに適合できないヘッダが除外されるＴＣＡＭに類似していることに留意されたい。本アーキテクチャーは、除外した入力値を報告し、それらを特殊な場合として処理することができる。以下にさらに説明するように、このような入力値はスピルオーバー・テーブルで処理できる。
【０２２１】
図１に示すアーキテクチャーの１つの利点は、誤ポジティブを除外することができることである。誤ポジティブ表１７０とその関連する論理は省略可能であり、その場合には、僅かな確率で誤ポジティブを可能にする図２に示すアーキテクチャーとなる。図１のアーキテクチャーの実効速度は、追加の表１７０が誤ポジティブを除外するために使用されるか否かとは無関係であることに留意すべきである。
【０２２２】
誤ポジティブは、情報検索アーキテクチャーにとって許容可能な条件であってもなくてもよい。誤ポジティブが発生する場合には、検索結果は、考えられる検索値の１つのランダムな選択であることに留意すべきである。このように、このような検索メカニズムを使用するルーターは、デフォルトのデスティネーションではなくランダムなデスティネーションに転送情報がないパケットを送信することになる。このような動作は、帯域制限された経路、たとえば、デスティネーションがサービス品質を指定されたパケットのみに使用されることを予想した経路に対して潜在的に余分なトラフィックを加えることがある。幸いにも、この確率は小さい。完全にランダムなハッシュ関数の場合、符号化表２１０が
【０２２３】
【数１０１】
2007524946.tif 000103
【０２２４】
ビット幅であり、かつ
【０２２５】
【数１０２】
2007524946.tif 000104
【０２２６】
個のハッシュ関数を有するならば、誤ポジティブの確率に対する理論的上限は次式で示すことができる。
【０２２７】
【数１０３】
2007524946.tif 000105
【０２２８】
したがって、４つのハッシュ関数を有する３２ビット幅の表の場合、誤ポジティブ率の限界は１０億中４、すなわち、表に存在しない１０億ヘッダごとに４ヘッダが誤ポジティブの恐れがあるが、他のヘッダは表に存在しないとしてフラグを正確に立てられるであろう。さらに、連続した誤ポジティブの確率は指数関数的に減少する。言い換えれば、所与の入力値が２つ以上の連続した誤ポジティブに遭遇する見込みは全くない。さらに、誤ポジティブに遭遇した２個のパケット・ヘッダ値が、帯域制限された同じ経路に沿って送信される見込みもない。
【０２２９】
図１および図２に示す情報検索アーキテクチャーは、図４から図６に示すように、ネットワーク・ルーターへの応用に特に有利である。図４は、本発明のこの態様の実施形態によるネットワーク・ルーター４００のアーキテクチャーを示す。
【０２３０】
ルーター４００は、インターネット・プロトコル（ＩＰ）データグラムのようなパケットを転送するために、最長プレフイックスマッチング（ＬＰＭ）を使用するように構成されている。ルーティング表は、長さが
【０２３１】
【数１０４】
2007524946.tif 000106
【０２３２】
であり、ＩＰアドレスの最初の
【０２３３】
【数１０５】
2007524946.tif 000107
【０２３４】
ビットからなる複数のプレフイックスを処理するようにセットアップされている。より短いプレフイックスはより長いプレフイックスを含むことが可能である、すなわち、より長いプレフイックスはより短いプレフイックスの転送情報を改良する（refine）ことが可能である。したがって、検索が、入力ＩＰアドレスがより長い考えられるプレフイックスと一致するか否かを判定するように実行されなければならない。図４の基本的なアーキテクチャーは、各々固有のプレフイックス長に対して検索フィルター４１１，．．．４１５を有し、各検索フィルターは上述のコンテンツ・ベース情報検索アーキテクチャーにもとづいている。検索フィルター４１１，．．．４１５は、それらの指定された長さに対応するプレフイックスでセットアップされる。動作中、入力問い合わせ４０１はすべてのフィルター４１１，．．．４１５に並行して送られ、各フィルター４１１，．．．４１５からの結果はプライオリティ・エンコーダ４４０に送られる。いくつかのフィルターは「肯定出力」（すなわち、少ない誤ポジティブ確率でプレフイックスとの一致を示す）を表示するが、他のフィルターは肯定出力を表示しない。一致を示すフィルターの中から、最長のプレフイックスに対応する出力が、入力問い合わせに対する転送情報として使用される。
【０２３５】
通常の転送動作に加えて、ルーターはそれらのテーブルを頻繁に更新する必要がある。エントリは連続的に除去され、他のエントリが加えられる。経路選択の更新を行うためには、フィルター４２１，．．．４２５の他の（平行な）集合を保持することが有利である。これらのフィルター４２１，．．．４２５はアップデート・テーブルと呼ばれ、他のフィルター４１１，．．．４１５は転送テーブルと呼ばれる。個々のプレフイックス長は、１つのアップデート・テーブルと１つの転送テーブルを有する。転送テーブルは能動的にパケットを転送し、アップデート・テーブルはルーティング・アップデートをオフラインで実行する。十分な数の更新が行われると、テーブルの役割は交換することができる。アップデート・テーブルは「オンラインにされ」、すなわち、転送テーブルにされ、転送テーブルはアップデート・テーブルの役目をする。２つのテーブル内のエントリは、交換の時点で同一であるべきことに留意されたい。これを保証するために、転送テーブルは交換の前にアップデート・テーブルからすべてのエントリを更新するべきである。
【０２３６】
ネットワーク・ルーターにおいては、要素は常時除去され、かつ追加される。ルーター４００への更新は、ハードウェアとソフトウェア技術の組み合わせを使用して行うことが可能である。たとえば、上記の連想記憶装置がヘッダの転送情報を追加し、除去し、変更することを可能にするために、次の方式が使用できる。
【０２３７】
ヘッダの追加
新しいヘッダ
【０２３８】
【数１０６】
2007524946.tif 000108
【０２３９】
が、いくつかの要素を使用して既にセツトアツプされている検索フィルターに追加されなければならない場合には、
【０２４０】
【数１０７】
2007524946.tif 000109
【０２４１】
が確認されなければならない。もし
【０２４２】
【数１０８】
2007524946.tif 000110
【０２４３】
が、表内にハッシュすべき他の
【０２４４】
【数１０９】
2007524946.tif 000111
【０２４５】
も存在しないハッシュ値
【０２４６】
【数１１０】
2007524946.tif 000112
【０２４７】
を有するならば、
【０２４８】
【数１１１】
2007524946.tif 000113
【０２４９】
は
【０２５０】
【数１１２】
2007524946.tif 000114
【０２５１】
に対する有望な候補である。しかし、
【０２５２】
【数１１３】
2007524946.tif 000115
【０２５３】
がこのようなハッシュ値を有しなければ、フィルターを再びセットアップする必要がある（あるいは、後に述べるように、それをスピルオーバー・テーブルに挿入してもよい。）これは、埋め込みプロセッサあるいは付属プロセッサを使用して、たとえばソフトウェアで、行うことが可能である。これはアップデート・テーブルを使用してオフラインで行うことも可能であり、したがって、検索のスループットに影響を与える必要はない。
【０２５４】
ヘッダの除去
要素の除去は、ソフトウェアの支援無しで可能である。各々のフィルター・テーブル・エントリは、「ダーティ・ビット（dirty bit）」および、そのエントリを指向するハッシュされた位置の番号のカウントを使用して増大することができる。要素
【０２５５】
【数１１４】
2007524946.tif 000116
【０２５６】
が除去される場合、
【０２５７】
【数１１５】
2007524946.tif 000117
【０２５８】
のすべてのハッシュされた位置に対応するダーティ・ビットはオンされる。同時に、該カウントはデクリメントされ、
【０２５９】
【数１１６】
2007524946.tif 000118
【０２６０】
のエントリに対して１つ少ないハッシュされた位置点をを示す。要素
【０２６１】
【数１１７】
2007524946.tif 000119
【０２６２】
の検索は、
【０２６３】
【数１１８】
2007524946.tif 000120
【０２６４】
のハッシュされた位置のすべてのダーティ・ビットが１ではないことを保証しなければならない。新しい要素
【０２６５】
【数１１９】
2007524946.tif 000121
【０２６６】
が表に追加された場合、そのハッシュされた位置のすべては、そのダーティ・ビットをリセットしなければならない。要素の除去は、追加される必要がある要素に対する
【０２６７】
【数１２０】
2007524946.tif 000122
【０２６８】
を発見する確率を増加させることに留意されたい。
【０２６９】
転送情報の変更
要素
【０２７０】
【数１２１】
2007524946.tif 000123
【０２７１】
に対する転送情報の変更は、図１に示す実施形態では、ささいなことである。データ構造を別々な表１１０と１２０に分離することは、それが、符号化表１１０に影響を与えずに、ルックアップ・テーブル１２０を容易に更新することを可能にする点で有利である。ヘッダに対する転送情報を変更する必要があれば、ルックアップ・テーブル１２０内の関連する位置を更新することだけが必要である。これは、たとえば、ハードウェアで、容易に行える。
【０２７２】
【数１２２】
2007524946.tif 000124
【０２７３】
が符号化表１１０に符号化される場合にのみ、構造全体を再度セットアップすることが必要である。
【０２７４】
図５は、図１に示す情報検索アーキテクチャーの構造を利用する、本発明の他の実施形態による、ネットワーク・ルーター５００の他のアーキテクチャーを示す。各プレフイックス長に対してデスティネーション・アドレス検索を完全に行って転送テーブル・フィルターを実現するよりも、プライオリティ・エンコーダ５６０が最長プレフイックス一致を選択した後にのみ関連するルックアップ・テーブル５２１，．．．または５２５上で検索を行うことが有利である。したがって、検索フィルターは符号化表５１１，．．．５１５、ならびに、望む場合には、誤ポジティブ表５３１，．．．５３５を実行することだけが必要である。さらに、図５に示すように、アップデート・テーブルは有利なことに、符号化表５４１，．．．５４５のオフライン版を使用して実行することのみが必要である。以下にさらに詳細に開示し説明するように、ルックアップ・テーブルは、オンライン／オフラインのアーキテクチャーに対してルックアップ・テーブルを２重化する必要のない方法で、符号化された表よりも小さく構築できる。
【０２７５】
最悪の場合には、フィルターの数はネットワーク・アドレスのビット数と等しいであろう。たとえば、ＩＰｖ６の場合、これは１２８個のフィルターとなる。しかし、この数は減らすことが可能である。たとえば、長いプレフイックスを収容するために短いプレフイックスを拡張するプレフイックス拡張がいくつかのプレフイックス長を除外するために使用できる。あるいは、極めて少数のメンバーでプレフイックス長を置換するために、簡単なハッシュ・テーブルあるいは直接検索アレイが使用できる。実際には、個々のプレフイックス長の数は僅かである。たとえば、各アドレスが３２ビットであるＩＰｖ４は、およそ８個ないし１０個の能動的なプレフイックス長を有し、ＩＰｖ６では通常１４個の個々のプレフイックス長を記録することが明らかになっている。これらは、上述の方式を使用して、さらに削減できる。
【０２７６】
所与のルーターにおいて、すべてのプレフイックス長が等しい頻度では発生するとは限らない。通常、少数のプレフイックス多くの時間に発生し、いくつかのプレフイックス長は全く発生しない。したがって、いくつかのフィルターが相対的に「過密」である可能性がある。フィルターを設定し誤ポジティブ率を維持するために、いくつかのフィルターは他のフィルターよりも多くのメモリを必要とする。すべてのフィルター・チップに等しく近接して基板上にＤＲＡＭメモリを配置することは有利であるかもしれない。ルーターの構成の間に、すなわち、始動の前に、特定のフィルターにメモリ・バンクを適切に割り当てるために、ＩＰアドレスのプロファイルを使用することができる。したがって、頻度の高いプレフイックス長を処理するフィルターに多くのバンクを割り当て、他のフィルターには少数のバンクを割り当てることが可能である。これは、経路選択アップデートの間に、動的に変更可能であることに留意されたい。たとえば、特定のフィルターのサイズが大きくなり他のフィルターのサイズが小さくなれば、いくつかのメモリ・バンクを「再割り当てする」ことができる。このようにして、基板は最高の自由度を保持するために実行中に再構成できる。図６は、関連するプロセッサ６７０および他の関連する回路に加えて、従来のＤＲＡＭ６５１，．．．，６５４を使用し、上述のコンテンツ・ベースの情報検索アーキテクチャーを実行するいくつかの連想記憶装置６４１，．．．，６４４を示すライン・カード６００のアーキテクチャーの例を示している。
【０２７７】
図１および図２に示すアーキテクチャーは、図３に示すように、セグメント化されたメモリと細粒度パイプライン方式（fine-grained pipelining）を利用することによって、さらに最適化してもよい。
【０２７８】
図１のように、入力値３０１は、
【０２７９】
【数１２３】
2007524946.tif 000125
【０２８０】
個の異なる値を作るために、３３０において
【０２８１】
【数１２４】
2007524946.tif 000126
【０２８２】
回ハッシュされる。しかし、
【０２８３】
【数１２５】
2007524946.tif 000127
【０２８４】
個の異なるハッシュ値は、図１の１１０のような１つの一体の符号化表内の位置を指していない。高速なメモリ・アクセス速度を維持するために、各メモリ・バンクに対す読み出しおよび書き込みポートの数を減らすことが望ましい。図３に示すように、アーキテクチャー内の各表のメモリを
【０２８５】
【数１２６】
2007524946.tif 000128
【０２８６】
個またはそれよりも多いバンクに分配することが有利なことがある。ここで、
【０２８７】
【数１２７】
2007524946.tif 000129
【０２８８】
はハッシュ関数の数である。各ハッシュ関数は固有のメモリ・セグメントを示し、したがって、特定のバンクにアクセスする必要がある。同じように、符号化表３１０内の各バンク３１１，３１２，．．．．３１５は、正確に１つの読み出しおよび書き込みポート（すなわち、標準のメモリ部品のように）のみを有する必要があり、したがって、マルチポート・メモリを不要にし、アクセス・スピードを改善する。この構造が、誤ポジティブ率あるいは所要のメモリ・サイズに不利な影響を与えないことはシミュレーションから示すことができる。
【０２８９】
細粒度パイプライン方式のハードウェア・アーキテクチャーを生成するために、情報検索アーキテクチャーの構造を利用することも可能である。図３は、ハードウェアがパイプラインで接続される異なる段階を示す。図３に示すように、トライあるいはハッシュ・テーブルのハードウェア実現と異なり、この方法には依存あるいは不確定な衝突連鎖がない。ハードウェア実現は、データのストリーミングを可能にし、高度にパイプラインで接続されたインプリメンテーションを可能にし、またパイプラインで接続されたメモリ・アクセスを可能にする。したがって、メモリは従来のオフチップＤＲＡＭを使用して実現できる。毎秒４億回を超えるアクセスの有効スループットを可能にするダブル・データ・レートのＤＲＡＭおよびＲＡＭＢＵＳメモリは、魅力的な選択である。
【０２９０】
ハッシュ関数およびＸＯＲ計算も、パイプライン方式としてもよい。図１３は、ストリング・ハッシュ関数のインプリメンテーションと、考えられるパイプライン方式のインプリメンテーションを示す。１つのオペランドが定数であるので、乗算器は単純化されている。さらに、乗算器も同様にパイプライン方式としてもよい。複数のプレフイックスは異なる長さであるので、短いプレフイックス上で動作しているハッシュ関数は、他のハッシュ関数と「歩調を揃える」ために追加の遅延段階を必要とすることに留意されたい。この特徴は、ハッシュ関数に対して非常に有効なストリーム・ベースのアーキテクチャーを設計するために、使用することができる。図１３は、ストリングハッシュ関数と、ｉ’番目のハッシュ関数のためのパイプライン方式の実現例を示す。
【０２９１】
本アーキテクチャーのハードウェア・インプリメンテーションで使用されるメモリの量は、埋め込みメモリとオフチップ・メモリとのトレードオフを決定するための重要な事項である。図１に示すアーキテクチャーのメモリ・サイズは、符号化表１１０とルックアップ・テーブル１２０、さらに、もし存在すればヘッダ・テーブル１７０の合成されたサイズである。符号化表１１０は、検索構造をセットアップするのを可能にするのに必要なだけ大きくする必要がある、すなわち、すべての要素は一致τを持たねばならない。さらに、符号化表１１０の幅
【０２９２】
【数１２８】
2007524946.tif 000130
【０２９３】
は、誤ポジティブ率（これは、上述のように、
【０２９４】
【数１２９】
2007524946.tif 000131
【０２９５】
に逆比例する）を減少させるために必要なだけ大きくするべきである。５００,０００個のエントリを含むセグメント化されたメモリを使用する実施形態は、それぞれ２４ビット幅の百万個のエントリを符号化表１１０内に有するであろう。ルックアップ・テーブル１２０も、それぞれ対応する検索情報を保有している百万個のエントリを有するであろう（以下に説明する、小規模なルックアップ・テーブルのための実施形態が使用されない限り）。検索情報は通常小さい、すなわち８ビットであると仮定して、２つのテーブルを合計して約４ＭＢであると予想できる。最近のＡＳＩＣおよびメモリ技術を使用して、メモリは埋め込みＳＲＡＭとしてオンチップで実現することが可能である。より多くのメモリが必要であれば、（たとえば、より多くのエントリをフィルターに格納する必要があれば）オフチップＤＲＡＭを使用してもよい。上述のように、ストリーミング・データおよびパイプライン方式のインプリメンテーションは、ダブル・データ・レートＤＲＡＭの使用が高スループットを達成することを可能にする。
【０２９６】
メモリの使用量を減らす技術は、図１および図２に示すアーキテクチャーを、２つの表ではなく、符号化表とルックアップ・テーブルの単一の表を用いて実現することである。２つの表があれば、要素と関連する検索値を更新するフレキシビリティがもたらされる。たとえば、ネットワークの用途においてＩＰアドレスの転送情報を更新することのみが必要であれば、ルックアップ・テーブル１２０内の対応するエントリのみを修正する必要がある。しかし、多くのＩＰルートにおいて、更新は多くの場合新しいアドレスの挿入、あるいは古いアドレスの削除を伴う。もしそうならば、図１のルックアップ・テーブル１２０は不要にできる。代わりに、符号化表１１０は実際の値を使用して構成することができ、得られた値が正しい検索をもたらすように、他のエントリと適切に排他的論理和演算をすることができる。この技術は、メモリの２５％を節約することができる。
【０２９７】
メモリの使用量を減らす他の技術が図７Ａおよび７Ｂに示されている。図７Ａは、図１に関して既に説明したように、ルックアップ・テーブル７２０と誤ポジティブ表７７０が符号化表７１０と正確に同じ深度である実施形態を示している。それぞれが
【０２９８】
【数１３０】
2007524946.tif 000132
【０２９９】
個のエントリを有し、符号化表は
【０３００】
【数１３１】
2007524946.tif 000133
【０３０１】
の幅を有する。ここで、
【０３０２】
【数１３２】
2007524946.tif 000134
【０３０３】
は格納する必要があるエントリの数であり、
【０３０４】
【数１３３】
2007524946.tif 000135
【０３０５】
はハッシュ関数の数である。本発明の他の実施形態にしたがって、および図７Ｂを参照すると、符号化表は有利な方法でそのサイズを変更することができる。ハッシュ関数を使用してインデックスをルックアップ・テーブルに供給する代わりに、符号化表（図７Ｂの７１５）は、ルックアップ・テーブル（図７Ｂの７２５）の中にインデックス全体を格納することができる。符号化表７１５は少し大きくなるが、ルックアップ・テーブル７２５と誤ポジティブ表７７５のサイズは共に小さくする。この結果、メモリをかなり節約することになる。
【０３０６】
符号化表７１５のセットアップは、図１および図２に対して既に説明したのと類似の方法で進行することができる。主な相違は、アドレス・ジェネレータがルックアップ・テーブル７２５のために維持されることである。アドレス・ジェネレータは、零に初期化されるカウンタとして容易に実現できる。要素
【０３０７】
【数１３４】
2007524946.tif 000136
【０３０８】
が符号化表７１５に加えられると、アドレス・ジェネレータからのアドレスは、
【０３０９】
【数１３５】
2007524946.tif 000137
【０３１０】
に対するマッチング位置
【０３１１】
【数１３６】
2007524946.tif 000138
【０３１２】
へと符号化される。これは、次のホップ情報、すなわち、より一般的には
【０３１３】
【数１３７】
2007524946.tif 000139
【０３１４】
が格納されるルックアップ・テーブル７２５内のアドレスを表している。
【０３１５】
【数１３８】
2007524946.tif 000140
【０３１６】
が一旦行われると、アドレス・ジェネレータは次の要素のために増分される。
【０３１７】
ルックアップ・テーブル７２５に対してアドレスを順次生成させることの重要な利点は、上記のネットワーク・アプリケーションにおけるオフライン・フィルター用のルックアップ・テーブルと誤ポジティブ表を二重化することが不要になることである。この理由は、ルックアップ・テーブルと誤ポジティブ表に対する変更は非常に軽微でありく、表の２重化を必要としないからである。最悪の場合に、要素
【０３１８】
【数１３９】
2007524946.tif 000141
【０３１９】
を加える必要があるとき、転送テーブル全体をセットアップする必要がある。既に表中にある要素に対するルックアップ・テーブル・インデックスは保持することができる。このように、ルックアップ・テーブルおよび誤ポジティブ表中の変更の必要がある唯一のエントリは、
【０３２０】
【数１４０】
2007524946.tif 000142
【０３２１】
に対するエントリである。この変更は簡単であり、能動的なルックアップ・テーブルおよび能動的な誤ポジティブ表に直接行うことが可能である。
【０３２２】
図７Ｂに示すように、そして本発明の他の実施形態によれば、符号化表７１５は索引付けメカニズムを担当し、フィルターリング・テーブル７７５はフィルターリングを担当する。したがって、これら表は検索の都度アクセスされ、これは消費電力に悪影響を与えることがある。
【０３２３】
図８は、本発明の他の実施形態による他のアーキテクチャーを示す。ヘッダ・テーブルへのアクセスを制限するために、フィルター８９０が情報検索アーキテクチャー８００の前に挿入される。フィルター８９０は、たとえば、ブルーム・フィルターのような、検索集合に対してメンバーシップ問い合わせを行う任意の有利なメカニズムを使用して実現できる。 Bloom B. H.の「許容誤差を有するハッシュ・コーディングにおける空間／時間トレードオフ」（Space/Time Trade-offs in Hash Coding with Allowable Errors）、Communications of the ACM, 13(7), p. 422-26 （１９７０年７月）を参照されたい。フィルター８９０は、プレフィルターリングを行い、表への唯一のアクセスがテーブルに存在すべきエントリ（ならびに、プレフィルター８９０によって許容されることがあるどんな誤ポジティブでも）であることを保証する。上述の最長プレフイックスマッチング用途の場合、この実施形態は追加の利益をもたらす。各検索は、存在するとしても、少数のプレフイックスにのみ存在している可能性がある。したがって、プレフイックス・フィルターの大部分はアクセスされることはないであろうし、その結果、著しく電力を節減する。
【０３２４】
本アーキテクチャーは、図９、１０、および１１に示す、本発明者がスピルオーバー・テーブルと呼ぶ表を使用することによって、さらに改良することが可能である。スピルオーバー・テーブルとは、情報検索アーキテクチャーによって処理できない、あるいは、望ましくは情報検索アーキテクチャーによって処理されるべきではない少数の入力値を有する表である。図９を参照すると、入力値９０１は、上述のアーキテクチャーに類似していても、していなくてもよい何らかの情報検索アーキテクチャー９１０に送られる。９２１，９２２，．．．等のさまざまなエントリを有するスピルオーバー・テーブル９２０がさらに設けられる。入力値９０１がスピルオーバー・テーブル９２０内のエントリと一致すれば、入力値９０１の処理は、情報検索アーキテクチャー９１０の代わりに、スピルオーバー・テーブル９２０によって行われる。
【０３２５】
このような表が有用であることには、さまざまな理由がある。
【０３２６】
表のセットアップ
符号化表を構築する、前述したセットアップメカニズムは、単集合が再帰的なセットアッププロセスの各段階において発見されない場合には失敗する。これは、たとえば、２つの個々の要素のすべての
【０３２７】
【数１４１】
2007524946.tif 000143
【０３２８】
個のハッシュ関数が正確に一致する、起こりそうにもない場合に、起こるであろう。単集合を発見できなければ、ハッシュ値の１つが最下位の入力ポインタを有する表エントリを示す要素を、情報検索アーキテクチャーから除去されるように選択することが可能である。この要素
【０３２９】
【数１４２】
2007524946.tif 000144
【０３３０】
は次に、スピルオーバー・テーブルに挿入できる。ハッシュ関数の一致によって表のセットアップに失敗する確率は、スピルオーバー・テーブルのサイズと共に指数関数的に小さくなることを示すことができる。たとえば、百万エントリ・アーキテクチャーに対するセットアップに失敗する確率はおよそ１０-14である。これは、サイズ１０のセツトアツプ・テーブルを使用すれば、およそ１０-140に減少する。
【０３３１】
単集合がない要素の追加も、スピルオーバー・テーブルを使用して、さらに容易にできる。既にセットアップされている符号化表にこのような要素を加えるためには、符号化表は零から作り直す必要がある。しかし、要素は、スピルオーバー・テーブルにも加えることができる。削除および追加が通常均等に挿入されると仮定すれば、適度のサイズのスピルオーバー・テーブルを有する符号化表を完全に作り直す必要は滅多にないであろう。
【０３３２】
要素の再配置
一般的な問題として、小さなスピルオーバー・テーブルが、表のセットアッププロセスを支援するために、任意の「問題となる」要素を他の要素の中に再配置するために、使用できる。これを、たとえば、図１０に示す。入力値１００１は、まずスピルオーバー・テーブル１０２０に送られる。入力値がスピルオーバー・テーブル１０２０内のエントリの１つと一致すれば、入力値１００１は他の値１００２の中に再配置される。この値１００２はおそらく、ある方法で情報検索アーキテクチャー１０１０に対してより有利であり、正しい検索値を生成するためによって容易に処理できる。
【０３３３】
誤ポジティブの格納
以上のような理由で、誤ポジティブは、識別されるために、すべてのテーブルへのアクセスを必要とする。検索が進行するにつれて、誤ポジティブをもたらす要素は、フィルターリング・アーキテクチャーの初めに近く位置するスピルオーバー・テーブルに格納できる。したがって、これらの要素の将来の検索は、アクセスを１回だけ必要とし、その結果相当量の電力を節減する。
【０３３４】
図１１は、図７Ｂに示したコンテンツ・ベース情報検索アーキテクチャー１１００に加えて、小さなスピルオーバー・テーブル１１９５を有する、１１９０におけるプレフィルターリングの使用を示している。図１２は、異なる処理要素の間の相互作用を例示するフローチャートを示す。図１２に示すように、フィルターリング・テーブル１２０６において識別された誤ポジティブは、１２０１に戻される。表検索をさらに減少するために、１２０２においてプレフィルターリングも使用される。
【０３３５】
上述した情報検索アーキテクチャーは、関連する技術に勝る多くの重要な利点を有している。上述したように、本構造はＳＲＡＭあるいはＤＲＡＭのような標準の廉価なメモリ部品を使用することが可能であり、その結果製造が容易である。本構造は、ハードウェア依存性のないストリーミング・データを使用し、高スループットを得るために深いパイプライン方式が可能であるので、高速な（おそらく毎秒１億エントリを超える速度で検索する）処理能力がある。さらに、本構造は等価なＴＣＡＭ部品よりも６分の１の消費電力（ビット当たり約５０ｎＷ）となる。格納されたヘッダ内の個々のプレフイックス長の数がヘッダの数と共に増加すると想定されるので、上記の構造のメモリ必要量は、ＴＣＡＭにおいて必要とされるよりも速く増加することに留意すべきである。しかし、プレフイックス長の数が安定すると、メモリの増加率はＴＣＡＭと同等となるであろう。
【０３３６】
本発明の発明者は、本構造が無損失ハッシュ・テーブルを容易に凌駕することと、誤ポジティブ率が、セグメント化されたメモリを有するフィルター、ならびに、セグメント化されたメモリを有しないフィルターに非常に類似していることを実証するシミュレーションを行った。本発明者は、表のサイズが、ハッシュ関数の数の増加と共に最初は小さくなり、その後に大きくなることも発見した。これは、ハッシュ関数の数の増加は、２つの相反する作用を有するためである。第１に、ハッシュ関数の数の増加は、より多くのエントリがハッシュされるので、単集合を発見する機会を改善する。しかし、より多くのハッシュ関数は、各エントリが指向される確率も増大させる。これは、単集合を発見する機会を減少させ、フィルターセットアッププロセスが収束する表のサイズを大きくする傾向がある。セグメント化されたメモリの使用も表のサイズを大きくする。ハッシュ関数は、そのメモリ・セグメント内に限定されているので、セグメント化されたより大きい表サイズが予想される。ある意味では、セグメント化されたメモリは、セグメント化されていないメモリのように「ランダム」ではない。これは単集合を発見する機会を減少させ、したがって、セットアップの間に収束する大きいメモリ・サイズを必要とする。
【０３３７】
当業者が、ここに明示的に示されていないか、あるいは説明されていないが、本発明の原理を具体化し、本発明の要旨と範囲に含まれる数多くの装置や変形を案出することが可能であることを理解されよう。たとえば、そして限定するものではなく、ネットワーク・ルーター・アプリケーションおよび連想記憶装置を特に参照して、本発明を説明した。本発明はそれにもかかわらず、上述のように、他の用途にも容易に拡張可能である。
【図面の簡単な説明】
【０３３８】
【図１】本発明の一態様の実施形態によるコンテンツ・ベース情報検索アーキテクチャーを示す図である。
【図２】誤ポジティブを可能にする他のコンテンツ・ベース情報検索アーキテクチャーを示す図である。
【図３】本発明の他の態様の実施形態によるコンテンツ・ベース情報検索アーキテクチャーにおけるセグメントされたメモリおよびパイプライン方式を示す図である。
【図４】本発明の他の態様の実施形態によって構築された最長プレフイックス・マッチング・ネットワーク・ルーターを示す図である。
【図５】本発明の他の実施形態によって構築された他のネットワーク・ルーター・アーキテクチャーを示す図である。
【図６】一例のルーター・ラインカードを示す図である。
【図７Ａ】小さい容量のメモリを使用する他のコンテンツ・ベース情報検索アーキテクチャーを示す図である。
【図７Ｂ】小さい容量のメモリを使用する他のコンテンツ・ベース情報検索アーキテクチャーを示す図である。
【図８】プレフィルターリングのメカニズムを示す他のコンテンツ・ベース情報検索アーキテクチャーを示す図である。
【図９】スピルオーバー・テーブルの使用法を示す図である。
【図１０】スピルオーバー・テーブルの使用法を示す図である。
【図１１】プレフィルターリングおよびスピルオーバー・テーブルを使用するコンテンツ・ベース情報検索アーキテクチャーを示す図である。
【図１２】図１１に示すアーキテクチャーによって実行される処理のフローチャートである。
【図１３】パイプライン方式のハッシュ関数の動作を示す図である。
【図１】
2007524946.tif 000149
【図２】
2007524946.tif 000150
【図３】
2007524946.tif 000151
【図４】
2007524946.tif 000152
【図５】
2007524946.tif 000153
【図６】
2007524946.tif 000154
【図７Ａ】
2007524946.tif 000155
【図７Ｂ】
2007524946.tif 000156
【図８】
2007524946.tif 000157
【図９】
2007524946.tif 000158
【図１０】
2007524946.tif 000159
【図１１】
2007524946.tif 000160
【図１２】
2007524946.tif 000161
【図１３】
2007524946.tif 000162
【国際調査報告】
2007524946.tif 000163
2007524946.tif 000164