JP6064291B2 - ネットワークデバイスのフロールックアップ管理のための技術 - Google Patents

Description

現代のコンピューティングデバイスは、パーソナル、ビジネス及びソーシャル利用のためのユビキタスツールとなっている。そのようなものとして、多くの現代のコンピューティングデバイスは、インターネット及び企業のイントラネットを含む、様々なデータネットワークに接続して、そのようなネットワークを介してデータ通信を取得し、及び、送信／受信することが可能である。複数のコンピューティングデバイス間の通信を容易にするために、ネットワークは、一般的に、一方のコンピューティングデバイスから他方へ通信をルーティングするべく、１又は複数のネットワークデバイス（例えば、ネットワークスイッチ、ネットワークルータ等）を含む。

ＳＤＮ（Ｓｏｆｔｗａｒｅ‐ｄｅｆｉｎｅｄ ｎｅｔｗｏｒｋｉｎｇ）は、ネットワーク上の通信を容易にするために用いられるネットワーキングアーキテクチャ（すなわち、ネットワークパケットのフロー）のようなものである。ソフトウェアディファインドネットワーク（ｓｏｆｔｗａｒｅ−ｄｅｆｉｎｅｄ ｎｅｔｗｏｒｋ）において、外部に位置付けられるＳＤＮコントローラは、ネットワークスイッチング／ルーティングデバイスに接続され、ネットワークのネットワークパケットのためのネットワークトラフィックフローロジックの決定を行い、タスクは、ネットワークデバイスレベルで伝統的に実行されていた。そのようなものとして、ネットワークデバイスの専用ネットワークプロセッサで事前に実行されるネットワークパケット処理（例えば、ネットワークトラフィックフローロジック）は、ここで、汎用プロセッサで処理される可能性があり、それによって、ソフトウェアディファインドネットワークに配置されるネットワークデバイスにとって必要なハードウェアコンポーネントの複雑性を低減し、ハードウェアリリースサイクルとは別の新しいソフトウェアベースの機能の配置を実現する。更に、ソフトウェアディファインドネットワークは、ネットワークインフラストラクチャを従来のネットワークより大きい規模にすることを可能にし、ネットワークの各ネットワークデバイスにより管理されるべきネットワークトラフィックフローロジックに関するデータの増加をもたらし得る。ネットワーク機能仮想化（ＮＦＶ）は、従来のサーバ仮想化技術（例えば、仮想マシン又はＶＭ）を用いてネットワークデバイス機能を仮想化するための他のネットワークアーキテクチャコンセプトであり、それによって、汎用プロセッサ上でネットワークトラフィックの処理を実現する。ＮＦＶ及びＳＤＮインフラストラクチャが組み合わせられたとき、ネットワークは、サイズを更に大きくすることができ、そのことによって、ネットワークの各ネットワークデバイスにより管理されるべきネットワークトラフィックフローロジックのボリュームが更に増加する。

本明細書で説明される複数の概念は、例示として示されるものであり、添付の複数の図において限定として示されるものではない。図示を簡潔及び明瞭にするため、図面に示される要素は、必ずしも縮尺通りに描かれていない。適切であると考えられる場合、複数の参照符号は、対応する又は類似の複数の要素を示すために、複数の図面間で繰り返される。
通信をルーティングするためのシステムの少なくとも１つの実施形態の簡略化されたブロック図である。 オンダイキャッシュのプロセッサを含む図１のネットワークデバイスの少なくとも１つの実施形態の簡略化されたブロック図である。 図２のネットワークデバイスのマルチレベルハッシュテーブルの構成の少なくとも１つの実施形態の簡略化されたブロック図である。 図２のネットワークデバイスのマルチレベルハッシュテーブルの構成の他の実施形態の簡略化されたブロック図である。 図２のネットワークデバイスの環境の少なくとも１つの実施形態の簡略化されたブロック図である。 図１のシステムのソフトウェアディファインドネットワークアーキテクチャの少なくとも１つの実施形態の簡略化されたブロック図である。 図２のネットワークデバイスのキャッシュエビクションポリシーを管理するための方法の少なくとも１つの実施形態の簡略化されたフロー図である。 図１のシステムのフローポリシー情報を受信するための方法の少なくとも１つの実施形態の簡略化されたフロー図である。

本開示の複数の概念は、様々な変形例及び代替的な形態に影響されやすい一方、その特定の複数の実施形態が、複数の図面において例示により示されており、本明細書において詳細に記載される。しかしながら、開示される特定の形態に対して本開示の概念を限定する意図はなく、それどころか、当該意図は、本開示及び添付の特許請求の範囲に一貫する全ての変更、均等物及び代替を網羅するものであると理解されるべきである。

本明細書において「一実施形態」、「実施形態」、「例示的な実施形態」等について言及するとき、そのことは、説明されている実施形態が特定の機能、構造、または特性を含むことを示しているが、あらゆる実施形態がその特定の機能、構造、又は特性を含んでもよいが、必ずしも含まなくてもよい。更に、そのような複数の表現は、必ずしも同じ実施形態に言及するものではない。更に、特定の機能、構造、又は特性が実施形態に関連して記載されているとき、これらは、明記されているか否かに関わらず、複数の他の実施形態に関連するそのような機能、構造、又は特性に関わる当業者の知識の範囲内であるとされる。更に、「Ａ、Ｂ、及びＣのうち少なくとも１つ」という形態のリストに含まれる複数のアイテムは、（Ａ）、（Ｂ）、（Ｃ）、（Ａ及びＢ）、（Ａ及びＣ）、（Ｂ及びＣ）、又は（Ａ，Ｂ，及びＣ）を意味し得ることが理解されるべきである。同様に、「Ａ、Ｂ又はＣの少なくとも１つ」という形態のリストに含まれる複数のアイテムは、（Ａ）、（Ｂ）、（Ｃ）、（Ａ及びＢ）、（Ａ及びＣ）、（Ｂ及びＣ）、又は、（Ａ、Ｂ及びＣ）を意味し得る。

開示されている複数の実施形態は、場合によっては、ハードウェア、ファームウェア、ソフトウェア、又はそれらの任意の組み合わせにおいて、実装されてもよい。開示されている複数の実施形態は、１又は複数のプロセッサにより読み取られ実行され得る、１又は複数の一時的又は非一時的機械可読（例えば、コンピュータ可読）記憶媒体上により伝達される、またはそれらに格納された複数の命令としても実装され得る。機械可読記憶媒体は、機械（例えば、揮発性若しくは非揮発性メモリ、メディアディスク又は他のメディアデバイス）により読み取り可能な形式で、情報を格納又は送信するための任意の記憶デバイス、メカニズム又は他の物理構造として具現化され得る。

複数の図面において、いくつかの構造的又は方法的な特徴は、具体的な構成及び／又は順序で示され得る。しかしながら、そのような具体的な構成及び／又は順序が必要とされなくてよいことを理解されるべきである。むしろ、いくつかの実施形態において、そのような特徴は、例示的な複数の図面に示されているものとは異なる方法及び／又は順序で配置され得る。更に、特定の図面に構造的又は方法的な特徴が含まれているからとって、全ての実施形態においてそのような特徴が必要とされることを示唆するわけではなく、いくつかの実施形態においては、それは含まれなくてもよく、又は他の複数の特徴と組み合わせられてもよい。

ここで図１を参照すると、例示的な実施形態において、ネットワークデバイスのフロールックアップ管理のためのシステム又はネットワーク１００は、ネットワーク制御デバイス１１０に接続されるリモートコンピューティングデバイス１０２及びネットワークインフラストラクチャ１２０を含む。ネットワーク制御デバイス１１０及びネットワークインフラストラクチャ１２０の各々は、ＳＤＮ（ｓｏｆｔｗａｒｅ−ｄｅｆｉｎｅｄ ｎｅｔｗｏｒｋｉｎｇ）アーキテクチャ及び／又はネットワーク機能仮想化（ＮＦＶ）アーキテクチャにおいて動作することが可能である。ネットワークインフラストラクチャ１２０は、ネットワーク通信経路１２４を介したリモートコンピューティングデバイス１０２及びコンピューティングデバイス１３０間のネットワークパケットの送信を容易にするための少なくとも１つのネットワークデバイス１２２を含み、少なくとも１つのネットワークデバイス１２２は、例示的に１２２ａ〜１２２ｈとして表され、本明細書でネットワークデバイス１２２と総称される。

使用において、以下で更に詳細に説明されるように、ネットワークデバイス１２２は、リモートコンピューティングデバイス１０２からネットワークパケットを受信し、ネットワークデバイス１２２に格納されるポリシーに基づいてネットワークパケットを処理し、ネットワークパケットを伝送路内の次のコンピューティングデバイス（例えば、他のネットワークデバイス１２２、コンピューティングデバイス１３０、リモートコンピューティングデバイス１０２等）に転送する。どのコンピューティングデバイスが伝送路内の次のコンピューティングデバイスであるかを知るために、ネットワークデバイス１２２は、ルックアップ動作を実行してネットワークフローを決定する。ルックアップ動作は、ネットワークパケットの一部でハッシュを実行し、結果を利用して、フロールックアップテーブル（すなわち、ネットワークフローの次の宛先にマッピングするハッシュテーブル）に対してチェックする。

一般的に、ネットワークフローがネットワークデバイス１２２のメモリに格納される一方、フロールックアップテーブルは、ルックアップ動作のレイテンシーを減らすべく、プロセッサ上のキャッシュに格納される。しかしながら、フロールックアップテーブルは、非常に大きくなる可能性があり、プロセッサ上のキャッシュ内で利用可能なスペースより大きくなる。このように、フロールックアップテーブルの一部（すなわち、ネットワークフローハッシュエントリーに対応するキャッシュライン）は、ネットワークデバイス１２２のメモリへ追い出され、このことにより、ルックアップ動作にレイテンシーがもたらされる。更に、いずれのキャッシュ追い出しアルゴリズムがネットワークデバイス１２２により採用されるかに基づいて、ネットワークデバイスにより、どのキャッシュラインがメモリに追い出されるかが制御される。しかしながら、マルチレベルフローハッシュテーブルにおいて、他のレベルのマルチレベルフローハッシュテーブルが、ネットワークデバイス１２２のメモリに格納され得る一方、特定のレベルのマルチレベルフローハッシュテーブルは、ネットワークデバイス１２２のプロセッサ上のキャッシュに格納され得る。例えば、以下で更に詳細に説明されるように、マルチレベルフローハッシュテーブルは、プロセッサ上のキャッシュに格納される、より高い優先度レベルのハッシュを格納する第１レベルフローハッシュテーブルと、メインメモリに格納される、より低い優先度レベルのハッシュを格納する第２レベルフローハッシュテーブルとを含んでよい。そのような実施形態において、ルックアップ動作に起因する全体的なレイテンシーは、特定に、高優先度を有するものとしてネットワークデバイス１２２に識別されたこれらネットワークフローハッシュに関して低減され得る。

ネットワークインフラストラクチャ１２０は、セルラーネットワーク（例えば、移動通信用グローバルシステム（ＧＳＭ（登録商標））、デジタル加入者線（ＤＳＬ）ネットワーク、ケーブルネットワーク、電話網、ローカル若しくはワイドエリアネットワーク、グローバルネットワーク（例えば、インターネット）又はそれらの任意の組み合わせを含む任意のタイプの有線又は無線通信ネットワークとして具現化され得る。更に、ネットワークインフラストラクチャ１２０は、各デバイス間の通信を容易にするために必要な任意の数の追加のデバイスを含んでよい。

使用において、ネットワークパケットは、ネットワークフロー又はパケットフローに基づいてネットワークデバイス１２２を相互接続するネットワーク通信経路１２４に沿って、リモートコンピューティングデバイス１０２とコンピューティングデバイス１３０との間で伝送される。ネットワークフローは、ソースから宛先へのパケットのセット又はシーケンスを表す。概して、パケットのセットは、共通の属性を共有する。ネットワークフローは、受信したネットワークパケットを処理した後、どこに（すなわち、ネットワーク通信経路１２４に沿って）送信するかを示すべく、各ネットワークデバイス１２２により用いられる。例えば、ネットワークフローは、例えば、特定のネットワークフローに対応するフロー識別子及びフロータプル（例えば、発信元ＩＰアドレス、発信元ポート番号、宛先ＩＰアドレス、宛先ポート番号及びプロトコル）のような情報を含んでよい。ネットワークフロー情報は、特定のネットワークフローに対応する情報の任意の他のタイプ又は組み合わせを含み得ることが理解されるべきである。

