(57)【要約】  一実施形態によれば、ここに説明されるのは、高性能ネットワークにおけるネットワークデバイスにおいて分類リソースを区分するためのシステムおよび方法である。分類リソースは、頻繁に使用されるフローまたは性能に敏感なフローに関連付けられたフローエントリを格納するように構成された１つ以上のハードウェアベースのパーティションと、分類リソーススケーラビリティのために１つ以上の追加メモリに格納された大型ルックアップテーブルにアクセスするためのファームウェアベースのパーティションとを有する、複数のレベルのパーティションへと構成可能である。まず、ハードウェアベースのパーティションにおけるフローエントリ一致の検索のために、ルックアップキーが使用され得る。ミスがある場合、さらに他の検索のために、ルックアップキーはファームウェアベースのパーティションへ提示され得る。ファームウェアベースのレベルからの結果が、さらに他の処理のために、ハードウェアベースのパーサへ発送し返され得る。フローエントリは、フローエントリの利用に基づいて、パーティション管理ブロックによってルックアップテーブル間を動かされ得る。
2020502828.tif 000002
【特許請求の範囲】
【請求項１】
高性能ネットワークにおけるネットワークデバイスにおいて分類リソースパーティションを提供するためのシステムであって、
高性能ネットワークにおけるネットワークデバイスと、
前記ネットワークデバイス上の分類リソースの複数のパーティションとを含み、前記分類リソースの複数のパーティションは、１つ以上のハードウェアベースのパーティションと、ファームウェアベースのパーティションとを含み、前記システムはさらに、
前記ネットワークデバイスで受信されたデータパケットの１つ以上のヘッダフィールドから合成されたルックアップキーを含み、
前記ネットワークデバイスは、前記１つ以上のハードウェアベースのパーティションにおいて前記ルックアップキーについての一致を検索し、前記ハードウェアベースのパーティションにおいてミスがある場合には、前記ファームウェアベースのパーティションにおいて前記ルックアップキーについての一致を検索するように構成されている、システム。
【請求項２】
前記１つ以上のハードウェアベースのパーティションは、三値連想メモリ（ＴＣＡＭ）と、静的ランダムアクセスメモリ（ＳＲＡＭ）に基づくハッシュテーブルとのうちの少なくとも１つを含む、請求項１に記載のシステム。
【請求項３】
前記分類リソースの複数のパーティションの各々は１つ以上のルックアップテーブルを含み、前記１つ以上のルックアップテーブルは、それらのテーブル識別子（ＩＤ）を使用してそのパーティションへと構成されている、先行する請求項のいずれか１項に記載のシステム。
【請求項４】
前記複数のパーティションの各々におけるルックアップテーブルを管理するために、前記ファームウェアベースのパーティションによって提供される複数のテーブル管理スレッドを使用するパーティション管理ブロックをさらに含む、先行する請求項のいずれか１項に記載のシステム。
【請求項５】
前記複数のパーティションの各々はエージェントを含み、前記エージェントは、そのパーティションにおけるルックアップテーブルでの各フローエントリについてのスコアボードを含み、前記スコアボードは、各フローエントリのヒットおよびミスの数と、所与の期間における前記ヒットおよびミスの頻度とを記録する、先行する請求項のいずれか１項に記載のシステム。
【請求項６】
前記ファームウェアベースのパーティションは、１つ以上の追加メモリにアクセスするように構成された複数のハードウェアベースの処理要素（ＰＥ）を含む、先行する請求項のいずれか１項に記載のシステム。
【請求項７】
前記１つ以上の追加メモリは、前記ネットワークデバイスに取付けられた外部メモリと、ネットワークを通してアクセスされるように構成された遠隔メモリと、周辺コンポーネント相互接続エクスプレス（ＰＣＩｅ）を通してアクセスされるように構成されたシステムメモリとのうちの１つを含む、請求項６に記載のシステム。
【請求項８】
前記複数のＰＥは、処理待ち時間を減少させるために並列で作動するように構成されており、各ＰＥは、複数の処理スレッドのうちの１つに関連付けられている、請求項６に記載のシステム。
【請求項９】
前記複数の処理スレッドは、レベル１パーティションおよびレベル２パーティションにおけるルックアップテーブルでのミスに起因して検索されたフローエントリの数を追跡し、しきい値を上回る場合には、前記レベル１パーティションまたは前記レベル２パーティションにおけるルックアップテーブルへフローエントリを挿入するように、テーブル管理スレッドへ要求を発送するように構成されている、請求項８に記載のシステム。
【請求項１０】
前記ファームウェアベースのパーティションは、複数のハードウェアベースのキューを通して、前記１つ以上のハードウェアベースのパーティションとインターフェイス接続する、先行する請求項のいずれか１項に記載のシステム。
【請求項１１】
高性能ネットワークにおけるネットワークデバイスにおいて分類リソースパーティションを提供するための方法であって、
高性能ネットワークにおけるネットワークデバイス上に分類リソースの複数のパーティションを提供するステップを含み、前記分類リソースの複数のパーティションは、１つ以上のハードウェアベースのパーティションと、ファームウェアベースのパーティションとを含み、前記方法はさらに、
前記ネットワークデバイスで受信されたデータパケットの１つ以上のヘッダフィールドからルックアップキーを合成するステップと、
前記１つ以上のハードウェアベースのパーティションにおいて前記ルックアップキーについての一致を検索するステップと、
前記ハードウェアベースのパーティションにおいてミスがある場合、前記ファームウェアベースのパーティションにおいて前記ルックアップキーについての一致を検索するステップとを含む、方法。
【請求項１２】
前記１つ以上のハードウェアベースのパーティションは、三値連想メモリ（ＴＣＡＭ）と、静的ランダムアクセスメモリ（ＳＲＡＭ）に基づくハッシュテーブルとのうちの少なくとも１つを含む、請求項１１に記載の方法。
【請求項１３】
前記分類リソースの複数のパーティションの各々は１つ以上のルックアップテーブルを含み、前記１つ以上のルックアップテーブルは、それらのテーブル識別子（ＩＤ）を使用してそのパーティションへと構成されている、請求項１１または１２に記載の方法。
【請求項１４】
前記複数のパーティションの各々におけるルックアップテーブルを管理するために、前記ファームウェアベースのパーティションによって提供される複数のテーブル管理スレッドを使用するステップをさらに含む、請求項１１〜１３のいずれか１項に記載の方法。
【請求項１５】
前記複数のパーティションの各々はエージェントを含み、前記エージェントは、そのパーティションにおけるルックアップテーブルでの各フローエントリについてのスコアボードを含み、前記スコアボードは、各フローエントリのヒットおよびミスの数と、所与の期間における前記ヒットおよびミスの頻度とを記録する、請求項１１〜１４のいずれか１項に記載の方法。
【請求項１６】
前記ファームウェアベースのパーティションは、１つ以上の追加メモリにアクセスするように構成された複数のハードウェアベースの処理要素（ＰＥ）を含む、請求項１１〜１５のいずれか１項に記載の方法。
【請求項１７】
前記１つ以上の追加メモリは、前記ネットワークデバイスに取付けられた外部メモリと、ネットワークを通してアクセスされるように構成された遠隔メモリと、周辺コンポーネント相互接続エクスプレス（ＰＣＩｅ）を通してアクセスされるように構成されたシステムメモリとのうちの１つを含む、請求項１６に記載の方法。
【請求項１８】
前記複数のＰＥは、処理待ち時間を減少させるために並列で作動するように構成されており、各ＰＥは、複数の処理スレッドのうちの１つに関連付けられている、請求項１６に記載の方法。
【請求項１９】
前記複数の処理スレッドは、レベル１パーティションおよびレベル２パーティションにおけるルックアップテーブルでのミスに起因して検索されたフローエントリの数を追跡し、しきい値を上回る場合には、前記レベル１パーティションまたは前記レベル２パーティションにおけるルックアップテーブルへフローエントリを挿入するように、テーブル管理スレッドへ要求を発送するように構成されている、請求項１８に記載の方法。
【請求項２０】
高性能ネットワークにおけるネットワークデバイスにおいてプログラマブルパケット分類フレームワークを提供するための１組の命令を格納する、非一時的なコンピュータ読取可能記憶媒体であって、前記命令は、１つ以上のプロセッサによって実行されると、前記１つ以上のプロセッサに複数のステップを実行させ、前記複数のステップは、
高性能ネットワークにおけるネットワークデバイス上に分類リソースの複数のパーティションを提供するステップを含み、前記分類リソースの複数のパーティションは、１つ以上のハードウェアベースのパーティションと、ファームウェアベースのパーティションとを含み、前記複数のステップはさらに、
前記ネットワークデバイスで受信されたデータパケットの１つ以上のヘッダフィールドからルックアップキーを合成するステップと、
前記１つ以上のハードウェアベースのパーティションにおいて前記ルックアップキーについての一致を検索するステップと、
前記ハードウェアベースのパーティションにおいてミスがある場合、前記ファームウェアベースのパーティションにおいて前記ルックアップキーについての一致を検索するステップとを含む、非一時的なコンピュータ読取可能記憶媒体。
【請求項２１】
コンピュータシステムによって実行されると、前記コンピュータシステムに請求項１１〜１９のいずれか１項に記載の方法を行なわせる、マシン読取可能フォーマットのプログラム命令を含む、コンピュータプログラム。
【請求項２２】
非一時的なマシン読取可能データ記憶媒体に格納された、請求項２１に記載のコンピュータプログラムを含む、コンピュータプログラム製品。
【請求項２３】
請求項１１〜１９のいずれか１項に記載の方法を行なうための手段を含む、装置。
【発明の詳細な説明】
【技術分野】
【０００１】
著作権表示
この特許文献の開示の一部は、著作権保護の対象となる資料を含む。この特許文献または特許開示は特許商標庁の特許ファイルまたは記録に記載されているため、著作権保有者は、何人によるその複写複製に対して異議はないが、その他の場合には如何なるときもすべての著作権を保有する。
【０００２】
発明の分野：
この発明の実施形態は概して高性能ネットワークに関し、特に、高性能ネットワークにおけるネットワークデバイスにおいて分類リソースのパーティションを提供するためのシステムおよび方法に関する。
【背景技術】
【０００３】
背景：
高性能ネットワークファブリック、たとえば、インフィニバンド（InfiniBand：登録商標）およびイーサネット（登録商標）は、複数のデータセンターサーバのための高スループット接続性を提供することができる。このファブリックを通って流れるさまざまな仮想マシン（virtual machine：ＶＭ）に関連するトラフィックストリームは、短い待ち時間のフローおよび高スループットのバルク転送フローといった、アプリケーションニーズごとのさまざまなクラスのトラフィックからなり得る。
【発明の概要】
【発明が解決しようとする課題】
【０００４】
高性能ファブリックを通るトラフィックは、データセンターにおけるさまざまなＶＭへの／からの仮想化されたトラフィックストリームを含み得る。オーバーレイネットワークは、より新しいオーバーレイプロトコルの出現により、データセンターが既存のネットワークの制限を超えてスケーリングすることを可能にする。スケーリングは、追加のパケット構文解析および処理の複雑性を追加し得る。
【０００５】
たとえば、より大型のデータセンター／ネットワークによるパケット構文解析の複雑性に加えて、Ｌ２〜Ｌ４パケット構文解析および施行規則の数はかなり多い傾向があり、それは、たとえばスループット、待ち時間、および電力の点で性能目標についていくために、パケット構文解析およびパケット構文解析ハードウェアに複雑性を追加する。
【０００６】
オーバーレイネットワークプロトコルが進化し、大型データセンターにおいてデプロイメントされるにつれて、ネットワークプロトコルレベルオフロードの一部は、より高いスループットおよび短い待ち時間要件についていくために、最も低いハードウェアコンポーネントのレベル（たとえば、ネットワークインターフェイスカードまたはスイッチ、またはそれらの組合せ）で行なわれる。プロトコルレベルオフロードは、ネットワークパケットのために、粗粒子フロー〜微粒子フロー（たとえばＬ２〜Ｌ４）識別を要する。このプロセスは典型的には、パケットからフィールドを識別し、それらを、ルックアップテーブル、たとえば三値連想メモリ（ternary content-addressable memory：ＴＣＡＭ）におけるルックアップテーブルにおいてプログラムされた規則／ポリシーに対して一致させるためのパケット構文解析を伴う。多数のフローがトラフィックストリームに存在し、総スループットが高い状態では、性能目標をスケーリングし、かつ性能目標についていくことができるソリューションを有することは、有利であろう。
【課題を解決するための手段】
【０００７】
概要：
一実施形態によれば、ここに説明されるのは、高性能ネットワークにおけるネットワークデバイスにおいて分類リソースパーティションを提供するためのシステムおよび方法である。分類リソースは、頻繁に使用されるフローまたは性能に敏感なフローに関連付けられたフローエントリを格納するように構成された１つ以上のハードウェアベースのパーティションと、分類リソーススケーラビリティのために１つ以上の追加メモリに格納された大型ルックアップテーブルにアクセスするためのファームウェアベースのパーティションとを有する、複数のレベルのパーティションへと構成可能である。まず、ハードウェアベースのパーティションにおけるフローエントリ一致の検索のために、ルックアップキーが使用され得る。ミスがある場合、さらに他の検索のために、ルックアップキーはファームウェアベースのパーティションへ提示され得る。ファームウェアベースのレベルからの結果が、さらに他の処理のために、ハードウェアベースのパーサへ発送し返され得る。フローエントリは、フローエントリの利用に基づいて、パーティション管理ブロックによってルックアップテーブル間を動かされ得る。
【図面の簡単な説明】
【０００８】
【図１】一実施形態に従った、高性能ネットワークにおけるネットワークデバイスにおいて分類リソースパーティションを提供するためのシステムを示す図である。
【図２】一実施形態に従った、高性能ネットワークにおけるネットワークデバイスにおいて分類リソースパーティションを提供するためのシステムをさらに示す図である。
【図３】一実施形態に従った、高性能ネットワークにおけるネットワークデバイスにおいて分類リソースパーティションを提供するための方法を示す図である。
【図４】一実施形態に従った、例示的な高性能ネットワークを示す図である。
【発明を実施するための形態】
【０００９】
詳細な説明：
高性能ネットワークでは、パケット分類とは、同じフローに属するすべてのデータパケットが予め規定されたルールに従い、同じ態様で処理されるように、データパケットを「フロー」へと類別するプロセスを指す。パケット分類は、ファイアウォールおよびサービス品質といった非ベストエフォート型サービスにとって必要とされ得る。
【００１０】
たとえば、同じ送信元および宛先ＩＰアドレスを有するすべてのパケットは、フローを形成すると識別され得る。
【００１１】
一実施形態によれば、ネットワークデバイスは、データパケット処理のために分類プリミティブに依拠し得る。例示的な分類プリミティブは、パケットパーサと、二値連想メモリ（binary content addressable memory：ＢＣＡＭ）、三値連想メモリ（ＴＣＡＭ）、およびランダムアクセスメモリ（random-access memory：ＲＡＭ）に格納された分類／ルックアップテーブルとを含み得る。各ルックアップテーブルは、複数のフローエントリを含み得る。
【００１２】
一実施形態によれば、各フローエントリは、データパケットに対して一致させるべき複数の一致フィールドを含み得る。一致フィールドは、入口ポート、パケットヘッダ、およびオプションで、前のテーブルによって特定されたメタデータといった他のパイプラインフィールドを含み得る。フローエントリはまた、フローエントリの一致する優先順位を示す優先順位フィールド、パケットが一致すると更新可能なカウンタフィールド、アクションセットまたはパイプライン処理を修正するための命令を含み得る。フローエントリはまた、データパケットをフィルタリングするために使用されるフロー規則およびポリシーを含み得る。
【００１３】
一実施形態によれば、フローエントリは、システムアドミニストレータによって自動的に入力または作成され得る。そのため、ルックアップテーブルにおけるフォーマットまたはフィールドは、アプリケーションのニーズに基づいて異なっていてもよい。たとえば、フローエントリは、データパケットの１つ以上のヘッダから選択されたバイトにおける値と、キーマスクとを含み得る。
【００１４】
典型的なパケット処理アプリケーションは、ネットワークパケットからさまざまなフィールドを識別し、キーを合成し、１つ以上のルックアップテーブルに対してルックアップ／検索を行なうためのパケット構文解析を伴う。キーを合成するために選択されるフィールドに依存して、ルックアップ／検索に使用されるテーブルのタイプは異なっていてもよい。同様に、ルックアップテーブルにとって必要とされるサイズは、アプリケーションに依存して変化してもよい。たとえば、あるアプリケーションは非常に大型のＬ２ルックアップテーブルと浅いＬ３ルックアップテーブルとを必要とするかもしれず、別のアプリケーションは、双方のルックアップテーブルについて同様のサイズを必要とするかもしれない。
【００１５】
ますます多くのオーバーレイプロトコルおよびますます多くのフローをサポートするために高性能ネットワークが必要とされるにつれて、ルックアップテーブルのサイズは、フローエントリの増加とともに増加し得る。ルックアップテーブルなどの分類リソースは実装コストおよびルックアップ速度の点で異なるため、性能目標をスケーリングし、かつ性能目標についていくことができるソリューションを有することは、有利であろう。
【００１６】
一実施形態によれば、ここに説明されるのは、高性能ネットワークにおけるネットワークデバイスにおいて分類リソースパーティションを提供するためのシステムおよび方法である。分類リソースは、頻繁に使用されるフローまたは性能に敏感なフローに関連付けられたフローエントリを格納するように構成された１つ以上のハードウェアベースのパーティションと、分類リソーススケーラビリティのために１つ以上の追加メモリに格納された大型ルックアップテーブルにアクセスするためのファームウェアベースのパーティションとを有する、複数のレベルのパーティションへと構成可能である。まず、ハードウェアベースのパーティションにおけるフローエントリ一致の検索のために、ルックアップキーが使用され得る。ミスがある場合、さらに他の検索のために、ルックアップキーはファームウェアベースのパーティションへ提示され得る。ファームウェアベースのレベルからの結果が、さらに他の処理のために、ハードウェアベースのパーサへ発送し返され得る。フローエントリは、フローエントリの利用に基づいて、パーティション管理ブロックによってルックアップテーブル間を動かされ得る。
【００１７】
一実施形態によれば、分類リソースのハードウェアベースのパーティションは、レベル１パーティションにおける１つ以上のＴＣＡＭと、レベル２パーティションにおける１つ以上のハッシュテーブルとを含み得る。ファームウェアベースのパーティションは、分類リソースのレベル３パーティションを表わすことができ、複数のネットワーク処理要素（processing element：ＰＥ）を含む埋込み型プロセッササブシステムを含み得る。各ＰＥは、完全なマイクロプロセッサ、またはマイクロコントローラ、またはステートマシンベースのハードウェアエンジンに基づき得る。
【００１８】
一実施形態によれば、パーティション管理ブロックは、所与の性能目標が満たされ得るように、分類リソースの各パーティションにおけるルックアップテーブルおよびフローエントリを効率的に管理するための、ハードウェアベースのアクションとファームウェアベースのアクションとの混合であり得る。システムは、ルックアップテーブルに関連する管理アクションを容易にするように複数の機能をサポートすることができる。
【００１９】
フレームワークは、ＴＣＡＭと、ハッシュテーブルと、外部メモリまたは遠隔メモリに接続されたファームウェアベースのサブシステムとの階層構造として区分された大量の分類リソースを、各レベルでキャッシングして管理し、スケーリングするために使用され得る。階層構造における各レベルはフローエントリを格納でき、スループット、待ち時間、および消費電力の点で異なり得る。ここに説明されるフレームワークは、インフィニバンドまたはイーサネットなどの基盤ネットワーキング技術のタイプから独立しており、複数のネットワーク技術に一律に適用され得る。
【００２０】
分類リソースパーティション
図１は、一実施形態に従った、高性能ネットワークにおけるネットワークデバイスにおいて分類リソースパーティションを提供するためのシステムを示す。
【００２１】
図１に示すように、高性能ネットワーク、たとえばインフィニバンドにおけるネットワークデバイス１０１は、複数の分類リソース、たとえば、ＢＣＡＭ、ＴＣＡＭ、およびＲＡＭに格納されたルックアップテーブルを含み得る。
【００２２】
一実施形態によれば、ルックアップテーブルは、ランタイム中に任意のタイプのものであるように構成された汎用ライブラリ要素として編成され得る。各ルックアップテーブルは、ルックアップのために使用される一意ＩＤで構成され得る。ルックアップキー生成および合成の一環として、一意テーブルｉｄが生成され得る。ルックアップキーのＩＤとルックアップテーブルのＩＤとは、ルックアップテーブルからのルックアップ結果が有効になるために互いに一致する必要がある。ルックアップテーブルＩＤおよびルックアップキーＩＤはそれにより、分類フレームワークが、ルックアップテーブルを並べ換えてそれらをサイズ変更することを通して、分類リソースを区分することを可能にすることができる。
【００２３】
たとえば、ある特定の範囲内のＩＤを有する複数のルックアップテーブルを、構成により、あるパーティションに配置することができる。同じ範囲内のＩＤを有するルックアップキーを構成することにより、フローエントリ一致の検索をそのパーティションに向けることができる。
【００２４】
図１に示すように、システムにおける分類リソース、たとえばルックアップテーブルは、３つのパーティションへと構成され得る。
【００２５】
一実施形態によれば、分類リソースのレベル１パーティション１１１は、ルックアップテーブルを内部に格納する１つ以上のプログラマブルＴＣＡＭ（たとえばＴＣＡＭ１１３）を含み得る。ＴＣＡＭは、頻繁に使用されるフローまたは性能に敏感なフローに関連付けられたフローエントリを格納するためのレベル１（Ｌ１）キャッシュとして機能し得る。
【００２６】
一実施形態によれば、分類リソースのレベル２パーティション１１９は、１つ以上のプログラマブルハッシュテーブル（たとえばハッシュテーブル１２２）を含み得る。各ハッシュテーブルは、フローエントリを格納するハッシュテーブルバケットを含んでいてもよく、静的ランダムアクセスメモリ（ＳＲＡＭ）１２１に基づいていてもよい。
【００２７】
ハッシュテーブル上での一致はエイリアシングをもたらし得るため、衝突／エイリアスを解決するには複数のルックアップがハッシュテーブル内で必要かもしれない。より多くのフローエントリをサポートするために、各ハッシュテーブルのサイズは構成可能であってもよく、ＴＣＡＭのサイズと比べて著しく大きくてもよい。ハッシュテーブルの一部として作成または詳説され得るリンクされたリストチェーンは、定数に制限されてもよく、ある特定のスループット要件ごとに構成可能であってもよい。
【００２８】
一実施形態によれば、分類リソースのレベル３パーティション１２５は、１つ以上の追加メモリ１２７に格納されたルックアップテーブルにアクセスするように構成された、ファームウェアベースの埋込み型プロセッササブシステム１２９を含み得る。追加メモリは、ネットワークデバイスに取付けられた外部メモリ、たとえば、デュアルインラインメモリモジュール（dual in-line memory module：ＤＩＭＭ）に基づいたダブルデータレート（double data rate：ＤＤＲ）メモリと、ネットワークを通してアクセスされ得る遠隔メモリと、高速シリアルコンピュータ拡張バスコンポーネントである周辺コンポーネント相互接続エクスプレス（peripheral component interconnect express：ＰＣＩｅ）を通してアクセスされ得るシステムメモリとを含み得る。
【００２９】
各パーティションにおける各分類リソースを実現するために使用される上述の媒体は、例示的な一例として提供されている。当業者であれば、システムにおいて分類リソースパーティションを実現するために他の媒体が同様に使用され得ることを理解するであろう。
【００３０】
一実施形態によれば、レベル１パーティションにおける分類リソースは、フローエントリ、規則、およびポリシーを格納する点で小型であり、価格および消費電力の点でより高価であるものの、性能の点でより高速であり得る。レベル２パーティションにおける分類リソースは、より大型で、それほど高価ではないものの、性能の点でより遅くなり得る。レベル３パーティションにおける分類リソースは、待ち時間が長いが、追加メモリ、たとえば、取付けられたメモリおよびネットワークメモリにアクセスすることを通して、必要なだけ多くの規則、ポリシー、およびフローエントリを格納するために使用され得る。
【００３１】
一実施形態によれば、各パーティションのサイズは、アプリケーションニーズ、必要な性能目標、ならびに、エリア（たとえば、オフロードエンジンが存在するところ）および／または消費電力の点で関連付けられたハードウェア複雑性を含む、複数の要因間のトレードオフとして定められ得る。
【００３２】
一実施形態によれば、分類リソースのレベル２パーティションと分類リソースのレベル３パーティションとは、分類リソースの第１のレベルへの拡張と考えられ得る。ネットワークデバイス１０１を通るデータパケットはまず、分類リソースの第１のレベルへ向けられ得る。そして、レベル１パーティションにおいて、たとえば、ＴＣＡＭにおけるルックアップテーブルにおいてヒットが見つからない場合のみ、データパケットは第２のレベルへ向けられる。レベル２パーティションにおいてヒットが見つからない場合、パケットはレベル３パーティションへ向けられる。
【００３３】
この開示では、一実施形態によれば、あるデータパケットが分類リソースのあるパーティションにおけるルックアップテーブルへ向けられると、そのデータパケットの１つ以上のヘッダフィールドから合成されたルックアップキーが、フローエントリ一致のためにルックアップテーブルへ提示される。
【００３４】
例示的な一例として、図１に示すように、データパケット１０５がパケットパーサ１０９で受信されると、パケットパーサは、データパケットにおける１つ以上のヘッダフィールドを表わす１つ以上のバイトを探し出して抽出し、ルックアップキーを構築することができる。ルックアップキーはまず、特定されたポリシーおよび規則に基づくフローエントリに対する一致のために、ＴＣＡＭ１１３へ向けられ得る。ミスがある場合、ルックアップキーはハッシュテーブル１２２へ向けられ（１３５）、ハッシュテーブルにおいてミスがある場合、ルックアップキーはファームウェアベースの埋込み型プロセッササブシステム１２９へ向けられる（１３７）。
【００３５】
一実施形態によれば、ファームウェアベースの埋込み型プロセッササブシステムは、規則がオーバーフローする場合、もしくは、レベル１パーティションおよびレベル２パーティションにおいて新しい規則または新しいフローエントリに遭遇する場合にも使用され得る。
【００３６】
一実施形態によれば、ファームウェアベースの埋込み型プロセッササブシステムを通る処理の待ち時間は長い場合があり、また、ルックアップキーの状態および検索中のポリシーに依存して変化し得る。全体的な待ち時間を緩和し、全体的なスループット要件についていくために、複数の処理要素（ＰＥ）が、並列で作動するように、ファームウェアベースの埋込み型プロセッササブシステムにおいて提供され得る。各ＰＥは、完全なマイクロプロセッサ、またはマイクロコントローラ、またはステートマシンベースのハードウェアエンジンに基づき得る。
【００３７】
一実施形態によれば、複数のＰＥ中に作業負荷を広げるために、ならびに、フロー類似性およびパケット順序付けを維持するために、ハッシュ関数１３２が、複数の負荷分散キュー１３１とともに使用され得る。ＰＥからの結果が、さらに他の処理のために、複数の結果発送キュー１３３を通してハードウェアベースのパケットパーサ１０９へ発送し返され得る（１４１）。
【００３８】
一実施形態によれば、負荷分散キューおよび結果発送キューは双方とも、ハードウェアベースであってもよく、たとえば、直接メモリアクセス（direct memory access：ＤＭＡ）エンジンに基づいていてもよい。
【００３９】
分類リソース管理
図１にさらに示すように、所与の性能目標を満たすように各パーティションにおけるルックアップテーブルを管理するために、パーティション管理ブロック１１７がネットワークデバイスにおいて提供され得る。ルックアップテーブルを管理する際にパーティション管理ブロックによって使用されるために、複数のテーブル管理スレッドがファームウェアベースの埋込み型プロセッササブシステムによって提供され得る。パーティション管理ブロックは、ハードウェアおよびファームウェアベースのアクションの混合を含み得る。
【００４０】
一実施形態によれば、パーティション管理ブロックは、３つのレベルのパーティションの各々におけるエージェント、たとえば、レベル１パーティションにおけるエージェント１１５、レベル２パーティションにおけるエージェント１２３、およびレベル３パーティションにおけるエージェント１３０と通信することができる。
【００４１】
一実施形態によれば、パーティション管理ブロックは、ヒットおよびミスに関する情報をエージェント１１５および１２３から収集し、その情報を使用して、さらに他の検索のためにルックアップキーを次のレベルのパーティションへ向ける必要があるかどうかを判断することができる。
【００４２】
一実施形態によれば、テーブル管理に関連するアクションを容易にするために、エージェント１１５、１２３、および１３１の各々は、それらのそれぞれのパーティションにおけるルックアップテーブルでの各フローエントリについてのスコアボードを含み得る。スコアボードは、フローエントリのヒットおよびミスの数と、所与の期間におけるヒットおよびミスの頻度と、フローエントリがシステムによってアクセスされた回数とを追跡することができる。スコアカード値は、一致がなければ周期的にディクリメントされ得る。
【００４３】
一実施形態によれば、レベル１パーティションまたはレベル２パーティションにおけるスコアカード値が所与のしきい値を下回る場合、関連付けられたフローエントリは無効としてマークされ得る。それは、ＴＣＡＭおよびハッシュテーブル双方からのフローエントリの完全な取出し、または、ＴＣＡＭからのフローエントリの取出しおよびハッシュテーブルへのフローエントリの挿入、または、ハッシュテーブルからのフローエントリの取出しおよびＴＣＡＭへのフローエントリの挿入をもたらし得る。フローエントリの無効化は、ルックアップテーブルにおけるミスをもたらし得る。フローエントリの取出しは、全体的なシステム構成を貫くポリシーによって駆動され得る。
【００４４】
一実施形態によれば、ハードウェアベースのパーティション（すなわち、レベル１パーティションおよびレベル２パーティション）におけるエージェントの各々は、ＴＣＡＭ（Ｌ１キャッシュ）またはハッシュテーブル（Ｌ２キャッシュ）を管理するために、たとえば、ルックアップテーブルからどのフローエントリを取出すべきかを判断するために、キャッシュ置換えアルゴリズムまたはポリシー、たとえば、最長時間未使用（least recently used：ＬＲＵ）または最低使用頻度（least frequently used：ＬＦＵ）を使用することができる。
【００４５】
一実施形態によれば、レベル３パーティションにおけるエージェント１３０は、短い待ち時間のフローのためにキャッシュを更新するために、パーティション管理ブロックとともに作動することができる。
【００４６】
たとえば、所与のフローエントリの検索がＴＣＡＭおよびハッシュテーブル双方においてミスをもたらし、その検索が結局、レベル３パーティションにおけるＰＥによって扱われることになった場合、ファームウェアエージェント１３０は、レベル３パーティションにローカルに格納されたポリシーに基づいて、所与の特定のフローエントリ１３９をレベル１パーティションまたはレベル２パーティションのルックアップテーブルへと追加することができる。
【００４７】
分類リソーススケーラビリティ
一実施形態によれば、分類リソースは、汎用ライブラリ要素を通して構成可能であり、キャッシュの階層構造として論理的に配置可能である。ルックアップキーは、データパケットのヘッダから、パケット構文解析エンジンまたはパケットパーサを通して生成され得る。各ルックアップキーは、テーブルＩＤとともに合成され得る。ルックアップキーは、テーブルＩＤとともにルックアップテーブルへ提示可能であり、ルックアップテーブルからの結果が、さらに他の処理のために、パケット処理エンジンまたはパケットパーサへ発送し返され得る。
【００４８】
一実施形態によれば、上述の分類リソース区分化フレームワークは、多数のフローエントリ、規則、およびポリシーをサポートすることができるように、区分された分類リソースをスケールアップするために使用され得る。
【００４９】
図２は、一実施形態に従った、高性能ネットワークにおけるネットワークデバイスにおいて分類リソースパーティションを提供するためのシステムをさらに示す。
【００５０】
より特定的には、図２は、一実施形態に従ったシステムにおいて分類リソースをスケールアップすることを示す。
【００５１】
一実施形態によれば、上述のように、ファームウェアベースの埋込み型プロセッササブシステムは、コヒーレンスメモリ階層構造２３９を介して１つ以上の追加メモリ１２７にアクセスするように構成された、複数のネットワーク処理要素（ＰＥ）を含み得る。追加メモリの例は、ネットワークデバイスに取付けられた外部メモリ２２８と、ネットワークを通してアクセスされ得る遠隔メモリ２２９と、周辺コンポーネント相互接続エクスプレス（ＰＣＩｅ）を通してアクセスされ得るシステムメモリ２２７とを含む。
【００５２】
一実施形態によれば、複数のＰＥは、ハードウェアキャッシュ、たとえば、レベル１パーティションおよびレベル２パーティションにおけるルックアップテーブルに存在しないかもしれないフローエントリについての、１つ以上の追加メモリ１２５におけるルックアップテーブルでの検索を管理するために、並列で作動することができる。実際の検索は、ファームウェアベースの埋込み型プロセッササブシステムにおける１つ以上のハードウェア支援エンジンによって実行可能であり、ＰＥは、１つ以上の追加メモリへの効率的なアクセスを提供するように構成される。
【００５３】
図２に示すように、複数の処理スレッド、たとえば、スレッドＡ２４５〜スレッドＮ２４９が、１つ以上の追加メモリにおけるフローエントリ検索のために使用され得る。各スレッドは、ファームウェアスレッドであってもよい。
【００５４】
フローエントリ検索は可変量の待ち時間を取り得るため、ＰＥの現在の負荷およびフロー類似性に基づいて、処理スレッドを複数のＰＥに割り当てることができる。
【００５５】
一実施形態によれば、１つ以上のハードウェア支援エンジン、たとえば、ハードウェア支援エンジン２４１が、検索タスクを各ＰＥへ発送するために使用され得る。１つ以上のパケットヘッダ、または、１つ以上のパケットヘッダから選択されたバイトに基づいて、ハッシュ２４３が、ハードウェア支援エンジンによって計算され得る。ハッシュに基づいて、特定の処理スレッドが各ＰＥへ割り当てられ得る。
【００５６】
一実施形態によれば、各々が処理スレッドに特有である、複数のＤＭＡエンジンベースの負荷分散キュー１３１が、ハードウェアベースのブロック（レベル１パーティションおよびレベル２パーティションを含み得る）と、ファームウェアベースのパーティションにおけるＰＥのインターフェイスとの間に提供され得る。各負荷分散キューをエンキューすることは、ハードウェアベースのブロックによって制御可能であり、各負荷分散キューをデキューすることは、ファームウェアベースの埋込み型プロセッササブシステムによって制御可能である。
【００５７】
一実施形態によれば、ルックアップキーを構成するヘッダから選択された、必要とされるパケットヘッダまたはバイトが、あるＰＥによってデキューされると、そのＰＥはサーチプロセスを始めることができ、それは、ハッシュテーブル検索または別のサーチアルゴリズムを行なうことができる。サーチプロセスからの結果が利用可能になると、結果は、結果２５３がさらに他の処理のためにパケットパーサへ送り返されるように、複数の結果発送キューへと発送し返され得る。結果発送キューは、ハードウェアキュー、たとえば、ＤＭＡエンジンに基づいたキューであり得る。
【００５８】
一実施形態によれば、負荷分散キューおよび結果発送キューの使用は、パケット順序付けおよびフロー類似性の維持を提供することができる。たとえば、負荷分散キューは、ルックアップキーまたはデータパケットが順番に処理され得るように、ルックアップキーまたはデータパケットをキューに入れることができる。結果発送キューは、結果がパケットプロセッサによって順番に処理され得るように、処理結果を送り返すために使用され得る。
【００５９】
一実施形態によれば、並列で作動するように複数のＰＥを使用することに加えて、レベル３パーティションはまた、各処理スレッドの処理待ち時間を減少させるために、複数のさまざまなハードウェア支援エンジンを使用することができる。
【００６０】
たとえば、ハードウェア支援エンジン２４１はハッシュを計算するために使用され、１つ以上のハードウェア支援エンジンが、フローエントリ一致の検索を行なうために使用され、１つ以上のＤＭＡエンジンが、結果発送キューおよび負荷分散キューを実現および／または管理するために使用される。
【００６１】
図２に示すように、負荷分散キューの各々、および結果発送キューの各々は、複数の処理スレッド２４５〜２４９のうちの１つに関連付けられ得る。追加のスレッドが、システムにおいてルックアップテーブルを管理し更新する際に使用するために、ファームウェアベースの埋込み型プロセッササブシステムにおいて利用可能であってもよい。
【００６２】
ルックアップテーブルの更新
一実施形態によれば、ファームウェアベースの埋込み型プロセッササブシステムは、レベル３パーティションにおけるルックアップテーブルを管理することができ、レベル１パーティションおよびレベル２パーティションにおける短い待ち時間のフローエントリを格納するルックアップテーブルを更新するためにパーティション管理ブロック１１７とともに作動することができる。
【００６３】
一実施形態によれば、システムにおけるルックアップテーブルは、１つ以上のテーブル管理スレッドによって管理され得る。各フローエントリは、ヒット／ミスの数と所与の期間におけるヒットおよびミスの頻度とを追跡するスコアカードに関連付けられ得る。パーティション管理ブロックによって維持されるしきい値は、テーブル管理スレッドがしきい値のうちの１つに基づいてルックアップテーブルからフローエントリを取出すことができるように、１つ以上の管理スレッドへの割込みを生成するためのトリガとして使用され得る。
【００６４】
同様に、一実施形態によれば、処理スレッドは、レベル１パーティションおよびレベル２パーティションにおけるルックアップテーブルでのミスに起因して頻繁に検索されたフローエントリの数を追跡することができる。しきい値が構成可能なしきい値を上回ると、処理スレッドは、管理スレッドが頻繁に使用されたフローエントリをレベル１パーティションまたはレベル２パーティションにおけるルックアップテーブルへ挿入し返すことができるように、テーブル管理スレッドへ要求を発送することができる。フローエントリの挿入は、更新の頻度などのポリシーおよびキャッシュ立ち退きポリシーに基づいて駆動され得る。
【００６５】
図３は、一実施形態に従った、高性能ネットワークにおけるネットワークデバイスにおいて分類リソースパーティションを提供するための方法を示す。
【００６６】
図３に示すように、ステップ３１１で、高性能ネットワークにおけるネットワークデバイス上に分類リソースの複数のパーティションが提供され、分類リソースの複数のパーティションは、１つ以上のハードウェアベースのパーティションと、ファームウェアベースのパーティションとを含む。
【００６７】
ステップ３１３で、ネットワークデバイスで受信されたデータパケットの１つ以上のヘッダフィールドから、ルックアップキーが合成される。
【００６８】
ステップ３１５で、１つ以上のハードウェアベースのパーティションにおいて、ルックアップキーについての一致について、１つ以上の検索が行なわれる。
【００６９】
ステップ３１７で、ハードウェアベースのパーティションにおいてミスがある場合、ファームウェアベースのパーティションにおいて、ルックアップキーについての一致について、検索が行なわれる。
【００７０】
インフィニバンド（登録商標）
インフィニバンド（登録商標）（ＩＢ）は、上述のシステムおよび方法が使用され得る例示的な高性能ネットワークである。
【００７１】
インフィニバンド（登録商標）は、インフィニバンド・トレード・アソシエーション（InfiniBandTMTrade Association）によって開発されたオープン標準無損失ネットワーク技術である。この技術は、特に高性能コンピューティング（high-performance computing：ＨＰＣ）アプリケーションおよびデータセンタを対象とする、高スループットおよび短い待ち時間の通信を提供するシリアルポイントツーポイント全二重相互接続（serial point-to-point full-duplex interconnect）に基づいている。
【００７２】
インフィニバンド・アーキテクチャ（InfiniBandTM Architecture：ＩＢＡ）は、２層トポロジー分割をサポートする。より低い層では、ＩＢネットワークはサブネットと称され、１つのサブネットは、スイッチおよびポイントツーポイントリンクを使用して相互接続される一組のホストを含み得る。より高いレベルでは、１つのＩＢファブリックは、ルータを使用して相互接続され得る１つ以上のサブネットを構成する。
【００７３】
１つのサブネット内で、ホストは、スイッチおよびポイントツーポイントリンクを使用して接続され得る。加えて、サブネットにおける指定されたデバイス上に存在する、１つのマスター管理エンティティ、すなわちサブネットマネージャ（subnet manager：ＳＭ）があり得る。サブネットマネージャは、ＩＢサブネットを構成し、起動し、維持する役割を果たす。加えて、サブネットマネージャ（ＳＭ）は、ＩＢファブリックにおいてルーティングテーブル計算を行なう役割を果たし得る。ここで、たとえば、ＩＢネットワークのルーティングは、ローカルサブネットにおけるすべての送信元と宛先とのペア間の適正な負荷分散を目標とする。
【００７４】
サブネット管理インターフェイスを通して、サブネットマネージャは、サブネット管理パケット（subnet management packet：ＳＭＰ）と称される制御パケットを、サブネット管理エージェント（subnet management agent：ＳＭＡ）と交換する。サブネット管理エージェントは、すべてのＩＢサブネットデバイス上に存在する。ＳＭＰを使用することにより、サブネットマネージャは、ファブリックを発見し、エンドノードおよびスイッチを構成し、ＳＭＡから通知を受信することができる。
【００７５】
一実施形態によれば、ＩＢネットワークにおけるサブネット内ルーティングは、スイッチに格納されたＬＦＴに基づき得る。ＬＦＴは、使用中のルーティングメカニズムに従って、ＳＭによって計算される。サブネットでは、エンドノードおよびスイッチ上のホストチャネルアダプタ（Host Channel Adapter：ＨＣＡ）ポートが、ローカル識別子（local identifier：ＬＩＤ）を使用してアドレス指定される。ＬＦＴにおける各エントリは、宛先ＬＩＤ（destination LID：ＤＬＩＤ）と出力ポートとからなる。テーブルにおけるＬＩＤごとに１つのエントリのみがサポートされる。パケットがあるスイッチに到着すると、その出力ポートは、そのスイッチのフォワーディングテーブルにおいてＤＬＩＤを探すことによって判断される。パケットはネットワークにおいて所与の送信元−宛先ペア（ＬＩＤペア）間で同じ経路を通るため、ルーティングは決定論的である。
【００７６】
一般に、マスターサブネットマネージャを除く他のすべてのサブネットマネージャは、耐故障性のために待機モードで作動する。しかしながら、マスターサブネットマネージャが故障した状況では、待機中のサブネットマネージャによって、新しいマスターサブネットマネージャが取り決められる。マスターサブネットマネージャはまた、サブネットの周期的なスイープ（sweep）を行なってあらゆるトポロジー変化を検出し、それに応じてネットワークを再構成する。
【００７７】
さらに、サブネット内のホストおよびスイッチは、ローカル識別子（ＬＩＤ）を使用してアドレス指定可能であり、単一のサブネットは、４９１５１個のユニキャストＬＩＤに制限可能である。サブネット内で有効なローカルアドレスであるＬＩＤの他に、各ＩＢデバイスは、６４ビットのグローバル一意識別子（global unique identifier：ＧＵＩＤ）を有し得る。ＧＵＩＤは、ＩＢレイヤー３（Ｌ３）アドレスであるグローバル識別子（global identifier：ＧＩＤ）を形成するために使用され得る。
【００７８】
ＳＭは、ネットワーク初期化時間に、ルーティングテーブル（すなわち、サブネット内のノードの各ペア間の接続／ルート）を計算し得る。さらに、トポロジーが変化するたびに、ルーティングテーブルは、接続性および最適性能を確実にするために更新され得る。通常動作中、ＳＭは、トポロジー変化をチェックするためにネットワークの周期的なライトスイープ（light sweep）を実行し得る。ライトスイープ中に変化が発見された場合、または、ネットワーク変化を信号で伝えるメッセージ（トラップ）をＳＭが受信した場合、ＳＭは、発見された変化に従ってネットワークを再構成し得る。
【００７９】
たとえば、ＳＭは、リンクがダウンした場合、デバイスが追加された場合、またはリンクが除去された場合など、ネットワークトポロジーが変化する場合に、ネットワークを再構成し得る。再構成ステップは、ネットワーク初期化中に行なわれるステップを含み得る。さらに、再構成は、ネットワーク変化が生じたサブネットに制限されるローカルスコープを有し得る。また、ルータを用いる大型ファブリックのセグメント化は、再構成の範囲を制限し得る。
【００８０】
一実施形態に従ったインフィニバンド環境の例示を示す図４に、例示的なインフィニバンドファブリックを示す。図４に示す例では、ノードＡ４０１〜Ｅ４０５は、インフィニバンドファブリック４２０を使用して、それぞれのホストチャネルアダプタ４１１〜４１５を介して通信する。一実施形態によれば、さまざまなノード、たとえばノードＡ４０１〜Ｅ４０５は、さまざまな物理デバイスによって表わされ得る。一実施形態によれば、さまざまなノード、たとえばノードＡ４０１〜Ｅ４０５は、仮想マシンなどのさまざまな仮想デバイスによって表わされ得る。
【００８１】
本発明は、本開示の教示に従ってプログラムされる１つ以上のプロセッサ、メモリ、および／またはコンピュータ読取可能記憶媒体を含む、１つ以上の従来の汎用または専用デジタルコンピュータ、コンピューティングデバイス、マシン、またはマイクロプロセッサを使用して、便利に実現され得る。ソフトウェア技術に精通した当業者には明らかであるように、適切なソフトウェアコーディングが、本開示の教示に基づいて、熟練したプログラマによって容易に準備され得る。
【００８２】
いくつかの実施形態では、本発明は、本発明のプロセスのいずれかを実行するようにコンピュータをプログラムするために使用され得る命令が格納されている非一時的な記憶媒体またはコンピュータ読取可能媒体であるコンピュータプログラム製品を含む。記憶媒体は、フロッピー（登録商標）ディスク、光ディスク、ＤＶＤ、ＣＤ−ＲＯＭ、マイクロドライブ、および磁気光ディスク、ＲＯＭ、ＲＡＭ、ＥＰＲＯＭ、ＥＥＰＲＯＭ、ＤＲＡＭ、ＶＲＡＭ、フラッシュメモリデバイス、磁気もしくは光カード、（分子メモリＩＣを含む）ナノシステムを含む任意のタイプのディスク、もしくは、命令および／またはデータを格納するのに適した任意のタイプの媒体もしくはデバイスを含み得るものの、これらに限定されない。
【００８３】
この発明の実施形態の前述の説明は、例示および説明のために提供されてきた。それは、網羅的であるよう、またはこの発明を開示された形態そのものに限定するよう意図されてはいない。当業者には、多くの修正および変形が明らかであろう。修正および変形は、開示された特徴のあらゆる関連する組合せを含む。実施形態は、この発明の原理およびその実際的な適用を最良に説明するために選択および説明されたものであり、それにより、他の当業者が、特定の使用に適したさまざまな修正を考慮して、さまざまな実施形態についてこの発明を理解することを可能にする。
【図１】
2020502828.tif 000003
【図２】
2020502828.tif 000004
【図３】
2020502828.tif 000005
【図４】
2020502828.tif 000006
【国際調査報告】
2020502828.tif 000007
2020502828.tif 000008
2020502828.tif 000009