(57)【特許請求の範囲】
【請求項１】
コンピュータ・プロセッサを包含するコントローラと、
セレクタ装置によって置き換え対象の候補となる複数のテーブルのうち最も高い衝突品質指標を有するテーブルを選出するための、前記コントローラと交信する前記セレクタ装置と、
前記セレクタ装置により選出された前記テーブルと置き換える、前記複数のテーブルとは別の予備テーブルを作成するための交換装置と、
前記交換装置が作成した前記予備テーブルへの置き換えに基づいて新規のハッシュ関数を使用し、前記予備テーブル中のハッシュ衝突を低減して挿入時間を短縮するのを可能にするスイッチと、
を含むシステム。
【請求項２】
前記セレクタ装置は、前記対象となるテーブル内のキーの配置に基づいて前記対象となるテーブルに対する前記衝突品質指標を判定する、請求項１に記載のシステム。
【請求項３】
ハッシュ関数の効率の目安として前記キーの分布がモニタされる、請求項２に記載のシステム。
【請求項４】
前記交換装置は、オーバーフロー閾値への到達が近くなったときには前記予備テーブルの作成を完了する、請求項１に記載のシステム。
【請求項５】
前記オーバーフロー閾値は、長めの挿入時間に基づいている、請求項４に記載のシステム。
【請求項６】
前記挿入時間は、所定数の衝突が処理された挿入の数をカウントすることによって計算される、請求項５に記載のシステム。
【請求項７】
前記ハッシュ関数はキーの直線分布を含む、請求項１に記載のシステム。
【請求項８】
コントローラと交信するセレクタ装置を使い、置き換え対象の候補となる複数のテーブルのうち最も高い衝突品質指標を有するテーブルを選出するステップと、
交換装置を使い、前記複数のテーブルとは別の予備テーブルを作成して前記セレクタ装置により選出された前記テーブルと置き換えるステップと、
スイッチを使い、前記交換装置が作成した前記予備テーブルへの置き換えに基づいて新規のハッシュ関数を使用し、前記予備テーブル中のハッシュ衝突を低減して挿入時間を短縮するのを可能にするステップと、
を含む方法。
【請求項９】
前記セレクタ装置を使い、前記対象となるテーブル内のキーの配置に基づいて前記対象となるテーブルに対する前記衝突品質指標を判定するステップをさらに含む、請求項８に記載の方法。
【請求項１０】
ハッシュ関数の効率の目安として前記キーの分布をモニタするステップをさらに含む、請求項９に記載の方法。
【請求項１１】
前記交換装置を使い、オーバーフロー閾値への到達が近くなったときには前記予備テーブルの作成を完了するステップをさらに含む、請求項８に記載の方法。
【請求項１２】
コンピュータ・プログラムであって、
コンピュータ・システムを改良するためのコンピュータ可読プログラム・コードを含み
、前記コンピュータ可読プログラム・コードは、コンピュータ・システムに含まれるコンピュータ・プロセッサに、
コンピュータ・システムに含まれるコントローラと交信する、コンピュータ・システムに含まれるセレクタ装置を使い、置き換え対象の候補となる複数のテーブルのうち最も高い衝突品質指標を有するテーブルを選出させ、
コンピュータ・システムに含まれる交換装置を使い、前記複数のテーブルとは別の予備テーブルを作成して前記セレクタ装置により選出された前記テーブルと置き換えさせ、そして
コンピュータ・システムに含まれるスイッチを使い、前記交換装置が作成した前記予備テーブルへの置き換えに基づいて新規のハッシュ関数を使用し、前記予備テーブル中のハッシュ衝突を低減して挿入時間を短縮させる、ように構成される、
前記コンピュータ・プログラム。
【請求項１３】
前記セレクタ装置を使い、前記対象となるテーブル内のキーの配置に基づいて、前記対象となるテーブルに対する前記衝突品質指標を判定するように構成されたプログラム・コードをさらに含む、請求項１２に記載のコンピュータ・プログラム。
【請求項１４】
ハッシュ関数の効率の目安として前記キーの分布をモニタするように構成されたプログラム・コードをさらに含む、請求項１３に記載のコンピュータ・プログラム。
【請求項１５】
前記交換装置を使い、オーバーフロー閾値への到達が近くなったときには前記予備テーブルの作成を完了するように構成されたプログラム・コードをさらに含む、請求項１２に記載のコンピュータ・プログラム。
【請求項１６】
コンピュータ・プロセッサ（１４）を包含する、コントローラ（１２）と、
セレクタ装置（１６）によって置き換え対象の候補となる複数のテーブルのうち最も高い衝突品質指標を有するテーブルを選出するための、前記コントローラと交信する、前記セレクタ装置（１６）と、
前記セレクタ装置により選出された前記テーブルと置き換える、前記複数のテーブルとは別の予備テーブルを作成するための、交換装置（１８）と、
前記交換装置が作成した前記予備テーブルへの置き換えに基づいて新規のハッシュ関数を使用し、前記予備テーブル中のハッシュ衝突を低減して挿入時間を短縮するのを可能にする、スイッチ（２０）と、
を含み、これらが通信ネットワーク（２１）によって繋がれている、システム（１０）。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明はコンピュータ・システムの分野に関し、さらに具体的には、衝突の回避および挿入時間最小化のための効率的なハッシュ処理およびの選択のための改良されたコンピュータ・システムに関する。
【背景技術】
【０００２】
イーサネット（Ｒ）ポートは、コンピュータとコンピュータ・ネットワークとの間の接続を提供することができる。１００Ｇｂｐｓのイーサネット（Ｒ）ポートに対し、最小の６４バイト・パケットの継続時間は６．７ナノ秒であり、ロジックが検索を行うために与えられるのは、５００Ｍｈｚでたったの３クロック・サイクルである。
【発明の概要】
【発明が解決しようとする課題】
【０００３】
例えば、１００Ｇｂｐｓのイーサネット（Ｒ）アプリケーション中で使われている、結合数の少ないテーブル・ルックアップにおいて、「Ｃｕｃｋｏｏアルゴリズム」などの連鎖法を用いる従来式のハッシュ法を使って検索を行うことは可能であるが、これの欠点は、非常に大きなテーブル中に多くのハッシュ衝突が存在する場合の挿入時間が長いことである。
【課題を解決するための手段】
【０００４】
本発明の一つの実施形態によれば、改良されたコンピュータ・システムには、コンピュータ・プロセッサを包含するコントローラを含めることができる。また、本システムには、コントローラと交信するセレクタ装置を含め、該セレクタ装置使い、対象となる他のテーブルよりも高い衝突品質指標を有するテーブルを選出することができる。本システムには、セレクタ装置により選出されたテーブルと置き換える予備テーブルを設定するための交換装置をさらに含めることが可能である。本システムには、交換装置の選出されたテーブルの置き換えに基づいてハッシュ関数を変更し、コントローラが、該コントローラに導入される新規コンポーネントとインターフェースをとるときの挿入時間もしくは衝突またはその両方を低減することを可能にする、スイッチを追加して含めることができる。
【０００５】
セレクタ装置は、対象となるテーブル内のキーの配置に基づいて該対象となるテーブルに対する衝突品質指標を判定することができる。ハッシュ関数の効率の目安としてキーの分布をモニタすることが可能である。
【０００６】
交換装置は、セレクタ装置により選出されたテーブルを置き換えることによって衝突品質指標を下げることができる。交換装置は、新規のハッシュ関数を使用するか、もしくは、セレクタ装置により選出された、対象となる他のテーブルよりも高い衝突品質指標を有するテーブルのエントリを複製するか、またはその両方を行うことによって予備テーブルを設定することができる。
【０００７】
交換装置は、オーバーフロー閾値への到達が近くなったときには予備テーブルの設定を完了することができる。このオーバーフロー閾値は、長めの挿入時間に基づくものとすることが可能である。
【０００８】
この挿入時間は、所定数の衝突が処理された挿入の数をカウントすることによって計算することが可能である。ハッシュ関数にはキーの直線分布（ｌｉｎｅａｒ  ｋｅｙ  ｄｉｓｔｒｉｂｕｔｉｏｎ）を含めることができる。
【０００９】
本発明の別の態様は、コンピュータ・システムを改良するための方法である。本方法には、コントローラと交信するセレクタ装置を使い、対象となる他のテーブルよりも高い衝突品質指標を有するテーブルを選出するステップを含めることができる。また、本方法には、交換装置を使い、予備テーブルを設定してセレクタ装置により選出されたテーブルと置き換えるステップも含めることができる。本方法には、スイッチを使い、交換装置の選出されたテーブルの置き換えに基づいてハッシュ関数を変更し、コントローラが、該コントローラに導入される新規コンポーネントとインターフェースをとるときの挿入時間もしくは衝突またはその両方を低減することを可能にするステップをさらに含めることができる。
【００１０】
本方法には、セレクタ装置を使い、対象となるテーブル内のキーの配置に基づいて該対象となるテーブルに対する衝突品質指標を判定するステップを追加して含めることができる。また、本方法には、ハッシュ関数の効率の目安としてキーの分布をモニタするステップを含めることも可能である。
【００１１】
本方法には、交換装置を使い、セレクタ装置により選出されたテーブルを置き換えることによって衝突品質指標を下げるステップをさらに含めることができる。本方法には、交換装置を使い、新規のハッシュ関数を使用するか、もしくは、セレクタ装置により選出された、対象となる他のテーブルよりも高い衝突品質指標を有するテーブルのエントリを複製するか、またはその両方を行うことによって予備テーブルを設定するステップを追加して含めることができる。また、本方法には、交換装置を使い、オーバーフロー閾値への到達が近くなったときには予備テーブルの設定を完了するステップも含めることも可能である。
【００１２】
本発明の別の実施形態は、（有形の媒体と組み合わされることが可能な、）コンピュータ・システムを改良するためのコンピュータ可読プログラム・コードである。本コンピュータ可読プログラム・コードは、プロセッサに、コントローラと交信するセレクタ装置を使い（ハードウエア資源とソフトウエア資源とが協働することで）、対象となる他のテーブルよりも高い衝突品質指標を有するテーブルを選出させるように構成することができる。また、本コンピュータ可読プログラム・コードは、交換装置を使い、予備テーブルを設定してセレクタ装置により選出されたテーブルと置き換えることが可能である。さらに、本コンピュータ可読プログラム・コードは、スイッチを使い、交換装置の選出されたテーブルの置き換えに基づいてハッシュ関数に変更を施し、コントローラが、該コントローラに導入される新規コンポーネントとインターフェースをとるときの挿入時間もしくは衝突またはその両方を低減することを可能にすることができる。
【００１３】
加えて、本コンピュータ可読プログラム・コードは、セレクタ装置を使い、対象となるテーブル内のキーの配置に基づいて、該対象となるテーブルに対する衝突品質指標を判定することができる。また、本コンピュータ可読プログラム・コードは、ハッシュ関数の効率の目安としてキーの分布をモニタすることが可能である。
【００１４】
また、本コンピュータ可読プログラム・コードは、交換装置を使い、セレクタ装置により選出されたテーブルを置き換えることによって衝突品質指標を下げることもできる。さらに、本コンピュータ可読プログラム・コードは、交換装置を使い、新規のハッシュ関数を使用するか、もしくは、セレクタ装置によって選出された、対象となる他のテーブルよりも高い衝突品質指標を有するテーブルのエントリを複製するか、またはその両方を行うことによって予備テーブルを設定することができる。加えて、本コンピュータ可読プログラム・コードは、交換装置を使い、オーバーフロー閾値への到達が近くなったときには予備テーブルの設定を完了することが可能である。
【図面の簡単な説明】
【００１５】
【図１】本発明による、データベース改良システムを示すブロック図である。
【図２】本発明による、方法態様を示すフローチャートである。
【図３】図２の方法に基づく、方法態様を示すフローチャートである。
【図４】図３の方法に基づく、方法態様を示すフローチャートである。
【図５】図２の方法に基づく、方法態様を示すフローチャートである。
【図６】図２の方法に基づく、方法態様を示すフローチャートである。
【図７】図６の方法に基づく、方法態様を示すフローチャートである。
【図８】本発明による、挿入閾値示すチャートである。
【図９】本発明による、例示的なキーのビットの並べ換え処理を示す一連のチャートである。
【図１０】本発明による、キーの直線分布を用いるハッシュ演算機能を示す図である。
【図１１】本発明による、キーの直線分布を用いるハッシュ演算機能を示す図である。
【図１２】本発明による、ビット並べ換えを使った再構成を示す。
【図１３】本発明による、キーの直線分布と同様な性能を有する、再構成されたハッシュ演算機能を示す図である。
【図１４】本発明による、キーの直線分布と同様な性能を有する、再構成されたハッシュ演算機能を示す図である。
【発明を実施するための形態】
【００１６】
以降において、本発明の好適な実施形態が示されている添付の図面を参照しながら、本発明を詳述する。図面全体を通して、同様の番号は同様のエレメントを表し、単一の実施形態中の類似の部分を識別するために、添え字の付いた同じ番号が使われる。
【００１７】
ここで図１を参照すると、改良されたコンピュータ・システム１０が最初に表されている。ある実施形態において、システム１０は、コンピュータ・プロセッサ１４を包含するコントローラ１２を含む。また、システム１０は、コントローラ１２と交信するセレクタ装置１６を含み、該セレクタ装置によって、対象となる他のテーブルよりも高い衝突品質指標を有するテーブルを選出する。システム１０は、セレクタ装置１６により選出されたテーブルと置き換える予備テーブルを設定するための交換装置１８をさらに含む。システム１０は、交換装置１８の選出されたテーブルの置き換えに基づいてハッシュ関数を変更し、コントローラ１２が、該コントローラに導入される新規コンポーネント２２とインターフェースをとるときの挿入時間もしくは衝突またはその両方を低減することを可能にする、スイッチ２０を追加して含む。システム１０のコンポーネントは、当業者ならよく理解しているように、通信ネットワーク２１によって繋がれる。
【００１８】
一つの実施形態において、セレクタ装置１６は、対象となるテーブル内のキーの配置に基づいて該対象となるテーブルに対する衝突品質指標を判定する。別の実施形態において、ハッシュ関数の効率の目安としてキーの分布をモニタすることが可能である。
【００１９】
一つの実施形態において、交換装置１８は、セレクタ装置１６により選出されたテーブルを置き換えることによって衝突品質指標を下げる。別の実施形態において、交換装置１８は、新規のハッシュ関数を使用するか、もしくは、セレクタ装置１６により選出された、対象となる他のテーブルよりも高い衝突品質指標を有するテーブルのエントリを複製するか、またはその両方を行うことによって予備テーブルを設定する。
【００２０】
一つの実施形態において、交換装置１８は、オーバーフロー閾値への到達が近くなったときには予備テーブルの設定を完了する。別の実施形態において、このオーバーフロー閾値は長めの挿入時間に基づいている。
【００２１】
一つの実施形態において、この挿入時間は、所定数の衝突が処理された挿入の数をカウントすることによって計算される。別の実施形態において、ハッシュ関数はキーの直線分布を含む。
【００２２】
別の態様は、コンピュータ・システムを改良するための方法であり、以降に、図２のフローチャート２４を参照しながらこれを説明する。本方法はブロック２６で開始され、本方法には、ブロック２８で、コントローラと交信するセレクタ装置を使い、対象となる他のテーブルよりも高い衝突品質指標を有するテーブルを選出するステップを含めることができる。また、本方法には、ブロック３０で、交換装置を使い、予備テーブルを設定してセレクタ装置により選出されたテーブルと置き換えるステップも含めることができる。本方法には、ブロック３２で、スイッチを使い、交換装置の選出されたテーブルの置き換えに基づいてハッシュ関数を変更し、コントローラが、該コントローラに導入される新規コンポーネントとインターフェースをとるときの挿入時間もしくは衝突またはその両方を低減することを可能にするステップをさらに含めることができる。本方法はブロック３４で終了する。
【００２３】
図３のフローチャート３６を参照しながら以下に説明する別の方法の実施形態では、方法はブロック３８で開始される。本方法には、図２のブロック２８、３０、および３２のステップを含めることができる。本方法には、ブロック４０で、セレクタ装置を使い、対象となるテーブル内のキーの配置に基づいて該対象となるテーブルに対する衝突品質指標を判定するステップを追加して含めることができる。本方法はブロック４２で終了する。
【００２４】
図４のフローチャート４４を参照しながら以下に説明する別の方法の実施形態では、方法はブロック４６で開始される。本方法には、図３のブロック２８、３０、３２、および４０のステップを含めることができる。また、本方法には、ブロック４８で、ハッシュ関数の効率の目安としてキーの分布をモニタするステップも含めることができる。本方法はブロック５０で終了する。本方法はブロック５０で終了する。
【００２５】
図５のフローチャート５２を参照しながら以下に説明する別の方法の実施形態では、方法はブロック５４で開始される。本方法には、図２のブロック２８、３０、および３２のステップを含めることができる。本方法には、ブロック５６で、交換装置を使い、セレクタ装置により選出されたテーブルを置き換えることによって衝突品質指標を下げるステップをさらに含めることができる。本方法はブロック５８で終了する。
【００２６】
図６のフローチャート６０を参照しながら以下に説明する別の方法の実施形態では、方法はブロック６２で開始される。本方法には、図２のブロック２８、３０、および３２のステップを含めることができる。本方法には、ブロック６４で、交換装置を使い、新規のハッシュ関数を使用するか、もしくは、セレクタ装置により選出された、対象となる他のテーブルよりも高い衝突品質指標を有するテーブルのエントリを複製するか、またはその両方を行うことによって予備テーブルを設定するステップを追加して含めることができる。本方法はブロック６６で終了する。
【００２７】
図７のフローチャート６８を参照しながら以下に説明する別の方法の実施形態では、方法はブロック７０で開始される。本方法には、図６のブロック２８、３０、３２、および６４のステップを含めることができる。また、本方法には、ブロック７２で、交換装置を使い、オーバーフロー閾値への到達が近くなったときには予備テーブルの設定を完了するステップも含めることができる。本方法はブロック７４で終了する。
【００２８】
本発明の別の態様は、（有形の媒体と組み合わされることが可能な、）コンピュータ・システム１０を改良するためのコンピュータ可読プログラム・コードである。本コンピュータ可読プログラム・コードは、コンピュータに、コントローラ１２と交信するセレクタ装置１６を使い、対象となる他のテーブルよりも高い衝突品質指標を有するテーブルを選出させるように構成することができる。また、本コンピュータ可読プログラム・コードは、交換装置１８を使い、予備テーブルを設定してセレクタ装置１６により選出されたテーブルと置き換えることが可能である。さらに、本コンピュータ可読プログラム・コードは、スイッチ２０を使い、交換装置１８の選出されたテーブルの置き換えに基づいてハッシュ関数に変更を施し、コントローラ１２が、該コントローラに導入される新規コンポーネント２２とインターフェースをとるときの挿入時間もしくは衝突またはその両方を低減することを可能にすることができる。
【００２９】
加えて、本コンピュータ可読プログラム・コードは、セレクタ装置１６を使い、対象となるテーブル内のキーの配置に基づいて、該対象となるテーブルに対する衝突品質指標を判定することができる。また、本コンピュータ可読プログラム・コードは、ハッシュ関数の効率の目安としてキーの分布をモニタすることが可能である。
【００３０】
また、本コンピュータ可読プログラム・コードは、交換装置１８を使い、セレクタ装置１６により選出されたテーブルを置き換えることによって衝突品質指標を下げることができる。さらに、本コンピュータ可読プログラム・コードは、交換装置１８を使い、新規のハッシュ関数を使用するか、もしくは、セレクタ装置１６によって選出された、対象となる他のテーブルよりも高い衝突品質指標を有するテーブルのエントリを複製するか、またはその両方を行うことによって予備テーブルを設定することができる。加えて、本コンピュータ可読プログラム・コードは、交換装置１８を使い、オーバーフロー閾値への到達が近くなったときには予備テーブルの設定を完了することが可能である。
【００３１】
前述の事項を踏まえ、システム１０は改良されたコンピュータ・システムを提供する。例えば、１００Ｇｂｐｓのイーサネット（Ｒ）アプリケーション中で使われている、結合数の少ないテーブル・ルックアップにおいて、「Ｃｕｃｋｏｏアルゴリズム」などの連鎖法を用いる従来式のハッシュ法を使って検索を行うことは可能であるが、これの欠点は、非常に大きなテーブル中に多くのハッシュ衝突が存在する場合の挿入時間が長いことである。これと対照的に、システム１０は、検索と同じ時間範囲内での挿入を可能にし、このことは、プラグ・アンド・プレイ・ネットワークにおけるパケット学習などで、実行中に新規テーブル挿入を行う場合には重要である。
【００３２】
システム１０は、衝突の回避および挿入時間の低減のため、効率的なハッシュ処理もしくはアルゴリズムの選択またはその両方を用いる。システム１０は、衝突品質指標を測定し次いでこの指標を低減または最小化する新規のテーブル多項式に切り替える方法、を用いる。
【００３３】
システム１０は、以下の３つのステップを実施し、より低効率なテーブルの逐次的な置き換えに基づいて、複数のハッシュ演算機能／テーブルを具えるルックアップ・メカニズムを使い、衝突を最少化することによって挿入時間を短縮する。第一は、より低効率なテーブルを見出すための測定である。第二は、最適な予備ハッシュ演算機能の構成および対応する予備テーブルの作成である。第三は、実行中に、より低効率なテーブルを予備テーブルで置き換えることである。
【００３４】
挿入に時間がかかりすぎる（オーバーフロー限度に達した）場合、より低効率なテーブルが新しいものと置き換えられる。
【００３５】
これは、旧来のＣｕｃｋｏｏアルゴリズム対処法で行われたように、３つの他のテーブル中のエントリを再ハッシュする必要なくして行われる。
【００３６】
テーブル中への挿入は、各テーブルに対する衝突品質指標が計算できるようにして行われる。より低効率なテーブルのエントリは、新規のハッシュ演算機能を具えた第五のテーブルに複写される（これは、バックグラウンドで行われ、いろいろなハッシュ演算機能をテストすることができる）。
【００３７】
あるエントリがこの第五のテーブルに配置できない場合、それは３つの他のテーブルにはまだインストールはされない（だが、新規ハッシュ演算機能の効率の見当を得るため単に記録はされる）。オーバーフローに達すると、より低効率なテーブルのエントリの第五テーブル中への転送が（第五テーブル中へのインストールができない場合の３つの他のテーブル中へのインストールと併せ）行われる。システム１０は、ハードウェアに対し、新規ルックアップ・テーブルへの切り替えをするためのアトミック操作を発行する。
【００３８】
システム１０は、衝突品質指標の測定を施す。テーブル中への挿入は、各テーブルに対する衝突品質指標が計算できるようにして行われる。
【００３９】
システム１０は、挿入処理の過程で、Ｎ個のハッシュ関数（Ｎ＝テーブルの数）を使い新規のキーをハッシュする。システム１０は、最も多くの空白エントリを有するバケット中に挿入を行う。システム１０は、テーブルごとの空白バケットの数を把握している。結果として、上記により全てのテーブルがほぼ同じ負荷を有することになる。そして、オーバーフローが検出されたとき、より低効率なテーブルとされるのは最多の空白バケットを有するものである。
【００４０】
さらに図８を参照すると、一つの実施形態において、挿入時間が長くなりすぎたとき、オーバーフローが検出されている。これは、所定数の衝突が処理された（長い挿入の閾値）挿入の数をカウントすることによって達成できる。このカウントが所定の閾値に達したとき、オーバーフローが検出される。この時点で、より低効率なテーブルが置き換えられることになる。
【００４１】
システム１０は、最も適切なハッシュ関数を定義することができる。短時間でオーバーフローに達する場合、これはキー分布の著しい変化に起因する可能性が高い。
【００４２】
システム１０は、キーのエントロピを測定しそれに適切に対応する。初期状態は、ハッシュ関数がキーの直線分布に対し最適化されている状態とすることができよう。その後、オーバーフローが検出されたとき、システム１０は、例えばＸＯＲマトリックスなどの新規ハッシュ関数を設定し、そのハッシュ関数がキーの直線分布を取り扱う。
【００４３】
さらに図９を参照すると、システム１０は、キー分布の測定を施している。一つの実施形態において、システム１０は、６４個のカウンタ（キーのビットあたりに一つ）＋一つの全体カウンタを使用する。システム１０は、挿入ごとに全体カウンタをインクリメントし、各キー・ビットに対しては、ｉｆ（ｂｉｔ＝１）の場合、ｃｏｕｎｔｅｒ［ｂｉｔ］のインクリメントを行う。また、システム１０は、キーの除去ごとに全体カウンタをデクリメントし、各キー・ビットに対しては、ｉｆ（ｂｉｔ＝１）の場合、ｃｏｕｎｔｅｒ［ｂｉｔ］のデクリメントを行う。
【００４４】
また、システム１０は、新規アルゴリズムの選択を施す。一つの実施形態において、システム１０は、各ビットに対するトグル比率を計算し、ｉｆ  ｃｏｕｎｔｅｒ［ｂｉｔ］／ＧｌｏｂａｌＣｏｕｎｔ／２であれば、ｃｏｕｎｔｅｒ［ｂｉｔ］＝（ＧｌｏｂａｌＣｏｕｎｔ／２）−（Ｃｏｕｎｔ［ｉ］−ＧｌｏｂａｌＣｏｕｎｔ／２）に変更する。また、システム１０は、ビットを、より小さなトグル・ビットから最も大きいトグル・ビットの順に並べ換えて、キーを直線分布に戻すことができる。さらに、システム１０は、並べ換えを考慮に入れて、ビットを選択するためＸＯＲマトリックスを再設定することも可能である。別の実施形態において、システム１０は、ビット毎カウンタのスキームの代わりにバイト毎カウンタのスキームを使用する。
【００４５】
さらに図１０〜１４を参照すると、図１０および図１１はＸＯＲマトリックスの再構成の例である（８ｂのキー対２ｂのハッシュ）。この初期ハッシュ演算機能構成は、キーの直線分布に対して最適化されているものと前提する。
【００４６】
図１２は、ビットの並べ換えによる再構成を示す。並びに、図１３および図１４は、あたかもキー分布が直線分布であるのと同じようなパフォーマンスを有する再構成ハッシュ演算機能を示す。
【００４７】
一つの実施形態において、システム１０は、数億のキーの一つを複数のテーブル中の一つのスロットにマップするための、ハードウェア内の単一のハッシュ関数を実行するための方法を具える。本方法は、複数のテーブルの１つ１つに対する衝突品質指標を判定するステップと、最も高い衝突品質指標を有するテーブルを選出するステップとを含む。また、本方法は、予備テーブルを設定するステップと、最も高い衝突品質指標を有するテーブルを予備テーブルと取り替え、該テーブルに対する衝突品質指標を低減するステップも含む。本方法は、スイッチ管理エレメントに対し、最高の衝突品質指標を有するテーブルが予備テーブルで置き換えられており、これにより該テーブルは新規のハッシュ関数を用いることになること、を通知するステップをさらに含む。
【００４８】
一つの実施形態において、システム１０は、各テーブルに同じ数のキーを配置すること、すなわち複数のテーブルへの公平なキー配分の試行に基づいて、特定の挿入アルゴリズムを使用する。別の実施形態において、システム１０は、衝突品質指標を測定するやり方として、未利用のバケットのパーセントもしくはテーブルのローディング率（良好な散布）またはその両方を用いる。
【００４９】
一つの実施形態において、システム１０は、キー分布が直線分布であれば、良好な雪崩を有し、相互に直行する相異なる巡回冗長検査（ＣＲＣ：ｃｙｃｌｉｃ  ｒｅｄｕｎｄａｎｃｙ  ｃｈｅｃｋ）多項式をどのように選択するかを存知する。短時間でハッシュ演算機能が劣化する場合、それはキー分布の著しい変化に起因する。従って、考え方は、キーのエントロピを測定し、ビット群を並べ換えて、それらがＸＯＲマトリックスに入力されるとき直線分布のように見えるようにすることである。
【００５０】
システム１０は、より良好な予備ハッシュ演算機能を判定する。一つの実施形態において、システム１０は、キーのエントロピ（インストールされたキーの各ビット）の連続的な測定を施す。これには、ビットごとに一つのカウンタと、一つの全体カウンタが使われる。
【００５１】
キー挿入処理に対し全体カウンタがインクリメントされ、各キー・ビットに対しては、ｉｆ（ｂｉｔ＝１）の場合、ｃｏｕｎｔｅｒ［ｂｉｔ］のインクリメントが行われる。
【００５２】
キーの除去処理に対し全体カウンタがデクリメントされ、各キー・ビットに対しては、ｉｆ（ｂｉｔ＝１）の場合、ｃｏｕｎｔｅｒ［ｂｉｔ］のデクリメントが行われる。
【００５３】
システム１０は、ＣＲＣ多項式が良好な雪崩パターンを生成するように、ＸＯＲマトリックスの直前でキーのビットを並べ換える。
【００５４】
システム１０は、予備テーブルを作成する。より低効率なテーブルのエントリは、新規のハッシュ演算機能構成を具えた第五のテーブルに複写される（これは、バックグラウンドで行い、いろいろなハッシュ演算機能をテストすることができる）。あるエントリが第五のテーブルに配置できない場合、それは３つの他のテーブルにはまだインストールされない（だが、新規ハッシュ演算機能の効率の見当を得るため単に記録はされる）。
【００５５】
システム１０は、切り替えを施す。オーバーフローに達すると、より低効率なテーブルのエントリの第五テーブルへの転送が（第五テーブル中への転送ができない場合は３つの他のテーブル中へのインストールと併せ）行われる。システム１０は、ハードウェアに対し、新規ルックアップ・テーブルへの切り替えをするためのアトミック操作を発行する。
【００５６】
一つの実施形態において、システム１０は、ハッシュ値の直線分布に対して最適化されたハッシュ関数を使って予備ハッシュ・テーブルを設定すること、およびより低効率のハッシュ・テーブルをその予備ハッシュ・テーブルで置き換えることを開示する。
【００５７】
一部の別の実装においては、フローチャートのブロック中に記載された機能が、図に記載された順序を外れて行われ得ることに留意すべきである。本明細書に示されたフロー図は単なる例であるので、例えば、連続して示された２つのブロックが、関与する機能によって実際にはほぼ同時に実行されることがあり、時にはこれらのブロックが逆の順序で実行されることもあり得る。本明細書に記載されたこれらの図またはステップ（またはオペレーション）に対し、本発明の趣旨から逸脱しない多くの変形があり得る。例えば、これらのステップは、同時にもしくは異なった順序でまたはその双方で実施することができ、あるいは、ステップを追加、削除、もしくは修改、またはこれらの組み合わせを実施することが可能である。これら変形の全ては請求対象の発明の一部と見なされる。
【００５８】
本明細書で使用する用語は、単に特定の実施形態を説明する目的のためのものであり、本発明を限定することは意図されていない。本明細書で用いられる、単数形「ある（“ａ”、“ａｎ”）」、および「該（“ｔｈｅ”）」は、文脈上明確に別途に示されていなければ、複数形も同じように含むことが意図されている。さらに、当然のことながら本明細書で用いられる「含む（“ｃｏｍｐｒｉｓｅ”）」もしくは「含んでいる（“ｃｏｍｐｒｉｓｉｎｇ”）」またはその両方は、述べられた機能、完全体、ステップ、オペレーション、エレメント、もしくはコンポーネント、またはこれらの組み合わせの存在を特定するが、一つ以上の他の機能、完全体、ステップ、オペレーション、エレメント、コンポーネント、もしくはこれらの群、または上記の組み合わせの存在を排除するものではない。
【００５９】
添付の特許請求の範囲におけるミーンズ・プラス・ファンクションまたはステップ・プラス・ファンクションの要素全ての、対応する構造、材料、動作および均等物は、具体的に請求された他の請求要素と組み合わせてその機能を遂行するための、一切の構造、材料または動作を包含することが意図されている。本発明の記述は、例示および説明の目的で提示されたもので、網羅的であることも、または本発明を開示した形態に限定することも意図されていない。当業者には、本発明の範囲および趣旨から逸脱することのない多くの修改および変形が明白であろう。本実施形態は、本発明の原理および実際的な応用を最善に説明し、他の当業者が、意図する特定の用途に適したさまざまな修改を加えたさまざまな実施形態に関して、本発明を理解できるように選択し説明されたものである。
【００６０】
本発明の好適な実施形態を説明してきたが、当然のことながら、現在のおよび将来双方の当業者は、添付の特許請求の範囲に含まれるさまざまな改良および増強を行うことができよう。これらの請求項は、前述で説明した本発明に対し、適正な保護を保持すると解釈すべきである。
【符号の説明】
【００６１】
１０  システム
１２  コントローラ
１４  コンピュータ・プロセッサ
１６  セレクタ装置
１８  交換装置
２０  スイッチ
２１  通信ネットワーク
２２  新規コンポーネント
【図１】
0006474189.tif 000002
【図２】
0006474189.tif 000003
【図３】
0006474189.tif 000004
【図４】
0006474189.tif 000005
【図５】
0006474189.tif 000006
【図６】
0006474189.tif 000007
【図７】
0006474189.tif 000008
【図８】
0006474189.tif 000009
【図９】
0006474189.tif 000010
【図１０】
0006474189.tif 000011
【図１１】
0006474189.tif 000012
【図１２】
0006474189.tif 000013
【図１３】
0006474189.tif 000014
【図１４】
0006474189.tif 000015