ネットワーク通信経路１２４は、各デバイス間の通信を容易にすることが可能な任意のタイプの有線又は無線信号経路として具現化され得る。例えば、ネットワーク通信経路は、任意の数のワイヤ、プリント回路基板トレース、ビアバス、ポイントツーポイント相互接続、介在デバイス等として具現化され得る。任意の適切な通信プロトコル（例えば、ＴＣＰ／ＩＰ）は、例えば、リモートコンピューティングデバイス１０２、コンピューティングデバイス１３０及びネットワークデバイス１２２の特定のタイプ又は構成に応じて、ネットワーク通信経路１２４に沿うネットワークパケットの伝送を実現するために用いられてよい。ネットワークデバイス１２２は、ルータ、スイッチ等のような、リモートコンピューティングデバイス１０２とコンピューティングデバイス１３０との間の通信を容易にすることが可能な任意のタイプのデバイスとして具現化され得る。いくつかの実施形態において、ＮＦＶアーキテクチャに示すように、ネットワークデバイス１２２の１又は複数は、ソフトウェアにネットワークデバイス１２２の物理ネットワーク機能を実装するべく、１又は複数の仮想マシン（ＶＭ）を実行してよい。言い換えれば、ネットワークデバイス１２２により実行されるいくつかの機能は、仮想化されてよい。

ネットワーク通信経路１２４の例示的な配置は、ネットワークパケットのネットワークインフラストラクチャ１２０内での移動には複数のオプション（すなわち、ルート）があることを示すことを意図される旨が理解されるべきであり、例示的なネットワークインフラストラクチャ１２０の限定として解釈されるべきではない。例えば、ネットワークデバイス１２２ａからネットワークデバイス１２２ｅへ移動するネットワークパケットは、ネットワークデバイス１２２ａからネットワークデバイス１２２ｅへ直接的にネットワークフローを割り振られてよい。他の例において、ネットワークデバイス１２２ａとネットワークデバイス１２２ｅとの間のネットワーク通信経路１２４上のクオリティオブサービス（ＱｏＳ）が貧弱であるなど特定の条件下で、当該同一のネットワークパケットは、ネットワークデバイス１２２ａにネットワークパケットをネットワークデバイス１２２ｂへ伝送することを命令するネットワークフローを割り振られてよく、次に、ネットワークデバイス１２２ｂにネットワークデバイス１２２ｅへネットワークパケットを更に伝送することを命令するネットワークフローを割り振られてよい。

ネットワークパケット管理情報（例えば、ネットワークフロー、ネットワークパケットタイプに対応するポリシー等）は、ネットワークアプリケーション１１４により管理され、ネットワーク制御デバイス１１０上で実行されているネットワークコントローラ１１２に提供される。ネットワークアプリケーション１１４がネットワークパケット管理情報を効果的に管理するために、ネットワークコントローラ１１２は、ネットワークインフラストラクチャ１２０の要約をネットワークアプリケーション１１４に提供する。いくつかの実施形態において、ネットワークコントローラ１１２は、複数の利用可能なネットワークフローに対応するＱｏＳ又は特定のワークロードタイプのネットワークパケットに関連付けられたポリシーに基づいてネットワークパケット管理情報を更新してよい。例えば、コンピューティングデバイス１３０は、リモートコンピューティングデバイス１０２がコンピューティングデバイス１３０で再生するためのビデオストリームを提供することをリクエストするリモートコンピューティングデバイス１０２にリクエストを送信してよい。リモートコンピューティングデバイス１０２は、リクエストを受信した後、次に、リクエストを処理し、リクエストされたビデオストリームのコンテンツに対応するデータ（すなわち、ペイロードデータ、オーバヘッドデータ等）を含むネットワークパケットをネットワークデバイス１２２の１つに提供する。受信側ネットワークデバイス１２２において、受信したネットワークパケットは、処理されるネットワークパケットを送信するためにターゲットデバイスの識別情報を用いて、処理されるネットワークパケットのヘッダを更新する前に処理される。受信したネットワークデバイス１２２は、次に、ターゲットデバイスに処理されたネットワークパケットを、ネットワークコントローラ１１２により提供されるネットワークフローに従って送信する。ターゲットデバイスは、受信したネットワークデバイス１２２がネットワークインフラストラクチャ１２０内のどこに存在するかに応じて、リクエストを開始した他のネットワークデバイス１２２又はコンピューティングデバイス１３０であってよい。

特定のネットワークインフラストラクチャ１２０（すなわち、数万又はそれより多いネットワークデバイス１２２を含むデータセンタ）は、ネットワークコントローラ１１２により提供されるネットワークフローの数量が膨大過ぎ得るのでネットワークデバイス１２２のストレージの優先度レベルに格納できないというような十分に多い数のネットワークデバイス１２２を含み得る。更に、より小さなネットワークインフラストラクチャ１２０であっても、各ネットワークデバイス１２２は、複数の仮想マシン（ＶＭ）をホストしてよく、更に、ネットワークインフラストラクチャ１２０を通じてネットワークパケットを伝達するための可能なネットワークフローの量を増加させる。

ネットワークパケットがネットワークデバイス１２２で受信されたとき、ルックアップ動作は、ネットワークデバイス１２２により実行され、受信したネットワークパケットに対応するネットワークフローを決定する。（複数の）コンピューティングデバイス１３０のユーザは、ネットワークインフラストラクチャ１２０を介してアプリケーションとインタフェースで接続するとき、リアルタイムに近い応答性を予期する。例えば、ネットワークレイテンシー（すなわち、一方の場所から他方へ到着するネットワークパケットの時間）は、フォームをロードする、ビデオをバッファする等についての待ち時間の形式でユーザにより容易に認識できる。このように、各ネットワークデバイス１２２は、各ネットワークパケットを処理して、処理動作に起因するレイテンシーを効率的に取り除く又は減らすべきである。例えば、ネットワークデバイス１２２の可能なストレージの各増分的（ｉｎｃｒｅｍｅｎｔａｌｌｙ）に低いレベルは、本来、各レベルがアクセスされると、増加したレイテンシーに苦しむ。ネットワークデバイス１２２が、（例えば、ワークロードタイプ、ペイロードタイプ、ネットワークプロトコル等）特定のネットワークパケットタイプに関連付けられるネットワークフローのための複数の位置をチェックしなければならない場合、そのような増加したレイテンシーがもたらされ、応答時間が悪化される。したがって、ネットワークデバイス１２２の（複数の）優先位置におけるネットワークデバイス１２２により容易にアクセス可能な特定のネットワークフローを保持することは、ネットワークフローアクセスに起因するレイテンシーをもたらす可能性を減らす。

リモートコンピューティングデバイス１０２は、コンテンツを格納し、ネットワーク制御デバイス１１０及びネットワークインフラストラクチャ１２０と通信することが可能な任意のタイプの記憶デバイスとして具現化され得る。いくつかの実施形態において、リモートコンピューティングデバイス１０２は、コンピュータ、マルチプロセッサシステム、サーバ、コンピューティングサーバ（例えば、データベースサーバ、アプリケーションサーバ、ウェブサーバ等）、ラックマウントサーバ、ブレードサーバ、ラップトップコンピュータ、ノートブックコンピュータネットワークアプライアンス、ウェブアプライアンス、分散コンピューティングシステム、プロセッサベースシステム及び／又はネットワークアタッチドストレージ（ＮＡＳ）デバイスを含むが、これらに限定されない、本明細書で説明される機能を実行することが可能な任意のタイプの計算又はコンピュータデバイスとして具現化され得る。リモートコンピューティングデバイス１０２は、（複数の）プロセッサ、メモリ、Ｉ／Ｏサブシステム、通信回路及び／又は周辺デバイスのような、そのようなデバイスに一般的に見られる任意のタイプのコンポーネントを含み得る。システム１００は、１つのリモートコンピューティングデバイス１０２を有することが例示的に示される一方、１より多いリモートコンピューティングデバイス１０２を含むネットワークが、本明細書で考えられることが理解されるべきである。いくつかの実施形態において、リモートコンピューティングデバイス１０２は、リモートアプリケーション１０６により検索可能なデータを格納することが可能な１又は複数のデータベース（不図示）を更に含んでよい。

例示的なリモートコンピューティングデバイス１０２は、リモートアプリケーション１０６を含む。リモートアプリケーション１０６は、ネットワークインフラストラクチャ１２０のネットワークデバイス１２２を介してコンピューティングデバイス１３０にデータを送信し及び受信することが可能な任意のタイプのアプリケーションとして具現化され得る。いくつかの実施形態において、リモートアプリケーション１０６は、ウェブアプリケーション（すなわち、シンクライアント）、プライベート、パブリック又はハイブリッドクラウドのクラウドベースのアプリケーション（すなわち、シンアプリケーション）として具現化され得る。更に、いくつかの実施形態において、ネットワークコントローラ１１２により提供されるネットワークフロー優先度は、リモートアプリケーション１０６からネットワークコントローラ１１２により受信された情報に基づいてよい。言い換えれば、リモートアプリケーション１０６は、リモートアプリケーション１０６から特定のネットワークパケットタイプに割り振られるネットワークフロー優先度のネットワークコントローラ１１２に情報を提供してよい。例えば、リモートアプリケーション１０６によりネットワークデバイス１２２へ送信されるストリーミングネットワークフロー又はリアルタイムネットワークフローは、他のネットワークフローと比較して、ストリーミングネットワークフローのフロー優先度が高優先度ネットワークフローであることをネットワークデバイス１２２に示すようにネットワークコントローラ１１２に命令してよい。

例示的なシステム１００は、単一のリモートアプリケーション１０６を含む一方、１より多いリモートアプリケーション１０６がリモートコンピューティングデバイス１０２上で実行され又は利用可能であり得ることが理解されるべきである。特定の実施形態において、分散型のコンピューティング環境などにおいて、リモートコンピューティングデバイス１０２の１又は複数にわたって実行する同一タイプのリモートアプリケーション１０６の１より多い例を１より多いリモートコンピューティングデバイス１０２が有し得ることが更に理解されるべきである。

ネットワーク制御デバイス１１０は、ネットワークコントローラ１１２を実行し、リモートコンピューティングデバイス１０２とネットワークインフラストラクチャ１２０との間の通信を容易にし、本明細書で説明される機能を実行することが可能な任意のタイプのコンピューティングデバイスとして具現化され得る。例えば、ネットワーク制御デバイス１１０は、サーバコンピュータ、デスクトップコンピュータ、ラップトップコンピューティングデバイス、民生用電子機器、モバイルコンピューティングデバイス、携帯電話、スマートフォン、タブレットコンピューティングデバイス、パーソナルデジタルアシスタント、ウェアラブルコンピューティングデバイス、スマートテレビ、スマートアプライアンス及び／又は他のタイプのコンピューティング若しくはネットワーキングデバイスとして具現化されてよく、そうでなければ含む。このように、ネットワーク制御デバイス１１０は、説明の明確化を目的として図１では示されていない、プロセッサ、メモリデバイス、通信回路及びデータストレージのようなネットワーク制御デバイス又は同様のコンピューティングデバイスによく見られる複数のデバイス及び複数の構造を含み得る。

