(57)【要約】  関連ＲＡＭの中で結果をルックアップするための複数のプレフィックスエントリを保持する三値連想メモリ（ＴＣＡＭ）であって、関連ＲＡＭはＴＣＡＭ一致インデックスに対応する結果を記憶する、ＴＣＡＭと、関連ＲＡＭからの結果を記憶する増設ランダムアクセスメモリ（ＲＡＭ）と、増設ＲＡＭの中に関連ＲＡＭからの少なくとも２つのエントリを表し、それによって、ＴＣＡＭの中の少なくとも１つのエントリが利用可能になる、ＴＣＡＭの中の１つのエントリと、を含む、ＴＣＡＭベースの最長プレフィックス一致（ＬＰＭ）ルックアップテーブル。【選択図】図１Ｂ
2013502020.tif 000002
【特許請求の範囲】
【請求項１】
三値連想メモリ（ＴＣＡＭ）の中に複数のプレフィックスエントリを配置することと、前記プレフィックスエントリのＴＣＡＭ一致インデックスに対応する結果を、関連結果ランダムアクセスメモリ（ＲＡＭ）の中に挿入することとを含む、最長プレフィックス一致ルックアップテーブルを構築するための方法であって、前記方法は、
前記ＴＣＡＭの中の単一エントリに削減することができる少なくとも２つの前記プレフィックスエントリのグループを選択することであって、前記単一エントリは前記グループの中の全てのプレフィックスエントリに対する共通プレフィックスから成ることと、
増設ＲＡＭの中に、前記プレフィックスのグループによって表される、前記関連ＲＡＭからの結果エントリを配置することと、
前記増設ＲＡＭの中の前記エントリをポイントしている結果エントリによって、前記関連ＲＡＭの中の前記結果エントリを置換することと、
前記ＴＣＡＭの中の前記プレフィックスエントリのグループを、前記関連ＲＡＭの中の前記結果エントリをポイントしている前記単一ＴＣＡＭエントリと置換し、それによって、前記ＴＣＡＭの中の少なくとも１つのエントリを利用可能にすることと、
を含む、方法。
【請求項２】
前記増設ＲＡＭの中の前記複数の結果エントリを配列の中に配置することをさらに含み、前記配列は、前記単一ＴＣＡＭエントリに一致する全ての可能なプレフィックスを含有する、請求項１に記載の方法。
【請求項３】
新しいプレフィックスエントリを前記ＴＣＡＭに追加し、
前記新しいプレフィックスエントリと共通プレフィックスを有する配列を前記増設ＲＡＭの中で検索し、
前記配列が検出された場合、前記新しいプレフィックスエントリに対応する結果を前記配列に追加することによって、
前記新しいプレフィックスエントリを前記ルックアップテーブルに追加することをさらに含む、請求項２に記載の方法。
【請求項４】
新しいプレフィックスエントリを前記ＴＣＡＭに追加し、前記新しいプレフィックスエントリの一致インデックスに対応する結果を、前記関連結果ＲＡＭに書き込むことによって、前記新しいプレフィックスエントリを前記ルックアップテーブルに追加することをさらに含む、請求項２に記載の方法。
【請求項５】
新しいプレフィックスエントリを前記ＴＣＡＭに入力し、
前記ＴＣＡＭの中の少なくとも１つの既存プレフィックスエントリの一致インデックスに対応する結果と、前記新しいプレフィックスエントリの一致インデックスに対応する結果とを含有する、前記増設ＲＡＭの中の新しい配列を作成し、
前記新しい配列をポイントする新しい共通プレフィックス結果を前記関連ＲＡＭに入力し、
前記新しいプレフィックスエントリの代わりに、前記新しい共通プレフィックスを前記ＴＣＡＭに入力することによって、
前記新しいプレフィックスエントリを前記ルックアップテーブルに追加することをさらに含む、請求項２に記載の方法。
【請求項６】
前記新しい配列の中に含まれるプレフィックスに対応する全ての既存配列と、全てのそれぞれのリソースを分解することをさらに含む、請求項５に記載の方法。
【請求項７】
消去されたプレフィックスエントリに一致する最長プレフィックスの結果によって、前記消去されたプレフィックスエントリに対応する、増設ＲＡＭの中の結果を上書きすることによって、前記ルックアップテーブルからプレフィックスエントリを消去することをさらに含む、請求項１に記載の方法。
【請求項８】
指定のプレフィックスに対応するＴＣＡＭエントリを無効化することによって、前記テーブルから指定のプレフィックスを消去することと、
結果ＲＡＭエントリまたは増設ＲＡＭエントリの中の古い結果を上書きすることによって、プレフィックスの結果を更新することと、
をさらに含む、請求項１に記載の方法。
【請求項９】
前記エントリがルックアップ結果、または前記増設ＲＡＭの中のルックアップ結果へのポインタを含有するかを示すビットを、前記結果ＲＡＭの中の各エントリに提供することをさらに含む、請求項１に記載の方法。
【請求項１０】
選択する前記ステップは、２つ以上のグループを選択することを含み、配置する前記ステップは、各前記グループからの結果を前記増設ＲＡＭの中の対応する配列に配置することを含み、
置換する前記ステップは、前記ＴＣＡＭの中の前記プレフィックスエントリのグループ各々を、単一ＴＣＡＭエントリと置換することを含み、
前記関連ＲＡＭの中のエントリを置換する前記ステップは、前記増設ＲＡＭの中の前記対応する配列をポイントするエントリによって、前記エントリを置換することを含む、
請求項１に記載の方法。
【請求項１１】
最長プレフィックス一致（ＬＰＭ）ルックアップを実施するための方法であって、前記方法は、
三値連想メモリ（ＴＣＡＭ）および関連結果ランダムアクセスメモリ（ＲＡＭ）と、
増設ＲＡＭと、
を含むルックアップテーブルを構築し、維持することであって、
前記増設ＲＡＭの中の少なくとも２つのエントリは、前記ＴＣＡＭの中の１つのエントリによって表されることと、
前記ＴＣＡＭの中でルックアップを実施することと、
前記増設ＲＡＭの中の結果のグループをポイントする、前記ＴＣＡＭの中のエントリに対する結果を前記関連結果ＲＡＭの中で検出することと、
それに応答して、前記増設ＲＡＭで前記結果のグループの中のエントリを読み出すことによって、前記ルックアップを完了することと、
を含む、方法。
【請求項１２】
ＴＣＡＭ一致インデックスを検出するために、指定のキーに対するＴＣＡＭルックアップを実施することと、
前記ＴＣＡＭ一致インデックスに対応する関連結果ＲＡＭエントリを読み出すことであって、前記結果ＲＡＭエントリは、開始ビットとストライドサイズとを含むことと、
前記ルックアップキー、ならびに前記結果ＲＡＭエントリからの前記開始ビットおよびストライドサイズに基づいてインデックスを計算することと、
前記計算されたインデックスに対応する増設ＲＡＭエントリを読み出すことによって、前記ＬＰＭルックアップを完了することと、
を含む、請求項１１に記載の方法。
【請求項１３】
前記ルックアップテーブルは、前記ＴＣＡＭの中の対応するエントリを有するリアルノードと、前記ＴＣＡＭの中に対応するエントリを全く有しないノードとを含む、テーブルトライ木によって表され、
構築し、維持する前記ステップはさらに、リアルノードである、前記テーブルトライ木の中のより短いプレフィックスを有する第１のリアルノードの結果を、前記ＴＣＡＭの中にエントリを全く有しない各ノードに対応する前記配列の中に挿入することを含む、
請求項１２に記載の方法。
【請求項１４】
構築し、維持する前記ステップはさらに、前記配列の中の２つ以上のエントリに結果を挿入することを含む、請求項１２に記載の方法。
【請求項１５】
三値連想メモリ（ＴＣＡＭ）ベースの最長プレフィックス一致（ＬＰＭ）ルックアップテーブルであって、
ＴＣＡＭおよび関連結果ランダムアクセスメモリ（ＲＡＭ）と、
増設ＲＡＭと、を備え、
前記増設ＲＡＭの中の少なくとも２つのエントリは、前記ＴＣＡＭの中の１つのエントリおよび前記関連結果ＲＡＭの中の１つのエントリによって表される、ルックアップテーブル。
【請求項１６】
前記ＴＣＡＭは、関連ＲＡＭの中の結果をルックアップするための複数のプレフィックスエントリを保持するＴＣＡＭであり、
前記関連ＲＡＭは、前記プレフィックスエントリのＴＣＡＭ一致インデックスに対応する結果を記憶し、
前記増設ＲＡＭは、前記関連ＲＡＭからの結果を記憶し、
前記ＴＣＡＭの中の１つのエントリは、前記関連ＲＡＭからの前記増設ＲＡＭの中の少なくとも２つのエントリを表し、それによって、前記ＴＣＡＭの中の少なくとも１つのエントリが利用可能になる、
請求項１４に記載のルックアップテーブル。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、最長プレフィックス一致を実施するデバイスの拡張性を向上するための方法およびデバイスに関する。
【背景技術】
【０００２】
最長プレフィックス一致（ＬＰＭ）は、データベースに記憶されたいくつかのプレフィックスの中から、指定のルックアップキーに一致する、最長プレフィックスを検出するという課題である。ＬＰＭは、多数の用途で使用することができ、ＩＰルーティングに限定されないが、ＩＰルーティングは主要なＬＰＭ用途のうちの１つであるので、本発明は、非限定例として、ＩＰルーティングの状況のみで検討されることになる。
【０００３】
転送情報ベース（ＦＩＢ）は、転送テーブルとも呼ばれ、入力インターフェースがルータによって伝送されるパケットを送信すべき適切なインターフェースを検出するために、ネットワークブリッジ、ルーティング、および類似の機能で最も一般的に使用される。このため、ＦＩＢは、対応する出力インターフェースを含む一連のプレフィックスを含有する。転送判定は、ルックアップキーに一致する最長プレフィックスを検出することによって行われる。現在最も一般的に使用されるルックアップキーは、パケットのＩＰｖ４またはＩＰｖ６の宛先アドレスである。
【０００４】
ＦＩＢ、またはＬＰＭを実施するための他のデバイスは、Ｍ−トライ木、ビットマップ木等のアルゴリズムを使用することによってランダムアクセスメモリ（ＲＡＭ）を用いて、または三値連想メモリ（ＴＣＡＭ）等の高速ハードウェアルックアップ機構を用いて、実装することができる。高度なＲＡＭベースのＦＩＢ実装／アルゴリズムは、何百万ものプレフィックスを保持するに充分な拡張性があるが、ＦＩＢメモリへのアクセス数はルックアップキー幅に依存するため、ルックアップキー幅の観点からは拡張可能ではない。概して、キーの幅が広ければ広いほど、より多くのルックアップが必要とされる。
【０００５】
一方、ＴＣＡＭベースのＦＩＢまたはＬＰＭ実装を用いると、ルックアップ時間は一定である。しかしながら、ＴＣＡＭベースのＦＩＢまたはルックアップテーブルは、プレフィックスの数の面では拡張可能ではない。現在知られている最も高度なＴＣＡＭデバイスは、４０Ｍビットの容量を有し、０．５Ｍまでのプレフィックスを保持するために使用することができる。
【０００６】
したがって、プレフィックスの数の面およびルックアップキー幅の面両方で拡張可能な最長プレフィックス一致ルックアップを実施するための方法および装置に対する長年にわたる必要性が存在する。
【発明の概要】
【０００７】
本発明において提案される解決策は、その関連結果ＲＡＭを備えるＴＣＡＭデバイスを利用し、増設ＲＡＭを追加し、増設ＲＡＭの中の複数のエントリを支持するＴＣＡＭにエントリを入力することによって、ＬＰＭの拡張性を向上することである。この構造は、従来の様式よりも少ないＴＣＡＭエントリを有する所定の規模のＬＰＭルックアップテーブルを提供することが理解される。このように、より小型のＴＣＡＭデバイスを使用すること、または他の用途による使用を可能にするためにより多くのＴＣＡＭエントリを解放すること、のいずれかが可能である。
【０００８】
本発明によると、ＴＣＡＭ（三値連想メモリ）の中に複数のプレフィックスエントリを配置することと、ＴＣＡＭ一致インデックスに対応する結果を関連結果ＲＡＭ（ランダムアクセスメモリ）の中に挿入することとを含む、最長プレフィックス一致ルックアップテーブルを構築するための方法が提供され、当該方法は、ＴＣＡＭの中の単一エントリに削減することができる少なくとも２つのプレフィックスエントリのグループを選択することであって、単一エントリは、グループの中の全てのプレフィックスエントリに対する共通プレフィックスから成り、増設ＲＡＭの中に、プレフィックスのグループによって表される関連ＲＡＭからの結果を配置することと、ＴＣＡＭの中のプレフィックスエントリのグループを増設ＲＡＭの中の複数の結果をポイントする単一ＴＣＡＭエントリと置換し、それによって、ＴＣＡＭの中の少なくとも１つのエントリを利用可能にすることと、増設ＲＡＭの中のエントリをポイントするエントリによって、関連ＲＡＭの中のエントリを置換することと、を含む。
【０００９】
さらに、本発明によると、最長プレフィックス一致（ＬＰＭ）ルックアップを実施するための方法が提供され、当該方法は、ＴＣＡＭおよび関連結果ランダムアクセスメモリ（ＲＡＭ）と、増設ＲＡＭとを含む、ルックアップテーブルを構築し、維持することであって、増設ＲＡＭの中の少なくとも２つのエントリは、ＴＣＡＭの中の１つのエントリによって表され、ＴＣＡＭの中でルックアップを実施することと、増設ＲＡＭの中の結果のグループをポイントする、ＴＣＡＭの中のエントリに対する結果を関連結果ＲＡＭで検出することと、それに応答して、増設ＲＡＭの中で結果のグループの中のエントリを読み出すことによって、ルックアップを完了することと、を含む。
【００１０】
また、本発明によると、関連ＲＡＭの中の結果をルックアップするための複数のプレフィックスエントリを保持するＴＣＡＭと、ＴＣＡＭ一致インデックスに対応する結果を記憶する関連ＲＡＭと、関連ＲＡＭからの結果を記憶する増設ランダムアクセスメモリ（ＲＡＭ）と、関連ＲＡＭからの、増設ＲＡＭの中の少なくとも２つのメモリを表し、それによって、ＴＣＡＭの中の少なくとも１つのエントリが利用可能になる、ＴＣＡＭの中の１つのエントリとを含む、三値連想メモリ（ＴＣＡＭ）ベースの最長プレフィックス一致（ＬＰＭ）ルックアップテーブルが提供される。
【図面の簡単な説明】
【００１１】
本発明は、図面と共に以下の発明を実施するための形態から、さらに理解し、評価される。
【図１ａ】先行技術に従い、ＴＣＡＭエントリによってＬＰＭデバイスエントリを表す模式図である。
【図１ｂ】本発明の一例示的実施形態に従い、ＴＣＡＭおよび増設ＲＡＭエントリによって、図１ａのＬＰＭエントリを表す模式図である。
【図２ａ】先行技術の別の例に従い、ＴＣＡＭエントリによってＬＰＭデバイスエントリを表す模式図である。
【図２ｂ】本発明の別の例示的実施形態に従い、ＴＣＡＭおよび増設ＲＡＭエントリによって、図２ａのＬＰＭエントリを表す模式図である。
【図３ａ】先行技術の別の例に従い、ＴＣＡＭエントリによってＬＰＭデバイスエントリを表す模式図である。
【図３ｂ】本発明のさらなる例示的実施形態に従い、ＴＣＡＭおよび増設ＲＡＭエントリによって、図３ａのＬＰＭエントリを表す模式図である。
【発明を実施するための形態】
【００１２】
本発明は、標準のＴＣＡＭベースの解決策より向上した規模（エントリの数に対して）を達成するために、三値連想メモリ（ＴＣＡＭ）（結果メモリとして機能する、その関連ランダムアクセスメモリ（ＲＡＭ）を備える）および増設ＲＡＭを使用して、最長プレフィックス一致（ＬＰＭ）ルックアップを実施するための方法および装置に関する。方法は、結果データの一部をＴＣＡＭに関連するＲＡＭの中に、およびデータの一部を増設ＲＡＭの中に記憶し、増設ＲＡＭの中の複数のエントリを支持するＴＣＡＭにエントリを挿入することによって、従来のＴＣＡＭベースのデバイスの中に占有されるＴＣＡＭエントリを利用可能にすることによって、ＬＰＭの拡張性を向上する。
【００１３】
従来のＴＣＡＭベースのＬＰＭ解決策において、各ＬＰＭエントリは、関連結果メモリ（関連ＲＡＭ）の中の結果をポイントする、１つのＴＣＡＭエントリによって表される。本発明において、ＬＰＭエントリのグループは、そのプレフィックスがそのグループの中のエントリ全ての共通なプレフィックスである、単一ＴＣＡＭエントリによって表すことができる。この場合、関連ＲＡＭの中のそれぞれの結果は、そのＬＰＭエントリのグループの中の各エントリの結果を含有する、増設ＲＡＭの中の結果の配列をポイントする。
【００１４】
増設ＲＡＭの中のエントリは、次いで、ルックアップキーの限られた部分を使用して検索することができ、それによって結果は１回のＲＡＭアクセスで取得することができる。このように、結果メモリの中の結果のうちのいくつかは、ＴＣＡＭのルックアップ中に検出され、結果のうちのいくつかは、増設ＲＡＭのその後のルックアップ中に検出される。所望の場合、１つ（以上）のさらなる増設ＲＡＭアクセスを提供することができ、すなわち、いくつかのレイヤーのＲＡＭ配列を有効にすることができ、各々１つはその結果を保持する１つをポイントすることが理解される。複数のレベルのＲＡＭを使用するアルゴリズムは、所定のサイズのＴＣＡＭおよびＲＡＭに対してＬＰＭエントリのより向上した規模を達成する場合がある。この配置の不利な点は、複数のＲＡＭアクセスが実施されることによる、ルックアップ時間である。
【００１５】
そのプレフィックスがある長さＭを有するＴＣＡＭエントリは、このＴＣＡＭエントリに一致する長さＭ＋Ｎの可能なプレフィックス全てを含有する、増設ＲＡＭの中の結果の配列を参照する場合がある。そのような配列は、２Ｎ個のエントリ（長さＭの所定のプレフィックスに一致する長さＭ＋Ｎのプレフィックスの数）を含有し、配列をポイントするＴＣＡＭエントリの（長さＭの）プレフィックスに一致する、長さがＭ以上Ｍ＋Ｎ以下のプレシックスを含むＬＰＭエントリ全てを表す。ＬＰＭエントリのグループがＴＣＡＭの中で単一のエントリによって表すことができる時、結果のグループは、関連結果ＲＡＭから増設ＲＡＭに移される。増設ＲＡＭの中の配列に結果が表されるＬＰＭエントリは、ＴＣＡＭから削除され、関連結果ＲＡＭの中の新しい結果をポイントし、したがって、増設ＲＡＭの中の対応する配列をポイントする、単一のエントリによって置換することができ、このために、指定のＴＣＡＭサイズを備えるより大型のＬＰＭルックアップテーブルを表すことが可能になる。対応する増設ＲＡＭ配列の中のその後のルックアップは、ルックアップキーのはるかにより小さい部分を使用、すなわち、Ｍ〜（Ｍ＋Ｎ−１）ビットだけになり、増設ＲＡＭの単一アクセス中に結果を取得することができる。
【００１６】
ＴＣＡＭルックアップによって示される関連ＲＡＭエントリの中の結果は、もはや本来の結果（現在増設ＲＡＭの中にある）を含有しないが、実際の結果の読み出しを可能にする３つのパラメータ、すなわち、開始ビット、ストライドサイズ、ならびにルックアップキー、開始ビットおよびストライドサイズに基づいて計算されたインデックスを含有する。これらのパラメータは、増設ＲＡＭの中の配列の開始の位置、および増設ＲＡＭの中でルックアップが実施されるルックアップキーの関連ビット（例えば、ＦＩＢの中のＩＰアドレスの関連ビット）を示し、増設ＲＡＭの中の配列内部でインデックスを呼び出すために使用される。典型的に、関連ビットは、ルックアップキーのＭ〜（Ｍ＋Ｎ−１）ビットである。ＬＰＭルックアップは、ＴＣＡＭ一致インデックスによってポイントされた配列内の計算されたインデックスに対応する、増設ＲＡＭの中のエントリを読み出すことによって完了される。結果アドレスは、これらの値に応じて計算され、増設ＲＡＭメモリから取得される。
【００１７】
配列の中でグループ化されないＴＣＡＭエントリの結果は、従来のＴＣＡＭルックアップテーブルのように、ＴＣＡＭに関連する結果ＲＡＭの中に格納される。関連結果ＲＡＭの中の結果のビットのうちの１つは、（関連ＲＡＭの中の）結果の残りが実際の結果であるか、または上記のように、実際の結果が存在する増設ＲＡＭの中の配列へのポインタを含有するかを示すために使用される場合がある。この方法は必須ではないが、結果プレフィックスが配列内でグループ化されない時に増設メモリアクセスを回避するために有用である。
【００１８】
本明細書の目的のために、２Ｎ個のエントリを備える配列において、Ｎは、配列のストライドサイズとして参照される。このため、ストライドサイズＮの配列をポイントするプレフィックス長ＭのＴＣＡＭエントリは、Ｍ以上Ｍ＋Ｎ以下の範囲の長さの（２Ｎ＋１−１）個のＬＰＭエントリまでを支持する。いくつかのストライドサイズがサポートされる場合があり、異なるサイズの配列は増設ＲＡＭの中で共存することができることが理解されるだろう。
【００１９】
ＬＰＭテーブルの作成に責任を負うソフトウェアアルゴリズムは、配列の作成のために候補のプレフィックスを発見することと、新しい配列を作成することまたは既存の配列を分解することを判定することにも責任を負う。すなわち、いくつかのルックアップキーは最後のＮビットだけが異なるので、これらは、ＴＣＡＭエントリの数を削減するという目的のために、単一グループまたは配列の中に結合することができることに注意されたい。作成されるべき配列を選択する１つの可能な方式は、それらの「利用率」によって候補の配列の優先順位を決定することである。本明細書において、利用率は、配列を作成する時に削減することができるＴＣＡＭエントリの数と、配列サイズ（ストライドサイズがＮの配列の場合２Ｎ）との比率として定義される。
【００２０】
利用率に従って優先順位を決定する場合、例えば、可能な実装には、グローバル利用率閾値を使用することが関与するので、所定の閾値より高い利用率を備える候補の配列が作成され、その利用率が何らかの他の閾値を下回る既存の配列は分解され、それらのＬＰＭエントリは個別にＴＣＡＭに戻される。ルックアップテーブルは特にＦＩＢテーブルの場合、経時的に変化する可能性があるので、動作中にこれらの配列を作成し、分解することができる。この例示的実装において、利用率閾値は、ＬＰＭルックアップを使用して特定の用途上でテストを実施することによって最適化することができ、また利用可能なＴＣＡＭサイズとアルゴリズムの使用専用の利用可能なＲＡＭサイズとの間の比率によって大きく影響を受ける。ＴＣＡＭサイズに比較してＲＡＭサイズが大きくなればなるほど、許可できる利用率閾値は低くなる。
【００２１】
例えば、ＩＰルーティングでは、テストで、２００９年４月のインターネットの転送テーブルのインターネットＩＰｖ４エントリの分布を利用すると、本発明の方法は次の規模結果を達成することができるだろうということが示されている。
【表１】
2013502020.tif 000003
【００２２】
表の真中の数値を見ると、増設ＲＡＭメモリ（プレフィックス配列を記憶するために使用）がＴＣＡＭが有するエントリの４倍の数のエントリを有する場合、アルゴリズムは、従来のＴＣＡＭ解決策に比較して、〜２．６５倍まで、ＦIＢテーブルの中のプレフィックスの数の規模を向上することができる。ＩＭエントリを保持することができるＴＣＡＭデバイスおよび４Ｍエントリを備える増設ＲＡＭメモリを使用して、例に数字をあてはめると、アルゴリズムは、〜２．６５ＭのＦＩＢエントリの規模を達成することができる。
【００２３】
図１ａを参照すると、本明細書ではＦＩＢテーブル２０として例示され、先行技術の一例に従って、ＴＣＡＭエントリによって複数のＦＩＢエントリを表すことを例示する、ＬＰＭテーブルの模式図が示される。示されるように、各ＦＩＢエントリ１２（ＦＩＢテーブルトライ木１０において黒丸で例示）は、関連結果ＲＡＭ２４の中の結果（ＡからＥ）１６をポイントする、ＴＣＡＭ２２の中の１つのエントリ１４によって表される。ノード１８（ＦＩＢテーブルトライ木１０の白丸として例示）は本当のＦＩＢエントリではなく、ＦＩＢテーブルトライ木の中の結合を示すに過ぎず、従ってＴＣＡＭには表示されない。
【００２４】
図１ｂは、本発明の一例示的実施形態に従い、図１ａのＦＩＢテーブルトライ木１０に対応する、ＦＩＢテーブルトライ木３１を表すＦＩＢテーブル３０を表す模式図である。ＦＩＢテーブル３０は、その関連結果ＲＡＭ２４および増設ＲＡＭ２６を備えるＴＣＡＭ２２を含む。図１ａおよび１ｂの小さい三角形１９は、単一ＴＣＡＭエントリに削減することができる（すなわち、対応結果は、その中の検索のために、増設ＲＡＭに移動可能）ＦＩＢトライ木の候補部分を示す。関連結果メモリからの対応する結果エントリは現在、増設ＲＡＭ２６の中の配列３６（Ａ、Ｂ、Ｃ、Ｄ）に記憶されている。このため、図１ｂにおいて、単一ＴＣＡＭエントリ３２、ＴＣＡＭ２２の中のプレフィックス０１００＊は、４つの以前のＴＣＡＭエントリ０１００＊、０１００１＊、０１００００＊、および０１０００１＊を置換し、それによって、ＴＣＡＭの中で３つのエントリが利用可能になる。好ましくは、プレフィックスのグループを置換するＴＣＡＭの中のプレフィックスは、グループのエントリ全ての共通プレフィックスである。
【００２５】
ＴＣＡＭルックアップによって現在呼び出された結果３４は、配列内部のインデックスを呼び出すように（ここではビット４および５として例示）、増設ＲＡＭの中の配列３６の開始位置、およびルックアップが実施されたエントリ（例えば、ＩＰアドレス）の関連ビットを含有する。この例で示された削減の利用率は、利用可能になったＴＣＡＭプレフィックスの数、ここでは３を、配列のサイズ、２２＝４で除した数である。したがって、この削減は、３／４または７５％の利用率を有する。
【００２６】
図２ａは、先行技術の別の例に従い、ＴＣＡＭエントリによってＬＰＭデバイスエントリを表す模式図である。このＦＩＢテーブルトライ木４０は、ノード０１００＊がリアルＦＩＢエントリではない点を除き、図１ｂのトライ木１０に類似する。従来のＴＣＡＭベースのＬＰＭデバイスにおいて、トライ木４０のエントリは、ＴＣＡＭ４２および関連結果メモリ４４に記憶される。プレフィックス０１００＊はリアルＦＩＢエントリではないので、ＴＣＡＭ４２および結果メモリ４４は、図１ａよりも１つ少ないエントリを含有する。
【００２７】
ここで図２ｂを参照すると、本発明の別の例示的実施形態に従い、ＴＣＡＭおよび増設ＲＡＭエントリによって図２ａのＬＰＭエントリの表現がＦＩＢテーブルトライ木５０に例示される。プレフィックス０１００＊はリアルＦＩＢエントリではないという事実にも関わらず、依然としてトライ木の候補部分の削減に使用することができる。このため、ＴＣＡＭ５１には、５つのエントリではなく、３つのエントリが存在する。エントリ５２は、関連結果ＲＡＭ５４の中の結果５６をポイントする０１００＊プレフィックスである。削減されたＴＣＡＭエントリに対応する関連結果ＲＡＭからの結果エントリは、増設ＲＡＭ５８の中の配列５７に記憶される。示されるように、増設ＲＡＭ５８の中の配列は、配列に削減されたエントリの群の中のＬＰＭエントリによって表されない、プレフィックス０１０００１＊を含む。この場合、配列は、「バックトラック」結果、すなわち、リアルノードであるＬＰＭテーブルトライ木の中のその上にある最初のノードの結果、ここでは、０１０＊、結果Ｅを含有する。すなわち、本発明によると、配列が削減されたグループのどのＬＰＭエントリによっても表されない長さＭ＋Ｎのプレフィックスを含む場合、配列は、バックトラック結果、すなわち、Ｍ＋Ｎのサブプレフィックスで、Ｍ未満の長さを有するテーブルの中の最長プレフィックスの結果の複製を含有する。この場合、配列サイズは２２＝４であるが、ＴＣＡＭプレフィックスの数は２に削減されるので、この削減は、２／４または５０％の利用率を有することが理解される。
【００２８】
図３ａは、先行技術のさらなる例に従い、ＴＣＡＭエントリによってＬＰＭデバイスエントリを表す模式図である。このＦＩＢテーブルトライ木６０は、ノード０１００１０＊がリアルＦＩＢエントリではない点を除き、図２ｂのトライ木４０に類似する。従来のＴＣＡＭベースのＬＰＭデバイスにおいて、トライ木６０のエントリは、ＴＣＡＭ６２および関連結果メモリ６４に記憶される。プレフィックス０１００１０＊はリアルＦＩＢエントリではないので、ＴＣＡＭ６２および結果メモリ６４は、図２ａよりも１つ少ないエントリを含有する。
【００２９】
図３ｂは、ＦＩＢテーブルトライ木７０の中に例示される、本発明のさらなる例示的実施形態に従い、ＴＣＡＭおよび増設ＲＡＭエントリによって図３ａのＬＰＭエントリを表す模式図である。この例においても、ＴＣＡＭ７１の中には３つのエントリが存在する。ここでも、エントリ７２は、関連結果ＲＡＭ７４の中の結果７６をポイントする０１００＊プレフィックスである。削減されたＴＣＡＭエントリに対応する結果ＲＡＭからの結果エントリは、増設ＲＡＭ７８の中の配列７７に記憶される。示されるように、増設ＲＡＭ７８の中の配列は、どのＬＰＭエントリによっても表されない、２つの追加のプレフィックス０１００１０＊および０１００１１＊を含む。この場合、配列は、「複製」結果を含有、すなわち、これらのエントリの両方は同じ結果、結果Ｃを有する。すなわち、本発明によると、このＭ＋Ｎプレフィックスを表す配列の中のより特定されたプレフィックス（すなわち、より長い長さ）が存在しない限り、配列の中で表される、Ｍ＋Ｎ未満のプレフィックス長を有するＬＰＭエントリは、このプレフィックスによって表される長さＭ＋Ｎの可能なプレフィックス全てを支持する配列の中のいくつかの結果に複製される場合がある。示されるように、この場合、配列サイズは２２＝４であるが、ＴＣＡＭプレフィックスの数は１だけ削減されるので、したがって、この削減は、１／４つまり２５％の利用率を有する。
【００３０】
要約すると、ＬＰＭルックアップは、本発明のＬＰＭデバイス上で次のように実施される。まず、ＴＣＡＭルックアップは、ＬＰＭデバイスのＴＣＡＭの中で、指定のキーに対して実施される。ＴＣＡＭ一致インデックスに対応する関連結果ＲＡＭエントリが読み出され、ルックアップキーおよび関連結果ＲＡＭエントリの中の２つのパラメータ（開始ビットおよびストライドサイズ）に基づいて、インデックスが計算される。ＬＰＭルックアップは、関連結果ＲＡＭエントリからの第３のパラメータによってポイントされる配列内の計算されたインデックスに対応する、増設ＲＡＭの中のエントリを読み出すことによって、完了される。この増設ＲＡＭエントリは、指定のキーに一致する最長プレフィックスに対する用途特定結果を含有する。
【００３１】
ＬＰＭテーブルは、必要に応じて、テーブルに新しいプレフィックスを追加し、テーブルから古いプレフィックスを削除することによって維持される。新しいプレフィックスは、３つの方式のうちの１つでテーブルに追加することができる。まず、従来のＬＰＭテーブルのように、指定のプレフィックスのための新しいエントリをＴＣＡＭに追加することができ、結果は、対応する結果ＲＡＭエントリに書き込まれる。代替として、新しいエントリと同じプレフィックスを有するエントリの適当な配列が増設ＲＡＭに既に作成されていた場合、プレフィックス結果は、増設ＲＡＭの中の既存配列の中の対応するエントリに追加することができる。必要に応じて、かつ対応する配列が全く存在しない場合、増設ＲＡＭの中には、既存のプレフィックス結果のうちのいくつかと共に新しいプレフィックス結果を含有する、新しい配列を作成することができる。新しく作成された配列をポイントする新しい共通プレフィックス結果は、結果ＲＡＭに書き込まれ、新しい共通プレフィックスはＴＣＡＭに追加される。新しい配列に含まれるプレフィックスに対応する任意の既存の配列は現在分解され、それぞれのリソース全て（例えば、ＴＣＡＭリソース）はＴＣＡＭおよび関連結果ＲＡＭに戻される。
【００３２】
プレフィックス結果は、結果ＲＡＭエントリまたは増設ＲＡＭエントリの中の古い結果を上書きすることによって更新することができる。
【００３３】
古いプレフィックスは、対応する増設ＲＡＭエントリの中のプレフィックス結果を消去されたプレフィックスに一致する最長プレフィックスの結果によって上書きするか、またはルックアップに含まれないように、指定のプレフィックスの対応するＴＣＡＭエントリを無効化することのいずれかによって、テーブルから削除することができる。
【００３４】
本発明は、限定された数の実施形態に関して記載されるが、本発明の多数の変形、変更、および他の用途が行われる場合があることが理解されるだろう。さらに、本発明は例に過ぎない上記の内容に限定されないことも理解されるだろう。そうではなく、本発明は後に続く請求項によってのみ限定される。
【図１ａ】
2013502020.tif 000004
【図１ｂ】
2013502020.tif 000005
【図２ａ】
2013502020.tif 000006
【図２ｂ】
2013502020.tif 000007
【図３ａ】
2013502020.tif 000008
【図３ｂ】
2013502020.tif 000009
【国際調査報告】
2013502020.tif 000010