(57)【特許請求の範囲】
【請求項１】
複数のキューを有するネットワークインタフェースカード（ＮＩＣ）を有する電子装置における、前記キューを管理する方法であって、
前記ＮＩＣへの、又はＮＩＣからのデータトラフィックを監視するステップと、
前記監視に基づいて、前記キューの第１セットを介するデータトラフィックを管理するための第１の基準セットを有する第１プールを指定し、且つ当該第１プールに前記キューの前記第１セットを割り当てるステップと、
前記第１の基準セットに基づいて、前記データトラフィックの第１サブセットをキューの前記第１セットに向けるステップと、
前記監視に基づいて、前記キューの第２セットを介するデータトラフィックを管理するための第２の基準セットを有する第２プールを指定し、且つ当該第２プールに前記キューの前記第２セットを割り当て、前記第２の基準セットは前記第１の基準セットと異なるステップと、
前記第２の基準セットに基づいて、前記データトラフィックの第２サブセットをキューの前記第２セットに向けるステップと、
を備えることを特徴とする方法。
【請求項２】
特定のプールの各々の基準セットは、前記特定のプールの各キューを通過するための最大閾値データトラフィック量を指定し、
前記第１の基準セットは、前記第２の基準セットと異なる最大閾値を指定し、
前記方法は、
特定のプール内の少なくともキューのサブセットを介するデータトラフィックが前記最大閾値量を上回る場合、前記特定のプールのキューのセットに新しいキューを割り当てるステップを更に備えることを特徴とする請求項１に記載の方法。
【請求項３】
前記特定のプールの前記キューのサブセットは、前記特定のプールのキューのセット内の全てのキューを含むことを特徴とする請求項２に記載の方法。
【請求項４】
前記特定のプールの前記キューのサブセットは、前記特定のプールのキューのセット内の全てのキューを含まないことを特徴とする請求項２に記載の方法。
【請求項５】
特定のプールの各々の基準セットは、前記特定のプールの各キューを通過するための最小閾値データトラフィック量を指定し、
前記第１の基準セットは前記第２の基準セットと異なる最小閾値を指定し、
前記方法は、
特定のキューを介するデータトラフィックがある期間の間前記最小閾値量を下回る場合、特定のプールのキューのセットから前記特定のキューを除去するステップを更に備えることを特徴とする請求項１に記載の方法。
【請求項６】
特定のプールの各々の基準セットは、前記特定のプールの各キューを通過するためのデータトラフィックの閾値量を指定し、
前記第１の基準セットは、最大閾値量を指定するが最小閾値量を指定せず、前記第２の基準セットは、最小閾値量を指定するが最大閾値量を指定しないことを特徴とする請求項１に記載の方法。
【請求項７】
データトラフィックを監視するステップは、前記電子装置上で実行するアドレス指定可能なノードに関連付けられるデータトラフィックを監視するステップを含むことを特徴とする請求項１に記載の方法。
【請求項８】
前記データトラフィックの前記第１サブセットおよび前記第２サブセットを向けるステップは、前記キューの前記第１および前記第２セットをそれぞれ介して前記データトラフィックの前記第１サブセットおよび前記第２サブセットをルーティングする前記ＮＩＣ内のフィルタセットを指定するステップを含み、
前記フィルタセットは、前記キューのセットを介する前記データトラフィックの前記第１サブセットおよび第２サブセットを前記電子装置上で実行するアドレス指定可能宛先ノードのセットにルーティングすることを特徴とする請求項１に記載の方法。
【請求項９】
前記データトラフィックの前記第１サブセットおよび前記第２サブセットを向けるステップは、前記データトラフィックの前記第１サブセットおよび第２サブセットを前記電子装置上で実行するアドレス指定可能送信元ノードのセットから前記キューの第１および第２セットを介して前記電子装置の外部にルーティングするフィルタセットを指定するステップを含むことを特徴とする請求項１に記載の方法。
【請求項１０】
前記監視するステップ、前記指定するステップ及び前記向けるステップは、複数の異なる仮想モジュール間で前記電子装置上のネットワーキングリソースのセットを共有するネットワーク仮想化レイヤにより実行される動作であり、
前記フィルタセットは、異なる仮想モジュールからのデータトラフィックを前記複数のキューにおける異なるキューに割り当てるために前記ネットワーク仮想化レイヤにおいて定義されることを特徴とする請求項９に記載の方法。
【請求項１１】
請求項１乃至１０のいずれか１項に記載の方法に記載の動作を実行するための命令を含むプログラムを格納したマシン読み取り可能な媒体。
【請求項１２】
ネットワークインターフェース（ＮＩＣ）を介したデータトラフィックを一時的に記憶するための複数のキューを有する当該ＮＩＣを含む電子装置における前記キューを管理する方法であって、
データトラフィックのサブセットをキューのセットに割り当てるステップと、
前記キューのセットを介してデータトラフィックのサブセットを監視するステップと、
当該監視に基づき、前記キューのセットの少なくともサブセットを介したデータトラフィックが最大閾値量を超えているとき、前記キューのセットに新たなキューを割り当てることにより、前記キューのセットを変更するステップと
を備えることを特徴とする方法。
【請求項１３】
前記キューのセットを変更するステップは、前記キューのセットの少なくともサブセットを介したデータトラフィックが、或る期間、最大閾値量を超えているとき、前記キューのセットに新たなキューを割り当てるステップを含むことを特徴とする請求項１２に記載の方法。
【請求項１４】
前記キューのセットを変更するステップは、特定のキューを介したデータトラフィックが最小閾値量を下回っているとき、前記キューのセットから前記特定のキューを除去するステップを含むことを特徴とする請求項１２に記載の方法。
【請求項１５】
前記キューのセットを変更するステップは、特定のキューを介したデータトラフィックが或る期間、最小閾値量を下回っているとき、前記キューのセットから前記特定のキューを除去するステップを含むことを特徴とする請求項１２に記載の方法。
【請求項１６】
前記データトラフィックを監視するステップは、前記電子装置上で実行するアドレス指定可能なノードに関連付けられるデータトラフィックを監視するステップを含むことを特徴とする請求項１２に記載の方法。
【請求項１７】
前記データトラフィックのサブセットを割り当てるステップは、前記キューのセットにデータトラフィックのサブセットが向くようにするステップを含むことを特徴とする請求項１２に記載の方法。
【請求項１８】
前記データトラフィックのサブセットを向けるステップは、前記ＮＩＣにおけるフィルタセットを指定して、前記キューのセットを介して前記データトラフィックのサブセットを、前記電子装置上で実行するアドレス指定可能な目標ノードのセットにルーティングするステップを含むことを特徴とする請求項１７に記載の方法。
【請求項１９】
前記データトラフィックのサブセットを向けるステップは、前記データトラフィックのサブセットを前記電子装置上で実行するアドレス指定可能送信元ノードのセットから前記キューのセットを介して前記電子装置の外部にルーティングするフィルタセットを指定するステップを含むことを特徴とする請求項１７に記載の方法。
【請求項２０】
前記割り当てるステップ、向けるステップ、監視するステップ、および、変更するステップは、複数の異なる仮想化モジュール間で、前記電子器装置上のネットワークを行うリソースのセットを共有するネットワーク仮想化レイヤにより実行される、
ここで、前記フィルタセットは、異なる仮想化モジュールからのデータトラフィックを前記複数のキューにおける異なるキューに割り当てるように、前記ネットワーク仮想化レイヤ内で定義されれることを特徴とする請求項１９に記載の方法。
【請求項２１】
請求項１２乃至２０のいずれか１項に記載の方法におけるステップを実行させるため命令を含むプログラムを記憶したマシン読み取り可能な媒体。
【請求項２２】
ネットワークインターフェース（ＮＩＣ）を介したデータトラフィックを一時的に記憶するための複数のキューを有する当該ＮＩＣを含む電子装置における前記キューを管理する方法であって、
データトラフィックのセブセットを第１のキューに割り当てるステップと、
前記第１のキューを介して前記データトラフィックのサブセットを監視するステップと、
当該監視に基づき、前記データトラフィックのサブセットを、第２のキューに再割り当てするステップと
を備え、
前記データトラフィックのサブセットを監視するステップは、前記データトラフィックのサブセットが最大閾値を超えているかどうか、または最小閾値を下回るかどうかを判定することを含む、
ことを特徴とする方法。
【請求項２３】
前記電子装置上では複数のアドレス指定可能なノードが実行され、
前記データトラフィックのサブセットは、第１のアドレス指定可能なノードに関連づけられたデータトラフィックを含む
ことを特徴とする請求項２２に記載の方法。
【請求項２４】
前記アドレス指定可能なノードは複数の仮想マシン（ＶＭ）であって、前記第１のアドレス指定可能なノードは或るＶＭであることを特徴とする請求項２３に記載の方法。
【請求項２５】
前記アドレス指定可能なノードは、ハイパーバイザカーネルネットワークインタフェースを更に有することを特徴とする請求項２４に記載の方法。
【請求項２６】
前記アドレス指定可能なノードは、前記電子装置のストレージ上の外部ストレージの少なくも一部をマウントするモジュールを有する、
ここで、前記マウントされる一部は前記電子装置上で実行されるＶＭによってアクセスするためである、
ことを特徴とする請求項２４に記載の方法。
【請求項２７】
前記アドレス指定可能なノードは、移動可能なＶＭのモジュールを含むことを特徴とする請求項２４に記載の方法。
【請求項２８】
前記データトラフィックのサブセットは、特定のタイプのデータトラフィックを含む
ことを特徴とする請求項２２に記載の方法。
【請求項２９】
データタプルのセットを含むパケットヘッダを有するデータパケットを受信するステップと、
前記パケットヘッダにおけるデータタプルの検査することでデータパケットのタイプを判定するステップと
を更に有することを特徴とする請求項２８に記載の方法。
【請求項３０】
前記データパケットはレイヤ２（Ｌ２）パケットであって、
前記データタプルのセットはメディアアクセス制御（ＭＡＣ）のアドレスを含む
ことを特徴とする請求項２９に記載の方法。
【請求項３１】
前記データパケットはレイヤ３（Ｌ３）パケットであって、
前記データタプルのセットは、送信元ポート識別子、宛先ポート識別子、送信元インターネットプロトコル（ＩＰ）アドレス、宛先ＩＰアドレス及びプロトコルを含む
ことを特徴とする請求項２９に記載の方法。
【請求項３２】
前記特定のタイプはボイスオーバーインターネットプロトコル（ＩＰ）データ、ビデオデータ、オーディオデータ、リモートデスクトップパケット、管理パケット、電子メールパケットの１つを含む
ことを特徴とする請求項２８に記載の方法。
【請求項３３】
前記第２のキューは、データトラフィックの他のセブセットに前回割り当てたキューであることを特徴とする請求項２２に記載の方法。
【請求項３４】
前記第１のキューを介したデータトラフィックは、データトラフィックのサブセットのみではなく、他のデータトラフィックを含み、
前記第２のキューは、データトラフィックの他のサブセットに割り当てたキューである
ことを特徴とする請求項２２に記載の方法。
【請求項３５】
キューの第１のプールを指定し、前記第１のキューを、キューのデフォルトの第２のプールから前記第１のプールに割り当てるステップと、
前記第１のキューを介したデータトラフィックがトラフィックの最大閾値量を超えたことを検出したことに応じて、前記デフォルトの第２のプールから前記第１のプールに第２のキューを割り当てるステップと
を有することを特徴とする請求項２２に記載の方法。
【請求項３６】
前記監視するステップは、前記第２のキューを介したデータトラフィックが前記第２のキューに対するトラフィックの最大閾値量を超えないことを検出するステップを更に有することを特徴とする請求項２２に記載の方法。
【請求項３７】
請求項２２乃至３６のいずれか１項に記載の方法のステップを実行するための命令を含む、マシン読み取り可能な媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、トラフィック及び負荷を認識する動的なキュー管理に関する。
【背景技術】
【０００２】
ここ数年、複数のキューを有するネットワークインタフェースカード（ＮＩＣ）を介するホストとの間の入出力トラフィックを分散するために、キュー管理システムが提案されてきた。図１は、そのようなシステムの１つを示す。詳細には、図１は、（１）ホストコンピュータ（不図示）上で実行する複数の仮想マシン（ＶＭ）１０２及び（２）複数のキューを有するＮＩＣ１００を示す。図１に示すように、各キューは、入力トラフィックを処理するための受信側バッファセット１０４と、出力トラフィックを処理するための送信側バッファセット１０６とを有する。システムは、デフォルトキュー１０５、複数の非デフォルトキュー１１５、ＬＲＯ（大量受信オフロード）キュー１２０及びＲＳＳ（受信側スケーリング）キュー１２５の４種類のキューを有する。後者の２種類のキューは、ＮＩＣによりサポートされる特定のハードウェアＬＲＯ及びＲＳＳ機能性に結び付けられる特別なキューである。
【発明の概要】
【発明が解決しようとする課題】
【０００３】
図１のキュー管理システムは、仮想マシン（ＶＭ）との間のトラフィックを複数のキューに分散する。このシステムにおいて、全てのＶＭはデフォルトキュー１０５から開始する。ＶＭのトラフィックが所定の閾値を上回ると、ＶＭはデフォルトキューから非デフォルトキュー１１５に移動される。この実現例は、ＶＭをデフォルトキューから移動する場合、ＶＭの要件に関係なく、負荷が最も少ない非デフォルトキューにＶＭを移動する。これにより、３つの大きな問題が生じる。
【０００４】
第１に、現在における実現例ではＶＭのトラフィックの種類を考慮せずに非デフォルトキューを選択するため、特定の要件を有するＶＭが他のＶＭにより妨害される場合がある。例えば待ち時間感度（latency-sensitive)のトラフィックを送受信する特定のＶＭが、待ち時間感度が低く且つ高スループットの仕事量を実行する複数の他のＶＭと同一のキューを共有する場合、前記特定のＶＭの待ち時間及びジッタは確実に影響を受ける。図１のキュー１５０は、短待ち時間を必要とする（ＬＬＲ；low latency required）ＶＭ１５２、及び、複数の、長待ち時間に耐えられる（ＨＬＴ;high latency tolerating）ＶＭの双方に対するトラフィックを有する過負荷状態のキューの例である。この状況では、ＬＬＲ  ＶＭ１５２は、種々のＨＬＴ  ＶＭのトラフィックのため、許容可能な最大待ち時間内にトラフィックを送受信できないことが起こり得る。
【０００５】
この実現例の第２の問題は、この実現例が非デフォルトキュー１１５、ＬＲＯ（大量受信オフロード）キュー１２０及びＲＳＳ（受信側スケーリング）キュー１２５であるキューの３つの異なる非デフォルトプールのうちの１つに固定数のキューを静的に割り当てることである。この手法において、各プールは、ドライバの初期化中に全てのキューを割り当てられる。デフォルトにより、プールが実際は使用されていない場合でも、各プールは同数のキューを取得する。その結果、あるプールがトラフィックを維持するために更なるキューを必要とする場合、システムに余裕がある場合でも、過負荷状態のプールは他のプールから未使用キューを取得することができず処理能力を増加できないため、性能の問題が生じる。
第３の問題は、ＶＭに対するキューの割り当てが１回限りであること、すなわち、一度ＶＭがキューに移動すると、別の非デフォルトキューには移動されないことである。これにより２つの問題が生じる。第１に、割り当てが１回限りであるため、後にＶＭがトラフィックを増加するために更なるリソースを必要とする場合、現在のキューを使用していることで制限される結果になる。トラフィックが少なく処理に余裕のあるキューが存在する場合でも、従来の手法ではＶＭがこれを使用することはできない。更に、この手法は、トラフィックを提供するために必要なキューがそれ程多くない場合でも、全てのキューが使用中である状態を静的に維持しようとすることである。この手法ではキュー毎に専用のカーネルコンテキストが存在するため、不必要な数のキューがアクティブになると、アクティブなコンテキストが増加する。これらのアクティブなコンテキストは必然的に、割込み到着時に他のコンテキスト（ｖＣＰＵ等）を停止させる。従って、ホストはコンテキストを切り替えるために更なるサイクルを使用することになり、ＶＭの統合率を低下させる。
【課題を解決するための手段】
【０００６】
いくつかの実施形態は、ホスト上で実行する複数の仮想マシン（ＶＭ）との間のトラフィックを処理する複数のキューを効率的且つ動的に管理するキュー管理システムを提供する。本システムは、（１）優先度の高いプールが特定の種類のトラフィック又はＶＭ（例えば、短い待ち時間を必要とするＶＭに対するトラフィック）に対して確保される優先度の異なるプールにキューを分割することと、（２）各プール内のキューの数を動的に調整し（すなわち、プールのサイズを動的に調整し）、（３）１つ以上の最適化基準（例えば、キューが十分に使用されていない又は過剰に使用されている場合に関する基準）に基づいてＶＭを新しいキューに動的に再割り当てすることにより、キューを管理する。
【０００７】
いくつかの実施形態において、キュー管理システムは最初、新たに初期化されたＶＭを割り当てが行われていないデフォルトプール内に有する。ＶＭのトラフィックが事前に設定された閾値を上回る場合、システムはＶＭのトラフィック要件に一致するプールが存在するかを判定し、そのようなプールが存在する場合、ＶＭを当該プールに割り当てる。一致するプールが存在しない場合、システムは新しいプールを作成し、ＶＭを当該プールに割り当てる。新しいプールを作成するための未使用キューが存在しない場合、キュー管理システムは、１つ以上の割り当て済キュー（すなわち、先に作成されたプールに割り当てられたキュー）を優先的に使用し、新たに作成されたプールに優先的に使用されるキューを割り当てる。この優先的使用により、既存のプールの間でキューのバランスが再調整され、新しいプールのための１つ以上のキューが解放される。いくつかの実施形態において、プールにわたるバランス再調整処理は、プールの最小サイズ及び最大サイズ、プールの相対優先度等のリソース割り当て基準により制御可能である。
【０００８】
また、キュー管理システムは、関連付けられた管理スレッド（例えば、カーネルコンテキスト）のＣＰＵ負荷、トラフィックの種類、トラフィックの負荷、キューの他の実時間負荷計測値等の１つ以上の基準に基づいて、プール内のトラフィックのバランスを再調整できる。いくつかの実施形態において、システムは、異なるプールに対して異なるバランス再調整基準を使用する。例えばシステムは、いくつかのプールでは少数のキューにＶＭを集約し、他のプールでは可能な限り多くのキューにＶＭを分散したい場合がある。いくつかの実施形態において、キュー管理システムは、周期的に及び／又は特定のイベントにバランス再調整処理を実行する負荷バランス調整器を有する。
【０００９】
ＶＭのトラフィックが閾値を下回る場合、いくつかの実施形態のキュー管理システムは、ＶＭをデフォルトキューに戻す。ＶＭが非デフォルトプールにおいてキューを使用している最後のＶＭである場合、システムは、後でいずれかのプールに再割り当てできるように、最後に使用されたキューを未使用キューのプールに移動する。
【００１０】
ＶＭのデータトラフィックに加えて、又は、ＶＭのデータトラフィックの代わりに、いくつかの実施形態のキュー管理システムは、プールを動的に定義し、各プールを一意に管理し、プール内のキューを動的に変更し、ホスト上で実行する非ＶＭアドレス指定可能なノード（例えば、送信元エンドノード又は宛先エンドノード）との間のデータトラフィックを動的に再割り当てする。詳細には、いくつかの実施形態のシステムは、ホスト装置のＮＩＣを介して、ＶＭ及び／又は非ＶＭアドレス指定可能なノード（例えば、データのエンドノード）のセットに対するデータトラフィックを監視する。システムは、この監視に基づいて少なくともアドレス指定可能なノードのセットに対するプールを指定し、プールにキューのセットを割り当てる。その後、システムは、宛先又は送信元メディアアクセス制御（ＭＡＣ）フィルタ、あるいは５タプルフィルタリングを使用して、ホスト装置により受信又は送信される非ＶＭアドレス指定可能なノードのセットに対するデータトラフィックを割り当て済みのキューのセットに向ける。
【００１１】
その代わりに又はそれに加えて、いくつかの実施形態のシステムは、監視に基づいてＶＭ及び非ＶＭアドレス指定可能なノードのセットに対するプールに割り当てられたキューのセットを変更できる。上述のように、そのような変更の例は、プールのキューのうちの１つ以上が過剰に使用されるか又は十分に使用されない場合にプールにキューを追加するか又はプールからキューを除去することを含む。いくつかの実施形態において、システムは、例えば上述の優先的使用方法のうちの１つを使用して、別のプールのキューを優先的に使用することによりプールにキューを追加する。
【００１２】
また、上述の動作の代わりに、又はそれに加えて、システムは、監視に基づいてＶＭ又は非ＶＭアドレス指定可能なノード（例えば、データのエンドノード）に対するデータトラフィックをプール内の第１のキューからプール内の第２のキューに再割り当てできる。例えばいくつかの実施形態のシステムは、監視に基づいて第１のキューを介するＶＭ又は非ＶＭアドレス指定可能なノードに対するトラフィックが最小閾値トラフィック量を下回る（例えば、ある期間の間）ことを検出する。この使用が十分ではないため、システムは当該トラフィックを第２のキューに切り替える。この切り替えを行う前に、いくつかの実施形態のシステムは、第２のキューを介するトラフィックが最大閾値トラフィック量を上回らないことを判定する。
【００１３】
いくつかの実施形態のシステムは、監視に基づいて第１のキューを介するトラフィックが最大閾値トラフィック量を上回る（例えば、ある期間の間）ことを検出する。この過剰な使用のため、システムは、ＶＭ又は非ＶＭアドレス指定可能なノード（例えば、データのエンドノード）に対するトラフィックを第１のキューから第２のキューに切り替える。この場合も、この切り替えを行う前に、いくつかの実施形態のシステムは、第２のキューを介するトラフィックが最大閾値トラフィック量を上回らないことを判定する。
【００１４】
上記の発明の概要は、本発明のいくつかの実施形態の簡単な説明であることを意図する。これは、本明細書において開示される全ての発明の主題の説明又は概要であることを意図しない。以下の発明を実施するための形態及びそこで参照される図面により、発明の概要において説明した実施形態及び他の実施形態を更に説明する。従って、本明細書により説明する全ての実施形態を理解するためには、発明の概要、発明を実施するための形態及び図面を全て読む必要がある。更に、請求項は、発明の概要、発明を実施するための形態及び図面における例示的な詳細により限定されない。
【図面の簡単な説明】
【００１５】
本発明の新規の特徴を添付の特許請求の範囲に記載する。しかし、説明のために、本発明の複数の実施形態を以下の図面において記載する。
【図１】短い待ち時間を必要とする（ＬＬＲ）ＶＭ及び長い待ち時間に耐えられる（ＨＬＴ）複数のＶＭの双方に対するトラフィックを有する過負荷状態のキューの例を示す図である。
【図２】トラフィック又はＶＭの要件の種類に基づいて、キューを２つの優先プールに概念的にグループ化することの例を示す図である。
【図３】３つの異なる種類のＶＭに対する３つの優先プールの例を示す図である。
【図４】ＰＮＩＣ内のキューに対する応答性を有するネットワーク仮想化レイヤ（ＮＶＬ）内のスレッド及び本発明のいくつかの実施形態の割込み生成アーキテクチャを示す図である。
【図５】いくつかの実施形態のキュー管理システムを示す図である。
【図６】いくつかの実施形態において負荷バランス調整器が実行する全体的な処理を概念的に示す図である。
【図７】いくつかの実施形態のキュー割り当て処理を示す図である。
【図８】いくつかの実施形態において負荷バランス調整器が周期的（例えば、数秒毎）に呼び出すプール調整処理を概念的に示す図である。
【図９】ＶＭによるキューの使用量を評価するためにいくつかの実施形態の負荷バランス調整器により実行される処理を示す図である。
【図１０】第１のキューが十分に使用されていないため、あるいはＶＭにより第１のキューが十分に使用されていないため、ＶＭを第１のキューから第２のキューに再割り当てする例を示す図である。
【図１１】第１のキューが過剰に使用されているため、ＶＭを第１のキューから第２のキューに再割り当てする例を示す図である。
【図１２】プールにわたるプールバランス調整の例を示す図である。
【図１３】ＭＡＣアドレスフィルタリングを使用して、ホスト装置上で実行するＶＭ及び非ＶＭデータアドレス指定可能なノードのデータトラフィックを異なるキュープール及びプール内の異なるキューにルーティングするいくつかの実施形態のキュー管理システムを示す図である。
【図１４】、
【図１５】いくつかの実施形態が５タプルフィルタを使用して、ビデオの提示中に仮想マシンにより送信又は受信されるＶＯＩＰパケット及びビデオパケットを区別することを示す例を示す図である。
【図１６】本発明のいくつかの実施形態が実現される電子システムを概念的に示す図である。
【発明を実施するための形態】
【００１６】
以下の本発明の詳細な説明において、本発明の多くの詳細、例及び実施形態を記載及び説明する。しかし、本発明は記載される実施形態に限定されず、説明する特定の詳細及び例のいくつかを用いずに実施されてもよいことが当業者には明らかになるだろう。
【００１７】
いくつかの実施形態は、ホスト上で実行する複数の仮想マシン（ＶＭ:virtual machines）との間のトラフィックを処理する複数のキューを効率的且つ動的に管理するキュー管理システムを提供する。本システムは、（１）優先度の高いプールが特定の種類のトラフィック又はＶＭ（例えば、短い待ち時間を必要とするＶＭに対するトラフィック）に対して確保される優先度の異なるプールにキューを分割し、（２）各プール内のキューの数を動的に調整し（すなわち、プールのサイズを動的に調整し）、（３）１つ以上の最適化基準（例えば、キューが十分に使用されていない又は過剰に使用されている場合に関する基準）に基づいてＶＭを新しいキューに動的に再割り当てすることにより、キューを管理する。
【００１８】
いくつかの実施形態において、キュー管理システムは、キューを以下の４種類のプールにグループ化する。
（１）いくつかの実施形態において、ＶＭの初期化時にＶＭの一部又は全てに対する初期キューである１つのデフォルトキューを含むデフォルトプール（他の実施形態において、デフォルトプールは２つ以上のデフォルトキューを含む）
（２）全ての未使用キュー（すなわち、どのＶＭとの間のトラフィックにも割り当てられていないキュー）を含む未使用プール
（３）ＬＲＯ及びＲＳＳ等の特定のハードウェア特徴に関連付けられたキューを含むハードウェア特徴プール
（４）短い待ち時間を必要とする（ＬＬＲ）ＶＭ及び長い待ち時間に耐えられる（ＨＬＴ）ＶＭ等の異なる種類の要件を有するＶＭを提供するキューを含むＶＭ要件プール
【００１９】
これらの実施形態のいくつかにおいて、キュー管理システムは最初、デフォルトプール内に存在する１つのデフォルトキューを除き、未使用のプール内の全キューを未割当とする。いくつかの実施形態は、最初のＶＭが初期化されるまでデフォルトキューを確保しないが、他の実施形態は、最初のＶＭが初期化される前でもデフォルトキューを指定する。
【００２０】
ＶＭのトラフィックが事前に設定された閾値を上回る場合、システムはＶＭのトラフィック要件に一致するプールが存在するか（例えば、閾値を上回っているＬＬＲ  ＶＭに対するＬＬＲプールが存在するか）を判定し、そのようなプールが存在する場合、ＶＭを当該プールに割り当てる。一致するプールが存在しない場合、システムは新しいプールを作成し、ＶＭを当該プールに割り当てる。新しいプールを作成するための未使用キューが存在しない場合、キュー管理システムは、１つ以上の割り当て済キュー（すなわち、先に指定されたプールに割り当てられたキュー）を優先的に使用し、新たに作成されたプールに優先的に使用されるキューを割り当てる。この優先的使用により、既存のプールの間でキューのバランスが再調整され、新しいプールのために１つ以上のキューが解放される。いくつかの実施形態において、プールにわたるバランス再調整処理は、プールの最小サイズ及び最大サイズ、プールの相対優先度等の１つ以上のリソース割り当て基準に基づく。
【００２１】
プールにわたるキューのバランス調整に加えて、いくつかの実施形態のキュー管理システムは、プール内のトラフィックのバランスを再調整する。本システムは、異なる実施形態において異なる基準を使用して、プール内のトラフィックのバランスを再調整する。そのような基準の例は、関連付けられた管理スレッドのＣＰＵ負荷、トラフィックの種類、トラフィックの負荷、キューの他の実時間負荷計測値等を含む。いくつかの実施形態において、システムは、異なるプールに対して異なるバランス再調整基準を使用する。例えばシステムは、いくつかのプールでは少数のキューにＶＭを集約しようとし、他のプールでは可能な限り多くのキューにＶＭを分散しようとする。いくつかの実施形態において、キュー管理システムは、周期的に及び／又は特定のイベントにバランス再調整処理を実行する負荷バランス調整器を有する。
【００２２】
ＶＭのトラフィックが閾値を下回る場合、いくつかの実施形態のキュー管理システムは、ＶＭをデフォルトキューに戻す。ＶＭが非デフォルトプールにおいてキューを使用している最後のＶＭである場合、最後に使用されたキューは、後でいずれかのプールに再割り当てできるように、割り当てが行われていないキューの未使用プールに移動される。このように、本手法において、キューは、ＶＭを割り当てられ次第、非デフォルトプールのうちの１つに割り当てられ、最後のＶＭが再割り当てされるか又は切り離され次第、未使用プールに再割り当てされる。
【００２３】
ＶＭのデータトラフィックに加えて又はＶＭのデータトラフィックの代わりに、いくつかの実施形態のキュー管理システムは、プールを動的に定義し、各プールを一意に管理し、プール内のキューを動的に変更し、ホスト上で実行する非ＶＭアドレス指定可能なノード（例えば、送信元エンドノード又は宛先エンドノード）との間のデータトラフィックを動的に再割り当てする。最初に、ＶＭに対するこれらの動作の実行を以下に説明する。その次に、非ＶＭアドレス指定可能なノードに対するこれらの動作の実行を説明する。
【００２４】
Ｉ．異なる要件を有するＶＭに対する異なるプール
上述のように、いくつかの実施形態のキュー管理システムは、優先度の高いプールが特定の種類のトラフィック又はＶＭ（例えば、短い待ち時間を必要とするＶＭに対するトラフィック）に対して確保される優先度の異なるプールに、キューを分割する。図２は、トラフィック又はＶＭの要件の種類に基づいて、キューを２つの優先プール２１０及び２１５に概念的にグループ化することの例を示す。詳細には、図２は、（１）複数のキューを有する物理ＮＩＣ(Physical NIC)２００、及び（２）異なる要件を有する複数の仮想マシン（ＶＭ）２０２を示す。ＶＭは、ホストコンピュータ（不図示）上で実行する。これらのＶＭとの間のトラフィックは、ＮＩＣの種々のキューに分散される。図２に示すように、各キューは、入力トラフィックを処理するための受信側バッファセット２０４と、出力トラフィックを処理するための送信側バッファセット２０６とを有する。いくつかの実施形態において、マルチコアプロセッサの１つのコアが各キューを管理する。従って、図２に示す例において、８つのコアがＮＩＣの８つのキューを管理する。
【００２５】
いくつかのＮＩＣにおいて、各受信側バッファセット２０４はＮＩＣにおける独自の独立型キューとなる。同様に、これらのＮＩＣにおいて、各送信側バッファセット２０６は、ＮＩＣにおける独自の独立型キューとなる。しかし、これらのＮＩＣにおいて受信側キューが送信側キューから分離し且つ独立している場合でも、いくつかの実施形態のキュー管理システムは１つの受信側キューと１つの送信側キューとを対にし、それにより、キューの対をＶＭに対する１つのキュー構造体として使用できる。しかし、他の実施形態はキューを「対」にしない。詳細には、これらの他の実施形態では、１つの受信側キューを使用する全てのＶＭが同一の送信側キューを使用する必要がない。２つのＶＭは、同一の受信側キューを使用するが異なる送信側キューを使用することができる。しかし、例示を簡略にするために、図３〜図６及び図１０〜図１５に示す各キューは、送信側キューと対にされた受信側キューを含むキューの対である。
【００２６】
図２において、キュー管理システムは、物理ＮＩＣ２００のキューを３つの異なる種類のプールにグループ化している。これらは、（１）デフォルトプール２０５、（２）ＬＬＲプール２１０及び（３）ＨＬＴプール２１５である。図２に示すように、いくつかの実施形態におけるデフォルトプール２０５は、１つのデフォルトキューのみを含む。他の実施形態において、デフォルトプール２０５は２つ以上のデフォルトキューを含む。デフォルトキューは、非デフォルトプールのキューに割り当てられないＶＭのトラフィックを提供する。１つのデフォルトキュー（デフォルトキュー２０７等）しか存在しない場合、「デフォルト」キューは、非デフォルトプールに割り当てられない全てのＶＭを提供する。いくつかの実施形態において、デフォルトキュー２０７は、全ての低トラフィックＶＭを提供し、すなわち、事前に設定されたトラフィック閾値より少ないトラフィックを有するあらゆるＶＭを提供する。これらのＶＭはトラフィックが少ないため、非デフォルトキューに配置する利点が小さい。
【００２７】
いくつかの点において、デフォルトキュー２０７は、どのプールにも属さないと見ることができる。というのは、ハードウェアから見た場合、デフォルトキュー２０７は、入出力トラフィックのルーティングを別のキューに向けるマッチングフィルタを有さない全てのＶＭを提供するためである。いくつかの実施形態のキュー管理システムは、ＶＭのトラフィックが閾値を上回るまで、各ＶＭをデフォルトキューから開始する。ＶＭのトラフィックが閾値を上回ると、システムはＶＭに対する非デフォルトキューを選択し、ＶＭのインバウンドトラフィックに対するフィルタを割り当てるようにＰＮＩＣに命令し、ＶＭのアウトバウンドトラフィックに対するフィルタを割り当てるように仮想化レイヤに命令する。いくつかの実施形態において、アウトバウンドトラフィックに対するフィルタは送信元ＭＡＣアドレスに基づき、インバウンドトラフィックに対するフィルタは宛先ＭＡＣアドレスに基づく。これらのフィルタは、入出力トラフィックを選択されたキューにルーティングするようにＰＮＩＣ及び仮想化レイヤ内のモジュールに命令する。尚、フィルタは他の識別子に基づいてもよい。例えば、いくつかの実施形態におけるアウトバウンドトラフィックに対するフィルタは、ソフトウェア転送要素のポートＩＤに基づく。
【００２８】
フィルタを割り当てることにより、非デフォルトプールに概念的に割り当てられるキューがＶＭのトラフィックを提供できる。換言すると、フィルタを指定することにより、システムはＶＭのトラフィックとキューとをリンクする。更に、キューとそれを保持する概念的な「プール」とを関連付けることにより、キュー管理システムは、異なる管理処理を適用して異なるプール内のキューを異なる方法で管理でき、それにより、異なる要件を有する異なるＶＭを管理できる。これについては第ＩＩ節で以下に更に説明する。
【００２９】
プールに割り当てられるべきキューに対するプールが存在しない場合、以下に更に説明するように、キュー管理システムは、最初にプールを定義した後、プールにキューを割り当てる。ＬＬＲプール２１０及びＨＬＴプール２１５は、特定のＶＭの要件に対処するために作成される２つのプールである。ＬＬＲプール２１０は、ＬＬＲ  ＶＭを提供することを意図するキューを含み、ＨＬＴプール２１５は、ＨＬＴ  ＶＭを提供することを意図するキューを含む。図２に示すように、ＬＬＲ  ＶＭ２５０及び２５２は、ＬＬＲプール２１０のＬＬＲキュー２２２及び２２４を介してパケットを送受信し、ＨＬＴ  ＶＭ２６０は、ＨＬＴプール２１５のＨＬＴキュー２３０〜２３８を介してパケットを送受信する。
【００３０】
いくつかの実施形態において、キュー管理システムは、ＬＬＲ  ＶＭのトラフィックが一方のキューのセットを通過し且つＨＬＴ  ＶＭのトラフィックが別のキューのセットを通過するようにフィルタを特に割り当てる（送信側及び受信側の双方において）ことにより、これらのプールを概念的に定義する。ＬＬＲ  ＶＭの場合、いくつかの実施形態のキュー管理システムは、ＬＬＲ  ＶＭが他のＶＭのトラフィックにより受ける影響が最小限になるように、ＶＭのトラフィックが可能な限り多くのＬＬＲキューに拡散されることを保証するために、ＬＬＲキューの割り当てを最適化する。それに対して、ＨＬＴ  ＶＭの場合、いくつかの実施形態のシステムは、多くの未使用キューを新しい割り当てに使用できるようにしておくために、ＨＬＴ  ＭＶにより使用されるＨＬＴキューの数を減少しようとすることにより、ＨＬＴキューの割り当てを最適化する。
【００３１】
ＬＬＲ  ＶＭに対するキューとＨＬＴ  ＶＭに対するキューとを分離することにより、いくつかの実施形態のキュー管理システムは、ＬＬＲ  ＶＭとの間のトラフィックが輻輳の少ないＬＬＲキューを通過するようにする。そのため、ＬＬＲ  ＶＭは、パケットの送受信における待ち時間を短くできる。
【００３２】
図２に示す例は３種類のプールを示すが、他の実施形態は２種類以下又は４種類以上のプールを使用することが当業者には認識されるだろう。例えばＬＬＲプール及びＨＬＴプールの双方を提供する代わりに、いくつかの実施形態のキュー管理システムはＬＬＲプールのみを定義し、全てのＨＬＴトラフィックがデフォルトプールを介するように向ける。そのようなＨＬＴトラフィックの全てを処理するために、いくつかの実施形態のキュー管理システムはデフォルトプール内に複数のキューを定義する。
【００３３】
ＬＬＲプール及び／又はＨＬＴプールに加えて、いくつかの実施形態のキュー管理システムは、ＮＩＣのＬＲＯハードウェア特徴及びＲＳＳハードウェア特徴をサポートするためにＬＲＯプール及びＲＳＳプール（図１と同様）を更に定義する。また、ＬＬＲプール及びＨＬＴプールはＶＭの要件に基づいて指定されるプールの例であり、ＬＬＲプールはＬＬＲ  ＶＭのトラフィックに対するプールであることを意図するため、ＬＬＲプールはＨＬＴプールより優先度の高いプールである。他の実施形態において、キュー管理システムは、３種類以上のＶＭの要件を処理するために３つ以上の優先プールを定義する。例えば図３は、３つの異なる種類のＶＭに対する３つの優先プールの例を示す。プールは、優先度の高いプール３０５、優先度が中間であるプール３１０及び優先度の低いプール３１５を含み、それらのキューはそれぞれ、優先度の高い（ＨＰ）ＶＭ３２０、優先度が中間である（ＭＰ）ＶＭ３２５及び優先度の低い（ＬＰ）ＶＭ３３０に対するトラフィックを処理する。いくつかの実施形態において、優先度の高いプールは、優先度の低いプールより少ないＶＭを有し、且つ／又は、キュー毎の総トラフィックが少ない。
【００３４】
また、ＬＬＲプール又はＨＬＴプールを定義する代わりに、あるいはそのようなプールを定義することに加えて、いくつかの実施形態のキュー管理システムは、高割込み（ＨＩ）プール又は低割込み（ＬＩ）プールを定義する。この場合、割込みは、ＰＮＩＣ内のキューに対して応答できる、ネットワーク仮想化レイヤ（ＮＶＬ）内のスレッドに対してＰＮＩＣにより生成される信号を参照する。図４は、そのようなスレッド及び本発明のいくつかの実施形態の割込み生成アーキテクチャを示す。いくつかの実施形態において、スレッドは、タスクセットを実行するために（例えば、ＶＭに対するネットワークスタック内の受信側モジュール又は送信側モジュールを管理するために）初期化される処理である。また、いくつかの実施形態において、異なるスレッドは、マルチスレッドプロセッサの異なるスレッド及び／又はマルチコアプロセッサの異なるコアにおける独立した処理として実行可能である。
【００３５】
図４はＰＮＩＣ４００を示し、このＰＮＩＣ４００は、（１）ＶＭに中継される必要のある入力トラフィックを受信する複数のキュー、（２）キューに対する入力トラフィックの割り当てを管理する受信側（ＲＸ）処理エンジン４０５、（３）キューの状態を監視するキュー監視器４１０、並びに（４）キューに格納されたデータを検索するようにＮＶＬの受信側スレッドに命令する割込みを生成する割込み生成器４３０を含んでいる。ＲＸ処理エンジンはＭＡＣフィルタ４２０を含み、これは、上述し且つ更に後述するように、ＶＭの入力トラフィックとキューとを対にするために使用される。
【００３６】
図４は、ＰＮＩＣ内の各キューに対する受信側（ＲＸ）スレッド４２７を更に示す。いくつかの実施形態において、スレッド４２７は、ＰＮＩＣを介する仮想マシンとの間のトラフィックを管理するネットワーク仮想化レイヤの一部である。いくつかの実施形態において、キュー管理システムはネットワーク仮想化レイヤの一部である。
【００３７】
各スレッドは、それに関連付けられたキューを管理する。キューが受信パケットで満たされる度に、ＰＮＩＣのキュー監視器４１０はこれを検出し、キューからパケットを検索するようにスレッドに命令するため、キューのスレッド４２５を実行するコアに対する割込みを生成するようにＰＮＩＣの割込み生成器４３０に命令する。生成器は、ＰＮＩＣドライバ４３５のＡＰＩを介して当該割込みを送出し、ＰＮＩＣドライバ４３５がコアに対する割込みを生成する。キューのスレッドが当該動作のために呼び出される度に、キューを管理し且つそのスレッドを実行するコアは、そのキューからパケットを読み出すスレッドを実行するため、実行中の別のタスクに割り込む必要がある。そのような割込みは、プロセッサの動作効率に影響を及ぼす。
【００３８】
従って、プロセッサの動作効率を向上し且つ／又は重要なＶＭに対する待ち時間を短縮するために、いくつかの実施形態のキュー管理システムは、ＨＩプール又はＬＩプールを定義する。このＨＩプールは、短い待ち時間で出力される必要のあるトラフィックを搬送するキューを含むプールであり、ＬＩプールは、長い待ち時間に耐えられるトラフィックを搬送するキューを含むプールである。
【００３９】
いくつかの実施形態において、ＨＩプールを管理するスレッドは、ＬＩプールを管理するスレッドより多く割込みを受信するため、いくつかの実施形態では、ＬＩプールを動作するコアより負荷の少ないプロセッサコアにより動作される。詳細には、ＬＬＲ  ＶＭの所望の短い待ち時間を考慮するために、いくつかの実施形態のキュー管理システムは、ＬＬＲ  ＶＭに対するトラフィックを処理するキューをＨＩプール内のキューとして指定する。この指定に基づいて、当該キューの管理及び当該キューのスレッドを実行するコアの管理を最適化するための種々のタスクを実行できる。例えばいくつかの実施形態におけるキュー管理システムは、当該ＨＩキューに割り当てられるＶＭの数を減少するか、あるいは同様に重要であり且つ短い待ち時間を必要とするＶＭのみを当該キューに割り当てる。それに加えて又はその代わりに、いくつかの実施形態のキュー管理システムは、当該ＨＩキューに対するスレッドを実行するコアに対する負荷を軽減するようにプロセッサのスケジューラに更に命令でき且つ／又は当該キューに対する割込みを早く生成するようにＰＮＩＣに命令できる。
【００４０】
図４は、ＨＩプールを実行するコアに対する負荷を軽減する例を示す。詳細には、本例において、キュー管理スレッドＴＱＭ１及びＴＱＭ２は、ＨＩキューである優先度の高いキューＨＰＱ１及びＨＰＱ２を管理するためのスレッドである。これらのスレッドは、マルチコアプロセッサ４５０のコア１及び２に割り当てられる。図４に示すように、コア２はスレッドＴＱＭ２のみを実行し且つコア１はスレッドＴＱＭ１及び非キュー管理スレッドＴＮＱＭ１を実行するため、これらのコアに対する負荷は相対的に軽い。これらのコアに対する負荷は、キュー管理スレッドＴＱＭ５（優先度の低いキュー５（ＬＰＱ５）に対する）を実行し且つ３つの他の非キュー管理スレッドＴＮＱＭ２〜ＴＮＱＭ４を更に実行するコア５に対する負荷と異なる。
【００４１】
ＨＬＴ  ＶＭの許容可能な長い待ち時間を考慮するために、いくつかの実施形態のキュー管理システムは、ＨＬＴ  ＶＭに対するトラフィックを処理するキューをＬＩプール内のＬＰＱとして指定する。この指定に基づいて、当該キューの管理及び当該キューのスレッドを実行するコアの管理を最適化するための種々のタスクを実行できる。例えばいくつかの実施形態におけるキュー管理システムは、より多くのＶＭを当該キューに割り当ててもよい。それに加えて又はその代わりに、いくつかの実施形態のキュー管理システムは、当該キューに対するスレッドを実行するコアに更なるスレッドをスケジュールできることをプロセッサのスケジューラに更に通知し且つ／又は当該キューに対して生成する割込みを少なくするように（すなわち、当該キューが更に満たされてから割込みを生成するように）ＰＮＩＣに命令する。
【００４２】
いくつかの実施形態において、ＨＩプール及び／又はＬＩプールの指定は、ＬＬＲプール及び／又はＨＬＴプールの指定に加えて使用されるが、他の実施形態において、それらはＬＬＲプール及び／又はＨＬＴプールの指定の代わりに使用される。いくつかの実施形態において、キューは、ＬＬＲキュー及びＨＩキューの双方として指定されてもよい。あるいは、ＬＬＲ  ＶＭはＨＬＴ  ＶＭと共にキューに含まれてもよいが、そのコアに対する負荷が重くならず且つキューを空にするために頻繁に割込みを行えるように、キューはＨＩキューとして指定されてもよい。
【００４３】
ＩＩ．キュー管理システム
図５を参照して、いくつかの実施形態のキュー管理システムを以下に説明する。このシステム５００は、優先度の高いプールが特定の種類のトラフィック又はＶＭ（例えば、短い待ち時間を必要とするＶＭに対するトラフィック）に対して確保される優先度の異なるプールに、キューを分割する。また、本システムは、各プール内のキューを動的に調整し（すなわち、プールのサイズを動的に調整し）、１つ以上の最適化基準（例えば、キューが十分に使用されていない又は過剰に使用されている場合に関する基準）に基づいてＶＭをプール内の新しいキューに動的に再割り当てする。
【００４４】
図５は、（１）ホスト上で実行している複数のＶＭ５０５、（２）ＶＭにより共有されるホストの物理ＮＩＣ５１５、（３）ホスト上で実行し且つ共有ＰＮＩＣを介するＶＭとの間のトラフィックを助長するネットワーク仮想化レイヤ５１０、並びに（４）スレッド（コンテキストとも呼ぶ）のうちの１つを実行するタイミング及び場所をプロセッサに命令するカーネルスケジューラである物理プロセッサスケジューラ５２５（物理ＣＰＵ又はＰＣＰＵとも呼ぶ）を示す。
【００４５】
ＰＮＩＣ５１５は、複数のキュー５１７を有する。これらのキューは、ホストにより受信された入力データを格納するための受信側キューと、ＶＭから送信された出力データを格納するための送信側キューとを含む。いくつかの実施形態において、各キューは、入力データ又は出力データを格納するためのバッファセットを含む。いくつかの実施形態において、受信側キューは送信側キューから分離し且つ独立しているが、仮想化レイヤは１つの受信側キューと１つの送信側キューとを対にし、それにより、キューの対をＶＭに対する１つのキュー構成体として使用できる。しかし、他の実施形態はキューを「対」にしない。換言すると、これらの実施形態では、１つの受信側キューを使用する全てのＶＭが同一の送信側キューを使用する必要がない。２つのＶＭは、同一の受信側キューを使用するが異なる送信側キューを使用することができる。
【００４６】
ＰＮＩＣは、有線又は無線リンクから入力パケットを受信する受信側（ＲＸ）処理エンジン５１１を更に有する。ＲＸ処理エンジンは、宛先ＭＡＣに基づいて各ＶＭの入力トラフィックと１つのキューの対とを関連付けるように構成されるＭＡＣフィルタ５１４を有する。仮想化レイヤは、出力パケットに対する同様のフィルタ５１６を保持し、当該レイヤ内のキュー選択器５１８は、当該フィルタ内のデータを使用して、各ＶＭの出力トラフィックが入力トラフィックと同一のキューの対を使用するように構成する。いくつかの実施形態において、フィルタ５１６は、ＶＭ又はＶＮＩＣの送信元ＭＡＣアドレスを用いてＶＭを指定するが、他の実施形態において、ＶＭのＶＮＩＣが接続するソフトウェア転送要素のポートＩＤを用いてＶＭを指定する。いくつかの実施形態において、ＰＮＩＣは、図４を参照して上述したように、キューを監視し且つ割込みを生成するための回路網を更に含む。
【００４７】
ＶＭは、いくつかの実施形態においてネットワーク仮想化レイヤ５１０を含むハイパーバイザ（不図示）上で実行する。図５は、各ＶＭが仮想ＮＩＣ（ＶＮＩＣ）５０７を含むことを示している。図５は、（１）ＶＭ毎に１つのネットワークスタック５５０、（２）ソフトウェア転送要素５３５、（３）統計データ収集エンジン５４０、（４）総計データ記憶装置５４５、並びに（５）動的負荷バランス調整器５５５を含むネットワーク仮想化レイヤ５１０を更に示す。各ネットワークスタックは、ＶＮＩＣエミュレータ５２７及びＩ／Ｏチェーン５２９を含む。各ネットワークスタックは、受信／送信スレッド５３１により管理される。
【００４８】
各ネットワークスタックは、ＶＮＩＣエミュレータを介してＶＭに接続し、全てのＶＭの全てのネットワークスタックにより共有されるソフトウェア転送要素５３５に接続する。各ネットワークスタックは、スイッチのポート（不図示）を介してソフトウェア転送要素に接続する。いくつかの実施形態において、ソフトウェア転送要素は、ＶＮＩＣ毎に単一のポートを保持する。ソフトウェア転送要素５３５は、自身のポートのうちの１つにおいて受信するパケットを自身のポートのうちの別の１つのポート又は別のホスト上で実行する別のソフトウェア転送要素のポートのうちの１つに転送するパケット処理動作を実行する。例えばいくつかの実施形態において、ソフトウェア転送要素は、パケット内のデータ（例えば、パケットヘッダ内のデータ）を使用してパケットとフローベースの規則とをマッチングしようとし、マッチングする規則が見つかると、マッチングする規則により指定される動作を実行する。
【００４９】
いくつかの実施形態において、異なるホスト装置（例えば、異なるコンピュータ）上で実行するソフトウェア転送要素は、同一の共有演算／ネットワーキングリソースを使用する異なるテナント、ユーザ、部門等の異なる論理ネットワークに対する異なる論理転送要素（ＬＦＥ）を実現するように構成される。例えば２つのホスト装置上で実行する２つのソフトウェア転送要素は、Ｌ２スイッチの機能性を実行できる。これらのソフトウェアスイッチの各々は、各論理Ｌ２スイッチが１つのエンティティのＶＭを接続することにより、２つの異なる論理Ｌ２スイッチを部分的に実現できる。いくつかの実施形態において、ソフトウェア転送要素はＬ３ルーティングの機能性を提供し、他のホスト上で実行するソフトウェアＬ３ルータを用いて異なる論理ルータを実現するように構成可能である。
【００５０】
仮想化の分野において、ソフトウェアスイッチがソフトウェア要素であるため、これらを仮想スイッチと呼ぶ場合がある。しかし、本明細書において、物理世界に結び付けられない論理構造体である論理転送要素と区別するために、ソフトウェア転送要素を物理転送要素（ＰＦＥ）と呼ぶ。換言すると、ソフトウェア転送要素は物理世界において存在し且つ動作するが、論理転送要素はユーザに対して提示される転送要素の単なる論理表現であるため、ソフトウェア転送要素をＰＦＥと呼ぶ。論理転送要素の例は、論理スイッチ、論理ルータ等の論理転送要素である。本明細書に参考として取り入れられる米国特許出願第１４／０７０，３６０号において、ＰＦＥ及びＬＦＥの更なる例が提供される。
【００５１】
ソフトウェア転送要素５３５は、出力パケットを送出し且つ入力パケットを受信するためにＰＮＩＣに接続する。いくつかの実施形態において、ソフトウェア転送要素は、パケットを送受信するためにＰＮＩＣに接続する際に介するポートを含むように定義される。上述のように、いくつかの実施形態において、キュー選択器５１８がソフトウェア転送要素５３５とＰＮＩＣとの間に配置される。キュー選択器は、入力パケットを検索するための受信側キュー及び出力パケットを供給するための送信側キューを選択する。上述のように、キュー選択器は、フィルタ５１６内のデータを使用して、特定のＶＭの出力トラフィックを供給するための送信側キューを識別する。選択器は、ＶＭのＲＸスレッドに対してキューを選択し且つそのパケットを検索するためにフィルタ内のデータを使用しない。いくつかの実施形態において、キュー選択器は、以下に更に説明するように、ネットワークスタックの受信／送信スレッド５３１の一部である。そのため、これらの実施形態の場合、キュー選択器５１８は、受信／送信スレッド５３１がいくつかの実施形態において実行するキュー選択動作の概念的表現である。
【００５２】
ＶＭ内の各ＶＮＩＣは、それに関連付けられたＶＮＩＣエミュレータ５２７を介するＶＭとネットワーク仮想化レイヤとの間のパケット交換を行う能力を有する。各ＶＮＩＣエミュレータは、ＶＭとの間でデータを送受信するためにＶＭ内のＮＩＣドライバと相互作用する。いくつかの実施形態において、ＶＮＩＣは、仮想ＮＩＣエミュレータにより実現される物理ＮＩＣのソフトウェア抽象化である。例えばいくつかの実施形態において、接続ＩＤを要求し且つ取得するためのコードは、仮想ＮＩＣエミュレータの構成要素内に常駐する。換言すると、いくつかの実施形態において、ＶＮＩＣの状態は、各ＶＮＩＣエミュレータにより実現され且つ保持される。ＶＮＩＣ等の仮想装置は、ＶＭの一部であるように説明するのに便利であるが実際はエミュレータを使用する仮想化ソフトウェアにより実現されるソフトウェア抽象化である。しかし、各ＶＭの状態は自身の仮想装置の状態を含み、これは下層の仮想化ソフトウェアにより制御され且つ保持される。図５は各ＶＭのＶＮＩＣ毎に１つのＶＮＩＣエミュレータを示すが、いくつかの実施形態において、各ＶＮＩＣエミュレータは２つ以上のＶＮＩＣ及び／又は２つ以上のＶＭに対する状態を保持してもよい。
【００５３】
各ネットワークスタック内のＩ／Ｏチェーンは、各パケットに対して一連のタスクを実行する一連のモジュールを含む。上述の本明細書に取り入れられる米国特許出願第１４／０７０，３６０号において説明されるように、Ｉ／Ｏチェーンのモジュールの２つの例は、ＡＲＰ及びＤＨＣＰ同報メッセージを同報通信することなく解決するＡＲＰ及びＤＨＣＰプロキシモジュールである。Ｉ／Ｏチェーン内のモジュールにより実行される処理の他の例は、ファイヤウォール及びトラフィックトンネリング動作を含む。Ｉ／Ｏチェーンの入力／出力は、ソフトウェア転送要素のポートのうちの１つに進む。
【００５４】
いくつかの実施形態において、各ネットワークスタック５５０の受信／送信スレッド５３１は、ネットワークスタック内のモジュールを管理するカーネルレベルのスレッドである。これらのスレッドは、スタックのＶＭに関連付けられるＰＮＩＣキュー５１７を更に管理する。詳細には、いくつかの実施形態において、各キューの受信側は、割込みを処理し且つキューの受信側からのパケットをポーリングするための専用ＲＸカーネルスレッドを有する。また、各ＶＭは、ＶＭから送出されたパケットを処理するための専用ＴＸカーネルスレッドを有する。いくつかの実施形態において、それらの実施形態で推奨されるキューの数はホストのマルチコアプロセッサのコアの数に等しいため、受信スレッド／送信スレッドの対の各々はホストのマルチコアプロセッサのコアのうちの１つにより実行される。図５において、スタック及びそれに関連付けられるキューの受信動作及び送信動作を別個に管理するために別個の受信スレッド及び送信スレッドが使用されるが、他の実施形態において、１つのスレッドが上記のタスクの双方を実行するために使用されることが当業者には認識されるだろう。また、いくつかの実施形態において、ＲＸ／ＴＸスレッドは、キュー、コア及び／又はＶＭに全く又は厳密に結び付けられなくてもよい。
【００５５】
上述のように、ネットワーク仮想化レイヤは、統計データ収集エンジン５４０、統計データ記憶装置５４５及び動的負荷バランス調整器５５５を更に含む。統計データ収集エンジン５４０、負荷バランス調整器５５５及びＲＸ／ＴＸスレッド５３１は、いくつかの実施形態のキュー管理システムを部分的に形成する。統計データ収集エンジン５４０により収集される統計データは、プールにキューを割り当てるタイミング及びプールを調整するタイミングを判定するために必要な情報を負荷バランス調整器に提供する。
【００５６】
異なる実施形態において、統計データ収集エンジンは異なるソースから統計データを取得する。例えばいくつかの実施形態において、当該エンジンは、ＣＰＵスケジューラ５２５（ＣＰＵ使用量の場合）及びＲＸ／ＴＸスレッド（ネットワークトラフィックの場合）のいずれかから統計データをプルするか又はプッシュされた統計データを受信する。ネットワークトラフィックの場合、ネットワーク仮想化レイヤは、ネットワークスタックの各レイヤ（すなわち、ＲＸ／ＴＸスレッドにより管理される各モジュール）を含む種々のソースから収集される統計データ（スループット、パケットレート、パケットドロップ等）を有する。
【００５７】
いくつかの実施形態において、統計データ収集エンジンは、ＰＮＩＣのパケットレート、ＰＮＩＣのスループット、並びにＲＸ／ＴＸスレッド毎のＣＰＵ使用量であるネットワークの統計データを負荷バランス調整器のために収集する。いくつかの実施形態において、ＲＸ／ＴＸスレッドが実際にＰＮＩＣと通信し且つ正確な数値を有するスレッドであるため、ＣＰＵスケジューラ５２５はＣＰＵ使用量データを更新し、ＲＸ／ＴＸスレッドはＰＮＩＣのパケットレート及びスループットを更新する。いくつかの実施形態において、ＰＮＩＣドライバモジュールがキュー選択器の下位に存在する。当該ＰＮＩＣドライバは、ＰＮＩＣと通信し且つＰＮＩＣの負荷の統計データを更新するモジュールである。また、いくつかの実施形態において、統計データ収集エンジンは、負荷バランス調整器のためにＰＮＩＣの統計データを収集するのに加えて、ＶＮＩＣエミュレータにより収集されるＶＮＩＣの統計データを更に収集する。
【００５８】
ＶＮＩＣの統計データに依存することにより、負荷バランス調整器は、同一のキューを共有するＶＭに悪影響を及ぼし始める何らかの閾値をＶＮＩＣのパケットレートが上回る場合、待ち時間の影響を受けやすいＶＭを専用キューに移動すると決定できる。更に一般的に、負荷バランス調整器５５５は収集された統計データを使用して、どのキューをどのＶＭに割り当てるか、プールにキューを動的に割り当てるタイミング及びプールを動的に調整するタイミングを判定する。
【００５９】
いくつかの実施形態において、負荷バランス調整器は、負荷バランス調整処理を周期的（例えば、数秒毎、数ミリ秒毎、数マイクロ秒毎等）に実行する。この処理は、統計データ収集エンジンが保持する「負荷統計データ」記憶装置５４５から統計データをプルし、これらの統計データに基づいて、プールを割り当てる必要があるか、プールの割り当てを解除する必要があるか、ＶＭをキューに割り当てる必要があるか、プールのサイズを変更する必要があるか及び／又はキューを優先的に使用する必要があるかを判定する。いくつかの実施形態において、負荷バランス調整器は、特定のキュー識別子と出力トラフィックの特定の送信元ＭＡＣアドレス及び入力トラフィックの特定の宛先ＭＡＣアドレスとを関連付けるようにＰＮＩＣ及び仮想化レイヤのフィルタを構成することにより、ＶＭをキューに割り当てる。ＰＮＩＣのＭＡＣフィルタを構成するために、負荷バランス調整器は、ＰＮＩＣドライバのＡＰＩを使用してキュー毎にフィルタ及びハードウェア特徴をプログラムする。
【００６０】
図５に示すように、負荷バランス調整器は、プール５６１、キューバランス再調整器５５９及びプールバランス再調整器５５７である３つのモジュールを有する。プールは、負荷バランス調整器が定義するＰＮＩＣキューのソフトウェアの抽象的グループ化である。負荷バランス調整器は、異なる処理を適用して異なる「プール」内のキューを管理する。そのため、各プールを同一の「特徴」を有するキューのセットであると見ることができる。この場合、特徴はハードウェア特徴（ＲＳＳ／ＬＲＯ等）と同様である。そのような特徴の例は、ＶＭの要件（短い待ち時間又は低い割込み率等）を含む。
【００６１】
異なる処理を適用して異なるプール内のキューを管理することにより、負荷バランス調整器は、異なるプールに対して異なる方法でキューの割り当て及びプールのサイズ変更を最適化できる。プールバランス再調整器５５７は、プールのリソース割り当て基準に基づいて各プールのサイズを変更し、必要に応じて他のプールのキューを優先的に使用する。そのようなリソース割り当て基準の例は、プールのキューの最大数／最小数、プールのＣＰＵ総使用量、プールのネットワークトラフィック、プールのサービス品質（ＱｏＳ）制約等を含む。キューバランス再調整器５５９は、プールのバランス再調整基準に基づいて、同一プール内のキューのバランスを再調整する。そのようなプールのバランス再調整基準の例は、可能な限り少ないキューにＶＭを集約すること（例えば、ＨＬＴプールの場合）、可能な限り多くのキューにＶＭを分散すること（例えば、ＬＬＲプールの場合）等である。いくつかの実施形態において、２つの異なるプールを管理する２つの異なる処理は、異なるリソース割り当て基準、異なる優先的使用基準、異なるバランス再調整基準等を指定する。
【００６２】
III．ＶＭの割り当ての調整及びプールの調整
図６は、いくつかの実施形態において負荷バランス調整器５５５が実行する全体的な処理６００を概念的に示す。いくつかの実施形態における負荷バランス調整器５５５は、当該処理を周期的（例えば、数秒毎、数ミリ秒毎、数マイクロ秒毎等）に実行して、ＶＭをキューに割り当て、各プール内のキューのバランスを再調整し、プールにわたる所望のバランスを保持する。
【００６３】
いくつかの実施形態において、処理６００は、タイマ（例えば、Ｎ秒タイマ）が満了した時に開始する。図６に示すように、処理６００は、最初に、デフォルトプール内のＶＭを検査して非デフォルトプールに移動する必要のあるＶＭを識別し且つ識別されたＶＭを非デフォルトプール内の適切な非デフォルトキューに移動するキュー割り当て処理を呼び出す（６０５）。いくつかの実施形態において、キュー割り当て処理では、ＶＭによるデフォルトキューの使用量がデフォルトキューに対する閾値レベル又はＶＭによるデフォルトキューの使用量に対する閾値レベルを上回る場合にＶＭを非デフォルトキューに移動する（６０５）。６０５において、デフォルトプールに戻す必要のある非デフォルトキュー内のＶＭを更に識別し、識別されたＶＭをデフォルトプールに戻す。いくつかの実施形態において、キュー割り当て処理は、ＶＭによる非デフォルトキューの使用量が非デフォルトキューに対する閾値レベル又はＶＭによる非デフォルトキューの使用量に対する閾値レベルを下回る場合にＶＭをデフォルトプールに戻す（６０５）。図７を参照して、いくつかの実施形態のキュー割り当て処理を以下に更に説明する。
【００６４】
６０５の後、処理６００は、各プール内のキューのバランスを再調整するプール調整処理を呼び出す（６１０）。いくつかの実施形態において、このプール調整処理は、各プールを検査し、プールに対する１つ以上の最適化基準に基づいて、１つ以上のＶＭをプール内のキュー間で移動するか又はプール内の新しいキューに移動する必要があるかを判定する。いくつかの実施形態のプール調整処理は、異なるプールに対して異なる最適化基準を使用する。例えばいくつかの実施形態において、ＬＬＲプールに対する最適化基準は、ＬＬＲプールのキューにＶＭを分散するように処理を偏らせるが、ＨＬＴプールに対する最適化基準は、ＨＬＴプール内の少数のキューにＶＭを集約するように処理を偏らせる。これらの基準及び６１０における判定に基づいて、処理６００において、ＶＭをプール内のキュー間で又はプール内の新しいキューに再割り当てする（６１０）。いくつかの実施形態のプール調整処理を以下に更に説明する。
【００６５】
次に６１５において、処理６００は、プールにわたる所望のバランスを保持するプールバランス調整処理を呼び出す。いくつかの実施形態において、プールバランス調整処理は、種々のプールにわたりキューの使用量を検査する。この検査に基づいて、バランス調整処理は１つのプールに１つ以上のキューを割り当ててもよい。この検査に基づいて、バランス調整処理は別のプールの１つ以上のキューの割り当てを解除してもよい。この処理は、１回の呼び出しで２つ以上のプールに更なるキューを割り当ててもよく、あるいは２つ以上のプールにおいてキューの割り当てを解除してもよい。プールにわたるバランス再調整処理を以下に更に説明する。
【００６６】
負荷バランス調整処理６００は他の実施形態と異なることが当業者には認識されるだろう。例えばいくつかの実施形態において、処理６００は、別個のバランス再調整動作６１５を有さず、動作６０５及び６１０の一部として当該動作を黙示的又は明示的に実行する。また、動作６０５、６１０及び６１５のうちの１つの一部として特定の副動作を上述及び後述するが、これらの副動作を上記の動作６０５、６１０又は６１５のうちの異なる動作において実行でき、あるいは、それ自体で異なる動作として又は異なる動作の副動作として実行できることが当業者には認識されるだろう。
【００６７】
６１５の後、処理６００は終了する。
【００６８】
図７は、いくつかの実施形態において負荷バランス調整器５５５が周期的（例えば、数秒毎、数ミリ秒毎、数マイクロ秒毎等）に呼び出すキュー割り当て処理７００を概念的に示す。いくつかの実施形態における負荷バランス調整器５５５は、当該処理を周期的に呼び出し、デフォルトキューを過剰に使用しているか又は非デフォルトキューを十分に使用していないＶＭを識別して移動する。図７に示すように、処理７００において、最初に、全てのＶＭによるデフォルトキュー及び非デフォルトキューの使用量に関する統計データを統計データ記憶装置５４５から収集する（７０５）。以下に更に説明するように、検索された統計データを使用して解析を実行する。
【００６９】
次に、検索された統計データに基づいて、デフォルトキューに対する閾値使用量又はＶＭによるデフォルトキューの使用量に対する閾値使用量（例えば、異なるＶＭがデフォルトキューに対する異なる閾値使用量を有する場合）を現在上回っているデフォルトプール内のデフォルトキューを使用するＶＭを識別する（７１０）。上述のように、いくつかの実施形態は、ＶＭの初期化時に各ＶＭをデフォルトキューに割り当てるが、各ＶＭによるデフォルトキューの使用量を監視し、ＶＭによる使用量が閾値レベルを上回る場合にＶＭを非デフォルトキューに移動する。
【００７０】
７１５において、７１０でＶＭが識別されたかを判定する。ＶＭが識別されなかった場合、以下に更に説明する７６５へ進む。ＶＭが識別された場合、７２０へ進み、７１０で識別されたＶＭのうちの１つを選択し、プールのキューに加わるための選択されたＶＭの要件を識別する。上述のように、本発明のいくつかの実施形態は、異なるＶＭのセットの１つ以上の異なる要件を満たすキューの１つ以上の非デフォルトプールを定義する。
【００７１】
次に７２５において、選択されたＶＭの要件に対するプールが事前に定義されているかを判定する。例えば選択されたＶＭがＬＬＲ  ＶＭであると仮定すると、ＬＬＲ  ＶＭをＬＬＲプールのキューに割り当てるためのＬＬＲプールが事前に定義されているかを判定する（７２５）。ＶＭの要件に対するプールが事前に定義されていると判定される場合（７２５）、事前に定義された当該プール内のキューのうちの１つに選択されたＶＭを割り当てることができるかを判定する（７３０）。換言すると、７３０において、プールの既存のキューが７２０で選択されたＶＭが使用できる十分な容量を有するかを判定する。
【００７２】
プール内のキューが十分な容量を有する場合、ＶＭを当該キュー及び当該キューのプールに割り当て（７３５）、以下に説明する７４０へ進む。上述のように、いくつかの実施形態は、送信元ＭＡＣアドレスを使用してＶＭの出力トラフィックと特定のキューとを結び付け且つ宛先ＭＡＣアドレスを使用して入力トラフィックと特定のキューとを結び付けるフィルタリングを介して、ＶＭとキューとを関連付ける。いくつかの実施形態は、ＶＭとプールとの関連付けを明示的に指定するが、他の実施形態は、ＶＭに関連付けられたキューとプールとの関連付けを介してＶＭとプールとの関連付けを黙示的に指定する。７３５でＶＭとプールとを関連付けることにより、負荷バランス調整器は、キューにおけるＶＭと当該キュー及び同一プール内の他のキューにおける他のＶＭとを共に管理するために共通の処理セットを適用できる。上述のように、いくつかの実施形態において、これらの処理セットは、他のキュープール内の他のＶＭを管理するために使用される処理セットと異なる。
【００７３】
選択されたＶＭの要件（例えば、ＬＬＲ要件）に対するプールが存在しないと判定される場合（７２５）、選択されたＶＭの要件に対するプールを指定し（例えば、ＬＬＲプールを指定し）（７４５）、７５０へ進む。ＶＭの要件に対する事前に指定されたプールが選択されたＶＭに対する十分な容量を有するキューを有さないと判定される場合（７３０）も７５０へ進む。
【００７４】
７５０において、現時点でＶＭに割り当てられていないＰＮＩＣキューが存在するか（すなわち、未使用キュープール内にキューが存在するか）を判定する。そのようなキューが存在する場合、未使用キューのうちの１つを選択し（７５５）、それをプールに割り当て、選択されたＶＭを当該キュー及びプールに割り当て、以下に説明する７４０へ進む。そのようなキューが存在しない場合、未使用プールではない別のプールにより使用されるキューのうちの１つを優先的に使用する（７６０）。優先的使用は、最初に、優先的に使用されるキューを使用しているＶＭを優先的に使用されるキューを含むプール内の他のキューに再割り当てすることを含む。いくつかの実施形態において、ＶＭの現在の非デフォルトプールの優先度が他の非デフォルトプールより低いため、別のプールのキューを優先的に使用できない場合がある。全てのＶＭが再割り当てされ且つキューがそのようなＶＭに対する全てのトラフィックの処理を終了すると、優先的に使用されるキューが選択されたＶＭの要件に対するプールに割り当てられる（７６０）。選択されたＶＭを当該キュー及びプールに更に割り当て（７６０）、７４０へ進む。
【００７５】
７４０において、７１０で識別された全てのＶＭを処理したかを判定する。全てのＶＭを処理していない場合、７２０に戻り、識別された別のＶＭを選択する。全てのＶＭを処理した場合、７１０で識別された各ＶＭをプール及びキューに割り当てた後、７０５で検索された統計データに基づいて、非デフォルトキューにおけるいずれかのＶＭをデフォルトプールに戻す必要があるかを判定する（７６５）。いくつかの実施形態において、ＶＭによる非デフォルトキューの使用量が非デフォルトキューに対する閾値使用量又はＶＭによる非デフォルトキューの使用量に対する閾値使用量を下回る場合、ＶＭをデフォルトキューに戻す。これらの実施形態のいくつかにおける処理は、ＶＭによる使用量が十分に長い期間にわたり閾値使用量を下回る場合のみ、ＶＭを移動する。７６５においてＶＭが識別される場合、識別されたＶＭをデフォルトプールのデフォルトキューに戻し、以前に割り当てられた非デフォルトキューのプールから当該ＶＭを除去する。この再割り当て後、以前に割り当てられた非デフォルトキューを他のＶＭが使用しない場合、処理７００において、更に非デフォルトキューを未使用キューのプールに再割り当てする（７６５）。この再割り当てされたキューがプールの最後のキューである場合、いくつかの実施形態の処理７００において、プールが現時点でキューを全く含まないため、更にプールの割り当てを解除する。しかし、他の実施形態は、そのような状況でプールの割り当てを解除しない。７６５の後、処理は終了する。
【００７６】
図８は、いくつかの実施形態において負荷バランス調整器５５５が周期的（例えば、数秒毎、数ミリ秒毎、数マイクロ秒毎）に呼び出すプール調整処理８００を概念的に示す。いくつかの実施形態における負荷バランス調整器５５５は、当該処理を周期的に呼び出して、各プール内のキューのバランスを再調整する。いくつかの実施形態において、プール調整処理は、各プールを検査し、プールに対する１つ以上の最適化基準に基づいて、１つ以上のＶＭをプール内のキュー間で移動するか又はプール内の新しいキューに移動する必要があるかを判定する。いくつかの実施形態のプール調整処理は、異なるプールに対して異なる最適化基準を使用する。例えばいくつかの実施形態において、ＬＬＲプールに対する最適化基準は、ＬＬＲプールのキューにＶＭを分散するように処理を偏らせるが、ＨＬＴプールに対する最適化基準は、ＨＬＴプール内のキューにＶＭを集約するように処理を偏らせる。
【００７７】
図８に示すように、処理８００において、最初に、全てのＶＭによるデフォルトキュー及び非デフォルトキューの使用量に関する統計データを統計データ記憶装置５４５から収集する（８０５）。以下に更に説明するように、検索された統計データを使用して解析を実行する。８０５の後、処理８００において、非デフォルトプールのうちの１つを選択して検査する（例えば、ＬＬＲプールを選択して検査する）（８１０）。次に８１５において、プール内のいずれかのキューが十分に使用されてないかを判定する。十分に使用されてないキューを見つけた場合、選択されたプール内の他のいずれかのキューが８１５で識別された十分に使用されてないキューを現在使用しているＶＭに対する容量を有するかを判定する（８１５）。そのような容量に余裕のあるキューが識別された場合、ＶＭを十分に使用されてないキューから容量に余裕のあるキューに割り当てる（８１５）。また、移動後、他のＶＭが十分に使用されてないキューに割り当てられていない場合、選択されたプールから十分に使用されてないキューの割り当てを解除する（すなわち、十分に使用されてないキューを未使用プールに割り当てる）（８１５）。このように、後で別のプール又は同一プールに割り当てるために、十分に使用されてないキューを解放することができる。
【００７８】
８１５の後、選択されたプール内の過剰に使用されているキューを識別する（８２０）。その後、選択されたプールが、識別された過剰に使用されているキューに現在割り当てられているＶＭのうちの１つ以上のトラフィックを処理するための容量に余裕のあるキューを有するかを判定する（８２５）。容量に余裕のある１つ以上のキューが識別される場合（８２５）、識別された過剰に使用されているキューに現在割り当てられているＶＭのうちの１つ以上を容量に余裕のある１つ以上のキューに割り当て（８３０）、以下に説明する８３５へ進む。
【００７９】
それに対して、選択されたプールが、過剰に使用されているキューを現在通過しているトラフィックの一部を処理するための容量に余裕のあるキューを有さないと判定される場合（８２５）、未使用キューが存在するか（例えば、未使用プールがキューを有するか）を判定する（８４０）。未使用キューが存在する場合、未使用キューのうちの１つ以上を選択されたプール（すなわち、８１０で選択されたプール）に割り当てる（８４５）。８４５において、識別された過剰に使用されているキューに現在割り当てられているＶＭのうちの１つ以上を新たに割り当てられたキューに更に割り当て、以下に説明する８３５へ進む。
【００８０】
未使用キューが存在しないと判定される場合（８４０）、別のプールのキューを優先的に使用できるかを判定する（８５０）。いくつかの実施形態において、全てのプールが他のプールのキューを優先的に使用できるわけではなく、いくつかのプール（例えば、ＬＬＲプール）のみが他のプール（例えば、ＨＬＴプール）のキューを優先的に使用できる。また、いくつかの実施形態において、いくつかのプールは、特定の状況において（例えば、他のプール自体が著しい過負荷状態になっていない場合）のみ、他のプールのキューを優先的に使用できる。
【００８１】
別のプールのキューを優先的に使用できないと判定される場合（８５０）、８３５へ進む。それに対して、別のプールのキューを優先的に使用できると判定される場合（８５０）、優先的に使用されるキューを現在使用している全てのＶＭを優先的に使用されるキューと同一プール内の新しいキューに割り当てる（８５５）。全てのＶＭを再割り当てした後、選択されたプール（すなわち、８１０で選択されたプール）に優先的に使用されるキューを割り当て（８５５）、識別された過剰に使用されているキューに現在割り当てられているＶＭのうちの１つ以上を新たに割り当てられたキューに割り当て、８３５へ進む。
【００８２】
８３５において、検査する必要のある非デフォルトプールの全てを検査したかを判定する。そのような非デフォルトプールの全てを検査したと判定される場合、処理は終了する。そのような非デフォルトプールの全てを検査したと判定されない場合、８１０に戻り、別の非デフォルトプールを選択する。異なるプールに対してキューが十分に使用されていない及び過剰に使用されていることを評価するために、異なる基準が使用される。例えばＬＬＲプールの場合、過剰な使用の閾値は５０％の負荷であってもよく、使用が十分ではない場合の閾値は５％であってもよいが、ＨＬＴプールの場合、過剰な使用の閾値は９０％であってもよく、使用が十分ではない場合の閾値は７５％であってもよい。
【００８３】
また、上述のように、いくつかの実施形態は、プールのキューの最大数／最小数、プールのＣＰＵ総使用量、プールのネットワークトラフィック、プールのサービス品質（ＱｏＳ）制約等の異なるプールリソース割り当て基準に基づいて、異なるプールのサイズを変更する。同様に、いくつかの実施形態は、可能な限り少ないキューにＶＭを集約すること（例えば、ＨＬＴプールの場合）、可能な限り多くのキューにＶＭを分散すること（例えば、ＬＬＲプールの場合）等の異なるバランス再調整基準に基づいて、異なるプール内のキューのバランスを再調整する。
【００８４】
いくつかの実施形態では、図８の処理８００において、ＶＭを同一プール内の他のキューに再割り当てすることにより十分に使用されてないキューの割り当てを解除できるようにするために、十分に使用されてないキューを検査する。十分に使用されてないキューの検査に加えて又はその代わりに、いくつかの実施形態の負荷バランス調整器は、非デフォルトキューに割り当てられる各ＶＭを検査し、ＶＭによる非デフォルトキューの使用量が閾値レベルを下回るかを判定する。図９は、ＶＭによるキューの使用量を評価するためにいくつかの実施形態の負荷バランス調整器により実行される処理９００を示す。
【００８５】
図９に示すように、処理９００は、非デフォルトキューのＶＭを選択する（９０５）ことから開始する。次に９１０において、そのＶＭがキューを十分に使用していないかを判定する。例えばいくつかの実施形態において、キューを介するトラフィックの１％のみがＶＭによるものである場合、ＶＭはキューを十分に使用していないと考えられる。
【００８６】
ＶＭがキューを十分に使用していると判定される場合（９１０）、処理は終了する。ＶＭがキューを十分に使用していないと判定される場合、ＶＭの現在のキューと同一プール内の別のキューが選択されたＶＭに対する容量を有するかを判定する（９１５）。別のキューがそのような容量を有さないと判定される場合、処理は終了する。別のキューがそのような容量を有すると判定される場合、ＶＭの現在のキューと同一プール内の新しいキューにＶＭを割り当てる（９２０）。その後、ＶＭの以前のキューに他のＶＭが割り当てられていない場合、ＶＭの以前のキューの割り当てを解除する（９２５）。
【００８７】
図１０は、第１のキューが十分に使用されていない、又は、ＶＭによる第１のキューが十分に使用されていないため、ＶＭを第１のキューから第２のキューに再割り当てする例を示す。詳細には、図１０は、最初に２つのキュー１０２５及び１０３０に割り当てられる２つのＶＭ１０１５及び１０２０のネットワークスタック１００５及び１０１０を示す。これらの２つのＶＭは、ＶＭの初期化時にこれらの２つのキューに割り当てられる。
【００８８】
その後、負荷バランス調整器５５５は、種々のＶＭによる種々のキューの使用量に関する統計データを検索する。これらの統計データに基づいて、負荷バランス調整器は、ＶＭ１０２０が使用するキュー１０３０の容量が１％未満であることを検出する。当該ＶＭがキューを十分に使用していないため、負荷バランス調整器は、ＶＭ１０２０及びそのネットワークスタック１０１０をキュー１０３０からキュー１０２５に再割り当てするフィルタをネットワーク仮想化レイヤ及びＰＮＩＣ内に定義する。他のＶＭがキュー１０３０を使用していない場合、負荷バランス調整器は更に、キュー１０３０を未使用キュープールに再割り当てする。いくつかの実施形態において、負荷バランス調整器は、ＶＭ１０２０をキュー１０２５に再割り当てする（且つキュー１０３０を同時に使用している他のＶＭを再割り当てする）ことによりキュー１０３０をＶＭのトラフィックから解放して未使用プールに再割り当てできるようになると判定される場合のみ、ＶＭ１０２０をキュー１０２５に再割り当てする。しかし、他の実施形態において、負荷バランス調整器は、ＶＭによるキューの使用量のみに基づいて再割り当てを決定する。
【００８９】
図１１は、第１のキューの過剰な使用のため、ＶＭを第１のキューから第２のキューに再割り当てする例を示す。詳細には、図１１は、ＶＭ１０１５及び１０２０の双方がキュー１０２５に割り当てられた後の、同一の２つのＶＭ１０１５及び１０２０の同一の２つのネットワークスタック１００５及び１０１０を示す。ある時点で、負荷バランス調整器５５５は、種々のＶＭによる種々のキューの使用量に関する統計データを検索する。これらの統計データに基づいて、負荷バランス調整器は、キュー１０２５が容量の９０％を使用してトラフィックを処理していることを検出する。当該キューが過剰に使用されているため、負荷バランス調整器は、ＶＭ１０２０及びそのネットワークスタック１０１０をキュー１０２５からキュー１０３０に再割り当てするフィルタをネットワーク仮想化レイヤ及びＰＮＩＣ内に定義する。
【００９０】
上述のように、いくつかの実施形態における負荷バランス調整器は、プールにわたる所望のバランスを保持するプールバランス調整処理である。いくつかの実施形態において、プールバランス調整処理は、種々のプールにわたりキューの使用量を検査する。この検査に基づいて、バランス調整処理は１つのプールに１つ以上のキューを割り当ててもよい。この検査に基づいて、バランス調整処理は別のプールの１つ以上のキューの割り当てを解除してもよい。この処理は、１回の呼び出しで２つ以上のプールに更なるキューを割り当ててもよく、あるいは２つ以上のプールにおいてキューの割り当てを解除してもよい。
【００９１】
図１２は、プールにわたるプールバランス調整の例を示す。詳細には、図１２は、優先度の低いプール１２１５から優先度の高いプール１２２０へのキューの追加を２つの段階１２０５及び１２１０で示す。第１の段階において、負荷バランス調整器５５５は、統計データ記憶装置５４５から統計データを検索する。検索された統計データに基づいて、負荷バランス調整器は、優先度の高いプール１２２０のキューを介する負荷（ＬＨ）が優先度の低いプール１２１５のキューを介する負荷（ＬＬ）の特定の割合（例えば、７５％）を上回ると判定する。
【００９２】
いくつかの実施形態では、優先度の高いキューを介する負荷は優先度の低いキューを介する負荷より大幅に小さいことが望ましいため、負荷バランス調整器は、優先度の低いプールのキュー１２５０が当該プールから除去されて優先度の高いプールに追加されるようにフィルタを設定する。キュー１２５０が優先度の高いプールに切り替えられる前に、優先度の低いプールにおいてキュー１２５０を使用していたＶＭが当該プール内の異なるキューに割り当てられる必要がある。図１２は、キュー１２５０を優先度の高いプールに追加した後、優先度の高いキューを介する負荷（ＬＨ）が優先度の低いキューを介する負荷（ＬＬ）の指定された割合を下回ることを示す。
【００９３】
ＩＶ．非ＶＭアドレス指定可能なノード及び他のフィルタリング
ホスト装置上で実行する１つ以上のＶＭとの間のデータトラフィックに対して、キューのプールを動的に定義し、各プールを一意に管理し、プール内のキューを動的に変更し且つＶＭのトラフィックを新しいキューに動的に再割り当てする複数の実施形態を上述した。これらの実施形態の多くは、ホスト装置により受信又は送信されるパケットの宛先又は送信元ＭＡＣアドレスを使用して、ＶＭのデータトラフィックパケットを異なるプール及びプール内の異なるキューに割り当てる。
【００９４】
しかし、全ての実施形態がＭＡＣアドレスを使用してデータトラフィックをプール及びプール内のキューに割り当てるわけではない。また、いくつかの実施形態のキュー管理方法及び装置は、ＶＭのデータトラフィック以外のデータトラフィックに対して使用される。詳細には、ＶＭのデータトラフィックに加えて又はＶＭのデータトラフィックの代わりに、いくつかの実施形態は、プールを動的に定義し、各プールを一意に管理し、プール内のキューを動的に変更し、ホスト上で実行する非ＶＭアドレス指定可能なノード（例えば、送信元エンドノード又は宛先エンドノード）との間のデータトラフィックを動的に再割り当てする。いくつかの実施形態の方法及び装置は、これらの動作を実行してキューを介する異なる種類のデータトラフィックのルーティングを区別するために使用される。
【００９５】
複数のそのような実施形態を以下に更に説明する。詳細には、第Ａ項において、ＭＡＣアドレスフィルタリングを使用して非ＶＭトラフィックデータを異なるプールの異なるキューにルーティングする複数の実施形態を説明する。次に第Ｂ項において、５タプルＩＰフィルタリングを使用して異なる種類のデータトラフィックを異なるプールの異なるキューにルーティングする複数の実施形態を説明する。
【００９６】
Ａ．非ＶＭトラフィックに対するＭＡＣフィルタリング
いくつかの実施形態は、ＭＡＣアドレスフィルタリングを使用して、ホスト装置上で実行する非ＶＭデータアドレス指定可能なノードのデータトラフィックを異なるキュープール及びプール内の異なるキューにルーティングする。例えばいくつかの実施形態の方法は、ホスト装置の物理ＮＩＣを介して、非ＶＭアドレス指定可能なノード（例えば、データのエンドノード）のセットに対するデータトラフィックを監視する。方法は、この監視に基づいて少なくとも非ＶＭアドレス指定可能なノードのセットに対するプールを指定し、プールにキューのセットを割り当てる。その後、方法は、宛先又は送信元ＭＡＣフィルタリングを使用して、ホスト装置により受信又は送信される非ＶＭアドレス指定可能なノードのセットに対するデータトラフィックを割り当て済みのキューのセットに向ける。
【００９７】
その代わりに又はそれに加えて、方法は、監視に基づいて非ＶＭアドレス指定可能なノードのセットに対するプールに割り当てられたキューのセットを変更できる。そのような変更の例は、プールのキューのうちの１つ以上が過剰に使用されるか又は十分に使用されない場合にプールにキューを追加するか又はプールからキューを除去することを含む。いくつかの実施形態において、方法は、例えば上述の優先的使用方法のうちの１つを使用して、別のプールのキューを優先的に使用することによりプールにキューを追加する。
【００９８】
また、上述の動作の代わりに又はそれに加えて、方法は、監視に基づいて非ＶＭアドレス指定可能なノード（例えば、データのエンドノード）に対するデータトラフィックをプール内の第１のキューからプール内の第２のキューに再割り当てできる。例えばいくつかの実施形態の方法は、監視に基づいて第１のキューを介する非ＶＭアドレス指定可能なノードに対するトラフィックが最小閾値トラフィック量を下回る（例えば、ある期間の間）ことを検出する。この使用が十分ではないのため、方法は当該トラフィックを第２のキューに切り替える。この切り替えを行う前に、いくつかの実施形態の方法は、第２のキューを介するトラフィックが最大閾値トラフィック量を上回らないことを判定する。
【００９９】
いくつかの実施形態の方法は、監視に基づいて第１のキューを介するトラフィックが最大閾値トラフィック量を上回る（例えば、ある期間の間）ことを検出する。この過剰な使用のため、方法は、非ＶＭアドレス指定可能なノード（例えば、データのエンドノード）に対するトラフィックを第１のキューから第２のキューに切り替える。この場合も、この切り替えを行う前に、いくつかの実施形態の方法は、第２のキューを介するトラフィックが最大閾値トラフィック量を上回らないことを判定する。
【０１００】
図１３は、ＭＡＣアドレスフィルタリングを使用して、ホスト装置上で実行するＶＭ及び非ＶＭデータアドレス指定可能なノードのデータトラフィックを異なるキュープール及びプール内の異なるキューにルーティングするいくつかの実施形態のキュー管理システム１３００を示す。本システムは図５のシステム５００と同様であるが、システム５００はＶＭエンドノードとの間のトラフィックのみを管理するのに対して、システム１３００はＶＭとの間のトラフィック、並びにｉＳＣＳＩ（内部小型コンピュータシステムインタフェース）マウンタ１３０５、ＮＦＳ（ネットワークファイル記憶装置）マウンタ１３０７及びＶＭマイグレータ１３０９等の非ＶＭアドレス指定可能なノードとの間のトラフィックを管理する点が異なる。システム１３００は、優先度の高いプールが特定の種類のアドレス指定可能なノードに対して確保される優先度の異なるプールにキューを分割する。また、システム１３００は、各プール内のキューを動的に調整し（すなわち、プールのサイズを動的に調整し）、１つ以上の最適化基準（例えば、キューが十分に使用されていない又は過剰に使用されている場合に関する基準）に基づいてアドレス指定可能なノードをプール内の新しいキューに動的に再割り当てする。
【０１０１】
図１３は、（１）ホスト（不図示）上で実行する複数のＶＭ５０５、（２）２つのマウント済記憶ボリューム１３２０及び１３２５、（３）ＶＭマイグレーションデータ１３３０、（４）ＶＭ及び非ＶＭノードにより共有されるホストの物理ＮＩＣ５１５、並びに（５）共有ＰＮＩＣを介するＶＭとの間のトラフィックを助長する仮想化レイヤ１３１０を示す。更に示すように、仮想化レイヤは、ｉＳＣＳＩマウンタ１３０５、ＮＦＳマウンタ１３０７及びＶＭマイグレータ１３０９等の非ＶＭ複数のアドレス指定可能なノードを含む。当該レイヤは、ＶＭ又は非ＶＭアドレス指定可能なノードの各々に対するネットワークスタック１３１１、１３１３、１３１５、１３１７又は１３１９を更に含む。仮想化レイヤは、ソフトウェア転送要素５３５（例えば、ソフトウェアスイッチ）、キュー選択器５１８、動的負荷バランス調整器５５５、統計データ収集エンジン５４０及び統計データ記憶装置５４５を更に含む。
【０１０２】
いくつかの実施形態において、図１３のＰＮＩＣ５１５は、上述した図５のＰＮＩＣ５１５と同一である。上述のように、ＰＮＩＣは、有線又は無線リンクから入力パケットを受信する受信側（ＲＸ）処理エンジン５１１を有する。ＲＸ処理エンジンは、宛先ＭＡＣに基づいて（ＶＭ又は非ＶＭ）各アドレス指定可能なノードの入力トラフィックと１つのキューの対とを関連付けるように構成されるＭＡＣフィルタ５１４を有する。仮想化レイヤは、出力パケットに対する同様のフィルタ５１６を保持し、当該レイヤ内のキュー選択器５１８は、当該フィルタ内のデータを使用して、各アドレス指定可能なノードの出力トラフィックが入力トラフィックと同一のキューの対を使用するように構成する。いくつかの実施形態において、フィルタ５１６は、ＶＭ又はＶＮＩＣの送信元ＭＡＣアドレスを用いてアドレス指定可能なノードを指定するが、他の実施形態において、ＶＭのＶＮＩＣが接続するソフトウェア転送要素のポートＩＤを用いてＶＭを指定する。図１３のＰＮＩＣ５１５が図５のＰＮＩＣ５１５と同一であるため、不必要な詳細により図１３の説明を不明瞭にしないために、これを更に説明しない。
【０１０３】
ＶＭ及び非ＶＭアドレス指定可能なノードは、いくつかの実施形態において仮想化レイヤ１３１０を含むハイパーバイザ（不図示）上で実行する。ＶＭ及び非ＶＭアドレス指定可能なノードは、ネットワークを介して送信されるパケットに対する送信元エンドノード及び宛先エンドノードである場合がある。上述のように、これらのノードは、ＶＭ５０５、ボリュームマウンタ１３０５及び１３０７、並びにＶＭマイグレータ１３０９を含む。ｉＳＣＳＩマウンタ１３０５は、ホスト上の記憶ボリューム１３２０をマウントする。この記憶ボリューム１３２０は、ｉＳＣＳＩプロトコルを介してアクセス可能な外部記憶装置（すなわち、記憶サーバ等のホストの外部の記憶装置）の一部又は全てである。同様に、ＮＦＳマウンタ１３０７は、ホスト上の記憶ボリューム１３２５をマウントする。この記憶ボリューム１３２５は、ＮＦＳプロトコルを介してアクセス可能な外部記憶装置（例えば、記憶サーバ）の一部又は全てである。その場合、マウント済ボリュームは、外部記憶装置がホスト上に常駐するかのようにホスト又は他の装置上で実行するモジュール（例えばＶＭ）によりアクセス可能である。ＶＭマイグレータ１３０９は、１つのホストから別のホストへのＶＭのライブマイグレーションを助長するために、ホスト上で実行する各ＶＭに関するデータを収集する。そのようなＶＭマイグレータの１つの例は、ＶＭｗａｒｅ  ＩｎｃのＥＳＸハイパーバイザにおいて使用されるｖＭｏｔｉｏｎモジュールである。
【０１０４】
各アドレス指定可能なノードは、ネットワークスタック及び転送要素のポート（不図示）を介してソフトウェア転送要素５３５に接続する。いくつかの実施形態において、各ＶＭのネットワークスタックは、図５を参照して上述したように、ＶＮＩＣエミュレータ５２７及びＩ／Ｏチェーン５２９を含み、受信／送信スレッド５３１により管理される。いくつかの実施形態において、非ＶＭ各アドレス指定可能なノードのネットワークスタックは、ハイパーバイザカーネルネットワークインタフェース及び受信／送信スレッドを含む。いくつかの実施形態において、非ＶＭ各アドレス指定可能なノードのハイパーバイザカーネルネットワークインタフェース（例えば、ＶＭｗａｒｅ  Ｉｎｃのｖｍｋｎｉｃ）は、非ＶＭアドレス指定可能なノードとの間で送受信されるＴＣＰ／ＩＰパケットを処理するためのＴＣＰ／ＩＰスタックを含む。例えばいくつかの実施形態において、非ＶＭ各アドレス指定可能なノードのネットワークは、（１）対応するマウント済ボリューム１３２０／１３２５又はマイグレーションデータ記憶装置１３３０から送出するパケットにＴＣＰ／ＩＰパケットヘッダを付与し、（２）対応するマウント済ボリューム又はマイグレーションデータ記憶装置に格納するために、受信するパケットからＴＣＰ／ＩＰパケットヘッダを除去する。
【０１０５】
いくつかの実施形態において、非ＶＭアドレス指定可能なノード（例えば、ＶＭマイグレータ１３０９）のハイパーバイザカーネルネットワークインタフェースは、ＴＣＰ／ＩＰスタックを含まず、ＲＤＭＡ（リモート直接メモリアクセス）パケット処理モジュール等の他のパケット処理モジュールを含む。また、いくつかの実施形態において、非ＶＭアドレス指定可能なノードのネットワークスタックは、対応するボリューム又はデータ記憶装置との間で送受信されるパケットに対して他の変換動作を実行するための他のＩ／Ｏチェーンモジュールを含む。図５の受信／送信スレッド５３１と同様に、非ＶＭ各アドレス指定可能なノードのネットワークスタックの受信／送信スレッドは、ネットワークスタック内のモジュールを管理し、スタックの非ＶＭアドレス指定可能なノードと関連付けられるＰＮＩＣキュー５１７と対話し、スタックのモジュールの動作に関する統計データを収集する。
【０１０６】
上述のように、仮想化レイヤは、統計データ収集エンジン５４０、統計データ記憶装置５４５及び動的負荷バランス調整器５５５を更に含む。統計データ収集エンジン５４０、負荷バランス調整器５５５及びＲＸ／ＴＸスレッド（不図示）は、いくつかの実施形態のキュー管理システムを部分的に形成する。統計データ収集エンジン５４０により収集される統計データは、プールにキューを割り当てるタイミング及びプールを調整するタイミングを判定するために必要な情報を負荷バランス調整器に提供する。
【０１０７】
異なる実施形態において、統計データ収集エンジンは異なるソースから統計データを取得する。例えばいくつかの実施形態において、当該エンジンは、ＣＰＵスケジューラ５２５（ＣＰＵ使用量の場合）及びＲＸ／ＴＸスレッド（ネットワークトラフィックの場合）のいずれかから統計データをプルするか又はプッシュされた統計データを受信する。ネットワークトラフィックの場合、仮想化レイヤは、ネットワークスタックの各レイヤ（すなわち、ＲＸ／ＴＸスレッドにより管理される各モジュール）を含む種々のソースから収集される統計データ（スループット、パケットレート、パケットドロップ等）を有する。
【０１０８】
いくつかの実施形態において、統計データ収集エンジンは、ＰＮＩＣのパケットレート、ＰＮＩＣのスループット、並びにＲＸ／ＴＸスレッド毎のＣＰＵ使用量であるネットワークの統計データを負荷バランス調整器のために収集する。いくつかの実施形態において、ＲＸ／ＴＸスレッドが実際にＰＮＩＣと通信し且つ正確な数値を有するスレッドであるため、ＣＰＵスケジューラはＣＰＵ使用量データを更新し、ＲＸ／ＴＸスレッドはＰＮＩＣのパケットレート及びスループットを更新する。いくつかの実施形態において、ＰＮＩＣドライバモジュールがキュー選択器の下位に存在する。当該ＰＮＩＣドライバは、ＰＮＩＣと通信し且つＰＮＩＣの負荷の統計データを更新するモジュールである。また、いくつかの実施形態において、統計データ収集エンジンは、負荷バランス調整器のためにＰＮＩＣの統計データを収集するのに加えて、ＶＮＩＣの統計データ又は非ＶＭアドレス指定可能なノードにより収集される統計データを更に収集する。
【０１０９】
収集された統計データに依存することにより、負荷バランス調整器は、パケットレートが何らかの閾値を上回る場合又は同一のキューを共有する１つ以上の他のノードのスループットにより悪影響を受けている場合、待ち時間の影響を受けやすい（ＶＭ又は非ＶＭ）アドレス指定可能なノードを専用キュー又は優先度の高いプールに移動すると決定できる。更に一般的に、負荷バランス調整器５５５は収集された統計データを使用して、どのキューをどのアドレス指定可能なノードに割り当てるか、プールにキューを動的に割り当てるタイミング及びプールを動的に調整するタイミングを判定する。
【０１１０】
いくつかの実施形態において、負荷バランス調整器は、負荷バランス調整処理を周期的（例えば、数秒毎、数ミリ秒毎、数マイクロ秒毎等）に実行する。この処理は、統計データ収集エンジンが保持する「負荷統計データ」記憶装置５４５から統計データをプルし、これらの統計データに基づいて、アドレス指定可能なノードをキューに割り当てる必要があるか、プールのサイズを変更する必要があるか及び／又はキューを優先的に使用する必要があるかを判定する。負荷バランス調整器は、特定のキュー識別子と出力トラフィックの特定の送信元ＭＡＣアドレス及び入力トラフィックの特定の宛先ＭＡＣアドレスとを関連付けるようにＰＮＩＣ及び仮想化レイヤのフィルタを構成することにより、ノードをキューに割り当てる。ＰＮＩＣのＭＡＣフィルタを構成するために、負荷バランス調整器は、ＰＮＩＣドライバのＡＰＩを使用してキュー毎にフィルタ及びハードウェア特徴をプログラムする。
【０１１１】
図１３に示すように、負荷バランス調整器は、プール５６１、キューバランス再調整器５５９及びプールバランス再調整器５５７である３つのモジュールを有する。プールは、負荷バランス調整器が定義するＰＮＩＣキューのソフトウェアの抽象的グループ化である。負荷バランス調整器は、異なる処理を適用して異なる「プール」内のキューを管理する。そのため、各プールを同一の「特徴」を有するキューのセットであると見ることができる。この場合、特徴はハードウェア特徴（ＲＳＳ／ＬＲＯ等）と同様である。そのような特徴の例は、ＶＭの要件（短い待ち時間又は低い割込み率等）を含む。
【０１１２】
異なる処理を適用して異なるプール内のキューを管理することにより、負荷バランス調整器は、異なるプールに対して異なる方法でキューの割り当て及びプールのサイズ変更を最適化できる。プールバランス再調整器５５７は、プールのリソース割り当て基準に基づいて各プールのサイズを変更し、必要に応じて他のプールのキューを優先的に使用する。そのようなリソース割り当て基準の例は、プールのキューの最大数／最小数、プールのＣＰＵ総使用量、プールのネットワークトラフィック、プールのサービス品質（ＱｏＳ）制約等を含む。キューバランス再調整器５５９は、プールのバランス再調整基準に基づいて、同一プール内のキューのバランスを再調整する。そのようなプールのバランス再調整基準の例は、可能な限り少ないキューにアドレス指定可能なノードを集約すること（例えば、ＨＬＴプールの場合）、可能な限り多くのキューにアドレス指定可能なノードを分散すること（例えば、ＬＬＲプールの場合）等である。いくつかの実施形態において、負荷バランス調整器５５５は、上記の図６〜図９を参照して上述した処理と同様の処理を使用することにより、ＰＮＩＣキューを管理してＶＭ及び非ＶＭアドレス指定可能なノードを処理する。これらの実施形態のいくつかにおいて、これらの処理は、ＶＭのトラフィックに加えて非ＶＭアドレス指定可能なノードとの間のトラフィック（例えば、マウンタ１３０５及び１３０７、並びにマイグレータ１３０９との間のトラフィック）を監視し且つ管理するように変更される。
【０１１３】
Ｂ．異なる種類のパケットを区別するための別のフィルタリング
ＭＡＣアドレスフィルタリングの代わりに、いくつかの実施形態は、例えば異なる種類のパケットのセットに対して異なるプールを定義し、各プールを異なる方法で管理し、プール内のキューを動的に変更し且つ異なる種類のデータトラフィックを動的に再割り当てするために、他のフィルタリング技術を使用して異なる種類のパケットを異なる方法で処理する。例えば非ＭＡＣパケット識別子に基づいて、いくつかの実施形態の方法は、ホスト装置のＮＩＣを介する第１の種類のデータトラフィックを識別し且つ監視する。方法は、監視に基づいて第１の種類のデータトラフィックに対するプールを指定し、キューのセットをプールに割り当てる。その後、方法は、非ＭＡＣアドレスフィルタリングを使用して、第１の種類のデータトラフィックを割り当てられたキューのセットに向ける。
【０１１４】
その代わりに又はそれに加えて、方法は、監視に基づいて非ＭＡＣパケット識別子を介して識別される第１の種類のデータトラフィックに対するプールに割り当てられたキューのセットを変更できる。そのような変更の例は、プールのキューのうちの１つ以上が過剰に使用されるか又は十分に使用されない場合にプールにキューを追加するか又はプールからキューを除去することを含む。いくつかの実施形態において、方法は、例えば上述の優先的使用方法のうちの１つを使用して、別のプールのキューを優先的に使用することによりプールにキューを追加する。
【０１１５】
また、上述の動作の代わりに又はそれに加えて、方法は、監視に基づいて第１の種類のデータトラフィックをプール内の第１のキューからプール内の第２のキューに再割り当てできる。例えばいくつかの実施形態の方法は、監視に基づいて第１のキューを介する第１の種類のデータトラフィックが最小閾値トラフィック量を下回る（例えば、ある期間の間）ことを検出する。この使用が十分ではないため、方法は当該トラフィックを第２のキューに切り替える。この切り替えを行う前に、いくつかの実施形態の方法は、第２のキューを介するトラフィックが最大閾値トラフィック量を上回らないことを判定する。
【０１１６】
あるいは、いくつかの実施形態の方法は、監視に基づいて第１のキューを介する第１の種類のデータトラフィックが最大閾値トラフィック量を上回る（例えば、ある期間の間）ことを検出してもよい。この過剰な使用のため、方法は、第１の種類のデータトラフィックを第１のキューから第２のキューに切り替える。この場合も、この切り替えを行う前に、いくつかの実施形態の方法は、第２のキューを介するトラフィックが最大閾値トラフィック量を上回らないことを判定する。
【０１１７】
異なる実施形態は、異なる非ＭＡＣフィルタリングを使用する。いくつかの実施形態は、パケットヘッダのデータを使用して、パケットのペイロードを複数の種類のうちの１つであると分類する。例えばいくつかの実施形態は、Ｌ３及びＬ４パケットヘッダ内の５タプルＩＰデータを使用して、パケットのペイロードを分類する。５タプルデータは、送信元ポート識別子、宛先ポート識別子、送信元ＩＰアドレス、宛先ＩＰアドレス及びプロトコルを含む。これらの５つの識別子を使用して、いくつかの実施形態のフィルタは、ＩＰパケットがＶＯＩＰパケット、ビデオパケット、音声パケット、ＦＴＰパケット、ＨＴＴＰパケット、ＨＴＴＰＳパケット、リモートデスクトップパケット（ＰＣｏＩＰ、ＶＮＣ、ＲＤＰ）、管理パケット（認証、サーバの健康状態の監視、時刻同期）、電子メールパケット（ＰＯＰ３、ＳＭＴＰ）等の任意の数の異なる種類であると指定する。これらのプロトコルの全てが異なるトラフィックパターンを有するため、いくつかの実施形態は、それらのうちの１つ以上を異なるキュープールに分離し、異なる最適化基準を使用してデータトラフィックを各プール内のキューに割り当てる。
【０１１８】
以下に提供するリストは、プロトコル−ｓｒｃ＿ｉｐ−ｄｓｔ＿ｉｐ−ｓｒｃ＿ｐｏｒｔ−ｄｅｓｔ＿ｐｏｒｔの表記を使用することにより、ウェブトラフィック、ＶｏＩＰ、ビデオストリーミング、リモートデスクトップ、管理、電子メールを区別するために５タプルを使用できる方法を示す。この場合、＊はワイルドカード検索を表す。当該リストにおいて、ＶＭはサーバからのサービス／データ／サービスを要求するクライアントであると仮定する。
・ウェブ（Ｗｅｂ）：ＴＣＰ−＊−＊−＊−８０／４４３（ＨＴＴＰの場合は８０であり、ＨＴＴＰＳの場合は４４３である）
・ＶｏＩＰ（スカイプ）：ＴＣＰ／ＵＤＰ−＊−＊−２３３９９−＊又はＴＣＰ／ＵＤＰ−＊−＊−＊−２３３９９（入力及び出力トラフィック）
・ビデオストリーミング（ＭＭＳ）：ＴＣＰ／ＵＤＰ−＊−＊−＊−１７５５
・リモートデスクトップ（ＰＣｏＩＰ）：ＴＣＰ／ＵＤＰ−＊−＊−＊−４１７２
・認証（ケルベロス）：ＴＣＰ／ＵＤＰ−＊−＊−＊−８８
・電子メール（ＰＯＰ３）：ＴＣＰ−＊−＊−＊−１１０
【０１１９】
図１４及び図１５は、いくつかの実施形態が５タプルフィルタを使用して、ビデオの提示中に仮想マシンにより送信又は受信されるＶＯＩＰパケット及びビデオパケットを区別することを示す例を示す。図１４は、ＶＭ１４０５により送信されているＶＯＩＰパケット及びビデオパケットを区別するために５タプルが使用される例を示す。本例において、動的負荷バランス調整器５５５は、ＶＯＩＰパケットをＶＭ１４０５から優先度の高いキュープール１４２０にルーティングするようにキュー選択器５１８内の１つの５タプルフィルタセット１４１０を設定し、ビデオパケットを当該ＶＭから優先度の低いキュープール１４２５にルーティングするように別の５タプルフィルタセットを設定する。
【０１２０】
図１５は、ＶＭ１４０５により受信されているＶＯＩＰパケット及びビデオパケットを区別するために５タプルが使用される例を示す。本例において、動的負荷バランス調整器５５５は、入力ＶＯＩＰパケット（ＶＭ１４０５に対する）を優先度の高いキュープール１４２０にルーティングするようにＰＮＩＣ５１５のＲＸ処理エンジン５１１内の１つの５タプルフィルタセット１５１０を設定し、入力ビデオパケット（ＶＭ１４０５に対する）を優先度の低いキュープール１４２５にルーティングするように別の５タプルフィルタセットを設定する。
【０１２１】
負荷バランス調整器５５５は、キューをプールにグループ化するために５タプルフィルタを設定し、異なる基準に基づいてそれらを管理する。詳細には、統計データ記憶装置５４５内の収集された統計データに依存することにより、負荷バランス調整器５５５は、どのアドレス指定可能なノードをどのキューに割り当てるか、プールにキューを動的に割り当てるタイミング、プールからキューを動的に除去するタイミング、並びにアドレス指定可能なノードを新しいキューに動的に再割り当てするタイミングを判定できる。
【０１２２】
いくつかの実施形態において、負荷バランス調整器は、負荷バランス調整処理を周期的（例えば、数秒毎、数ミリ秒毎、数マイクロ秒毎等）に実行する。この処理は、統計データ収集エンジンが保持する「負荷統計データ」記憶装置５４５から統計データをプルし、これらの統計データに基づいて、アドレス指定可能なノードをキューに割り当てる必要があるか、プールのサイズを変更する必要があるか及び／又はキューを優先的に使用する必要があるかを判定する。負荷バランス調整器は、特定のキュー識別子と特定の５タプルフィルタとを関連付けるようにＰＮＩＣ及び仮想化レイヤの５タプルフィルタを構成することにより、ノードをキューに割り当てる。ＰＮＩＣのフィルタを構成するために、負荷バランス調整器は、ＰＮＩＣドライバのＡＰＩを使用してキュー毎にフィルタ及びハードウェア特徴をプログラムする。
【０１２３】
図５及び図１３を参照して上述したように、いくつかの実施形態において、図１４及び図１５の仮想化レイヤ内の負荷バランス調整器５５５は、３つのモジュール（不図示）を有する。これらの３つのモジュールは、（１）プール、それらに関連付けられたキューの識別子及び各キューに関連付けられたアドレス指定可能なノードを格納する記憶装置、（２）キューバランス再調整器、並びに（３）プールバランス再調整器である。
【０１２４】
図１４及び図１５の負荷バランス調整器５５５は、異なる処理を適用して異なる「プール」内のキューを管理する。そのため、各プールを同一の「特徴」を有するキューのセットであると見ることができる。異なる処理を適用して異なるプール内のキューを管理することにより、負荷バランス調整器は、異なるプールに対して異なる方法でキューの割り当て及びプールのサイズ変更を最適化できる。プールバランス再調整器は、プールのリソース割り当て基準に基づいて各プールのサイズを変更し、必要に応じて他のプールのキューを優先的に使用する。そのようなリソース割り当て基準の例（例えば、プールのキューの最大数／最小数、プールのＣＰＵ総使用量、プールのネットワークトラフィック、プールのサービス品質（ＱｏＳ）制約等）は上述した。
【０１２５】
キューバランス再調整器は、可能な限り少ないキューにアドレス指定可能なノードを集約すること（例えば、ＨＬＴプールの場合）、可能な限り多くのキューにアドレス指定可能なノードを分散すること（例えば、ＬＬＲプールの場合）等であるプールのバランス再調整基準に基づいて、同一プール内のキューのバランスを再調整する。いくつかの実施形態において、図１４及び図１５の負荷バランス調整器５５５は、上記の図６〜図９を参照して上述した処理と同様の処理を使用することにより、ＰＮＩＣキューを管理してＶＭ及び非ＶＭアドレス指定可能なノードを処理する。これらの実施形態のいくつかにおいて、これらの処理は、ＶＭのトラフィックに加えて非ＶＭアドレス指定可能なノードとの間のトラフィックを監視し且つ管理するように変更される。
【０１２６】
Ｖ．電子システム
上述の特徴及びアプリケーションの多くは、コンピュータ可読記憶媒体（コンピュータ可読媒体とも呼ぶ）に記録された命令セットとして指定されるソフトウェア処理として実現される。１つ以上の処理装置（例えば、１つ以上のプロセッサ、プロセッサのコア又は他の処理装置）により実行される場合、これらの命令は、命令において示される動作を処理装置に実行させる。コンピュータ可読媒体の例は、ＣＤ−ＲＯＭ、フラッシュドライブ、ＲＡＭチップ、ハードドライブ、ＥＰＲＯＭ等を含むがそれらに限定されない。コンピュータ可読媒体は、無線又は有線接続を介する搬送波及び電子信号を含まない。
【０１２７】
本明細書において、用語「ソフトウェア」は、プロセッサにより処理するためにメモリに読み込み可能である読出し専用メモリに常駐するファームウェア又は磁気記憶装置に格納されたアプリケーションを含むことを意図する。また、いくつかの実施形態において、複数のソフトウェア発明は、残りの部分が異なるソフトウェア発明である大きいプログラムの一部として実現可能である。いくつかの実施形態において、複数のソフトウェア発明は、別個のプログラムとしても実現可能である。最後に、本明細書中で説明する処理を共に実現する別個のプログラムの何らかの組み合わせは、本発明の範囲内である。いくつかの実施形態において、１つ以上の電子システムにおいて動作するためにインストールされる場合、プログラムは、ソフトウェアプログラムの動作を実行する１つ以上の特定のマシンの実現を定義する。
【０１２８】
図１６は、本発明のいくつかの実施形態が実現される電子システム１６００を概念的に示す。電子システム１６００は、上述のホスト装置のいずれかであってもよい。本システムは、上述の処理及び／又はキュー管理システムのうちのいずれかを実行する装置のいずれかであってもよい。電子システム１６００は、コンピュータ（例えば、デスクトップコンピュータ、パーソナルコンピュータ、タブレットコンピュータ、サーバコンピュータ、大型コンピュータ、ブレードコンピュータ等）、電話、ＰＤＡ又は他の何らかの種類の電子装置であってもよい。そのような電子システムは、種々のコンピュータ可読媒体と、種々の他のコンピュータ可読媒体に対するインタフェースとを含む。電子システム１６００は、バス１６０５、処理装置１６１０、システムメモリ１６２５、読出し専用メモリ１６３０、固定記憶装置１６３５、入力装置１６４０及び出力装置１６４５を含む。
【０１２９】
バス１６０５は、電子システム１６００の多くの内部装置を通信可能に接続する全てのシステムバス、周辺バス及びチップセットバスを一括して表す。例えばバス１６０５は、処理装置１６１０と、読出し専用メモリ１６３０、システムメモリ１６２５及び固定記憶装置１６３５とを通信可能に接続する。
【０１３０】
処理装置１６１０は、これらの種々の記憶装置から、本発明の処理を実行するために実行する命令及び処理するデータを検索する。異なる実施形態において、処理装置は単一のプロセッサであってもよく、あるいはマルチコアプロセッサであってもよい。
【０１３１】
読出し専用メモリ（ＲＯＭ）１６３０は、処理装置１６１０及び電子システムの他のモジュールが必要とする静的データ及び命令を格納する。それに対して、固定記憶装置１６３５は、読出し書込み記憶装置である。当該装置は、電子システム１６００の電源がオフである場合でも命令及びデータを格納する不揮発性記憶装置である。本発明のいくつかの実施形態は、固定記憶装置１６３５として大容量記憶装置（磁気ディスク又は光ディスク及びそれに対応するディスクドライブ等）を使用する。
【０１３２】
他の実施形態は、固定記憶装置として取外し可能記憶装置（フロッピディスク、フラッシュドライブ等）を使用する。固定記憶装置１６３５と同様に、システムメモリ１６２５は読出し書込み記憶装置である。しかし、記憶装置１６３５と異なり、システムメモリは、ランダムアクセスメモリ等の揮発性読出し書込みメモリである。システムメモリは、プロセッサが実行時に必要とする命令及びデータの一部を格納する。いくつかの実施形態において、本発明の処理は、システムメモリ１６２５、固定記憶装置１６３５及び／又は読出し専用メモリ１６３０に格納される。処理装置１６１０は、これらの種々の記憶装置から、いくつかの実施形態の処理を実行するために実行する命令及び処理するデータを検索する。
【０１３３】
バス１６０５は、入力装置１６４０及び出力装置１６４５に更に接続する。入力装置により、ユーザは電子システムに対して情報を通信し且つコマンドを選択できる。入力装置１６４０は、英数字キーボード及びポインティングデバイス（「カーソル制御装置」とも呼ぶ）を含む。出力装置１６４５は、電子システムにより生成される画像を表示する。出力装置は、プリンタ、並びにブラウン管（ＣＲＴ）又は液晶ディスプレイ（ＬＣＤ）等の表示装置を含む。いくつかの実施形態は、入力装置及び出力装置の双方として機能するタッチスクリーン等の装置を含む。
【０１３４】
最後に、図１６に示すように、バス１６０５は、ネットワークアダプタ（不図示）を介して電子システム１６００をネットワーク１６６５に更に結合する。このように、コンピュータは、コンピュータのネットワーク（ローカルエリアネットワーク（「ＬＡＮ」）、ワイドエリアネットワーク（「ＷＡＮ」）又はイントラネット等）の一部であってもよく、あるいはインターネット等のネットワークのネットワークの一部であってもよい。電子システム１６００のいずれか又は全ての構成要素が本発明に関連して使用されてもよい。
【０１３５】
いくつかの実施形態は、機械可読媒体又はコンピュータ可読媒体（あるいは、コンピュータ可読記憶媒体、機械可読媒体又は機械可読記憶媒体と呼ぶ）にコンピュータプログラム命令を格納するマイクロプロセッサ、記憶装置及びメモリ等の電子構成要素を含む。そのようなコンピュータ可読媒体のいくつかの例は、ＲＡＭ、ＲＯＭ、読出し専用コンパクトディスク（ＣＤ−ＲＯＭ）、記録可能コンパクトディスク（ＣＤ−Ｒ）、書換え可能コンパクトディスク（ＣＤ−ＲＷ）、読出し専用デジタル汎用ディスク（例えば、ＤＶＤ−ＲＯＭ、２層式ＤＶＤ−ＲＯＭ）、種々の記録可能／書換え可能ＤＶＤ（例えば、ＤＶＤ−ＲＡＭ、ＤＶＤ−ＲＷ、ＤＶＤ＋ＲＷ等）、フラッシュメモリ（例えば、ＳＤカード、ミニＳＤカード、マイクロＳＤカード等）、磁気ハードドライブ及び／又は固体ハードドライブ、読出し専用Ｂｌｕ−Ｒａｙ（登録商標）ディスク及び記録可能Ｂｌｕ−Ｒａｙ（登録商標）ディスク、超高密度光ディスク、他の何らかの光媒体又は磁気媒体、並びにフロッピディスクを含む。コンピュータ可読媒体は、少なくとも１つの処理装置により実行可能であり且つ種々の動作を実行するための命令セットを含むコンピュータプログラムを格納してもよい。コンピュータプログラム又はコンピュータコードの例は、コンパイラにより生成されるような機械コード、並びにインタープリタを使用するコンピュータ、電子構成要素又はマイクロプロセッサにより実行される高レベルコードを含むファイルを含む。
【０１３６】
上記の説明はソフトウェアを実行するマイクロプロセッサ又はマルチコアプロセッサを主に参照するが、いくつかの実施形態は、特定用途向け集積回路（ＡＳＩＣ）又はフィールドプログラマブルゲートアレイ（ＦＰＧＡ）等の１つ以上の集積回路により実行される。いくつかの実施形態において、そのような集積回路は、回路自体に格納される命令を実行する。
【０１３７】
本明細書中で使用される場合、用語「コンピュータ」、「サーバ」、「プロセッサ」及び「メモリ」は全て、電子装置又は他の技術装置を参照する。これらの用語は、人間又は人間のグループを含まない。本明細書の便宜上、用語「表示する」は、電子装置上に表示することを意味する。本明細書中で使用される場合、用語「コンピュータ可読媒体」及び「機械可読媒体」は全て、コンピュータが読み出せる形態で情報を格納する有形の物理物体に限定される。これらの用語は、無線信号、有線ダウンロード信号及び他の何らかの一時的な信号を含まない。
【０１３８】
多くの特定の詳細を参照して本発明を説明したが、本発明が本発明の主旨から逸脱せずに他の特定の形態で実現可能であることが当業者には認識されるだろう。更に、多くの図面（図６〜図９を含む）は処理を概念的に示す。これらの処理の特定の動作は、図示及び説明される正確な順序で実行されなくてもよい。特定の動作は、一連の連続する動作で実行される必要がなく、異なる実施形態において、異なる特定の動作が実行されてもよい。更に、処理は、複数のサブプロセスを使用して実現されてもよく、あるいは大きいマクロ処理の一部として実現されてもよい。
【図１】
0005905921.tif 000002
【図２】
0005905921.tif 000003
【図３】
0005905921.tif 000004
【図４】
0005905921.tif 000005
【図５】
0005905921.tif 000006
【図６】
0005905921.tif 000007
【図７】
0005905921.tif 000008
【図８】
0005905921.tif 000009
【図９】
0005905921.tif 000010
【図１０】
0005905921.tif 000011
【図１１】
0005905921.tif 000012
【図１２】
0005905921.tif 000013
【図１３】
0005905921.tif 000014
【図１４】
0005905921.tif 000015
【図１５】
0005905921.tif 000016
【図１６】
0005905921.tif 000017