ネットワークコントローラ１１２は、ネットワークインフラストラクチャ１２０のネットワークフローを制御することが可能な任意のタイプのハードウェア、ソフトウェア及び／又はファームウェアとして具現化され、そうでなければ含む。例えば、例示的な実施形態では、ネットワークコントローラ１１２は、ＳＤＮ（ｓｏｆｔｗａｒｅ−ｄｅｆｉｎｅｄ ｎｅｔｗｏｒｋｉｎｇ）環境（すなわち、ＳＤＮコントローラ）及び／又はネットワーク機能仮想化（ＮＦＶ）環境（すなわち、ＮＦＶマネージャ及びネットワークオーケストレータ（ｍａｎａｇｅｒ ａｎｄ ｎｅｔｗｏｒｋ ｏｒｃｈｅｓｔｒａｔｏｒ（ＭＡＮＯ））で動作することが可能である。このように、ネットワークコントローラ１１２は、ＳＤＮ環境及び／又はＮＦＶ環境で動作することが可能なネットワークデバイス１２２へネットワークフロー情報を送信（例えば、伝送等）し得る。ＳＤＮアーキテクチャにおいて、ＳＤＮネットワークコントローラは、遠隔地からネットワークデバイス１２２の構成を管理する抽象化された制御プレーンを提供する集中ネットワーク管理アプリケーションとしての役割を果たす。

使用において、ネットワークコントローラ１１２は、以下で更に詳細に説明されるように、フローベースのポリシー及びキャッシュ管理ポリシーのような特定のポリシー情報をネットワークデバイス１２２に提供するように構成される。ポリシー情報は、ストリーミングワークロードのネットワークパケットのようなネットワークパケットのタイプに基づいてよい。例えば、ポリシー情報は、ネットワークデバイス１２２の各々のネットワークフロータイプに対応する優先度を含んでよい。前述のように、ネットワークフローの優先度は、ネットワークパケットのタイプ（例えば、ワークロードタイプ、ペイロードタイプ、ネットワークプロトコル等）に基づいてよい。ネットワークコントローラ１１２からネットワークデバイス１２２の各々により受信されるネットワークフロー優先度は、ネットワークフロー情報をどこ（すなわち、メモリ２０８又はキャッシュ２０４）に格納するかを決定するときに用いるネットワークデバイス１２２のための命令を含む。

ネットワークアプリケーション１１４は、一般的に、ＳＤＮネットワーク内でビジネスアプリケーションと称され、ネットワークインフラストラクチャ１２０を通じてネットワークパケットの処理及びフローを動的に制御することが可能な任意のタイプのネットワークアプリケーションとして具現化され得る。例えば、ネットワークアプリケーション１１４は、ネットワーク仮想化アプリケーション、ファイアウォール監視アプリケーション、ユーザ識別管理アプリケーション、アクセスポリシー制御アプリケーション及び／又はそれらの組み合わせとして具現化され得る。ネットワークアプリケーション１１４は、ネットワークコントローラ１１２をインタフェースと接続し、ネットワークコントローラ１１２に転送されるパケットを受信し、ネットワークデバイス１２２に提供されるネットワークフローを管理するように構成される。

使用において、ネットワークアプリケーション１１４は、ネットワークインフラストラクチャ１２０のトポロジーの要約モデルを受信し、ネットワークインフラストラクチャ１２０のネットワークデバイス１２２の挙動を適合させる。例えば、適合される挙動は、ネットワークフローの変更であってよい。いくつかの実施形態において、変更されるネットワークフローは、リモートアプリケーション１０６の要求に基づいてよく、リアクティブネットワークフローと一般的に称される。以下で更に詳細に説明されるように、いくつかの実施形態において、ネットワークアプリケーション１１４は、アプリケーションプログラミングインタフェース（ＡＰＩ）を介してシステム１００の抽象化を動作することが可能なＳＤＮアプリケーション又は他のコンピュータソフトウェア若しくはプラットフォームであってよい。いくつかの実施形態において、例えば、ネットワークアプリケーション１１４がＳＤＮアプリケーションである場合、ネットワークアプリケーション１１４は、仮想ファイアウォール、仮想アプリケーション配信コントローラ及び仮想ロードバランサーのようなネットワーク仮想化サービスを提供し得る。

コンピューティングデバイス１３０は、ネットワークデバイス１２２を介してリモートアプリケーション１０６へ／からネットワークパケットを送信及び／又は受信するように構成される。コンピューティングデバイス１３０は、デスクトップコンピュータ、ラップトップコンピューティングデバイス、サーバコンピュータ、民生用電子機器、モバイルコンピューティングデバイス、携帯電話、スマートフォン、タブレットコンピューティングデバイス、パーソナルデジタルアシスタント、ウェアラブルコンピューティングデバイス、スマートテレビ、スマートアプライアンス、及び／又は他のタイプのコンピューティングデバイスを含むがこれらに限定されない、本明細書で説明されている複数の機能を実行することが可能な任意のタイプのコンピューティングデバイスとして具現化され得る、又はそうでなければそれらを含み得る。このように、コンピューティングデバイス１３０は、説明の明確化を目的として図１では示されていない、プロセッサ、メモリデバイス、通信回路及びデータストレージのような、コンピューティングデバイスによく見られる複数のデバイス及び複数の構造を含み得る。

ここで図２を参照すると、例示的なネットワークデバイス１２２は、オンダイキャッシュ２０４を有するプロセッサ２０２、メインメモリ２０８、入力／出力（Ｉ／Ｏ）サブシステム２０６、通信回路２１２及び１又は複数の周辺デバイス２１４を含む。ネットワークデバイス１２２は、汎用コンピューティングデバイス、ネットワークアプライアンス（例えば、物理又は仮想）、ウェブアプライアンス、ルータ、スイッチ、マルチプロセッサシステム、サーバ（例えば、スタンドアロン、ラックマウント、ブレード等）、分散コンピューティングシステム、プロセッサベースシステム、デスクトップコンピュータ、ラップトップコンピュータ、ノートブックコンピュータ、タブレットコンピュータ、スマートフォン、モバイルコンピューティングデバイス、ウェアラブルコンピューティングデバイス、民生用電子機器又は他のコンピュータデバイスを含むがこれらに限定されない、本明細書で説明される機能を実行することが可能な任意のタイプの計算又はコンピュータデバイスとして具現化され得る。

使用において、以下で更に詳細に説明されるように、ネットワークデバイス１２２のうちの１つがネットワークコントローラ１１２からネットワークフロー情報を受信したとき、ネットワークフロー情報が、一般的に、ルーティングテーブル又は転送テーブルとも称される、ネットワークフローテーブルに書き込まれる。ネットワークフローテーブルは、一般的に、ネットワークデバイス１２２のメモリ２０８（すなわち、メインメモリ）に格納される。メモリ２０８内のネットワークフロー情報のルックアップを実行しなければならないことに関連するレイテンシーに起因して、ネットワークフロー情報は、ネットワークデバイス１２２のキャッシュ２０４に一般的に格納されるハッシュテーブル又はハッシュルックアップテーブルに書き込まれてよい。

以下で更に詳細に説明されるように、データは、オンダイキャッシュ２０４又はメモリ２０８に格納されてよい。オンダイキャッシュ２０４に格納されたデータは、メモリ２０８からフェッチされるデータよりも少なくとも一桁速くアクセスされ得る。言い換えれば、オンダイキャッシュ２０４内の特定のデータを保持することは、データがメモリ２０８に存在した場合より速くデータにアクセスされることを可能にする。しかしながら、オンダイキャッシュ２０４のスペースは限られているので、ネットワークデバイス１２２は、どのデータをオンダイキャッシュ２０４に格納し、どのデータをメモリ２０８から追い出すかを決定する、置換ポリシー又はキャッシュアルゴリズムとも一般的に称される、キャッシュ置換アルゴリズムに概して依存する。ハッシュテーブルの各エントリーは、オンダイキャッシュ２０４のキャッシュラインに格納される。一般的に、キャッシュ置換アルゴリズムは、どのキャッシュラインを追い出すかを決定するネットワークデバイス１２２のハードウェア（例えば、プロセッサ２０２）に依存する。例えば、ＬＲＵ（ｌｅａｓｔ ｒｅｃｅｎｔｌｙ ｕｓｅｄ）キャッシュ置換アルゴリズムは、まず、キャッシュラインに格納されたデータの重要性に拘らず、最も長い間使用されていないキャッシュラインを追い出す。どのキャッシュラインを追い出すかを決定するハードウェア予測を用いるそのようなキャッシュ置換アルゴリズムは、エラーを起こしやすく、小さなエラーでさえ、レイテンシーを増加させ得る干渉妨害及びキャッシュ汚染をもたらし得る。いくつかの実施形態において、プロセッサ２０２のオンダイキャッシュ２０４は、マルチレベルアーキテクチャを有してよい。そのような実施形態において、オンダイキャッシュ２０４内のデータは、オンダイキャッシュ２０４の最も低いレベルから、ラストレベルキャッシュ（ＬＣＣ）と一般的に称される、オンダイキャッシュ２０４の最も高いレベルに一般的に追い出される。データがオンダイキャッシュ２０４の最も高いレベル（すなわち、ＬＬＣ）から追い出さたとき、データは、概して、メモリ２０８に書き込まれる。

プロセッサ２０２は、本明細書で説明される機能を実行することが可能な任意のタイプのプロセッサとして具現化され得る。例えば、プロセッサ２０２は、（複数の）シングル又はマルチコアプロセッサ、デジタルシグナルプロセッサ、マイクロコントローラ又は他のプロセッサ若しくは処理／制御回路として具現化され得る。メモリ２０８は、本明細書で説明される機能を実行することが可能な任意のタイプの揮発性若しくは非揮発性メモリ又はデータストレージとして具現化され得る。動作において、メモリ２０８は、ネットワークデバイス１２２の動作中に用いられる様々なデータ及びソフトウェアを格納し得る。メモリ２０８は、プロセッサ２０２、メモリ２０８及びネットワークデバイス１２２の他のコンポーネントと共に入力／出力処理を容易にする回路及び／又はコンポーネントとして具現化され得るＩ／Ｏサブシステム２０６を介してプロセッサ２０２に通信可能に連結される。Ｉ／Ｏサブシステム２０６は、オンダイキャッシュ２０４及びメモリ２０８へのデータの伝達を容易にするように構成される。例えば、Ｉ／Ｏサブシステム２０６は、メモリコントローラハブ、入力／出力制御ハブ、ファームウェアデバイス、通信リンク（すなわち、ポイントツーポイントリンク、バスリンク、ワイヤ、ケーブル、ライトガイド、プリント回路基板トレース等）及び／又は入力／出力動作を容易にする他のコンポーネント及びサブシステムとして具現化され得る、そうでなければ含む。いくつかの実施形態において、Ｉ／Ｏサブシステム２０６は、システムオンチップ（ＳｏＣ）の一部を形成してよく、プロセッサ２０２、メモリ２０８及びネットワークデバイス１２２の他のコンポーネントと共に単一の集積回路チップ上に組み込まれてよい。

通信回路２１２は、ネットワークを介して、リモートコンピューティングデバイス１０２、ネットワーク制御デバイス１１０及び他のネットワークデバイス１２２間の通信を実現することが可能な任意の通信回路、デバイス又はそれらの集合として具現化され得る。通信回路２１２は、そのような通信を達成する任意の１又は複数の通信技術（例えば、無線又は有線通信）及び関連プロトコル（例えば、イーサネット（登録商標）、Ｂｌｕｅｔｏｏｔｈ（登録商標）、Ｗｉ-Ｆｉ（登録商標）、ＷｉＭＡＸ（登録商標）等）を用いるように構成され得る。いくつかの実施形態において、通信回路２１２は、セルラー通信回路及び／又は他の長距離無線通信回路を含む。１又は複数の周辺デバイス２１４は、コンピューティングデバイスでよく見られる任意のタイプの周辺デバイスを含んでよく、例えば、ハードウェアキーボード、入力／出力デバイス、周辺通信デバイス等のようなネットワークデバイスを具体的に含み得る。周辺デバイス２１４は、例えば、ＵＳＢ（登録商標）のような外部の周辺デバイスをネットワークデバイス１２２に接続するための１又は複数のポートを追加的又は代替的に含み得ることが本明細書に意図されている。

