(57)【要約】  集中型ディスパッチャ（１０３）から複数の仮想機械（ＶＭ）の間で負荷を分散させるための方法、装置、および機械可読記憶媒体が開示され、ディスパッチャは、データパケット（１０４）を受信し、各ＶＭに対する関連する重み付けを有する重み付きハッシュ関数（１０６）を使用して、複数のＶＭ（１０８、１１０、１１２）から選択されるＶＭにデータパケットをマッピングし、それに従って各パケットをＶＭに転送し、ロードバランサは、ＶＭに対する負荷が第１の負荷閾値を超えているという指示に応答して、ＶＭに対する重み付けをデクリメントする。重み付けは、各ＶＭと関連付けられるビンの数に対応することができる。重み付けは、それらのそれぞれの負荷を表す、ＶＭからのインバイト（１０７）およびディスインバイト（１０５）メッセージの受信に応答して調整される。
2019522936.tif 000002
【特許請求の範囲】
【請求項１】
集中型ディスパッチャから複数の仮想機械（ＶＭ）の間で負荷を分散させるための方法であって、
前記ディスパッチャにおいてデータパケットを受信するステップと、
各ＶＭに対する関連する重み付けを有する重み付きハッシュ関数を使用して、複数のＶＭから選択される第１のＶＭに前記データパケットをマッピングするステップと、
前記パケットを前記第１のＶＭに転送するステップと
を含み、
ロードバランサが、前記第１のＶＭに対する負荷が第１の負荷閾値を超えているという指示に応答して、前記重み付きハッシュ関数の前記第１のＶＭに対する重み付けをデクリメントする、方法。
【請求項２】
前記第１のＶＭに対する負荷が第１の負荷閾値を超えているという前記指示が、前記第１のＶＭからディスインバイトメッセージを受信することを含む、請求項１に記載の方法。
【請求項３】
前記ロードバランサが、第２のＶＭに対する負荷が第２の負荷閾値を下回っているという指示に応答して、前記第２のＶＭに対する重み付けをインクリメントする、請求項１および２のいずれか一項に記載の方法。
【請求項４】
前記第２のＶＭに対する負荷が第２の負荷閾値を下回っているという前記指示が、前記第２のＶＭからインバイトメッセージを受信することを含む、請求項３に記載の方法。
【請求項５】
第１のＶＭに前記データパケットをマッピングする前記ステップが、前記第１のＶＭと関連付けられる複数のビンから選択される第１のビンに前記データパケットをマッピングすることを含み、
各ＶＭに対する重み付けが、前記各ＶＭと関連付けられるビンの数に対応する、請求項１および４のいずれか一項に記載の方法。
【請求項６】
前記ロードバランサが、前記ディスインバイトメッセージの受信に応答して前記第１のＶＭに対する重み付けをデクリメントし、
前記第１のＶＭと関連付けられる複数のビンの中から、いずれのビンが最もアクティブでないかを決定するステップと、
第２の負荷閾値よりも少ない負荷を有する第３のＶＭに、前記最もアクティブでないビンを再割り当てするステップと、
それに従って前記第３のＶＭに対する重み付けをインクリメントするステップと
をさらに含む、請求項５に記載の方法。
【請求項７】
前記第１のＶＭと関連付けられる複数のビンの中から、いずれのビンが最もアクティブでないかを決定する前記ステップが、所定の時間区間にわたって、前記複数のビンの各ビンに対するトラフィックを監視することと、前記第１のＶＭと関連付けられる複数のビンの中から、いずれのビンが、前記所定の時間区間にわたって最小数のパケット到来を有するかを決定することとを含む、請求項６に記載の方法。
【請求項８】
いずれのビンが最もアクティブでないかを決定する前記ステップが、前記第１のＶＭと関連付けられる複数のビンの中から、いずれのビンが、前記所定の時間区間にわたって最大パケット到来間間隙を有するかを決定することを含む、請求項７に記載の方法。
【請求項９】
前記ロードバランサが、前記第３のＶＭからのインバイトメッセージの受信に応答して、前記第３のＶＭが前記第２の負荷閾値より少ない負荷を有していると決定する、請求項６に記載の方法。
【請求項１０】
集中型ディスパッチャから複数の仮想機械（ＶＭ）の間で負荷を分散させるための集中型ロードバランサであって、
データパケットを受信し、前記データパケットを前記複数のＶＭに転送するためのディスパッチャと、
プロセッサおよびメモリと
を備え、
前記メモリは、
前記ディスパッチャにおいてデータパケットを受信し、
各ＶＭに対する関連する重み付けを有する重み付きハッシュ関数を使用して、複数のＶＭから選択される第１のＶＭに前記データパケットをマッピングし、
前記パケットを前記第１のＶＭに転送するために、
前記プロセッサによって実行可能なプログラム命令をさらに含み、
前記ロードバランサは、前記第１のＶＭに対する負荷が第１の負荷閾値を超えているという指示に応答して、前記重み付きハッシュ関数の前記第１のＶＭに対する重み付けをデクリメントする、集中型ロードバランサ。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、コンピュータシステムに関し、より詳細には、データセンタネットワークのための改善されたロードバランサに関する。
【背景技術】
【０００２】
サーバは、ほぼ間違いなくデータセンタ内の最も価値あるリソースであるが、データセンタネットワーク内の接続の複雑さおよびオーバーブッキングに起因して、サーバは、著しく過剰利用であるかまたは利用不足であるかのいずれかであることが多い。サーバの効率的な利用は、良好なロードバランサによって是正され得る、動的リソース配分問題である。従来の見識では、ロードバランサが効率的に動作するためには、ロードバランサはサーバおよび／または仮想機械（ＶＭ）からの相当量の状態情報を必要とすると主張されている。この論点は、提案されているロードバランサが、データセンタ内のすべてのサーバおよびＶＭにわたって大域的に監視することができるように意図されている場合、特に重大と考えられる。加えて、データセンタ内の多くの作業は、同じサーバに割り当てられることが好ましい一連のパケット（フロー）を伴い、したがって、より大きいスケールにおいてリソース配分問題が複雑になる。したがって、フローの完全性を保持しながらスケーラビリティを達成することが課題である。サーバおよびＶＭへのフローの割当は、たとえ、提案されているＶＩＮＥ（仮想統合ネットワークエッジ）スケールのデータセンタのような小規模なデータセンタにおいても、満足に行われないことが非常に多く、結果としてサーバの利用が満足に行われない。
【０００３】
上記の理由は、ロードバランサ（ＬＢ）が一般的に、データセンタ内の１つのラックに、または、せいぜい小さいラック群に局在化されることである。この制限は、データセンタ内のジョブを追跡するための大量の状態情報を回避する必要性から生じる。自己完結型のジョブ（ジョブが同じ５タプルを有する一連のパケットから構成されないことを意味する）を取り扱う現行技術水準のＬＢは、一般的に、ラウンドロビンスケジューリング、または、「ハッシュ関数」を介して実施されるより効率的なランダム化されたラウンドロビンバージョンによって機能する。フローベースのジョブについて負荷を分散させるとき、ランダム化されたラウンドロビンは一般的に、以下のように機能する：フロー（すなわち：送信元ＩＰアドレス、宛先ＩＰアドレス、プロトコル、送信元ポート、および宛先ポートから構成される５タプル）のすべての関連情報がパケットヘッダから読み出され、その後、ハッシュ関数を介してＶＭアドレスに一意にマッピングされる。ハッシュ関数は、すべてのＶＭのセットについて、各々が平均してデータセンタに到来するフローの総数のうちの等しい割合を受け取ること、および、このマッピングが、サーバまたはＶＭからロードバランサへの状態の交換なしに効率的に実施されることを保証する。そのような、フローベースの負荷分散のための負荷分散メカニズムは、すべてのＶＭの性能が均質であり、かつ、フロー処理要件にばらつきが少ない場合には、比較的良好に機能することができる。実際には、これらの条件はいずれも一般的に当てはまらない。これは複数の要因に起因するが、主に、サーバ／ＶＭが、たとえそれらが最初は等しいサイズであっても、互いに著しく異なるように動作し、フロー処理要件が一般的に、大きなばらつきのあるヘビーテールな特性を有するためである。これらの２つの要因の結果として、従来の、さらには現行技術水準のロードバランサでは、データセンタ内のサーバ／ＶＭの利用が非効率的で、しばしば著しく不足／過剰になり得る。ネットワーキングおよびキューイングに関する文献において、これらの問題を一定程度まで軽減することができる代替的な動的ロードバランサが提案されている。しかしながら、これらのロードバランサは、一般的に、パケット化されたトラフィックに対するフロー認識の概念を欠き、実践においては許容されない、状態情報の取得における通信オーバヘッドを招き、結果として、スケーラビリティを不満足なものにする。そのような方式の一例は、ランダム化されたラウンドロビンスケジューラ（「ｋの累乗」スケジューラとして参照される場合もある）の系統であり、ｋ個のランダムに選択されたサーバ／ＶＭの状態がチェックされ、負荷の最も小さいサーバ／ＶＭに配分が行われる。さらなる例は、サーバが、アイドルであるときに集中化キューからジョブを要求する方式である。
【発明の概要】
【発明が解決しようとする課題】
【０００４】
それゆえ、一般にロードバランサの改善、特に、集中型ロードバランサの改善が特に望ましい。
【課題を解決するための手段】
【０００５】
様々な例示的な実施形態の簡潔な概要が提示される。いくつかの単純化および省略が以下の概要において行われている場合があり、それは、様々な例示的な実施形態のいくつかの態様を強調および紹介するように意図されており、本発明の範囲を限定するようには意図されていない。当業者が本発明の概念を作成および使用することを可能にするのに十分な好ましい例示的な実施形態の詳細な説明は、続いて後の節に記載する。
【０００６】
様々な例示的な実施形態は、集中型ディスパッチャから複数の仮想機械（ＶＭ）の間で負荷を分散させるための方法に関する。方法は：ディスパッチャにおいてデータパケットを受信するステップと、各ＶＭに対する関連する重み付けを有する重み付きハッシュ関数を使用して、複数のＶＭから選択される第１のＶＭにデータパケットをマッピングするステップと、パケットを第１のＶＭに転送するステップとを含み、ロードバランサが、第１のＶＭに対する負荷が第１の負荷閾値を超えているという指示に応答して、重み付きハッシュ関数の第１のＶＭに対する重み付けをデクリメントする。
【０００７】
様々な代替的な実施形態において、第１のＶＭに対する負荷が第１の負荷閾値を超えているという指示は、第１のＶＭからディスインバイトメッセージ（ｄｉｓｉｎｖｉｔｅ  ｍｅｓｓａｇｅ）を受信することを含む。
【０００８】
様々な代替的な実施形態において、ロードバランサは、第２のＶＭに対する負荷が第２の負荷閾値を下回っているという指示に応答して、第２のＶＭに対する重み付けをインクリメントする。
【０００９】
様々な代替的な実施形態において、第２のＶＭに対する負荷が第２の負荷閾値を下回っているという指示は、第２のＶＭからインバイトメッセージ（ｉｎｖｉｔｅ  ｍｅｓｓａｇｅ）を受信することを含む。
【００１０】
様々な代替的な実施形態において、第１のＶＭにデータパケットをマッピングするステップは、第１のＶＭと関連付けられる複数のビンから選択される第１のビンにデータパケットをマッピングすることを含み、各ＶＭに対する重み付けは、各ＶＭと関連付けられるビンの数に対応する。
【００１１】
様々な代替的な実施形態において、ロードバランサは、ディスインバイトメッセージの受信に応答して第１のＶＭに対する重み付けをデクリメントし、第１のＶＭと関連付けられる複数のビンの中から、いずれのビンが最もアクティブでないかを決定するステップと、第２の負荷閾値よりも少ない負荷を有する第３のＶＭに、最もアクティブでないビンを再割り当てするステップと、それに従って第３のＶＭに対する重み付けをインクリメントするステップとをさらに含む。
【００１２】
様々な代替的な実施形態において、第１のＶＭと関連付けられる複数のビンの中から、いずれのビンが最もアクティブでないかを決定するステップは、所定の時間区間にわたって、複数のビンの各ビンに対するトラフィックを監視することと、第１のＶＭと関連付けられる複数のビンの中から、いずれのビンが、所定の時間区間にわたって最小数のパケット到来を有するかを決定することとを含む。
【００１３】
様々な代替的な実施形態において、いずれのビンが最もアクティブでないかを決定するステップは、第１のＶＭと関連付けられる複数のビンの中から、いずれのビンが、所定の時間区間にわたって最大パケット到来間間隙を有するかを決定することを含む。
【００１４】
様々な代替的な実施形態において、ロードバランサは、第３のＶＭからのインバイトメッセージの受信に応答して、第３のＶＭが第２の負荷閾値より少ない負荷を有していると決定する。
【００１５】
他の実施形態は、集中型ディスパッチャから複数の仮想機械（ＶＭ）の間で負荷を分散させるための集中型ロードバランサを提供する。ロードバランサは：データパケットを受信し、データパケットを複数のＶＭに転送するためのディスパッチャと、プロセッサと、メモリとを備える。メモリは：ディスパッチャにおいてデータパケットを受信し、各ＶＭに対する関連する重み付けを有する重み付きハッシュ関数を使用して、複数のＶＭから選択される第１のＶＭにデータパケットをマッピングし、パケットを第１のＶＭに転送するために、プロセッサによって実行可能なプログラム命令を含み、ロードバランサは、第１のＶＭに対する負荷が第１の負荷閾値を超えているという指示に応答して、重み付きハッシュ関数の第１のＶＭに対する重み付けをデクリメントする。
【００１６】
他の実施形態は、集中型ロードバランサによって実行するための命令を符号化されている有形非一時的機械可読記憶媒体を提供し、有形非一時的機械可読記憶媒体は：ディスパッチャにおいてデータパケットを受信し、各ＶＭに対する関連する重み付けを有する重み付きハッシュ関数を使用して、複数のＶＭから選択される第１のＶＭにデータパケットをマッピングし、パケットを第１のＶＭに転送するステップと、第１のＶＭに対する負荷が第１の負荷閾値を超えているという指示に応答して、重み付きハッシュ関数の第１のＶＭに対する重み付けをデクリメントするための、命令を備える。
【００１７】
本発明の実施形態による装置および／または方法のいくつかの実施形態を、ここで例としてのみ、添付の図面を参照して説明する。
【図面の簡単な説明】
【００１８】
【図１】重み付きハッシュ関数を用いる集中型ロードバランサのブロック図である。
【図２】集中型ディスパッチャにおけるデータパケットの処理のプロセスフロー図である。
【図３】集中型ロードバランサにおけるディスインバイトメッセージの処理のプロセスフロー図である。
【図４】集中型ロードバランサにおけるインバイトメッセージの処理のプロセスフロー図である。
【図５】ＶＭにおける負荷情報の処理のプロセスフロー図である。
【図６】重み付きハッシュ関数の代替の実施形態の抽象表現を示す図である。
【図７】インバイト／ディスインバイト方式を使用した、実験比較応答時間を示す図である。
【図８】ネットワーク機器プロセッサアセンブリの上位レベルブロック図である。
【発明を実施するための形態】
【００１９】
図面において、同様の特徴は同様の参照符号によって示される。
【００２０】
ネットワークおよびインターネットに対する無線と有線の両方のアクセスのためのソフトウェア定義ネットワーク（ＳＤＮ）／仮想化要素として機能する仮想統合ネットワークエッジ（ＶＩＮＥ）内で想定されるような、小規模な、すなわち、１００個程度のサーバラックの規模のＶＩＮＥスケールデータセンタに焦点を当てた、サーバ／ＶＭに対するフローの割当のための集中型ロードバランサ（ＣＬＢ）またはコントローラの実施形態が説明される。
【００２１】
ＶＩＮＥスケールデータセンタの文脈における、説明される実施形態は、サーバおよびＶＭの著しく良好な利用をもたらすことができ、また、著しく良好な応答時間、サービス時間ジッタ、損失およびＱｏＳに関連する他の測定基準を可能にすることもでき、それらのいくつかは、例えば：仮想インターネットプロトコルマルチメディアサブシステム（ｖＩＭＳ）、仮想サーバゲートウェイ（ｖＳＧＷ）、仮想ボーダゲートウェイ（ｖＢＧＷ）、および仮想コンテンツ配信ネットワーク（ｖＣＤＮ）などの、新興のアクセスノード技術の円滑な動作の中核を成す。
【００２２】
様々な実施形態は、均一ではなくバイアスされた様式でＶＭにフローをマッピングする重み付きハッシュ関数を作成する。重みは、「インバイト／ディスインバイト」方式を通じて、アクティブなＶＭの誘導に基づいて調整される。前の文において参照されているバイアスは、予め指定されている時間窓の間にＶＭの実際の性能の代理としての負荷指標に基づいて計算される。サーバ／ＶＭからの「インバイト」および「ディスインバイト」メッセージは、サーバ／ＶＭが、ハッシュ関数に対する重みを再調整するためにロードバランサに提供するフィードバックである。
【００２３】
「インバイトスタック」は、様々なＶＭから受信されるインバイトメッセージによって供給され、インバイトメッセージに基づいて、ディスインバイトメッセージに応答してＶＭにビンを再割り当てするように、ロードバランサによって制御される。インバイタスタック内にメッセージを有する特定のＶＭに、最もアクティブでないビンを再割り当てした後、インバイトメッセージはインバイトスタックから消去される。
【００２４】
ここで図面を参照すると、同様の参照符号が同様の構成要素またはステップを参照しているが、様々な例示的な実施形態の広範な態様が開示される。
【００２５】
図１は、着信するパケット１０４を受信し、説明するように、ビンメカニズムを用いる重み付きハッシュ関数を使用してＶＭ１０８、１１０、１１２にそれらのパケットを転送する集中型ロードバランサ１０２のブロック図である。ディスパッチャ１０３（キューイング要素ではない）は、着信するパケット１０４を受信し、静的ハッシュ関数１０６を介して、着信するパケットを十分に多数のビン１１６、１２０（一般的に、ＶＭの数の約１０倍多い）にマッピングする。したがって、例えば、着信するパケット１１４はビン１１６に割り当てられており、着信するパケット１１８はビン１２０に割り当てられている。ディスパッチャ１０３は、その後、いずれのＶＭがビン１１６と関連付けられているかを決定し、着信するパケット１１６をそのＶＭ（１０８）に転送する。図１に示すビンの表記は、仮想ビン（１１６、１２０、．．．、１２４）を示し、キューではないことに留意されたい。着信するパケットは、物理的にはＶＭ（１０８、１１０、．．．、１１２）においてキューに入れられる。
【００２６】
ロードバランサ１０２は、ＶＭに対するビンの割り当てを格納する動的ビンテーブル（表１参照）を維持する。バックグラウンドプロセスにおいて、ロードバランサ１０２は、同じくロードバランサが計算する「重み」に基づいて、いずれのビンを各ＶＭと関連付けるべきかを決定する。最初に、各ＶＭが、同じ数のビンと関連付けられる。ＶＭに対するビンの割り当てが、表１に示すような動的ビンテーブルに格納される。静的ハッシュ関数を介して着信するパケットが特定のビンにマッピングされると、このビンテーブル内でルックアップが実施され、その後、パケットは関連付けられるＶＭに転送される。
【００２７】
ハッシュ関数は、決定論的かつ高速に機能すべきである。好ましくは、同じフローに属するすべてのパケットが、同じサーバ／ＶＭにマッピングされるべきである。これは、「スティッキーネス（ｓｔｉｃｋｉｎｅｓｓ）」として参照されることがある。スティッキーネスを達成するために、ビンタイマが、フローが論理的にいつ終了しているかを決定するために、表１に示すように各ビンと関連付けられ、したがって、ビンは、たとえハッシュ値が、異なるサーバ／ＶＭに以前にマッピングされたものと同じである場合であっても、新たなサーバ／ＶＭに再割り当てすることができる。
【００２８】
過負荷および負荷不足になっているＶＭに関するインバイト／ディスインバイトフィードバックが受信され、ディスインバイトメッセージと関連付けられるビンに対するパケット到来が追跡されるとき、ビンは動的に再割り当てされ、ビンテーブルがそれに応じて更新される。一般的なＶＩＮＥデータセンタの動的ビンテーブルは、標準的なパケットプロセッサによってマイクロ秒単位またはより高速に容易に処理される、１００，０００個程度の２列エントリから成る。ビンタイマの一般的な値は、１０ｍｓ程度である。ビンタイマは、パケットが特定のビンにハッシュされた直近の時間を追跡し、そのビンと関連付けられるフローのトラフィック活動のレベルの代理を提供する。これが次に、ビンを異なるＶＭに再割り当てするときの潜在的な中断の程度（スティッキーネスの違反）の推定値を提供する。
【００２９】
【表１】
2019522936.tif 000003
【００３０】
ロードバランサ１０２は、任意選択的に、インバイト／ディスインバイト要求時に再配分するための予備のビンがないときに、各ＶＭのインバイト／ディスインバイトステータスのテーブル（表２参照）を維持する。このステータスは、インバイトスタック内に維持され、インバイトスタックは、時間によって順序付けされたＬＩＦＯ（後入れ先出し）リストであり得る。表２はまた、一般的に整数値であり、１、２、３、１０、２０程度であり得る、各ＶＭに対するハッシュ重み（例えば、関連付けられるビンの数）をも表示することができる。ハッシュ重みは、インバイト／ディスインバイトプロセスおよびビンテーブルを通じて管理される。
【００３１】
【表２】
2019522936.tif 000004
【００３２】
図２は、ロードバランサ１０２におけるデータパケットの処理のプロセスフロー図を示す。プロセスは、ステップ２０２において開始する。ステップ２０４において、ディスパッチャ１０３が、新たな着信するパケットを受信する。ステップ２０６において、ディスパッチャ１０３が、ハッシュ関数１０６を使用して、パケットヘッダ内のパケットフロー５タプルに基づいてハッシュ値を計算し、その後、計算されたハッシュ値に対応するビンに、着信するパケットをマッピングする。ステップ２０８において、ディスパッチャ１０３が、ビンテーブル（表１）を使用して、着信するパケットがマッピングされている、ビンと関連付けられるＶＭをルックアップし、その後、関連付けられるＶＭにパケットを転送する。ステップ２１０において、ディスパッチャ１０３が、ビンに対してフラグが設定されているか否かを決定し、そうである場合、ステップ２１２において、ディスパッチャ１０３がビンタイマをリセットする。その後、プロセスは、ステップ２２０において終了する。
【００３３】
ロードバランサ１０２は、着信するパケットトラフィックとは非同期的に、様々なＶＭ（１０８、１１０、．．．、１１２）からディスインバイトメッセージ１０５を受信することができる。図３は、ロードバランサ１０２におけるディスインバイトメッセージの処理のプロセスフロー図を示す。プロセスは、ステップ３０２において開始する。ステップ３０４において、ロードバランサ１０２が、ＶＭからディスインバイトメッセージ１０５を受信する。ステップ３０６において、ロードバランサ１０２が、そのＶＭに現在割り当てられているすべてのビンに対して、ビンテーブル（表１）内でフラグを設定する。ステップ３０８において、ロードバランサ１０２は、予め指定されている活動監視期間にわたって待機し、一方その間ステップ３１０において、ロードバランサ１０２が最大ビンタイマ値、最小数のパケット到来または最大パケット到来間間隙に関してＶＭと関連付けられる最もアクティブでないビンを（フラグが設定されているビンの中から）決定する。ステップ３１２において、ロードバランサ１０２が、ＶＭと関連付けられるすべてのフラグをリセットする。ステップ３１４において、ロードバランサ１０２が、識別された最もアクティブでないビンを、インバイトスタック内の直近のメッセージを有する別のＶＭに再割り当てする。この結果として、そのビンにマッピングされている任意の進行中のフローのパケットが異なるＶＭにリダイレクトされることが潜在的にあり得ることに留意されたい。
【００３４】
ステップ３１６において、ロードバランサ１０２は、前述した識別されている最もアクティブでないビンの再割り当てを反映するように、ビンテーブル（表１）を更新する。プロセスは、ステップ３１８において終了する。
【００３５】
ディスインバイトメッセージの場合に「重み」が調整される前に、ディスパッチャは、そのサーバ／ＶＭに現在割り当てられているビン（ハッシュ値）に関する到来パケットの数および／または到来回数の追跡を開始する。ディスパッチャは、その後、例えば、最大ビンタイマ値、最小数のパケット到来または最大パケット到来間間隙に関して、最もアクティブでないと決定されているビン（ハッシュ値）を再割り当てし、任意の進行中のフローのパケットが異なるサーバ／ＶＭにリダイレクトされる可能性が低いことを保証する。結果として、インバイト／ディスインバイトフィードバックの動作は、一般的に単一のパケットの処理よりも低速である、フローの完了時間よりも一般的に低速である。したがって、フローを認識するロードバランサの記載されている実施形態の重み調整の動態は、フローを認識しないパケットスケジューリングロードバランサよりも低速である。シミュレーションは、負荷不足／過負荷条件に起因するインバイト／ディスインバイトメッセージに対する、十分を超える応答性を示している。サーバ／ＶＭに対する決定論的かつフローがスティッキーなマッピングは、各フローのパケットがデータセンタ内の同一の経路に従い、異なる経路に沿って中断／分割されて、結果としてリアセンブルを必要とすることがないことを保証するのを助ける。
【００３６】
図４は、集中型ディスパッチャにおけるインバイトメッセージの処理のプロセスフロー図を示す。プロセスは、ステップ４０２において開始する。ステップ４０４において、ロードバランサ１０２が、ＶＭからインバイトメッセージ１０７を受信する。ステップ４０６において、ロードバランサ１０２が、インバイトスタック内のＶＭに対するタイムスタンプをリフレッシュする。プロセスは、ステップ４０８において終了する。
【００３７】
上記の方式への機能強化は、以下のような、寿命の長いフローの外因的な決定を含み、したがって、ＣＢＬの性能をさらに改善する。ディスパッチャへの着信するフローは「エレファントフロー」（例えば、パケットレートが高く寿命が長い）と「マウスフロー」（例えば、パケットレートが低く寿命が短い）との混合である可能性が高いため、あるビンテーブルをエレファントフローに使用し、別個のビンテーブルをマウスフローに使用することによって、負荷分散をさらに改善することができる。エレファントフローは、ＴＣＰポート情報またはアプリケーション署名に基づく、知られている技法を使用して直ちに検出することができる。結果としてもたらされる２つのビンテーブルは、柔軟性およびより微細な負荷分散粒度を可能にするはずである。例えば、エレファントフローが遅い時間スケールにおいてサーバに割り当てられ、マウスフローがより速い時間スケールにおいて割り当てられる、２階層負荷分散を達成することができる。
【００３８】
ＶＭの各々は、例えば、メモリ要件を最小限に抑えるような幾何学的平滑化を介して、単純な負荷推定値を維持する。負荷推定値が（例えば、定期的に）更新される度に、負荷が一定の目標値を下回って降下しているか、または、一定の目標値を上回っているかがチェックされ、これらの場合に、それぞれインバイト（目標負荷１を下回る）またはディスインバイト（目標負荷２を上回る）メッセージのいずれかが、ディスパッチャに送信される。負荷更新の頻度、したがって、インバイトおよびディスインバイトメッセージの頻度は、負荷平滑化の時間スケールと釣り合うはずであり、ＶＭにおける負荷変動に対する応答性と、インバイトおよびディスインバイトメッセージからもたらされるディスパッチャとの情報交換の量との間の最適なトレードオフを達成するように選択される。目標負荷範囲の下限および上限は、実験的発見に基づいて設定されるか、または、学習技法を通じて最適化されるさらなる設計パラメータであり、また、ロードバランサの敏捷性と通信オーバヘッドの度合いとの間の最適なバランスに行き当たるように選択される。
【００３９】
図５は、ＶＭにおける負荷情報の処理のプロセスフロー図である。プロセスは、ステップ５０２において開始する。ステップ５０４において、ＶＭは、上述したように負荷推定値を計算する。ステップ５０６において、ＶＭは、負荷がプリセットの負荷目標１を下回るか否かを決定し、そうである場合、ステップ５０８において、ＶＭは、ロードバランサ１０２にインバイトメッセージを送信し、プロセスはステップ５１０において終了する。ステップ５０６において、ＶＭが、負荷がプリセットの負荷目標１を下回っていないと決定する場合、ステップ５１２において、ＶＭは、負荷がプリセットの負荷目標２よりも大きいか否かを決定し、そうである場合、ステップ５１４において、ＶＭは、ロードバランサ１０２にディスインバイトメッセージを送信し、プロセスはステップ５１０において終了する。ステップ５１２において、ＶＭが、負荷がプリセットの負荷目標２以下であると決定する場合、プロセスはステップ５１０において終了する。閾値負荷目標１および負荷目標２は、これらが、公称負荷目標と実際に観測される負荷との間に非常に大きい不整合がある場合を除き、まれにしか呼び出されないように設定される。
【００４０】
上記の記述は、重み付きハッシュ関数の重み付けを実装するためにビンを使用する例示的な実施形態を説明している。例えば、図６の抽象グラフに表されるようなデータ構造６００を使用することのような、他の実施形態が企図されることが理解されるべきである。円は、１００の合計重み付けを表す。この例において、４つのＶＭ：ＶＭ１、ＶＭ２、ＶＭ３、ＶＭ４が、円の周りのＶＭの分布によって示されるように、それぞれ１０、２０、３０、および４０の重み付けを割り当てられ、各円セグメントの長さは、それぞれのＶＭの重み付けを表す。データパケットがディスパッチャによって受信されると、パケットの５タプルが、ハッシュ関数によって円の円周に沿って均一にマッピングされる。より高い重み付けを有するＶＭが、比例的に、より低い重み付けを有するＶＭよりも多くのデータフローを割り当てられることになる。
【００４１】
図７は、実験室シミュレーションに基づく、現行技術水準のランダム化されたラウンドロビンスケジューラ７０６を使用したパケットの処理時間と比較した、説明されているインバイト−ディスインバイト方式７０８の実施形態を使用したパケットのサンプル実験比較処理時間を示す。見てとれるように、現行技術水準のランダム化されたラウンドロビン方式７０６の２０ｍｓの応答時間を超える２４％のパケットと比較して、説明されているインバイト−ディスインバイト方式７０８については、２０ｍｓの応答時間を超えるパケットは４％（０．０４の確率）であり、現行技術水準のランダム化されたラウンドロビン方式７０６の１５％と比較して、説明されているインバイト−ディスインバイト方式７０８については、１００ｍｓの応答時間を超えるパケットは０．４％である。
【００４２】
図８は、本明細書に記載されている機能を実施するのに使用するのに適したネットワーク機器プロセッサアセンブリの上位レベルブロック図を示す。
【００４３】
図８に示すように、ネットワーク機器プロセッサアセンブリ８００は、ネットワーク機器プロセッサ要素８０２（例えば、中央処理装置（ＣＰＵ）および／または他の適切なプロセッサ）と、メモリ８０４（例えば、ランダムアクセスメモリ（ＲＡＭ）、読み出し専用メモリ（ＲＯＭ）など）、協調モジュール／プロセス８０８と、様々な入出力デバイス８０６（例えば、ユーザ入力デバイス（キーボード、キーパッド、マウスなど）、ユーザ出力デバイス（ディスプレイ、スピーカなど）、入力ポート、出力ポート、受信機、送信機、および記憶デバイス（例えば、テープドライブ、フロッピードライブ、ハードディスクドライブ、コンパクトディスクドライブなど））とを含む。
【００４４】
本明細書において図示および記載されている機能は、例えば、１つまたは複数の特定用途向け集積回路（ＡＳＩＣ）、および／または任意の他のハードウェア均等物を使用して、ハードウェアにおいて実装されてもよいことが諒解されよう。代替的に、１つの実施形態によれば、協調プロセス８０８は、メモリ８０４にロードされ、本明細書において論じられているような機能を実装するために、ネットワーク機器プロセッサ８０２によって実行されてもよい。同様に、協調プロセス８０８（関連付けられるデータ構造を含む）は、例えば、磁気または光学ドライブまたはディスケット、半導体メモリなどの、有形非一時的コンピュータ可読記憶媒体に記憶されてもよい。
【００４５】
本明細書において方法として論じられているステップのうちのいくつかは、例えば、様々な方法ステップを実装するためにネットワーク機器プロセッサと協働する回路として、ハードウェア内で実装されてもよいことが企図される。本明細書において記載されている機能／要素の部分は、コンピュータ命令が、ネットワーク機器プロセッサによって処理されると、本明細書において記載されている方法および／または技法が呼び出されるか、または、他の様態で提供されるように、ネットワーク機器プロセッサの動作を適合させるコンピュータプログラム製品として実装されてもよい。本発明の方法を呼び出すための命令は、固定または取り外し可能媒体に記憶されてもよく、および／または、命令に従って動作するコンピュータデバイス内のメモリ内に記憶されてもよい。
【００４６】
「プロセッサ」としてラベリングされている任意の機能ブロックを含む、図面に示されている様々な要素の機能は、専用ハードウェア、および、適切なソフトウェアと関連してソフトウェアを実行することが可能なハードウェアを使用することによって提供することができる。プロセッサによって提供されるとき、機能は、単一の専用プロセッサによって、単一の共有プロセッサによって、または、複数の個々のプロセッサによって提供されてもよく、それらのうちのいくつかは共有されてもよい。その上、「プロセッサ」または「コントローラ」という用語が明示的に使用されている場合、これは、ソフトウェアを実行することが可能なハードウェアを排他的に指すように解釈されるべきではなく、黙示的に、限定ではなく、デジタル信号プロセッサ（ＤＳＰ）ハードウェア、ネットワークプロセッサ、特定用途向け集積回路（ＡＳＩＣ）、フィールドプログラマブルゲートアレイ（ＦＰＧＡ）、ソフトウェアを記憶するための読み出し専用メモリ（ＲＯＭ）、ランダムアクセスメモリ（ＲＡＭ）、および不揮発性記憶装置を含んでもよい。従来のおよび／またはカスタムの他のハードウェアも含まれてもよい。同様に、図面に示す任意のスイッチは、概念に過ぎない。それらの機能は、プログラム論理の動作を通じて、専用論理を通じて、プログラム制御および専用論理の相互作用を通じて、または、さらには手動で実行されてもよく、特定の機能は、文脈からより特定的に理解されるように、実装者によって選択可能である。
【００４７】
本明細書における任意のブロック図は、本発明の原理を具現化する例示的な回路の概念図を表すことが、当業者には諒解されるべきである。同様に、任意のフローチャート、流れ図、状態遷移図、疑似コードなどは、実質的にコンピュータ可読媒体において表されてもよく、そのため、コンピュータまたはプロセッサが明示的に図示されているか否かにかかわらず、そのようなコンピュータまたはプロセッサによって実行されてもよい様々なプロセスを表すことが諒解されよう。
【００４８】
本明細書において記載されている例示的な方法のステップは、必ずしも、記載されている順序において実装される必要はなく、そのような方法のステップの順序は、例示に過ぎないと理解されるべきであることも、理解されるべきである。同様に、追加のステップがそのような方法に含まれてもよく、特定のステップが、本発明の様々な実施形態と一致して、方法において省略または組み合わされてもよい。
【００４９】
添付の方法クレーム内の要素は、存在する場合、対応する符号を伴って特定の配列において記載されているが、クレームの表記が、それらの要素の一部または全部を実装するために特定の配列を別途暗示していない限り、それらの要素は必ずしも、その特定の配列において実装されるように限定されるようには意図されていない。
【００５０】
本明細書において、「１つの実施形態」または「一実施形態」が参照されている場合、これは、その実施形態と関連して説明されている特定の特徴、構造、または特性が、本発明の少なくとも１つの実施形態に含まれ得ることを意味する。本明細書内の様々な箇所における「１つの実施形態において」という語句の出現は、必ずしもすべてが同じ実施形態を参照しているとは限らず、別個のまたは代替的な実施形態は、必ずしも他の実施形態と相互に排他的ではない。同じことが、「実施態様」と言う用語にも当てはまる。
【００５１】
本明細書および図面は、本発明の原理を示しているに過ぎない。したがって、本明細書において明示的に記載または図示されていなくても、本発明の原理を具現化し、その精神および範囲内に含まれる様々な構成を当業者が考案することが可能になることが諒解されよう。さらに、本明細書において記載されているすべての例は、主に、読者が、当該技術分野の促進のために本発明者によって与えられる概念および本発明の原理を理解するのを補助する教育的目的のみのためのものであるように明示的に意図されており、そのような特定的に記載されている例および条件に限定されないように解釈されるべきである。その上、本発明の原理、態様、および実施形態ならびにその特定の例を記載している本明細書におけるすべての陳述は、その均等物を包含するように意図されている。
【００５２】
本明細書における任意のブロック図は、本発明の原理を具現化する例示的な回路の概念図を表すことが、当業者には諒解されるべきである。特許請求の範囲において規定されている本発明の範囲から逸脱することなく、上述した本発明の実施形態に、多数の修正、変更および適合を行うことができる。
【図１】
2019522936.tif 000005
【図２】
2019522936.tif 000006
【図３】
2019522936.tif 000007
【図４】
2019522936.tif 000008
【図５】
2019522936.tif 000009
【図６】
2019522936.tif 000010
【図７】
2019522936.tif 000011
【図８】
2019522936.tif 000012
【国際調査報告】
2019522936.tif 000013
2019522936.tif 000014
2019522936.tif 000015