(57)【要約】  第1および第2のハッシュ値が、パケットに関連する情報から構築されたキーを使用して生成される。ブロック番号が、第1のテーブル内のスロット内のセルから読み取られ、第1のテーブル内のスロットが第1のハッシュ値によって索引付けされ、セルが第2のハッシュ値によって索引付けされる。第2のテーブル内のスロット内のブロックを対象とするメモリアクセス操作が、ブロックからパケットについてのパケット処理情報を含むデータを読み取るために実施される。第2のテーブル内のスロットが第1のハッシュ値によって索引付けされ、ブロックがブロック番号によって索引付けされる。パケットは、パケット処理情報に従って処理される。
2017519433.tif 000002
【特許請求の範囲】
【請求項１】
第1のパケットに関連する情報から構築された第1のキーを使用して、第1のハッシュ値および第2のハッシュ値を生成するステップと、
第1のテーブル内のスロット内のセルから第1のブロック番号を読み取るステップであって、前記第1のテーブル内の前記スロットが、前記第1のハッシュ値によって索引付けされ、前記セルが前記第2のハッシュ値によって索引付けされる、ステップと、
第2のテーブル内のスロット内のブロックを対象とするメモリアクセスを実施して、前記第1のパケットについてのパケット処理情報を含むデータを前記ブロックから読み取るステップであって、前記第2のテーブル内の前記スロットが、前記第1のハッシュ値によって索引付けされ、前記ブロックが前記第1のブロック番号によって索引付けされる、ステップと、
前記第1のパケットについての前記パケット処理情報に従って前記第1のパケットを処理するステップと
を含むパケット処理方法。
【請求項２】
前記第1のハッシュ値を生成する前記ステップが、前記第1のキーに第1のハッシュ関数を適用するステップを含み、
前記第2のハッシュ値を生成する前記ステップが、前記第1のキーに第2のハッシュ関数を適用するステップを含む、
請求項1に記載の方法。
【請求項３】
前記ブロックを対象とする前記メモリアクセスを実施する前記ステップが、前記第2のテーブルを記憶するメモリから、前記ブロックをバーストで読み取るステップを含む、請求項1に記載の方法。
【請求項４】
前記ブロックが複数のコリジョン要素を記憶し、
前記複数のコリジョン要素のうちの各コリジョン要素が、それぞれのキーと、前記それぞれのキーに関連するそれぞれのパケット処理情報とを記憶し、
前記ブロックを対象とする前記メモリアクセスを実施する前記ステップが、前記複数のコリジョン要素を読み取るステップを含む、
請求項1に記載の方法。
【請求項５】
前記複数のコリジョン要素のうちのコリジョン要素のそれぞれのキーが前記第1のキーに合致すると判定するステップをさらに含み、
前記第1のパケットを処理する前記ステップが、前記第1のキーに合致する前記それぞれのキーを有する前記コリジョン要素内の前記それぞれのパケット処理情報に従って前記第1のパケットを処理するステップを含む、請求項4に記載の方法。
【請求項６】
前記複数のコリジョン要素を読み取る前記ステップが、
前記第2のテーブルを記憶するメモリ内のメモリオフセットを求めるステップと、
前記メモリオフセットを有する前記メモリ内の位置を読み取るステップと
を含み、
前記メモリオフセットを求める前記ステップが、式(h1(k)*n+q*(第1のブロック番号))*yを計算するステップを含み、上式で、h1(k)は、前記第1のハッシュ値であり、nは、前記第2のテーブルの各スロット内のコリジョン要素の数であり、qは、前記複数のコリジョン要素内のコリジョン要素の数であり、yは、各コリジョン要素のサイズである、
請求項4に記載の方法。
【請求項７】
前記第1のテーブルがスタティックランダムアクセスメモリ(SRAM)内に記憶され、
前記第2のテーブルがダイナミックランダムアクセスメモリ(DRAM)内に記憶される、
請求項1に記載の方法。
【請求項８】
前記第1のブロック番号が前記第2のテーブルについての有効なブロック番号であると判定するステップをさらに含み、
前記ブロックを対象とする前記メモリアクセスが、前記第1のブロック番号が前記第2のテーブルについての有効なブロック番号であると判定したことに応答して実施される、請求項1に記載の方法。
【請求項９】
前記第1のパケットについての前記パケット処理情報が出力ポートを指定し、
前記第1のパケットについての前記パケット処理情報に従って前記第1のパケットを処理する前記ステップが、送信のために前記出力ポートに前記第1のパケットを供給するステップを含む、
請求項1に記載の方法。
【請求項１０】
前記第2のテーブルが第2のパケットについてのパケット処理情報を記憶しないと判定するステップと、
前記第2のパケットに関連する情報から構築された第2のキーを使用して、第3のハッシュ値および第4のハッシュ値を生成するステップと、
第3のテーブル内のスロット内のセルから第2のブロック番号を読み取るステップであって、前記第3のテーブル内の前記スロットが、前記第3のハッシュ値によって索引付けされ、前記第3のテーブル内の前記スロット内の前記セルが、前記第4のハッシュ値によって索引付けされ、
第4のテーブル内のスロット内のブロックを対象とするメモリアクセスを実施して、前記第2のパケットについてのパケット処理情報を含むデータを前記ブロックから読み取るステップであって、前記第4のテーブル内の前記スロットが、前記第3のハッシュ値によって索引付けされ、前記第4のテーブル内の前記スロット内の前記ブロックが、前記第2のブロック番号によって索引付けされるステップと、
前記第2のパケットについての前記パケット処理情報に従って前記第2のパケットを処理するステップと
をさらに含む請求項1に記載の方法。
【請求項１１】
前記第3のハッシュ値を生成する前記ステップが、前記第2のキーに第3のハッシュ関数を適用するステップを含み、
前記第4のハッシュ値を生成する前記ステップが、前記第2のキーに第4のハッシュ関数を適用するステップを含む、
請求項10に記載の方法。
【請求項１２】
前記第2のテーブルが前記第2のパケットについてのパケット処理情報を記憶しないと判定する前記ステップが、
前記第2のキーを使用して第5のハッシュ値および第6のハッシュ値を生成するステップと、
前記第1のテーブル内で、前記第5のハッシュ値によって索引付けされたスロット内の前記第6のハッシュ値によって索引付けされたセルを読み取るステップと、
前記第5のハッシュ値によって索引付けされた前記スロット内の前記第6のハッシュ値によって索引付けされた前記セルから読み取った値が、前記第2のテーブルが前記第2のパケットについてのパケット処理情報を記憶しないことを示すと判定するステップと
を含む請求項10に記載の方法。
【請求項１３】
前記第4のテーブル内の前記スロット内の前記ブロックが、複数のコリジョン要素を記憶し、
前記複数のコリジョン要素の各コリジョン要素が、それぞれのキーと、前記それぞれのキーに関連するそれぞれのパケット処理情報とを記憶し、
前記第4のテーブル内の前記スロット内の前記ブロックを対象とするメモリアクセスを実施する前記ステップが、前記複数のコリジョン要素を読み取るステップを含む、
請求項10に記載の方法。
【請求項１４】
前記複数のコリジョン要素のうちのコリジョン要素のそれぞれのキーが前記第2のキーに合致すると判定するステップをさらに含み、
前記第2のパケットを処理する前記ステップが、前記第2のキーに合致する前記それぞれのキーを有する前記コリジョン要素内の前記それぞれのパケット処理情報に従って前記第2のパケットを処理するステップを含む、請求項13に記載の方法。
【請求項１５】
前記複数のコリジョン要素を読み取る前記ステップが、
前記第4のテーブルを記憶するメモリ内のメモリオフセットを求めるステップと、
前記メモリオフセットを有する前記メモリ内の位置を読み取るステップと
を含み、
前記メモリオフセットを求める前記ステップが、式(h3(k)*n+q*(第2のブロック番号))*yを計算するステップを含み、上式で、h3(k)は、前記第3のハッシュ値であり、nは、前記第4のテーブルの各スロット内のコリジョン要素の数であり、qは、前記複数のコリジョン要素内のコリジョン要素の数であり、yは、各コリジョン要素のサイズである、
請求項13に記載の方法。
【請求項１６】
前記第3のテーブルがSRAM内に記憶され、
前記第4のテーブルがDRAM内に記憶される、
請求項10に記載の方法。
【請求項１７】
前記第4のテーブル内の前記スロット内の前記ブロックを対象とする前記メモリアクセスを実施する前記ステップが、前記第4のテーブルを記憶するメモリから、前記第4のテーブル内の前記スロット内の前記ブロックをバーストで読み取るステップを含む、請求項10に記載の方法。
【請求項１８】
パケット処理のために使用されるルックアップテーブルを維持する方法であって、
第1の複数のスロットに分割された第1のテーブルを作成するステップであって、前記第1の複数のスロットの各スロットが、第1の複数のセルに分割される、ステップと、
第2の複数のスロットに分割された第2のテーブルを作成するステップであって、前記第2の複数のスロットの各スロットが、第1の複数のブロックに分割される、ステップと、
第1のキーを使用して第1のハッシュ値および第2のハッシュ値を生成するステップと、
前記第2のテーブル内のそれぞれのスロット内のそれぞれのブロック内に、前記第1のキーおよび前記第1のキーに関連するパケット処理情報を記憶するステップであって、前記第2のテーブル内の前記それぞれのスロットが、第1のハッシュ値によって索引付けされ、前記それぞれのブロックが第1のブロック番号を有する、ステップと、
前記第1のテーブル内のそれぞれのスロット内のそれぞれのセル内に前記第1のブロック番号を記憶するステップであって、前記第1のテーブル内の前記それぞれのスロットが、前記第1のハッシュ値によって索引付けされ、前記第1のテーブル内の前記それぞれのスロット内の前記それぞれのセルが、前記第2のハッシュ値によって索引付けされる、ステップと
を含む方法。
【請求項１９】
前記第1の複数のブロックの各ブロックが、複数のコリジョン要素を含み、
前記第1のキーおよび前記第1のキーに関連する前記パケット処理情報を記憶する前記ステップが、前記第2のテーブル内の前記それぞれのスロット内の前記それぞれのブロック内のコリジョン要素内に、前記第1のキーおよび前記第1のキーに関連する前記パケット処理情報を記憶するステップを含む、
請求項18に記載の方法。
【請求項２０】
前記第1のテーブルを作成する前記ステップが、第1のメモリ内に前記第1のテーブルを記憶するステップを含み、
前記第2のテーブルを作成する前記ステップが、第2のメモリ内に前記第2のテーブルを記憶するステップを含む、
方法が、前記第1の複数のブロックのそれぞれのブロックに、前記第1の複数のブロックの他のブロックとは独立にアクセスするステップをさらに含む、
請求項18に記載の方法。
【請求項２１】
前記第1の複数のセルのそれぞれのセルに、前記第1の複数のセルの他のセルとは独立にアクセスするステップをさらに含む、請求項20に記載の方法。
【請求項２２】
第3の複数のスロットに分割された第3のテーブルを作成するステップであって、前記第3の複数のスロットの各スロットが、第2の複数のセルに分割される、ステップと、
第4の複数のスロットに分割された第4のテーブルを作成するステップであって、前記第4の複数のスロットの各スロットが、第2の複数のブロックに分割される、ステップと、
第2のキーを使用して第3のハッシュ値および第4のハッシュ値を生成するステップと、
前記第4のテーブル内のそれぞれのスロット内のそれぞれのブロック内に、前記第2のキーおよび前記第2のキーに関連するパケット処理情報を記憶するステップであって、前記第4のテーブル内の前記それぞれのスロットが、前記第3のハッシュ値によって索引付けされ、前記それぞれのブロックが第2のブロック番号を有する、ステップと、
前記第3のテーブル内のそれぞれのスロット内のそれぞれのセル内に前記第2のブロック番号を記憶するステップであって、前記第3のテーブル内の前記それぞれのスロットが、前記第3のハッシュ値によって索引付けされ、前記第3のテーブル内の前記それぞれのスロット内の前記それぞれのセルが、前記第4のハッシュ値によって索引付けされる、ステップと
をさらに含む請求項18に記載の方法。
【請求項２３】
第1のパケットに関連する情報から構築された第1のキーを使用して、第1のハッシュ値および第2のハッシュ値を生成するためのハッシングモジュールと、
第1のテーブル内のスロット内のセルから第1のブロック番号を読み取ることであって、前記第1のテーブル内の前記スロットが、前記第1のハッシュ値によって索引付けされ、前記セルが、前記第2のハッシュ値によって索引付けされること、および
第2のテーブル内のスロット内のブロックを対象とするメモリアクセスを実施し、前記ブロックから、パケット処理情報を含むデータを読み取ることであって、前記第2のテーブル内の前記スロットが、前記第1のハッシュ値によって索引付けされ、前記ブロックが、前記第1のブロック番号によって索引付けされること
を行うためのテーブルアクセスモジュールと、
前記ブロックから読み取ったパケット処理情報に従って前記第1のパケットを処理するためのパケット処理モジュールと
を備えるパケット処理システム。
【請求項２４】
前記テーブルアクセスモジュールが、前記ブロックから複数のコリジョン要素を読み取るためのものであり、前記複数のコリジョン要素のそれぞれのコリジョン要素が、それぞれのキーおよび前記それぞれのキーに関連するそれぞれのパケット処理情報を記憶し、
前記テーブルアクセスモジュールが、前記複数のコリジョン要素のうちのコリジョン要素のそれぞれのキーが前記第1のキーに合致すると判定するための比較論理機構を備え、
前記パケット処理モジュールが、前記第1のキーに合致する前記それぞれのキーを有する前記コリジョン要素内の前記それぞれのパケット処理情報に従って前記第1のパケットを処理するためのものである、
請求項23に記載のシステム。
【請求項２５】
前記第1のテーブルを記憶するためのスタティックランダムアクセスメモリ(SRAM)と、
前記第2のテーブルを記憶するためのダイナミックランダムアクセスメモリ(DRAM)と
をさらに備える、請求項23に記載のシステム。
【請求項２６】
前記テーブルアクセスモジュールがさらに、
前記第1のブロック番号が前記第2のテーブルについての有効なブロック番号であるかどうかを判定し、
前記第1のブロック番号が前記第2のテーブルについての有効なブロック番号であると判定したことに応答して、前記第2のテーブル内の前記スロット内の前記ブロックを対象とする前記メモリアクセスを実施する
ためのものである、請求項23に記載のシステム。
【請求項２７】
パケットを受信および送信するための複数のポートをさらに備え、
前記パケット処理モジュールが、前記ブロックから読み取ったパケット処理情報を使用して、送信のために前記複数のポートのそれぞれのポートに前記第1のパケットをルーティングするためのものである、請求項23に記載のシステム。
【請求項２８】
前記テーブルアクセスモジュールがさらに、前記第2のテーブルが第2のパケットについてのパケット処理情報を記憶しないと判定するためのものであり、
前記ハッシングモジュールがさらに、前記第2のパケットに関連する情報から構築された第2のキーを使用して、第3のハッシュ値および第4のハッシュ値を生成するためのものであり、
前記テーブルアクセスモジュールがさらに、
第3のテーブル内のスロット内のセルから第2のブロック番号を読み取ることであって、前記第3のテーブル内の前記スロットが、前記第3のハッシュ値によって索引付けされ、前記第3のテーブル内の前記スロット内の前記セルが、前記第4のハッシュ値によって索引付けされること、および
第4のテーブル内のスロット内のブロックを対象とするメモリアクセスを実施し、パケット処理情報を含むデータを読み取ることであって、前記第4のテーブル内の前記スロットが、前記第3のハッシュ値によって索引付けされ、前記第4のテーブル内の前記スロット内の前記ブロックが、前記第2のブロック番号によって索引付けされること
を行うためのものであり、
前記パケット処理モジュールがさらに、前記第4のテーブル内の前記スロット内の前記ブロックから読み取ったパケット処理情報に従って前記第2のパケットを処理するためのものである、
請求項23に記載のシステム。
【請求項２９】
第1のパケットに関連する情報から構築された第1のキーを使用して、第1のハッシュ値および第2のハッシュ値を生成するための手段を備える、ハッシングのための手段と、
テーブルを読み取るための手段であって、
第1のテーブル内のスロット内のセルから第1のブロック番号を読み取るための手段であって、前記第1のテーブル内の前記スロットが、前記第1のハッシュ値によって索引付けされ、前記セルが、前記第2のハッシュ値によって索引付けされる、手段と、
第2のテーブル内のスロット内のブロックを対象とするメモリアクセスを実施するための手段であって、前記第2のテーブル内の前記スロットが、前記第1のハッシュ値によって索引付けされ、前記ブロックが、前記第1のブロック番号によって索引付けされる、手段と
を備える手段と、
前記ブロックから読み取ったパケット処理情報に従って前記第1のパケットを処理するための手段を備える、パケットを処理するための手段と
を備えるパケット処理システム。
【請求項３０】
テーブルを読み取るための前記手段が、前記第2のテーブルが第2のパケットについてのパケット処理情報を記憶しないと判定するための手段をさらに備え、
ハッシングのための前記手段が、前記第2のパケットに関連する情報から構築された第2のキーを使用して、第3のハッシュ値および第4のハッシュ値を生成するための手段をさらに備え、
テーブルを読み取るための前記手段が、
第3のテーブル内のスロット内のセルから第2のブロック番号を読み取るための手段であって、前記第3のテーブル内の前記スロットが、前記第3のハッシュ値によって索引付けされ、前記第3のテーブル内の前記スロット内の前記セルが、前記第4のハッシュ値によって索引付けされる、手段と、
第4のテーブル内のスロット内のブロックを対象とするメモリアクセスを実施するための手段であって、前記第4のテーブル内の前記スロットが、前記第3のハッシュ値によって索引付けされ、前記第4のテーブル内の前記スロット内の前記ブロックが、前記第2のブロック番号によって索引付けされる、手段と
をさらに備え、
パケットを処理するための前記手段が、前記第4のテーブル内の前記スロット内の前記ブロックから読み取ったパケット処理情報に従って前記第2のパケットを処理するための手段をさらに備える、
請求項29に記載のシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本実施形態は、一般にはパケット処理に関し、詳細には、パケット処理でのルックアップのために使用されるハッシュテーブルに関する。
【背景技術】
【０００２】
パケット処理チップでは、パケット情報(たとえば、パケットヘッダからのメタデータ)が、ルックアップテーブル内のパケット処理情報をルックアップするためのキーとして使用され得る。パケット処理情報は、パケット転送および/または分類のために使用される。たとえば、キーは、転送テーブル内の転送情報をルックアップするために使用される。ルックアップテーブル(たとえば、転送テーブル)は複数のスロットに分割される。各スロットは、それぞれのコリジョン要素を記憶するための複数のセルを有し得る。各コリジョン要素は、それぞれのキーについてのパケット処理情報ならびにキー自体を記憶する。スロットは、ハッシュ関数h(k)を使用して索引付けされ、ここでkはキーである。ハッシュ関数は複数のキーを同一のスロットに対応付けるので、複数のコリジョン要素が各スロット内に含まれる。特定のキーkについてのパケット処理情報を探索するために、索引h(k)を有するスロット内のコリジョン要素が読み取られ、コリジョン要素内に記憶されたキー値がkと比較され得る。合致は、合致するコリジョン要素がkについてのパケット処理情報を記憶することを示す。
【０００３】
セル数を増加させることによって、ルックアップテーブル(たとえば、転送テーブル)についての使用率、したがってスロット当たりのコリジョン要素が増加し得る。スロット当たりのコリジョン要素の数が増加するにつれてルックアップ成功の可能性が増大する。しかしながら、スロット当たりのセル数を増加させると、ルックアップを実施するときにスロットから読み取るべきデータ量が増大し、パケットを処理するための待ち時間が増大する。待ち時間の増大の結果、性能が低下する。
【発明の概要】
【発明が解決しようとする課題】
【０００４】
したがって、メモリアクセスを制限するが、高い使用率を実現するパケット処理ルックアップ技法が求められている。
【課題を解決するための手段】
【０００５】
いくつかの実施形態では、パケット処理方法が、パケットに関連する情報から構築されたキーを使用して第1および第2のハッシュ値を生成することを含む。ブロック番号が、第1のテーブル内のスロット内のセルから読み取られ、第1のテーブル内のスロットが第1のハッシュ値によって索引付けされ、セルが第2のハッシュ値によって索引付けされる。第2のテーブル内のスロット内のブロックを対象とするメモリアクセス操作が、ブロックからパケットについてのパケット処理情報を含むデータを読み取るために実施される。第2のテーブル内のスロットが第1のハッシュ値によって索引付けされ、ブロックがブロック番号によって索引付けされる。パケットは、パケット処理情報に従って処理される。
【０００６】
いくつかの実施形態では、パケット処理のために使用されるルックアップテーブルを維持する方法が、第1の複数のスロットに分割された第1のテーブルを作成すること、および第2の複数のスロットに分割された第2のテーブルを作成することを含む。第1の複数のスロットの各スロットが、複数のセルに分割される。第2の複数のスロットの各スロットが、複数のブロックに分割される。第1および第2のハッシュ値が、キーを使用して生成される。キーおよびキーに関連するパケット処理情報が、第2のテーブル内のそれぞれのスロット内のそれぞれのブロック内に記憶され、第2のテーブル内のそれぞれのスロットが、第1のハッシュ値によって索引付けされ、それぞれのブロックがブロック番号によって索引付けされる。ブロック番号が、第1のテーブル内のそれぞれのスロット内のそれぞれのセル内に記憶され、第1のテーブル内のそれぞれのスロットが、第1のハッシュ値によって索引付けされ、第1のテーブル内のそれぞれのスロット内のそれぞれのセルが、第2のハッシュ値によって索引付けされる。
【０００７】
いくつかの実施形態では、パケット処理システムが、パケットに関連する情報から構築されたキーを使用して第1および第2のハッシュ値を生成するためのハッシングモジュールを含む。パケット処理システムはまた、第1のテーブル内のスロット内のセルからブロック番号を読み取り、第2のテーブル内のスロット内のブロックを対象とするメモリアクセスを実施し、ブロックからパケット処理情報を含むデータを読み取るためのテーブルアクセスモジュールをも含む。第1のテーブル内のスロットが第1のハッシュ値によって索引付けされ、セルが第2のハッシュ値によって索引付けされる。第2のテーブル内のスロットが第1のハッシュ値によって索引付けされ、ブロックがブロック番号によって索引付けされる。パケット処理システムは、ブロックから読み取ったパケット処理情報に従ってパケットを処理するためのパケット処理モジュールをさらに含む。
【０００８】
本実施形態が例として図示され、本実施形態は添付の図面の図によって限定されないものとする。
【図面の簡単な説明】
【０００９】
【図１】いくつかの実施形態による、パケットを処理するためのシステムのブロック図である。
【図２Ａ】いくつかの実施形態による、ハッシュテーブルおよび対応するスタブテーブルのブロック図である。
【図２Ｂ】いくつかの実施形態による、図2Aのハッシュテーブル内のブロックを示す図である。
【図３】いくつかの実施形態による、2つのハッシュテーブルおよび2つの対応するスタブテーブルを示すブロック図である。
【図４Ａ】いくつかの実施形態による、パケットを処理する方法の流れ図である。
【図４Ｂ】いくつかの実施形態による、パケットを処理する方法の流れ図である。
【図５Ａ】いくつかの実施形態による、ルックアップテーブルを維持する方法の流れ図である。
【図５Ｂ】いくつかの実施形態による、ルックアップテーブルを維持する方法の流れ図である。
【発明を実施するための形態】
【００１０】
図面および本明細書全体にわたって、同様の参照番号は対応する部分を指す。
【００１１】
以下の説明では、本開示の完全な理解を与えるために、特定の構成要素、回路、およびプロセスの例などの多数の特定の詳細が述べられる。さらに、以下の説明では、説明のために、本実施形態の完全な理解を与えるために特定の名称が述べられる。しかしながら、これらの特定の詳細が本実施形態を実施するのに必要ではないことがあることは当業者には明らかであろう。別の例では、本開示を曖昧にすることを避けるために、周知の回路およびデバイスがブロック図で示される。本明細書で使用される「結合される」という用語は、直接的に接続されること、または1つまたは複数の介在構成要素または回路を通じて接続されることを意味する。本明細書に記載の様々なバスを介して供給される信号のいずれかは、他の信号と時間多重化され、1つまたは複数の共通バスを介して供給され得る。さらに、回路要素またはソフトウェアブロックの間の相互接続は、バスとして、または単一の信号線として示され得る。あるいは、バスの各々は単一の信号線であり得、あるいは、単一の信号線の各々はバスであり得、単一の線またはバスは、構成要素間の通信のための無数の物理機構または論理機構のうちの任意の1つまたは複数を表し得る。本実施形態は、本明細書に記載の特定の例に限定されると解釈されるべきではなく、むしろその範囲内に、添付の特許請求の範囲によって定義されるすべての実施形態を含むべきである。
【００１２】
図1は、いくつかの実施形態による、パケットを処理するためのシステム100のブロック図である。いくつかの実施形態では、システム100は、ネットワークスイッチまたはルータの部分である。システム100は、パケットを受信および送信する複数のポート102を含む。ポート102は処理回路104に結合され、処理回路104は、メモリ120およびメモリ124に結合される。処理回路104は、メモリコントローラ(単純化のために図示せず)を通じてメモリ120および/またはメモリ124に結合され得る。
【００１３】
メモリ120は、1つまたは複数のハッシュテーブル122を記憶し、ハッシュテーブル122は、それぞれのパケットをどのように処理するかを指定するパケット処理情報を記憶する。1つまたは複数のハッシュテーブル122は、それぞれスロットに分割され、スロットはバケットとも呼ばれることがある。スロットはブロックに分割され、ブロックはセルに分割される。セルはビンとも呼ばれることがある。各セルはコリジョン要素を記憶し、各コリジョン要素は、それぞれのキーについてのパケット処理情報ならびにキー自体を記憶する。メモリ124は1つまたは複数のスタブテーブル126を記憶する。1つまたは複数のスタブテーブル126はそれぞれスロットに分割され、スロットはそれぞれセルに分割される。1つまたは複数のスタブテーブル126内のセルは、いくつかの実施形態による、1つまたは複数のハッシュテーブル122内のブロックに対するポインタを記憶する(本明細書で使用される「セル」という用語は、スロットの一部を指す。ハッシュテーブル122内で、セルはコリジョン要素を記憶する。スタブテーブル126内で、セルは、対応するハッシュテーブル122内のブロックを指し示すブロック番号を記憶する。したがって、本明細書で使用される用語としての「セル」は、「メモリセル」と同じ物ではない。そうではなく、スロット内の各セルは複数のメモリセルを含む。)。1つまたは複数のハッシュテーブル122および1つまたは複数のスタブテーブル126の例が、図2A、図2B、および図3に関連して以下で説明される。
【００１４】
処理回路104は、キー構築モジュール106、ハッシングモジュール108、テーブルアクセスモジュール110、パケット処理モジュール116、およびテーブル保守モジュール119を含む。キー構築モジュール106は、1つまたは複数のハッシュテーブル122内に記憶されたパケット処理情報をルックアップする際に使用されるキーを構築する。キーは、キー構築規則に従って、パケットに関連する(たとえば、パケットから抽出された)情報を使用して構築される。たとえば、キーは、パケットヘッダから抽出されたメタデータを使用して構築され得る。一例では、パケットヘッダの宛先アドレスが抽出され、キーとして使用される。別の例では、パケットのパケットヘッダ(たとえば、インターネットプロトコル(IP)ヘッダ)全体が抽出され、キーとして使用される。
【００１５】
キー構築モジュール106によって構築されたキーは、ハッシングモジュール108に与えられ、ハッシングモジュール108は、キーをハッシングしてハッシュ値を生成する。ハッシングモジュール108は、それぞれにキーについて複数のハッシュ値を生成し得る。いくつかの実施形態では、ハッシングモジュール108は複数のハッシュ関数を実装する。たとえば、ハッシングモジュール108は、第1のハッシュ関数h1をキーkに適用して第1のハッシュ値h1(k)を生成し、第2のハッシュ関数h2をキーkに適用して第2のハッシュ値h2(k)を生成し得る。ハッシングモジュール108はさらに、第3のハッシュ関数h3をキーkに適用して第3のハッシュ値h3(k)を生成し、第4のハッシュ関数h4をキーkに適用して第4のハッシュ値h4(k)を生成し得る。別個のハッシング関数の使用はハッシュ値h1(k)、h2(k)、h3(k)、および/またはh4(k)を生成することの一例にすぎず、他の例も可能である。
【００１６】
ハッシングモジュール108によって生成されたハッシュ値は、キー構築モジュール106によって構築されたキーとともにテーブルアクセスモジュール110に与えられる。テーブルアクセスモジュール110は、ハッシュ値を使用して、1つまたは複数のスタブテーブル126および1つまたは複数のハッシュテーブル122にアクセスする。ハッシュ値を使用してこれらのテーブルにアクセスすることの例が、図2Aおよび図3に関連して以下で与えられ、図4A〜図4Bの方法400、および図5A〜図5Bの方法500でも与えられる。いくつかの実施形態では、テーブルアクセスモジュール110は、ハッシュテーブル122内のコリジョン要素から読み取ったキーをキー構築モジュール106によって与えられたキーと比較するための比較論理機構112を含む。いくつかの実施形態では、テーブルアクセスモジュール110は、スタブテーブル126内のセルから読み取ったブロック番号が有効なブロックポインタであるかどうかを判定するための検証論理機構114を含む。
【００１７】
テーブルアクセスモジュール110によってハッシュテーブル122から取り出されたパケット処理情報が、パケット処理モジュール116に与えられ、パケット処理モジュール116は、パケット処理情報に従ってパケットを処理する。いくつかの実施形態では、パケット処理モジュール116は、パケット処理情報によって指定される出力ポート102にパケットを送信のためにルーティングするパケット転送エンジン118を含む。
【００１８】
テーブル保守モジュール119は、1つまたは複数のハッシュテーブル122および1つまたは複数のスタブテーブル126を構築し、更新する。たとえば、テーブル保守モジュール119は、1つまたは複数のハッシュテーブル122内にキーおよび対応するパケット処理情報を記憶し、1つまたは複数のスタブテーブル126内に対応するブロック番号を記憶する。
【００１９】
いくつかの実施形態では、メモリ120は処理回路104の外部にある。たとえば、処理回路104はパケット処理チップ内に実装され、メモリ120は1つまたは複数の外部メモリチップ内に実装される。メモリ124は、処理回路104と同一の集積回路(すなわち、同一のチップ)内で(たとえば、キャッシュメモリとして)実施され得る。あるいは、メモリ124は、処理回路104を含む集積回路(たとえば、パケット処理チップ)の外部の1つまたは複数のメモリチップ内に実装され得る。いくつかの実施形態では、メモリ120はダイナミックランダムアクセスメモリ(DRAM)であり、メモリ124はスタティックランダムアクセスメモリ(SRAM)である。いくつかの実施形態では、メモリ120はダブルデータレート(DDR)メモリ(たとえば、DDR DRAM)である。
【００２０】
図2Aは、いくつかの実施形態による、ハッシュテーブル202および対応するスタブテーブル210のブロック図である。ハッシュテーブル202は、メモリ120(図1)内のハッシュテーブル122の一例であり、スタブテーブル210は、メモリ124(図1)内のスタブテーブル126の一例である。ハッシュテーブル202は、mが1より大きい整数であるとして、m個のスロット(すなわち、バケット)204に分割され、したがってハッシュテーブル202は、スロット204-0から204-(m-1)を含む。スロット204-0から204-(m-1)は、ハッシュ値の第1のセットh1(k)を使用して(たとえば、第1のハッシュ関数h1(k)を使用して)索引付けされ、ただしh1(k)の値は、0から(m-1)の間の範囲である。したがって、特定のキーkに適用されるh1(k)の値は、ハッシュテーブル202内のスロット204の索引を与える。
【００２１】
ハッシュテーブル202内の各スロット204は、pが1より大きい整数であるとして、p個のブロック206に分割され、したがって各スロット204は、ブロック206-0から206-(p-1)を含む。図2Bは、いくつかの実施形態によるブロック206を示す。ブロック206は、qが1より大きい整数であるとして、q個のそれぞれのコリジョン要素220を記憶するq個のセルに分割され、したがってブロックは、コリジョン要素220-0から220-(q-1)を含む。各コリジョン要素220は、キー222およびパケット処理情報224を含む。各ブロック206は、同一のスロット204内の他のブロック206とは独立にアクセスされ得る。いくつかの実施形態では、ブロック206は、単一のメモリトランザクション(たとえば、メモリ120を処理回路104に結合するデータバスについての単一のバス要求トランザクション)でメモリ120から読み取ることを可能にするサイズx(たとえば、バイト単位)を有する。多くの要因が、システム効率を改善するためのxの値の選択に影響を及ぼし得る(たとえば、データバーストサイズ、キャッシュ線サイズ)。たとえば、(たとえば、メモリ120がDDRであるとき)、バス要求トランザクションは、メモリ120から読み取られたデータの単一のバーストを参照し得、したがってブロック206は、メモリ120についてのデータバースト当たりのバイト数に等しいサイズxを有する。一例では、メモリ120は、データバースト当たり128バイト(すなわち、128B)を有するDRAMであり、ブロック206は128Bである(すなわち、x=128B)。各コリジョン要素220、すなわち各セルは、q=ceiling(x/y,1)(すなわち、xをyで割り、最も近い整数に切り上げたもの)となるようなyバイトである。各スロット204はn個のコリジョン要素、すなわちn個のセルを有する。したがって各スロット204は、p=ceiling(n/q,1)であるとして、p個のブロック206に分割される。
【００２２】
スタブテーブル210はm個のスロット212に分割され、したがってスタブテーブルは、スロット212-0から212-(m-1)を含む。スロット212-0から212-(m-1)は、ハッシュテーブル202内のスロット204-0から204-(m-1)のように、ハッシュ値の第1のセットh1(k)を使用して(たとえば、第1のハッシュ関数h1(k)を使用して)索引付けされる。各スロット212は、bがp以上の整数であるとして、b個のセル214に分割され、したがって各スロットは、セル214-0から214-(b-1)を含む。一例では、bはnに等しい。各セル214のサイズはceiling(log2(p),1)(すなわち、ハッシュテーブル202の各スロット204内のブロック206の数の2を底とする対数を最も近い整数に切り上げたもの)である。スタブテーブル210のビット単位のサイズは、ceiling(log2(p),1)*m*bである。
【００２３】
セル214-0から214-(b-1)は、ハッシュ値の第2のセットh2(k)を使用して(たとえば、第2のハッシュ関数h2(k)を使用して)索引付けされ、ただしh2(k)の値は、0からb-1の間の範囲である。したがって、特定のキーkに適用されるh2(k)の値は、スタブテーブル210内のセル214の索引を与える。スロット212内のセル214-0から214-(b-1)は、ブロック206のブロック番号を、ハッシュテーブル202内の対応するスロット204内に記憶する。図2Aの例では、スロット212-(m-1)内のセル214-1は、ハッシュテーブル202のスロット204-(m-1)内のブロック206-0のブロック番号である「0」を記憶する。スロット212-(m-1)内のセル214-2は、ハッシュテーブル202のスロット204-(m-1)内のブロック206-(p-1)のブロック番号である値「p-1」を記憶する。したがって、スロット212-(m-1)内のセル214-1は、スロット204-(m-1)内のブロック206-0に対するポインタを記憶し、したがってスロット212-(m-1)内のセル214-2は、スロット204-(m-1)内のブロック206-(p-1)に対するポインタを記憶する。いくつかの実施形態では、各セル214は、同一のスロット212内の他のセル214とは独立にアクセスされ得る。
【００２４】
したがって、キーkについてのコリジョン要素220は、スタブテーブル210内の対応するセル214内に記憶されたブロック番号で指定されるブロック206内のハッシュテーブル202内に記憶される。対応するセル214はh2(k)によって索引付けされ、h1(k)によって索引付けされたスロット212内にあり、一方、コリジョン要素220は、h1(k)によって索引付けされたスロット204内にある。
【００２５】
一例では、ハッシュテーブル202はDRAM内に実装され、スタブテーブル210はSRAM内に実装され、m=8k、n=16、x=128B、y=32B、およびb=16である。したがってp=4およびq=4である。したがって、ハッシュテーブル202のサイズは8k*16*32B=4メガバイト(MB)であり、したがってスタブテーブル219のサイズは2*8k*16ビット=256キロビット=32キロバイト(KB)である。4MB DRAMハッシュテーブル202は、いくつかの応用例に従って高い使用率を実現し、ブロック番号を記憶する32KB SRAMスタブテーブル210の追加は、DRAMアクセスのサイズを制限し、その結果、待ち時間が低下する。
【００２６】
ハッシュテーブル202がルックアップにおいて使用されるキーについてのコリジョン要素を含まない場合、ルックアップは失敗する。システム100の負荷因子を増大させることによってルックアップ失敗の可能性が低減され得る。負荷因子は、エントリ数をバケット(すなわち、スロット)数で割ったものと定義され、エントリ数は、テーブル内に首尾よく挿入されたエントリ数を指す。システム100が高い負荷因子とともに低いコリジョン率を有することが望ましい。低いコリジョン率を達成しながら負荷因子を改善するために、第2のハッシュテーブル122および対応するスタブテーブル126がシステム100内に含まれ得る。
【００２７】
図3は、いくつかの実施形態による、ハッシュテーブル202およびスタブテーブル210(図2A)とともに使用され得る第2のハッシュテーブル302および第2のスタブテーブル310を示すブロック図である。ハッシュテーブル302は、メモリ120(図1)内のハッシュテーブル122の一例であり、スタブテーブル310は、メモリ124(図1)内のスタブテーブル126の一例である。ハッシュテーブル302およびスタブテーブル310は、ハッシュテーブル202が特定のキーについてのコリジョン要素を記憶しないという判定に応答してアクセスされ得る。
【００２８】
ハッシュテーブル302は、cが1より大きい整数であるとして、c個のスロット(すなわち、バケット)304に分割され、したがってハッシュテーブル302は、スロット304-0から304-(c-1)を含む。スロット304-0から304-(c-1)は、ハッシュ値の第3のセットh3(k)(たとえば、第3のハッシュ関数h3(k))を使用して索引付けされ、ただしh3(k)の値は、0から(c-1)の間の範囲である。各スロット304はp個のブロック206に分割され、したがって各スロット304は、ブロック206-0から206-(p-1)を含む。ハッシュテーブル202内のブロック206について説明したのと同様に、各スロット206は、同一のスロット304内の他のブロック206とは独立にアクセスされ得る。スタブテーブル310は、c個のスロット312に分割され、したがってスタブテーブル310は、スロット312-0から312-(c-1)を含む。スロット312-0から312-(c-1)は、スロット304-0から304-(c-1)のように、ハッシュ値の第3のセットh3(k)(たとえば、第3のハッシュ関数h3(k))を使用して索引付けされる。各スロット312はb個のセル214に分割され、したがって各スロット312は、セル214-0から214-(b-1)を含む。セル214-0から214-(b-1)は、ハッシュ値の第4のセットh4(k)(たとえば、第4のハッシュ関数h4(k))を使用して索引付けされ、ただしh4(k)の値は、0からb-1の間の範囲である。スタブテーブル310の各スロット312内のセル214-0から214-(b-1)は、ハッシュテーブル302内の対応するスロット304内のブロック206を指し示すブロック番号を記憶する。いくつかの実施形態では、各セル214は、同一のスロット312内の他のセル214とは独立にアクセスされ得る。
【００２９】
したがって、キーkについてのコリジョン要素220は、スタブテーブル310内の対応するセル214内に記憶されたブロック番号で指定されるブロック206内のハッシュテーブル302内に記憶される。対応するセル214はh4(k)によって索引付けされ、h3(k)によって索引付けされたスロット312内にあり、一方、コリジョン要素220は、h3(k)によって索引付けされたスロット304内にある。
【００３０】
図3の例では、ハッシュテーブル202の各スロット204内のブロック206の数が、ハッシュテーブル302の各スロット304内のブロック206の数に等しいものとして示されている。しかしながら、これらの数は異なり得る。同様に、スタブテーブル210の各スロット212内のセル214の数が、スタブテーブル310の各スロット312内のセル214の数に等しいものとして示されている。しかしながら、これらの数は異なり得る。
【００３１】
図4Aおよび図4Bは、いくつかの実施形態による、パケットを処理する方法400の流れ図を示す。方法400は、たとえばシステム100(図1)内で実施される。
【００３２】
方法400では、第1のパケットが受信される。第1のキーk1が、第1のパケットに関連する情報から(たとえば、パケットヘッダ内のメタデータから)構築される(402、図4A)。第1のキーは、たとえばキー構築モジュール106(図1)によって構築される。
【００３３】
第1のキーを使用してハッシュ値h1(k1)およびh2(k1)が生成される(404、406)。たとえば、第1のハッシュ関数が第1のキーに適用されてハッシュ値h1(k1)が求められ、第2のハッシュ関数が第1のキーに適用されてハッシュ値h2(k1)が求められる。ハッシング動作404および406は、たとえばハッシングモジュール108(図1)によって実施される。
【００３４】
第1のブロック番号が、第1のテーブル内のスロット内のセルから(たとえば、図2Aのスタブテーブル210内のスロット212内のセル214から)(たとえば、図1のテーブルアクセスモジュール110によって)読み取られる(408)。スロットはハッシュ値h1(k1)によって索引付けされ、セルはハッシュ値h2(k1)によって索引付けされる。いくつかの実施形態では、セルは、スロット内の他のセルを読み取ることなく読み取られる。いくつかの実施形態では、第1のブロック番号は、(たとえば、図1のメモリ124内の)第1のテーブルを記憶するメモリから、単一のトランザクション(たとえば、単一のメモリアクセス)で読み取られる。いくつかの実施形態では、第1のテーブルを記憶するメモリはSRAMである。
【００３５】
いくつかの実施形態では、第1のブロック番号が第2のテーブルについての有効なブロック番号であると(たとえば、図1の検証論理機構114によって)判定される(410)。
【００３６】
第2のテーブル内のスロット(たとえば、図2Aのハッシュテーブル202内のスロット204)内のブロック(たとえば、図2Bのブロック206)を対象とするメモリアクセスが実施され(412)、第1のパケットについてのパケット処理情報(たとえば、図2Bのパケット処理情報224)を含むデータが読み取られる。メモリアクセスは、たとえば図1のテーブルアクセスモジュール110によって実施される。スロットはハッシュ値h1(k1)によって索引付けされ、ブロックは第1のブロック番号によって索引付けされる。メモリアクセスでは、ブロックは、スロット内の他のブロックを読み取ることなく読み取られる。いくつかの実施形態では、パケット処理情報は(たとえば、図1の出力ポート102を指定する)パケット転送情報を含む。いくつかの実施形態では、ブロックは、(たとえば、図1のメモリ120内の)第2のテーブルを記憶するメモリから、単一のメモリトランザクション(たとえば、単一のバス要求トランザクション。その一例は単一のバーストである)で読み取られる(414)。いくつかの実施形態では、第2のテーブルを記憶するメモリはDRAMである。
【００３７】
ブロックは、第1のブロック番号が第2のテーブルについての有効なブロック番号であると判定した(410)ことに応答して読み取られ得る。あるいは、動作410の判定が省略され得る。
【００３８】
いくつかの実施形態では、複数のコリジョン要素220-0から220-(q-1)(図2B)がブロックから読み取られる(416)。各コリジョン要素220は、それぞれのキー222と、それぞれのキー222に関連するそれぞれのパケット処理情報224とを記憶する。(たとえば、図1の比較論理機構112を使用して)コリジョン要素220-0から220-(q-1)のうちの1つのそれぞれのキー222が第1のキーと合致すると判定される。そのコリジョン要素220のそれぞれのパケット処理情報224が、第1のパケットについてのパケット処理情報と識別される。
【００３９】
いくつかの実施形態では、複数のコリジョン要素220-0から220-(q-1)を読み取るために、第2のテーブルを記憶するメモリ(たとえば、メモリ120)内のメモリオフセットが、次の式を使用して求められる。
(h1(k1)*n+q*(第1のブロック番号))*y (1)
上式で、h1(k1)は、動作404で生成されたハッシュ値であり、nは、第2のテーブルの各スロット(たとえば、図2Aのハッシュテーブル202の各スロット204)内のコリジョン要素220の数であり、qは、複数のコリジョン要素220-0から220-(q-1)内のコリジョン要素220の数であり、yは、各コリジョン要素220のサイズである。次いで、複数のコリジョン要素220-0から220-(q-1)は、(たとえば、メモリ120内のハッシュテーブル202の開始位置に関して)メモリオフセットを有するメモリ位置から読み取られる。
【００４０】
第1のパケットが、第1のパケットについてのパケット処理情報に従って処理される(418)。いくつかの実施形態では、第1のパケットは、送信のためにパケット処理情報で指定される出力ポートに供給される(420)。たとえば、パケット転送エンジン118が、指定されたポート102(図1)に第1のパケットをルーティングする。
【００４１】
いくつかの実施形態では、第2のパケットが受信される(422、図4B)。第2のキーk2が、第2のパケットに関連する情報から(たとえば、パケットヘッダ内のメタデータから)構築される(422)。第2のキーは、たとえばキー構築モジュール106(図1)によって構築される。
【００４２】
ハッシュ値h1(k2)およびh2(k2)が、第2のキーを使用して生成される(424、426)。たとえば、第1のハッシュ関数が第2のキーに適用されてハッシュ値h1(k2)が求められ、第2のハッシュ関数が第2のキーに適用されてハッシュ値h2(k2)が求められる。ハッシング動作424および426は、たとえばハッシングモジュール108(図1)によって実施される。
【００４３】
ハッシュ値h1(k2)およびh2(k2)を使用して、第2のテーブル(たとえば、ハッシュテーブル202、図2A)が第2のパケットについてのパケット処理情報を記憶しないと判定される(428)。たとえば、第1のテーブル内のh1(k2)によって索引付けされたスロット内のh2(k2)によって索引付けされたセル(たとえば、図2Aのスタブテーブル210内のスロット212内のセル214)が読み取られ、第2のテーブルが第2のパケットについてのパケット処理情報を記憶しないことを、セルから読み取られた値が示すという判定が行われる。たとえば、検証論理機構114(図1)は、セルから読み取られた値が有効なブロック番号ではないと判定する。
【００４４】
ハッシュ値h3(k2)およびh4(k2)が、第2のキーを使用して生成される(430、432)。たとえば、第3のハッシュ関数が第2のキーに適用されてハッシュ値h3(k2)が求められ、第4のハッシュ関数が第2のキーに適用されてハッシュ値h4(k2)が求められる。ハッシング動作430および432は、たとえばハッシングモジュール108(図1)によって実施される。
【００４５】
第2のブロック番号が第3のテーブル内のスロット内のセル(たとえば、図3のスタブテーブル310内のスロット312内のセル214)から読み取られる(434)。スロットはハッシュ値h3(k2)によって索引付けされ、セルはハッシュ値h4(k2)によって索引付けされる。いくつかの実施形態では、セルは、スロット内の他のセルを読み取ることなく読み取られる。いくつかの実施形態では、第2のブロック番号は、(たとえば、図1のメモリ124内の)第3のテーブルを記憶するメモリから、単一のトランザクション(たとえば、単一のメモリアクセス)で読み取られる。いくつかの実施形態では、第3のテーブルを記憶するメモリはSRAMである。
【００４６】
第4のテーブル内のスロット(たとえば、図3のハッシュテーブル302内のスロット304)内のブロック(たとえば、図2Bのブロック206)を対象とするメモリアクセスが実施され(436)、第2のパケットについてのパケット処理情報(たとえば、図2Bのパケット処理情報224)を含むデータが読み取られる。スロットはハッシュ値h3(k2)によって索引付けされ、ブロックは第2のブロック番号によって索引付けされる。メモリアクセスでは、ブロックは、スロット内の他のブロックを読み取ることなく読み取られる。いくつかの実施形態では、ブロックは、(たとえば、図1のメモリ120内の)第4のテーブルを記憶するメモリから、単一のメモリトランザクション(たとえば、単一のバス要求トランザクション。その一例は単一のバーストである)で読み取られる(438)。いくつかの実施形態では、第4のテーブルを記憶するメモリはDRAMである。
【００４７】
動作436では、複数のコリジョン要素220-0から220-(q-1)(図2B)がブロックから読み取られ得る(440)。各コリジョン要素220は、それぞれのキー222と、それぞれのキー222に関連するそれぞれのパケット処理情報224とを記憶する。(たとえば、図1の比較論理機構112を使用して)コリジョン要素220-0から220-(q-1)のうちの1つのそれぞれのキー222が第2のキーと合致すると判定される。そのコリジョン要素220内のそれぞれのパケット処理情報224が、第2のパケットについてのパケット処理情報と識別される。
【００４８】
いくつかの実施形態では、動作440において複数のコリジョン要素220-0から220-(q-1)を読み取るために、第4のテーブルを記憶するメモリ(たとえば、メモリ120)内のメモリオフセットが、次の式を使用して求められる。
(h3(k2)*n+q*(第2のブロック番号))*y (2)
上式で、h3(k2)は、動作430で生成されたハッシュ値であり、nは、第4のテーブルの各スロット(たとえば、図3のハッシュテーブル302の各スロット304)内のコリジョン要素220の数であり、qは、複数のコリジョン要素220-0から220-(q-1)内のコリジョン要素220の数であり、yは、各コリジョン要素220のサイズである。次いで、複数のコリジョン要素220-0から220-(q-1)は、(たとえば、メモリ120内のハッシュテーブル302の開始に関して)メモリオフセットを有するメモリ位置から読み取られる。
【００４９】
読取り動作434および436は、たとえばテーブルアクセスモジュール110(図1)によって実施される。
【００５０】
第2のパケットが、第2のパケットについてのパケット処理情報に従って処理される(442)。いくつかの実施形態では、第2のパケットは、送信のためにパケット処理情報で指定される出力ポートに供給される。たとえば、パケット転送エンジン118が、指定されたポート102(図1)に第2のパケットをルーティングする。
【００５１】
方法400は、第2および/または第4のテーブルについてのメモリアクセスのサイズを、スロット全体ではなくスロット内のブロックに制限することによって、低待ち時間テーブルルックアップを実現する。方法400はまた、第1および/または第3のテーブルについてのメモリアクセスのサイズを、スロット全体ではなくスロット内のセルに制限し得る。第1および/または第3のテーブル内にブロック番号を記憶することは、待ち時間を増大させることなく第2および/または第4のテーブルの各スロット内のコリジョン要素の数を増加させることを可能にする。それによって、高い使用率および高い負荷因子とともに低いコリジョン率および短い待ち時間を有する大規模ルックアップテーブルが達成される。
【００５２】
方法400は、特定の順序で行われるように見えるいくつかの動作を含むが、方法400がより多数または少数の動作を含み得ること、および動作のうちのいくつかが逐次、または並列に実行され得ることは明らかなはずである。2つ以上の動作の順序が変更され得、2つ以上の動作の実施が重複し得、2つ以上の動作が単一の動作として組み合わされ得る。
【００５３】
図5Aおよび図5Bは、いくつかの実施形態による、ルックアップテーブルを維持する方法500の流れ図である。方法500は、たとえばシステム100(図1)内で実施され、方法400(図4A〜図4B)とともに実施され得る。
【００５４】
方法500では、第1の複数のスロット(たとえば、スロット212-0から212-(m-1))に分割される第1のテーブル(たとえば、スタブテーブル210、図2A)が作成され(502、図5A)、各スロットは第1の複数のセル(たとえば、セル214-0から214-(b-1))に分割される。たとえば、第1のテーブルはメモリ124(図1)内に記憶され、メモリ124は、いくつかの実施形態ではSRAMである。いくつかの実施形態では、各セルは、(たとえば、単一のそれぞれのメモリトランザクションで)メモリ124内で独立にアクセス可能である。
【００５５】
第2の複数のスロット(たとえば、スロット204-0から204-(m-1))に分割される第2のテーブル(たとえば、ハッシュテーブル202、図2A)が作成され(504)、各スロットは第1の複数のブロック(たとえば、ブロック206-0から206-(p-1))に分割される。たとえば、第2のテーブルはメモリ120(図1)内に記憶され、メモリ120は、いくつかの実施形態ではDRAMである。いくつかの実施形態では、各ブロックは複数のコリジョン要素(たとえば、コリジョン要素220-0から220-(q-1)、図2B)を含む(506)。いくつかの実施形態では、各ブロックは、メモリ120内で独立にアクセス可能である(たとえば、単一のバス要求トランザクションで。その一例はバーストである)。たとえば、各ブロックのサイズは、メモリ120についてのデータバースト当たりのバイト数と同一であり得る。
【００５６】
ハッシュ値h1(k1)およびh2(k1)が、第1のキーk1を使用して生成される(508、510)。たとえば、第1のハッシュ関数が第1のキーに適用されてハッシュ値h1(k1)が求められ、第2のハッシュ関数が第1のキーに適用されてハッシュ値h2(k1)が求められる。ハッシング動作508および510は、たとえばハッシングモジュール108(図1)によって実施される。
【００５７】
第1のキーおよび第1のキーに関連するパケット処理情報が、第2のテーブル内のそれぞれのスロット内のそれぞれのブロック内に記憶される(512)。それぞれのスロットは、ハッシュ値h1(k1)によって索引付けされる。それぞれのブロックは第1のブロック番号を有する。いくつかの実施形態では、第1のキーおよび第1のキーに関連するパケット処理情報が、それぞれのブロック内のコリジョン要素220内に記憶される(514)。
【００５８】
第1のブロック番号が、第1のテーブル内のそれぞれのスロット内のそれぞれのセル内に記憶される(516)。それぞれのスロットは、ハッシュ値h1(k1)によって索引付けされる。それぞれのセルは、ハッシュ値h2(k1)によって索引付けされる。
【００５９】
記憶動作512(たとえば、動作514を含む)および516は、いくつかの実施形態によれば、テーブル保守モジュール119(図1)によって実施される。
【００６０】
いくつかの実施形態では、第3の複数のスロット(たとえば、スロット312-0から312-(c-1))に分割される第3のテーブル(たとえば、スタブテーブル312、図3)が作成され(518、図5B)、各スロットは第2の複数のセル(たとえば、セル214-0から214-(b-1))に分割される。いくつかの実施形態では、各セルは、(たとえば、単一のそれぞれのメモリトランザクションで)メモリ124内で独立にアクセス可能である。さらに、第4の複数のスロット(たとえば、スロット304-0から304-(c-1))に分割される第4のテーブル(たとえば、ハッシュテーブル302、図3)が作成され(520)、各スロットは第2の複数のブロック(たとえば、ブロック206-0から206-(p-1))に分割される。いくつかの実施形態では、各ブロックは、メモリ120内で独立にアクセス可能である(たとえば、単一のバス要求トランザクションで。その一例はバーストである)。いくつかの実施形態では、各ブロックは複数のコリジョン要素(たとえば、コリジョン要素220-0から220-(q-1)、図2B)を含む(522)。
【００６１】
ハッシュ値h3(k2)およびh4(k2)が、第2のキーk2を使用して生成される(524、526)。たとえば、第3のハッシュ関数が第2のキーに適用されてハッシュ値h3(k2)が求められ、第4のハッシュ関数が第2のキーに適用されてハッシュ値h4(k2)が求められる。ハッシング動作524および526は、たとえばハッシングモジュール108(図1)によって実施される。
【００６２】
第2のキーおよび第2のキーに関連するパケット処理情報が、第4のテーブル内のそれぞれのスロット内のそれぞれのブロック内に記憶される(528)。それぞれのスロットは、ハッシュ値h3(k2)によって索引付けされる。それぞれのブロックは第2のブロック番号を有する。いくつかの実施形態では、第2のキーおよび第2のキーに関連するパケット処理情報が、第4のテーブル内のそれぞれのスロット内のそれぞれのブロック内のコリジョン要素220内に記憶される(530)。
【００６３】
第2のブロック番号が、第3のテーブル内のそれぞれのスロット内のそれぞれのセル内に記憶される(532)。それぞれのスロットは、ハッシュ値h3(k2)によって索引付けされる。それぞれのセルは、ハッシュ値h4(k2)によって索引付けされる。
【００６４】
記憶動作528(たとえば、動作540を含む)および532は、いくつかの実施形態によれば、テーブル保守モジュール119(図1)によって実施される。いくつかの実施形態では、記憶動作528および532は、第2のテーブル内のh1(k2)によって索引付けされたスロットが(たとえば、スロットが満杯であるので)第2のキーおよびその関連するパケット処理情報を記憶することができないと判定したことに応答して実施される。
【００６５】
方法500は、高い使用率、高い負荷因子、低いコリジョン率、および短い待ち時間を有するルックアップテーブルを実現する。方法500は、特定の順序で行われるように見えるいくつかの動作を含むが、方法500がより多数または少数の動作を含み得ること、および動作のうちのいくつかが逐次、または並列に実行され得ることは明らかなはずである。2つ以上の動作の順序が変更され得、2つ以上の動作の実施が重複し得、2つ以上の動作が単一の動作として組み合わされ得る。
【００６６】
いくつかの実施形態では、方法400および/または500はハードウェアで実施される。たとえば、方法400および/または500は、キー構築モジュール106、ハッシングモジュール108、テーブルアクセスモジュール110、パケット処理モジュール116、および/またはテーブル保守モジュール119に対応する、処理回路104内の1つまたは複数のステートマシーンを使用して実施される。あるいは、方法400および/または500はソフトウェアで実装され得る。たとえば、処理回路104はプロセッサを含み得、プロセッサによる実行のために構成された1つまたは複数のプログラムを記憶する非一時的コンピュータ可読記憶媒体として働く不揮発性メモリに結合され得る。1つまたは複数のプログラムは、プロセッサによって実行されるとき、方法400および/または500をシステム100に実施させる命令を含み得る。したがって、1つまたは複数のプログラムは、プロセッサによって実行されるとき、キー構築モジュール106、ハッシングモジュール108、テーブルアクセスモジュール110、パケット処理モジュール116、および/またはテーブル保守モジュール119の機能を達成する命令を含み得る。
【００６７】
上記の明細書では、本実施形態が、その特定の例示的実施形態を参照して説明された。しかしながら、添付の特許請求の範囲に記載の本開示のより広い精神および範囲から逸脱することなく、それに対して様々な修正および変更が行われ得ることは明らかであろう。したがって、本明細書および図面は、限定的な意味ではなく、例示的な意味で考えるべきである。
【符号の説明】
【００６８】
100  システム
102  ポート
104  処理回路
106  キー構築モジュール
108  ハッシングモジュール
110  テーブルアクセスモジュール
112  比較論理機構
114  検証論理機構
116  パケット処理モジュール
118  パケット転送エンジン
119  テーブル保守モジュール
120  メモリ
122  ハッシュテーブル
124  メモリ
126  スタブテーブル
202  ハッシュテーブル
204  スロット
206  ブロック
210  スタブテーブル
212  スロット
214  セル
220  コリジョン要素
222  キー
224  パケット処理情報
302  ハッシュテーブル
304  スロット
312  スロット
【図１】
2017519433.tif 000003
【図２Ａ】
2017519433.tif 000004
【図２Ｂ】
2017519433.tif 000005
【図３】
2017519433.tif 000006
【図４Ａ】
2017519433.tif 000007
【図４Ｂ】
2017519433.tif 000008
【図５Ａ】
2017519433.tif 000009
【図５Ｂ】
2017519433.tif 000010
【手続補正書】
【提出日】平成29年5月15日(2017.5.15)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
第1のパケットに関連する情報から構築された第1のキーを使用して、第1のハッシュ値および第2のハッシュ値を生成するステップと、
第1のテーブル内のスロット内のセルから第1のブロック番号を読み取るステップであって、前記第1のテーブル内の前記スロットが、前記第1のハッシュ値によって索引付けされ、前記セルが前記第2のハッシュ値によって索引付けされる、ステップと、
第2のテーブル内のスロット内のブロックを対象とするメモリアクセスを実施して、前記第1のパケットについてのパケット処理情報を含むデータを前記ブロックから読み取るステップであって、前記第2のテーブル内の前記スロットが、前記第1のハッシュ値によって索引付けされ、前記ブロックが前記第1のブロック番号によって索引付けされる、ステップと、
前記第1のパケットについての前記パケット処理情報に従って前記第1のパケットを処理するステップと
を含むパケット処理方法。
【請求項２】
前記第1のハッシュ値を生成する前記ステップが、前記第1のキーに第1のハッシュ関数を適用するステップを含み、
前記第2のハッシュ値を生成する前記ステップが、前記第1のキーに第2のハッシュ関数を適用するステップを含む、
請求項1に記載の方法。
【請求項３】
前記ブロックを対象とする前記メモリアクセスを実施する前記ステップが、前記第2のテーブルを記憶するメモリから、前記ブロックをバーストで読み取るステップを含む、請求項1に記載の方法。
【請求項４】
前記ブロックが複数のコリジョン要素を記憶し、
前記複数のコリジョン要素のうちの各コリジョン要素が、それぞれのキーと、前記それぞれのキーに関連するそれぞれのパケット処理情報とを記憶し、
前記ブロックを対象とする前記メモリアクセスを実施する前記ステップが、前記複数のコリジョン要素を読み取るステップを含む、
請求項1に記載の方法。
【請求項５】
前記複数のコリジョン要素のうちのコリジョン要素のそれぞれのキーが前記第1のキーに合致すると判定するステップをさらに含み、
前記第1のパケットを処理する前記ステップが、前記第1のキーに合致する前記それぞれのキーを有する前記コリジョン要素内の前記それぞれのパケット処理情報に従って前記第1のパケットを処理するステップを含む、請求項4に記載の方法。
【請求項６】
前記第1のブロック番号が前記第2のテーブルについての有効なブロック番号であると判定するステップをさらに含み、
前記ブロックを対象とする前記メモリアクセスが、前記第1のブロック番号が前記第2のテーブルについての有効なブロック番号であると判定したことに応答して実施される、請求項1に記載の方法。
【請求項７】
前記第1のパケットについての前記パケット処理情報が出力ポートを指定し、
前記第1のパケットについての前記パケット処理情報に従って前記第1のパケットを処理する前記ステップが、送信のために前記出力ポートに前記第1のパケットを供給するステップを含む、
請求項1に記載の方法。
【請求項８】
前記第2のテーブルが第2のパケットについてのパケット処理情報を記憶しないと判定するステップと、
前記第2のパケットに関連する情報から構築された第2のキーを使用して、第3のハッシュ値および第4のハッシュ値を生成するステップと、
第3のテーブル内のスロット内のセルから第2のブロック番号を読み取るステップであって、前記第3のテーブル内の前記スロットが、前記第3のハッシュ値によって索引付けされ、前記第3のテーブル内の前記スロット内の前記セルが、前記第4のハッシュ値によって索引付けされ、
第4のテーブル内のスロット内のブロックを対象とするメモリアクセスを実施して、前記第2のパケットについてのパケット処理情報を含むデータを前記ブロックから読み取るステップであって、前記第4のテーブル内の前記スロットが、前記第3のハッシュ値によって索引付けされ、前記第4のテーブル内の前記スロット内の前記ブロックが、前記第2のブロック番号によって索引付けされるステップと、
前記第2のパケットについての前記パケット処理情報に従って前記第2のパケットを処理するステップと
をさらに含む請求項1に記載の方法。
【請求項９】
パケット処理のために使用されるルックアップテーブルを維持する方法であって、
第1の複数のスロットに分割された第1のテーブルを作成するステップであって、前記第1の複数のスロットの各スロットが、第1の複数のセルに分割される、ステップと、
第2の複数のスロットに分割された第2のテーブルを作成するステップであって、前記第2の複数のスロットの各スロットが、第1の複数のブロックに分割される、ステップと、
第1のキーを使用して第1のハッシュ値および第2のハッシュ値を生成するステップと、
前記第2のテーブル内のそれぞれのスロット内のそれぞれのブロック内に、前記第1のキーおよび前記第1のキーに関連するパケット処理情報を記憶するステップであって、前記第2のテーブル内の前記それぞれのスロットが、第1のハッシュ値によって索引付けされ、前記それぞれのブロックが第1のブロック番号を有する、ステップと、
前記第1のテーブル内のそれぞれのスロット内のそれぞれのセル内に前記第1のブロック番号を記憶するステップであって、前記第1のテーブル内の前記それぞれのスロットが、前記第1のハッシュ値によって索引付けされ、前記第1のテーブル内の前記それぞれのスロット内の前記それぞれのセルが、前記第2のハッシュ値によって索引付けされる、ステップと
を含む方法。
【請求項１０】
前記第1の複数のブロックの各ブロックが、複数のコリジョン要素を含み、
前記第1のキーおよび前記第1のキーに関連する前記パケット処理情報を記憶する前記ステップが、前記第2のテーブル内の前記それぞれのスロット内の前記それぞれのブロック内のコリジョン要素内に、前記第1のキーおよび前記第1のキーに関連する前記パケット処理情報を記憶するステップを含む、
請求項9に記載の方法。
【請求項１１】
前記第1のテーブルを作成する前記ステップが、第1のメモリ内に前記第1のテーブルを記憶するステップを含み、
前記第2のテーブルを作成する前記ステップが、第2のメモリ内に前記第2のテーブルを記憶するステップを含む、
方法が、前記第1の複数のブロックのそれぞれのブロックに、前記第1の複数のブロックの他のブロックとは独立にアクセスするステップをさらに含む、
請求項9に記載の方法。
【請求項１２】
第3の複数のスロットに分割された第3のテーブルを作成するステップであって、前記第3の複数のスロットの各スロットが、第2の複数のセルに分割される、ステップと、
第4の複数のスロットに分割された第4のテーブルを作成するステップであって、前記第4の複数のスロットの各スロットが、第2の複数のブロックに分割される、ステップと、
第2のキーを使用して第3のハッシュ値および第4のハッシュ値を生成するステップと、
前記第4のテーブル内のそれぞれのスロット内のそれぞれのブロック内に、前記第2のキーおよび前記第2のキーに関連するパケット処理情報を記憶するステップであって、前記第4のテーブル内の前記それぞれのスロットが、前記第3のハッシュ値によって索引付けされ、前記それぞれのブロックが第2のブロック番号を有する、ステップと、
前記第3のテーブル内のそれぞれのスロット内のそれぞれのセル内に前記第2のブロック番号を記憶するステップであって、前記第3のテーブル内の前記それぞれのスロットが、前記第3のハッシュ値によって索引付けされ、前記第3のテーブル内の前記それぞれのスロット内の前記それぞれのセルが、前記第4のハッシュ値によって索引付けされる、ステップと
をさらに含む請求項9に記載の方法。
【請求項１３】
第1のパケットに関連する情報から構築された第1のキーを使用して、第1のハッシュ値および第2のハッシュ値を生成するためのハッシングモジュールと、
第1のテーブル内のスロット内のセルから第1のブロック番号を読み取ることであって、前記第1のテーブル内の前記スロットが、前記第1のハッシュ値によって索引付けされ、前記セルが、前記第2のハッシュ値によって索引付けされること、および
第2のテーブル内のスロット内のブロックを対象とするメモリアクセスを実施し、前記ブロックから、パケット処理情報を含むデータを読み取ることであって、前記第2のテーブル内の前記スロットが、前記第1のハッシュ値によって索引付けされ、前記ブロックが、前記第1のブロック番号によって索引付けされること
を行うためのテーブルアクセスモジュールと、
前記ブロックから読み取ったパケット処理情報に従って前記第1のパケットを処理するためのパケット処理モジュールと
を備えるパケット処理システム。
【請求項１４】
第1のパケットに関連する情報から構築された第1のキーを使用して、第1のハッシュ値および第2のハッシュ値を生成するための手段を備える、ハッシングのための手段と、
テーブルを読み取るための手段であって、
第1のテーブル内のスロット内のセルから第1のブロック番号を読み取るための手段であって、前記第1のテーブル内の前記スロットが、前記第1のハッシュ値によって索引付けされ、前記セルが、前記第2のハッシュ値によって索引付けされる、手段と、
第2のテーブル内のスロット内のブロックを対象とするメモリアクセスを実施するための手段であって、前記第2のテーブル内の前記スロットが、前記第1のハッシュ値によって索引付けされ、前記ブロックが、前記第1のブロック番号によって索引付けされる、手段と
を備える手段と、
前記ブロックから読み取ったパケット処理情報に従って前記第1のパケットを処理するための手段を備える、パケットを処理するための手段と
を備えるパケット処理システム。
【請求項１５】
請求項1乃至8および/又は9乃至12のいずれか1項に記載の方法をコンピュータに実行させるコンピュータ実行可能コードを記憶したコンピュータ可読記憶媒体。
【国際調査報告】
2017519433.tif 000011
2017519433.tif 000012