ここで図３を参照すると、マルチレベルハッシュテーブルを含むネットワークデバイス１２２の構成３００の例示的な実施形態が示されている。新たな技術は、データセンタ及び通信事業者のネットワークにサイズ及び容量を継続的に増やすことを可能し、今までよりも大きいネットワークインフラストラクチャを生み出し、結果として、より多くのネットワークフローのオプションをもたらしている。更に、仮想マシン（ＶＭ）の出現は、ネットワークインフラストラクチャ１２０で利用可能なネットワークフローの数を更に増加させた。いくつかの実施形態において、現在の単一レベルハッシュテーブルは、ハッシュテーブルの全体がネットワークデバイス１２２のオンダイキャッシュ２０４に収まることができないほど大きくなり得る。例示的なマルチレベルハッシュテーブルは、第１レベルハッシュテーブル３０２及び第２レベルハッシュテーブル３０４を含む。いくつかの実施形態において、マルチレベルハッシュテーブルは、「第Ｎ」レベルハッシュテーブル３０６を更に含み、ここで「Ｎ」は、正の整数であり、第２レベルハッシュテーブル３０４を超えた、ハッシュテーブルの１又は複数の追加のレベルを示す。例示的な第２レベルハッシュテーブル３０４及び「第Ｎ」レベルハッシュテーブル３０６がメモリ２０８に存在する一方、例示的な第１レベルハッシュテーブル３０２は、プロセッサ２０２のオンダイキャッシュ２０４に存在する。第１レベルハッシュテーブル３０２及び第２レベルハッシュテーブル３０４から「第Ｎ」レベルハッシュテーブル３０６の各々は、ネットワークフローの優先度及び／又はネットワークフローのアクセス頻度に基づいてメモリ２０８に格納されたネットワークフローにマッピングされるハッシュエントリーを含む。更に、以下で更に詳細に説明されるように、ネットワークフローの優先度及び／又はネットワークフローのアクセス頻度が、継時的に変化するにつれて、Ｉ／Ｏサブシステム２０６は、オンダイキャッシュ２０４とメモリ２０８との間で特定のハッシュエントリーを移動させ得る。

第１レベルハッシュテーブル３０２のハッシュエントリーは、ネットワークコントローラ１１２からネットワークデバイス１２２に提供されるネットワークフローの優先度に基づいて、オンダイキャッシュ２０４にロックされ得る。例えば、リアルタイムネットワークパケットのネットワークフローは、リアルタイムに処理されることが予期されていないネットワークパケットより高い優先度を与えられ得る。他の例において、他のネットワークフローより頻繁にアクセスされる予定のネットワークフローは、より高い優先度を与えられ得る。追加的又は代替的に、第１レベルハッシュテーブル３０２のハッシュエントリーは、ハッシュエントリーがアクセスされる頻度に基づいてオンダイキャッシュ２０４をロックされ得る。例えば、ネットワークコントローラ１１２は、特定の優先度が、予め定められた回数（すなわち、アクセス頻度閾値）より多くアクセスされたハッシュエントリーに取って代わることをネットワークデバイス１２２に通知してよい。いくつかの実施形態において、アクセスカウンタは、アクセス頻度を追跡するべく、各ハッシュエントリーに対応して格納されてよい。アクセスされたハッシュエントリーに対応するアクセスカウンタは、ハッシュエントリーがアクセスされる度にインクリメントされてよい。いくつかの実施形態において、アクセスカウンタは、アクセスカウンタがインクリメントされた最後の時間を示すタイムスタンプを更に含んでよい。いくつかの実施形態において、ネットワークコントローラ１１２は、アクセス頻度が古くになること及びキャッシュ汚染をもたらすことを避けるべく、予め定められた時間の間にアクセスされなかったアクセスカウンタをリセットすることをネットワークデバイス１２２に更に通知してよい。

概して、より小さいサイズに制限されたオンダイキャッシュ２０４上に存在する第１レベルハッシュテーブル３０２は、一般的に、ハッシュテーブルの他のレベルより小さい。使用において、以下で更に詳細に説明されるように、ネットワークパケットがネットワークデバイス１２２により受信されたとき、ヘッダの一部は、キーフィールドを抽出するべくデコードされる。ハッシュ機能は、次に、抽出されたキーフィールドに対して実行され、ルックアップは、オンダイキャッシュ２０４の第１レベルハッシュテーブル３０２に対して実行される。ルックアップが成功（すなわち、ルックアップがオンダイキャッシュ２０４の第１レベルハッシュテーブル３０２にハッシュを発見）した場合、「ヒット」が発生し、ネットワークフローテーブル３０８に格納されたフローに関連付けられたデータが一般的に更新される。ルックアップが失敗だった（すなわち、ルックアップがオンダイキャッシュ２０４の第１レベルハッシュテーブル３０２にハッシュを発見しなかった）場合、「ミス」が発生する。「ヒット」が発生するまで、ネットワークデバイス１２２が残りの各レベルでルックアップを実行しなければならないことに起因して、「ヒット」は、「ミス」より速い（すなわち、より少ない計算サイクル）。

例示的な構成３００において、第２レベルハッシュテーブル３０４は、メモリ２０８内に完全に存在し、そのようなものとして、メモリ２０８内のルックアップ動作が、ルックアップがオンダイキャッシュ２０４の第１レベルハッシュテーブル３０２内にハッシュを発見した場合よりも、少なくとも一桁長いＩ／Ｏレイテンシーをもたらし得る。いくつかの実施形態において、他の構成が本明細書で考えられると理解されるべきである。例えば、図４は、第２レベルハッシュテーブル３０４の少なくとも一部がプロセッサ２０２のオンダイキャッシュ２０４に存在するマルチレベルハッシュテーブルを含むネットワークデバイス１２２の構成４００の例示的な実施形態を示す。いくつかの実施形態において、特定のフロー優先度は、マルチレベルハッシュテーブルのレベルの排他性に関する情報を更に含んでよい。例えば、ネットワークコントローラ１１２は、高優先度フローに対応するハッシュエントリーのみを含めることをネットワークデバイス１２２に命令するための情報を、第１レベルハッシュテーブル３０２に提供し、第２レベルハッシュテーブル３０４に提供しなくてよい。他の例において、ネットワークコントローラ１１２は、第１レベルハッシュテーブル３０２に高優先度フローに対応するハッシュエントリーのみを含めること、及び、オンダイキャッシュ２０４に存在する第２レベルハッシュテーブル３０４の一部に頻繁にアクセスされるハッシュエントリーのみを含めることをネットワークデバイス１２２に命令するための情報を提供してよい。更に他の例において、ネットワークコントローラ１１２は、第１レベルハッシュテーブル３０２及び第２レベルハッシュテーブル３０４に高優先度フローに対応するハッシュエントリー及び頻繁にアクセスされるハッシュエントリーを含めることをネットワークデバイス１２２に命令するための情報を提供してよい。

再び図３を参照すると、例示的な構成３００は、ネットワークフローテーブル３０８を含む。前述のように、ネットワークフロー情報は、ネットワークフローテーブル３０８に書き込まれるフロー識別子及びフロータプルを一般的に含む。ネットワークフローテーブルは、特定のネットワークフローに対応する情報の任意の他のタイプ又は組み合わせを追加的又は代替的に含んでよい。ネットワークフローテーブル３０８は、ネットワークデバイス１２２のメモリ２０８（すなわち、メインメモリ）に一般的に格納される。他の実施形態において、第２レベルハッシュテーブル３０４の一部が第１レベルハッシュテーブル３０２より大きいサイズであってよい一方、いくつかの実施形態において、第１レベルハッシュテーブル３０２は、第２レベルハッシュテーブル３０４の一部より大きいサイズであってよいことが理解されるべきである。

ここで図５を参照すると、使用において、ネットワークデバイス１２２の各々は、動作中に環境５００を確立する。例示的な環境５００は、ネットワークフローハッシュルックアップモジュール５０２、ネットワークフローハッシュテーブル管理モジュール５１０及びネットワークパケット処理モジュール５２０を含む。ネットワークフローハッシュルックアップモジュール５０２は、ハッシュテーブル内のハッシュエントリーに対応するアクセスカウントを表すデータを含み得るフローアクセスデータ５０４を含む。例えば、ハッシュが、レベルに拘らず、ハッシュテーブルにアクセスされる度に、そのハッシュのためにネットワークデバイス１２２によるアクセスの頻度に対する履歴参照を提供するべく、当該カウンタに対応するカウンタがインクリメントされてよい。いくつかの実施形態において、アクセスの時間及び／又は最後の「ヒット」ハッシュテーブルレベルのような、追加の情報がフローアクセスデータに含まれてよい。ネットワークフローハッシュテーブル管理モジュール５１０は、ネットワークコントローラ１１２から受信されるフロー優先度データ５１２を含む。フロー優先度データ５１２は、どのネットワークフローハッシュエントリーをマルチレベルハッシュテーブルのどのレベルに置くべきかをネットワークフローハッシュテーブル管理モジュール５１０に示すポリシー（すなわち、命令）を含む。いくつかの実施形態において、フロー優先度データ５１２は、ネットワークパケットタイプに対応するキャッシュエビクションポリシーを含んでよい。

環境５００の様々なモジュールは、ハードウェア、ファームウェア、ソフトウェア又はそれらの組み合わせとして具現化され得る。例えば、環境５００の様々なモジュール、ロジック及び他のコンポーネントは、プロセッサ２０２又はネットワークデバイス１２２の他のハードウェアコンポーネントの一部を形成してよく、そうでなければ、それらにより確立されてよい。このように、いくつかの実施形態において、環境５００のモジュールの１又は複数は、電気デバイスの回路又は集合（例えば、ネットワークフロー検索回路、ネットワークフローハッシュ管理回路、ネットワークパケット処理回路等）として具現化され得る。各ネットワークデバイス１２２は、説明の明確化を目的として図５に示されていない、他のコンポーネント、サブコンポーネント、モジュール及びコンピューティングデバイスでよく見られるデバイスを含み得ることが理解されるべきである。更に、ネットワークデバイス１２２の各々が動作中に例示的な環境５００を確立し得るが、例示的な環境５００の以下の説明では、説明の明確化を目的として、単一のネットワークデバイス１２２を具体的に参照して説明されることが理解されるべきである。

ネットワークフローハッシュルックアップモジュール５０２は、ネットワークデバイス１２２で受信したネットワークパケットに基づいて、ネットワークフローハッシュルックアップを実行するように構成される。いくつかの実施形態において、ネットワークフローハッシュルックアップモジュール５０２は、ネットワークパケットハッシュモジュール５０６及び／又はハッシュルックアップモジュール５０８を含んでよい。ネットワークパケットハッシュモジュール５０６は、ネットワークデバイス１２２により受信されるネットワークパケットのヘッダの一部をハッシュするように構成される。ハッシュルックアップモジュール５０８は、ヘッダのハッシュされた一部を用いてルックアップ動作を実行するように構成される。前述のように、ルックアップ動作は、第１レベルハッシュテーブル３０２で実行され、ルックアップ動作が成功したか否かに応じて、ルックアップ動作は、ネットワークフローテーブル３０８内のネットワークフローの位置に戻るか、又は、第２レベルハッシュテーブル３０４へ進むなどを行う。いくつかの実施形態において、各ハッシュエントリーは、アクセスカウンタを有してよい。ルックアップ動作が戻るとき、ネットワークフローテーブル３０８内を検索されたネットワークフローのハッシュエントリーに対応するアクセスカウンタがインクリメントされ得る。いくつかの実施形態において、アクセスカウンタは、ハッシュエントリーがアクセスされた最後の時間に対応するタイム値を更に含んでよい。

ネットワークフローハッシュテーブル管理モジュール５１０は、マルチレベルハッシュテーブル内のネットワークフローハッシュエントリーの位置を管理するように構成される。いくつかの実施形態において、ネットワークフローハッシュテーブル管理モジュール５１０は、ネットワークフローハッシュ格納優先度決定モジュール５１４及び／又はネットワークフローハッシュ格納位置強制モジュール５１６を含んでよい。ネットワークフローハッシュ格納優先度決定モジュール５１４は、コントローラ１１２から受信されたフロー優先度データ５１２に格納されたフロー優先度から、どのフロー優先度がネットワークフローテーブル３０８内のネットワークフローに対応するハッシュエントリーに適用されるべきかを決定するように構成される。

