(57)【要約】【課題】改良されたコンピュータ・システムを提供する。【解決手段】本システムにはコンピュータ・プロセッサを有するコントローラを含めることが可能であり、該コントローラは、コントローラに導入される新規コンポーネントとインターフェースを取るときの挿入時間もしくはハッシュ衝突またはその両方を低減する。また、本システムには、複数のテーブルおよびバケットあたり複数のキーを使うことによってハッシュ衝突を低減する、衝突回避装置も含めることができる。本システムには、複数のキーを複数のテーブルにマップするための、コントローラと交信するハッシュ装置をさらに含めることができ、該ハッシュ装置は、一つのキーが変更されたとき、単一のハッシュ・ロジックを用いて雪崩効果を施し、これは複数のテーブル中のほぼ半数のビットの変更をもたらす。【選択図】図１
2013242539.tif 000002
【特許請求の範囲】
【請求項１】
コンピュータ・プロセッサを包含するコントローラであって、前記コントローラは、前記コントローラに導入される新規コンポーネントとインターフェースをとるときの挿入時間とハッシュ衝突との少なくとも一つを低減する、前記コントローラと、
複数のテーブルおよびバケットあたり複数のキーを使うことによって前記ハッシュ衝突を低減する、衝突回避装置と、
前記複数のキーを前記複数のテーブルにマップするための、前記コントローラと交信するハッシュ装置であって、前記ハッシュ装置は、一つのキーが変更されたとき、単一のハッシュ・ロジックを用いて雪崩効果を施し、これは前記複数のテーブル中のビットのほぼ半数の変更をもたらす、前記ハッシュ装置と、
を含むシステム。
【請求項２】
前記単一のハッシュ・ロジックはＣｕｃｋｏｏアルゴリズムに基づく、請求項１に記載のシステム。
【請求項３】
前記単一のハッシュ・ロジックは更新設定可能な巡回冗長検査多項式を含む、請求項１に記載のシステム。
【請求項４】
前記ハッシュ装置は、前記雪崩効果に基づいて前記複数のテーブルの並列テーブル・ルックアップを設ける、請求項１に記載のシステム。
【請求項５】
前記雪崩効果は、前記複数のテーブルの各々に対する直交ハッシュ関数列に基づいており、前記単一のハッシュ・ロジックが各直交ハッシュ関数を実行する、請求項１に記載のシステム。
【請求項６】
前記単一のハッシュ・ロジックの各ビット出力は、前記キーのビットの絞り込み結果を含む、請求項５に記載のシステム。
【請求項７】
前記絞り込み結果はＸＯＲ関数によって生成される、請求項６に記載のシステム。
【請求項８】
前記複数のテーブルは更新設定可能である、請求項１に記載のシステム。
【請求項９】
前記複数のテーブルの全体負荷は、前記単一のハッシュ・ロジックの出力に対するビットの数を制御することによって更新設定可能である、請求項８に記載のシステム。
【請求項１０】
コンピュータ・プロセッサを包含するコントローラに新規コンポーネントが導入されるときの挿入時間とハッシュ衝突との少なくとも一つを低減するステップと、
衝突回避装置を介し、複数のテーブルおよびバケットあたり複数のキーを使うことによって前記ハッシュ衝突を低減するステップと、
前記コントローラと交信するハッシュ装置を使って、前記複数のキーを前記複数のテーブルにマップするステップであって、前記ハッシュ装置は、一つのキーが変更されたとき、単一のハッシュ・ロジックを用いて雪崩効果を施し、これは前記複数のテーブル中のビットのほぼ半数の変更をもたらす、前記マップするステップと、
を含む方法。
【請求項１１】
前記ハッシュ装置を介し前記雪崩効果に基づいて、前記複数のテーブルの並列テーブル・ルックアップを設けるステップをさらに含む、請求項１０に記載の方法。
【請求項１２】
前記雪崩効果を、前記複数のテーブルの各々に対する直交ハッシュ関数列に基づくものとするステップをさらに含み、前記単一のハッシュ・ロジックが各直交ハッシュ関数を実行する、請求項１０に記載の方法。
【請求項１３】
前記単一のハッシュ・ロジックの各ビット出力に対する前記キーのビットの結果を絞り込むステップをさらに含む、請求項１２に記載の方法。
【請求項１４】
前記複数のテーブルを更新設定可能にするステップをさらに含む、請求項１０に記載の方法。
【請求項１５】
前記単一のハッシュ・ロジック出力に対するビットの数を制御することによって、前記複数のテーブルの全体負荷を更新設定可能にするステップをさらに含む、請求項１４に記載の方法。
【請求項１６】
有形の媒体中に具現されたコンピュータ・プログラムであって、
コンピュータ・システムを改良するための、前記有形の媒体と組み合わされたコンピュータ可読プログラム・コードであって、前記コンピュータ可読プログラム・コードは、前記プログラムに、
コンピュータ・プロセッサを包含するコントローラに新規コンポーネントが導入されるときの挿入時間とハッシュ衝突との少なくとも一つを低減することと、
衝突回避装置を介し、複数のテーブルおよびバケットあたり複数のキーを使うことによって前記ハッシュ衝突を低減することと、
前記コントローラと交信するハッシュ装置を使って、前記複数のキーを前記複数のテーブルにマップすることであって、前記ハッシュ装置は、一つのキーが変更されたとき、単一のハッシュ・ロジックを用いて雪崩効果を施し、これは前記複数のテーブル中のビットのほぼ半数の変更をもたらす、前記マップすることと、
を行わせる前記コンピュータ可読プログラム・コード、
を含む、前記コンピュータ・プログラム。
【請求項１７】
前記ハッシュ装置を介し、前記雪崩効果に基づいて前記複数のテーブルの並列テーブル・ルックアップを設けるよう構成されたプログラム・コードをさらに含む、請求項１６に記載のコンピュータ・プログラム。
【請求項１８】
前記雪崩効果を、前記複数のテーブルの各々に対する直交ハッシュ関数列に基づくものとするよう構成されたプログラム・コードをさらに含み、前記単一のハッシュ・ロジックが各直交ハッシュ関数を実行する、請求項１６に記載のコンピュータ・プログラム。
【請求項１９】
前記単一のハッシュ・ロジックの各ビット出力に対する前記キーのビットの結果を絞り込むよう構成されたプログラム・コードをさらに含む、請求項１８に記載のコンピュータ・プログラム。
【請求項２０】
前記複数のテーブルを更新設定可能にするよう構成されたプログラム・コードをさらに含む、請求項１６に記載のコンピュータ・プログラム。
【請求項２１】
前記単一のハッシュ・ロジックの出力に対するビットの数を制御することによって、前記複数のテーブルの全体負荷を更新設定可能にするよう構成されたプログラム・コードをさらに含む、請求項２０に記載のコンピュータ・プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明はコンピュータ・システムの分野に関し、さらに具体的には、非常に大きなテーブルおよび非常に高いスループットのための、コンピュータ実装のパケット・ルックアップ・メカニズムに関する。
【背景技術】
【０００２】
イーサネット（Ｒ）ポートは、コンピュータとコンピュータ・ネットワークとの間の接続を提供することができる。１００Ｇｂｐｓのイーサネット（Ｒ）ポートに対し、最小の６４バイト・パケットの継続時間は６．７ナノ秒であり、ロジックが検索を行うために与えられるのは、５００Ｍｈｚでたったの３クロック・サイクルである。
【発明の概要】
【発明が解決しようとする課題】
【０００３】
例えば、１００Ｇｂｐｓのイーサネット（Ｒ）アプリケーション中で使われている、結合数の少ないテーブル・ルックアップにおいて、「Ｃｕｃｋｏｏアルゴリズム」などの連鎖法を用いる従来式のハッシュ法を使って検索を行うことは可能であるが、これの欠点は、非常に大きなテーブル中に多くのハッシュ衝突が存在する場合の挿入時間が長いことである。
【課題を解決するための手段】
【０００４】
本発明の一つの実施形態によれば、改良されたコンピュータ・システムには、コンピュータ・プロセッサを有するコントローラを含めることができ、該コントローラは、コントローラに導入される新規コンポーネントとインターフェースをとるときの挿入時間もしくはハッシュ衝突またはその両方を低減する。また、本システムには、複数のテーブルおよびバケットあたり複数のキーを使うことによってハッシュ衝突を低減する衝突回避装置も含めることができる。本システムには、複数のキーを複数のテーブルにマップするための、コントローラと交信するハッシュ装置をさらに含めることができ、該ハッシュ装置は、一つのキーが変更されたとき、単一のハッシュ・ロジックを用いて雪崩効果を施し、これは複数のテーブル中のビットのほぼ半数の変更をもたらす。
【０００５】
この単一のハッシュ・ロジックはＣｕｃｋｏｏアルゴリズムに基づくものとすることができる。該単一のハッシュ・ロジックには、更新設定可能な巡回冗長検査多項式を含めることが可能である。ハッシュ装置は、雪崩効果に基づいて複数のテーブルの並列テーブル・ルックアップを設けることができる。
【０００６】
雪崩効果は、複数のテーブルの各々に対する直交ハッシュ関数列に基づくものとすることができ、単一のハッシュ・ロジックが各直交ハッシュ関数を実行する。単一のハッシュ・ロジックの各ビット出力には、キーのビットの絞り込み結果（ｆｕｎｎｅｌｅｄ  ｒｅｓｕｌｔｓ）を含めることができる。
【０００７】
この絞り込み結果はＸＯＲ関数によって生成することが可能である。これら複数のテーブルは更新設定可能にすることができる。複数のテーブルの全体負荷は、単一のハッシュ・ロジックの出力に対するビットの数を制御することで設定できるようにすることができる。
【０００８】
本発明の別の態様は、コンピュータ・システムを改良するための方法である。本方法には、コンピュータ・プロセッサを包含するコントローラに新規コンポーネントが導入されるときの挿入時間もしくはハッシュ衝突またはその両方を低減するステップを含めることができる。また、本方法には、衝突回避装置を介し、複数のテーブルおよびバケットあたり複数のキーを使うことによってハッシュ衝突を低減するステップも含めることができる。本方法には、コントローラと交信するハッシュ装置を使って、複数のキーを複数のテーブルにマップするステップをさらに含めることができ、該ハッシュ装置は、一つのキーが変更されたとき、単一のハッシュ・ロジックを用いて雪崩効果を施し、これは複数のテーブル中のビットのほぼ半数の変更をもたらす。
【０００９】
本方法には、ハッシュ装置を介し雪崩効果に基づいて、複数のテーブルの並列テーブル・ルックアップを設けるステップを追加して含めることができる。また、本方法には、雪崩効果を、複数のテーブルの各々に対する直交ハッシュ関数列に基づくものとするステップをさらに含めることができ、単一のハッシュ・ロジックが各直交ハッシュ関数を実行する。
【００１０】
本方法には、単一のハッシュ・ロジックの各ビット出力に対する、キーのビットの結果を絞り込むステップをさらに含めることができる。本方法には、複数のテーブルを更新設定可能にするステップを追加して含めることが可能である。また、本方法には、単一のハッシュ・ロジック出力に対するビットの数を制御することによって、これら複数のテーブルの全体負荷を更新設定可能にするステップも含めることができる。
【００１１】
本発明の別の態様は、有形の媒体と組み合わされた、コンピュータ・システムを改良するためのコンピュータ可読プログラム・コードである。本コンピュータ可読プログラム・コードは、新規コンポーネントが、コンピュータ・プロセッサを包含するコントローラに導入されるとき、プログラムに、挿入時間もしくはハッシュ衝突またはその両方を低減させるように構成することが可能である。また、本コンピュータ可読プログラム・コードは、衝突回避装置を介し、複数のテーブルおよびバケットあたり複数のキーを使うことによってハッシュ衝突を低減することができる。本コンピュータ可読プログラム・コードは、さらに、コントローラと交信するハッシュ装置を使って、複数のキーを複数のテーブルにマップすることができ、該ハッシュ装置は、一つのキーが変更されたとき、単一のハッシュ・ロジックを用いて雪崩効果を施し、これは複数のテーブル中のビットのほぼ半数の変更をもたらす。
【００１２】
加えて、本コンピュータ可読プログラム・コードは、ハッシュ装置を介し、雪崩効果に基づいて複数のテーブルの並列テーブル・ルックアップを設けることができる。また、本コンピュータ可読プログラム・コードは、雪崩効果を、複数のテーブルの各々に対する直交ハッシュ関数列に基づくものとすることができ、単一のハッシュ・ロジックが各直交ハッシュ関数を実行する。
【００１３】
本コンピュータ可読プログラム・コードは、さらに、単一のハッシュ・ロジックの各ビット出力に対するキーのビットの結果を絞り込むことができる。加えて、本コンピュータ可読プログラム・コードは、該複数のテーブルを更新設定可能にすることができる。また、本コンピュータ可読プログラム・コードは、単一のハッシュ・ロジックの出力に対するビットの数を制御することによって、これら複数のテーブルの全体負荷を更新設定可能にすることができる。
【図面の簡単な説明】
【００１４】
【図１】本発明による、データベース改良システムを示すブロック図である。
【図２】本発明による、方法の諸態様を示すフローチャートである。
【図３】図２の方法による、方法の諸態様を示すフローチャートである。
【図４】図２の方法による、方法の諸態様を示すフローチャートである。
【図５】図４の方法による、方法の諸態様を示すフローチャートである。
【図６】図２の方法による、方法の諸態様を示すフローチャートである。
【図７】図６の方法による、方法の諸態様を示すフローチャートである。
【図８】本発明による、ＣＣＢテーブル・ルックアップ・エンジンのハイ・レベルの構造を示す。
【図９】本発明による、５モードプログラム可能ハッシュ・ロジックのハイ・レベルの構造を示す。
【図１０】本発明による、４対２の例を示す。
【図１１】本発明による、ＸＯＲマトリックスの例を示す。
【図１２】本発明による、遠隔ルックアップ要求のタイミングを示す。
【図１３】本発明による、「オン・ザ・フライ」比較エンジンを示す。
【発明を実施するための形態】
【００１５】
以降において、本発明の好適な実施形態が示されている添付の図面を参照しながら、本発明を詳述する。図面全体を通して、同様の番号は同様のエレメントを表す。
【００１６】
ここで図１を参照すると、最初に、改良されたコンピュータ・システム１０が表されている。ある実施形態において、システム１０は、コンピュータ・プロセッサ１４を包含するコントローラ１２を含む。コントローラ１２は、該コントローラに導入される新規コンポーネント１６とインターフェースをとるときの挿入時間もしくはハッシュ衝突またはその両方を低減する。また、システム１０は、複数のテーブルおよびバケットあたり複数のキーを使ってハッシュ衝突を低減する衝突回避装置１８も含む。システム１０は、複数のキーを複数のテーブルにマップするための、コントローラ１２と交信するハッシュ装置２０をさらに含み、該ハッシュ装置は、一つのキーが変更されたとき、単一のハッシュ・ロジック２２を用いて雪崩効果を施し、これは複数のテーブル中のビットのほぼ半数の変更をもたらす。システム１０のコンポーネント群は、当業者ならよく理解しているように、通信ネットワーク２１によって繋がれている。
【００１７】
一つの実施形態において、この単一のハッシュ・ロジック２２はＣｕｃｋｏｏアルゴリズムに基づいている。別の実施形態では、この単一のハッシュ・ロジック２２は、更新設定可能な巡回冗長検査（ＣＲＣ：ｃｙｃｌｉｃ  ｒｅｄｕｎｄａｎｃｙ  ｃｈｅｃｋ）多項式を含む。別の実施形態では、ハッシュ装置２０は、雪崩効果に基づいて複数のテーブルの並列テーブル・ルックアップを設ける。
【００１８】
一つの実施形態において、雪崩効果は、複数のテーブルの各々に対する直交ハッシュ関数列に基づき、単一のハッシュ・ロジック２２が各直交ハッシュ関数を実行する。別の実施形態において、単一のハッシュ・ロジック２２の各ビット出力は、キーのビットの絞り込み結果を含む。
【００１９】
一つの実施形態において、この絞り込み結果はＸＯＲ関数によって生成される。別の実施形態において、該複数のテーブルは更新設定可能である。別の実施形態では、これら複数のテーブルの全体負荷は、単一のハッシュ・ロジック２２の出力に対するビット数を制御することによって更新設定が可能である。
【００２０】
本発明の別の態様は、コンピュータ・システムを改良するための方法であって、これについて図２のフローチャート２４を参照しながら以下に説明する。この方法はブロック２６で開始され、ブロック２８で、該方法には、コンピュータ・プロセッサを包含するコントローラに新規コンポーネントが導入されるときの挿入時間もしくはハッシュ衝突またはその両方を低減するステップを含めることができる。また、本方法には、ブロック３０で、衝突回避装置を介し、複数のテーブルおよびバケットあたり複数のキーを使うことによってハッシュ衝突を低減するステップも含めることができる。ブロック３２で、本方法には、コントローラと交信するハッシュ装置を使って、複数のキーを複数のテーブルにマップするステップをさらに含めることができ、該ハッシュ装置は、一つのキーが変更されたとき、単一のハッシュ・ロジックを用いて雪崩効果を施し、これは複数のテーブル中のビットのほぼ半数の変更をもたらす。本方法はブロック３４で終了する。
【００２１】
図３のフローチャート３６を参照しながら以下に説明する別の方法の実施形態では、方法はブロック３８で開始される。本方法には、図２のブロック２８、３０、および３２のステップを含めることができる。ブロック４０で、本方法には、ハッシュ装置を介し雪崩効果に基づいて複数のテーブルの並列テーブル・ルックアップを設けるステップを、追加して含めることができる。本方法はブロック４２で終了する。
【００２２】
図４のフローチャート４４を参照しながら以下に説明する別の方法の実施形態では、方法はブロック４６で開始される。本方法には、図２のブロック２８、３０、および３２のステップを含めることができる。また、ブロック４８で、本方法には、雪崩効果を複数のテーブルの各々に対する直交ハッシュ関数列に基づくものとするステップをさらに含めることができ、単一のハッシュ・ロジックが各直交ハッシュ関数を実行する。本方法はブロック５０で終了する。
【００２３】
図５のフローチャート５２を参照しながら以下に説明する別の方法の実施形態では、方法はブロック５４で開始される。本方法には、図４のブロック２８、３０、３２、および４８のステップを含めることができる。ブロック５６で、本方法には、単一のハッシュ・ロジックの各ビット出力に対するキーのビットの結果を絞り込むステップをさらに含めることができる。本方法はブロック５８で終了する。
【００２４】
図６のフローチャート６０を参照しながら以下に説明する別の方法の実施形態では、方法はブロック６２で開始される。本方法には、図２のブロック２８、３０、および３２のステップを含めることができる。ブロック６４で、本方法には、複数のテーブルを更新設定可能にするステップを追加して含めることができる。本方法はブロック６６で終了する。
【００２５】
図７のフローチャート６８を参照しながら以下に説明する別の方法の実施形態では、方法はブロック７０で開始される。本方法には、図６のブロック２８、３０、３２、および６４のステップを含めることができる。また、ブロック７２で、本方法には、単一のハッシュ・ロジックの出力に対するビットの数を制御することによって、これら複数のテーブルの全体負荷を更新設定可能にするステップも含めることができる。本方法はブロック７４で終了する。
【００２６】
本発明の別の態様は、有形の媒体と組み合わされた、コンピュータ・システムを改良するためのコンピュータ可読プログラム・コードである。本コンピュータ可読プログラム・コードは、コンピュータ・プロセッサ１４を包含するコントローラ１２に新規コンポーネント１６が導入されるときプログラムに挿入時間もしくはハッシュ衝突またはその両方を低減させるように構成することが可能である。また、本コンピュータ可読プログラム・コードは、衝突回避装置１８を介し、複数のテーブルおよびバケットあたり複数のキーを使うことによってハッシュ衝突を低減することができる。本コンピュータ可読プログラム・コードは、さらに、コントローラ１２と交信するハッシュ装置２０を使って、複数のキーを複数のテーブルにマップすることができ、該ハッシュ装置は、一つのキーが変更されたとき、単一のハッシュ・ロジック２２を用いて雪崩効果を施し、これは複数のテーブル中のビットのほぼ半数の変更をもたらす。
【００２７】
加えて、本コンピュータ可読プログラム・コードは、ハッシュ装置２０を介し、雪崩効果に基づいて複数のテーブルの並列テーブル・ルックアップを設けることができる。また、本コンピュータ可読プログラム・コードは、雪崩効果を複数のテーブルの各々に対する直交ハッシュ関数列に基づくものとすることができ、単一のハッシュ・ロジック２２が各直交ハッシュ関数を実行する。
【００２８】
さらに、本コンピュータ可読プログラム・コードは、単一のハッシュ・ロジック２２の各ビット出力に対するキーのビットの結果を絞り込むことが可能である。加えて、本コンピュータ可読プログラム・コードは、複数のテーブルを更新設定可能にすることができる。また、本コンピュータ可読プログラム・コードは、単一のハッシュ・ロジック２２の出力に対するビットの数を制御することによって、これら複数のテーブルの全体負荷を更新設定可能にすることができる。
【００２９】
前述を踏まえ、システム１０は改良されたコンピュータ・システムを提供する。例えば、１００Ｇｂｐｓのイーサネット（Ｒ）アプリケーション中で使われている、結合数の少ないテーブル・ルックアップにおいて、「Ｃｕｃｋｏｏアルゴリズム」などの連鎖法を用いる従来式のハッシュ法を使って検索を行うことは可能であるが、これの欠点は、非常に大きなテーブル中に、多くのハッシュ衝突が存在する場合の長い挿入時間にある。これと対照的に、システム１０は、検索と同じ時間範囲内での挿入を可能にし、これは、プラグ・アンド・プレイ・ネットワークにおけるパケット学習などで、実行中に新規テーブル挿入を行う場合には重要である。
【００３０】
システム１０は、衝突回避および挿入時間低減のため、効率的なハッシュ法もしくはアルゴリズムまたはその両方の選択を用いる。システム１０は、非常に大きなテーブルおよび高いスループットに対するパケット・ルックアップを提供する。
【００３１】
一つの実施形態において、システム１０は、任意の数のロジック・テーブルに対し任意の型のＣＲＣ多項式の除算を使うことが可能な、単一のハッシュ方法のハードウェア実装を提供し、これによりキャッシュ衝突を低減する。システム１０のパケット・ルックアップ機能のハードウェア実装は、大きなキーの非常に多くの数（数億）と非常に高いスループット（１００Ｇｂｐｓイーサネット（Ｒ））をサポートする。別の実施形態において、システム１０は、システム１０が任意の型のＣＲＣ多項式を設定できる単一のロジック２２に基づいている。別の実施形態において、システム１０は、複数のハッシュ演算子に対して直交性および高い雪崩効果を用い、これによりいくつかのテーブルを並行して検索することを可能にして衝突を低減する。
【００３２】
一つの実施形態において、各異なるテーブルに対し、効率的な相直交するハッシュ演算子が使われる。別の実施形態において、効率的処理ために、ハッシュ演算子は、例えば、キーのたった一つのビットが変更された場合でもハッシュ結果のビットの約半数が変更されるといった、高い雪崩効果を施す必要がある。
【００３３】
これは、キーの除算または乗算によって可能であるが、１００Ｇｂｐｓの総量スループットに対する非常に限られたクロック・サイクルでは、このような乗算のハードウェア実装は困難である。ＸＯＲ折り畳みを、ハードウェア中に実装することは可能であるが、これらは良好な雪崩効果を提供しない。ＣＲＣは、良好な雪崩効果を提供し、ＸＯＲ絞り込み法を使いハードウェア中に実装できるので効果的であるが、数多くのロジックＸＯＲ回路を必要とし、相異なるテーブルに対する大きなロジック回路をもたらすことになる。
【００３４】
一つの実施形態において、システム１０は、衝突を低減するために、４つの異なるテーブルおよびバケットあたり８つのキーを用いる。別の実施形態において、単一のプログラム可能ハッシュ機能２２が使われ、そのハッシュ演算結果の各ビットはキーの全ビットの絞り込み結果であり、これは任意の型のＣＲＣ多項式の実装を可能にする。これは、多数のＸＯＲ回路を必要とするが、４つの異なるテーブルに対する単一のロジック２２の共用によって、十分に対応が可能である。
【００３５】
一つの実施形態において、ルックアップ・テーブルによる処理法を最適化するための、このフレキシブルなハードウェア実装には、２〜５個に更新設定可能なハッシュ・テーブルの数を備えることが含まれる（基本的設定は、４つを作動中＋１つの予備とすることができよう）。別の実施形態において、５つのハッシュ演算関数は、全面的に更新設定が可能なＸＯＲマトリックスである。このマトリックスが各種の型のハッシュ設定を可能にするものであっても、ＣＲＣハッシュ関数が望ましい選択肢である。
【００３６】
一つの実施形態において、全体のテーブル負荷は、ハッシュ結果に対するビット数の設定を定めることにより更新設定可能となろう（ハードウェアは、テーブルあたり、１９ｂハッシュ値の４Ｍエントリまでサポートすることができる）。別の実施形態において、「オン・ザ・フライ」のキー比較は、折り返しのＤＭＡ要求および応答を最適化する助力となる。
【００３７】
さらに図８を参照すると、ＣＣＢテーブル・ルックアップ・エンジンのハイ・レベル構造が示されている。一つの実施形態において、ルックアップ処理は、受信されたルックアップ要求と、ハッシュ関数を使ってメモリ・アドレスを計算することと、ＤＭＡ読み取り要求と、ＤＭＡ読み取り応答と、読み取りデータを元のキーと比較することと、ルックアップ応答を要求元に送信することと、を含む。
【００３８】
さらに図９〜１０を参照すると、図９には、５モードのプログラム可能ハッシュ・ロジックのハイ・レベル構造が示されている。図１０には、本発明の４対２の例示的実施形態が開示されている。
【００３９】
おそらくはシステム１０の最もフレキシブルな実装である、一つの実施形態においては、キーの全ビットが任意のハッシュ・ビットに参加することが可能である。この実装では、ハッシュ・ロジック２２中に「インテリジェンス」があるので、ハードウェアと、アルゴリズムの改新およびテーブルの最大数とはほとんど無関係になる。
【００４０】
一つの実施形態において、６４ｂのキー、１９ｂのハッシュ、および５つのハッシュ関数にサイズ形成することによって、
６４＊１９＊５＝６０８０の設定ラッチと、
設定を選択するための（６４＊１９）の５対１のマルチプレクサと、
（６４＊１９）の２対１のＡＮＤゲートと、
１９＊（３２＋１６＋８＋４＋２＋１）＝１１９７の２対１のＸＯＲゲートと、
が設けられる。
【００４１】
４５ｎｍ実装の大まかな面積見積もりは、
ラッチ：６０８０＊１０μｍ２＝６０８００μｍ２
ＸＯＲ２：１１９７＊４μｍ２＝４７８８μｍ２
ＡＮＤ２：６４＊１９＊３μｍ２＝３６４８μｍ２
ＡＯ２２：３＊６４＊１９＊４μｍ２＝１４５９２μｍ２
合計＝（６０８００＋４７８８＋３６４８＋１４５９２）＊１．４（６０％の配線余裕度を想定）＝１１７３５９μｍ２、約０．１２ｍｍ２となる。
【００４２】
図１１は、本発明による、ＸＯＲマトリックスの例を示す。この例では、６４ｂのキーは１６ｂハッシュ値にハッシュされる。
【００４３】
図１２は、遠隔ルックアップ要求のタイミングを示す。この例では、４つのハッシュ・テーブルのケースが示されている。図１３は、「オン・ザ・フライ」比較エンジンを示す。
【００４４】
一つの実施形態において、システム１０は、テーブル・ルックアップのための方法を備えている。この方法には、数億のキーの一つを、テーブル内の例えばバケットなどのスロットにマップするための単一のハッシュ関数を実行する、ハードウェア手段を含めることができ、それによって、該ハッシュ関数は、あるキー中のただ一つのビットが変更されたときでも高い雪崩効果を生成する。また、本方法には、４つの異なるテーブルとバケットあたり８つのキーを実装することによってハッシュ衝突を最少化するための手段を含めることもできる。
【００４５】
一つの実施形態において、システム１０は、任意の型のＣＲＣ多項式に設定することが可能な単一のロジック２２に基づいて、いくつかのテーブルを並行してルックアップができるように、複数のハッシュ演算子に対し直交性および高雪崩効果を用いて衝突を低減しながら、例えば数億といった非常に多くの数の大きなキー、および例えば１００Ｇｂｐｓイーサネット（Ｒ）といった非常に高いスループットをサポートする、パケット・ルックアップ機能のハードウェア実装を提供する。
【００４６】
一つの実施形態において、システム１０は、単一のハッシュ・ロジック２２を実行し、高い雪崩効果によって、キーの非常に大きなセットを、例えばバケットなどのスロットにマップするための方法およびシステムを提供する。別の実施形態において、システム１０は、単一のハッシュ・ロジック２２を４つの異なるテーブルおよびスロット当たり８つのキーに対し共用することによってハッシュ衝突を低減する。
【００４７】
一部の別の実装においては、フローチャートのブロック中に記載された機能が、図に記載された順序を外れて行われ得ることに留意すべきである。本明細書に示されたフロー図は単なる例であるので、例えば、連続して示された２つのブロックが、関与する機能によって実際にはほぼ同時に実行されることがあり、時にはこれらのブロックが逆の順序で実行されることもあり得る。本明細書に記載されたこれらの図またはステップ（またはオペレーション）に対し、本発明の趣旨から逸脱しない多くの変形があり得る。例えば、これらのステップは、同時にもしくは異なった順序でまたはその双方で実施することができ、あるいは、ステップを追加、削除、もしくは修改、またはこれらの組み合わせを実施することが可能である。これら変形の全ては、請求対象の発明の一部と見なされる。
【００４８】
本発明の好適な実施形態を説明してきたが、現在のまたは将来の当業者は、添付の特許請求の範囲に含まれる、さまざまな改良および増強を行うことができよう。これらの請求項は、前述で説明した本発明に対し、適正な保護を保持すると解釈すべきである。
【符号の説明】
【００４９】
１０    コンピュータ・システム
１２    コントローラ
１４    コンピュータ・プロセッサ
１６    新規コンポーネント
１８    衝突回避装置
２０    ハッシュ装置
２１    通信ネットワーク
２２    単一のハッシュ・ロジック
【図１】
2013242539.tif 000003
【図２】
2013242539.tif 000004
【図３】
2013242539.tif 000005
【図４】
2013242539.tif 000006
【図５】
2013242539.tif 000007
【図６】
2013242539.tif 000008
【図７】
2013242539.tif 000009
【図８】
2013242539.tif 000010
【図９】
2013242539.tif 000011
【図１０】
2013242539.tif 000012
【図１１】
2013242539.tif 000013
【図１２】
2013242539.tif 000014
【図１３】
2013242539.tif 000015