(57)【要約】【課題】ホストコンピュータの物理ＮＩＣにおけるパケットスケジューリングを改善すること。【解決手段】ルートノード、中間ノード（Ｐ１、Ｐ２）、およびリーフノード（Ｖ１、Ｖ２、Ｖ３、Ｖ４）を備えたノード階層に従って仮想マシン（ＶＭ）にネットワーク帯域を割り当てる。各リーフノードは、ＶＭからのパケット送信リクエストのキューを表し、各中間ノードは、リーフキューの集合を表す。ＶＭがリクエストを生成してパケットをネットワーク上で送信する際、送信用パケットをリーフノードにキューイングし、ネットワーク帯域のノードへの割り当て量を表すトラッキングデータに基づいてパケットを送信するリーフノードを選択して、ネットワーク帯域を割り当てる。リーフノードの選択では、選択リーフノードのトラッキングデータおよび親ノードである中間ノードのトラッキングデータを更新し、コマンドを発行して選択リーフノードのパケットを送信する。【選択図】図１
2014220780.tif 000002
【特許請求の範囲】
【請求項１】
ルートノード、中間ノード、およびリーフノードを備えたノード階層に従ってネットワーク帯域の占有体に当該ネットワーク帯域を割り当てる方法であって、各リーフノードが、前記占有体のうちの１つからのパケット送信リクエストのキューを表し、各中間ノードが、１または複数のリーフキューの集合を表す、前記方法において、
送信用データパケットを前記リーフノードにキューイングすること、
前記ノードの帯域割り当てデータに基づいてデータパケットを送信するリーフノードを選択することであって、当該ノードの帯域割り当てデータが、ネットワーク帯域の当該ノードへの割り当て量を表すトラッキングデータを含む、前記リーフノードを選択すること、
前記リーフノードの選択に際して、当該選択リーフノードのトラッキングデータおよび当該選択リーフノードの親ノードである中間ノードのトラッキングデータを更新し、コマンドを発行して当該選択リーフノードのデータパケットを送信することを備える、方法。
【請求項２】
前記リーフノードの選択に際して、送信する前記データパケットを当該選択リーフノードから削除することをさらに含む、請求項１に記載の方法。
【請求項３】
前記帯域割り当てデータが前記各リーフノードの帯域予約をさらに含み、前記リーフノードの選択時に、当該選択リーフノードの帯域予約を満たしていない、請求項１に記載の方法。
【請求項４】
リーフノードのトラッキングデータが、所定長さの先行時間に当該リーフノードに割り当てられた総予約帯域量を示す当該リーフノードの現行予約帯域合計を含み、
当該リーフノードが選択された場合、当該選択リーフノードの現行予約帯域合計がその帯域予約以下である、請求項３に記載の方法。
【請求項５】
前記更新することが、前記選択リーフノードの現行予約帯域合計を更新することを含む、請求項４に記載の方法。
【請求項６】
前記更新することが、前記選択リーフノードの現行予約帯域合計および当該選択リーフノードの少なくとも１つの先行ノードの現行予約帯域合計を更新することを含む、請求項４に記載の方法。
【請求項７】
前記帯域割り当てデータが、前記各リーフノードの帯域限界をさらに含み、前記リーフノードの選択時に、当該選択リーフノードの帯域限界を上回っていない、請求項４に記載の方法。
【請求項８】
前記各リーフノードのトラッキングデータが、所定長さの先行時間に親ノードとして同じ中間ノードを共有している他のノードまたはノード群に対して当該各リーフノードに付与される帯域割り当て優先度を示す現行占有合計を含み、
当該リーフノードが選択された場合、当該選択リーフノードの現行占有合計が前記他のノードまたはノード群の各現行占有合計以下である、請求項１に記載の方法。
【請求項９】
前記各リーフノードおよび前記各中間ノードのトラッキングデータが、所定長さの先行時間に当該各ノードに割り当てられた総帯域量を示す現行帯域合計を含み、
前記更新することは、
前記選択リーフノードの現行帯域合計を更新すること、
当該選択リーフノードの先行ノードであるすべての中間ノードの現行帯域合計を更新することを含む、請求項８に記載の方法。
【請求項１０】
前記帯域割り当てデータが、前記各ノードの帯域限界をさらに含み、
前記リーフノードの選択時に、当該選択リーフノードおよびその先行ノードであるすべての中間ノードの帯域限界をいずれも上回っていない、請求項９に記載の方法。
【請求項１１】
１または複数のネットワークインターフェースコントローラ（ＮＩＣ）と、当該ＮＩＣを共有して内部動作する仮想マシンと、ルートノード、中間ノード、およびリーフノードを備えたノード階層に従って当該仮想マシンに当該ＮＩＣを通して有効なネットワーク帯域を割り当てるパケットスケジューラとを有するコンピュータシステムであって、
各リーフノードが前記仮想マシンのうちの１つからのパケット送信リクエストのキューを表し、各中間ノードが１または複数のリーフキューの集合を表し、前記パケットスケジューラが、
送信用データパケットを前記リーフノードにキューイングすること、
前記ノードの帯域割り当てデータに基づいてデータパケットを送信するリーフノードを選択することであって、当該ノードの帯域割り当てデータがネットワーク帯域の当該ノードへの割り当て量を表すトラッキングデータを含むこと、
前記リーフノードの選択に際して、当該選択リーフノードのトラッキングデータおよび当該選択リーフノードの親ノードである中間ノードのトラッキングデータを更新し、コマンドを生成して当該選択リーフノードのデータパケットを送信すること、
を含む方法を実行するように構成された、コンピュータシステム。
【請求項１２】
前記帯域割り当てデータが前記各リーフノードの帯域予約および帯域限界をさらに含み、
前記リーフノードの選択時に、当該選択リーフノードの帯域予約を満たさず、当該選択リーフノードの帯域限界を上回っていない、請求項１１に記載のコンピュータシステム。
【請求項１３】
前記更新することは、
前記選択リーフノードの現行予約帯域合計および当該選択リーフノードの先行ノードである少なくとも１つの中間ノードの現行予約帯域合計を更新することを含む、請求項１２に記載のコンピュータシステム。
【請求項１４】
前記各リーフノードのトラッキングデータが、所定長さの先行時間に親ノードとして同じ中間ノードを共有している他のノードまたはノード群に対して当該各リーフノードに付与される帯域割り当て優先度を示す現行占有合計を含み、
当該リーフノードの選択時に、当該選択リーフノードの現行占有合計が前記他のノードまたはノード群の各現行占有合計以下である、請求項１１に記載のコンピュータシステム。
【請求項１５】
前記帯域割り当てデータが、前記各リーフノードの帯域限界をさらに含み、前記リーフノードの選択時に、当該選択リーフノードの帯域限界を上回っていない、請求項１４に記載のコンピュータシステム。
【請求項１６】
１または複数のネットワークインターフェースコントローラ（ＮＩＣ）と、当該ＮＩＣを共有して内部動作するプロセスと、ルートノード、中間ノード、およびリーフノードを備えたノード階層に従って仮想マシンにＮＩＣを通して有効なネットワーク帯域を割り当てるパケットスケジューラとを有するコンピュータシステムで実行される命令を含む持続性コンピュータ可読媒体であって、各リーフノードが前記プロセスのうちの１つからのパケット送信リクエストのキューを表し、各中間ノードが１または複数のリーフキューの集合を表し、前記パケットスケジューラが、
送信用データパケットを前記リーフノードにキューイングすること、
前記ノードの帯域割り当てデータに基づいてデータパケットを送信するリーフノードを選択することであって、当該ノードの帯域割り当てデータがネットワーク帯域の当該ノードへの割り当て量を表すトラッキングデータを含むこと、
前記リーフノードの選択に際して、当該選択リーフノードのトラッキングデータおよび当該選択リーフノードの親ノードである中間ノードのトラッキングデータを更新し、コマンドを発行して当該選択リーフノードのデータパケットを送信すること、
を含む方法を実行するように構成された持続性コンピュータ可読媒体。
【請求項１７】
前記帯域割り当てデータが前記各リーフノードの帯域予約および帯域限界をさらに含み、
前記リーフノードの選択時に、当該選択リーフノードの帯域予約を満たさず、当該選択リーフノードの帯域限界を上回っていない、請求項１６に記載の持続性コンピュータ可読媒体。
【請求項１８】
前記更新することは、
前記選択リーフノードの現行予約帯域合計および当該選択リーフノードの先行ノードである少なくとも１つの中間ノードの現行予約帯域合計を更新することを含む、請求項１７に記載の持続性コンピュータ可読媒体。
【請求項１９】
前記各リーフノードのトラッキングデータが、所定長さの先行時間に親ノードとして同じ中間ノードを共有している他のノードまたはノード群に対して当該各リーフノードに付与される帯域割り当て優先度を示す現行占有合計を含み、当該リーフノードの選択時に、当該選択リーフノードの現行占有合計が前記他のノードまたはノード群の各現行占有合計以下である、請求項１６に記載の持続性コンピュータ可読媒体。
【請求項２０】
前記帯域割り当てデータが前記各リーフノードの帯域限界をさらに含み、前記リーフノードの選択時に、当該選択リーフノードの帯域限界を上回っていない、請求項１９に記載の持続性コンピュータ可読媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
クオリティ・オブ・サービスのためのネットワーク帯域の階層割り当てに関する。
【背景技術】
【０００２】
仮想コンピュータ環境では、複数の仮想マシン（ＶＭ：Ｖｉｒｔｕａｌ  Ｍａｃｈｉｎｅ）が１つの物理プラットフォーム上で動作可能であるとともに、物理プラットフォームの物理リソース（ハードウェア等）を共有可能である。ＶＭは、仮想上のコンピュータの仕様に基づくものであってもよいし、現実世界のコンピュータのアーキテクチャおよび機能をエミュレートするものであってもよい。ＶＭのインスタンスを作成する通常の物理プラットフォームまたはサーバ（ホストコンピュータまたはホストとも称する）は、中央演算処理装置（ＣＰＵ）、ランダムアクセスメモリー（ＲＡＭ）、ネットワークインターフェースカード（ＮＩＣ：Ｎｅｔｗｏｒｋ  Ｉｎｔｅｒｆａｃｅ  Ｃａｒｄ）、およびストレージアクセス用のホストバスアダプタ（ＨＢＡ：Ｈｏｓｔ  Ｂｕｓ  Ａｄａｐｔｅｒ）を備えている。サーバが大型化すると、１つのサーバ上に数十〜数百のＶＭが実装される仮想データセンターにスケールメリットが生じて、コストが抑えられるとともに稼働率が向上する。
【０００３】
ＶＭの実行には、ハイパーバイザおよびその内部に実装された仮想マシンモニター（ＶＭＭ：Ｖｉｒｔｕａｌ  Ｍａｃｈｉｎｅ  Ｍｏｎｉｔｏｒ）が対応する。ハイパーバイザは、ＶＭ間での物理リソースの共有を制御する。また、ＣＰＵリソースおよびメモリーリソースを管理するため、ハイパーバイザのスケジューラには、何らかの重み付けに基づく割り当てを実装して、レイテンシの影響を受けやすいＶＭを優先するようにしてもよい。ただし、残念ながら、ＣＰＵリソースおよびメモリーリソースを管理する技術は、ＮＩＣの有効なネットワーク帯域のスケジューリングに直接適用することはできない。
【０００４】
その代わりに、ネットワーク帯域のスケジューリング管理用に実装されるハイパーバイザの従来のパケットスケジューラは、各ＶＭの保証スループットを規定するクオリティ・オブ・サービス（ＱｏＳ：Ｑｕａｌｉｔｙ  ｏｆ  Ｓｅｒｖｉｃｅ）モデルに従うものであってもよい。ハイパーバイザは、ＱｏＳモデルを用いて、（１または複数の）特定のＶＭに関してレイテンシが規定レベルを超えないように保証を試みる。一例としては、トラヒックシェーパーを用いて、制限および重み付けに基づく割り当てのうちの少なくとも一方を強制するようにしてもよい。重み付けに基づく割り当てを採用した場合は、有効なネットワーク帯域が広いか又は一定の状態を維持している限り、上記保証に従ってネットワーク帯域を提供可能である。有効なネットワーク帯域が狭いか又は変動する場合は、上記保証を満足するために重み付けの調整が必要となることがある。
【０００５】
従来のパケットスケジューラは、十分に満足できるものであった。これは主に、ネットワークが過剰な場合が多く、サーバにおけるＮＩＣの物理的な飽和が起こり難いためである。ただし、いくつかの理由で、そのような状況も急速に変わりつつある。第１に、サーバの演算処理コアの数が増え、メモリーサイズも大きくなっていることから、サーバ当たりの連結された割当量（consolidation rations）が大きくなっている。２つの演算処理コアを用いると、１キロバイト（ＫＢ：Ｋｉｌｏｂｙｔｅ）以上のパケットサイズを扱う１０ギガビット／秒（Ｇｂｐｓ：Ｇｉｇａｂｉｔ  ｐｅｒ  ｓｅｃｏｎｄｓ）ＮＩＣがすぐに飽和してしまうことが分かっている。第２に、ネットワークアタッチトストレージ（ＮＡＳ：Ｎｅｔｗｏｒｋ−ａｔｔａｃｈｅｄ  ｓｔｏｒａｇｅ）システム等のようにＮＩＣを介してストレージにアクセスする場合、半導体ドライブ（ＳＳＤ：Ｓｏｌｉｄ−Ｓｔａｔｅ  Ｄｒｉｖｅ）の改良によりストレージ性能が向上している。ストレージアレイにＳＳＤを採用することで、ディスクの貧弱なランダム入出力性能によって１秒当たりの入出力動作（ＩＯＰＳ：Ｉｎｐｕｔ−ｏｕｔｐｕｔ  ｏｐｅｒａｔｉｏｎｓ  ｐｅｒ  ｓｅｃｏｎｄｓ）が制限されることはなくなり、ＳＳＤ階層中の高いヒット率（≧９５％）によって、ＮＩＣの帯域占有量が大幅に増加している。第３に、ＶＭおよび仮想ディスクのライブマイグレーション等の管理用途の実行に際し、仮想環境において、管理用トラヒックがかなりの帯域を占有している。第４に、集中型のストレージアーキテクチャが一般的になり、サーバを跨ぐローカルストレージが集約されて、ＮＩＣ経由でアクセス可能な共有ストレージデバイスが提供されている。
【０００６】
以上から、ネットワーク上で利用可能な物理リソースの消費増大により、ホストコンピュータ上の物理ＮＩＣにおけるパケットスケジューリングの改善が必要となっている。
【発明の概要】
【課題を解決するための手段】
【０００７】
実施形態は、加重または占有比に基づく階層割り当て、最小保証または予約、最大限界、および予備帯域の優先割り当てに対応するように物理ＮＩＣ経由で送信されるパケットのスケジューリングを行うクオリティ・オブ・サービス（ＱｏＳ）モデルを提供する。
【０００８】
一実施形態によれば、ルートノード、中間ノード、およびリーフノードを備えたノード階層に従って仮想マシンまたはその他の帯域占有体にネットワーク帯域を割り当て、各リーフノードが上記仮想マシンまたはその他の帯域占有体のうちの１つからのパケット送信リクエストの（１または複数の）キューを表し、各中間ノードが１または複数のリーフキューの集合を表す。仮想マシンまたはその他の帯域占有体がリクエストを生成してデータパケットをネットワーク上で送信する際には、送信用データパケットを上記リーフノードにキューイングし、ネットワーク帯域のノードへの割り当て量を表すトラッキングデータを含む当該ノードの帯域割り当てデータに基づいてデータパケットを送信するリーフノードを選択することによってネットワーク帯域を割り当てる。上記リーフノードの選択に際しては、当該選択リーフノードのトラッキングデータおよび当該選択リーフノードの親ノードである中間ノードのトラッキングデータを更新し、コマンドを発行して当該選択リーフノードのデータパケットをＮＩＣ経由で送信する。
【０００９】
別の実施形態としては、コンピュータシステムによる上記方法の１または複数の態様の実行を可能とする命令を含む持続性コンピュータ可読記憶媒体のほか、上記方法の１または複数の態様を実行するように構成されたコンピュータシステム等が挙げられるが、これらに限定されない。
【図面の簡単な説明】
【００１０】
【図１】１または複数の実施形態を実装可能な仮想コンピュータシステムの概念図である。
【図２】１または複数の実施形態における、ネットワーク帯域を割り当てるリソース割り当て階層を示した図である。
【図３】一実施形態に係る、パケットをキューイングしてスケジューリングする方法の各工程を示したフローチャートである。
【図４】一実施形態に係る、キューをアクティブにする方法の各工程を示したフローチャートである。
【図５】一実施形態に係る、送信用パケットをスケジューリングする方法の各工程を示したフローチャートである。
【図６】一実施形態に係る、パケットをスケジューリングして送信するキューを選択する方法の各工程を示したフローチャートである。
【図７】一実施形態に係る、パケットをスケジューリングして送信する際にキューのトラッキングデータを更新する方法の各工程を示したフローチャートである。
【図８Ａ】図３〜図７の方法に対応した疑似コードである。
【図８Ｂ】図３〜図７の方法に対応した疑似コードである。
【図８Ｃ】図３〜図７の方法に対応した疑似コードである。
【図８Ｄ】図３〜図７の方法に対応した疑似コードである。
【図８Ｅ】図３〜図７の方法に対応した疑似コードである。
【図８Ｆ】図３〜図７の方法に対応した疑似コードである。
【発明を実施するための形態】
【００１１】
図１は、１または複数の実施形態を実装可能な仮想コンピュータシステムの概念図である。この仮想コンピュータシステムは、１または複数のクライアント１０２、１または複数の物理マシン１０８、およびＶＭ管理サーバ１０５等の機器を接続するネットワーク１０４を備えている。物理マシン１０８の一例としては、１または複数の仮想マシンが実行されるサーバーコンピュータが挙げられる。図示の例において、物理マシン１０８は、物理リンク１４９を介してその他の物理マシンおよびネットワーク１０４に接続された１または複数の物理ＮＩＣ（ｐＮＩＣ）１５０、メモリー１５２（ＲＡＭ等）、およびプロセッサ１５４（ＣＰＵ等）といった物理リソース１４８を備えている。仮想マシン管理サーバ１０５は、物理マシンのＶＭ設定およびＶＭ電源オン／オフを制御するとともに、内部動作するリソース管理ソフトウェアモジュール（図１には分散リソーススケジューラ（ＤＲＳ：Ｄｉｓｔｒｉｂｕｔｅｄ  Ｒｅｓｏｕｒｃｅ  Ｓｃｈｅｄｕｌｅｒ）１０６として示す）を有し、ハードウェアリソースをＶＭに割り当てるとともにＶＭ間でハードウェアリソース上の負荷を均衡させる。
【００１２】
物理マシン１０８は、物理リソース１４８上にインストールされたハイパーバイザ１３９を備えている。ハイパーバイザ１３９は、１または複数の仮想マシン（ＶＭ）１１０、１１２について、インスタンスの作成と実行を同時に行える仮想化ソフトウェアコンポーネントである。ハイパーバイザ１３９は、対応するＶＭのハードウェアリソースをエミュレートする仮想マシンモニター（ＶＭＭ）１２０、１３０を備えている。たとえば、図１においては、ＶＭＭ１２０がＶＭ１１０の仮想ディスク１２２および仮想ＮＩＣ１２４等のハードウェアリソースをエミュレートし、ＶＭＭ１３０がＶＭ１１２の仮想ディスク１４２および仮想ＮＩＣ１４４等のハードウェアリソースをエミュレートする。各ＶＭは、内部実装されたゲストオペレーティングシステム（ＯＳ）（ゲストＯＳ１１８、１２８等）を有しており、かかるゲストＯＳは、ＶＭで動作するゲストアプリケーション（ゲストＯＳ１１８上で実行されたアプリケーション１１４、１１６およびゲストＯＳ１２８上で実行されたアプリケーション１３４、１３６等）に対して仮想ハードウェアリソースへのインターフェースを提供している。ゲストＯＳの例としては、Ｍｉｃｒｏｓｏｆｔ  ＷＩＮＤＯＷＳ（登録商標）やＬＩＮＵＸ（登録商標）等の周知の汎用オペレーティングシステムが挙げられる。
【００１３】
また、ハイパーバイザ１３９は、ｖＮＩＣ１２４、１４４からｐＮＩＣ１５０およびｐＮＩＣ１５０からｖＮＩＣ１２４、１４４へのパケットの転送を扱う仮想スイッチ１３８を実装している。また、仮想スイッチ１３８にはパケットスケジューラ１３７が実装されており、特に実施形態によれば、ｐＮＩＣ１５０のネットワークリンク当たり１つのパケットスケジューラが備えられており、重み付けまたは占有比に基づく階層ネットワーク帯域割り当て、最小保証（minimum guarantees）または予約、最大限界（maximum limits）、および予備ネットワーク帯域の優先割り当てに対応するクオリティ・オブ・サービス（ＱｏＳ）モデルに準拠するように、ＶＭからｐＮＩＣ１５０経由で送信される送信パケットのスケジューリングを扱う。
【００１４】
当然のことながら、図１の仮想化コンポーネントの記述に用いる種々用語、階層、および分類は、それぞれの機能性もしくは本発明の精神または範囲を逸脱することなく別称してもよい。たとえば、ＶＭＭ１２０、１３０は、ＶＭ１１０、１１２とハイパーバイザ１３９間の別個の仮想化コンポーネントとみなしてもよい（このような考え方では、それ自体を仮想化「カーネル」コンポーネントとみなしてもよい）。これは、インスタンスを作成したＶＭに別個のＶＭＭが存在するためである。あるいは、各ＶＭＭは、対応する仮想マシンのコンポーネントとみなしてもよい。このようなＶＭＭは、当該仮想マシンのハードウェアエミュレーションコンポーネントを備えているためである。
【００１５】
図２は、１または複数の実施形態における、ネットワーク帯域（「帯域」と簡素化して称する場合もある）を割り当てるリソース割り当て階層を示した図である。図示のように、このリソース割り当て階層は、ルートノードと、リーフノードＶ１、Ｖ２、Ｖ３、Ｖ４の親ノードである２つの中間ノードＰ１、Ｐ２を備えている。中間ノードＰ１は、リーフノードＶ１、Ｖ２の親ノードである。中間ノードＰ２は、リーフノードＶ３、Ｖ４の親ノードである。各リーフノードは、異なるＶＭからのパケット送信リクエストの（１または複数の）キュー（queue）を表しており、本明細書ではリーフキュー（leaf queue）とも称する。各中間ノードは、リーフキューの集合を表しており、本明細書では中間キュー（intermediate queue）とも称する。
【００１６】
本明細書に記載のリソース割り当てモデルでは、中間キューおよびリーフキューのそれぞれにおいて、３つのリソース設定を規定する。かかる３つのリソース設定は予約、限界（limit）、占有である。あるキューの予約設定は、当該キューに保証される最小帯域割り当てを規定する。また、あるキューの限界設定は、当該キューに割り当て可能な最大帯域を規定する。さらに、あるキューの占有設定は、親キューとして同じ中間キューを共有している他のキューまたはキュー群に対して当該キューに付与される帯域割り当て優先度を規定する。本明細書では、同じ親キューを共有しているキューを兄弟キューと称する。たとえば、２つの兄弟キューがあって、第１および第２のキューの占有比が２対１の場合は、３００メガビット／秒（Ｍｂｐｓ：Ｍｂｉｔｓ／ｓｅｃｏｎｄ）の予備帯域容量がこの占有比に従って分割され、第１および第２のキューにそれぞれ２００Ｍｂｐｓおよび１００Ｍｂｐｓが割り当てられる。
【００１７】
キューにおける有効なリソース設定は、以下２つの制約を満足する。すなわち、（１）親キューにおける予約設定は、その子キューにおける予約設定の合計以上でなければならず、（２）各キューにおける限界設定は、当該キューにおける予約設定未満とはならない。また、パケットスケジューラ１３７は、予約設定に従って帯域を割り当てる。この割り当ては、あらゆる階層レベルにおいて以下の特性を満足する。すなわち、（１）パケットスケジューラ１３７は、各キューに対して、少なくとも当該キューの予約設定を割り当て、（２）パケットスケジューラ１３７は、各キューに対して、最大でも当該キューにおける限界設定を割り当てる。また、パケットスケジューラ１３７は、２つの異なるセマンティック（semantic）の一方に従って占有比を考慮することにより、予約設定を満足した後の予備帯域を割り当てる。これは、ＭＡＸ（Ｒ，Ｓ）セマンティックおよびＳＵＭ（Ｒ、Ｓ）セマンティックと称する場合がある。２つのセマンティックのいずれを選択するかは、パケットスケジューラ１３７のユーザー設定により指示される。
【００１８】
パケットスケジューラ１３７は、ＭＡＸ（Ｒ，Ｓ）セマンティックに従って、予約設定および限界設定を満足しつつ、占有比に比例して全体の割り当てを行う。たとえば、図２に示すリソース割り当て階層において、パケットスケジューラ１３７は、予約制約（０Ｍｂｐｓ、５００Ｍｂｐｓ）および限界制約（５００Ｍｂｐｓ、限界なし）を満足しつつ、キューＰ１、Ｐ２の占有比２：３に比例して１０００Ｍｂｐｓのネットワーク帯域を分割する。その結果、中間キューＰ１、Ｐ２の帯域割り当ては、それぞれ４００Ｍｂｐｓおよび６００Ｍｂｐｓとなる。同様に、パケットスケジューラ１３７は、子キューＶ１、Ｖ２の占有比設定１：２に従って、キューＰ１の４００Ｍｂｐｓをさらに分割する。ただし、パケットスケジューラ１３７は、キューＰ２の６００Ｍｂｐｓについては、子キューＶ３、Ｖ４にそれぞれ４００Ｍｂｐｓおよび２００Ｍｂｐｓを分割する。子キューＶ３、Ｖ４は、占有比設定が同じであることから３００Ｍｂｐｓずつを割り当てるべきところだが、キューＶ３の４００Ｍｂｐｓの予約設定を満足する必要がある。
【００１９】
パケットスケジューラ１３７は、ＳＵＭ（Ｒ，Ｓ）セマンティックに従って、まず初めに、子キューの予約設定に基づいてその親キューに帯域容量を割り当てる。そして、パケットスケジューラ１３７は、容量が残っていれば、限界制約に配慮しつつ占有比設定に基づいて、残存容量を割り当てる。たとえば、図２に示すリソース割り当て階層において、パケットスケジューラ１３７は、０＋（１０００−５００）＊２／５＝２００ＭｂｐｓをキューＰ１に、５００＋（１０００−５００）＊３／５＝８００ＭｂｐｓをキューＰ２に割り当てる。したがって、キューは、その占有比設定および任意の兄弟キューの占有比設定に基づいて、予約設定と予備帯域の一部とを得ることになる。
【００２０】
パケットスケジューラ１３７は、キュー当たり３つのタグのトラッキングおよび更新によって、パケットの送信スケジューリングを実時間で実行する。このタグには、予約タグ、限界タグ、および占有タグが含まれる。これらタグの値は、パケットスケジューラ１３７がスケジューリングするパケットを決定した場合に検知され、パケットのスケジューリングが行われた場合に更新される。これについては、以下に詳述する。特定キューの予約タグの値が現時点よりも小さい場合は、当該キューが最小帯域で割り当てられていないことを意味する。特定キューの限界タグの値が現時点よりも小さい場合は、当該キューが最大帯域で割り当てられていないことを意味する。また、特定キューの占有タグの値は、任意の（１つもしくは複数の）兄弟キューの占有タグの値と対比される。占有タグの値が小さいキューは、割り当てが優先される。
【００２１】
パケットスケジューラ１３７は、パケットのスケジューリングを行ったら、当該パケットのリーフキューに保持されたタグ値およびリーフキューの先行キューに保持されたタグ値を更新する。一般的に、タグ値の更新は、ｐＮＩＣ１５０が最終的にパケットを送信する場合に当該パケットが占有する帯域量を反映して増加させる。
【００２２】
実施形態に係るネットワーク帯域の割り当て方法は、図３に示すパケットをキューイングしてスケジューリングする方法、図４に示すキューをアクティブにする方法、図５に示す送信用パケットをスケジューリングする方法、および図６に示すパケットをスケジューリングして送信するキューを選択する方法に分けることができる。また、図７に示すように、パケットスケジューラ１３７は、パケットをスケジューリングして送信したら、当該許可パケットに対応するリーフノードに保持されたタグ値およびリーフキューの先行キューに保持されたタグ値を更新する。図８Ａ〜図８Ｆは、図３〜図７の方法に対応した疑似コードである。
【００２３】
実施形態によれば、パケットスケジューラ１３７は、ステップ３０２において新たなパケットを受信したら、ステップ３０４において、パケット送信をリクエストしているＶＭに付随のリーフキューに当該パケットを追加する。ステップ３０６において、このキューがアイドル状態と判定された場合は、ステップ３０８において当該キューをアクティブにする。その後、ステップ３１０において、パケットスケジューラ１３７は、図５に示す方法に従って、送信用パケットの新たなスケジューリングサイクルを開始する。ステップ３０６において、キューが既にアクティブであると判定された場合は、判定後にステップ３０８を飛ばしてステップ３１０を実行する。当然のことながら、如何なるＶＭから如何なる送信用パケットを受信しても、図５に示す方法に従った送信用パケットのスケジューリングが開始される。
【００２４】
図４に、ステップ３０８のキューのアクティブ化を詳細に示す。ステップ４０２において、パケットスケジューラ１３７は、当該キューに関してトラッキングしている予約タグ、限界タグ、および占有タグを初期化する。予約タグおよび限界タグについては、新たにアクティブとなるキューが現在アクティブのキューと同期可能であるとともに、古い予約タグが新たにアクティブとなるキューに割り当てられることでパケットスケジューラ１３７が現在アクティブのキューに不足を生じることのないように、前の値と現時点の値との大きい方で初期化する。占有タグについて、パケットスケジューラ１３７は、実時間の代わりに仮想時間を用いて同期を行う。占有タグの同期には、占有設定により無制限な帯域割り当てが強いられることはないため、仮想時間を用いることができる。図示の例において、パケットスケジューラ１３７は、新たにアクティブとなるキューの占有タグを初期化して、アクティブな兄弟キューの中で最小の占有タグとなるようにする。
【００２５】
ステップ４０４において、パケットスケジューラ１３７は、アクティブとなったキューをグローバルキューセット（global set of queues）（疑似コードではｇｌｏｂａｌ  ｍｉｎＨｅａｐと称する）に追加する。このキューセットは、後々、パケットのデキューイングおよびスケジューリングを行ってｐＮＩＣ１５０経由で送信するキューの選択に使用する。また、パケットスケジューラ１３７は、アクティブとなったキューの親キューが保持するローカルキューセット（local set of queues）（疑似コードではｓｈａｒｅｓ  ａｎｄ  ｌｉｍｉｔ  ｍｉｎＨｅａｐと称する）にもアクティブキューを追加する。その後、ステップ４０６および４０８において、パケットスケジューラ１３７は、親キューがアイドル状態であればアクティブにする。親キューをアクティブにした場合は、フローがステップ４０２に戻る。親キューが既にアクティブである場合は、本方法を終了する。本明細書の実施形態では、予約設定に対してネットワーク帯域をより正確かつきめ細かく割り当てるためにグローバルｍｉｎＨｅａｐを用いたが、その他の実施形態においては、階層のノードごとにローカル予約ｍｉｎＨｅａｐを実装するようにしてもよい。
【００２６】
図５は、一実施形態に係る、送信用パケットをスケジューリングする方法の各工程を示している。上述の通り、この方法は、任意のリーフキューにパケットが追加された時点で開始となる。この方法が開始されると、パケットスケジューラ１３７は、まず初めに、ステップ５０２において、ｐＮＩＣ１５０の全容量が現在使用中であるか否かを確認する。一実施形態において、パケットスケジューラ１３７は、先行のＮマイクロ秒（１６０マイクロ秒等）の間にスケジューリングされたバイト数がその時間にスケジューリング可能な最大バイト数を超えている場合、ｐＮＩＣ１５０の全容量が使用中であると判定する。その場合、パケットスケジューラ１３７は、１サイクルだけ待ってから（ステップ５０４）確認を再度行う。１サイクルの時間は、ｐＮＩＣ１５０の「Ｉｎｔｅｒｒｕｐｔ  Ｃｏａｌｅｓｃｉｎｇ」時間と同等である。「Ｉｎｔｅｒｒｕｐｔ  Ｃｏａｌｅｓｃｉｎｇ」とは、ｐＮＩＣ１５０に実装された技術であって、所定時間にわたってパケットを収集することによりネットワークパケット送信（および受信）に付随する割り込みの数を低減するとともに、当該各時間の最後に収集パケットを送信（および受信）する割り込みを１回だけ発生させるものである。この所定の時間が「Ｉｎｔｅｒｒｕｐｔ  Ｃｏａｌｅｓｃｉｎｇ」時間であって、一実施態様においては、２０マイクロ秒である。
【００２７】
ステップ５０２において、パケットスケジューラ１３７は、ｐＮＩＣ１５０の全容量が現在使用中ではないと判定した場合、ステップ５０６において、図６の方法によりパケットをスケジューリングして送信する適格キューを探索する。適格キューが見つからなかった場合は、本方法を終了する。適格キューが見つかった場合は、ステップ５１０において、適格キューの最初の（すなわち、最も古い）パケットをデキューイングする（キューから取り出して削除する）。その後、パケットスケジューラ１３７は、ステップ５１２において、図７に示す方法によりこの送信用パケットのスケジューリングの順序付けを行う。この順序付けは、ステップ５０８で見つかった適格キューを最初とし、その親キューとその他の先行キューがあれば、それらを後続として、ボトムアップ式に行う。順序付けを終えたら、パケットスケジューラ１３７は、ステップ５１４において、パケットをｐＮＩＣ１５０に渡して送信する。
【００２８】
図６は、一実施形態に係る、パケットをスケジューリングして送信するキューを選択する方法の各工程を示している。この方法は、ステップ６０２で開始して、パケットスケジューラ１３７がグローバルアクティブキューセットを検査するとともに、適格な予約タグ値および限界タグ値を有するキューが存在するか否かを判定する。適格な予約タグ値とは、現時点の値以下のものであって、対応するキューがその予約設定まで帯域割り当てされていないことを意味する。同様に、適格な限界タグ値とは、現時点の値以下のものであって、対応するキューに割り当てられた帯域がその限界設定を超えていないことを意味する。適格な予約タグ値および限界タグ値を有するキューが存在しない場合、パケットスケジューラ１３７は、ステップ６０４においてルートキューを選択し、ステップ６０８に進む。
【００２９】
一方、適格な予約タグ値および限界タグ値を有するキューが少なくとも１つ存在する場合、パケットスケジューラ１３７は、ステップ６０６において予約タグ値が最小のキューを選択し、当該選択したキューおよびそのすべての先行キューに対して「予約適格」というフラグを立てる。このフラグは、後述の図７の方法で利用する。その後、ステップ６０８を実行する。
【００３０】
パケットスケジューラ１３７は、ステップ６０８において、選択したキューがリーフキューであるか否かを判定する。リーフキューである場合、パケットスケジューラは、ステップ６１０において選択したキューを戻し、図５の方法に従ってスケジューリングを行う。リーフキューではない場合、パケットスケジューラ１３７は、ステップ６１２において選択したキューのローカルアクティブキューセットを検査し、適格な限界タグ値を有するキューが存在するか否かを判定する。適格な限界タグ値とは、現時点の値以下のものであって、対応するキューに割り当てられた帯域がその限界設定を超えていないことを意味する。適格な限界タグ値を有するキューが存在しない場合、パケットスケジューラ１３７は、図５の方法に従ってスケジューリングを行うためにキューを戻すことはない。一方、適格な限界タグ値を有するキューが少なくとも１つ存在する場合、パケットスケジューラ１３７は、ステップ６１６において占有タグ値が最小のキューを選択し、ステップ６０８に戻る。最小の占有タグ値を選択することにより、兄弟キューの中で、優先度が最も高いキューが他に優先して選択されることになる。
【００３１】
図７は、パケットをスケジューリングして送信する際にキューのトラッキングデータを更新する方法の各工程を示している。この方法は、ステップ７０２で開始して、パケットスケジューラ１３７がキューに「予約適格」というフラグが立っているかを検知する。立っていない場合は、帯域割り当てが予約設定ではなく相対占有率に基づいて行われたか否かを判定する。そこで、ステップ７０４を実行して、パケットスケジューラ１３７は、（新しい占有タグ値）＝（古い占有タグ値）＋（スケジューリングして送信するパケットの長さ）／（キューの占有設定）という式により、当該キューの占有タグ値を更新する。パケットスケジューラ１３７は、ステップ７０２において、キューに「予約適格」というフラグが立っていると判定した場合、（新しい予約タグ値）＝（古い予約タグ値）＋（スケジューリングして送信するパケットの長さ）／（キューの予約設定）という式により、当該キューの予約タグ値を更新する。
【００３２】
パケットスケジューラ１３７は、ステップ７０８においてユーザー設定を検知し、２つのセマンティック（ＭＡＸセマンティックまたはＳＵＭセマンティック）のいずれが指定されているかを判定する。ＳＵＭセマンティックが指定されている場合は、次にステップ７１０を実行する。ＭＡＸセマンティックが指定されている場合は、上述のステップ７０４を実行した後にステップ７１０を実行する。パケットスケジューラ１３７は、ステップ７１０において、（新しい限界タグ値）＝（古い限界タグ値）＋（スケジューリングして送信するパケットの長さ）／（キューの限界設定）という式により、当該キューの限界タグ値を更新する。
【００３３】
パケットスケジューラ１３７は、ステップ７１２において、キューが依然としてアクティブ状態であるか否かを判定する。リーフキューは、その最後のパケットをスケジューリングして送信したら、アクティブ状態ではなくなる。中間キューは、その子キューのいずれもアクティブでなければ、アクティブ状態ではなくなる。キューがアクティブ状態でなければ、ステップ７１４を実行して、パケットスケジューラ１３７は、グローバルアクティブキューセットおよびその親キューのローカルアクティブキューセットから当該キューを削除する。その後、ステップ７１６を実行する。パケットスケジューラ１３７は、ステップ７１６において、処理直後のキューの親キューが存在するか否かを判定する。存在する場合は、フローがステップ７０２に戻って、親キューの処理を行う。存在しない場合は、本方法を終了する。ステップ７１２に戻り、キューが依然としてアクティブ状態であるとパケットスケジューラ１３７が判定した場合には、ステップ７１４を飛ばして、ステップ７１２の後で上述の通りにステップ７１６を実行する。
【００３４】
別の実施形態では、パケットスケジューラ１３７で最適化を実施することにより、上述の階層スケジューリング方法のランタイムオーバーヘッドを最小化する。
一実施形態において、パケットスケジューラ１３７は、親キューの限界タグ値をそれ自体の限界タグ値およびそのアクティブな子キューの最小限界タグ値のうちの最大値と等しくする。子キューに最大帯域制約が一切ない場合、その限界タグ値は０とみなされる。本実施形態では、親キューがスケジューリング適格であってもその子キューがいずれも非適格である、という事態が避けられる。
【００３５】
別の実施形態においては、２段階のアクティブ化メカニズムを採用したロッキングモデルを実装する。このモデルでは、各中間キューに対してキューのアクティブ化を保留する専用リストをハイパーバイザ１３９が保持する。キューがアクティブとなった場合、当該キューは、その親キューのローカルセットに自動的に追加される（ステップ４０４を参照）代わりに、親キューのアクティブ化保留リストに追加される。その後、パケットスケジューラ１３７は、上述の方法により対応する親キューがスケジューリング対象として選択された場合にのみ、親キューのアクティブ化保留リストのキューを親キューのローカルセットに追加する。
【００３６】
２５６バイト等の小さなメッセージサイズの場合は、コスト上、階層を経由してパケット単位ですべての関連タグを更新することができない場合もある。したがって、別の実施形態において、パケットスケジューラ１３７は、適格なリーフキューを選択した場合、ペイロードに見合う所定サイズ（１０ＫＢ等）に到達するまで、この同じキューからのパケットをスケジューリングする。このようなバッチの程度は、巨視的には公正性に影響を及ぼさないが、性能を大幅に向上させることが分かっている。
【００３７】
さらに別の実施形態は、総予約設定が総有効容量を超える過剰シナリオへの対処方法に関する。これは、スループットの変動性に起因して、許可制御に関係なく起こり得る。たとえば、上流スイッチ（仮想スイッチ１３８等）が何らかの深刻なコンテンションへの対処を試みつつ一時停止通知を発行したり、故障したハードウェアが強制的にリンク速度を落としたりする場合がある。より一般的には、ハードウェアの性能が不十分で、最大リンク容量の実現可能性に影響を及ぼす場合がある。したがって、一実施形態においては、最大リンク容量の７５％までしか予約できないようにする。この利用率を超えると、上述の理由によりリンク性能が確定し得なくなる場合がある。
【００３８】
別の実施形態においては、過剰状態での容量変動に対処するため、パケットスケジューラ１３７が予約設定の相対比に基づいて帯域割り当てを行うように、階層の各リーフキューに高い予約値を設定する（たとえば、１０Ｇｂｐｓのリンクに合計１６Ｇｂｐｓを予約する）。当然のことながら、この環境では、予約を満足する際の遅延により、各リーフキューの予約タグが物理時間から遅れることになる。通常、各リーフキューがアクティブ状態を保っていれば、これは問題とならない。予約に基づく比率に従った順序でリクエストが出されるためである。ただし、リーフキューのうちの１つがしばらくの間アイドル状態になると、問題が生じる。このリーフキューが再度アクティブ状態になったら、パケットスケジューラ１３７は、上述のように（ステップ４０２）、当該リーフキューの予約タグを現時点の値Ｔに調整する。その他のリーフキューが遅延しているため、新たにアクティブとなるこのリーフキューは、その他のリーフキューがＴに追いつくまで動作が拒否される。この不足問題は、新たにアクティブとなるリーフキューの予約タグの初期値として、（１）その前の値と、（２）現時点の値Ｔおよびすべてのアクティブなリーフキューの予約タグのうちの最小値との最大値を設定することによって対処可能である。
【００３９】
本明細書に記載の実施形態は、仮想マシンをネットワーク帯域占有体（network bandwidth consumers）として特徴付けるものである。その他の実施形態において、ネットワーク帯域占有体は、管理サーバと連通した物理マシン内部で動作する管理エージェントであってもよいし、物理マシン間での仮想マシンのライブマイグレーションまたはデータストア、ＮＦＳ（ネットワークファイルシステム：Ｎｅｔｗｏｒｋ  Ｆｉｌｅ  Ｓｙｓｔｅｍ）ドライバ、およびｉＳＣＳＩ（インターネットスモールコンピュータシステムインターフェース：Ｉｎｔｅｒｎｅｔ  Ｓｍａｌｌ  Ｃｏｍｐｕｔｅｒ  Ｓｙｓｔｅｍ  Ｉｎｔｅｒｆａｃｅ）ドライバ間での仮想ディスクのマイグレーションを管理するハイパーバイザ内部で動作するマイグレーションモジュールであってもよい。
【００４０】
本明細書に記載の種々実施形態では、コンピュータシステムに格納されたデータを伴う種々コンピュータ実行動作を採用してもよい。たとえば、これらの動作においては、物理量の物理的な操作を必要とする場合が多く、必ずしもそうではないが、これらの物理量が電気信号または磁気信号の形態であってもよい。この場合は、信号またはその代替の格納、転送、組み合わせ、比較、あるいは操作が可能である。さらに、このような操作は、生成、識別、判定、または比較等の用語で称することが多い。本発明の１または複数の実施形態の一部を成す本明細書記載の任意の動作は、有用なマシン動作であってもよい。また、本発明の１または複数の実施形態は、これらの動作を行う機器または装置にも関する。この装置は、特定の所要目的に対して特別に構成したものであってもよいし、内部に格納されたコンピュータプログラムで選択的に起動または設定される汎用コンピュータであってもよい。特に、本明細書の教示に従って記述されたコンピュータプログラムと併せて種々汎用マシンを使用するようにしてもよいし、より特殊な装置を構成して所要動作を行うようにすればなお都合が良い。
【００４１】
本明細書に記載の種々実施形態は、携帯用機器、マイクロプロセッサシステム、マイクロプロセッサベースまたはプログラム可能な家庭用電化製品、小型コンピュータ、メインフレームコンピュータ等のその他コンピュータシステム構成と併せて実施するようにしてもよい。
【００４２】
本発明の１または複数の実施形態は、１または複数のコンピュータプログラムもしくは１または複数のコンピュータ可読媒体（有形のコンピュータ可読記憶媒体等）に具現化された１または複数のコンピュータプログラムモジュールとして実装してもよい。コンピュータ可読媒体（有形のコンピュータ可読記憶媒体等）という用語は、コンピュータシステムのコンピュータ可読媒体に後で入力可能なデータを格納できる任意のデータ記憶装置を表しており、コンピュータ可読の態様でコンピュータプログラムを具現化する任意の既存技術または今後開発される技術に基づくものであってもよい。コンピュータ可読媒体の例としては、ハードドライブ、ネットワークアタッチトストレージ（ＮＡＳ）、リードオンリーメモリー、ランダムアクセスメモリー（フラッシュメモリー素子等）、ＣＤ（コンパクトディスク）、ＣＤ−ＲＯＭ、ＣＤ−Ｒ、ＣＤ−ＲＷ、ＤＶＤ（デジタル多用途ディスク）、磁気テープ、ならびにその他の光学的データ記憶装置および非光学的データ記憶装置等が挙げられる。また、コンピュータ可読媒体は、コンピュータ可読コードが分散して格納および実行されるように、ネットワーク接続したコンピュータシステムに分散可能である。
【００４３】
以上、本発明の１または複数の実施形態を詳細に説明して理解の促進を図ってきたが、請求の範囲内で特定の変更および改良が可能であることは明らかである。したがって、上記実施形態はほんの一例に過ぎず、何ら制限がないものと考えるべきである。また、請求の範囲は、本明細書の詳細内容に限定されるものではなく、その範囲と均等物の範囲において改良してもよい。請求の範囲において特段の明確な記述がない限り、要素およびステップのうちの少なくとも一方は、如何なる特定の動作順序も示唆するものではない。
【００４４】
本明細書に記載の構成要素、動作、または構造に関しては、複数の事例を単一の事例として提供してもよい。最後に、種々構成要素、動作、およびデータストア間の境界は任意であり、説明のための具体的な構成との関係で特定の動作を示している。その他の機能割り当ても想定内であって、本発明の範囲内に含まれる。一般的に、例示的な構成において別個の構成要素として提示された構造および機能は、組み合わせ構造または構成要素として実装してもよい。同様に、単一の構成要素として提示された構造および機能は、別個の構成要素として実装してもよい。これらのほか、その他の変形、変更、追加、および改良についても、添付の請求の範囲に含まれる。
【符号の説明】
【００４５】
中間ノード…Ｐ１、Ｐ２、リーフノード…Ｖ１、Ｖ２、Ｖ３、Ｖ４。
【図１】
2014220780.tif 000003
【図２】
2014220780.tif 000004
【図３】
2014220780.tif 000005
【図４】
2014220780.tif 000006
【図５】
2014220780.tif 000007
【図６】
2014220780.tif 000008
【図７】
2014220780.tif 000009
【図８Ａ】
2014220780.tif 000010
【図８Ｂ】
2014220780.tif 000011
【図８Ｃ】
2014220780.tif 000012
【図８Ｄ】
2014220780.tif 000013
【図８Ｅ】
2014220780.tif 000014
【図８Ｆ】
2014220780.tif 000015