ネットワークフローハッシュ格納位置強制モジュール５１６は、フロー優先度に基づいて、ハッシュエントリーの位置（すなわち、オンダイキャッシュ２０４又はメモリ２０８）を強制するように構成される。前述のように、特定のハッシュエントリーは、これらハッシュエントリーに対応するネットワークフローのフロー優先度及び／又はアクセス頻度に基づいて、第１レベルハッシュテーブル３０２内にロックされ得る。キャッシュ置換アルゴリズムに依存して、ハッシュエントリーは、オンダイキャッシュ２０４からメモリ２０８へ追い出され、又は、ハッシュエントリーのアクセスパターンに基づいて、メモリ２０８からオンダイキャッシュ２０４に促される。このように、優先度フローに対応するハッシュエントリーは、オンダイキャッシュ２０４からメモリ２０８へ追い出され、レイテンシーをもたらす。ネットワークフローハッシュ格納位置強制モジュール５１６は、ネットワークコントローラ１１２から受信したフロー優先度に基づいてオンダイキャッシュ２０４又はメモリ２０８のいずれかに位置付けられるようにハッシュエントリーを強制することによりキャッシュ置換アルゴリズムのみに依存するといった欠点を克服する。

いくつかの実施形態において、キャッシュ置換アルゴリズムがＬＲＵ（ｌｅａｓｔ ｒｅｃｅｎｔｌｙ ｕｓｅｄ）ポリシーを実装するもののように、ネットワークフローハッシュ格納位置強制モジュール５１６は、高優先度ハッシュエントリーに関連するキャッシュラインに定期的に「接触」するべく、別個のスレッドを生成し得る。そのような実施形態において、特定のキャッシュラインに「接触」することは、エイジビットがＬＲＵ位置に存在しないように、「接触」されたキャッシュラインが追い出されないことを保証するべくエイジビットを設定する。いくつかの実施形態において、ハードウェアロードロック命令（例えば、「ｌｏａｄＬＫ」）は、ネットワークデバイス１２２のプロセッサ２０２により顕在化され得る。そのような実施形態において、ハードウェアロードロック命令は、キャッシュラインを追い出すべきか否か又はオンダイキャッシュ２０４にキャッシュラインをロックするべきか否かをプロセッサに示す。言い換えれば、ハードウェアロードロック命令は、キャッシュ置換アルゴリズムに取って代わるものである。オンダイキャッシュ２０４内のキャッシュラインでロックされたハッシュエントリーに対応するネットワークフローが終了したとき、ネットワークコントローラ１１２は、ネットワークフローに対応するハッシュエントリーのキャッシュラインがこれ以上オンダイキャッシュ２０４にロックされる必要がないという命令をネットワークデバイス１２２に提供してよい。いくつかの実施形態において、プロセッサ２０２は、ロックされたキャッシュラインを定期的にチェックし、任意のロックされたキャッシュラインが古くなる（すなわち、キャッシュラインが予め定められた期間にアクセスされなかった）か否かを決定する。いくつかの実施形態において、任意のキャッシュラインが古くなっていた場合、プロセッサ２０２は、キャッシュ汚染に起因する潜在的なレイテンシーを減らすべく、古くなったキャッシュラインをアンロックしてよい。更に、以下で更に詳細に説明されるように、ネットワークフローハッシュ格納位置強制モジュール５１６は、ネットワークフローテーブル３０８内のネットワークフローのハッシュエントリーに対応するアクセスカウンタを解釈してよい。ネットワークフローハッシュ格納位置強制モジュール５１６は、アクセスカウンタを解釈して、その現在の位置にハッシュエントリーを保持しておくか否か又はハッシュエントリーを移動するか（すなわち、オンダイキャッシュ２０４からメモリ２０８へ移動する、逆もまた然り）否かを決定する。

ネットワークパケット処理モジュール５２０は、他のネットワークデバイス１２２、リモートコンピューティングデバイス１０２又はコンピューティングデバイス１３０のようなターゲットデバイスへ、処理されるネットワークパケットを送信する前にネットワークパケットを処理するように構成される。いくつかの実施形態において、ネットワークパケット処理モジュール５２０は、ルーティングプロトコル検索モジュール５２２及び／又はパケットヘッダ更新モジュール５２４を含んでよい。ルーティングプロトコル検索モジュール５２２は、ネットワークパケットがＩ／Ｏサブシステム２０６からオンダイキャッシュ２０４で受信されることに応答してネットワークパケットを処理するべく、どのルーティングプロトコルを用いるかを決定するべく、ルックアップ動作を実行するように構成される。いくつかの実施形態において、ルックアップ動作を実行することは、ネットワークデバイス１２２のルックアップテーブル内のルーティングプロトコルを検索することを含み得る。パケットヘッダ更新モジュール５２４は、ネットワークパケットのヘッダを更新するように構成される。更新されたヘッダは、例えば、ネットワークフローハッシュルックアップモジュール５０２により検索された、更新されたネットワークフロー情報を含み得る。

ここで図６を参照すると、システム１００により実装され得るＳＤＮアーキテクチャ６００の例示的な実施形態は、アプリケーション層６０２、制御層６１０及びインフラストラクチャ層６２０を含む。アプリケーション層６０２は、１又は複数のネットワークアプリケーション１１４を含んでよく、インフラストラクチャ層６２０は、１又は複数のネットワークデバイス１２２を含んでよい。ＳＤＮアーキテクチャの実施形態において、システム１００は、概して、ＡＤＮ（ａｐｐｌｉｃａｔｉｏｎ ｄｅｆｉｎｅｄ ｎｅｔｗｏｒｋｉｎｇ）ネットワークである。したがって、ネットワークアプリケーション１１４は、ＡＤＮネットワーク内のネットワークデバイス１２２の挙動を制御する。そうするべく、ネットワークアプリケーション１１４は、それらの要求をネットワークコントローラ１１２へ通信し、ノースバウンドＡＰＩ６０４を介してネットワークコントローラ１１２からフィードバックを受信する。いくつかの実施形態において、要求は、リモートアプリケーション１０６及び／又はネットワークパケットタイプの要求に基づいてよい。ノースバウンドＡＰＩ６０４は、アプリケーション層６０２のネットワークアプリケーション１１４に、ネットワークパケットフロー及びポリシー情報を含む情報を通信することを可能にするべく、ネットワーク要約インタフェースを制御層６１０のネットワークコントローラ１１２に提供する。ネットワークコントローラ１１２で受信した情報は、ネットワークデバイス１２２の挙動を定義及び制御するサウスバウンドＡＰＩ６１２を通過する。

ここで図７を参照すると、使用において、各ネットワークデバイス１２２は、図３のネットワークフローテーブル３０８のようなネットワークフローハッシュテーブルのハッシュエントリーについてルックアップを実行するための方法７００を実行してよい。方法７００は、ブロック７０２で始まり、ここで、ネットワークデバイス１２２は、ネットワークパケットがソースデバイスからネットワークデバイス１２２において受信されたか否かを決定する。ソースデバイスは、ネットワークパケットを受信したネットワークインフラストラクチャ１２０内のネットワークデバイス１２２の位置に応じて、リモートコンピューティングデバイス１０２又は他のネットワークデバイス１２２であってよい。ネットワークパケットが受信されなかった場合、方法７００は、ブロック７０２に戻って、ネットワークパケットの監視を継続する。ネットワークパケットがネットワークデバイス１２２で受信された場合、ネットワークパケットのヘッダがブロック７０４で処理される。ネットワークパケットのヘッダを処理することは、例えば、ネットワークパケットヘッダの少なくとも一部に対してハッシュを実行し、キーフィールドを抽出し及び／又はネットワークパケットタイプに対応するフローを決定するべくルックアップを実行することを含む任意のタイプのパケット処理を含んでよい。ブロック７０６において、ネットワークデバイス１２２は、ブロック７０４で生成されたネットワークパケットヘッダの一部の結果（すなわち、ハッシュ）を用いて第１レベルハッシュテーブル３０２でハッシュルックアップを実行する。

ブロック７０８において、ネットワークデバイス１２２は、方法７００がブロック７０８へ進む前に実行されたハッシュルックアップが成功したか否かを決定する。ハッシュルックアップが成功した（すなわち、「ヒット」という結果になった）場合、方法７００はブロック７１２に進む。いくつかの実施形態において、ブロック７１０に示すように、ネットワークデバイス１２２は、ブロック７１２に進む前に、検索されたハッシュエントリーに対応するアクセスカウンタをインクリメントされ得る。前述のように、各ハッシュエントリーに対応するアクセスカウンタは、ハッシュエントリーのアクセス頻度を追跡するべく、ネットワークデバイス１２２により用いられる。いくつかの実施形態において、アクセスカウンタは、アクセスカウンタがインクリメントされた最後の時間を示すタイムスタンプを更に含む。

ブロック７１２において、ネットワークデバイス１２２は、ハッシュエントリーの格納位置を更新する。特定のマルチレベルハッシュテーブル配置において、ハッシュエントリーの格納位置を更新することは、オンダイキャッシュ２０４からメモリ２０８へハッシュエントリーを追い出すこと、メモリ２０８からオンダイキャッシュ２０４へハッシュエントリーを促すこと、及び／又は、同じ格納位置でマルチレベルハッシュテーブルの異なるレベルにハッシュエントリーを移動させること（例えば、図４に示すように、オンダイキャッシュ２０４内に存在する第１レベルハッシュテーブル３０２からオンダイキャッシュ２０４内に同じく存在する第２レベルハッシュテーブル３０４の一部へハッシュエントリーを移動させる）を含んでよい。

特定の条件の下において、ブロック７１４に示すように、ネットワークデバイス１２２は、より低いレベルのハッシュテーブルへハッシュエントリーを追い出してよい。例えば、ハッシュエントリーに対応するネットワークフローが、もはやアクティブでなく、予め定められた時間内にアクセスされておらず、及び／又はより高い優先度ネットワークフローがオンダイキャッシュ２０４内にスペースを必要としている場合、ネットワークデバイス１２２は、より低いレベルのハッシュテーブルへハッシュエントリーを追い出してよい。

特定の条件の下において、ブロック７１６のように、ネットワークデバイス１２２は、より高いレベルのハッシュテーブルへハッシュエントリーを促してよい。例えば、ハッシュエントリーに対応するネットワークフローがアクティブになり、予め定められた時間にわたってアクセスの数がアクセス頻度閾値を超えており、及び／又はハッシュエントリーに対応するネットワークフローがオンダイキャッシュ２０４内に現在存在するハッシュエントリーより高い優先度を有している場合、ネットワークデバイス１２２は、より高いレベルのハッシュテーブルへハッシュエントリーを促してよい。

特定の条件の下において、ブロック７１８に示すように、ネットワークデバイス１２２は、第１レベルハッシュテーブル３０２内のハッシュエントリーをロックしてよい。いくつかの実施形態において、ＬＲＵキャッシュ置換アルゴリズムを実装する実施形態のように、ネットワークデバイス１２２は、高優先度のハッシュエントリーのキャッシュラインに「接触」するために専用のスレッドを用いてハッシュエントリーのキャッシュラインに「接触」することにより、第１レベルハッシュテーブル３０２にハッシュエントリーをロックしてよい。このように、ターゲットキャッシュラインに「接触」することは、高優先度を有するハッシュエントリーのキャッシュラインがＬＲＵ位置には存在せず、そのため、追い出されないことを保証する。いくつかの実施形態において、プロセッサ２０２は、リソース競合を避けるべく、プロセッサ２０２の別個のコア上でスレッドが実行され得るマルチコアプロセッサであることが意図される。いくつかの実施形態において、ネットワークデバイス１２２のプロセッサ２０２は、ネットワークデバイス１２２のソフトウェアが第１レベルハッシュテーブル３０２にロックするべく、特定のハッシュエントリーの特定のキャッシュラインを追い出さないようにプロセッサ２０２に命令できるように、ロードロック命令（すなわち、第１レベルハッシュテーブル３０２にキャッシュラインをロックするか否かを示すビット）を顕在化してよい。

