(57)【要約】【課題】複数のネットワーク資源と、複数のクラスタ・メンバを有する少なくとも１つのネットワーク・クラスタとを備える、ネットワークを提供する。【解決手段】クラスタの各メンバは、１つ以上のネットワーク資源を利用し且つその使用を追跡するように構成される。例えば、クラスタの各メンバは、当該メンバによるネットワーク資源の使用を追跡するための１つ以上のトークン・バケットを含む。クラスタの少なくとも１つのメンバ（予約コーディネータ）は、特定のネットワーク資源を宛先とするネットワーク・トラフィックを第１のレート（最大平均持続レート）で受信するための、第１セットのコンピュータ実行可能命令を含む。また、予約コーディネータは、前記第１のレートをクラスタ・メンバの少なくとも１つのサブセット間で配分するための、第２セットのコンピュータ実行可能命令を含む。ある場合には、クラスタの各メンバは、前記第１のレートを前記サブセットのメンバ間で配分する方法を変更するための、第３セットのコンピュータ実行可能命令を含む。例えば、第３セットのコンピュータ実行可能命令は、前記第１のレートの実質的により大きい又はより小さい部分を予約するように試行するための命令を含む。【選択図】  図５
2009543485.tif 000002
【特許請求の範囲】
【請求項１】
複数のクラスタ・メンバを有する一のネットワーク・クラスタに送信されるネットワーク・トラフィックの配分を制御するための方法であって、
特定のネットワーク資源を宛先とするネットワーク・トラフィックを第１のレートで受信するステップを含み、
前記ネットワーク・トラフィックが、複数のクライアント要求を含み、各クライアント要求が、それに割り当てられた一の重みを有し、
前記第１のレートを前記クラスタ・メンバの一のサブセット間で配分するステップをさらに含み、
前記サブセット内の各クラスタ・メンバが、前記特定のネットワーク資源用の一のトークン・バケットを維持し、前記サブセット内の各クラスタ・メンバに配分されるレートの量が、それぞれのトークン・バケット用の一の再生成レートに対応する、方法。
【請求項２】
バーストを前記サブセット間で配分するステップをさらに含む、請求項１記載の方法。
【請求項３】
前記サブセット内の各クラスタ・メンバに配分されるレートの合計が、前記第１のレートに等しく、前記サブセット内の各クラスタ・メンバに配分される前記バーストの合計が、前記ネットワーク・クラスタ用の全バースト出力に等しい、請求項２記載の方法。
【請求項４】
実質的に等しいレートとバーストの合計が前記サブセット内の各クラスタ・メンバに配分される、請求項３記載の方法。
【請求項５】
前記サブセット内の１つ以上のクラスタ・メンバに配分されるレートの量及びバーストの量が、前記サブセット内の他のクラスタ・メンバに配分されるレートの量及びバーストの量と異なる、請求項３記載の方法。
【請求項６】
前記全バースト出力を前記サブセット内の任意のクラスタ・メンバに配分されるバーストの最大の量で割った値が、前記複数のクライアント要求に割り当てられた最大の重み以上である、請求項３記載の方法。
【請求項７】
前記全バースト出力を前記サブセットのアクティブ・メンバ間で再配分するステップをさらに含む、請求項３記載の方法。
【請求項８】
１つの前記クライアント要求を前記サブセット内の１つのクラスタ・メンバに向けるステップと、
前記特定のネットワーク資源の使用を追跡するために、前記１つのクラスタ・メンバ内に格納された一のローカル・トークン・バケットにアクセスするステップとをさらに含み、
前記ローカル・トークン・バケットが、トークンの現在の数を保持し且つ当該ローカル・トークン・バケットに割り当てられた前記再生成レートに等しい第２のレートで追加のトークンを受け入れるように構成可能である、請求項１記載の方法。
【請求項９】
前記ローカル・トークン・バケットから一の数のトークンを消費するステップをさらに含み、
前記ローカル・トークン・バケット内に保持されるトークンの前記現在の数が前記１つのクライアント要求に割り当てられた前記重み以上である場合は、前記一の数が前記１つのクライアント要求に割り当てられた前記重みに等しい、請求項８記載の方法。
【請求項１０】
前記ローカル・トークン・バケットからトークンが消費されたか否かに拘わらず、前記ローカル・トークン・バケットに割り当てられた前記再生成レートを増加させることを試行するステップをさらに含む、請求項９記載の方法。
【請求項１１】
前記試行するステップが、
一の予約要求をいつ満たすべきかを決定するように構成可能な一の推定アルゴリズムに対し、一の予約要求を送信するステップと、
前記推定アルゴリズムから一の予約量を受信するステップとを含み、
前記予約量が、前記１つのクライアント要求がネットワーク・トラフィックの一のバースト内で受信されたか否かに基づく、請求項１０記載の方法。
【請求項１２】
前記１つのクライアント要求がネットワーク・トラフィックの一のバースト内で受信されなかった場合、前記受信するステップが、
前記予約要求が一の指定された沈黙期間中に送信される場合は、前記推定アルゴリズムから一のゼロ予約量を受信するステップと、
前記予約要求が前記指定された沈黙期間の終了後に送信される場合は、前記推定アルゴリズムから一の非ゼロ予約量を受信するステップとを含む、請求項１１記載の方法。
【請求項１３】
前記１つのクライアント要求がネットワーク・トラフィックの一のバースト内で受信された場合、前記受信するステップが、
現在の期間中に前記特定のネットワーク資源のために前記１つのクラスタ・メンバによって受信された全てのネットワーク・トラフィック用の現在のレート消費傾向を決定するステップと、
前記予約要求が一の指定された沈黙期間中に送信される場合、又は前記１つのクラスタ・メンバ用の前記現在のレート消費傾向が減少傾向にあるか若しくは定常傾向にあり且つ前記１つのクラスタ・メンバに配分されるレートの量がゼロより大きい場合は、前記推定アルゴリズムから一のゼロ予約量を受信するステップと、
前記予約要求が前記指定された沈黙期間の終了後に送信される場合は、前記推定アルゴリズムから一の非ゼロ予約量を受信するステップとを含む、請求項１２記載の方法。
【請求項１４】
前記推定アルゴリズムから一の非ゼロ予約量を受信する際に、前記試行するステップが、
前記クラスタ内に前記予約要求を満たすのに十分なレート容量が残存するか否かを決定するように構成可能な一の予約アルゴリズムに対し、前記予約要求を送信するステップと、
前記クラスタ内に前記予約要求を満たすのに不十分なレート容量が残存する場合は、前記予約アルゴリズムから一のゼロ予約量を受信するステップと、
前記クラスタ内に前記予約要求を満たすのに十分なレート容量が残存する場合は、前記予約アルゴリズムから一の非ゼロ予約量を受信するステップとをさらに含む、請求項１３記載の方法。
【請求項１５】
前記予約アルゴリズムから一の非ゼロ予約量を受信する際に、前記非ゼロ予約量を前記ローカル・トークン・バケット用の前記再生成レートに加えることにより、前記１つのクラスタ・メンバに配分されるレートの量を増加させるステップをさらに含む、請求項１４記載の方法。
【請求項１６】
複数のクラスタ・メンバを有する一のネットワーク・クラスタに送信されるネットワーク・トラフィックの配分を制御するための装置であって、
特定のネットワーク資源を宛先とするネットワーク・トラフィックを第１のレートで受信するための手段を備え、
前記ネットワーク・トラフィックが、複数のクライアント要求を含み、各クライアント要求が、それに割り当てられた一の重みを有し、
前記第１のレートを前記クラスタ・メンバの一のサブセット間で配分するための手段をさらに備え、
前記サブセット内の各クラスタ・メンバが、前記特定のネットワーク資源用の一のトークン・バケットを維持するように動作可能であり、前記サブセット内の各クラスタ・メンバに配分されるレートの量が、それぞれのトークン・バケット用の一の再生成レートに対応する、装置。
【請求項１７】
バーストを前記サブセット間で配分するための手段をさらに備える、請求項１６に記載の装置。
【請求項１８】
前記サブセット内の各クラスタ・メンバに配分されるレートの合計が、前記第１のレートに等しく、前記サブセット内の各クラスタ・メンバに配分される前記バーストの合計が、前記ネットワーク・クラスタ用の全バースト出力に等しい、請求項１７に記載の装置。
【請求項１９】
レート及びバーストの実質的に等しい量が、前記サブセット内の各クラスタ・メンバに配分される、請求項１８に記載の装置。
【請求項２０】
前記サブセット内の１つ以上のクラスタ・メンバに配分されるレートの量及びバーストの量が、前記サブセット内の他のクラスタ・メンバに配分されるレートの量及びバーストの量と異なる、請求項１８に記載の装置。
【請求項２１】
前記全バースト出力を前記サブセット内の任意のクラスタ・メンバに配分されるバーストの最大の量で割った値が、前記複数のクライアント要求に割り当てられた最大の重み以上である、請求項１８に記載の装置。
【請求項２２】
前記全バースト出力を前記サブセットのアクティブ・メンバ間で再配分するための手段をさらに備える、請求項１８に記載の装置。
【請求項２３】
１つの前記クライアント要求を前記サブセット内の１つのクラスタ・メンバに向けるための手段と、
前記特定のネットワーク資源の使用を追跡するために、前記１つのクラスタ・メンバ内に格納された一のローカル・トークン・バケットにアクセスするための手段とをさらに備え、
前記ローカル・トークン・バケットが、トークンの現在の数を保持し且つ当該ローカル・トークン・バケットに割り当てられた前記再生成レートに等しい第２のレートで追加のトークンを受け入れるように構成可能である、請求項１６に記載の装置
【請求項２４】
前記ローカル・トークン・バケットから一の数のトークンを消費するための手段をさらに備え、
前記ローカル・トークン・バケット内に保持されるトークンの前記現在の数が前記１つのクライアント要求に割り当てられた前記重み以上である場合は、前記一の数が前記１つのクライアント要求に割り当てられた前記重みに等しい、請求項２３に記載の装置。
【請求項２５】
前記ローカル・トークン・バケットからトークンが消費されたか否かに拘わらず、前記ローカル・トークン・バケットに割り当てられた前記再生成レートを増加させることを試行するための手段をさらに備える、請求項２４に記載の装置。
【請求項２６】
前記試行するための手段が、
一の予約要求をいつ満たすべきかを決定するように構成可能な一の推定アルゴリズムに対し、一の予約要求を送信するための手段と、
前記推定アルゴリズムから一の予約量を受信するための手段とを有し、
前記予約量が、前記１つのクライアント要求がネットワーク・トラフィックの一のバースト内で受信されたか否かに基づく、請求項２５に記載の装置。
【請求項２７】
前記１つのクライアント要求がネットワーク・トラフィックの一のバースト内で受信されなかった場合、前記受信するための手段が、
前記予約要求が一の指定された沈黙期間中に送信される場合は、前記推定アルゴリズムから一のゼロ予約量を受信するための手段と、
前記予約要求が前記指定された沈黙期間の終了後に送信される場合は、前記推定アルゴリズムから一の非ゼロ予約量を受信するための手段とを有する、請求項２６に記載の装置。
【請求項２８】
前記１つのクライアント要求がネットワーク・トラフィックの一のバースト内で受信された場合、前記受信するための手段が、
現在の期間中に前記特定のネットワーク資源のために前記１つのクラスタ・メンバによって受信された全てのネットワーク・トラフィック用の現在のレート消費傾向を決定するための手段と、
前記予約要求が一の指定された沈黙期間中に送信される場合、又は前記１つのクラスタ・メンバ用の前記現在のレート消費傾向が減少傾向にあるか若しくは定常傾向にあり且つ前記１つのクラスタ・メンバに配分されるレートの量がゼロより大きい場合は、前記推定アルゴリズムから一のゼロ予約量を受信するための手段と、
前記予約要求が前記指定された沈黙期間の終了後に送信される場合は、前記推定アルゴリズムから一の非ゼロ予約量を受信するための手段とを有する、請求項２７に記載の装置。
【請求項２９】
前記推定アルゴリズムから一の非ゼロ予約量を受信する際に、前記試行するための手段が、
前記クラスタ内に前記予約要求を満たすのに十分なレート容量が残存するか否かを決定するように構成可能な一の予約アルゴリズムに対し、前記予約要求を送信するための手段と、
前記クラスタ内に前記予約要求を満たすのに不十分なレート容量が残存する場合は、前記予約アルゴリズムから一のゼロ予約量を受信するための手段と、
前記クラスタ内に前記予約要求を満たすのに十分なレート容量が残存する場合は、前記予約アルゴリズムから一の非ゼロ予約量を受信するための手段とをさらに有する、請求項２８に記載の装置。
【請求項３０】
前記予約アルゴリズムから一の非ゼロ予約量を受信する際に、前記非ゼロ予約量を前記ローカル・トークン・バケット用の前記再生成レートに加えることにより、前記１つのクラスタ・メンバに配分されるレートの量を増加させるための手段をさらに備える、請求項２９に記載の装置。
【請求項３１】
請求項１ないし請求項１５の何れか１項に記載の方法の各ステップをコンピュータに実行させるためのコンピュータ・プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、コンピュータ・ネットワーキングに係り、さらに詳細に説明すれば、複数のクラスタ・メンバを有するネットワーク・クラスタ上でトラフィック・シェーピング手順を実装するための方法に係る。
【背景技術】
【０００２】
コンピュータ・ネットワーキングのコンテキストでは、「可用性」という用語は、一般に、状況がどのようなものであれ、要求に応答すべきネットワーク・ノードの能力を意味する。例えば、連続的に使用可能なあるノードは、所与の時間フレーム（例えば、１年）内に実質的に故障時間を有さない。しかし、殆どのネットワーク・ノードは、少なくともある量の故障時間を経験するから、これらのノードは、あるレベルの可用性を有する。例えば、ある「高可用性」ノードは、ほぼ９９．９%の使用可能時間を有し、これを１年当たりの故障時間に換算すると、数時間に相当するに過ぎない。
【０００３】
具体的には、「高可用性」という用語は、一般に、上級ユーザの経験なしに、ネットワーク・プロセス及び関連するデータへの高レベルのアクセスを維持することを意味する。高可用性又は高可用性を維持するための努力から利益を享受するネットワーク・プロセスは、管理プロセス、ファイアウォール・プロセス、ロード・バランシング・プロセス、オペレーティング・システム・プロセス、種々のタイプのサーバ・プロセス（例えば、ＨＴＴＰサーバ、アプリケーション・サーバ及びデータベース・サーバ・プロセス）等を含む。また、高可用性は、アプリケーション・サーバによって使用されるアプリケーション・データ、持続セッション・データ、セキュリティ・データ、トランザクション・ログ・ファイル等の、種々のタイプのネットワーク・データについて望まれることがある。
【０００４】
クラスタリングは、高可用性を達成するための１つのアプローチである。多くの場合、「クラスタ」は、「クラスタ・メンバ」と呼ばれる２つ以上のマシンが、ローカルの高速ネットワーク（即ち、高速のローカル・エリア・ネットワーク（ＬＡＮ））上で相互に結合されるものとして定義される。クラスタ・メンバは、任意のネットワーク・トポロジ（例えば、バス、スター、リング、又はメッシュ構成）を介して、ＬＡＮに接続することができる。一般的でない事例では、異なる地理的位置に存在するクラスタ・メンバが、広域ネットワーク（ＷＡＮ）上で結合されることがある（ＷＡＮの１つの例がインターネットである）。図１は、ＬＡＮ １１０に結合されたネットワーク・クラスタ１００の概要を示す。図１内の点線は、クラスタ・メンバがＷＡＮ １２０上で結合される可能性を示す。
【０００５】
高可用性クラスタは、各々が共通のアプリケーションを実行するように構成された複数の冗長ノードを設けることにより、サービスの可用性を改良する。もし、ノードのうちの１つが故障すれば、この構成は、他のノード（即ち、クラスタ・メンバ）がワークロードを共有し且つ追加のロードを引き継ぐことを可能にする。一般に、高可用性クラスタは、重要なデータベース、ネットワーク上のファイル共有、ビジネス・アプリケーション及び電子商取引Ｗｅｂサイトのような消費者サービスを実装するために使用される。
【０００６】
ある場合には、複数のクラスタ・メンバを同一の物理マシン上で定義することにより（即ち、垂直方向に拡張されたクラスタ）、より効率的な方法でそのマシンに使用可能な処理パワーを割り振ることができる。他の場合には、複数のクラスタ・メンバを複数のマシン上で作成することができる（即ち、水平方向に拡張されたクラスタ）。後者の技術は、単一のシステム・イメージを提示しつつ、複数の異なるマシン上で単一のアプリケーションを実行することを可能にする。その結果、後者の技術を採用しない場合は単一のマシンを圧倒するであろうクライアント要求を、複数の異なるマシン上に配分することができる。両方の技術の利点を享受すべきクラスタを作成する場合は、垂直及び水平方向の拡張方式の組み合わせを使用することができる。
【０００７】
一般に、「ネットワーク・トラフィック制御」という用語は、輻輳、遅延時間及びパケット・ロスを減少させるように、ネットワーク・トラフィックを管理し、優先順位付けし、制御又は減少させるプロセスを意味する。他の機能に加えて、ネットワーク・トラフィック制御は、帯域幅管理及びアドミッション制御手順を含む。
【０００８】
一般に、「帯域幅管理」は、（１）ネットワーク・リンクを一杯に満たさないように、又は（２）ネットワーク・リンクを過剰に満たさないように、当該ネットワーク・リンク上のトラフィックの量を測定し且つ制御するプロセスとして定義される。かかる事象は、ネットワークの輻輳及び性能低下に帰着するからである。２つの共通の帯域幅管理技術は、レート制限（rate limiting）及びトラフィック・シェーピングを含む。
【０００９】
「レート制限」は、ネットワーク・インタフェース上でトラフィックが送信又は受信されるレートを制御する。指定されたレート以下のトラフィックが送信されるのに対し、指定されたレートを超えるトラフィックは除去又は遅延される。一般に、レート制限は、ポリシング（即ち、過剰パケットを廃棄すること）、キューイング（即ち、送信中のパケットを遅延させること）又は輻輳の制御（即ち、プロトコルの輻輳機構を操作すること）により行われる。レート制限を行う装置は、「レート・リミッタ」と呼ばれる。
【００１０】
一般に、「トラフィック・シェーピング」は、性能、低い遅延時間及び／又は帯域幅を最適化又は保証するように、ネットワーク・トラフィックを制御するための試みとして定義される。一般に、トラフィック・シェーピング・アルゴリズムは、分類、キュー規則、ポリシ強制、輻輳管理、サービス品質（ＱｏＳ）及び公平性の概念を処理する。最も一般的なトラフィック・シェーピング・アルゴリズムは、トークン・バケット・アルゴリズム及びリーキー・バケット・アルゴリズムである。
【００１１】
トークン・バケット・アルゴリズムは、バケット内の「トークン」の存在に基づき、トラフィックをいつ送信できるかを指示する。例えば、「トークン・バケット」は、最大でｂ個（通常は特定のバイト数を表す）のトークンを保持する。１／ｒ秒（トークン再生成レートと呼ばれる）ごとに、「トークン」がバケットに加えられる。もし、トークンが到着するとき、バケットが満杯であれば、そのトークンは廃棄される。ｎバイトのパケットが到着する場合、ｎ個のトークンがバケットから除去され、当該パケットがネットワークに送信される。しかし、ｎ個より少ないトークンが使用可能であれば、どのトークンもバケットから除去されず、当該パケットは標準非準拠（non-conformant）であると見なされる。標準非準拠パケットは、これを（１）除去するか、（２）十分なトークンがバケット内に蓄積した時点における後の送信のためにキューに入れるか、又は（３）ネットワークが過負荷になる時点で事後的に除去することができるように、標準非準拠とマークして送信することができる。従って、トークン・バケット・アルゴリズムは、平均データ伝送レートに制限を課すことにより、ネットワーク内に注入されるデータ量を制御する。言い換えれば、トークン・バケット・アルゴリズムは、バケット内に適切なトークンが存在し且つバーストしきい値が適正に構成されていることを条件として、データの「バースト」を（そのピーク・バースト・レートに達するまで）送信することを可能にする。
【００１２】
リーキー・バケット・アルゴリズムは、データ伝送レートにハード制限を課すという点が、トークン・バケット・アルゴリズムと異なる。例えば、底に「穴」があるバケットに着信パケットが入れられるものとする。前述のように、このバケットは、最大でｂバイトを保持することができる。もし、このバケットが満杯であるときに、一のパケットが到着すれば、当該パケットは廃棄される。トークン・バケットと異なり、「リーキー」バケットからｌバイト／秒の一定レートでパケットをフィルタさせることができる。かかるフィルタリングは、（パケット間のスペースを強制することにより）データ伝送レートにハード制限を課し、バースト性データを平準化する効果をもたらす。
【００１３】
一般に、「アドミッション制御」という用語は、ある基準に基づき、ネットワーク資源及びサービスの使用をモニタし、制御し、強制する能力を意味する。例えば、サービス品質（ＱｏＳ）を提供するように努力するネットワークでは、アドミッション制御手順は、種々の優先順位の設定、ポリシ及び／又は使用可能な帯域幅に基づき、ユーザ・セッション（又は個別フロー）を許可又は拒否するために使用することができる。サービス品質保証契約（ＳＬＡ）は、要求元（即ち、ユーザ又はクライアント）に保証されたサービス品質（例えば、使用可能時間、遅延時間、１故障当たりの復旧時間、パケット・ロス、等に関する特定の保証）を提供するように、例えば、サービスごとに及び要求元ごとに強制することができる、アドミッション制御の概念の１つの態様を表す。他のタイプのアドミッション制御も存在する。
【００１４】
アドミッション制御に対する殆どのアプローチは、パケット又はトランスポート・レベルの要求においてレート制限強制を提供する。例えば、通常のアドミッション制御アルゴリズムは、保護されたネットワーク・ノードに流入するメッセージのレートに課された制限を有するバケットを想定する。新しいメッセージが処理される都度、一のトークンがこのバケットに加えられる。バケット・コンテンツは、各インターバル（例えば、毎秒）の後にクリアされ、その結果、メッセージ間のスペースの強制を伴わないレート制限が提供される。一般に、このスライディング・ウィンドウ方法は、「レート・リミッタ・バケット」と呼ばれ、アクティブ・トラフィックの期間中にのみ使用される。
【発明の開示】
【発明が解決しようとする課題】
【００１５】
従来の帯域幅管理及びアドミッション制御手順は、幾つかのネットワークについては適切であるが、クラスタを含むネットワークには適していない。従って、当分野では、クラスタ環境内で実行中のネットワーク資源、サービス及びアプリケーションを保護するために使用することができる、改良された手順が依然として要請されている。
【課題を解決するための手段】
【００１６】
以下、ネットワーク・クラスタに送信されるネットワーク・トラフィックの配分を制御するためのネットワーク及び方法の種々の実施形態を説明する。
【００１７】
１つの実施形態に従って、複数のネットワーク資源と、複数のクラスタ・メンバを有する少なくとも１つのネットワーク・クラスタとを備える、一のネットワークが提供される。以下で詳述するように、前記クラスタの各メンバは、１つ以上の前記ネットワーク資源を利用し且つその使用を追跡するように、個別に構成可能である。ある場合には、前記クラスタ・メンバは、単一の物理マシン上に常駐するか、又は複数のマシン上に分散される。殆どの場合、前記クラスタ・メンバは、高速ローカル・エリア・ネットワーク（ＬＡＮ）を介して相互に結合される。トポロジに拘わらず、前記クラスタの各メンバは、前記ネットワーク・クラスタに送信されるネットワーク・トラフィックの配分を制御するためのトラフィック・シェーピング・ソフトウェアを含む。
【００１８】
例えば、前記クラスタの各メンバは、当該メンバによる特定のネットワーク資源の使用を追跡するための一のローカル・トークン・バケットを含む。前記クラスタの少なくとも１つのメンバ（即ち、「予約コーディネータ」）は、前記ネットワーク資源を宛先とするネットワーク・トラフィックを第１のレート（即ち、最大平均持続レート）で受信するための、第１セットのコンピュータ実行可能命令を含む。また、予約コーディネータは、前記第１のレートを前記クラスタ・メンバの少なくとも１つのサブセット間で配分するための、第２セットのコンピュータ実行可能命令を含む。前記サブセットの各メンバに配分されるレートの量は、それぞれのローカル・トークン・バケット用の再生成レートに対応する。ある場合には、前記第２セットのコンピュータ実行可能命令を、前記サブセットのアクティブ・メンバ間でバーストを配分するようにさらに構成することができる。以下で詳述するように、バースト割り振りを、前記サブセットのアクティブ・メンバ間である程度均等に配分することができる。しかし、バーストの任意の配分をも使用することができる。
【００１９】
ある場合には、前記クラスタの各メンバは、前記第１のレートを前記サブセットのメンバ間で配分する方法を変更するための、第３セットのコンピュータ実行可能命令を含む。例えば、前記第３セットのコンピュータ実行可能命令は、前記第１のレートのより大きな部分を予約するように試行するための第４セットのコンピュータ実行可能命令と、前記第１のレートのより小さな部分を予約するように試行するための第５セットのコンピュータ実行可能命令を含む。以下で詳述するように、前記第４セットのコンピュータ実行可能命令は、一のクライアント要求を満たすための追加のレート容量を予約するために使用される。これに対し、前記第５セットのコンピュータ実行可能命令は、再配分のためにレート容量を前記クラスタに解放するために使用される。
【００２０】
他の実施形態に従って、複数のクラスタ・メンバを有する一のネットワーク・クラスタに送信されるネットワーク・トラフィックの配分を制御するための方法が提供される。ある場合には、この方法は、特定のネットワーク資源を宛先とするネットワーク・トラフィックを第１のレートで受信する。以下で詳述するように、前記ネットワーク・トラフィックは、複数のクライアント要求を含み、当該クライアント要求の各々は、それに割り当てられた一の重みを有する。次に、この方法は、前記第１のレートを前記クラスタ・メンバの少なくとも１つのサブセット間で配分する。前述のように、前記サブセット内の各メンバは、前記特定のネットワーク資源用の一のローカル・トークン・バケットを含む。前記サブセット内の各メンバに配分されるレートの量は、それぞれのローカル・トークン・バケット用の再生成レートに対応する。
【００２１】
また、この方法は、バーストを前記サブセットのアクティブ・メンバ間で配分する。ある場合には、レート及びバーストの実質的に等しい量を前記サブセットの各メンバに配分する。他の場合には、前記サブセットの１つ以上のメンバに配分されるレートの量及びバーストの量は、前記サブセットの他のメンバに配分されるレートの量及びバーストの量と異なる。特定のレート配分に拘わらず、前記サブセット内の各メンバに配分されるレートの合計は、前記第１のレートと実質的に等しくなければならない。同様に、前記サブセット内の各メンバに配分されるバースト割り振りの合計は、前記ネットワーク・クラスタ用の全バースト出力と実質的に等しくなければならない。もし、前記サブセットの１つ以上のメンバが故障するか、又はオフラインにされるのであれば、全バースト出力を前記サブセットの残存するアクティブ・メンバ間で再配分することができる。
【００２２】
前記第１のレートを配分した後、この方法は、１つの前記クライアント要求を前記サブセット内の１つのクラスタ・メンバに向けるステップと、前記特定のネットワーク資源の使用を追跡するために前記１つのクラスタ・メンバ内に格納されたローカル・トークン・バケットにアクセスするステップとを含む。概して言えば、前記ローカル・トークン・バケットは、トークンの現在の数を保持し且つ当該ローカル・トークン・バケットに割り当てられた再生成レートに等しい第２のレートで追加のトークンを受け入れるように構成することができる。もし、前記ローカル・トークン・バケット内に保持されるトークンの前記現在の数が、前記１つのクライアント要求に割り当てられた前記重み以上であれば、一の数（即ち、前記１つのクライアント要求に割り当てられた重みに等しい数）のトークンが、前記ローカル・トークン・バケットから消費される。しかし、前記１つのクライアント要求を満たすのに不十分な数のトークンが前記ローカル・トークン・バケット内に残存すれば、如何なるトークンも消費されない。
【００２３】
次に、この方法は、トークンが実際に消費されたか否かに拘わらず、前記ローカル・トークン・バケットに割り当てられた再生成レートを増加させることを試行する。例えば、一の予約要求をいつ満たすべきかを決定するように構成可能な一の推定アルゴリズムに対し、一の予約要求を送信する。前記推定アルゴリズムは、前記ネットワーク・トラフィックのある特性に基づき、一の予約量を戻すことができる。
【００２４】
もし、前記１つのクライアント要求が実質的に切れ目のないトラフィック内で受信されたならば、前記推定アルゴリズムによって戻される前記予約量は、前記予約要求が受信される時間にのみ依存する。例えば、前記予約要求が一の指定された沈黙期間中に送信されるならば、前記推定アルゴリズムは、一のゼロ予約量を戻す。他方、前記予約要求が前記指定された沈黙期間の終了後に送信されるならば、一の非ゼロ予約量が戻される。
【００２５】
しかし、前記１つのクライアント要求が、ネットワーク・トラフィックの一のバースト内で受信されたならば、前記予約量は、前記１つのクラスタ・メンバの種々の特性にも依存する。例えば、この方法は、前記特定のネットワーク資源のために前記１つのクラスタ・メンバによって受信された全てのネットワーク・トラフィック用の現在のレート消費傾向を決定する。前記現在のレート消費傾向は、現在の期間中に受信されたネットワーク・トラフィックの平均レートを、先行する期間中に受信されたネットワーク・トラフィックの平均レートと比較することにより、決定することができる。前記現在のレート消費傾向は、（１）前記現在の期間の平均レートが前記先行する期間の平均レートよりも高ければ、増加傾向にあり、（２）前記現在の期間の平均レートが前記先行する期間の平均レートに等しければ、定常傾向にあり、（３）前記現在の期間の平均レートが前記先行する期間の平均レートよりも低ければ、減少傾向にあると見なすことができる。
【００２６】
前記推定アルゴリズムが一のゼロ予約量を戻すのは、（ａ）前記予約要求が一の指定された沈黙期間中に送信される場合、又は（ｂ）前記１つのクラスタ・メンバ用の前記現在のレート消費傾向が減少傾向にあるか若しくは定常傾向にあり且つ前記１つのクラスタ・メンバに配分されるレートの量がゼロを超える場合である。他方、前記指定された沈黙期間の終了後に前記予約要求が送信される場合は、前記推定アルゴリズムは、一の非ゼロ予約量を戻す。
【００２７】
前記推定アルゴリズムから一の非ゼロ予約量を受信する際、前記予約要求は、一の予約アルゴリズムに送信される。前記予約要求が許可されるのは、前記クラスタ内に前記予約要求を満たすのに十分なレート容量が存在する場合である。例えば、前記予約アルゴリズムは、（それぞれのローカル・トークン・バケット内に格納された）全てのクラスタ・メンバの現在のレート消費を、前記クラスタ全体の最大平均持続レートと比較する。もし、前記１つのクラスタ・メンバが前記追加のレート容量を求める結果として、全てのメンバの組み合わされた予約容量が最大平均持続レートを超えれば、前記予約アルゴリズムは、前記予約要求を拒否し且つ一のゼロ予約量を戻す。さもなければ、前記予約アルゴリズムは、前記予約要求を許可し且つ一の非ゼロ予約量を戻す。前記予約要求が許可される場合、前記１つのクラスタ・メンバに配分されるレートの量を増加させるため、前記非ゼロ予約量がそのローカル・トークン・バケット用の前記再生成レートに加えられる。
【００２８】
追加のレート容量を予約することに加えて、他のクラスタ・メンバへの再配分のために、レート容量を前記クラスタに解放するための方法が提供される。
【００２９】
好ましくは、この方法は、前記サブセットの１つ以上のクラスタ・メンバが故障するか、又はオフラインにされるのであれば、前記全バースト出力を前記サブセットのアクティブ・メンバ間で再配分するステップをさらに含む。
【００３０】
好ましい実施形態では、一のネットワークが提供される。このネットワークは、複数のネットワーク資源と、複数のクラスタ・メンバを有する一のネットワーク・クラスタとを備え、各クラスタ・メンバは、１つ以上の前記ネットワーク資源を使用し且つその使用を追跡するように個別に構成可能である。好ましくは、前記クラスタの各メンバは、当該メンバによる１つ以上のネットワーク資源の使用を追跡するための１つ以上のトークン・バケットを保持する、個別のデータベースを備える。より好ましくは、前記クラスタの少なくとも１つのメンバは、特定のネットワーク資源を宛先とし且つ複数のクライアント要求を含むネットワーク・トラフィックを第１のレートで受信するように構成可能な第１セットのコンピュータ実行可能命令と、前記第１のレートをクラスタ・メンバの一のサブセット間で配分するように構成可能な第２セットのコンピュータ実行可能命令とを備え、前記サブセット内の各メンバは、前記特定のネットワーク資源用の一のローカル・トークン・バケットを維持し、また前記サブセット内の各メンバに配分されるレートの量は、それぞれのローカル・トークン・バケット用の一の再生成レートに対応する。さらに好ましくは、前記第２セットのコンピュータ実行可能命令は、前記サブセットのアクティブ・メンバ間でバーストを配分するように構成可能である。
【００３１】
好ましい実施形態では、前記クラスタの各メンバは、前記第１のレートを前記サブセットのメンバ間で配分する方法を変更するための第３セットのコンピュータ実行可能命令を備える。好ましくは、前記第３セットのコンピュータ実行可能命令は、前記第１のレートのより大きな部分を予約するように試行するための第４セットのコンピュータ実行可能命令と、前記第１のレートのより小さな部分を予約するように試行するための第５セットのコンピュータ実行可能命令とを含む。より好ましくは、前記第４セットのコンピュータ実行可能命令は、任意の所与の時間において前記サブセットの１つのメンバだけによって実行される。さらに好ましくは、前記第５セットのコンピュータ実行可能命令は、前記サブセットの全てのメンバによって直ちに実行される。
【発明を実施するための最良の形態】
【００３２】
多くの場合、ネットワーク・クラスタは、「クラスタ・メンバ」と呼ばれる２つ以上のマシンが、ローカル・エリア・ネットワーク（ＬＡＮ）又は広域ネットワーク（ＷＡＮ）上で相互に結合されるものとして定義される。一般に、ネットワーク・クラスタが作成される目的は、（１）ワークロードをクラスタ・メンバ間で配分することにより、ロード・バランシングを提供すること、（２）一の計算タスクをクラスタ・メンバ間で分割することにより、性能を改良すること、又は（３）共通のアプリケーションを実行する複数の冗長ノードを設けることにより、サービスの可用性を改良することにある。一般に、サービスの可用性を改良するように実装されたクラスタは、「高可用性クラスタ」と呼ばれる。
【００３３】
１つの例では、高可用性クラスタは、相互に管理され且つワークロード管理（ＷＬＭ）に関与する、１セットのアプリケーション・サーバを含む。一のクラスタに関与する当該アプリケーション・サーバ（即ち、クラスタ・メンバ）は、同じネットワーク・ノード上で又は異なるノード上で実装することができる。従って、一般化すると、「クラスタ」は、当該クラスタに関与するマシン及び当該マシンに関連するワークロード容量の論理表現として定義される。アプリケーション・サーバに加えて、クラスタは、他のタイプのサーバ及びシステム（例えば、ＨＴＴＰサーバ、ロード・バランサ、データベース・サーバ及び他のデータ・ストレージ媒体）を結合することにより、作成することができる。
【００３４】
図２は、１グループのアプリケーション・サーバ（例えば、アプリケーション・サーバ１〜４）が、複数のネットワーク・ノード（例えば、ノードＡ及びＢ）上で相互にクラスタ化される、１つの態様を例示する。殆どの場合、これらのネットワーク・ノードは、高速ＬＡＮ上で結合されるが、他の場合にはＷＡＮを使用することができる。図２の特定の例では、クラスタ化されたアプリケーション・サーバは、単一のシステム・イメージを維持しつつ、処理パワーを最適化し且つワークロードを配分するように、垂直方向及び水平方向に拡張される。また、図２の構成は、データベース・サーバ（例えば、ＤＢ １及びＤＢ ２）のクラスタを作成することにより、データ・フェイルオーバをサポートする。必要に応じて、本明細書には開示していない他のクラスタ構成も作成することができる。
【００３５】
ある場合には、ロード・バランサ（ＬＢ）及びＨＴＴＰサーバと協力して、ワークロード（即ち、当該クラスタに送信される要求の量）を、クラスタ・メンバ（アプリケーション・サーバ１〜４）間で、配分又は「平衡化」することができる。サービスの可用性を改良するために、当該クラスタに配備されたアプリケーションは、全てのクラスタ・メンバ上で同時に実行される。ある場合には、ワークロード管理（ＷＬＭ）及びフェイルオーバ手順を実装することにより、高可用性を提供することができる。例えば、ワークロード管理は、要求がクラスタ・メンバに経路指定される方法を制御することにより、当該クラスタ・メンバがワークロードを共有し且つクライアント要求のスループットを改良することを可能にする。もし、当該クラスタ内の一のサーバが故障すれば、当該故障したサーバに現に送信されている任意のクライアント要求を、残存するアクティブ・サーバのうちの１つに宛先変更することができる。一般に、かかるフェイルオーバは、サービスの中断なしに、又はクライアント側の任意の特別アクションを必要とすることなく、これを行うことができる。
【００３６】
ある場合には、図２のアプリケーション・サーバは、一の高可用性フレームワークを利用することにより、サービス及びサーバ上で実行中のアプリケーションの正常性をモニタすることができる。高可用性フレームワークの１つの例は、ＩＢＭ社によって開発された WebSphere Application Server（ＷＡＳ）で見つけることができる。WebSphere Application Server は、Ｗｅｂサービス技術を使用して、複数のコンピューティング・プラットフォーム上で電子商取引アプリケーションをセットアップし、操作し且つ統合するように設計された、ＩＢＭ専有ソフトウェアを実行する。ＷＡＳのネットワーク配備バージョン６．０は、フェイルオーバ・サポートを有するクラスタ化セル構成の配備をサポートするとともに、プロキシ・サーバ、ロード・バランシング及びコンテンツ・ベースの経路指定を提供する。
【００３７】
前記高可用性フレームワークが提供する主な機能は、（１）グループ・メンバシップ（即ち、一のクラスタのメンバを一のグループに属するものとして識別する能力）、（２）予約コーディネータの選択（即ち、一のクラスタの１つ以上のメンバを予約コーディネータとして選択する能力）、（３）グループ間メッセージング（即ち、当該グループのメンバにメッセージを送信する能力）、及び（４）仮想シンクロニシティ（即ち、高速且つ遅延時間が小さいＬＡＮ上のメッセージングを通して、仮想的な同期オペレーションを達成する能力）を含む。以下で詳述するように、元々ＷＡＳ内に含まれていた前記高可用性フレームワークは、本発明に従って、クラスタ環境用のアドミッション制御及びトラフィック・シェーピング手順を提供するように更新された。しかし、本明細書に開示した発明概念は、ＷＡＳ環境に限定されないのであり、任意のクラスタにも実質的に適用することができる。
【００３８】
従来技術の殆どのアドミッション制御及びトラフィック・シェーピング・アルゴリズムは、ネットワークの周辺又は「エッジ」上に位置するエッジ・ルータ内でローカルに実行される。一般に、これらのアルゴリズムによって使用されるレート制限及びバケット・コンテンツは、当該ネットワーク内の各マシンごとに強制／追跡される。この理由で、従来技術のアドミッション制御及びトラフィック・シェーピング・アルゴリズムは、一般に、クラスタ環境に適用することができない。即ち、クラスタ環境では、複数のクラスタ・メンバ間で共有される個々のアプリケーション、サービス及び／又はオペレーションについて、レート制限を強制し且つバケット・コンテンツを追跡することが望ましいからである。また、従来技術のアルゴリズムは、セッション類似性（即ち、初期接続後にワークロード管理を不能にし且つクライアントの要求が同じサーバに送信されるように強制する条件）に依存するサービス及びアプリケーション内で生じるような、レート配分の変化に適合することができない。
【００３９】
セッション類似性に依存するサービス及びアプリケーションの例は、セッションの間中、ユーザ情報（例えば、ユーザのショッピング・カート）を維持する、電子商取引Ｗｅｂサイト及び他のＷｅｂサービスを含む。他の例は、同じバックエンド・データベースを使用して要求をバインドする、Ｗｅｂアプリケーションである。当該要求は、データベース・エラーを回避するために、同じアプリケーション・サーバに経路指定される。また、セッション確立プロトコル（ＳＩＰ）を利用するアプリケーションは、所与のセッション用の全ての要求を特定のアプリケーション・サーバに経路指定するために、セッション類似性に依存する。
【００４０】
前述の諸問題を解決するため、前記高可用性フレームワークは、一のクラスタの複数のメンバ間でレート制限及びバケット・コンテンツを配分するための手段を提供するように更新された。また、クラスタ・メンバ間のレート制限及びバケット・コンテンツの配分をモニタし且つ制御するための、改良されたアドミッション制御及びトラフィック・シェーピング・アルゴリズムが提供される。その結果、これらのアルゴリズムは、（アドミッション制御用の）レート配分及び（トラフィック・シェーピング用の）バースト割り振りの変化に適合することができる。例えば、当該クラスタへのレート配分が変わる場合（但し、一のグローバル・レート制限を超えないものとする）、改良されたアドミッション制御アルゴリズムは、新しい配分に従って当該クラスタのメンバ間でレートを再配分することができる。もし、１つ以上のクラスタ・メンバが故障するか、オフラインにされるならば、改良されたトラフィック・シェーピング・アルゴリズムは、同様のアプローチを使用して、バースト割り振りをアクティブなクラスタ・メンバ間で再配分する。
【００４１】
図３〜図１１は、本発明の種々の側面を例示する。例えば、図３及び図４は、レート制限を複数のクラスタ・メンバ（例えば、メンバ１〜Ｎ）間で階層式に配分することができる、種々の方法を明示する。以下で詳述するように、一のレート制限ツリーを使用することにより、レート制限を複数のクラスタ・メンバ間で配分することができる。このことは、これらのメンバによって提供される種々のサービス、アプリケーション及びオペレーションについても同様である。図５〜図７のフローチャートは、本発明に従った、改良されたアドミッション制御アルゴリズムの１つの実施形態を例示する。図９〜図１１の追加のフローチャートは、ネットワーク資源の使用をモニタし且つ制御するための、改良されたトラフィック・シェーピング・アルゴリズムの使用方法を例示する。図８は、資源用のバースト割り振りをクラスタ・メンバ間で動的に配分し且つ追跡するための１つの態様を例示する。
【００４２】
本発明に従った、改良されたアドミッション制御アルゴリズム及びトラフィック・シェーピング・アルゴリズムは、各々が一の高可用性フレームワークの主な機能を利用するという点で互いに類似している。例えば、当該クラスタの１つのメンバは、「予約コーディネータ」として選択される。以下で詳述するように、クラスタの任意のメンバを予約コーディネータとして選択することができる。もし、この選択された予約コーディネータが何らかの理由で故障すれば、新しい選択が行われ、一のメッセージを各メンバに送出することにより、各メンバの状態が（グループ間メッセージングを介して）リセットされ、その後、これらのアルゴリズムが再び開始する。前記選択された予約コーディネータは、レート・ディーラとして活動する。例えば、各メンバは、要求の引き渡しを可能にするために、予約コーディネータからあるレートを予約しなければならない。レート配分の変化に適応するために、当該クラスタの各メンバは、一の推定アルゴリズム（以下「エスティメータ」と称する）を実行することにより、リアルタイムのレート容量推定を行う。
【００４３】
以下で詳述するように、エスティメータは、追加のレート容量をいつ予約すべか又はレート容量をクラスタにいつ解放すべきかを決定するために使用される。例えば、エスティメータが、一のクラスタ・メンバに現に送信されているクライアント要求の流入を満たすために追加のレート容量が必要であることを決定すれば、当該クラスタ・メンバは、一の予約要求をアクティブな予約コーディネータに送信することにより、追加のレートを予約することができる。同様に、エスティメータが、一のクラスタ・メンバに割り当てられた現在のレート容量が十分に利用されていないことを決定すれば、レート容量を当該クラスタに解放することにより、これを再配分することができる。殆どの場合、レート容量は、速度を増加させ且つ（クラスタ・メンバ間の通信パス上の帯域幅を消費する）グループ間メッセージングを減少させるために、チャンクの形式で要求され且つ解放される。
【００４４】
＜アドミッション制御のための階層的レート制限＞
前述のように、「レート・リミッタ・バケット」は、アドミッション制御手順を実装するために一般的に使用されるアルゴリズムである。従来技術のアルゴリズムでは、「バケット」は、保護されたネットワーク・ノードに流入するメッセージのレートに課される一の制限を具備する。新しいメッセージが処理される都度、一の「トークン」が当該バケットに加えられる。そのため、前記レート制限は、１つのトークンが１つのメッセージを表すものとして、トークン数／秒でしばしば表現される。バケット・コンテンツは、パケット間のスペースを強制することなくレート制限を提供するために、各インターバル（例えば、毎秒）の後にクリアされる。
【００４５】
かかるアルゴリズムを簡述するため、当該バケットに課されたレート制限が１０トークン／秒であるものと仮定する。また、同じ期間中に、第１の要求が当該バケットに２つのトークンを加え、第２の要求が当該バケットに８つのトークンを加えるものと仮定する。最初の２つの要求の後に制限に達したので、当該アルゴリズムは、同じ期間内に到着する後続の要求を拒否することにより、レート制限を提供する。
【００４６】
前述の従来技術のアドミッション制御アルゴリズムは、幾つかのネットワークについては適切であるが、クラスタ環境には適用することができない。例えば、前記バケットに課されたレート制限は、クラスタ全体のレート容量を表す。従来技術のアルゴリズムは、クラスタ・メンバによって提供される種々のサービス、アプリケーション及びオペレーションの必要性に対処するために、当該クラスタ・メンバ間でレート容量を配分するための手段を提供しない。また、従来技術のアルゴリズムは、レート容量の配分をモニタし且つ制御するための手段を提供しないのであり、従って、レート配分の変化をもたらすようなサービス及びアプリケーション（例えば、セッション類似性に依存する集中アプリケーション及び他のサービス）を保護するために、これを使用することができない。
【００４７】
前述の諸問題を解決するため、基本的なレート・リミッタ・アルゴリズムは、アドミッション制御用の階層的なレート制限強制を提供するように拡張された。クラスタ全体用の一のグローバル・レート制限を指定する代わりに、当該グローバル・レート制限は、必要に応じて、クラスタ・メンバ間で配分される。図３及び図４に示すように、レート制限は、「レート制限ツリー」を形成する階層的な方法で配分することができる。幾つかの実施形態では、図３に示すように、レート制限は、これをグローバル・レベルで設定することができ、さらには当該クラスタの各メンバ（１〜Ｎ）ごとにサービス及びオペレーション・レベルで設定することができる。クラスタ・メンバによって提供されるサービス及びオペレーションの１つの例は、多くのＷｅｂサービスで利用される StockQuote サービス及び getQuote（）オペレーションである。しかし、他の例も存在する。他の実施形態では、前記レート制限ツリーは、図３のものと異なる数及び／又はタイプのレベルを含むことがある。前記レート制限ツリーに課される唯一の要件は、一の親ノードに課された各レート制限が、その子ノードに課された制限の合計に等しいということである。例えば、サービス１に割り当てられたレート制限は、サービス１の子孫であるオペレーション１〜Ｎに割り当てられた制限の合計に等しくなければならない。
【００４８】
後述するように、改良されたアドミッション制御アルゴリズムは、前記「レート制限ツリー」内で指定された各レベルにおけるレート消費を追跡するための、一の「レート・リミッタ・バケット・ツリー」を含むことができる。ある場合には、バケット・コンテンツは、抽象トークン（即ち、必ずしも１つのパケットに対応しないトークン）で測定される。こうすることにより、重み付け（即ち、幾つかの要求が複数のトークンを消費すること）が可能になる。例えば、要求レートがＮトークン／秒で且つ各要求の重みが１であれば、トークン制限は、Ｎ要求／秒に対応する。もし、各要求の重みがＭであれば、トークン制限は、Ｎ／Ｍ要求／秒に対応する。
【００４９】
一の要求を許可することができるか否かを確認する場合、前記レート・リミッタ・バケット・ツリーは、グローバル・レベルから１つの子ノードに至る一のパスに沿って探索される。前述のように、当該パスに沿って各バケットに割り当てられるレート制限は、その子ノードに課された制限の合計である。一の子ノード（例えば、オペレーション１）に対する一の要求を許可するためには、当該要求は、当該探索されたパス（例えば、グローバル−＞サービス１−＞オペレーション１）に沿った各バケットに適合できなければならない。もし、当該要求が各バケットに適合すれば、当該パスに沿った各バケットにその要求トークンが加えられる。もし、当該要求トークンが当該パスに沿った各バケットに適合しなければ、これらの要求トークンは加えられず、当該要求が拒否される。
【００５０】
かかるアルゴリズムを簡述するため、１００トークン／秒のレート制限がサービス１に割り当てられ、７５トークン／秒のレート制限がその子孫であるオペレーション１〜Ｎの各々に割り当てられるものと仮定する。また、オペレーション１に対する第１の要求がオペレーション１のバケットに５０トークンを加え、オペレーション３に対する第２の要求がオペレーション３のバケットに７５トークンを加えることを試行するものと仮定する。もし、第２の要求が第１の要求と同じ期間内に到着すれば、第２の要求は、たとえそれがオペレーション３に割り当てられたレート制限を超えなくても、拒否されるであろう。なぜなら、オペレーション１及び３に対する第１及び第２の要求の組み合わされたレート（即ち、１２５トークン／秒）が、サービス１（即ち、親ノード）に課されたレート制限を超えるからである。
【００５１】
図４は、一の「レート制限ツリー」内でレート制限を配分し、一の「レート・リミッタ・バケット・ツリー」内でバケット・コンテンツを追跡するための、他の方法を例示する。例えば、レート制限は、前述のグローバル、サービス及びオペレーション・レベルに加えて、要求元レベルで配分／追跡することができる。「要求元」とは、当該クラスタによって提供される特定のサービス又はアプリケーションへのアクセスを要求する、一のクライアント又はユーザとして定義される。ある場合には、図４のツリー構造は、サービス品質保証契約（ＳＬＡ）の配分強制を含むように、アドミッション制御の概念を拡張するために使用することができる。
【００５２】
サービス品質保証契約（ＳＬＡ）とは、一のネットワーク・サービス・プロバイダと一の顧客との間の契約であって、一般に、当該ネットワーク・サービス・プロバイダが提供するサービスを測定可能な条件で指定するものである。多くのインターネット・サービス・プロバイダ（ＩＳＰ）が、ＳＬＡの下で、それらの顧客にサービスを提供する。他の測定法に加えて、ＳＬＡは、当該サービスに同時にアクセス可能なユーザ（即ち、要求元）の数に関するサービス品質保証や、サービス使用可能時間、遅延時間、１故障当たりの復旧時間、パケット・ロス等のサービス品質保証を提供することができる。サービス品質保証を提供するために、多くのＳＬＡは、１要求元当たりのサービス及び／又はオペレーションのレート制限を指定する。一般に、ＳＬＡのレート制限は、ポリシ駆動型であって、単なる条項的なものではなく、動的に更新可能でなければならない。
【００５３】
一般に、ＳＬＡのレート制限を管理するポリシは、一のポリシ・データベース内に格納され、メッセージ処理中にシステムにアクセス可能にされる。一のサービスへのアクセスを有する多数の要求元が存在するという理由で、従来は、ＳＬＡのレート制限情報は、各メッセージによって局所的な方法でのみ使用可能にされていた。例えば、ＳＬＡのレート制限は、メッセージ処理の時点で、ポリシ・データベースからしばしば検索されていた。従って、制限情報は、メッセージ処理の前には使用不能であったし、一のクラスタの個々のメンバがこれを使用することもできなかった。以下で詳述するように、本明細書に開示したＳＬＡ強制のためのアドミッション制御アルゴリズムは、少なくともクラスタ・メンバのサブセットに対しＳＬＡのレート制限に関する知識を先験的に提供することにより、従来技術の方法を改良する。
【００５４】
本明細書には、階層的レート・リミッティングの少数の例だけが開示されているに過ぎないことに留意されたい。本発明の概念は、図３及び図４のツリー構造だけに限定されない。図３及び図４に示すツリー構造に加えて、レート制限は、異なる数及び／又はタイプのレベル間で配分することができる。しかし、レベルの数、従ってツリー内の葉の数が拡大するにつれて、予約推定を正確に行うことがますます高価になる点に留意されたい。
【００５５】
＜分散式アドミッション制御／ＳＬＡ強制のための方法＞
本明細書に開示したアドミッション制御アルゴリズムは、一のクラスタ環境で使用可能な方法を提供することにより、基本的なレート・リミッタ・バケット・アルゴリズムを改良する。そうするために、改良されたアドミッション制御アルゴリズムは、グループ・メンバシップ、予約コーディネータの選択及びグループ間メッセージング等を含む、高可用性フレームワークの主な機能を利用する。前述のように、当該クラスタの１つのメンバは、「予約コーディネータ」として選択される。殆どの場合、予約コーディネータの選択には、如何なる制限も課されない。即ち、当該クラスタの任意のメンバを予約コーディネータとして選択することができる。もし、選択された予約コーディネータが何らかの理由で故障すれば、一のメッセージを（グループ間メッセージングを介して）残存するクラスタ・メンバに送出することにより、当該クラスタ・メンバの状態がリセットされ、その後、アドミッション制御アルゴリズムが再び開始する。
【００５６】
ある場合には、予約コーディネータは、当該クラスタ全体用の一のレート制限ツリー（「クラスタ・ツリー」と呼ばれる）と、当該クラスタの各メンバごとの別個のレート制限ツリー（「メンバ・ツリー」と呼ばれる）を維持する。前記クラスタ・ツリーは、当該クラスタの全てのメンバ間のレート制限及び消費を追跡するために使用される。前記メンバ・ツリーは、特定のメンバに割り振られたレート制限をクラスタ制限と比較するために使用される。例えば、一のメンバ・ツリーの各ノード用に指定されたレート制限は、前記クラスタ・ツリー内で指定されたレート制限のあるシェアに対応するであろう。メンバ消費は、各クラスタ・メンバ内に格納されたローカル・レート・リミッタ・バケット・ツリー内で追跡される。
【００５７】
任意のメンバを予約コーディネータとして選択可能であるという理由で、レート制限情報は、当該クラスタの各メンバにアクセス可能でなければならない。また、幾つかの実施形態では、前記クラスタ・ツリーは、全ての各クラスタ・メンバ内にローカルに格納することができる。このようにすると、現在の予約コーディネータが故障したとしても、任意のメンバは、クラスタ制限への即時アクセスをすることができる。しかし、前記クラスタ・ツリーの複数のコピーを維持することは、メモリ消費量及び（ネットワーク帯域幅を消費する）グループ間メッセージングが増加するという欠点がある。従って、他の方法でレート制限情報をクラスタ・メンバに提供することが望ましいであろう。
【００５８】
１つの例では、前記クラスタ・ツリーは、クラスタ・メンバの小さなサブセットだけにローカルに格納することができる。この場合、クラスタ・ツリー情報を当該クラスタの全てのメンバに送出する必要がないので、メモリ及びグループ間メッセージングを減少させることができる。他の例では、前記クラスタ・ツリーを、別個の構成データベース内に格納することができる。その場合、適切なレート制限情報を、予約コーディネータに送信される各予約要求と結合することができる。後者の例では、予約コーディネータが、クラスタ制限を発見することが可能になり、しかも新しい更新済みの制限を動的に発見することが可能になる。もし、前記制限情報が各予約要求と結合されるならば、予約コーディネータは、前記クラスタ・ツリーのうち一のノードの消費がゼロである（従って、その子ノードもゼロである）ような任意のセクションを忘れることができ、その結果、空ノードの簡単なクリーンアップ及びメモリの節約が可能となる。その場合、前記クラスタ・ツリー構造は、後続の予約要求中に「再発見」することができるであろう。
【００５９】
一のクラスタ・メンバが（一のクライアント要求を満たすために）より多くのレートを使用することを望む場合、当該メンバは、追加の「予約量」を求める一の「予約要求」を予約コーディネータに送信する。予約コーディネータは、当該追加の予約量を当該クラスタ用のグローバル制限と比較し、当該予約要求を許可すべきか否かを決定する。もし、当該追加の予約量が前記指定された制限以下であれば、当該予約要求を許可することができる。さもなければ、当該予約要求は、ゼロ予約量で拒否される。フェイルオーバは、単純な機構を使用して処理される。即ち、各予約要求が、それに関連する一の期間を有するということである。もし、この期間内に一の「キープ・アライブ」が送信されなければ、当該予約が除去される。
【００６０】
図５は、改良されたアドミッション制御アルゴリズムの１つの実施形態を例示するフローチャートである。一のクライアント要求を許可すべきか否かを決定する場合、改良されたアドミッション制御アルゴリズムは、（一のレート・リミッタ・バケット・ツリー内にローカルに格納された）一のクラスタ・メンバの現在のレート消費を、（予約コーディネータ内に格納された）当該メンバのレート制限ツリー内で指定されたレート制限と比較する。具体的には、当該アルゴリズムは、前記グローバル・レート・バケットと、当該クラスタ・メンバのレート・リミッタ・バケット・ツリー内に含まれる１つの子ノード・バケットとの間の一のパスを探索する。もし、当該探索されたパスに沿った各バケットに対し要求トークンを加えるのに十分な余地があれば、当該要求が許可される。さもなければ、エスティメータを呼び出して、当該クライアント要求を満たすために追加のレート容量を予約することができるか否かを決定する。もし、前記クラスタ・ツリー内で十分なレートが使用可能であれば、追加のレート容量を要求中のメンバに与えることができる。
【００６１】
ある場合には、図５のアドミッション制御アルゴリズムは、図３及び図４に示すレート制限（又はレート・リミッタ・バケット）ツリーのうちの１つを使用することにより、一のクライアント要求を許可することができるか否かを決定することができる。そのため、当該アドミッション制御アルゴリズムを使用することにより、一般的なアドミッション制御手順を実装するか、又はサービス品質保証契約内で指定されたレート制限を強制することができる。前述のように、当該アドミッション制御アルゴリズムは、本明細書に詳細に開示していない代替的なツリー構造も、使用することができる。
【００６２】
図５に示すように、アドミッション制御／ＳＬＡアルゴリズムは、現在のクライアント要求用に指定された重み付けを用いて、エスティメータを更新する（ステップ５００）。言いかえれば、エスティメータは、「移動平均（moving average）」、即ち各期間中に各クラスタ・メンバによって消費されるトークンの数のカウントを維持する。殆どの場合、各期間は１秒として定義されるから、このカウントは、当該クラスタ・メンバ用の現在のレート消費（トークン数／秒で表される）に対応するであろう。一のクライアント要求が２つ以上のトークンを消費することができるという理由で、当該クライアント要求の重み（即ち、当該要求によって消費されるトークンの数）をエスティメータのカウンタに加えることにより、当該現在のレート消費を更新する。当該現在のレート消費は、レート容量を当該クラスタに解放すべきか否かを決定するために、後の時点で使用されるであろう。
【００６３】
一旦当該クライアント要求の重みがカウンタに加えられると、当該アルゴリズムは、当該要求（ステップ５０５）を処理する責任を有する、当該クラスタ・メンバ内に格納されたレート・リミッタ・バケット・ツリーを探索する。例えば、一の要求がオペレーション１に対してなされるならば、当該アルゴリズムは、グローバル・バケットからオペレーション１のバケットに至るパス（例えば、図３のレート・リミッタ・バケット・ツリー内のグローバル−＞サービス１−＞オペレーション１のパス）に沿って並んだバケットのチェーンを回復する。次に、当該アルゴリズムは、当該バケット内の各チェーンが当該要求を満たすのに十分な余地を有するか否かを決定する（ステップ５１０）。もし、十分な余地が存在すれば（即ち、当該トークンを加えても、当該チェーン内の任意のレベルで課されたレート制限を超えなければ）、当該トークンが当該チェーン内の各バケットに加えられ（ステップ５１５）、当該要求が許可され（ステップ５２０）、そして当該アルゴリズムが終了する。
【００６４】
もし、各バケット内に当該要求を許可するための余地がなければ、エスティメータを呼び出すことにより、当該要求を最終的に満たすための追加のレート容量を予約することができるか否かを決定する（ステップ５２５）。図６は、追加の予約量を決定するためにエスティメータが使用される、１つの態様を例示する。本発明の範囲内で、追加の予約量を決定するための他の方法が可能である。
【００６５】
図６に示すように、エスティメータは、現在の時間と最後の沈黙期間の開始時点との間の経過時間の量を計算する（ステップ６００）。本明細書で使用するように、「沈黙期間」は、一の予約要求が拒否された後に後続の予約要求が抑止される所定の期間として定義される。一旦一の予約要求（即ち、追加のレート容量を求める要求）が拒否されると、「沈黙期間」が開始する。沈黙期間が使用されるのは、反復される予約要求及び拒否によって予約コーディネータが過負荷になるのを回避するためである。言いかえれば、エスティメータは、より多くのレートを予約する可能性がない場合は、メンバが追加の予約要求を送信しないように要求レートの抑止を実装する。抑止がないと、メッセージ・チャンキング（message chunking）も機能しなくなるであろう。
【００６６】
次に、エスティメータは、経過時間が沈黙期間よりも小さいか否かを決定する（ステップ６１０）。もし、経過時間が沈黙期間よりも小さければ、エスティメータは、当該予約要求を拒否して、ゼロ予約量を戻す（ステップ６２０）。さもなければ、エスティメータは、当該予約要求を許可し、一の予約チャンク量を戻す（ステップ６３０）。予約チャンク量は、エスティメータ内の一の調整可能パラメータである。例えば、予約チャンク量が増加されると、予約速度を増加させ且つグループ間メッセージングを減少させることができ、予約チャンク量が減少されると、レート制限の近傍で動作する場合は推定精度を向上させることができる。
【００６７】
図５を再度参照すると、エスティメータによって提供される予約チャンク量は、アドミッション制御／ＳＬＡアルゴリズムに適用される（ステップ５３０）。もし、予約チャンク量がゼロであれば、当該クライアント要求が拒否され（ステップ５３５）、その後、当該アルゴリズムが終了する。前述のように、経過時間が沈黙期間よりも小さければ、ゼロの予約チャンク量が戻される。ゼロの予約チャンク量を戻す他の理由も、存在することがある。例えば、各メンバごとに最大の予約量が指定される場合は、一の要求中メンバがその割り振られた量を既に超えている（又は超えるであろう）ことを条件として、ゼロ予約量を戻すことができる。
【００６８】
もし、予約チャンク量がゼロより大きければ（ステップ５３０）、当該クラスタ・メンバは、一の予約要求を予約コーディネータに送信することにより、より多くのレートを求める（ステップ５４０）。もし、当該クラスタ内に当該予約要求を満たすのに十分なレート容量があれば、この予約要求が許可される。例えば、予約コーディネータは、全てのクラスタ・メンバの（メンバ・ツリー内に格納された）現在のレート消費を、クラスタ・ツリー内に格納されたレート制限と比較する。もし、当該クラスタ・メンバが追加のレート容量を求めているために、全てのメンバの組み合わされた予約容量がクラスタ・ツリーに指定された予約量を超えるのであれば、予約コーディネータは、当該予約要求を拒否して、ゼロ予約量を戻す。さもなければ、予約コーディネータは、当該予約要求を許可して、（１）予約チャンク・サイズに等しい予約量を戻すか、又は（２）ゼロより大きく且つ予約チャンク・サイズより小さいある新しい量を戻す。もし、当該チャンク要求を満たすのに不十分なレート容量が残存するのであれば、「新しい量」は、例えば、予約チャンク・サイズより小さいものとなる。前述のように、予約チャンク・サイズは、エスティメータ内の一の調整可能パラメータである。
【００６９】
次に、エスティメータは、当該予約要求の許可又は拒否を反映するように更新される。例えば、予約コーディネータが追加のレート容量を予約することができれば（ステップ５４５）、予約コーディネータは、新しく予約された量をエスティメータに送信するから（ステップ５５０）、エスティメータは、そのカウンタを新しく予約された量で更新することができる。このカウンタの更新は、「新しい量」を当該クラスタ・メンバによって現に予約された量に加えることにより行われる。前述のように、「新しい量」は、（１）予約チャンク・サイズに等しいか、又は（２）クラスタ内に不十分なレート容量が残存する場合は、予約チャンク・サイズより小さい。
【００７０】
一旦エスティメータのカウンタが新しい予約量で更新されると（ステップ５５０）、バケットのチェーンを得るために、（追加のレート容量を要求した）当該クラスタ・メンバ用のレート・リミッタ・バケット・ツリーが、再び探索される（ステップ５６０）。前述の例に従うと、オペレーション１に対する一のクライアント要求の結果として、当該クラスタ・メンバは、グローバル・バケットからオペレーション１のバケットに至るパス（例えば、図３のグローバル−＞サービス１−＞オペレーション１のパス）に沿って並んだバケットのチェーンを戻す。以前には、これらのバケットには、当該クライアント要求を満たすのに不十分な余地があった。しかし、予約コーディネータが、これらのバケットのチェーンに追加のレートを割り振ることができたので、当該アルゴリズムは、当該要求を満たすのに十分な余地が各バケット内にあるか否かを再び照会する（ステップ５６５）。もし、十分な余地が存在すれば、当該要求トークンがチェーン内の各バケットに加えられ（ステップ５７０）、当該クライアント要求が許可され（ステップ５７５）、その後、当該アルゴリズムが終了する。さもなければ、クライアント要求が拒否され（ステップ５３５）、その後、当該アルゴリズムが終了する。
【００７１】
予約コーディネータが、当該クラスタ・メンバ用の追加のレート能力を予約することができない場合も（ステップ５４０及び５４５）、当該クライアント要求が拒否される（ステップ５３５）。この場合、予約コーディネータは、予約要求が拒否されたことをエスティメータに通知する（ステップ５５５）。その結果、沈黙期間の終了時点が現在の時間に設定され、これにより沈黙期間をリセットする。幾つかの実施形態では、当該アルゴリズムは、エスティメータを更新し（ステップ５５５）且つ予約要求を拒否した（ステップ５３５）後に終了する。しかし、予約ソフトウェアを実行する間に、バケットのチェーン内にあるスペースがクリアされることがある。例えば、この時間インターバル（例えば、１秒）の終わりに、バケット・コンテンツがクリアされて、追加のトークン用の余地を作ることができる。この理由で、本発明の他の実施形態では、当該アルゴリズムは、拒否された予約要求をエスティメータに通知した後、ステップ５６０にプログラム制御を転換することができる。このようにすると、今や要求トークンを加えるべき余地を有し且つ当該要求を許可することがある、潜在的に更新されたレート・リミッタ・バケット・ツリーを探索するための追加の機会が、当該クラスタ・メンバに提供されるであろう。
【００７２】
前述のように、エスティメータは、当該クラスタの各メンバごとに、連続的で且つリアルタイムの容量推定を行う。その結果、エスティメータは、追加のレート容量を予約コーディネータにいつ求めるべきか及びレート容量をクラスタにいつ解放すべきかを決定することができる。１つのクラスタ・メンバからのレート容量を解放すると、このレートを、追加の容量を必要とする他のクラスタ・メンバに再配分することができる。図７を参照して後述するように、１つのクラスタ・メンバからのレート容量を解放することができるのは、「現在のレート消費傾向」が定常傾向にあるか又は減少傾向にあり且つ当該メンバが現に使用しているものより多い予約済みのレートを有する場合である。
【００７３】
図７は、再配分用のレート容量をクラスタにいつ解放すべきかを決定するためにエスティメータが使用される、１つの態様を例示する。本発明の範囲内で、レート容量を解放するための他の方法が可能である。図７に示すように、エスティメータは、「移動平均」、又は現在の期間中に特定のクラスタ・メンバが消費するトークンの数のカウントを更新する（ステップ７００）。前述のように、移動平均の更新は、許可された要求トークンをエスティメータのカウンタに加えることにより行われる。このカウンタは、現在の期間の終わりにリセットされ（ステップ７１０）。次に、現在の移動平均が、「最終平均値」、又は最後の期間中に当該クラスタ・メンバが消費したトークンの数のカウントと比較される（ステップ７２０）。この比較の結果に依存して、「現在のレート消費傾向」が、増加傾向（ステップ７３０Ａ）、定常傾向（ステップ７３０Ｂ）又は減少傾向（ステップ７３０Ｃ）に設定される。
【００７４】
次に、エスティメータは、レート容量を当該クラスタに解放すべきか否かを決定する。例えば、エスティメータは、当該クラスタ・メンバ用の現在の予約量を決定するために、（当該クラスタ・メンバ内に格納された）レート・リミッタ・バケット・ツリーにアクセスする。もし、現在の予約量がゼロに等しければ（ステップ７４０）、当該クラスタ・メンバは、解放すべきレートを有していないから、エスティメータは、この方法を再開し且つ潜在的にレートを解放するために次の期間まで待機する（ステップ７５０）。
【００７５】
もし、現在の予約量がゼロより大きければ（ステップ７４０）、エスティメータは、「現在のレート消費傾向」が増加傾向、定常傾向及び減少傾向のうちのどれであるかに基づき、次のステップに進む。もし、「現在のレート消費傾向」が増加傾向にあれば（ステップ７６０及び７７０のＮＯ枝路）、エスティメータは、当該クラスタ・メンバが着信クライアント要求を満たすためにその現在の予約量（又はより多くの容量）を必要とすることを理解する。従って、増加傾向にあると決定する場合、エスティメータは、潜在的にレートを解放するために次の期間まで待機する（ステップ７５０）。しかし、「現在のレート消費傾向」が減少傾向にあるか又は定常傾向にあれば（ステップ７６０及び７７０のＹＥＳ枝路）、エスティメータは、当該メンバの現在の予約量とその移動平均との間の差を計算する（ステップ７８０）。もし、その差が解放チャンク・サイズより大きければ、当該メンバの予約済み容量の一のチャンクがクラスタに解放される（ステップ７９０）。さもなければ、エスティメータは、レートを解放するために次の期間まで待機する（ステップ７５０）。
【００７６】
予約チャンク・サイズのように、解放チャンク・サイズは、エスティメータ内の一の調整可能パラメータである。解放チャンク・サイズは、予約チャンク・サイズと同じであることもあるし、異なることもある。ある場合には、予約チャンク・サイズ及び解放チャンク・サイズは、クラスタ全体について設定されたレート制限のあるパーセンテージとして指定することができる。他の場合には、予約チャンク・サイズ及び解放チャンク・サイズは、任意の適切なサイズに設定することができる。レート容量は、必ずしもチャンクの形式で予約及び解放されるとは限らないことに留意されたい。チャンキングを使用すると、予約／解放の速度を増加させ且つグループ間メッセージングを減少させるから、クラスタ・メンバ間の通信パス上のネットワーク帯域幅を減少させることができる。しかし、チャンキングは、レート制限の近傍で精度を低下させるから、予約チャンク・サイズ及び解放チャンク・サイズを決定する場合には、精度と速度との間のトレードオフを考慮しなければならない。
【００７７】
幾つかの実施形態では、エスティメータは、レート・リミッタ・バケット・ツリー内の各オペレーションに割り当てることができる。このようにすると、エスティメータは、葉ノードに至るまでレート消費を推定することができる。他の実施形態では、エスティメータは、レート・リミッタ・バケット・ツリーのより高いレベル内のノードに割り当てることができる。例えば、エスティメータは、図４の要求元レベルに存在するノードにのみ割り当てることができる。このアプローチを取ることができるのは、例えば、サービス品質保証契約によって保護されたアプリケーション及びサービスへのアクセスを要求する、多数の要求元（従って、多数のクライアント要求）が存在する場合である。ツリー内の任意のレベルで推定を行うことができることに留意されたい。しかし、葉ノードにおける推定がより高い精度を提供するのに対し、より高いノードにおける推定はより少ないメモリ及び計算資源を消費するという点で、トレードオフが存在する。
【００７８】
＜分散式トラフィック・シェーピングのための方法＞
前述のように、トークン・バケット・アルゴリズム及びリーキー・バケット・アルゴリズムは、トラフィック・シェーピングを行うために一般に使用されている２つのアルゴリズムである。トークン・バケット・アルゴリズムは、平均データ伝送レートに制限を課すことにより、ネットワークに注入されるデータの量を制御する。言いかえれば、トークン・バケット・アルゴリズムは、バケット内に適切なトークンが存在し且つバーストしきい値が適正に構成されていることを条件として、データの「バースト」を（そのピーク・バースト・レートに達するまで）送信することを可能にする。リーキー・バケット・アルゴリズムは、データ伝送レートにハード制限を課すという点が、トークン・バケット・アルゴリズムと異なる。言いかえれば、リーキー・バケット・アルゴリズムは、「リーキー」バケットから一定のレートでパケットをフィルタするように強要することにより、バースト性トラフィックを平準化する。リーキー・バケット・アルゴリズムによって提供されるフィルタリングは、パケット間のスペースを強制することにより、データ伝送レートにハード制限を課す。
【００７９】
従来技術のトークン・バケット・アルゴリズム及びリーキー・バケット・アルゴリズムは、幾つかのネットワークには適切であるが、クラスタ環境には適用することができない。例えば、従来技術のアルゴリズムは、クラスタ全体について１つのネットワーク資源当たり１つのバケットだけを維持するに過ぎない。従来技術のアルゴリズムは、バースト割り振りの変化に適合するようにクラスタ・メンバ間でバケット・コンテンツを配分するための手段を提供しない。また、従来技術のアルゴリズムは、バースト割り振りの配分をモニタし且つ制御するのための手段を提供しないのであり、従って、バースト割り振りが変化する場合（例えば、１つ以上のクラスタ・メンバが故障するか、オフラインにされる場合）、ネットワーク資源を保護するために使用することができない。
【００８０】
前述の諸問題を解決するため、基本的なトークン・バケット・アルゴリズムは、クラスタ環境内でトラフィック・シェーピングをサポートするように拡張された。例えば、当該クラスタの各メンバは、特定のネットワーク資源用のそれ自体のキュー付き又はキューなしトークン・バケットを与えられる。任意のネットワーク・サービス（例えば、呼び出し制御サーバ）は、一の資源と見なすことができる。図８に示すように、当該クラスタの各メンバは、当該クラスタが全体として使用する、又は当該クラスタに対し全体して使用可能にされる資源（例えば、資源１〜３）の数に依存して、１つ以上のネットワーク資源バケット（例えば、バケットＲ１〜Ｒ３）を維持する。これらのネットワーク資源バケットは、当該クラスタの各メンバ内にローカルに格納される。
【００８１】
改良されたトラフィック・シェーピング・アルゴリズムは、各々がレートを予約し且つ解放するための予約コーディネータ及びエスティメータを利用するという点で、改良されたアドミッション制御アルゴリズムに類似する。レートを予約することに加えて、予約コーディネータは、トラフィック・シェーピング・アルゴリズムにおける当該クラスタのメンバ間のバースト割り振りを配分することに責任を有する。幾つかの実施形態では、バースト割り振りについて保守的なアプローチを取ることができる。例えば、最初のバースト割り振りは、当該クラスタのメンバ間で均等に分割することができる。他の実施形態では、最初のバースト割り振りは、ある予定の重み付けに従って、クラスタ・メンバ間で多少不均等に分割することができる。このようにすると、より強力なマシンに対し、それほど強力ではないマシンよりも多くのバースト割り振りを提供することができる。しかし、バースト割り振りは、単にクラスタのアクティブなメンバ間でのみ分割されることに留意されたい。もし、クラスタの一のメンバが故障するか、又はオフラインにされるならば、当該クラスタ用の全バースト出力が一定に留まるように、予約コーディネータによってバースト割り振りが再配分される。
【００８２】
ある場合には、クラスタ用の全バースト出力を任意のクラスタ・メンバ用の最大のバースト割り振りで割った値が、最大の要求重み（要求の重み付けは、諸要求が２つ以上のトークンを消費することを可能にすることを想起されたい）以上になるように、バースト割り振りを選択することができる。このようにすると、各要求が許可されるか、又は当該要求を許可するのに不十分なトークンがバケット内に存在することを保証する。最大のバースト割り振りは、任意のクラスタ・メンバ用のローカル・バケットのサイズ（即ち、ローカル・バケットに課されるレート制限）に対応する。バースト割り振りは非同期的であるから、各バケットに課されるレート制限は、任意の時間に変化することがある。
【００８３】
エスティメータは、「ローカル・トークン・バケット」（即ち、一のクラスタ・メンバ内にその資源用に格納されたトークン・バケット）によって追跡される、各資源に割り当てられる。トラフィック・シェーピング・アルゴリズムにおいて、エスティメータは、当該クラスタ内でどれだけの平均レートを予約又は解放すべきかを決定するように試行する。グループ間メッセージングを減少させるため、チャンクの形式で、予約が要求又は解放される。エスティメータは、現在の期間中に消費されるトークンの数の「移動平均」を追跡するとともに、現在の期間対先行する期間の派生値（derivative）を追跡する。この派生値は、レート変動に対する頑強性を提供するための重要な要素である。
【００８４】
以下で詳述するように、トラフィック・シェーピング・アルゴリズムは、（１）エスティメータがいつ呼び出されるか、及び（２）容量をいつ解放すべきかという点で、アドミッション制御アルゴリズムと異なる。例えば、後述するエスティメータは、各要求が許可又は拒否されるか否かに拘わらず、各要求ごとに呼び出されなければならない。その理由は、トークン・バケットがアクティブにバーストを再生成し、従って各要求におけるトークンの消費までにバーストをできるだけ速く再生成することが望ましいということにある。同様に、一旦一のバケットがその最大レート制限に達する場合にのみ、容量を解放することにより、最大のローカル・バースト能力を提供し且つレートが真に過大であることを指示しなければならない。図９〜図１１は、１つの実施形態に従った、改良されたトラフィック・シェーピング・アルゴリズムを例示する。
【００８５】
図９は、一のクライアント要求を処理するために使用される、トラフィック・シェーピング・アルゴリズムの１つの実施形態を例示する。従来技術のトークン・バケット・アルゴリズムと同様に、１／ｒ秒ごとに、一の「トークン」が一のローカル・トークン・バケットに加えられる。トークンの一定の再充填レートは、「ローカル・トークン再生成レート」と呼ばれる。ローカル・トークン・バケットは、最大でｂ個のトークンを保持することができる。トークンが到着するときに当該バケットが一杯であれば、このトークンは廃棄される。ｎトークンに対応する一の要求が到着する場合、ｎトークンが当該バケットから除去され、そして当該要求は、許可可能としてマークされる。もし、ｎより少ないトークンが使用可能であれば、どのトークンも当該バケットから除去されない。
【００８６】
従来技術のアルゴリズムとは異なり、本明細書に開示するトラフィック・シェーピング・アルゴリズムは、当該クラスタのメンバ間で動的に配分される、レート容量及びバースト割り振りをモニタし且つ制御する。例えば、レート容量については、各メンバのレートの合計が当該クラスタ全体に課されるグローバル・レート制限に等しくなるように、これを配分することができる。バースト割り振りも、同様の方法で配分することができる。但し、各バケットのバーストの合計が、当該クラスタ全体の全バースト出力に等しいことを条件とする。
【００８７】
また、改良されたトラフィック・シェーピング・アルゴリズムは、レート容量をいつ予約又は解放すべきかを推定するために、エスティメータを使用する。前述のように、エスティメータは、各要求が成功するか否かに拘わらず、各要求の後に呼び出される。例えば、一の要求が到着する場合、エスティメータ内の一のカウンタは、現在のクライアント要求用に指定された重み付けで更新される（ステップ９００）。言いかえれば、エスティメータは、各期間中に、「移動平均」又は各ローカル・トークン・バケットによって消費されるトークンの数のカウントを維持する。殆どの場合、一の期間は、１秒として定義されるから、移動平均は、当該バケット用の現在のレート消費（トークン数／秒で表される）に対応するであろう。一のクライアント要求が２つ以上のトークンを消費することができるから、当該クライアント要求の重み（即ち、当該要求によって消費されるトークンの数）をエスティメータのカウンタに加えることにより、現在のレート消費を更新する。現在のレート消費は、レート容量を当該クラスタに解放すべきか否かを決定するために、その後に使用されるであろう。
【００８８】
一旦当該クライアント要求の重みがカウンタに加えられると、当該アルゴリズムは、特定の資源用のローカル・トークン・バケットが当該要求を満たすのに十分なトークンを有するか否かを決定する（ステップ９０５）。もし、十分なトークンが残存していれば、当該要求を満たすのに必要とされるトークンの数が当該バケットから除去され（ステップ９１０）、当該要求が「許可可能」とマークされる（ステップ９１５）。
【００８９】
当該トークン・バケットの除去を開始する最初の要求を受信する際、レートを予約し且つ当該ローカル・トークン・バケットを再充填することを試行するために、エスティメータが呼び出される（ステップ９２０）。前述のように、各クラスタ・メンバ用のレートの合計が当該クラスタ全体の最大平均持続レートに等しくなるように、トラフィック出力配分に従って、レートが当該クラスタの各メンバに配分される。当該クラスタの各メンバ用の配分又は予約されるレートは、ローカル・トークン再生成レートに対応する。このアプローチは、数学的に単一のトークン・バケットに同等であることに留意されたい。例えば、全てのメンバの組み合わされたバースト消費［sum(members_b_i）］がＢ（即ち、当該クラスタ全体用の全バースト出力）に等しく且つ全てのメンバの組み合わされたローカル・トークン再生成レート［sum(members_r_i）］がＲ（即ち、当該クラスタ全体用のトークン再生成レート）に等しければ、任意の所与の期間中に当該クラスタを通して許可される要求の最大数ｔは、Ｂ＋Ｒｔの単一のトークン・バケットによってバインドされるであろう。
【００９０】
図１０は、追加の予約量を決定するために（図９のステップ９２０）エスティメータが使用される、１つの態様を例示する。本発明の範囲内で、追加の予約量を決定するための他の方法が可能である。
【００９１】
図１０に示すように、エスティメータは、現在の時間と最後の沈黙期間の開始時点との間の経過時間の量を計算する（ステップ１０００）。前述のように、「沈黙期間」は、一の予約要求が拒否された後に後続の予約要求が抑止される所定の期間として定義される。一旦一の予約要求（即ち、追加のレート容量を求める要求）が拒否されると、「沈黙期間」が開始する。沈黙期間が使用されるのは、メッセージ・チャンキングを可能にし且つ反復される予約要求及び拒否によって予約コーディネータが過負荷になるのを回避するためである。
【００９２】
次に、エスティメータは、ナイキスト・レートを計算し（ステップ１００５）且つ最後の要求以後の時間を計算することにより（ステップ１０１０）、当該要求がデータの「バースト」で送信されたか否かを検出する。ナイキスト・レートは、現在の移動平均を２で割ることにより計算される。次に、エスティメータは、最後の要求以後の時間がナイキスト期間より小さいか又はそれに等しいか否かを決定する（ステップ１０１５）。もし、最後の要求以後の時間がナイキスト期間以下であれば、即ちバーストが存在しなければ、エスティメータは、経過時間を沈黙期間と比較することにより、適切な予約チャンク量を戻す（ステップ１０４０、１０４５及び１０５０）。これらのステップは、前述の図６のステップ６１０、６２０及び６３０と同等である。
【００９３】
もし、最後の要求以後の時間がナイキスト期間より大きければ、即ちバーストが生じたことを指示すれば、エスティメータは、現在の移動平均が、増加傾向、定常傾向又は減少傾向の何れにあるかを決定する（図１１を参照）。エスティメータが追加のレートを予約するように試行するのは、（１）増加傾向にある場合（ステップ１０２０）、（２）定常傾向にあるが、現在の移動平均が現在の予約量より大きい場合（ステップ１０２５及び１０３０）、又は（３）定常傾向若しくは減少傾向にあるが、現在の予約量がゼロである場合（ステップ１０２５、１０３０、１０３５）である。エスティメータは、経過時間を沈黙期間と比較し（ステップ１０４０、１０４５及び１０５０）且つ適切な予約チャンク量を戻すことにより、追加のレートを予約するように試行する。しかし、エスティメータが、現在の移動平均が定常傾向又は減少傾向にあり（ステップ１０２５）且つ現在の予約量がゼロより大きいことを決定すれば（ステップ１０３５）、エスティメータは、沈黙期間について忘れて、単にゼロの予約チャンク量を戻す。このことは、定常傾向又は減少傾向にあり且つ十分なレートを既に有している場合は、恐らく、追加のレートを予約する必要はないということによる。
【００９４】
前述のように、予約チャンク・サイズ（及び解放チャンク・サイズ）は、エスティメータ内の一の調整可能パラメータである。しかし、レート容量は、チャンクの形式で必ずしも予約及び解放されるとは限らない。チャンキングを使用すると、予約／解放の速度を増加させ且つグループ間メッセージングを減少させるから、クラスタ・メンバ間の通信パス上のネットワーク帯域幅を減少させることができる。しかし、チャンキングは、レート制限の近傍で精度を低下させるから、予約チャンク・サイズ及び解放チャンク・サイズを決定する場合には、精度と速度との間のトレードオフを考慮しなければならない。
【００９５】
図９を再度参照すると、エスティメータによって提供される予約チャンク量は、トラフィック・シェーピング・アルゴリズムに適用される。もし、予約チャンク量がゼロであれば（ステップ９２５）、トラフィック・シェーピング・アルゴリズムは、当該要求が以前に許可可能とマークされたか否かを決定する（ステップ９５５）。もし、当該要求が許可可能とマークされていたならば、当該クライアント要求が許可される（ステップ９６０）。さもなければ、当該クライアント要求が拒否され（ステップ９６５）、その後、当該アルゴリズムが終了する。
【００９６】
もし、予約チャンク量がゼロより大きければ（ステップ９２５）、当該クラスタ・メンバは、より多くのレートを求めるために、一の予約要求を予約コーディネータに送信する（ステップ９３０）。もし、当該予約要求を満たすのに十分なレート容量が当該クラスタ内に存在すれば、当該予約要求を許可することができる。例えば、予約コーディネータは、全てのクラスタ・メンバの（ローカル・トークン・バケット内に格納された）現在のレート消費を、当該クラスタ全体用の最大平均持続レートと比較することができる。もし、当該クラスタ・メンバが追加のレート容量を求める結果として、全てのメンバの組み合わされた予約容量が最大平均持続レートを超えれば、予約コーディネータは、当該予約要求を拒否して、ゼロ予約量を戻す。さもなければ、予約コーディネータは、当該予約要求を許可して、一の予約量を戻す。この予約量は、（１）予約チャンク・サイズに等しいか、又は（２）ゼロより大きく且つ予約チャンク・サイズより小さいある新しい量に等しい。例えば、チャンク要求を満たすのに十分なレート容量が残存していない場合は、当該「新しい量」は、予約チャンク・サイズより小さいことがある。前述のように、予約チャンク・サイズは、エスティメータ内の一の調整可能パラメータである。
【００９７】
次に、エスティメータは、当該予約要求の許可又は拒否を反映するように更新される。例えば、予約コーディネータが追加のレート容量を予約することができたならば（ステップ９３０及び９３５）、予約コーディネータは、新しく予約された量をエスティメータに送信し（ステップ９４０）、その結果、エスティメータは、新しく予約された量を用いて、そのカウンタを更新することができる。即ち、このカウンタを更新するため、「新しい量」が当該クラスタ・メンバによって現に予約された量に加えられる。前述のように、「新しい量」は、（１）予約チャンク・サイズに等しいか、又は（２）クラスタ内にチャンク要求を満たすのに十分なレート容量が残存していない場合は、予約チャンク・サイズより小さいことがある。その後、当該追加のレート容量を反映するように、ローカル・トークン・バケット再生成レートが更新される（ステップ９５０）。もし、予約コーディネータが、当該クラスタ・メンバ用の追加のレート能力を予約することができなければ（ステップ９３０及び９３５）、予約コーディネータは、当該予約要求が拒否されたことをエスティメータに通知する（ステップ９４５）。これは、最後の沈黙期間を現在の時間に設定することにより、沈黙期間をリセットすることを可能にする。一旦エスティメータが更新されると（ステップ９４０又は９４５）、当該アルゴリズムは、当該クライアント要求が以前に許可可能としてマークされたか否かを決定する（ステップ９５５）。もし、当該要求が許可可能としてマークされていたならば、当該クライアント要求が許可される（ステップ９６０）。さもなければ、当該クライアント要求が拒否され（ステップ９６５）、その後、当該アルゴリズムが終了する。
【００９８】
前述のアドミッション制御アルゴリズムのように、トラフィック・シェーピング・アルゴリズム内で使用されるエスティメータは、当該クラスタの各メンバごとに、連続的で且つリアルタイムの容量推定を行う。その結果、エスティメータは、追加のレート容量を予約コーディネータにいつ求めるべきか及びレート容量を当該クラスタにいつ解放すべきかを決定することができる。１つのクラスタ・メンバからのレート容量を解放すると、このレートを、追加の容量を必要とする他のクラスタ・メンバに再配分することができる。図１１を参照して後述するように、１つのクラスタ・メンバからのレート容量を解放することができるのは、「現在のレート消費傾向」が定常傾向にあるか又は減少傾向にあり且つ当該メンバが現に使用しているものより多い予約済みのレートを有する場合である。
【００９９】
図１１は、再配分用のレート容量を当該クラスタにいつ解放すべきかを決定するためにエスティメータが使用される、１つの態様を例示する。図１１の方法ステップの幾つかは、図７に示す前述のものに類似する。これらのステップは、図７及び図１１の全体にわたって同様の参照数字を付されている。簡潔のために、両図面で共通する方法ステップについては、詳細な説明を省略する。図１１の方法を十分に理解するためには、図７に関連する前述の説明を参照されたい。本発明の範囲内で、レート容量を解放するための他の方法が可能である。
【０１００】
図１１に示すように、エスティメータは、現在の期間用の移動平均を更新し（ステップ１０００）、カウンタをゼロにリセットする（ステップ１１１０）。次に、エスティメータは、「現在の移動平均」を「最終値平均」と比較することにより（ステップ１１２０）、「現在のレート消費傾向」を決定する（ステップ１１３０）。前述のように、この比較の結果に依存して、「現在のレート消費傾向」を、増加傾向（ステップ１１３０Ａ）、定常傾向（ステップ１１３０Ｂ）又は減少傾向（ステップ１１３０Ｃ）に設定することができる。幾つかの実施形態では、エスティメータは、図７の方法ステップ（図１１のステップ１１４０〜１１９０として再掲）を使用することにより、レート容量を当該クラスタにいつ解放すべきかを決定することができる。例えば、エスティメータは、前述の方法ステップを使用することにより、（１）バケット・カウンタがバケット制限に等しいか否かを決定し（ステップ１２００）、そして（２）バケット・カウンタからバケット制限を減じた値が、ローカル・トークン・バケット再生成レートから１を減じた値より小さいか否かを決定する（ステップ１２１０）。前述のように、図７の方法は、１チャンクの予約容量を解放するか、又は（潜在的に）レートを解放するために次の期間まで待機する。
【０１０１】
前述のように、「バケット制限」は、特定のクラスタ・メンバに割り当てられたローカル・トークン再生成レートと同等である。「バケット・カウンタ」は、各期間中に各ローカル・トークン・バケットによって消費されるトークンの数を追跡する。バケット制限からバケット・カウンタを減じた値を、ローカル・トークン・バケット再生成レートから１を減じた値に比較すると（ステップ１２１０）、エスティメータは、特定のトークン・バケットがその最大レート制限（即ち、最大バースト割り振り）にいつ接近するかを決定することができる。一の最大レート制限に接近することは、エスティメータに対し、当該メンバのローカル・トークン・バケット・レート容量のうちの幾らか（全てではない場合）を解放すべき時間であることを知らせる。
【０１０２】
しかし、レート容量を解放するための推定方法は、トラフィック・シェーピングの実施形態において、時には異なることがある。例えば、バケット・カウンタがバケット制限に等しければ（ステップ１２００）、エスティメータは、全ての予約済み容量を当該クラスタに解放する（ステップ１２２０）。一般に、これが行われるのは、バースト性伝送を処理する場合である。他方、エスティメータは、（１）バケット・カウンタがバケット制限に等しくない場合で（ステップ１２００）、しかも（２）バケット制限からバケット・カウンタを減じた値が、ローカル・トークン・バケット再生成レートから１を減じた値以上である場合は（ステップ１２１０）、次の期間までレートを解放することを待機する。言いかえれば、エスティメータは、（バケット・コンテンツを速やかに消費するデータのバーストとは異なり）バケット・コンテンツを徐々に消費するような定常傾向にある場合は、レートを解放することを待機する。
【０１０３】
本発明が、クラスタ環境でアドミッション制御及びトラフィック・シェーピング手順を実装するための改良されたアルゴリズムを提供することは、当業者にとって明らかであろう。本明細書に開示したアルゴリズムは、クラスタ・メンバ間のレート制限の配分をモニタし且つ制御するための手段を提供することにより、従来技術の方法を改良することができる。即ち、これらのアルゴリズムは、（アドミッション制御用の）レート配分及び（トラフィック・シェーピング用の）バースト割り振りの変化に適合することができる。例えば、グローバル・レート制限を超えないことを条件として、クラスタへのレート配分が変わる場合、本明細書に開示した、改良されたアドミッション制御アルゴリズムは、新しい配分に従って、クラスタ・メンバ間でレートを再配分することを可能にする。もし、１つ以上のクラスタ・メンバが故障するか、又はオフラインにされるならば、改良されたトラフィック・シェーピング・アルゴリズムは、同様のアプローチを使用することにより、アクティブなクラスタ・メンバ間でバースト割り振りを再配分する。当業者にとっては、本明細書の記載に照らして、本発明の種々の側面のさらなる修正及び他の実施形態が明らかであろう。従って、全てのかかる修正及び変形は、本発明の範囲内に属するものと解すべきである。本明細書及び図面の記載は、例示的なものであり、これを制限的なものであると見なしてはならない。
【図面の簡単な説明】
【０１０４】
【図１】ネットワーク・クラスタの概要を例示するブロック図である。
【図２】クラスタを形成するようにアプリケーション及びデータベース・サーバが結合される、１つの態様を例示するブロック図である。
【図３】１つの実施形態に従った、レート制限ツリー又はレート・リミッタ・バケット・ツリーを例示するブロック図である。
【図４】他の実施形態に従った、レート制限ツリー又はレート・リミッタ・バケット・ツリーを例示するブロック図である。
【図５】要求を処理するために使用される、アドミッション制御アルゴリズムの１つの実施形態を例示するフローチャートである。
【図６】図５のアドミッション制御アルゴリズムにおいて追加のレート容量をいつ予約するかを決定するために推定アルゴリズムが使用される、１つの態様を例示するフローチャートである。
【図７】図５のアドミッション制御アルゴリズムにおいてレート容量をいつ解放すべきかを決定するために推定アルゴリズムが使用される、１つの態様を例示するフローチャートである。
【図８】クラスタ・メンバがネットワーク資源の使用を追跡する、１つの態様を例示するブロック図である。
【図９】要求を処理するために使用される、トラフィック・シェーピング・アルゴリズムの１つの実施形態を例示するフローチャートである。
【図１０】図９のトラフィック・シェーピング・アルゴリズムにおいて追加のレート容量をいつ予約すべかを決定するために推定アルゴリズムが使用される、１つの態様を例示するフローチャートである。
【図１１】図９のトラフィック・シェーピング・アルゴリズムにおいてレート容量をいつ解放すべきかを決定するために推定アルゴリズムが使用される、１つの態様を例示するフローチャートである。
【図１】
2009543485.tif 000003
【図２】
2009543485.tif 000004
【図３】
2009543485.tif 000005
【図４】
2009543485.tif 000006
【図５】
2009543485.tif 000007
【図６】
2009543485.tif 000008
【図７】
2009543485.tif 000009
【図８】
2009543485.tif 000010
【図９】
2009543485.tif 000011
【図１０】
2009543485.tif 000012
【図１１】
2009543485.tif 000013
【手続補正書】
【提出日】平成21年6月16日(2009.6.16)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
複数のクラスタ・メンバを有する一のネットワーク・クラスタに送信されるネットワーク・トラフィックの配分を制御するための方法であって、
特定のネットワーク資源を宛先とするネットワーク・トラフィックを第１のレートで受信するステップを含み、
前記ネットワーク・トラフィックが、複数のクライアント要求を含み、各クライアント要求が、それに割り当てられた一の重みを有し、
前記第１のレートを前記クラスタ・メンバの一のサブセット間で配分するステップをさらに含み、
前記サブセット内の各クラスタ・メンバが、前記特定のネットワーク資源用の一のトークン・バケットを維持し、前記サブセット内の各クラスタ・メンバに配分されるレートの量が、それぞれのトークン・バケット用の一の再生成レートに対応する、方法。
【請求項２】
バーストを前記サブセット間で配分するステップをさらに含む、請求項１記載の方法。
【請求項３】
前記サブセット内の各クラスタ・メンバに配分されるレートの合計が、前記第１のレートに等しく、前記サブセット内の各クラスタ・メンバに配分される前記バーストの合計が、前記ネットワーク・クラスタ用の全バースト出力に等しい、請求項２記載の方法。
【請求項４】
実質的に等しいレートとバーストの合計が前記サブセット内の各クラスタ・メンバに配分される、請求項３記載の方法。
【請求項５】
前記サブセット内の１つ以上のクラスタ・メンバに配分されるレートの量及びバーストの量が、前記サブセット内の他のクラスタ・メンバに配分されるレートの量及びバーストの量と異なる、請求項３記載の方法。
【請求項６】
前記全バースト出力を前記サブセット内の任意のクラスタ・メンバに配分されるバーストの最大の量で割った値が、前記複数のクライアント要求に割り当てられた最大の重み以上である、請求項３記載の方法。
【請求項７】
前記全バースト出力を前記サブセットのアクティブ・メンバ間で再配分するステップをさらに含む、請求項３記載の方法。
【請求項８】
１つの前記クライアント要求を前記サブセット内の１つのクラスタ・メンバに向けるステップと、
前記特定のネットワーク資源の使用を追跡するために、前記１つのクラスタ・メンバ内に格納された一のローカル・トークン・バケットにアクセスするステップとをさらに含み、
前記ローカル・トークン・バケットが、トークンの現在の数を保持し且つ当該ローカル・トークン・バケットに割り当てられた前記再生成レートに等しい第２のレートで追加のトークンを受け入れるように構成可能である、請求項１記載の方法。
【請求項９】
前記ローカル・トークン・バケットから一の数のトークンを消費するステップをさらに含み、
前記ローカル・トークン・バケット内に保持されるトークンの前記現在の数が前記１つのクライアント要求に割り当てられた前記重み以上である場合は、前記一の数が前記１つのクライアント要求に割り当てられた前記重みに等しい、請求項８記載の方法。
【請求項１０】
前記ローカル・トークン・バケットからトークンが消費されたか否かに拘わらず、前記ローカル・トークン・バケットに割り当てられた前記再生成レートを増加させることを試行するステップをさらに含む、請求項９記載の方法。
【請求項１１】
前記試行するステップが、
一の予約要求をいつ満たすべきかを決定するように構成可能な一の推定アルゴリズムに対し、一の予約要求を送信するステップと、
前記推定アルゴリズムから一の予約量を受信するステップとを含み、
前記予約量が、前記１つのクライアント要求がネットワーク・トラフィックの一のバースト内で受信されたか否かに基づく、請求項１０記載の方法。
【請求項１２】
前記１つのクライアント要求がネットワーク・トラフィックの一のバースト内で受信されなかった場合、前記受信するステップが、
前記予約要求が一の指定された沈黙期間中に送信される場合は、前記推定アルゴリズムから一のゼロ予約量を受信するステップと、
前記予約要求が前記指定された沈黙期間の終了後に送信される場合は、前記推定アルゴリズムから一の非ゼロ予約量を受信するステップとを含む、請求項１１記載の方法。
【請求項１３】
前記１つのクライアント要求がネットワーク・トラフィックの一のバースト内で受信された場合、前記受信するステップが、
現在の期間中に前記特定のネットワーク資源のために前記１つのクラスタ・メンバによって受信された全てのネットワーク・トラフィック用の現在のレート消費傾向を決定するステップと、
前記予約要求が一の指定された沈黙期間中に送信される場合、又は前記１つのクラスタ・メンバ用の前記現在のレート消費傾向が減少傾向にあるか若しくは定常傾向にあり且つ前記１つのクラスタ・メンバに配分されるレートの量がゼロより大きい場合は、前記推定アルゴリズムから一のゼロ予約量を受信するステップと、
前記予約要求が前記指定された沈黙期間の終了後に送信される場合は、前記推定アルゴリズムから一の非ゼロ予約量を受信するステップとを含む、請求項１２記載の方法。
【請求項１４】
前記推定アルゴリズムから一の非ゼロ予約量を受信する際に、前記試行するステップが、
前記クラスタ内に前記予約要求を満たすのに十分なレート容量が残存するか否かを決定するように構成可能な一の予約アルゴリズムに対し、前記予約要求を送信するステップと、
前記クラスタ内に前記予約要求を満たすのに不十分なレート容量が残存する場合は、前記予約アルゴリズムから一のゼロ予約量を受信するステップと、
前記クラスタ内に前記予約要求を満たすのに十分なレート容量が残存する場合は、前記予約アルゴリズムから一の非ゼロ予約量を受信するステップとをさらに含む、請求項１３記載の方法。
【請求項１５】
前記予約アルゴリズムから一の非ゼロ予約量を受信する際に、前記非ゼロ予約量を前記ローカル・トークン・バケット用の前記再生成レートに加えることにより、前記１つのクラスタ・メンバに配分されるレートの量を増加させるステップをさらに含む、請求項１４記載の方法。
【請求項１６】
複数のクラスタ・メンバを有する一のネットワーク・クラスタに送信されるネットワーク・トラフィックの配分を制御するための装置であって、
特定のネットワーク資源を宛先とするネットワーク・トラフィックを第１のレートで受信するための手段を備え、
前記ネットワーク・トラフィックが、複数のクライアント要求を含み、各クライアント要求が、それに割り当てられた一の重みを有し、
前記第１のレートを前記クラスタ・メンバの一のサブセット間で配分するための手段をさらに備え、
前記サブセット内の各クラスタ・メンバが、前記特定のネットワーク資源用の一のトークン・バケットを維持するように動作可能であり、前記サブセット内の各クラスタ・メンバに配分されるレートの量が、それぞれのトークン・バケット用の一の再生成レートに対応する、装置。
【請求項１７】
バーストを前記サブセット間で配分するための手段をさらに備える、請求項１６に記載の装置。
【請求項１８】
前記サブセット内の各クラスタ・メンバに配分されるレートの合計が、前記第１のレートに等しく、前記サブセット内の各クラスタ・メンバに配分される前記バーストの合計が、前記ネットワーク・クラスタ用の全バースト出力に等しい、請求項１７に記載の装置。
【請求項１９】
レート及びバーストの実質的に等しい量が、前記サブセット内の各クラスタ・メンバに配分される、請求項１８に記載の装置。
【請求項２０】
請求項１ないし請求項１５の何れか１項に記載の方法の各ステップをコンピュータに実行させるためのコンピュータ・プログラム。
【国際調査報告】
2009543485.tif 000014
2009543485.tif 000015
2009543485.tif 000016