ネットワークデバイス１２２がハッシュエントリーの格納位置を更新した後、方法は、ブロック７２０に進み、そこでネットワークパケットヘッダがハッシュエントリーに対応するネットワークフローに基づいて更新される。ブロック７２２において、更新されたネットワークパケットは、ターゲットデバイスに送信される。ネットワークインフラストラクチャ１２０及びネットワークフロー内のネットワークデバイス１２２の位置に応じて、ターゲットデバイスは、他のネットワークデバイス１２２、リモートコンピューティングデバイス１０２又はコンピューティングデバイス１３０であってよい。ブロック７２２から、方法７００は、ブロック７０２に戻る。

ブロック７０８で、ハッシュルックアップが成功しなかった（すなわち、「ミス」の結果となった）場合、方法７００は、ブロック７２４に進む。ブロック７２４において、ネットワークデバイス１２２は、次のレベルのハッシュテーブルが利用可能か否かを決定する。例えば、最初の反復では、次のレベルのハッシュテーブルは、第２レベルハッシュテーブル３０４に対応する。各後続の反復は、「第Ｎ」レベルハッシュテーブル３０６が到達されるまで、ハッシュテーブルのレベルをインクリメントする。次のレベルのハッシュテーブルが利用可能である場合、ハッシュルックアップは、ブロック７２６において、次のレベルのハッシュテーブル上で実行される。言い換えれば、ハッシュルックアップは、ブロック７２４の各後続の反復についてブロック７２６で実行される。

いくつかの実施形態において、ハッシュルックアップは、ハッシュルックアップを実行する前に、ブロック７２８において次のレベルのハッシュテーブル上で確率演算を実行することを含んでよい。いくつかの実施形態において、確率演算は、ルックアップを実行する前に、ハッシュエントリーがハッシュテーブル内に存在するか否かの確率を決定するべく実行され得る。確率演算を実行することは、ハッシュルックアップ上の「ミス」に起因するレイテンシーを減らす。確率演算は、ハッシュエントリーがハッシュテーブルに位置付けられる確率を決定することが可能な任意のタイプの確率方法を用いて実行され得る。例えば、ブルームフィルタを用いた実施形態において、ブルームフィルタは、ビットベクトルベースのデータ構造を有する。ブルームフィルタに要素を追加するべく、ハッシュのキーは、ビットベクトル内の対応するビットを設定するべく用いられてよい。ハッシュエントリーが、ハッシュルックアップが実行されるハッシュテーブル内に存在するか否かを決定するべく、ハッシュのキーが適用され、次に、設定されたビットが適切なビットベクトル内でチェックされる。設定されたビットがビットベクトル内に存在しない場合、ハッシュエントリーは、ハッシュルックアップが実行されるハッシュテーブル内に存在しない。設定されたビットがビットベクトル内に存在する場合、ハッシュエントリーは、ハッシュルックアップが実行されるハッシュテーブル内に存在し得る。いくつかの実施形態において、確率演算は、同様に、第１レベルハッシュテーブル３０２内でハッシュルックアップを実行する前に更に実行されてよい。そうすることで、ハッシュテーブルのレベル内の検索を実行することに関連するレイテンシーは減らされ得、更に、全体のルックアップ時間が改善される。

次のレベルのハッシュテーブルがブロック７２４で利用可能でない場合、方法７００は、図８に示すブロック７３０へ進む。ブロック７３０で、リクエストは、ブロック７０２で受信されたネットワークパケットに対応するフロー優先度情報について、ネットワークデバイス１２２からネットワークコントローラ１１２へ送信される。ブロック７３２で、ネットワークフロー及びフロー優先度情報は、ネットワークコントローラから受信される。いくつかの実施形態において、ブロック７３４で、フロー優先度情報は、受信したネットワークパケットのネットワークフローに対応するハッシュエントリーに割り振られる優先度のレベルを含んでよい。いくつかの実施形態において、ブロック７３６で、フロー優先度情報は、ロードロック命令に対応するハッシュエントリーのビットを設定するか否かの指標を追加的に又は代替的に含んでよい。ブロック７３８で、ネットワークフローは、ネットワークフローテーブル３０８に追加される。ブロック７４０で、ブロック７４０で生成されたハッシュの格納位置を更新するべく、方法７００がブロック７１２へ進む前に、ハッシュは、ブロック７３８でネットワークフローテーブル３０８に追加されたネットワークフローに対応して生成される。

キャッシュ２０４は、オンダイキャッシュ又はプロセッサ上のキャッシュとして上記で説明されているが、いくつかの実施形態において、キャッシュ２０４は、コンピューティングデバイス１０２のプロセッサ２０２がメモリ２０８より速くアクセスできる任意のタイプのキャッシュメモリとして具現化され得ることが理解されるべきである。例えば、いくつかの実施形態において、キャッシュ２０４は、オフダイキャッシュであってよいが、プロセッサ２０２と同じＳｏＣ上に存在する。

実施例

本明細書に開示されている技術の例示的な実施例が以下に提供される。複数の技術の実施形態は、以下で説明される実施例のうち、任意の１又は複数及び任意の組み合わせを含んでよい。

実施例１は、ネットワークフローに対応するネットワークフローハッシュの格納位置管理のためのネットワークデバイスであって、ネットワークデバイスのプロセッサのためのキャッシュと、キャッシュとは異なるメインメモリと、ネットワークフローを含むメインメモリに格納されるネットワークフローテーブルと、複数のフローハッシュテーブルを含むマルチレベルフローハッシュテーブルであって、複数のフローハッシュテーブルがキャッシュに格納される第１レベルフローハッシュテーブル及び第２レベルフローハッシュテーブルを有し、第２レベルフローハッシュテーブルの少なくとも一部がキャッシュに格納される、マルチレベルフローハッシュテーブルと、ネットワークデバイスに通信可能に連結されるネットワークコントローラからネットワークフローに対応する優先度を受信し、受信した優先度に基づいて第１レベル又は第２レベルフローハッシュテーブルのいずれかにネットワークフローに対応するネットワークフローハッシュを格納するネットワークフローハッシュテーブル管理モジュールとを含む。

実施例２は、実施例１の主題を含み、第１レベル及び第２レベルフローハッシュテーブルの各々は、複数のネットワークフローハッシュを含み、複数のネットワークフローハッシュの各々は、ネットワークフローテーブル内の複数のネットワークフローのネットワークフローに対応する。

実施例３は、実施例１及び２のいずれかの主題を含み、第１レベル又は第２レベルフローハッシュテーブルのいずれかにネットワークフローに対応するネットワークフローハッシュを格納することは、ネットワークフローハッシュに対応する優先度が第１レベルフローハッシュテーブルに現在格納されている他のネットワークフローハッシュに対応する優先度より高いとの決定に応じて、第１レベルフローハッシュテーブルでネットワークフローハッシュを格納することを含む。

実施例４は、実施例１―３のいずれかの主題を含み、ネットワークフローハッシュテーブル管理モジュールは、更に、ネットワークフローハッシュに対応する優先度が他のネットワークフローハッシュに対応する優先度より高いとの決定に応じて、第２レベルフローハッシュテーブルへ他のネットワークフローハッシュを追い出す。

実施例５は、実施例１―４のいずれかの主題を含み、第１レベル又は第２レベルフローハッシュテーブルのいずれかにネットワークフローに対応するネットワークフローハッシュを格納することは、ネットワークフローハッシュのアクセスの頻度が第１レベルフローハッシュテーブルに現在格納されている他のネットワークフローハッシュのアクセスの頻度より高いとの決定に応じて、第１レベルフローハッシュテーブルにネットワークフローハッシュを格納することを含む。

実施例６は、実施例１―５のいずれかの主題を含み、第１レベル又は第２レベルフローハッシュテーブルのいずれかにネットワークフローに対応するネットワークフローハッシュを格納することは、更に、ネットワークフローハッシュのアクセス頻度に基づく。

実施例７は、実施例１―６のいずれかの主題を含み、第１レベル又は第２レベルフローハッシュテーブルのいずれかにネットワークフローに対応するネットワークフローハッシュを格納することは、ネットワークフローハッシュのアクセス頻度が第１レベルフローハッシュテーブルに現在格納されている他のネットワークフローハッシュのアクセス頻度より高いとの決定に応じて、第１レベルフローハッシュテーブルにネットワークフローハッシュを格納することを含む。

実施例８は、実施例１―７のいずれかの主題を含み、第２レベルフローハッシュテーブルの他の一部は、ネットワークデバイスのメインメモリに格納される。

実施例９は、実施例１―８のいずれかの主題を含み、第１又は第２レベルフローハッシュテーブルのいずれにネットワークフローに対応するネットワークフローハッシュを格納することは、ネットワークフローハッシュに対応する優先度が第１レベルフローハッシュテーブルに現在格納されているネットワークフローハッシュの優先度より低く、かつ、ネットワークフローハッシュに対応するアクセス頻度がキャッシュに格納された第２レベルフローハッシュテーブルの一部に現在格納されている他のネットワークフローハッシュのアクセス頻度より高いとの決定に応じて、キャッシュに格納された第２レベルフローハッシュテーブルの一部にネットワークフローハッシュを格納することを含む。

実施例１０は、実施例１―９のいずれかの主題を含み、ネットワークフローハッシュテーブル管理モジュールは、更に、ネットワークコントローラから受信された優先度に基づいてキャッシュ内のネットワークフローに対応するネットワークフローハッシュをロックする。

実施例１１は、実施例１―１０のいずれかの主題を含み、キャッシュは、複数のキャッシュラインを含み、各キャッシュラインは、ネットワークフローハッシュを収容可能であり、キャッシュ内のネットワークフローハッシュをロックすることは、ネットワークコントローラから受信される優先度に基づいてネットワークフローハッシュに対応するキャッシュラインのビットを設定することを含む。

実施例１２は、実施例１―１１のいずれかの主題を含み、キャッシュラインのビットを設定することは、キャッシュラインのエイジビットを設定することを含む。

実施例１３は、実施例１―１２のいずれかの主題を含み、キャッシュラインのビットを設定することは、キャッシュラインの追い出しインジケータビットを設定することを含む。

実施例１４は、実施例１―１３のいずれかの主題を含み、更に、ネットワークデバイスにより受信されるネットワークパケットのヘッダの少なくとも一部をハッシュし、マルチレベルフローハッシュテーブルの第１レベルフローハッシュテーブルでネットワークパケットのヘッダのハッシュされた一部について第１ルックアップを実行するネットワークフローハッシュルックアップモジュールを含む。

実施例１５は、実施例１―１４のいずれかの主題を含み、ネットワークフローハッシュルックアップモジュールは、第１レベルフローハッシュテーブルで第１ルックアップが失敗した後に、第２レベルフローハッシュテーブルでネットワークパケットのヘッダのハッシュされた一部について第２ルックアップを更に実行する。

実施例１６は、実施例１―１５のいずれかの主題を含み、ネットワークフローハッシュルックアップモジュールは、更に、第２ルックアップを実行する前に、ネットワークパケットのヘッダのハッシュされた一部に対応するネットワークフローハッシュが第２レベルフローハッシュテーブル内に存在するか否かの確率を決定するべく、確率演算を実行することを更に含む。

実施例１７は、実施例１―１６のいずれかの主題を含み、ネットワークフローハッシュルックアップモジュールは、更に、ネットワークフローハッシュに対応するアクセス情報を更新する。

実施例１８は、実施例１―１７のいずれかの主題を含み、ネットワークフローハッシュに対応するアクセス情報を更新することは、アクセス頻度を提供するべく、ネットワークフローハッシュのアクセスカウンタをインクリメントすることを含む。

実施例１９は、実施例１―１８のいずれかの主題を含み、ネットワークフローハッシュに対応するアクセス情報を更新することは、更に、ネットワークフローハッシュのアクセスカウンタのインクリメントされた最後の時間の指標を提供するべく、ネットワークフローハッシュのタイムスタンプを更新することを含む。

実施例２０は、ネットワークフローに対応するネットワークフローハッシュの格納位置を管理するための方法を含み、方法は、ネットワークデバイスが、ネットワークコントローラからネットワークフロー及びネットワークフローに対応する優先度を受信する段階と、ネットワークデバイスが、ネットワークデバイスのメインメモリ内のネットワークフローテーブルにネットワークフローを格納する段階と、ネットワークデバイスがネットワークフローに対応するネットワークフローハッシュを生成する段階と、ネットワークデバイスが、ネットワークコントローラから受信される優先度に基づいてマルチレベルフローハッシュテーブルの第１レベルフローハッシュテーブル又は第２レベルフローハッシュテーブルの一方にネットワークフローに対応するネットワークフローハッシュを格納する段階とを含み、第１レベルフローハッシュテーブルは、ネットワークデバイスのプロセッサのためのキャッシュに格納され、第２レベルフローハッシュテーブルの少なくとも一部は、キャッシュに格納される。

実施例２１は、実施例２０の主題を含み、第１レベル及び第２レベルフローハッシュテーブルの各々は、ネットワークフローテーブルに格納される複数のネットワークフローに対応する複数のネットワークフローハッシュエントリーを含む。

実施例２２は、実施例２０及び２１のいずれかの主題を含み、ネットワークフローハッシュを格納する段階は、ネットワークフローハッシュに対応する優先度が第１レベルフローハッシュテーブルに現在格納されている他のネットワークフローハッシュに対応する優先度より高いとの決定に応じて、第１レベルフローハッシュテーブルにネットワークフローハッシュを格納する段階を含む。

実施例２３は、実施例２０―２２のいずれかの主題を含み、更に、ネットワークフローハッシュに対応する優先度が他のネットワークフローハッシュに対応する優先度より高いとの決定に応じて、ネットワークデバイスが、第２レベルフローハッシュテーブルに他のネットワークフローハッシュを追い出す段階を含む。

実施例２４は、実施例２０―２３のいずれかの主題を含み、ネットワークフローハッシュを格納する段階は、ネットワークフローハッシュのアクセスの頻度が第１レベルフローハッシュテーブルに現在格納されている他のネットワークフローハッシュのアクセスの頻度より高いとの決定の後に、第１レベルフローハッシュテーブルにネットワークフローハッシュを格納する段階を含む。

実施例２５は、実施例２０―２４のいずれかの主題を含み、第２レベルフローハッシュテーブルの他の一部は、ネットワークデバイスのメインメモリに格納される。

実施例２６は、実施例２０―２５のいずれかの主題を含み、ネットワークフローハッシュを格納する段階は、ネットワークフローハッシュに対応する優先度が第１レベルフローハッシュテーブルに現在格納されているネットワークフローハッシュの優先度より低く、かつ、ネットワークフローハッシュのアクセス頻度がプロセッサのキャッシュに格納される第２レベルフローハッシュテーブルの一部に現在格納されている他のネットワークフローハッシュのアクセス頻度より高いと決定することに応じて、プロセッサのキャッシュに格納された第２レベルフローハッシュテーブルの一部にネットワークフローハッシュを格納する段階を含む。

実施例２７は、実施例２０―２６のいずれかの主題を含み、更に、ネットワークデバイスが、ネットワークコントローラから受信される優先度に基づいてキャッシュ内のネットワークフローに対応するネットワークフローハッシュをロックする段階を含む。

実施例２８は、実施例２０―２７のいずれかの主題を含み、キャッシュは、複数のキャッシュラインを含み、各キャッシュラインは、ネットワークフローハッシュを収容可能であり、キャッシュ内のネットワークフローハッシュをロックする段階は、ネットワークコントローラから受信される優先度に基づいてネットワークフローハッシュに対応するキャッシュラインのビットを設定する段階を含む。

実施例２９は、実施例２０―２８のいずれかの主題を含み、キャッシュラインのビットを設定する段階は、キャッシュラインのエイジビットを設定する段階を含む。

実施例３０は、実施例２０―２９のいずれかの主題を含み、キャッシュラインのビットを設定する段階は、キャッシュラインの追い出しインジケータビットを設定する段階を含む。

実施例３１は、実施例２０―３０のいずれかの主題を含み、更に、ネットワークデバイスが、ネットワークデバイスにより受信されるネットワークパケットのヘッダの少なくとも一部をハッシュする段階と、ネットワークデバイスが、マルチレベルフローハッシュテーブルの第１レベルフローハッシュテーブルでネットワークパケットのヘッダのハッシュされた一部について第１ルックアップを実行する段階とを含む。

実施例３２は、実施例２０―３１のいずれかの主題を含み、更に、ネットワークデバイスが第１レベルフローハッシュテーブルで失敗した第１ルックアップの後に、第２レベルフローハッシュテーブルでネットワークパケットのヘッダのハッシュされた一部について第２ルックアップを実行する段階を含む。

実施例３３は、実施例２０―３２のいずれかの主題を含み、更に、第２ルックアップを実行する前に、ネットワークパケットのヘッダのハッシュされた一部に対応するネットワークフローハッシュが第２レベルフローハッシュテーブルに存在するか否かの確率を決定するべく、ネットワークデバイスが確率演算を実行する段階を含む。

実施例３４は、実施例２０―３３のいずれかの主題を含み、更に、ネットワークデバイスがネットワークフローハッシュに対応するアクセス情報を更新する段階を含む。

実施例３５は、実施例２０―３４のいずれかの主題を含み、ネットワークフローハッシュに対応するアクセス情報を更新する段階は、アクセス頻度を提供するべく、ネットワークフローハッシュのアクセスカウンタをインクリメントする段階を含む。

実施例３６は、実施例２０―３５のいずれかの主題を含み、ネットワークフローハッシュに対応するアクセス情報を更新する段階は、ネットワークフローハッシュの前回のアクセスカウンタの指標がインクリメントされたことを提供するべく、ネットワークフローハッシュのタイムスタンプを更新する段階を更に含む。

実施例３７は、プロセッサを有するネットワークデバイスと、プロセッサにより実行されたときに、実施例２０―３６のいずれかの方法をネットワークデバイスに実行させる複数の命令を格納したメモリとを含む。

実施例３８は、実施例２０―３６のいずれかの方法を実行するネットワークデバイスで実行される結果に応じて、そこに格納される複数の命令を有する１又は複数の機械可読記憶媒体を含む。

実施例３９は、ネットワークフローに対応するネットワークフローハッシュの格納位置を管理するためのコンピューティングデバイスを含み、コンピューティングデバイスは、ネットワークコントローラからネットワークフロー及びネットワークフローに対応する優先度を受信する手段と、ネットワークデバイスのメインメモリ内のネットワークフローテーブルにネットワークフローを格納する手段と、ネットワークフローに対応するネットワークフローハッシュを生成する手段と、ネットワークコントローラから受信される優先度に基づいて、マルチレベルフローハッシュテーブルの第１レベルフローハッシュテーブル又は第２レベルフローハッシュテーブルの一方に、ネットワークフローに対応するネットワークフローハッシュを格納する手段とを備え、第１レベルフローハッシュテーブルは、ネットワークデバイスのプロセッサのためのキャッシュに格納され、第２レベルフローハッシュテーブルの少なくとも一部は、キャッシュに格納される。

実施例４０は、実施例３９の主題を含み、第１レベル及び第２レベルフローハッシュテーブルの各々は、ネットワークフローテーブルに格納される複数のネットワークフローに対応する複数のネットワークフローハッシュエントリーを含む。

実施例４１は、実施例３９及び４０のいずれかの主題を含み、ネットワークフローハッシュを格納する手段は、ネットワークフローハッシュに対応する優先度が第１レベルフローハッシュテーブルに現在格納されている他のネットワークフローハッシュに対応する優先度より高いとの決定に応じて、第１レベルフローハッシュテーブルにネットワークフローハッシュを格納する手段を含む。

実施例４２は、実施例３９―４１のいずれかの主題を含み、更に、ネットワークフローハッシュに対応する優先度が他のネットワークフローハッシュに対応する優先度より高いとの決定に応じて、第２レベルフローハッシュテーブルに他のネットワークフローハッシュを追い出す手段を含む。

実施例４３は、実施例３９―４２のいずれかの主題を含み、ネットワークフローハッシュを格納する手段は、ネットワークフローハッシュのアクセスの頻度が第１レベルフローハッシュテーブルに現在格納されている他のネットワークフローハッシュのアクセスの頻度より高いとの決定の後に、第１レベルフローハッシュテーブルにネットワークフローハッシュを格納する手段を含む。

実施例４４は、実施例３９―４３のいずれかの主題を含み、第２レベルフローハッシュテーブルの他の一部は、ネットワークデバイスのメインメモリに格納される。

実施例４５は、実施例３９―４４のいずれかの主題を含み、ネットワークフローハッシュを格納する手段は、ネットワークフローハッシュに対応する優先度が第１レベルフローハッシュテーブルに現在格納されているネットワークフローハッシュの優先度より低く、かつ、ネットワークフローハッシュのアクセス頻度がキャッシュに格納される第２レベルフローハッシュテーブルの一部に現在格納されている他のネットワークフローハッシュのアクセス頻度より高いと決定することに応じてキャッシュに格納される第２レベルフローハッシュテーブルの一部にネットワークフローハッシュを格納する手段を含む。

実施例４６は、実施例３９―４５のいずれかの主題を含み、更に、ネットワークコントローラから受信される優先度に基づいてキャッシュ内のネットワークフローに対応するネットワークフローハッシュをロックする手段を含む。

実施例４７は、実施例３９―４６のいずれかの主題を含み、キャッシュは、複数のキャッシュラインを含み、各キャッシュラインは、ネットワークフローハッシュを収容可能であり、キャッシュ内のネットワークフローハッシュをロックする手段は、ネットワークコントローラから受信される優先度に基づいてネットワークフローハッシュに対応するキャッシュラインのビットを設定する手段を含む。

実施例４８は、実施例３９―４７のいずれかの主題を含み、キャッシュラインのビットを設定する手段は、キャッシュラインのエイジビットを設定する手段を含む。

実施例４９は、実施例３９―４８のいずれかの主題を含み、キャッシュラインのビットを設定する手段は、キャッシュラインの追い出しインジケータビットを設定する手段を含む。

実施例５０は、実施例３９―４９のいずれかの主題を含み、更に、ネットワークデバイスにより受信されるネットワークパケットのヘッダの少なくとも一部をハッシュする手段と、マルチレベルフローハッシュテーブルの第１レベルフローハッシュテーブルでネットワークパケットのヘッダのハッシュされた一部について第１ルックアップを実行する手段とを含む。

実施例５１は、実施例３９―５０のいずれかの主題を含み、更に、第１レベルフローハッシュテーブルで第１ルックアップが失敗した後に、第２レベルフローハッシュテーブルでネットワークパケットのヘッダのハッシュされた一部について第２ルックアップを実行する手段を含む。

実施例５２は、実施例３９―５１のいずれかの主題を含み、更に、第２ルックアップの実行の前に、ネットワークパケットのヘッダのハッシュされた一部に対応するネットワークフローハッシュが第２レベルフローハッシュテーブル内に存在するか否かの確率を決定するべく、確率演算を実行する手段を含む。

実施例５３は、実施例３９―５２のいずれかの主題を含み、更に、ネットワークフローハッシュに対応するアクセス情報を更新する手段を含む。

実施例５４は、実施例３９―５３のいずれかの主題を含み、ネットワークフローハッシュに対応するアクセス情報を更新する手段は、アクセス頻度を提供するべく、ネットワークフローハッシュのアクセスカウンタをインクリメントする手段を含む。

実施例５５は、実施例３９―５４のいずかの主題を含み、ネットワークフローハッシュに対応するアクセス情報を更新する手段は、更に、ネットワークフローハッシュの前回のアクセスカウンタの指標がインクリメントされたことを提供するべく、ネットワークフローハッシュのタイムスタンプを更新する手段を含む。

Claims (26)

1. ネットワークフローに対応するネットワークフローハッシュの格納位置管理のためのネットワークデバイスであって、
   前記ネットワークデバイスのプロセッサのためのキャッシュと、
   前記キャッシュとは異なるメインメモリと、
   前記ネットワークフローを含む前記メインメモリに格納されるネットワークフローテーブルと、
   複数のフローハッシュテーブルを含むマルチレベルフローハッシュテーブルであって、前記複数のフローハッシュテーブルが、前記キャッシュに格納される第１レベルフローハッシュテーブル、及び、第２レベルフローハッシュテーブルを含み、前記第２レベルフローハッシュテーブルの少なくとも一部が前記キャッシュに格納される、マルチレベルフローハッシュテーブルと、
   前記ネットワークデバイスに通信可能に連結されるネットワークコントローラから前記ネットワークフローに対応する優先度を受信し、受信した前記優先度に基づいて前記第１レベル又は第２レベルフローハッシュテーブルのいずれかに、前記ネットワークフローに対応する前記ネットワークフローハッシュを格納するネットワークフローハッシュテーブル管理モジュールと
   を備える、ネットワークデバイス。
2. 前記第１レベル及び第２レベルフローハッシュテーブルの各々は、複数のネットワークフローハッシュを含み、前記複数のネットワークフローハッシュの各々は、前記ネットワークフローテーブル内の複数の前記ネットワークフローのうちの１つのネットワークフローに対応する、請求項１に記載のネットワークデバイス。
3. 前記第１レベル又は第２レベルフローハッシュテーブルのいずれかに、前記ネットワークフローに対応する前記ネットワークフローハッシュを格納することは、前記ネットワークフローハッシュに対応する優先度が前記第１レベルフローハッシュテーブルに現在格納されている他のネットワークフローハッシュに対応する優先度より高いという決定に応じて、前記第１レベルフローハッシュテーブルに前記ネットワークフローハッシュを格納すること含み、
   前記ネットワークフローハッシュテーブル管理モジュールは、更に、前記ネットワークフローハッシュに対応する前記優先度が前記他のネットワークフローハッシュに対応する前記優先度より高いという前記決定に応じて、前記第２レベルフローハッシュテーブルへ前記他のネットワークフローハッシュを追い出す、請求項１又は２に記載のネットワークデバイス。
4. 前記第１レベル又は第２レベルフローハッシュテーブルのいずれかに、前記ネットワークフローに対応する前記ネットワークフローハッシュを格納することは、前記ネットワークフローハッシュのアクセスの頻度が前記第１レベルフローハッシュテーブルに現在格納されている他のネットワークフローハッシュのアクセスの頻度より高いという決定に応じて、前記第１レベルフローハッシュテーブルに前記ネットワークフローハッシュを格納することを含む、請求項１から３のいずれか一項に記載のネットワークデバイス。
5. 前記第１レベル又は第２レベルフローハッシュテーブルのいずれかに、前記ネットワークフローに対応する前記ネットワークフローハッシュを格納することは、前記ネットワークフローハッシュのアクセス頻度が前記第１レベルフローハッシュテーブルに現在格納されている他のネットワークフローハッシュのアクセス頻度より高いという決定に応じて、前記第１レベルフローハッシュテーブルに前記ネットワークフローハッシュを格納することを含む、請求項１から３のいずれか一項に記載のネットワークデバイス。
6. 前記第２レベルフローハッシュテーブルの他の一部は、前記ネットワークデバイスの前記メインメモリに格納される、請求項１から５のいずれか一項に記載のネットワークデバイス。
7. 前記第１又は第２レベルフローハッシュテーブルのいずれかに、前記ネットワークフローに対応する前記ネットワークフローハッシュを格納することは、前記ネットワークフローハッシュに対応する優先度が前記第１レベルフローハッシュテーブルに現在格納されている複数の他のネットワークフローハッシュの複数の優先度より低い、かつ、前記ネットワークフローハッシュに対応するアクセス頻度が前記キャッシュに格納される前記第２レベルフローハッシュテーブルの前記一部に現在格納されている前記複数の他のネットワークフローハッシュの複数のアクセス頻度より高いという決定に応じて、前記キャッシュに格納される前記第２レベルフローハッシュテーブルの前記一部に前記ネットワークフローハッシュを格納することを含む、請求項１から６のいずれか一項に記載のネットワークデバイス。
8. 前記ネットワークフローハッシュテーブル管理モジュールは、更に、前記ネットワークコントローラから受信される前記優先度に基づいてキャッシュ内の前記ネットワークフローに対応する前記ネットワークフローハッシュをロックし、
   前記キャッシュは、複数のキャッシュラインを含み、各キャッシュラインは、前記ネットワークフローハッシュを収容可能であり、
   キャッシュ内の前記ネットワークフローハッシュをロックすることは、前記ネットワークコントローラから受信される前記優先度に基づいて前記ネットワークフローハッシュに対応するキャッシュラインのビットを設定することを含む、請求項１から７のいずれか一項に記載のネットワークデバイス。
9. 前記キャッシュラインの前記ビットを設定することは、前記キャッシュラインのエイジビット及び追い出しインジケータビットのうちの少なくとも１つを設定することを含む、請求項８に記載のネットワークデバイス。
10. 前記ネットワークデバイスにより受信されるネットワークパケットのヘッダの少なくとも一部をハッシュして、前記マルチレベルフローハッシュテーブルの前記第１レベルフローハッシュテーブルで前記ネットワークパケットの前記ヘッダのハッシュされた前記一部のための第１ルックアップを実行し、前記第１レベルフローハッシュテーブルで失敗した第１ルックアップの後に、前記第２レベルフローハッシュテーブルで前記ネットワークパケットの前記ヘッダのハッシュされた前記一部のための第２ルックアップを実行するネットワークフローハッシュルックアップモジュールを更に備える、請求項１から９のいずれか一項に記載のネットワークデバイス。
11. 前記ネットワークフローハッシュルックアップモジュールは、前記ネットワークパケットの前記ヘッダのハッシュされた前記一部に対応する前記ネットワークフローハッシュが前記第２ルックアップを実行する前に、前記第２レベルフローハッシュテーブルが存在するか否かの確率を決定するべく、確率演算を更に実行する、請求項１０に記載のネットワークデバイス。
12. 前記ネットワークフローハッシュルックアップモジュールは、更に、前記ネットワークフローハッシュに対応するアクセス情報を更新する、請求項１０又は１１に記載のネットワークデバイス。
13. 前記ネットワークフローハッシュに対応する前記アクセス情報を更新することは、アクセス頻度を提供するべく、前記ネットワークフローハッシュのアクセスカウンタをインクリメントすることを含む、請求項１２に記載のネットワークデバイス。
14. 複数のネットワークフローに対応する複数のネットワークフローハッシュの複数の格納位置を管理するための方法であって、
    ネットワークデバイスが、ネットワークフロー及び前記ネットワークフローに対応する優先度をネットワークコントローラから受信する段階と、
    前記ネットワークデバイスが、前記ネットワークデバイスのメインメモリ内のネットワークフローテーブルに前記ネットワークフローを格納する段階と、
    前記ネットワークデバイスが、前記ネットワークフローに対応するネットワークフローハッシュを生成する段階と、
    前記ネットワークデバイスが、前記ネットワークコントローラから受信される前記優先度に基づいてマルチレベルフローハッシュテーブルの第１レベルフローハッシュテーブル又は第２レベルフローハッシュテーブルの一方に、前記ネットワークフローに対応する前記ネットワークフローハッシュを格納する段階と
    を備え、
    前記第１レベルフローハッシュテーブルは、前記ネットワークデバイスのプロセッサ用のキャッシュに格納され、前記第２レベルフローハッシュテーブルの少なくとも一部は、前記キャッシュに格納される、方法。
15. 前記ネットワークフローハッシュを格納する段階は、前記ネットワークフローハッシュに対応する優先度が、前記第１レベルフローハッシュテーブルに現在格納されている他のネットワークフローハッシュに対応する優先度より高いという決定に応じて、前記第１レベルフローハッシュテーブルに前記ネットワークフローハッシュを格納する段階を含む、請求項１４に記載の方法。
16. 前記ネットワークデバイスが、前記ネットワークフローハッシュに対応する前記優先度が、他のネットワークフローハッシュに対応する前記優先度より高いという前記決定に応じて、前記第２レベルフローハッシュテーブルへ前記他のネットワークフローハッシュを追い出す段階を更に備える、請求項１５に記載の方法。
17. 前記ネットワークフローハッシュを格納する段階は、前記ネットワークフローハッシュのアクセスの頻度が前記第１レベルフローハッシュテーブルに現在格納されている他のネットワークフローハッシュのアクセスの頻度より高いことを決定する段階の後に、前記第１レベルフローハッシュテーブルに前記ネットワークフローハッシュを格納する段階を含む、請求項１４から１６のいずれか一項に記載の方法。
18. 前記ネットワークフローハッシュを格納する段階は、前記ネットワークフローハッシュに対応する優先度が、前記第１レベルフローハッシュテーブルに現在格納されている前記ネットワークフローハッシュの複数の優先度より低い、かつ、前記ネットワークフローハッシュのアクセス頻度が、前記プロセッサの前記キャッシュに格納される前記第２レベルフローハッシュテーブルの前記一部に現在格納されている複数の他のネットワークフローハッシュの複数のアクセス頻度より高いことを決定する段階に応じて、前記キャッシュに格納される前記第２レベルフローハッシュテーブルの前記一部に前記ネットワークフローハッシュを格納する段階を含む、請求項１４から１７のいずれか一項に記載の方法。
19. 前記ネットワークデバイスが、前記ネットワークコントローラから受信される前記優先度に基づいて、キャッシュ内の前記ネットワークフローに対応する前記ネットワークフローハッシュをロックする段階
    を更に備え、
    前記キャッシュは、複数のキャッシュラインを含み、各キャッシュラインは、前記ネットワークフローハッシュに収容可能であり、
    キャッシュ内の前記ネットワークフローハッシュをロックする段階は、前記ネットワークコントローラから受信される前記優先度に基づいて前記ネットワークフローハッシュに対応するキャッシュラインのビットを設定する段階を含む、請求項１４から１８のいずれか一項に記載の方法。
20. 前記ネットワークデバイスが、前記ネットワークデバイスにより受信されるネットワークパケットのヘッダの少なくとも一部をハッシュする段階と、
    前記ネットワークデバイスが、前記マルチレベルフローハッシュテーブルの前記第１レベルフローハッシュテーブルで前記ネットワークパケットの前記ヘッダのハッシュされた前記一部のための第１ルックアップを実行する段階と、
    前記ネットワークデバイスが、前記第１レベルフローハッシュテーブルで失敗した第１ルックアップの後に、前記第２レベルフローハッシュテーブルで前記ネットワークパケットの前記ヘッダのハッシュされた前記一部のための第２ルックアップを実行する段階と
    を更に備える、請求項１４から１９のいずれか一項に記載の方法。
21. 前記ネットワークデバイスが、前記第２ルックアップを実行する前に、前記ネットワークパケットの前記ヘッダの前記ハッシュされた一部に対応する前記ネットワークフローハッシュが前記第２レベルフローハッシュテーブル内に存在するか否かの確率を決定するべく、確率演算を実行する段階を更に備える、請求項２０に記載の方法。
22. アクセス頻度を提供するべく、前記ネットワークフローハッシュのアクセスカウンタをインクリメントする段階を更に備える、請求項１４から２１のいずれか一項に記載の方法。
23. 前記ネットワークフローハッシュのアクセスカウンタがインクリメントされた最後の時間の指標を提供するべく、前記ネットワークフローハッシュのタイムスタンプを更新する段階を更に備える、請求項２２に記載の方法。
24. プロセッサと、
    前記プロセッサにより実行されるときに、請求項１４から２３のいずれか一項に記載の方法を前記ネットワークデバイスに実行させる複数の命令をその中に格納したメモリと
    を備える、ネットワークデバイス。
25. プロセッサに、請求項１４から２３のいずれか一項に記載の方法を実行させるためのプログラム。
26. 請求項２５に記載のプログラムを格納するコンピュータ可読媒体。

Images