説明

過負荷シグナルに基づく適応性速度制御

クライアント・コントロールを介したサーバー過負荷制限を目的とするコンピュータ・プログラム製品を含む方法及び装置について記述する。複数リクエストの第一セットを第一期間中に第一伝送速度でサーバーに伝送する。前記第一伝送速度を第一伝送制限速度以下になるよう制限する。サービスに関する前記複数リクエストの第一セットのうち少なくとも2以上のリクエストが過負荷基準を満たしているかどうかに基づいて過負荷値を決定する。前記過負荷値及び前記第一伝送制限速度に基づいて第二伝送制限速度を決定する。複数リクエストの第二セットを第二期間中に第二伝送速度で前記サーバーに伝送する。前記第二伝送速度を前記第二伝送制限速度以下になるよう制限する。

【発明の詳細な説明】
【技術分野】
【0001】
本発明は、概して、ネットワーク中に集中するサーバー過負荷を検出及び軽減することを目的とするコンピュータ・プログラム製品を含めた方法及び装置に関する。
【背景技術】
【0002】
通信サービスへの要求が増すにつれて、効果的な通信システムの重要性が増してきている。通信サービスには、電話コール設定要求の処理から、ネットワークのインターネット・プロトコル(IP)のデータ・パケットのルーティング、ウェブサイト及び/又はコンテンツを要求するハイパーテキスト・ドランスファー・プロトコル(HTTP)要求の処理等を含むことができる。通信システムには、クライアントからのサービス要求を処理するサーバーが一般的には含まれる。サーバーには、電話コール設定要求処理を行うための遠距離通信スイッチから、IPデータ・パケットをルーティングするためのネットワーク・ルーター、HTTP要求を処理するためのウェブサーバー及び/又はコンテンツ・サーバー等を含むことができる。
【0003】
時として、サービス要求(リクエスト)は、サーバーが前記要求を処理する速度よりも速い速度で前記サーバーに到達することがある。前記リクエストを処理するサーバーの速度は、以下の要素のうちの1以上が原因で変動しうる:異なる要求を処理する際のバリエーション;サーバー上で実行されるバックグラウンド動作又は管理動作;及び/又は前記サーバー中のソフトウェア若しくはハードウェアの部分的若しくは全体的な故障。通信サーバーは、典型的には過負荷制御(コントロール)を実施する。そして、高度な要求が成されている期間中、許容可能なレベルで、前記サーバーが処理を行うサービス要求のスループットを維持している。
【0004】
過負荷が生じるのは、前記サーバーが受ける全ての要求を処理することに成功するためのサーバーのリソース(例えばCPUの処理容量、メモリ、ネットワーク帯域、入力/出力、ディスク・リソース等)が不充分なときである。ある種のサーバーでは、サービス要求が高速度で入ってきたり、及び/又はネットワークが部分的に損傷することが原因となって、過負荷が継続される事態を経験する可能性がある。過負荷は、以下の要素(個々又は組合せ)によって生じうる:(1)メディアが喚起する大衆要求イベント(例えば、遠隔投票、慈善活動アピール、コンペ、マーケティング・キャンペーン等);(2)緊急事態;(3)ネットワーク装置の故障;(4)自動スケジュール要求(例えば、雪の日にキャンセルする警告);及び/又は(5)サービス拒否(Dos)攻撃。過負荷集中というものは、ネットワークのサブセットに過負荷が集中するという、ネットワーク過負荷の特殊なケースである。前記サブセットとしては、ネットワーク目的地(例えば、電話番号やIPアドレス等)から、ネットワーク・サーバのグループまで等が挙げられる。
【0005】
過負荷制御がない状態では、こうした過負荷によって、通信ネットワークの安定性が脅かされる可能性がある。そして、サービス完了に成功する可能性を著しく減少させることにもなりうる。究極的には、要求が失われることが原因となって、サーバー(複数可)はサービス(複数可)を提供することに失敗する可能性があり、結果としてクライアントへサービスの非可用性へとつながる。また、過負荷問題については、これら過負荷問題自身が重なり合うことが良くあり、これによって、サーバー(複数可)に更なる負荷を引き起こす可能性がある。更に、過負荷がかかっている最中は、サーバー(複数可)の全体容量はダウンする可能性がある。なぜなら、該サーバーのリソースの多くは、サーバーが実際に処理することが出来ない負荷を拒否したり及び/又は処理したりするするのに費やされるからである。こうした深刻な過負荷の下、スループットは、元々の処理能力と比べて低い割合まで低下する可能性がある。こうした現象は、しばしば、コンジェスション・コラプス(congestion collapse)と呼ばれる。更に言えば、過負荷によって、サービス要求が遅延したり及び/又は失われたりする傾向が生じ、これによって、クライアントの取り下げや及び/又はリトライ(reattempts)を高速化させる可能性がある。
【0006】
高度且つ予想不可能な要求レベルから保護することを目的とし、且つ、過負荷を処理する最中クライアントが早まってサービス要求を取り下げることを防ぐのに充分に短い応答時間を維持することを目的として、サーバーは、適応性の過負荷検出及び制御の形態を幾つか備えることができる。あるサーバーでは過負荷コントロール機構を内部に実装している。該機構では、過負荷がかかったサーバーは新たな要求を拒否して、許容セッションの完了が成功することを最大化させることができる。また、あるサーバーでは過負荷コントロール機構を外部に実装することができる。該機構では、1以上のクライアントにコントロール・メッセージを通信することによって、サービスを要求する追加要求をクライアントが送ることができる速度(例えば、要求速度についての制限を設定する等)にサーバーがコントロールすることができる。
【0007】
しかし、サーバーが実装した、内部又は外部の機構は、「受信側ベース」のコントロール機構としても知られているが、上述したように、サーバーを過負荷から限定された度合いで保護することができるにすぎず、コンジェスション・コラプスを防止するのは困難である。特に、受信側ベース・コントロール機構は、サーバーに対して、サーバーの内部の過負荷レベルに基づいたクライアントへの制限を管理及び更新し、その後クライアントに対して過負荷フィードバック機構を介してこうした制限を配信する必要が生じる。例えば、制限には、明示的な速度メッセージ、(確認なしでサーバーに送ることができるメッセージ数を制限する)過負荷ウィンドウ・サイズ・メッセージ、及び/又はロス・パーセンテージ・メッセージ(該メッセージによりクライアント側はサーバーに向かって通常送られる要求の数を減らす)。全ての受信側ベースの概念は、配信リストを更新するために、クライアントの活動を監視する必要が生じる。配信リストについては、新たなクライアントが出現した場合に前記サーバー配信リストに新たなクライアントを追加することや、適切な時間クライアントが送信を中断している場合に既存のクライアントを削除すること等を含むことができる。こうしたことが各々必要になることにより、既に過負荷がかかっているサーバーに更に処理負荷が追加されることになってしまう。
【0008】
更に、明示的な速度及び過負荷ウィンドウ・スキーマにおいて、過負荷がかかったサーバーは、各上流近隣から該サーバーが受け取る負荷の量を連続的に評価する。従って、適切な速度キャップ又は過負荷ウィンドウサイズを割り当て、それらについては、制限レベルを更新するために送信クライアントに対して、時間内に送り返すべきものである。ロス・パーセンテージをフィードバックする受信側ベースの概念は、過負荷のかかったサーバーにたいして同様のオーバーヘッドをかけることができない。なぜなら、同じロス・パーセンテージを全ての上流近隣に送ることが可能であり、従って、各クライアントから受け取る要求速度を追跡するための要求を落としてしまうからである。しかし、ロス・パーセンテージの概念は、効果的なコントロールを提供することができない。なぜなら、上流クライアントが、過負荷のかかったサーバー(該ロス・パーセンテージは素早く変動するが)に対する要求速度に関するロス・パーセンテージを適用するにつれて、前記過負荷のかかったサーバーに対する要求速度も素早く変動しうるからである。こうした変動があるため、過負荷のかかったサーバーには、スロットル・パーセンテージを現在の過負荷状態に素早く適応させる能力が要求される。
【0009】
受信者ベース制御に関する別の欠点としては、該コントロールは、過負荷フィードバック機構を実装することを目的として、クライアント及びサーバー(複数可)において特定のプロトコル・スタックに対する変更を必要とする可能性がある点がある。例えば、集中過負荷を検出するために提案されたある技術は負荷フィルタリングであり、該技術においては、特定の目的地へのコールや特定のソースからのコールについては速度制限したりまたはランダムに落としたりするように指示するフィルターをネットワーク・オペレータが作成する。しかし、こうした機構では、サーバーのSIPスタックが新たな過負荷イベント・パッケージを含むことが必要になる。プロトコル・スタックに対する変更は、こうした制御を適用することを遅くしてしまう可能性がある。更に、こうした機構は、過負荷イベントを予め知っていること(例えば、遠隔投票)に基づいて設計される静的な機構であり、突然の過負荷(例えば、緊急事態やネットワーク故障に関連した過負荷)に反応することについては失敗に終わるであろう。
【0010】
集中過負荷を検出するために提案された別の技術として、特定の目的地へのコール拒否速度(例えば、コールされた数)を監視しており、前記速度が特定の閾値を超えているかどうかを監視している。そして、該目的地へ集中する可能性がある過負荷として該イベントをレポートする。前記サーバーは、該目的地へのコールに対するスロットルを開始し、同時に上流サーバーに対して該過負荷イベントを広げる。しかし、こうした検出アルゴリズムは、トークン・バケットを使用して実装され、大量のストレージを必要とする。更に言えば、こうした機構は、過負荷を検出するための明示的なコール拒否のみに依存しており、集中した過負荷イベントを検出するためにネットワーク間の配信されたモニターチームを必要とする。
【発明の概要】
【課題を解決するための手段】
【0011】
過負荷がかかっている最中にサーバーのリソースをコントロールするためのアプローチの一つとして、クライアント・コントロールを介したサーバー過負荷制限が挙げられる。一態様において、本発明は、ネットワーク中のサーバー過負荷を制限するためのコンピュータ化された方法を特徴とする。該方法は、ネットワークのサーバー・ノードによって、下流サーバーからフィードバック・メッセージを受け取ることを含む。ここで前記フィードバック・メッセージは、通信プロトコルの統計情報を含む。前記方法は、前記フィードバック・メッセージ中に含まれる情報に基づいて1以上のハッシュ関数を用いて、コンピュータ・メモリ・モジュール中に保存された、カウンター配列からの1以上のカンウターのうちどれが下流サーバーと関連しているかを、サーバー・ノードが決定することを含む。1以上のカウンターは、下流サーバーから受け取った統計情報を含むフィードバック・メッセージの数に対応する数を保存する。前記方法は、統計情報を含むフィードバック・メッセージに応答して、1以上のカウンターをサーバー・ノードが増加させることを含む。前記方法は、1以上のカウンター中に保存された数の値を、1以上のハッシュ関数を用いて、サーバー・ノードが決定することを含む。前記方法は、前記値が所定の基準を充足するかどうかに基づいて、下流サーバーに関するネットワーク中の過負荷エピソードを前記値が表していることを、サーバー・ノードが決定することを含む。
【0012】
別の実施形態では、前記所定の基準は閾値であり、前記決定することは、前記値が閾値を超えることを決定することを含む。前記閾値は、ヒステレシスを用いて計算することができる。過負荷エピソードを引きおこす原因となる1以上のソースを特定することができ、ここで各ソースは、下流サーバーに対して伝送を開始し、該伝送によって下流サーバーは、統計情報を含むフィードバック・メッセージを伝送させる。
【0013】
別の実施形態では、前記値に基づくコントロール動作を行うことを目的とする1以上のコントロール・パラメータを決定する。ここで、前記コントロール動作は、過負荷エピソードの原因となる1以上のソースから下流サーバーへの転送データ速度を減少させる。前記1以上のコントロール・パラメータは、過負荷エピソードの原因となるソースと下流サーバーとの間のサーバー・ノードに送ることができる。前記コントロール動作は、ソースから下流サーバーへ伝送される伝送データ速度を減少させることによって、ソースから下流サーバーへ伝送されるデータに関してサーバー・ノードで行うことができる。ここで前記減少は1以上のコントロール・パラメータに基づいて行う。前記伝送速度は、過負荷エピソードの原因となる1以上のソースの下流サーバーへの要求試行速度(call attempt rate)であってもよい。
【0014】
別の実施形態では、1以上のコントロール・パラメータを決定することが、以下の決定することを含む:コントロール動作をどこで行うべきかを特定する動作位置を決定すること;前記動作位置でコントロール動作を適用する1以上のソースを定義する動作フィルターを決定すること;及び、コントロール動作に関する動作レベルを決定すること。前記動作レベルを決定することには以下の決定を含めることができる:所定の閾値を前記値が超えているかどうかを決定すること;そして、所定の閾値を前記値が超えている場合には、減少因子を用いて以前の動作レベルから減少させることを決定すること、前記値が前記所定の閾値未満の場合、前記動作レベルについて、増加ステップを用いて以前の前記動作レベルから増加させることを決定すること。前記所定の閾値はヒステレシスを用いて計算することができる。決定することについて、以下の動作定を含めることができる:前記値が所定の目標値と等しいかどうかを決定すること;並びに、もし前記値が前記所定の目標値と等しい場合には、前記動作レベルを変更しないこと;又は、もし前記値が前記所定の目標値と等しくない場合には、前記値と前記所定の目標値との差異及び以前の動作レベルに基づいて前記動作レベルを決定すること。前記1以上のコントロール・パラメータは前記動作位置に配信することができる。
【0015】
別の実施形態では、前記方法は、以下のステップを含む:第二フィードバック・メッセージを第二下流サーバーから受け取るステップ(ここで前記 第二フィードバック・メッセージは前記統計情報を含む);前記第二フィードバック・メッセージ中に含まれる情報に基づき1以上のハッシュ関数を用いて、カウンター配列からの1以上のカンウターのうちのどれが前記第二下流サーバーと関連しているかを決定するステップ;及び、前記統計情報を含む前記第二フィードバック・メッセージに応答して前記1以上のカウンターを増加させるステップ。複数のカウンター配列は保存することができ、ここで前記複数のカウンター配列それぞれは、異なるサーバー・ノードに保存されている。そして、複数のサーバー・ノードに跨る前記複数のカウンター配列に関連する各下流サーバーから受け取ったフィードバック・メッセージの数を計算するために前記複数のカウンター配列を集計することができる。前記通信プロトコルはセッション確立プロトコル (Session Initiation Protocol、SIP)であってもよく、及び前記統計情報がセッション拒否、前記下流サーバーからの過負荷フィードバック又はその両方であってもよい。前記通信プロトコルがセッション確立プロトコル、ハイパーテキスト・ドランスファー・プロトコル(HTTP)、ストリーム制御転送プロトコル(SCTP)、又はTCPプロトコル(transmission control protocol)であってもよい。
【0016】
別の実施形態では、前記1以上のハッシュ関数及び前記カウンター配列がカウンティング・ブルーム・フィルターに関連している。また、1以上のカウンターのうちどれが前記下流サーバーに関連するかについて決定することが、キーに関連するハッシュ関数を用いて前記1以上のカウンターを決定することを含み、前記キーは前記下流サーバーに関する識別子である。前記増加させるステップが以下のステップを含むことができる:前記1以上のカウンターを1ずつ増加させるステップ;又は、前記1以上のカウンターを1を超える数で増加させるステップ(ここで、前記1を超える数は以下に基づいて決定される:前記統計情報;一定期間、前記下流サーバーから受け取る統計情報;複数の一定期間、前記下流サーバーから受け取る統計情報;ソースから前記下流サーバーへ行われる伝送の種類;又はこれらの任意の組合せ)。
【0017】
別の実施形態では、ブルーム・フィルターに基づくマルチ(複数)・レベルな閾値を動作位置に配信するステップを更に含む(ここで前記ブルーム・フィルターに基づくマルチ・レベルな閾値は、以下を保存する:複数の閾値(ここで前記複数の各閾値は、前記通信プロトコルに関するコール・リクエストと関連する複数のクラス(分類)からの1つのクラスに対応する);及び、1以上のハッシュ関数を用いた前記複数の各クラスに関する、前記下流サーバーに対するコール・リクエストのカウント)。前記方法は、以下のステップを含むことができる:ソースから前記下流サーバーへのコール・リクエスト・メッセージを受け取るステップ(前記コール・リクエスト・メッセージは、前記複数のクラスのうち1つのクラスを含む); 前記ブルーム・フィルターに基づくマルチ・レベルな閾値を用いて、以下を決定するステップ:(1)前記コール・リクエスト・メッセージ中の前記クラスに関する閾値;及び、(2)前記1以上のハッシュ関数を用いて、ブルーム・フィルターに基づく前記コール・リクエスト・メッセージ中の前記クラスに関する、前記下流サーバーへのコール・リクエストのカウント;並びに、もし、前記コール・リクエストのカウントが前記閾値を超える場合、前記コール・リクエスト・メッセージを拒否するステップ;又は、もし、前記コール・リクエストのカウントが前記閾値未満の場合、前記コール・リクエスト・メッセージを受け入れるステップ。前記統計情報は:ソースから前記下流サーバーへの失敗した接続リクエスト;前記下流サーバーからの過負荷通知;又はこれら両方であってもよい。
【0018】
別の態様において、本発明は、ネットワーク中のサーバ過負荷を制限するためのシステムを特徴とする。前記システムは、以下を備える:カウンター配列を保存するように設計されるコンピュータ・メモリ・モジュール;及び、前記コンピュータ・メモリ・モジュールと通信し、以下の手段を備えるコントローラ:下流サーバーからフィードバック・メッセージを受け取るためのコンピューティング手段(ここで前記フィードバック・メッセージは通信プロトコルの統計情報を含む);前記カウンター配列からの1以上のカウンターのうちのどれが前記下流サーバーに関連するかについて、1以上のハッシュ関数を用い、前記フィードバック・メッセージ中に含まれる情報に基づいて決定するためのコンピューティング手段(ここで前記1以上のカウンターは、前記下流サーバーから受け取り、且つ前記統計情報を含むフィードバック・メッセージの数に対応する数を保存する)。また、前記コントローラは、以下のコンピューティング手段を備える:前記統計情報を含む前記フィードバック・メッセージに応答して前記1以上のカウンターを増加させるためのコンピューティング手段;前記1以上のカウンターに保存される数の値を前記1以上のハッシュ関数を用いて決定するためのコンピューティング手段;及び、前記値が所定の基準を満たすかどうかに基づいて、前記下流サーバーが関連する前記ネットワーク中の過負荷エピソードを前記値が表すことを決定するためのコンピューティング手段。
【0019】
別の態様において、本発明は、情報キャリア中で実際に実行されるコンピュータ・プログラム製品であることを特徴とする。コンピュータ・プログラム製品は、データ処理装置に以下の動作を行わせるために実行可能な指示を含む:下流サーバーからのフィードバック・メッセージを受け取ること(ここで前記フィードバック・メッセージは通信プロトコルの統計情報を含む);コンピュータ・メモリ・モジュールに保存されたカウンター配列からの1以上のカウンターのうちのどれが前記下流サーバーと関連するかを、前記フィードバック・メッセージ中に含まれる情報に基づき、1以上のハッシュ関数を用いて決定すること(ここで前記1以上のカウンターは、前記下流サーバーから受け取とり、且つ前記統計情報を含むフィードバック・メッセージの数に対応する数を保存する)。前記コンピュータ・プログラム製品は、以下の動作をデータ処理装置に行わせるために実行可能な指示を更に含む:前記統計情報を含む前記フィードバック・メッセージに応答して前記1以上のカウンターを増加させること;前記1以上のカウンターに保存される数の値を前記1以上のハッシュ関数を用いて決定すること;及び、前記値が所定の基準を満たすかどうかに基づいて、前記下流サーバーが関連する前記ネットワーク中の過負荷エピソードを前記値が表すことを決定すること。
【0020】
別の態様において、クライアント・コントロールを介したサーバー過負荷制限を目的とするコンピュータ化された方法がある。前記方法は、以下のステップを含む:サービスに関する複数要求(リクエスト)の第一セットを第一期間中第一伝送速度でサーバーに伝送するステップ;及び第一期間中第一伝送制限速度以下になるよう前記第一伝送速度を制限するステップ。また、前記方法は以下のステップを含む:サービスに関する前記複数リクエストの第一セットのうち少なくとも2以上のリクエストが過負荷基準を満たしているかどうかに基づいて過負荷値を決定するステップ;前記過負荷値をコンピュータ・メモリ・モジュールに保存するステップ。また、前記方法は以下のステップを含む:前記過負荷値及び前記第一伝送制限速度に基づいて第二伝送制限速度を決定するステップ。また、前記方法は以下のステップを含む:サービスに関する複数リクエストの第二セットを前記第一期間後の第二期間中に第二伝送速度で前記サーバーに伝送するステップ;及び、前記第二期間中の第二伝送速度を前記第二伝送制限速度以下になるよう制限するステップ。
【0021】
別の態様において、クライアント・コントロールを介したサーバー過負荷制限を目的とするシステムがある。前記システムは、バッファ、伝送機、及びコントローラを備える。前記バッファは、サービスを要求する複数リクエストの第一セットを保存するように設計される。前記伝送機は、前記バッファと接続され、サービスを要求する前記1以上のリクエストを伝送制限速度以下となる伝送速度で第一期間中サーバーに伝送するように設計される。前記コントローラは、以下の手段を備える:サービスに関する前記複数リクエストの第一セットのうち少なくとも2以上のリクエストが過負荷基準を満たしているかどうかに基づいて過負荷値を決定するためのコンピューティング手段。また、前記コントローラは、以下の手段を備える:前記過負荷値及び前記伝送制限速度に基づいて、伝送制限速度を調整するためのコンピューティング手段。
【0022】
別の態様において、コンピュータ・プログラム製品がある。前記コンピュータ・プログラム製品は、機械読取可能ストレージデバイスで実際に実行され、前記コンピュータ・プログラム製品が、データ処理装置に以下の動作を行わせるために実行可能な指示を含む:サービスに関する複数リクエストの第一セットを第一期間中第一伝送速度でサーバーに伝送すること;及び、前記第一伝送速度を前記第一期間中第一伝送制限速度以下に制限すること。また、前記コンピュータ・プログラム製品が、データ処理装置に以下の動作を行わせるために実行可能な指示を含む:サービスを要求する前記複数リクエストの第一セットのうち少なくとも2以上のリクエストが過負荷基準を満たしているかどうかに基づいて過負荷値を決定すること;及びコンピュータ・メモリ・モジュールに前記過負荷値を保存すること。また、前記コンピュータ・プログラム製品が、データ処理装置に以下の動作を行わせるために実行可能な指示を含む:前記過負荷値及び前記第一伝送制限速度に基づいて第二伝送制限速度を決定すること。また、前記コンピュータ・プログラム製品が、データ処理装置に以下の動作を行わせるために実行可能な指示を含む:サービスを要求する1以上のリクエストの第二セットを前記第一期間後である第二期間中に第二伝送速度で前記サーバーに伝送すること;及び、前記第二期間中前記第二伝送制限速度以下になるように前記第二伝送速度を制限すること。
【0023】
他の態様において、上記態様の何れかは、以下の特徴の1以上を含むことができる。本発明では、前記過負荷値が目標過負荷値を下回るか上回るかを決定することをができる。前記過負荷値が前記目標過負荷値を超える場合に、前記第二伝送制限速度を決定することが、前記過負荷値と前記目標過負荷値との差分に比例する量だけ前記第一伝送制限速度を低下させることを含むことができる。前記過負荷値が前記目標過負荷値を超える場合に、前記第二伝送制限速度を決定するステップが、前記過負荷値に比例する量又は該過負荷値の目標過負荷値からの偏差に比例する量だけ前記第一伝送制限速度を低下させるステップを含むことができる。
【0024】
幾つかの実施形態において、前記過負荷値が前記過負荷基準を満たすリクエスト速度を表す。前記過負荷値が前記目標過負荷値未満の場合に、前記第二伝送制限速度を決定することが前記第一伝送制限速度を速度ステップ(rate step)だけ上昇させることを含むことができる。前記速度ステップは固定されていてもよい。前記速度ステップは前記第一伝送制限速度に基づくことができる。前記速度ステップの範囲は最大速度ステップ及び最小速度ステップで決定することができる。第一層エンティティは前記過負荷値を決定することができ、第二層エンティティは前記第一伝送速度を制限することができ、前記第一層エンティティは前記第二層エンティティとは異なってもよい。前記第一層エンティティは、トランスポート層エンティティを含むことができ、前記第二層エンティティがアプリケーション層エンティティを含むことができる。
【0025】
前記過負荷基準は明示的な過負荷基準であってもよい。前記明示的な過負荷基準は単一のリクエストのみに適用されてもよい。前記明示的な過負荷基準は非スロットリング型クライアント・レスポンスを特定することができる。さらに他の実施形態では、前記第一セットからのリクエストであって且つサービスを要求する第一リクエストに関する第一拒否メッセージを前記サーバーから受け取った場合、前記第一リクエストが前記明示的な過負荷基準を満たすことができる。
【0026】
前記過負荷基準は暗黙的な過負荷基準であってもよい。前記第一セットからのリクエストであって且つサービスを要求する第一リクエストが伝送されてからの経過時間が遅延閾値を超える場合に、前記第一リクエストが前記暗黙的な過負荷基準を満たすことができる。ある時間間隔でサービスを要求する未応答のリクエストの割合が割合閾値以上になった場合に、前記暗黙的な過負荷基準を満たすことができる。前記暗黙的な過負荷基準はピア・コンジェスションとは無関係の前記サーバーからの1以上の応答メッセージに基づくことができる。前記1以上の応答の割合が割合閾値以上になった場合に、前記暗黙的な過負荷基準を満たすことができる。前記暗黙的な過負荷基準は、割合閾値以上である前記1以上の応答割合の変化に基づくことができる。
【0027】
前記遅延閾値は静的であってもよい。前記遅延閾値は、前記サーバーに伝送されサービスを要求する1以上の以前のリクエストに対する平均応答時間に基づくことができる。前記遅延閾値は、前記サーバーに伝送されサービスを要求する1以上の以前のリクエストに対する百分率の応答時間に基づくことができる。前記第一セットからのリクエストであって且つサービスを要求する前記第一リクエストに対する第一応答を受け取る前に、前記第一セットからのリクエストであって且つサービスを要求する第二リクエストに対する第二応答を受け取るか否かに基づいて、第一リクエストが前記過負荷基準を満たすことができる(ここで、前記第二リクエストは、前記第一リクエストの後に前記サーバーへ伝送される)。
【0028】
幾つかの実施形態において、前記過負荷値を決定するステップが、前記過負荷基準を満たす前記第一セットからのリクエスト数を平均化するステップ及び/又はフィルタリングするステップを含むことができる。前記過負荷値を決定するステップは、更に、前記第一期間の前の1以上の期間に関連する1以上の以前の過負荷値に基づくことができる。前記第一期間は、前記第二期間とブラインド間隔期間だけ離れていてもよい。前記ブラインド間隔は、固定時間間隔であるか、及び/又は前記サーバーに伝送されサービスを要求する1以上の以前のリクエストに対する平均応答時間に基づくことができる。
【0029】
幾つかの実施形態において、前記複数リクエストの第一セットを伝送することは、前記1以上のリクエストの伝送について、リクエストの種類に基づいて優先順位を付けることを含むことができる。前記1以上のリクエストのリクエスト種類は、高優先度、通常、又はこれらの任意の組合せを含むことができる。前記複数リクエストの第一セット及び第二セットは、同一の分類又は種類であってもよい。前記複数リクエストの第一セットは、第一分類又は種類及び第二分類又は種類のリクエストを少なくとも含みことができる。前記複数リクエストの第二セットは前記第一分類及び/又は種類のリクエストのみを含むことができる。前記第一分類及び/又は種類は、1以上のサービス要求を自動的に再伝送することを含むことができる。
【0030】
別の実施例において、方法に関連する上述の任意の特徴は、システム及び/又は前記システムのコントローラが実行することができ、該システム及び/又は該コントローラは前記方法を実行するために設計され又はそのための手段を有する。さらに、方法に関連する上述の任意の特徴は、コンピュータ・プログラム製品が実行することができ、プログラム製品がデータ処理装置に前記方法を行わせるために実行可能な指示を含む。
【発明の効果】
【0031】
上述した任意の実施形態は、以下の1以上の利点を実現することができる。通信プロトコルの統計情報を保存するために、スペース的に有効な及びコンピュータ的に効果的なデータ構造(例えばブルーム・フィルター)を用いることにより、過負荷エピソード(例えば集中した過負荷エピソード)の検出を素早く効果的に行うことができる。前記実施形態は、複数のネットワーク要素(例えば、ソース、サーバー・ノード)に跨って保存されるデータ構造を集計するように設計することができ、下流サーバーやネットワーク要素に関連するネットワーク・ワイドな統計情報を集めることができる。コントロール・パラメータは、前記データ構造に基づいて計算され、適切な動作位置に配信される(例えば、クライアント、サーバー・ノード)。そして、過負荷エピソードを引き起こすメッセージの数を、下流サーバーに到達する前に減らす。そして、ネットワーク帯域を不必要に使用することを防止する。さらに、下流サーバーへの処理負荷を減らす。過負荷コントロールをクライアント側に分散させることにより、サーバーに与えられる負荷を、サーバースループットを最大化させるレベルにまで減少させることができる。幾つかの前記実施形態では、過負荷のかかったサーバーに到達する前に、幾つかのサービス要求をクライアントに抑えさせるように設計することができる。このことにより、結果としては、過負荷のかかったシステムに、より極端な過負荷が係ることを防止することができ、及び/又は過負荷イベントの全期間中最適に近い負荷でサーバーが稼動することを可能にすることができる。
【0032】
他の実施形態では、応答(レスポンス)時間を決定することができる。サービス要求の遅延フィードバックを減らすことによりコントロールの安定性に寄与することができる点で有利である。更に、クライアント・ベースのコントロールは、処理過負荷をクライアント側に移行させることにより、クライアントへの制限レベル・コントロール・メッセージを更新及び/又は配信するというサーバー側の負荷を軽減できる点で有利である。更なる実施形態では、前記サービス・プロトコル(例えば、SIP)の変更を必要とせずに設計できる点で有利である。更には、クライアント実施の過負荷コントロールは、前記クライアント・システム上で完全に実施することができる。そして、過負荷のかかったサーバーへの処理負荷を減らすことが出来る点で有利である。サーバーのパフォーマンスは、サービス由来のインフラの操作に非常に重要なものと成りうるため、クライアント実施過負荷コントロール技術は、メディアへの応用の際の待ち時間(例えば電話コールを開始する場合)を減らすことができる点で有利である。そして、サーバーに過負荷がかかったとしても、スループットを最大又は実質的に最大に維持できる点で有利である。
【0033】
クライアント実施過負荷コントロール技術は、方法及び装置が含まれるが、例えば以下の要件を1以上満たすことができる:(1)過負荷のかかったサーバーにおいてスループットを自動的に最大化すること;(2)過負荷イベント期間中の高スループットを実現すること;(3)過負荷がかかっている最中、クライアントが早まってサービス要求を取り下げることが無い様に、応答時間の高い割合が充分に低いこと;(4)作業過負荷の変化に素早く反応すること。前記過負荷コントロール技術は、前記過負荷イベントを予め知っておくことに依存しない点で有利である。更に、サービス識別子(例えば、ユニーク・コード)は、特定のサービス要求を、1以上のサービス分類に分類することができる(例えば、各サービスの分類が異なるレベルのスループットを有する)。
【0034】
1以上の実施例に関する詳細は、添付した図面及び以降の記述の中で述べる。更に、本発明の特徴、態様、及び利点については、本明細書、図面、及び特許請求の範囲から明らかになるであろう。前記図面については、必ずしも本発明そのものを表すものではなく、本発明の原則を例示する際に一般的に示されるものである点を強調しておく。
【0035】
添付した図面と関連して以降の記載を参照することにより、上述した本発明の利点については、更なる利点と共に、より深く理解されるであろう。前記図面については、必ずしも本発明そのものを表すものではなく、本発明の原則を例示する際に一般的に示されるものである点を強調しておく。
【図面の簡単な説明】
【0036】
【図1】クライアントからのサービス要求を処理するサーバーに関係する装置(デバイス)に関する例示的なネットワークを表したブロック図である。
【図2】クライアントの構成要素を表したブロック図である。
【図3】モデル・コントロール・ループの構成要素を表したブロック図である。
【図4】ウィンドウ化したタイム・インターバルを表す図である。
【図5】サーバー・リソースの外部コントロールを描いたフローチャートである。
【図6】サーバー・リソースの外部コントロールを描いたフローチャートである。
【図7】SIPメッセージ・フローのシミュレート・モデルを描いたハシゴ図である。
【図8】異なる過負荷コントロール概念(スキーマ)に関して、与えられた負荷に対するスループットを表した二次元プロットである。
【図9】本発明の例示的な実施形態に従って、集中したサーバー過負荷を検出及び制限することを目的とするネットワークを概念的に図示したものである。
【図10】本発明の例示的な実施形態に従って、ネットワーク中の集中したサーバー過負荷を保存及び検出することを目的とするブルーム・フィルターを概念的に図示したものである。
【図11】本発明の例示的な実施形態に従って、ネットワーク中の集中したサーバー過負荷を検出することを目的とする方法を例示したフローチャートである。
【図12A】本発明の例示的な実施形態に従って、ネットワーク中の集中したサーバー過負荷を検出することを目的とするカウンティング・ブルーム・フィルターに関するチャートを概念的に図示したものである。
【図12B】本発明の例示的な実施形態に従って、ネットワーク中の集中したサーバー過負荷を検出することを目的とする集計カウンティング・ブルーム・フィルターに関するチャートを概念的に図示したものである。
【図12C】本発明の例示的な実施形態に従って、ネットワーク中の集中したサーバー過負荷を検出することを目的とする、集計されたコール数の分布に関するチャートを概念的に図示したものである。
【図13】本発明の例示的な実施形態に従って、ネットワーク中の集中したサーバー過負荷を制限することを目的とする1以上のコントロール・パラメータを決定するための方法を図示したフローチャートである。
【図14A】本発明の例示的な実施形態に従って、ネットワーク中の集中したサーバー過負荷を制限することを目的とする動作レベルを決定するための方法を図示したフローチャートである。
【図14B】本発明の例示的な実施形態に従って、ネットワーク中の集中したサーバー過負荷を制限することを目的とする動作レベルを決定するための方法を図示したフローチャートである。
【図15】本発明の例示的な実施形態に従って、ネットワーク中の集中したサーバー過負荷を制限することを目的とする方法を図示したフローチャートである。
【発明を実施するための形態】
【0037】
1.ネットワークの概要
本明細書で記述するシステム及び方法は、コンピュータ中に通信プロトコル統計情報(例えば、下流サーバーからフィードバック・メッセージを介して受け取るなど)を保存するものであり、スペース的に有効な及びコンピュータ的に効果的なデータ構造(例えばブルーム・フィルター、カウンティング・ブルーム・フィルター、又はブルーム・フィルターに基づくマルチ・レベルな閾値(MLBF))を使用する。ここで、用語「ブルーム・フィルター」が、本明細書において概して使用されているが、任意の種類のブルーム・フィルターを意味し、例えば、従来のブルーム・フィルター、カウンティング・ブルーム・フィルター、MLBF等が挙げられる点を理解されたい。前記データ構造を用いて、過負荷エピソードが下流サーバーや目的地に存在するかどうか(例えば、集中過負荷が下流サーバーに存在するかどうか)をネットワーク上のサーバーが決定する。もし、過負荷が存在する場合には、コントロール・パラメータがコンピューターを用いて計算され、該パラメータはコントロール動作を定義し、そして、該コントロール動作は1以上のネットワーク構成要素に配信され、過負荷エピソードをコントロールする(例えば、ソースから過負荷のかかった下流サーバーや目的地への伝送速度を減少させるなど)。
【0038】
図1は、クライアントからのサービス要求を処理するサーバーに関係する装置に関する例示的なネットワーク(100)を表したブロック図である。前記ネットワーク(100)は、伝送媒体(110)、1以上のクライアント(120a、120b、及び/又は120c、概して120)、及び少なくとも1つのサーバー(130)(例えば下流サーバー)を含む。伝送媒体(110)(例えば、通信ネットワーク)は、サービス要求を含む情報を、1以上のクライアント(120)及び/又はサーバー(130)の間で伝送する役割を担う。以降でさらに詳述するが、クライアント(120)は、本明細書に記述された幾つかの発明技術に従って設計される。1以上のクライアント(120)及びサーバー(130)の間で、1以上の中継サーバー・ノードがあってもよく、該サーバー・ノードはクライアント(120)でもサーバー(130)(又は下流サーバー(130))でもない任意のノードである。
【0039】
伝送媒体(110)は、接続部(115)によってクライアント(120)と接続することができる。クライアント(120)は、サーバー(130)からの1以上のサービスを要求することができる任意の装置である。クライアント(120)としては、ユーザーデバイスを含むことができ、例えば、コンピュータ、電話、IP電話、携帯端末(例えば、携帯電話、PDA装置、ラップトップ・コンピュータ等)、及び/又は他の通信装置が挙げられる。幾つかの実施形態(例えば遠距離通信ネットワーク等)において、クライアント(120)は、メディア・ゲートウェイであり、例えば、コール・ソースからのセッション要求(図示しない)がネットワーク(110)に入る。また、幾つかの実施形態において、1以上のクライアント(120)は、1以上のサーバー機能を実行することもでき、従って、サーバー(130)とは異なるサーバー(複数可)としてみなしてもよい。例えば、遠距離通信ネットワークにおいては、遠距離通信スイッチ(例えば、端局又はタンデム・スイッチ)がサーバーとして動作することができ、及び/又は、任意の近隣遠距離通信スイッチに対するクライアントとして動作することができる。そして、それぞれが、コール・セットアップ等のサービスを要求するクライアントとして動作したり及び/又はサーバーとして動作したりすることができる。別の例においては、IPルータやネットワーク・スイッチは、任意の近隣の又は遠隔のIPルータ又はネットワーク・スイッチに対するサーバー及び/又はクライアントとして動作することができる。そして、前記任意の近隣の又は遠隔のIPルータ又はネットワーク・スイッチも、それぞれ、クライアント及び/又はサーバーとして動作することができる。クライアントとして、近隣又は遠隔のIP装置は、IPパケットの伝送を要求することができ、及び/又はゲートウェイ・コントロール要求を送ることができる。本発明の別の例では、クライアント(120)及びサーバー(130)は、物理的に同一及び/又は論理的のいずれかの意味で同一のコンピューティング・デバイス内に配置することができる。例えば、コンピュータは、複数のタスク、プログラム、及び/又はプロセスを実行することができるが、この場合、サーバー(130)中の単一の処理ユニットは、クライアント(120)として動作するためのタスク、プログラム、及び/又はプロセスそれぞれに関するサービスの処理を担う。この例において、クライアント(120)が前記処理ユニット(即ち、サーバー(130))から分離している場合には、伝送媒体(110)は内部バスを含むことができる。
【0040】
接続部(115)は、電線、光学ファイバー、及び/又は無線伝送部等を含むことができる。また、接続部(115)は、クライアント(120)をネットワーク(110)に接続する1以上の中継装置を含むことができる。クライアント(120)は、ユニークな識別子及び/又は共有された識別子によって識別することができる。ユニークなクライアント識別子は、例えば、電話番号、IPアドレス等が挙げられる。共有されたクライアント識別子としては、例えば、ネットワーク・アドレス、エリア・コード、国別コード、サービス識別子等が挙げられる。
【0041】
サービス識別子は、特定のサービス要求を1以上のサービス分類に分類するユニークなコードであってもよい。また、サービス要求は要求種類に基づいて分類することもできる。例えば、サービス要求は、新たなセッションを要求する要求メッセージ、又は既存のセッションの更新又は変更を要求する要求メッセージのいずれかに分類することができる。また、サービス要求は、以前送信された要求メッセージの再送信であるかどうかについて分類することができる(例えば、タイムアウト条件によって、クライアントに対して要求の再送信を指示した場合等)。別の例では、サービス要求は、データベース探索を必要としない要求メッセージ、又は1以上のデータベースの探索をプロセスに対して要求する要求メッセージの何れかに分類することができる。更に別の例では、サービス要求は、クライアントが登録した購入(subscription)レベルに基づいて分類することができる。更に別の例では、サービス要求は、電子商取引購入活動、又は非電子商取引活動(例えば閲覧活動)のいずれかに関連するものとして分類することができる。更に別の例では、サービス要求は、以下のように優先度で分類することができる:優先要求;通常要求;又は、低優先度要求。一般的に、要求の優先度は、レベルに関する任意の番号で分類される(例えばレベル0〜10までの優先度レベルを割り当てるなど)。
【0042】
異なる分類のサービスを提供することは、サーバー(130)の異なるリソースを消費しうる(例えば、メモリ、ディスク帯域(disk bandwidth)、通信帯域、及び/又は処理サイクル)。別の実施形態では、クライアント(120)及び/又はサービス要求の分類付けは任意であってもよいため、クライアント(120)及び/又はサービス要求は識別子によって同定したり分類したりする必要がない。
【0043】
また、伝送媒体(110)は、接続部(115)によって、サーバー(130)に接続することができる。サーバー(130)は、クライアント(120)からのサービスの各要求を処理することにより、1以上のクライアント(120)に対して、1種以上のサービスを提供する役割を担っている。サーバー(130)としては、例えば、ウェブ・サーバー、アプリケーション・サーバー、メディア・サーバー、ゲートウェイ、ソフトスイッチ、遠距離通信スイッチ(例えば、トール(toll)又はタンデム・スイッチ)、ネットワーク・ルータ、又はスイッチ等が含まれる。幾つかの実施形態において(例えば、ピア・ツー・ピア・ネットワークにおいて)、サーバー(130)は、他のサーバー(図示しない)からの1以上のサービスを要求することもでき、従って、該サーバーは、クライアント(120)とは別のクライアントとしてみなすこともできる。
【0044】
サーバー(130)が提供しているサービスの種類として、例えば、音声サービス、ビデオ・サービス、データ・サービス、マルチメディア・サービス、及び/又は他の電子的なサービスを含むことができる。音声サービスとしては、例えば、遠距離通信ネットワークに関連するサービスの確立、維持、及び開放等が挙げられる。例えば、遠距離通信ネットワークに関して言えば、セッション要求がサーバーからネットワークへ出る。例えば、SS7 IAMメッセージ、SIPプロトコルINVITEメッセージ、又はH.323セットアップメッセージは、新たな電話コール又はコールセッションを開始するための要求であってもよい。同様にSIPプロトコルUPDATEメッセージは、既存のコールセッションの状態を更新するための要求であってもよい。ビデオ・サービスとしては、例えば、インターネットを介したビデオ・ストリーミングの確立、維持、及び開放を含むことができる。ビデオ・ストリーミングとしては、リアルタイム・ビデオ、及び/又はオンデマンド・ビデオを含むことができる。データ・サービスとしては、例えば、ウェブ・サイト(HTTP要求を処理する)、パケット・ルーティング(IPパケットをルーティングする)、及び/又は一般的なコンテンツ配信を含むことができる。他のサービスとしては、例えば、1以上のビデオ、オーディオ、及び/又はデータ・サービスを含むことができる。他の実施形態では、例えば、飛行機の予約システムに関するウェブ・サーバー、1以上のオーディオ・サーバー、e−mailサーバー、コラボレーション・サーバー、認証サーバー、及び/又は他のサーバー(複数可)がある。
【0045】
特に、セッション確立プロトコル(SIP)やH.323等のプロトコルは、様々な種類のメディア(例えば、音声、ビデオ、及び/又はテキストを含む)に関するセッションを作成したり、維持したり、及び/又は破棄したりするために使用することができる。SIPは、多くのメディア由来のアプリケーションで使用することができ、例えば、ボイップ(Voice over IP (VoIP))、ボイスメール、インスタントメッセージ、プレゼンス(presence)、IPTV,ネットワーク・ゲーム等が上げられる。また、SIPは、IPマルチメディアサブシステム(IMS)に関するコアプロトコルとして使用することができ、固定電話及び無線電話ネットワーク両方のための第三世代パートナーシップ・プログラム(3GPP)に関する基礎となっている。
【0046】
一実施形態において、例えば、サーバー(130)は、クライアント(120)にとってインターネットを介して利用可能な1以上のウェブサイトを管理するウェブ・サーバーであってもよい。別の構成では、サーバー(130)は、電話コールをセットアップしたり切断したり(tear down)するためのSS7シグナリング・メッセージを受信したり処理するPSTNに関するタンデム・スイッチであってもよい。別の構成では、サーバー(130)は、MGCPメディア・ゲートウェイ又はH.248/MEGACOメディア・ゲートウェイであってもよく、それぞれ、コール・エージェント(複数可)やメディア・ゲートウェイ・コントローラ(複数可)(MGC)からの要求を受け取る。更に別の構成では、サーバー(130)は、ネットワーク(110)上の他のクライアント(120)からのデータベース要求を処理するためのアプリケーション・サーバーであってもよい。他の構成では、サーバ(130)は、例えば、ソーナス・ネットワーク・PSX(商標)、ASX(商標)、GSX(商標)/NBS、及び/又はAGCFサーバーであっても良い。
【0047】
II クライアント実施過負荷コントロール
本発明に係る幾つかの実施形態によれば、外部の過負荷コントロールは、クライアント(120)(又は、クライアント(120)とサーバー(130)の間の中継サーバー・ノード、一般的には動作位置(action location)と呼ばれている)で実施されてもよい。有利な点として、クライアント実施過負荷コントロールは、過負荷がかかったサーバー(130)に対して、かかっている負荷をクライアント(120)が減らすことを可能にすることができ、その一方で、過負荷コントロールを目的として、サーバー(130)における負荷処理を犠牲にすることがない。その結果サーバー(130)のスループットが最大化できる。例えば、各クライアント(120)は、サーバー(130)での過負荷を表す明示的及び/又は暗黙的過負荷基準に基づいて、過負荷値(overload value)を決定することができる。この決定された過負荷値をフィードバックとして使用して、クライアント(120)は、サーバー(130)へのサービス要求を伝送する速度を適切に調整することができる。例えば、サーバー(130)に対するサービス要求の伝送速度は、前記決定された過負荷値に反比例するようにすることができる。従って、クライアント実施過負荷コントロールは、過負荷コントロール目的(例えば内部の過負荷コントロール)でサーバー(130)が処理リソースを割り当る必要性を防止したり、及び/又は補助したりすることができ、代わりに、サービス要求を処理するために最大量のリソースを割り当て、それによってスループットを上昇させる。
【0048】
一般的に、サービスに関するサービス要求の生成及び/又は発生は、通信プロトコル・スタックの任意の層で行うことができる。図2は、クライアント(120)の構成要素を表したブロック図(200)である。クライアント(120)は、少なくとも1つのコントローラ(280)、少なくとも1つのコンピュータ・メモリ・モジュール(290)を含むことができ、また、OSI参照モデル(ITU−T勧告X.200で定義されている)の1以上の層(210〜270)に従った1以上のプロトコルを含むことができる。前記OSI参照モデルは、通信システムに関する抽象的な記述であり、以下のように7つの層に分割される;物理層(210);データリンク層(220);ネットワーク層(230);トランスポート層(240);セッション層(250);プレゼンテーション層(260);及びアプリケーション層(270)。各層内で、1以上のエンティティが、別の上位層又は下位層に対してサービスを提供する同様の機能の集合体を実装することができる。
【0049】
物理層(210)は、機械的、電気的、機能的、及び手続き的な仕様を提供することができ、データリンクエンティティ間のビット伝送に関する物理的な接続を作動させたり、維持したり、不活化させたりする。データリンク層(220)は、機能的及び手続き的な仕様を提供することができ、ネットワーク・エンティティ間のデータリンク接続を確立したり、維持したり、及び開放したりすることを目的とする。そして、物理層(210)で発生するエラーを検出したり、おそらくは修正したりする。ネットワーク層(230)は、1以上のネットワーク上でのソース又は目的地間でのネットワーク接続を確立したり、維持したり、終了させたりするための仕様を提供することができ、そして、ソース及び目的地間でのデータ交換を行うための機能的及び手続き的な仕様を提供することができる。トランスポート層(240)は、セッション・エンティティ間での透過的なデータ伝送を提供する。そして、信頼性がありコスト的に有利なデータ伝送が達成される詳細な方法に関連する任意のものから開放する。また、トランスポート層(240)は、利用可能なネットワークの利用を最適化して、各セッション・エンティティが必要とする性能を最小限のコストで提供することができる。セッション層(250)は、エンティティ間でのダイアログ/接続をコントロールする仕様を提供することができる。また、セッション層(250)は、2つのプレゼンテーション・エンティティ間でのセッション接続を確立し、順番通りのデータ交換相互作用をサポートしたり、順番通りに接続を開放したりするためのサービスを提供することができる。プレゼンテーション層(260)は、アプリケーション・エンティティが通信内で通信又は参照のいずれかを行う情報を表したものを提供することができる。アプリケーション層(270)は、クライアント(120)上に存在するソフトウェア・アプリケーションと相互作用することができる。
【0050】
図2に示したクライアント(120)では、OSI参照モデルの7層に関してモデル化されたプロトコル・スタックを含んでいる。しかし、他のモデル及び/又は層を使用することもできる。例えば、クライアント(120)は、層210〜230(例えばルーターやレイヤー3スイッチ)のみに従ったプロトコルを含むことができる。また、他のモデルも使用可能であり、例えば、インターネットのTCP/IPモデルが挙げられ、該モデルでは4つの抽象層(リンク層、インターネット層、トランスポート層、及びアプリケーション層)を含む。一般的に、通信プロトコルは、必ずしも前述した抽象層(210〜270)の1つに属する必要はなく、ある場合には、2つ以上の層に含まれることができる。
【0051】
上述したように、サービス要求は、クライアント(120)のプロトコル・スタック(210〜270)中の1以上のプロトコルから発生又は生成することができる。コントローラ(280)は、プロトコル・スタック(210〜270)の1以上の層で、過負荷コントロールを実施して、サーバー(130)でのサービス要求処理に関するスループット及び/又は遅延を管理することを補助する。幾つかの実施形態において、コントローラ(280)は、プロセッサー又は装置であってもよい。他の実施形態では、コントローラ(280)はクライアント(120)中の別のプロセッサ又は装置によって実行される論理的な機能であってもよい。プロセッサとして、コントローラ(280)を設計することができ、コンピュータ・プログラムを実行し、入力データに関して操作したり及び/又は出力データを生成したりすることにより上述した技術を実践する。コンピュータ・プログラムを実行するのに適したプロセッサとして、例示的な意味で、汎用目的のマイクロプロセッサ、特定目的のマイクロプロセッサ、及び任意の種類のデジタル又はアナログコンピュータに関する1以上のプロセッサが含まれる。プロセッサは、例えばROMやRAM、又はその両方からの指示及びデータを受け取ることができる。
【0052】
装置として、コントローラ(280)は、特定目的の論理回路として実装することができ、例えば、FPGA(field programmable gate array)、FPAA(field−programmable analog array)、CPLD(complex programmable logic device)、PSoC(Programmable System−on−Chip)、ASIP(application−specific instruction−set processor)、ASIC(application−specific integrated circuit)等が挙げられる。サブルーチンは、1以上の関数を実行する保存されたコンピュータ・プログラム、及び/又はプロセッサ、及び/又は特別回路の一部を参照することができる。
【0053】
図2では、コントローラ(280)は、プロトコル・スタック(210〜270)とは別になるように図示されている。しかし、他の構成を使用することも可能である。例えば、コントローラ(280)は、プロトコル・スタック(210〜270)(例えばアプリケーション層(270))中の1以上のエンティティ(例えば、プロトコル又は層)に組み込むことができ、また前記プロトコル・スタック(210〜270)はコントローラ(280)に含むことができる。幾つかの実施形態において、一の層に組み込まれるコントローラ(280)には、プロトコル・スタック(210〜270)中の1以上の他のプロトコル又は層からのシグナルを提供することができる。例えば、アプリケーション層(270)に組み込まれたコントローラは、トランスポート層(240)からのシグナルに基づいた過負荷コントロールを実施することができる。
【0054】
コントローラ(280)は、コンピュータ・メモリ・モジュール(290)と通信するように連結することができる。コンピュータ・メモリ・モジュール(290)としては、指示及び/又はデータを保存するための1以上のメモリ装置又はメモリ・サブ・モジュールを含むことができる。メモリ装置(例えばキャッシュ・メモリ)は、一時的にデータを保存するために使用することができる。また、メモリ装置は、マス・ストレージ・デバイスとして実装することができる。コントローラ(280)及びコンピュータ・メモリ・モジュール(290)は、特定目的の論理回路に補足したり組み込んだりすることができる。
【0055】
クライアント・ベースの過負荷コントロールは、ホップ・バイ・ホップ又はエンド・ツー・エンドで実装することができる。ホップ・バイ・ホップには、直接トラフィックを交換する全ての近隣のクライアント(120)及びサーバー(130)間での分離したコントロール・ループを含むことができる。エンド・ツー・エンドには、サービス要求の全体パスにそったコントロール・ループを含むことができる。図3は、モデル・コントロール・ループ(300)の構成要素を表したブロック図である。モデル・コントロール・ループ(300)は、クライアント(120)のプロトコル・スタック(210〜270)の1以上の層において、クライアント・ベースの過負荷コントロール概念をどのように実装するかについて、物理的に又は論理的にの何れかで表すことができる。モデル・コントロール・ループ(300)には、フィードバック・シグナル/値(305)を受け取ったり及び/又は暗黙的なフィードバック値(図示しない)を作成したりすることができるセンサー/フィルター(310)を含むことができる。センサー/フィルター(310)は、参照入力(315)を用いたコントロール・ユニット(320)と連結している。コントロール・ユニット(320)はアクチュエータ(330)(例えば、レストリクタ)と連結しており、該アクチュエータは、内部のサービス要求(325)(例えば、かけられた負荷)が出力される(335)速度を電子的に調整することができる。コントロール・ユニット(320)は、センサー/フィルター(310)からのフィードバック値と参照入力(315)との間の差分に基づいて速度設定を決定し、該設定をアクチュエータ(330)へ送ることができる。参照入力(315)(例えば、目標過負荷値)は、システム出力(335)に関する所望の値をとることができる。参照入力(315)は、固定値をとることもでき、及び/又は変数をとることもできる。例えば、参照入力(315)は、サーバー(130)の容量に基づくことができる。フィードバック値(305)及び/又はシステム出力(335)は、接続部(115)から若しくは該接続部へ及び/又はプロトコル・スタック(210〜270)の1以上の層から、受け取ったり又は送ったりすることができる。
【0056】
センサー/フィルター(310)は、過負荷値を決定(例えば測定)することができ、該過負荷値は、サーバー(130)から受け取る明示的な過負荷シグナル又は通知(例えば、SIP 503(Service−Unavailable)、H.323/Q.931 Causeコード42、H.248 過負荷通知)の速度であってもよく、及び/又は暗黙的な過負荷値(例えば、リクエスト・タイムアウト)の速度であってもよい。また、暗黙的な過負荷通知は、過負荷コントロールを目的としないサーバー(130)から受け取ったメッセージを含むことができる(例えば、SIP 480 (Temporarily Unavailable)、又はH.323/Q.931 41 (Temporary Failure))。更なる過負荷通知機構を用いて、過負荷フィードバックをクライアント(120)に送るために使用することができ、該フィードバックとしては、例えば、特別なSIP応答ヘッダ又はSIP過負荷イベント・パッケージが含まれる。前記SIP過負荷イベント・パッケージによって、送信エンティティは、サーバーの過負荷状態に寄与したり、及びNOTIFY要求における過負荷コントロール状態変化に関する通知を受け取ることができるようになる。
【0057】
幾つかの実施形態において、過負荷通知(明示的及び/又は暗黙的)速度は、平均化フィルター(例えば、センサー/フィルター(310)中に含まれるもの)を通すことができ、測定を平坦化する。その後、平均過負荷通知速度を、目標過負荷値(315)と比較することができ、そして、その差分は、コントローラ(320)を作動させるために使用することができる。コントローラ(320)については、前記過負荷通知速度(305)(フィードバック値)(及び/又は暗黙的な過負荷値)が、小さな値を持つことができる目標過負荷値(315)の近くに集束させるようにするため、サーバー(130)へのサービス要求(335)の速度を許容された速度(コントロール入力)に調整することができる。拒否速度は、対象となるシステム(例えばサーバー(130))に関する負荷レベルを反映することができるため、良好なフィードバック値となりうる。サーバー(130)への負荷が増加するにつれて、サーバー(130)における内部過負荷コントロール・スキーマは、より多くのサービス要求を拒絶する。従って、過負荷通知を受け取る速度も同様に増加する。そして、拒否の変化速度が、かかっている負荷の変化速度に近づくことができる。
【0058】
一般的に、センサー/フィルター(310)によって測定される過負荷通知は、明示的及び/又は暗黙的の何れかであってよい。幾つかの実施形態において、明示的な過負荷値は、例えば、503 Service Unavailableという応答を介したSIP要求拒否をうけとったことを表すものであってもよい。暗黙的な過負荷値としては、例えば、サービス要求に対する応答が欠失していることを表すものであってもよい。一実施形態において、暗黙的な過負荷基準は、サービスを要求している仕掛中の要求(例えば、応答を受け取ってない要求)の割合を追跡することによって実現することができる。もし、ある時間間隔内での未応答のサービス要求の割合が割合閾値以上である場合、過負荷基準を満たすことができる。また、暗黙的な検出は、例えば、サービス要求を送るたびにクライアント(120)がタイマーをスタートさせることによって実現することもできる。前記タイマーは、タイムアウトを経過する前にサービス要求に対する応答を受け取った場合には、キャンセルすることができる。幾つかの実施形態において、前記タイムアウト期間は、サーバー(130)での高負荷で予想される応答時間を少し超える程度に設定することができる。センター(310)は、過負荷がかかったサーバー(130)からの暗黙的及び/又は明示的な過負荷通知の速度を測定することができる。幾つかの実施形態において、測定された速度は、指数加重移動平均(EWMA)ローパスフィルターを介して平均化することができる。フィルター(310)は、前記測定値の推計学情報を平坦化することができ、そして、前記コントロールが過負荷通知の突発的なバーストによって作動することのないようにすることができる。EWMAフィルターは以下の通り記述することができる。
【数1】

(1)
ここで、Om(n)は、時間nで測定された過負荷値を表す。Oavg(n)は、時間nでの平均過負荷値を表す。重みwはローパス・フィルターの時間定数を表す。
【0059】
幾つかの実施形態において、センサー/フィルター(310)は、サービス要求の1以上の特定の分類に関する過負荷通知を測定することができる。例えば、センサー/フィルター(310)は、通常のサービス要求のみに関する過負荷値を決定することができる。あるいは、センサー/フィルター(310)は、所定の優先値未満の優先値を持つ全てのサービス要求に関する過負荷値を決定することができる(例えば、優先分類が10レベルであって、1〜6の間の優先レベルを有する全てのサービス要求)。別の実施形態又は補足的な実施形態では、センター/フィルター(310)は、1以上の過負荷値を決定し、コントローラ(320)に提供することができる。例えば、センサー/フィルター(310)は、通常のサービス要求及び優先度の高いサービス要求に第一過負荷値を提供することができ、そして再送信要求については第二過負荷値を提供することができる。
【0060】
幾つかの実施形態において、かけられた負荷の変化の効果が功を奏し、クライアント(120)にフィードバックされる過負荷通知速度に反映されるまでは、クライアント(120)は過負荷通知応答を幾つも受け取る可能性がある。従って、毎回の過負荷通知で提供される速度が変化した場合には、早まってかかっている負荷を変化させる可能性があり、これによってかかっている負荷を過剰に矯正したり及び/又は著しく変動させたりする可能性がある。幾つかの実施形態において、提供された負荷速度に対して1以上の更新がなされた後で、待機期間Twait(又は、ブラインド間隔期間)を導入することができ、該期間では過負荷通知はカウントしない。前記待機期間終了後は、過負荷通知を過負荷通知速度にカウントすることができる。
【0061】
コントロール・ユニット(320)は、設計された目標過負荷値の近くに平均過負荷値を維持するように、許容されたサービス要求伝送速度をサーバー(130)に対して適用することができる。従って、コントロールは、平均過負荷値が目標過負荷値を超えるとすぐに作動することができる。幾つかの実施形態において、コントロール・ユニット(320)は、AIMD(Additive Increase/Multiplicative Decrease)の原理に基づいてもよく、時間に対する許容された速度を更に増加させることができる。過負荷を検出すると、その後、コントロール・ユニット(320)は、特定の因子によって許容速度を倍数的に減少させることができる。AIMDコントロール・スキーマによって、安定且つ正当な稼動ポイントに収束させることができる。AIMDアルゴリズムを用いて、コントロール・ユニット(320)は、固定サイズのステップで直線的に許容速度を増加させて、余分な容量を探ることができる。そして、過負荷を検出した際には、許容速度を固定因子(例えば0.5)によって倍数的に減少させることができる。
【0062】
幾つかの実施形態において、コントロール・ユニット(320)は、過負荷値がすぐに目標過負荷値に収束するように許容速度を適用することができる。他の実施形態では、過負荷設定に素早く反応できるようにするため、許容速度の変化速度を、目標過負荷値に対する前記過負荷値の偏差に比例するようにすることができる。例えば、設定された目標速度に過負荷値が近い場合には、コントロール・ユニット(320)は、許容速度に対する変化を小さくすることができる。同様に、設定された目標過負荷値から更に過負荷値が離れるにつれて、コントロール・ユニット(320)は、許容速度への変化を大きくすることができる。該スキーマは、提供されたサービス要求伝送速度における急激な変化(増加及び/又は減少)に素早く反応することができる。
【0063】
幾つかの実施形態において、コントロール・ユニット(320)は、1以上の特定分類の提供されるサービス要求(325)に関する許容サービス要求伝送速度をサーバー(130)に対して適用することができる。例えば、コントロール・ユニット(320)は、優先サービス要求に関する許容伝送速度については変化しない状態のままにする一方で、通常のサービス要求に関する許容伝送速度については適用することができる。あるいは、コントロール・ユニット(320)は、所定の優先度未満の優先度を持つ全てのサービス要求(例えば、10段階の優先分類のなかで、優先度1〜6のサービス要求全て)に関して許容伝送速度を適用することができる。別の実施形態又は補足的な実施形態では、コントロール・ユニット(320)は、提供されたサービス要求(325)の1以上の分類に関して許容伝送速度を別々に適用することができる。例えば、第一種類のサービス要求に関する許容伝送速度は、センサー/フィルター(310)からの第一過負荷値に基づくことができ、第二種類のサービス要求に関する許容伝送速度は、センサー/フィルター(310)からの第二過負荷値に基づくことができる。
【0064】
アクチュエータ(330)は、コントローラ(320)からの出力に基づいて、サービス要求(335)の伝送速度を電子的に制限することができる。前記制限を実施するために、異なる機構を使用することができる。例えば:(1)パーセント拒否;(2)要求ギャッピング;及び/又は(3)リーキィ・バケット(leaky bucket)。割合拒否機構は、あるパーセンテージの提供された要求(325)を許容することができ、従って、提供された速度が変化するのに伴って許容速度を変化させることができる。コントローラ(320)は、許容サービス要求のパーセンテージを調整して、提供された速度を追跡することができる。もし、リーキィ・バケットを用いる場合、コントローラ(320)は、出力を更新する頻度をより少なくして、提供された速度を追跡することができる。これにより、フィードバック・コントロールを安定化させることを補助することができる。リーキィ・バケットと同様に、要求ギャッピングも、1つのトークンに関するバケットサイズを用いて動作することができる。補助的な実施形態において、アクチュエータ(330)は、入ってくる負荷(325)を一時的に保存するために1以上のバッファを含むことができる。
【0065】
また、補足的又は別の実施形態において、アクチュエータ(330)は、分類に基づいてサービス要求の伝送を制限することもできる。一実施形態において、オーバーロード・フレンドリー・再伝送(overload−friendly retransmissions)は、以前のサービス要求からの再伝送である1以上の提供されたサービス要求(325)の自動再伝送を電子的に落とすアクチュエータ(330)を含むことができる。オーバーロード・フレンドリー・再伝送は、過負荷のかかったサーバー(130)に対する集合速度の自動コントロールを提供できる点で有利であり、該サーバーは古い要求の再伝送と新たな要求とを含む。更に、オーバーロード・フレンドリー・再伝送は、通常の要求の伝送よりも、高い優先度要求の再伝送を優先させることができる点で有利である。一般に、アクチュエータ(330)は、提供されたサービス要求(325)に関する1以上の分類に基づいて、サービス要求の伝送について優先度を付けることができる。
【0066】
モデル・コントロール・ループ(300)の構成要素は図3では別々に図示されているが、他の構成も使用可能である。例えば、モデル・コントロール・ループ(300)の1以上の構成要素は、例えばコントローラ(280)等と同じユニット内に結合することができる。更に、クライアント(120)は、1以上の追加コントロール・ループ(300)を有することができる。ある場合には、追加コントロール・ループ(300)は、1以上の追加下流サーバーへのサービス要求伝送速度をコントロールするために使用することができる。補助的又は別の実施形態では、追加コントロール・ループ(300)は、同じサーバーへの異なる分類のサービスに関するサービス要求伝送速度をコントロールするために使用することができる。
【0067】
図4は、ウィンドウ化したタイム・インターバルを表す図である。幾つかの実施形態において、クライアント実施過負荷コントロール・スキーマはタイム・ドリブン(time driven)であってもよい。タイム・ドリブン・スキーマにおいて、過負荷値は、所定の回数(例えば、ti, ti+1, ti+2等)で測定することができ、及び/又は所定の期間(例えば、Tn-1, Tn, Tn+1)測定することができる。1以上のブラインド間隔時間(例えば、TBn-1, TBn, TBn+1等)を含むことができ、該間隔時間では、過負荷値を測定しない。幾つかの実施形態において、期間Tj及び/又はTBjを固定することができる。他の実施形態では、期間Tj及び/又はTBjは、変数であってもよい(例えば、既知のネットワーク遅延及び/又はシステム帯域等のシステム・パラメータに基づく)。
【0068】
図5は、クライアント(120)での、コントローラ(280)によって実行されるクライアント・ベース過負荷コントロールを描いたフローチャート(500)である。フローチャート(500)の要素は、図3の例示的なモデル・コントロール・ループ(300)を用いて記述される。クライアント・コントロールを介したサーバー過負荷制限としては、過負荷値(510)を決定すること(510)、過負荷値に基づいて伝送制限速度を決定すること(520)、伝送制限速度に基づいてサービス要求の伝送を制限すること(530)、及び/又は、任意で、新たな過負荷値を決定する前にブラインド間隔期間待機すること(540)が含まれる。幾つかの実施形態において、コントローラ(280)は、長さTのウィンドウ・タイム・インターバルに関するフローチャート(500)中に描かれたアルゴリズムを実行することができる。例えば、もし、長さTの間隔を1秒に設定した場合、コントローラ(280)は、フローチャート(500)の要素を1秒ごとに実行する。補助的又は別の実施形態では、コントローラ(280)は、イベンド・ドリブン・ベースでフローチャート(500)を実行することができる。例えば、フローチャート(500)が最後に実行されてから受け取り、そして入ってくる要求(325)の数が、値Nを超えた場合に、コントローラ(280)は、フローチャート(500)を実行することができる。フローチャート(500)の要素は、クライアント(120)のプロトコル・スタック(210−270)内の1以上のプロトコル又はプロセスの間別々に実行することができるし、あるいは同時に実行することもできる。
【0069】
過負荷値の決定(510)は、センサー/フィルター(310)が行うことができる。期間nの間の過負荷値の決定(510)は、On-avgで表すことができるが、以前にサーバー(130)に伝送された少なくとも2以上の要求が過負荷基準を満たしているかどうかを決定することを含むことができる。過負荷値On-avgは、例えばコンピュータ・メモリ・モジュール(290)中に保存することができる。幾つかの実施形態において、過負荷値は、過負荷基準を満たす要求の平均数であってもよい。例えば以下の通り。
【数2】

(2)
一般的に、過負荷値は、1以上の以前の期間からの過負荷測定数に基づく任意の関数f(例えば、滑らかな関数)であってもよい。例えば、
【数3】

(3)
【0070】
幾つかの実施形態によると、過負荷基準は、サーバー(130)からの明示的な拒否メッセージ(例えば、On-meashured=Σrejections)を受け取ることを含むことができる。補足的又は別の実施形態では、過負荷基準は、例えば以下のタイムアウト等の暗黙的な値に基づいても良い。
【数4】

(4)
ここでSnは、1以上の現在の又は以前の期間(例えば、期間n)の間に送られた要求の数を表し、また、
【数5】

(5)
ここでtsiは、i番目要求が送られた時間を表すことができる。triはi番目要求に対する要求を受け取った時間を表すことができる。tmeasuredは、過負荷測定の時間を表すことができる。Dは遅延閾値を表すことができる。前記遅延閾値Dは静的(例えば、予め知られたサーバー(130)遅延に基づく)及び/又は動的(例えば、クライアント(120)による設定変化)であってもよい。幾つかの実施形態において、時間nに関する動的遅延閾値Dnは、
【数6】

である。
ここで、Rnは平均応答時間を表すことができ、
【数7】

は、安全因子である(例えば≧1)。
平均応答時間は、
【数8】

であってもよい。ここで、αは平均因子を表すことができ、dは遅延測定を表すことができる。
【0071】
更に他の補助的又は別の実施形態では、過負荷基準は暗黙的な値に基づくことができ、例えば、以下のような故障応答(out of order)に基づくことができる。
【数9】

(6)
ここで、Snは1以上の期間(例えば、期間n)の間に送られた要求の数を表すことができる。そして、
【数10】

(7)
である。ここで、tsiは、i番目の要求が送られた時間を表すことができる。triは、i番目の要求に対する応答を受け取った時間を表すことができる。そして、fは|tsj - tsi| 及び/又は |j-i|の関数を表すことができる。一般的に、過負荷値は上記(2)〜(7)の1以上に基づくことができる。
【0072】
過負荷値に基づいて伝送制限速度を決定すること(520)は、コントロール・ユニット(320)によって実行するこができる。図6は、過負荷値に基づいて伝送制限速度を決定すること(520)を表すフローチャート(600)である。伝送制限速度を決定することには、過負荷条件が存在するかどうかを決定すること(610)が含まれる。もし、過負荷条件が存在する場合には、伝送制限速度はステップ・ダウンすることができる(620)。もし、過負荷条件が存在しない場合には、伝送制限速度はステップ・アップ(630)することができる。過負荷条件が存在するかどうかを決定すること(610)は、過負荷値と目標過負荷値(315)を比較することを含むことができ、該目標過負荷値はOtargetで表すことができる。
【0073】
幾つかの実施形態によれば、伝送制限速度は、期間n中に対する
【数11】

で表現される。そして、
【数12】

に従ってステップ・ダウン(620)される。ここで、Pn+1は以下の通り、伝送速度のパーセンテージである:
【数13】

, (8)
ここで、GSDは、コントローラのステップ・ダウン・ゲインを表す。別の又は補助的な実施形態において、伝送速度制限は以下に従ってステップ・ダウンすること(620)ができる:
【数14】

【0074】
過負荷値が目標過負荷値を下回っている場合には、クライアント(120)は、ステップ・アップ・フェーズ(630)に入ることができる。前記ステップ・アップ・フェーズ(630)は、以下の条件の場合に継続される:(1)過負荷値が目標過負荷値を下回るとき;及び、(2)到達した過負荷(λ)(325)が、コントローラ(320)が許容した速度(λ*)を上回る場合。幾つかの実施形態において、ステップ・アップ・フェーズは以下の2つのサブ・フェーズに分けることができる:「過負荷リカバリ」及び「過負荷防止」。過負荷リカバリの最中は、コントローラ(320)は、過負荷イベントの前に平均許容速度まで回復させようとすることができる。過負荷防止の最中は、コントローラ(320)は、許容速度をゆっくりと増加させることができる。補助的又は別の実施形態では、到達した過負荷(λ)(325)がコントローラ(320)が許容した速度(λ*)を下回る場合に、コントローラ(320)での許容速度(λ*)を変化しないままにすることができる。
【0075】
伝送制限速度は以下に従ってステップ・アップすることができる(630):
【数15】

ここでstep_sizeは固定することができる。あるいは、step_sizeは以下に従って決定することができる:
【数16】

ここでGSUはステップ・アップ・ゲインを表し、
【数17】

(9)
ここで、
【数18】

は、クライアント(120)がサーバー(130)と共に有する最大シェアに基づくことができる値であって、予め設計された巨大な値を表すことができる。
そして、
【数19】

は、過負荷に入る前又はステップ・ダウン・フェーズに入る前に提供される平均過負荷(325)を表すことができる。
【数20】

であるときには、「過負荷リカバリ」と呼ぶことができるが、クライアント(120)は、過負荷状態の前の平均的な提供された負荷にリカバリすることを試みることができる。
【数21】

であるときには、「過負荷回避」と呼ぶことができるが、クライアント(120)は、将来的な過負荷を回避するためにサーバー(130)を探索することを試みることができる。別の実施形態では、
【数22】

は、時間nでの入ってくる要求(325)の速度を表すことができる。前記step_size値は、step_sizemaxを上限及び/又はstep_sizeminを下限値として境界値を設けることができる。ステップ・アップ・ゲインGSUは固定しても、変動してもよい。例えば、
【数23】

の場合には、より保守的にするために、GSUにより低いゲインを割り当てることができる。さらに別の又は補助的な実施形態では、step_sizeは以下に従って決定することができる:
【数24】

【0076】
調査フェーズ(即ち、ステップ・アップ・フェーズ)中、もし現在提供されている負荷(325)が最大速度ratemaxを超え、且つ最大速度ratemax
【数25】

を下回る場合には、前記最大速度ratemaxは、
【数26】

に設定される。前記調査フェーズ中、もし、センサー/フィルター(310)からの平均過負荷値が目標過負荷値(315)を超える場合には、クライアント(120)は、ステップ・ダウン・フェーズに(再度)突入し、現在の伝送制限速度を、最大速度ratemaxに関する現在の値として記録することができる。例えば、クライアント(120)は、現在の伝送制限速度を、
【数27】

に関する現在の値として記録することができる。
【0077】
伝送制限速度である
【数28】

は、アクチュエータ(330)へ送られる。アクチュエータ(330)は、入ってきたサービス要求(325)を前記伝送制限速度である
【数29】

によって(例えば前記伝送速度以下に)制限された速度で伝送(335)することができる。
【0078】
新たな過負荷値を決定する(510)前のブラインド間隔期間待機するステップ(540)は、ブラインド間隔期間Tblindに基づくことができ、該期間は静的(例えば、サーバー(130)からの既知の平均応答時間に基づく)及び/又は動的(例えば、クライアント(120)による設定変化)であっても良い。幾つかの実施形態において、ブラインド間隔は、下記のとおり平均要求・応答遅延を動的に測定することに基づくことができる:
【数30】

(10)
ここで、Rnは平均応答時間を表す。αは平均因子であり、dは遅延測定である。時間n+1におけるブラインド時間間隔Tblindは、下記の通り設定することができる:
【数31】

(11)
ここで、fblindは、1以上の安全因子(safety factor)を表すことができる。Tblindを動的に設定する別の方法として、連続した番号Ninit、及び速度を減少させた後の第一リクエストを送る時間を保存すること、並びに該ポイントでTblindを開始することを含めることができる。Tblindは、Ninitよりも大きい連続番号Nを有する要求に関する応答を受け取ったあとで終了することができる。
【0079】
新たな要求を拒絶することなく所定量の時間を維持し、過負荷値が目標過負荷値を下回った状態を維持した場合には、クライアント(120)は過負荷状態を脱することができ、以下のように設定することができる:
【数32】

【0080】
III.計算の結果(Computational Results)
量的な調査では、クライアント実施過負荷コントロールが、異なる過負荷プロファイル下で、ターゲット・サーバーの容量及び負荷分散をどのように適切に適用するかを表す。以下のシミュレーションでは、パケットレベルのシミュレーターOPNETを使用しており、該OPNETは、SIPモジュール、並びにSIPサーバー内の内外過負荷コントロールを実施するためのモジュールと共に拡張されている。SIPモデルはSIP RFC 3261を実装する。ネットワーク・トポロジーには、ユーザー・エージェント(UA)が含まれており、該エージェントはエッジ・プロキシに接続されており、該プロキシはUAの要求をコア・プロキシに送る。各エッジ・プロキシは、10のUAクライアント及び10のUAサーバーに接続されている。エッジ・プロキシ及びコア・プロキシの数は、異なるシミュレーション・シナリオ間で変化する。各UAクライアントは、INVITEトランザクションで表されるコールを生成し、続いてBYEトランザクションで表されるコールを生成する。
【0081】
図7は、セッション確立に関するシミュレートされたモデルSIPメッセージ・フローを表したハシゴ図である。UAクライアントが生成したコールは、ポワゾン到着モデルに従い、目的地UAサーバーは、ネットワーク中の利用可能な全てのUAサーバーからランダムに選択される。全てのコア・プロキシが過負荷状態であるときには、エッジ・プロキシは要求を拒絶することができる。コア・プロキシは、目的地UAのエッジ・プロキシに対する要求を送ることができる。プロキシは、到着するSIPメッセージを保持する有限のキューとして表現することができ、一定の速度で該メッセージを提供(例えば、再伝送)することができる。こうしたサービス速度は、プロキシのメッセージ処理容量を規定する。このシミュレーションにおいては、エッジ・プロキシは無限の容量を有すると仮定されており、一方コア・プロキシは有限の容量を有するように設定されている。こうした仮定によって、コア・プロキシにおける過負荷の振る舞いに関する検証を行うことが可能となる。また、該仮定は、複数のエッジ・プロキシからの集中負荷をコア・プロキシが処理するものとして妥当な仮定である。このシミュレーションにおける全てのSIPメッセージはUDPを介して伝送され、従って、SIPによって再伝送を介してメッセージの信頼性が保障される。表1は、シミュレーションの為に使用される設定を表にしたものである(Ahmed Abdelal, Wassim Matragi, "Signal-Based Overload Control for SIP Servers", In Proceedings of IEEE Consumer Communications and Networking Conference (CCNC), January 2010を参照されたい。該文献全体を本明細書中に組み込む)。
【表1】

【0082】
SIPシミュレーションにおいて、フル・コールすると、7つのメッセージの負荷がプロキシにかかる事になる(5つのメッセージはINVITEトランザクションであり、2つのメッセージはBYEトランザクションである)。500 messages/secの容量で処理するコア・プロキシメッセージの場合、各コア・プロキシの容量は約72 calls/secである。以下の結果の中で、プロキシ/ネットワーク・スループットは、パフォーマンス・メトリックとして使用することができる。スループットは、成功したコールの速度を表す。もし、UAクライアントが10秒未満内に200−OKを受け取った場合コールが成功したものと定義する。そして、UAサーバーはINTITE−ACKを受け取る。コール・セットアップ遅延は、最初のINVITE要求を送ってから200−OKを受け取るまでの間の時間で定義される。全てのシミュレーションは、システムが一貫した動作に達することを保証するのに充分長い時間実行される。
【0083】
図8は、過負荷スキーマなし(810)、キュー・ベース実行を利用したサーバー・ベースの内部過負荷スキーマ(820)、及びクライアント・ベース過負荷スキーマ(830)に関しての与えられた負荷に対するスループットを表すシミュレーションの結果の二次元プロット図(800)である。過負荷コントロールがない状態では、与えられた負荷がプロキシの集計容量である約142 calls/secを超えると、スループットが急速にゼロまで低下する。これは、キューのオーバー・フローによりSIPメッセージが落ち、それに続いて上流クライアントからのSIP要求再伝送が行われることが原因となって生じる。内部過負荷コントロールは、過負荷コントロールが無い場合と比べると多少良好なスループットを達成できている。この理由は、拒否する作業量が、受け入れる場合と比べて労力を要さないからである。クライアント・ベースの過負荷コントロールでは、約142 Calls/Secのスループットを達成できている。
【0084】
図9は、本発明の例示的な実施形態に従って、集中したサーバー過負荷を検出及び制限するためのネットワーク(900)を概念的に表したものである。ネットワーク(900)(例えば、図1の伝送媒体110)は、ソース(902A,902B〜902N)(集合的にソース902)を含む。幾つかの例では、遠距離通信ネットワークに関して、通信プロトコルのセッション要求がネットワーク(900)に入ってソース(902)を通過する(例えば、図1を参照すると、コールするクライアント(120)はセッション要求を接続部(115)を経由してソース(902)に伝送する)。例えば、通信プロトコルは、セッション確立プロトコル (SIP),ハイパーテキスト・ドランスファー・プロトコル (HTTP)、ストリーム制御転送プロトコル (SCTP)、トランスミッション・コントロール・プロトコル (TCP)、及び任意の他の種類のセッション/コネクションベースのプロトコル(例えば、要求−応答方法論に従ったプロトコル)であってよい。データは、ソース(902)から下流サーバー(904)(例えば図1のサーバー(130))へ送られる。また、ネットワークは、ソース(902A及び902B)並びに下流サーバー(904)に接続されたサーバー・ノード(906)を含む。サーバー・ノード(906)は、プロセッサ(908)、コンピューター・メモリ・モジュール(910)(例えばデータベース)を含む。コンピューテーション・ノード(912)は、サーバー・ノード(906)を接続されている。コンピューテーション・ノード(912)は、コントロール・データベース(914)を含む。
【0085】
ネットワーク(900)は、1つのサーバー・ノード(906)及び1つの下流サーバー(904)だけを示してはいるが、ネットワーク(900)は、任意の数のサーバー・ノード(例えば、ソース(902)と下流サーバー(904)との間の中継ノード)及び/又は下流サーバー(904)を含むように設計することができる。中継ノードは、ソース(例えばソース(902))でもなく、下流サーバー(例えば下流サーバー(904))でもない任意のノードである。ソース(902)からのデータは、下流サーバー(904)を介してネットワークを出発する(例えば、ソース(902)からのセッション要求が下流サーバー(904)を介してネットワーク(900)を出発する)。コンピューテーション・ノード(912)は、該ノードが(例えばサーバー・ノード(906)を介して)受け取るデータを処理することができる。幾つかの実施形態において、コントロール・データベース(914)は、図13−14Bで更に詳述するが、1以上の動作位置(例えば、サーバー・ノード(906)等の中継ノード)にコントロール・パラメータ(即ち、コントロール情報)を送るためのコンピューテーション・ノード(912)によって使用される中央データベースである。
【0086】
図10は、本発明の例示的な実施形態に従って、ネットワーク中の集中したサーバー過負荷を保存及び検出するためのブルーム・フィルター(1000)を概念的に表したものである。ブルーム・フィルター(1000)は、ストレージ・デバイス(例えば、コンピュータ・メモリ・モジュール(910)及び/又はコントロール・データベース(914))によって実装され、ここで、キー(例えば、x1及びx2)は、カウンター配列(1004)中のカウンター(1002A〜1002N)(集合的にカウンター(1002))に、1以上のハッシュ関数(例えば、ハッシュ関数 Hash1〜Hash3)によって配置される。幾つかの実施形態において、カウンター配列(1004)は、0又は1の何れかをセットできるカウンター・ビット配列である(ここで値0は、ブルーム・フィルター中の非メンバーシップを表し、値1はブルーム・フィルター中のメンバーシップを表す)。幾つかの実施形態において、ハッシュ関数及びカウンター配列(1004)は、カウンティング・ブルーム・フィルター(又は、マルチ・レベル・ブルーム・フィルター(MLBF))であり、ここでカウンター配列(1004)はカウンティング整数の配列である。例えば、MLBFは複数閾値を有し、該閾値は異なるコール又はセッションに関連する。高優先度のコール又はセッションについては、高い閾値を使用し、一方で、低優先度のコール又はセッションについては、低い閾値を使用する。値がブルーム・フィルター(1000)に挿入されるたびに、ハッシュ関数によって決定されるカウンティング整数が増加する(例えば、0又は1のいずれかを設定するのではなく、挿入の度に0〜1〜2等)。
【0087】
ハッシュ関数は、任意のデータ・ストリームを入力(例えば、下流サーバー(904)等の下流サーバーの名前)として受け取り、整数を出力として戻す関数である。リターンされた整数は、カウンター配列(1004)のカウンター(1002)を同定するのに使用される(例えば、カウンター配列(1004)中の全てのカウンター(1002)が0に設定される)。従って、ブルーム・フィルター(1000)は、複数のハッシュ関数(例えば、ハッシュ関数Hash1〜Hash3)を用いて、単一のキーについて、カウンター配列(1004)内の複数のカウンター(1002)にマッピングを行う。該実施形態において、2つの操作をブルーム・フィルター(1000)上で実行することができる:INSERT(key) (例えば、INSERT (x1)(1010)及び INSERT (x2)(1012)) 並びに TEST(key) (例えば、 TEST(x1)(1014))。ブルーム・フィルター(1000)の一実施形態の機能性については、以降の図11を参照しながら述べることにする。
【0088】
ブルーム・フィルター(1000)は、通信プロトコルに関する複数の統計情報についての追跡を継続するために使用することができる。例えば、もしネットワーク(例えばネットワーク(900))がSIPを使用している場合、ブルーム・フィルター(1000)は、以下に関する数を保存する:下流サーバー(904)に関するセッション拒否;ソース(902)から下流サーバー(904)への失敗した接続要求;下流サーバー(904)からの過負荷通知;及び、任意で他の有用な通信プロトコル統計情報。ブルーム・フィルターは、分散させるやり方で、情報(例えば、セッション拒否統計情報等のフィードバック・メッセージ統計情報、及び/又は下流サーバー(904)からの他の過負荷フィードバック)を保存することを目的とする計算処理的及び空間的に有効な構造を提供する。有利な点として、ブルーム・フィルターは、一定の挿入時間、一定のテスト時間、及びフォールス・ポジティブに関する有限の確率(例えば、ブルーム・フィルターがキーを表す回数が、キーが設定されていなくてもブルーム・フィルター中に存在するなど)を有している。更に言えば、ブルーム・リルターは、保存目的用に極端にコンパクトであり、多数のブルーム・フィルターを追加して集合させることができる。例えば、複数のカウンター配列を(例えばネットワーク中(900)で)使用することができ、ここで、複数のカウンター配列それぞれは、異なるサーバー・ノードに保存することができる(例えば、ネットワーク(900)が複数のサーバー・ノード(912)を備える実施形態、又は中継ノード(906)がカウンティング・ブルーム・フィルターを保存するためのサーバー・ノードとして設計される実施形態など)。中央サーバー・ノード(例えば、コンピューテーション・ノード(912))は、複数のカウンター配列を集合させる。そして、異なるサーバー・ノード間での複数のカウンター配列に関連する各下流サーバー(例えば下流サーバー(904))からフィードバック・メッセージを受け取った数を計算する。
【0089】
図11は、本発明の例示的な実施形態に従って、ネットワーク中の集中したサーバー過負荷を検出するための方法(1100)を示したフローチャート図である。
ステップ(1102)では、サーバー・ノード(906)は、下流サーバー(例えば下流サーバー(904))からフィードバック・メッセージを受け取る。フィードバック・メッセージは、通信プロトコルの統計情報(例えば下流サーバー(904)からのSIPセッション拒否)を含む。ステップ(1104)では、サーバー・ノード(906)は、フィードバック・メッセージ中に含まれる情報をもとに(例えば下流サーバーの名前をもとに)1以上のハッシュ関数(例えば、ハッシュ関数Hash1〜Hash3)を用いて、カウンター配列(例えば、カウンター配列(1004)であって、コンピューター・メモリ・モジュール(910)中に保存できるもの)からの1以上のカウンターのうちどれが下流サーバーに関連しているかを決定する。1以上のカウンターは、統計情報(例えば、下流サーバー(904)から受け取ったセッション拒否の数)を含む下流サーバーからのフィードバックの数に対応する数を保存することができる。
【0090】
ステップ(1106)では、サーバー・ノード(906)は、統計情報を含むフィードバック・メッセージに応答して、1以上のカウンターを増加させる。ステップ(1108)では、サーバー・ノード(906)は、1以上のハッシュ関数を用いて、1以上のカウンター内に保存される数の値を決定する。ステップ(1110)では、サーバー・ノード(906)は、値が所定の基準を満たしているかどうかに基づいて、下流サーバーに関するネットワーク(例えばネットワーク(900)中の過負荷エピソードを前記値が表しているかどうかを決定する。もし、前記値が過負荷エピソードを表していない場合には、前記方法はステップ(1102)に戻る。もし、前記値が過負荷エピソードを表す場合には、前記方法(1100)はステップ(1112)に進む。該ステップでは、サーバー・ノード(906)(及び/又はコンピューテーション・ノード(912))は、過負荷エピソードの原因となっている1以上のソース(例えばソース(902)からの1以上のソース)を同定する。ここで、統計情報を含むフィードバック・メッセージを下流サーバーに伝送させている各ソースは、下流サーバーへの伝送を開始する。ステップ(1114)では、サーバー・ノード(906)(及び/又はコンピューテーション・ノード(912))は、前記値に基づいてコントロール動作を実行するための1以上のコントロール・パラメータを決定する。
【0091】
ステップ(1104)に関して言うと、本発明のシステム及び方法は、下流サーバー(例えば下流サーバー(904))に関するネットワーク中の各サーバー・ノード(例えば、ネットワーク(900)中のサーバー・ノード(906))において通信プロトコルの統計情報(例えばセッション拒否)の追跡を継続する。一実施形態において、各サーバー・ノードは、カウンティング・ブルーム・フィルターを使用し、サーバー・ノード基盤(basis)ごとに、サーバー・ノード上の対象となる通信プロトコルの統計情報に関する計算を管理する。通信プロトコル統計情報を含むフィードバック・メッセージをサーバー・ノードが受け取るたびに、サーバー・ノードは、該サーバー・ノードに対応するカウンティング・ブルーム・フィルターと、増加され且つ組み合わされる目的キーに関するカウンターとを更新する。
【0092】
通信プロトコル統計情報の受け取りについては、下流サーバーからサーバー・ノードへ伝送されるフィードバック・メッセージとして上述したが、サーバー・ノードは、複数の方法で観察可能なフィードバック・メッセージ(例えばセッション拒否通知)を観察することができる。例えば、サーバー・ノードは、明示的にフィードバック・メッセージを観察することができる(例えば、セッション・シグナリング・メッセージ等のフィードバック・メッセージの経路中にあるサーバー・ノード(906)等のネットワーク要素上への実装を介して)。サーバー・ノードは、暗黙的にフィードバック・メッセージを観察することができる(例えば、VoIP/IMSネットワーク内のコール・ディテール・レコード(CDR:Call Detail Record)等のサーバー・ログを調査することによるなど)。
【0093】
ブルーム・フィルターにキーを挿入(INSERT)することを目的として、N個のハッシュ関数の各ハッシュ関数をキーに適用することにより、N個のハッシュ値を作成する。その後、N個のハッシュ値に相当するビット・ベクトル中のN個のポジションを増加させる(例えば、1に設定し、1ずつ増加させる等)。図9及び10を参照すると、サーバー・ノード(906)は、3つのハッシュ関数Hash1〜Hash3を用いて、カウンター配列(1004)からの1以上のカウンター(1002)のうちどれが下流サーバーと関連しているかについて決定を行っている。ここで、キーは、下流サーバー(904)の名前等、下流サーバーに関する識別子である。例えば、フィードバック・メッセージが下流サーバー(904)から送られたことを表すデータをサーバー・ノード(906)が保存する必要がある場合に、サーバー・ノード(906)は、INSERT(x1)(1010)を実行して、新たな値をブルーム・フィルター(1000)内に挿入する。ここで、x1は、下流サーバー(906)の名前である。図10に示すように、INSERT(x1)(1010)は、3つのハッシュ関数Hash1〜Hash3を使用して、x1(下流サーバー(906)の名称)に関連するカウンター配列内(1004)のポジション(1010A、1010B、及び1010C)を特定している。例えば、もし、フィードバック・バックメッセージが異なる下流サーバー(下流サーバー(904)ではない)から送られたことを表すデータを保存する必要がサーバー・ノード(906)にある場合には、サーバー・ノード(906)は、INSERT(x2)(1012)を実行して、新たな値をブルーム・フィルター(1000)に挿入することができる。ここでx2は前記異なる下流サーバーの名前である。図10に示すように、INSERT(xx)(1012)は、3つのハッシュ関数Hash1〜Hash3を使用して、x2(前記異なる下流サーバーの名前)に関連するカウンター配列(1004)内のポジション(1012A、1012B及び1012C)を同定する。
【0094】
ステップ(1106)に関して述べると、特定の下流サーバーから受け取った通信プロトコルの統計情報(例えば、統計情報を含むフィードバック・メッセージ)の数に関するカウントを増加させる(例えば0から1へ、1から2へ等)ように、1以上のカウンター(1002)を増加させる。幾つかの実施形態において、通信プロトコルの統計情報の数に基づいて、サーバー・ノード(906)はカウンター(1012A,1012B,及び1012C)を直線的に増加させる(例えば、サーバー・ノード(906)は、各通信プロトコルの統計情報に対して、整数xだけ増加させることができる)。例えば、図10に示すように、サーバー・ノード(906)は、カウンター(1012A,1012B,及び1012C)を1だけ(即ち0から1へ)増加させる。幾つかの実施形態において、サーバー・ノード(906)は、1を超える数(例えば、2、3等)だけ、1以上のカウンターを増加させることもできる。1を超える数については、以下のものに基づいて決定することができる:サーバー・ノード(906)が監視している統計情報;ある期間下流サーバー(904)から受け取る統計情報(例えば、5分間の時間枠で受け取った統計情報);ソースから下流サーバーへの伝送の種類(例えば、ソースが行うコールの種類に基づく)(ここで、高優先度のコール/セッションは、通常のコール/セッションよりも重み付けを低くすることができ、従って、高優先度のコール/セッションは成功率が高くなる);及び/又は、複数の期間に下流サーバー(904)から受け取る統計情報(例えば、所定の5分の時間枠内で、3日間連続で受け取る統計情報)。幾つかの実施形態において、サーバー・ノード(906)は、非直線的な関数に基づいて、カウンター(1012A,1012B,及び1012C)を増加させる(例えば、増加値xは、SIP 503 (Service Unavailable)応答におけるRetry−Afterパラメーター、コール/拒否応答中に戻される過負荷レベルの値に基づくことができる)。
【0095】
ステップ(1108)に関して述べると、サーバー・ノード(906)は、ネットワーク(例えば図9のネットワーク(900))中の1以上の下流サーバーから受け取った下流サーバーに関する通信プロトコル統計情報の数を決定する。一実施形態において、サーバー・ノードは、ブルーム・フィルター中に保存する通信プロトコル統計情報のカウント(又は計算)に基づいて、各下流サーバーに関する受け取った通信プロトコル統計情報の数を決定する。ブルーム・フィルター中にキーが設定されているかどうかをテスト(TEST)するために、N個のハッシュ関数を用いた挿入の間に、キーに関してN個のハッシュ値を計算する。ベクトル中の対応するN個のビット・ポジション全てが設定されている場合には、キーはブルーム・フィルター中に存在するといえる。例えば、図10を参照すると、TEST(x1)(1014)操作は、所与のキーx1が、ブルーム・フィルター(1000)に関するカウンター配列(1004)に以前挿入されているかどうかを見るためにテストする。ハッシュ関数Hash1〜Hash3は、カウンター(1014A〜1014C)をそれぞれ同定する。カウンター(1014A〜1014C)は、INSERT(x1)(1010)の際に同定された同一のカウンターに対応している。なぜなら、ハッシュ関数は、特定のキー(この場合はx1)に対しては同じ値を生成するからである。従って、ブルーム・フィルター(1000)は、各カウンター(1014A〜1014C)における値が1に設定されていることを決定し、キーx1がブルーム・フィルター(1000)に存在し、1の値を持っていることを表す(例えば、カウンティング・ブルーム・フィルター(1000)に関しては、キーx1はブルーム・フィルター(1000)に一度挿入され、通信プロトコル統計情報がキーx1に関して一度観察されたことを示す)。例えば、もし、x1が15回挿入された場合には、カウンター(1014A〜1014C)は「1」の代わりに「15」になるであろう。
【0096】
ステップ(1110)に関して述べると、サーバー・ノード(906)による所定の基準は、例えば、閾値(例えば、「25」というカウント値)であってもよい。そして、過負荷エピソードがあることを決定するこが、値が閾値を超えることを決定することを含む。幾つかの実施形態において、所定の基準はヒステレシスを用いて掲載される(例えば、現在の値と以前の値の履歴との両方に基づいて)。例えば、コントロール理論において、ヒステレシスは、幾つかの目標値(例えばX)にシステムの出力を維持するために使用することができる。以下のように2つの閾値を定義することができる:(1)低い方の閾値をX−Δ、及び(2)高いほうの閾値をX+Δ。この場合、コントロールは、システムの状態が連続する数のサンプルに関して、高いほうの閾値(即ち、X+Δ)を超えたときに可能となる。一方で、システムの状態が、連続する数のサンプルに関して、低い方の閾値(即ち、X−Δ)を下回ったときには不能になる。こうしたことにより、オン・オフ状態をバタバタと切り替わることを防止できる点で有利である。
【0097】
例えば、ステップ(1110)に関して述べると、サーバー・ノード(906)による所定の基準は、例えば、低い方の閾値及び高い方の閾値によって定義される閾値であってもよい(例えば、カウント値「23」と「25」)。そして、過負荷エピソードが存在することを決定することには、値が閾値を超えることを決定することが含まれる。任意の時間のポイントにおいて、システム状態が高い方と低い方の閾値の間にある場合には、システムは、以前の値の履歴を見ることなく過負荷エピソード(例えばコントロール状態;オン/オフ)があるかどうかの決定をすることができない。
【0098】
幾つかの実施形態において、ブルーム・フィルターは、サーバー・ノード・基盤ごとに管理される(例えば、サーバー・ノードごとに1つのブルーム・フィルター)。各ブルーム・フィルターに関するカウンターは、上述したように各サーバー・ノードにおいて、及び/又は集合レベルで集計される。例えば、ブルーム・フィルターは、周期的に集計することができ(例えば、コンピューテーション・ノード(912)が30秒ごとに1度)、広範な範囲(例えば、サーバー・ノード基盤ごとではなく、サーバー・ノード・ワイド又はネットワーク・ワイド)にわたる通信プロトコル統計情報を計算することができる(例えば、セッション拒否分散カウント)。幾つかの実施形態において、サーバー・ノード(906)及び/又はコンピューテーション・ノード(912)は、統計的な手法を用いて過負荷エピソードを検出することができる。例えば、ホルト・ウィンターズ法を使用することができる。ホルト・ウィンターズ法は、タイム・シリーズの複数の指数加重移動平均(multiple exponentially weighted moving averages)を利用する例外検出アルゴリズムである。ホルト・ウィンターズ法は、例えば、データ・シリーズにおいて、単一のシーズン・バリエーション(single seasonal variation)(例えば、遠距離通信ネットワークにおいて典型的なトラフィック量における日中のバリエーション(例えば、毎日発生する変動))を組み込むことができる。ホルト・ウィンターズ法は、データ・シリーズの平均を追跡するために、そして、許容可能な値範囲、シーズン・バリエーションを組み込む所与のユーザー特定モデルを予想するために使用することができる。もし、データ値が予想された許容値の範囲外になった場合には、例外(anomaly)が宣言される。
【0099】
更にステップ(1110)に関して述べると、一旦過負荷エピソードが特定の下流サーバーに関して検出されると、適切な情報がステップ(1112)の同定フェーズに渡される。こうした情報としては、例えば、ネットワーク中に過負荷エピソードが存在することを表すものであったり、過負荷のかかった下流サーバーのカウンター(例えば、ビット又は整数)がマークされたブルーム・フィルターを含むことができる。幾つかの例において、同定フェーズに渡されたブルーム・フィルターは、通信プロトコル統計情報の追跡を継続するために使用されるブルーム・フィルターと同じであってもよい。
【0100】
更にステップ(1110)に関して述べると、例えば、通信帯域だけでなくコンピューテーションの観点から効果的な態様で検出を行うことが有利である。ブルーム・フィルターの使用によって、検出を行うための極端に効果的な方法が提供されるという点で有利である。図12Aは、本発明の例示的な実施形態に従って、ネットワーク中の集中したサーバー過負荷を検出するためのカウンティング・ブルーム・フィルター(例えば特定のサーバー・ノードに関するブルーム・フィルター)に関するチャート(1200)を概念的に示したものである。チャート(1200)は、特定のカウンターに関するカウントを表す縦軸に沿った値(1202)(例えば、図10のカウンター配列(1004)のカウンターに関するもの)を含む。また、チャート(1200)は、カウンター配列内の各カウンタのポジションを表す横軸に沿ったカウンター・インデックス(1204)(例えば、第一カウンター、第二カウンター等)を含む。また、チャート(1200)は、特定のカウンター・インデックス(1204)に関する値(1202)を表すグラフ化された線(1206)を含む。チャート(1200)は、ブルーム・フィルター中に保存された情報を視覚的に表しており、集中したサーバー過負荷を検出するのに使用される。例えば、ピーク(1208)は、インデックス部位が19であるカウンターに関する値(約320)を示している。ブルーム・フィルターは、カウンター・インデックスにおける情報を特定のキー値(例えば下流サーバー名称)に割り当てている。例えば、インデックス部位19に割り当てられた下流サーバーは、値320と関連付けられている(例えば、チャート(1200)に関連付けられたブルーム・フィルターを保存するデバイス(例えば、サーバー・ノード(906))へ下流サーバーから送られた320のセッション拒否が存在する)。
【0101】
図12Bは、本発明の例示的な実施形態に従って、ネットワーク中の集中したサーバー過負荷を検出するための、集合カウンティング・ブルーム・フィルター(例えば、図12Aに示したもの等の複数のサーバー・ノードに広がる複数のブルーム・フィルターの集計値を表すブルーム・フィルター)に関するチャート(1230)を概念的に表したものである。チャート(1230)は、複数のブルーム・フィルターにまたがる特定のカウンターに関するカウントを表す縦軸に沿った値(1232)を含む(例えば、特定のカウンター・インデックスに関する各カウンター配列のカウンター値の合計)。また、チャート(1230)は、複数の集合ブルーム・フィルター内の各カウンターのポジションを表す横軸に沿ったブルーム・フィルター・インデックス(1234)を含む(例えば、各ブルーム・フィルターに関する第一カウンター、第二カウンター等)。また、チャート(1230)は、特定のブルーム・フィルター・インデックス(1234)に関する値(1232)を表示するグラフ化された線(1236)を含む。チャート(1230)は、複数の集合ブルーム・フィルターにまたがって保存される情報を視覚的に表しており、集中しているサーバー過負荷を検出するために使用される。 例えば、ピーク(1238)は、ネットワークのブルームフィルター全てを一旦集合させると、図12Aのインデックス部位19でのカウンターに関する値(約320)が、約15100まで上昇することを示している。ノード(例えばコンピューテーション・ノード(912))は、集合ブルーム・フィルターに関するカウンター・インデックスにおける情報を特定のキー値(例えばサーバー名称)に割り当てる。例えば、インデックス部位19に割り当てられた下流サーバーは、値15100に関連付けられる(例えば、チャート(1230)において値を集合させたブルーム・フィルターが保存されているデバイスへ下流サーバーから伝送された15100のセッション拒否が存在する)。
【0102】
図12Cは、本発明の例示的な実施形態に従って、ネットワーク中の集中したサーバー過負荷を検出するための集合させたコール数分布に関するチャート(1260)を概念的に表したものである。チャート(1260)は、各コール数インデックス(1264)(例えば、遠距離通信プロトコルにおいてコールされた各数)に関するコールの数(1262)をグラフ化したヒストグラムである。数学的な操作を通して、図12Bの集合ブルーム・フィルターを、チャート(1260)に示したネットワーク・ワイド通信プロトコル統計情報ヒストグラム(例えばセッション拒否ヒストグラム)を計算するために使用することができる。サーバー・ノード(906)及び/又はコンピューテーション・ノード(912)は、特定の下流サーバーに対する通信プロトコル統計情報の頻度を決定するために、チャート(1260)を使用することができる。例えば、コンピューテーション・ノード(912)は、ソース(902)から特定の目的地数へのセッション拒否の数(又は値)を決定するためにチャート(1260)を使用することができる。ここで目的地数は下流サーバー(904)を通して到達する。そして、例外検出技術は、上述したようにこうしたチャート(又はヒストグラム)(1260)に適用され、過負荷エピソードが存在するかどうかについて決定する。
【0103】
ステップ(1112)について述べると、ステップ(1110)で検出される任意の過負荷エピソードを引き起こす伝送のソースは、フィードバック・メッセージを受け取ることに基づいて検出することができる。例えば、あるサーバー・ノードでのブルーム・フィルターは、目的地基盤(例えば下流サーバー目的地に基づく)に関する通信プロトコル統計情報を管理することができる。遠距離通信ネットワークに関して、例えば、セッション要求を受け取った場合、目的地は、上述したようにブルーム・フィルターへのキーとして使用することができる。目的地キーに関するTESTは、目的地が現在過負荷がかかっているかどうかについて決定することができ、要求のソース(例えば、複数のクライアント(120)の1つ)を過負荷エピソードに関するコンジェスション(渋滞)のソースとして特定するであろう。
【0104】
ステップ(1114)に関して述べると、コントロール動作により、下流サーバー(例えば下流サーバー(904))に対して過負荷エピソードを引き起こす原因となっている1以上のソース(例えばソース(902))からのデータの伝送速度を減少させる。図13は、本発明の例示的な実施形態に従った、ネットワーク中の集中したサーバー過負荷を制限するための1以上のコントロール・パラメータを決定する(例えば、図11のステップ(1114)における1以上のコントロールパラメータを決定することを目的とする)ための方法(1300)を表すフローチャートである。ステップ(1302)において、コンピューテーション・ノード(912)(又はサーバー・ノード(906))は、サーバー・ノード又は他のネットワーク要素がコントロール動作を受ける場所を特定する動作位置を決定する。ステップ(1304)では、コンピューテーション・ノード(912)は、動作位置においてコントロール動作を適用すべき1以上のソースを定義する動作フィルターを決定する。ステップ(1306)では、コンピューテーション・ノード(912)は、コントロール動作に関する動作レベルを(例えばヒステレシスを用いて)決定する。ステップ(1308)では、コンピューテーション・ノード(912)は、動作位置に1以上のコントロール・パラメータを配信する。
【0105】
ステップ(1302)に関して述べると、動作位置の値は、以下のいずれかであってもよい:ワイルドカード(例えば、コントロール・パラメータが全てのサーバー・ノードにおいてネットワークワイドに適用される);又は、特定のサーバー・ノード(例えばネットワーク・スイッチ)、通信グループ(例えば、基幹グループ)等を特定する特定の組(tuple)。動作位置の選定は、所定のアプリオリであるポリシー・レベルの決定であってよい。例えば、動作位置は、コントロール・パラメータが全てのソースにおける動作に適用されるように決定することができる(例えば、侵入(ingress)ノード)。別の例として、遠距離通信ネットワークに関して、同定された目的地数にマッチする入ってくる基幹グループに関するコールは、入ってくる基幹グループからのコールを受け取るサーバー・ノードによって制限される速度であってよい。
【0106】
ステップ(1304)に関して述べると、動作フィルターは過負荷エピソードを引き起こす原因となる同定されたソースに基づいて計算することができる。ステップ(1306)に関して述べると、動作レベルは、複数のアルゴリズムを用いて計算することができる。図14A及び14Bは、本発明の例示的な実施形態に従って、ネットワーク中の集中したサーバー過負荷を制限するための動作レベルを決定するための方法を表すフローチャートである。図14Aは、動作レベルを決定するための方法(1400)を表す。ステップ(1402)では、コンピューテーション・ノード(912)(又はサーバー・ノード(906))は、値が所定の閾値を超えるかどうかを決定する。もし、値が所定の閾値を超える場合には、方法はステップ(1404)へと進み、コンピューテーション・ノード(912)が、減少因子を用いて以前の動作レベルから動作レベルを減少させるように決定する。もし、値が所定の閾値を下回る場合には、方法はステップ(1406)へと進み、コンピューテーション・ノード(912)が、増加ステップを用いて以前の動作レベルから動作レベルを増加させるように決定する。
【0107】
ステップ(1402〜1406)に関して述べると、方法は以下のような式を使用することができる:
while True: (12)
if VALUE > θ:
ACTION_LEVEL[k+1] = ACTION_LEVEL[k] × β
else:
ACTION_LEVEL[k+1] = ACTION_LEVEL[k] − step
k = k + 1
sleep T,
ここで:
VALUE = 現在の通信プロトコル統計情報に関する値(例えば、セッション拒否カウント);
β = 許容されたインター・コール・ギャップ時間における倍数増加値(β> 1 (例えば1.1));
step =許容されたインター・コール・ギャップ時間における更なる減少値(単位はms、例えば10 ms);
θ = コントロール・シグナル目標値(例えば、閾値);
T = 周期的な動作計算間隔;
ACTION_LEVEL[k] = k番目の間隔での動作レベル(例えば、インター・コール・ギャップ・時間が50 ms)であり、その範囲が最大値及び最小値で規定することができる(例えば最小値が40 ms 及び最大値が60 ms)。
【0108】
ステップ(1402)に関して、T秒ごとに、新たな動作レベルをシータ(θ)に基づいて計算される。最初のACTION_LEVEL[k]には、例えば、初期値を設定する
(例えば、ms単位のコール・ギャップ、例えば10ms等)。コンピューテーション・ノード(912)(又は、サーバー・ノード(906))は、VALUEがθを超えるかどうかを決定する。ステップ(1404)に関して、もし、VALUEがθを超える場合には、コンピューテーション・ノード(912)は、コール・ギャップにおける倍数増加(許容要求速度に対する減少である)を計算する。具体的には、式(12)に関して述べると、ACTION_LEVEL[k+1]は、k番目の間隔での現在の動作レベルであるが、以前の動作レベルACTION_LEVEL[k]に対する倍数増加として計算される。ステップ(1406)に関して、もしVALUEがθ以下の場合には、コンピューテーション・ノード(912)は、コール・ギャップにおける更なる減少値(許容要求速度に対する増加である)を計算する。具体的には、式(12)に関して述べると、ACTION_LEVEL[k+1]は、以前の動作レベルACTION_LEVEL[k]に対する更なる増加として計算される。有利な点として、式(12)は容易に設計され、プロセッサ(例えばサーバー・ノード(906)のプロセッサ(908))上で素早く実行される。
【0109】
図14Bは、動作レベルを決定するための方法(1450)を表すフローチャートである。ステップ(1452)では、コンピューテーション・ノード(912)は、値が所定の目標値と等しいかどうかを決定する。もし、値が所定の目標値と等しい場合には、方法はステップ(1454)に進み、コンピューテーション・ノード(912)は動作レベルの変更を行わない。もし、値が所定の目標値と等しくない場合には、方法はステップ(1456)に進み、コンピューテーション・ノード(912)は、以前の動作レベル、並びに値及び所定の目標値の差に基づいて動作レベルを決定する。
【0110】
ステップ(912〜914)に関して、方法は以下の式を使用することができる:
while True: (13)
if ABSOLUTE(VALUE − θ) > Δ:
ACTION_LEVEL[k+1] = ACTION_LEVEL[k] +γ× (VALUE -θ)
else:
ACTION_LEVEL[k+1] = ACTION_LEVEL[k]
k = k + 1
sleep T,
ここで:
Δ = 過負荷シグナルに対する目標値からの偏差に関する所定の閾値;
VALUE = 現在の通信プロトコル統計情報に関する値(例えばセッション拒否カウント);
γ =コンジェスション中コール・ギャップがどれだけ急速に増加するかについてコントロールする比例利得定数(proportional gain constant)(例えば、001);
θ =コントロール・シグナル目標値;
T = 周期的な動作計算間隔;及び
ACTION_LEVEL[k] = k番目の間隔での動作レベル(例えば、インター・コール・ギャップ・時間が50 ms)。
【0111】
ステップ(1452)に関して、T秒ごとに、新たなACTION_LEVELをVALUEに基づいて計算する。コンピューテーション・ノード(912)は、VALUE−θの絶対値がΔを超えるかどうかを決定する。ステップ(1454)に関して、ABSOLUTE(VALUE −θ)がΔの場合(即ち値がθと等しい場合)、コンピューテーション・ノード(912)は動作レベルを変更しない。ステップ(1456)に関して、もし、ABSOLUTE(VALUE − θ)がΔを超える場合(即ち、VALUEがθと等しくない場合)、コンピューテーション・ノード(912)が、以前の動作レベルACTION_LEVEL[k]に基づいて、比例アルゴリズムを用いて動作レベルACTION_LEVEL[k+1]を決定する(例えば、コントロールシグナルVALUEと所望のレベルθとの差分に比例するコール・ギャップを増加させる等)。有利な点として、式(13)は、振動動作するような結果にはならない。なぜなら、式(13)は、コントロール理論概念を使用して(例えば、比例アルゴリズムを用いて)、目標ポイントθへより早く収束するようにしているからである。
【0112】
ステップ(1308)に関して述べると、コンピューテーション・ノード(912)は、過負荷エピソードを軽減するために、1以上のコントロール・パラメータを動作位置に配信することができる。例えば、サーバー・ノード(906)及び/又はコンピューテーション・ノード(912)は、過負荷エピソードの原因となるソースと下流サーバーとの間のサーバー・ノードに、1以上のコントロール・パラメータを送る。サーバー・ノードは、ソースから下流サーバーへ伝送されるデータに関する伝送速度(例えば、過負荷エピソードの原因となる1以上のソースから下流サーバーへのコール試行速度)を減少させることにより、サーバー・ノードでの該データに関するコントロール動作を実行する。ここで前記減少は1以上のコントロール・パラメータに基づいて実行される。
【0113】
例えば、検出され、及び(例えばコンピューテーション・ノード(912)により)同定された目的地であって、過負荷がかかった目的地(例えば、下流サーバー(904)又はコールされた目的地の電話番号等の下流サーバー(904)を介して到達可能な目的地)が与えられた場合は、セッション・ギャッピングを使用して、過負荷のかかった目的地へのセッション要求(例えばクライアント(120)からの要求)間に最小限の時間制限を適用することができる。セッション・ギャッピングは、過負荷のかかった目的地へのセッション要求の入ってくる速度を制限するために使用することができる。例えば、コンピューテーション・ノード(912)は、コントロール・パラメータを配信して、クライアント(120)から受け取ったセッション要求に対して、セッション・ギャッピング(コントロール動作)をソース(902)(例えば、ネットワークの侵入ノード)で実行することができる。コントロール動作は、過負荷のかかった目的地に対して、提供されたセッション要求速度をコントロールし、(拒否されるであろう)セッションがネットワークに入って、ネットワーク・リソースを使用することを防止する。過負荷がかかった目的地に対するコール間の最小限の時間間隔は、例えば、図14A及び図14Bを参照しながら述べたACTION_LEVELとして計算することができる。このACTION_LEVELは、(例えば、マス・コーリング・イベント等の予想できないイベントに基づいて)目的地での過負荷の度合いが変化するにつれて変化することができる。
【0114】
図15は、本発明の例示的な実施形態に従って、ネットワーク中の集中したサーバー過負荷を制限するための方法(1500)を表したフローチャートである。ステップ(1502)では、コンピューテーション・ノード(912)は、ブルーム・フィルターに基づくマルチ・レベルな閾値を動作位置(例えばサーバー・ノード(906)に配信する。ブルーム・フィルターに基づくマルチ・レベルな閾値は複数の閾値を保存する。ここで、各複数の閾値は、通信プロトコルに関するコール・リクエストに関連する複数の分類からの1つのクラスに対応する。また、ブルーム・フィルターに基づくマルチ・レベルな閾値は、各複数の分類に関する下流サーバー(例えば、下流サーバー(904))へのコール・リクエストのカウントを、1以上のハッシュ関数を持ちいて保存する。ステップ(1504)では、動作位置は、ソースから下流サーバーへのコール・リクエスト・メッセージを受け取る。ここで、コール・リクエスト・メッセージは、複数の分類のうち一つの分類を含む。ステップ(1506)では、動作位置は、ブルーム・フィルターに基づくマルチ・レベルな閾値を用いて、以下について決定をする:(1)コール・リクエスト・メッセージにおける分類に関する閾値;及び(2)1以上のハッシュ関数を用いたブルーム・フィルターに基づく、コール・リクエスト・メッセージにおける分類に関する下流サーバーへのコール・リクエストのカウント。ステップ(1508)では、動作位置は、コール・リクエストのカウントが閾値を超えるかどうかを決定する。もし、コール・リクエストのカウントが閾値を超えている場合には、方法はステップ(1510)へ進み、動作位置はコール・リクエスト・メッセージを拒否する。コール・リクエストのカウントが閾値未満の場合には、方法はステップ(1512)へ進み、動作位置は、コール・リクエスト・メッセージを受け入れる。
【0115】
ステップ(1502)を参照すると、ブルーム・フィルターに基づくマルチ・レベルな閾値を、M個の分類のコール・リクエストを扱うために使用する(例えば、上述したような低、中、及び高優先度要求)。各分類は、伝送(例えば、クライアント(120)から下流サーバー(904)へ)が現状のネットワーク条件(例えば、過負荷エピソードがあるかどうか、又は下流サーバー(904)と関連するかどうか)の下で受け入れられる可能性を決定する関連優先度を有する。ブルーム・フィルターに基づくマルチ・レベルな閾値はM個の閾値を管理し、M個の分類の1分類につき1つずつ管理する。例えば、遠距離通信ネットワークに関するステップ(1504〜1512)を参照を参照すると、クライアント(120)から目的地へのコール・リクエストがソース(902)(例えば、侵入ノード)に入ったとき、ブルーム・フィルターに基づくマルチ・レベルな閾値によって追跡される現在のコンジェスション・レベル(目的地へのコール・リクエストのカウント)が、コール・リクエストに対応する分類に関する閾値と比較される。もし、コンジェスション・レベルが、コール・リクエスト閾値を超える場合には、コールは拒否される。そうでない場合にはコールは受け入れられる。
【0116】
上述した技術は、デジタル及び/又はアナログ電子回路や、コンピュータ・ハードウェア、ファームウェア、ソフトウェア、又はこれらの組合せにおいて実装することができる。こうした実装は、コンピュータ・プログラム製品として行うことができる。即ち、データ処理装置(例えば、プログラム可能なプロセッサ、コンピュータ、及び/又は複数のコンピュータ)での動作によって実行、又はコントロールするための機械読取可能ストレージデバイスで実際に実行されるコンピュータ・プログラムである。コンピュータ・プログラムは、任意の形態のコンピュータ言語又はプログラム言語で記載することができ、これらにはソース・コード、コンパイラ・コード、インタプリタ・コード、及び/又は機械コードが含まれる。そして、コンピュータ・プログラムは、任意の形態で配置することができ、該形態としては、スタンド・アロンなプログラム若しくはサブルーチン、要素、又はコンピューティング環境での使用に適した他のユニット等が含まれる。コンピュータ・プログラムは、1以上のサイトでの1つのコンピュータ又は複数のコンピュータで実行するために配置することができる。
【0117】
方法のステップは、コンピュータ・プログラムを実行する1以上のプロセッサによって実行される。そして、入力データに関して操作したり、及び/又は出力データを生成したりすることによって本発明の機能を実践する。また、方法のステップは、特定目的の論理回路(例えば、FPGA(field programmable gate array)、FPAA(field−programmable analog array)、CPLD(complex programmable logic device)、PSoC(Programmable system−on−Chip)、ASIP(application−specific instruction−set processor)、又はASIC(application−specific integrated circuit)等)によって実行することができ、そして装置は該回路として実装することができる。サブルーチンは、保存されたコンピュータ・プログラムの一部を参照することができ、並びに/又は1以上の関数を実行することができるプロセッサ及び/若しくは特殊回路を参照することができる。
【0118】
コンピュータ・プログラムの実行に適したプロセッサとしては、例示的な意味で汎用目的のマイクロプロセッサ及び特殊目的のマイクロプロセッサの両方、並びに任意の種類のデジタル又はアナログコンピュータにおける1以上の任意のプロセッサが含まれる。一般的に、プロセッサは、ROM、RAM、又はその両方から指示やデータを受け取る。コンピュータの本質的な要素は、指示を実行するためのプロセッサ、並びに指示及び/又はデータを保存するための1以上のメモリ・デバイスである。キャッシュ等のメモリ・デバイスは、一時的にデータを保存するために使用することができる。また、メモリ・デバイスは長期間のデータ保存目的で使用することもできる。また、一般的に、コンピュータは、それらからデータを受け取ったり、又はそれらへデータを送ったり、又はその両方を目的として、データ保存用の1以上のマス・ストレージデバイス(例えば、磁気媒体、光磁気ディスク、又は光ディスク等)を含む、又は動作上連結している。また、ネットワークから指示及び/若しくはデータを受け取ったり、並びに/又はネットワークへ指示及び/若しくはデータを送ったりすることを目的として、コンピュータは動作上通信ネットワークと連結している。コンピュータ・プログラムの指示及びデータを実行することに適したコンピュータ読取可能保存媒体としては以下の物が含まれる:あらゆる形態の揮発性及び不揮発性メモリ(例示的な意味として、半導体メモリ・デバイス、例えば、DRAM、SRAM、EPROM、EEPROM及びフラッシュ・メモリ・デバイス);磁気ディスク(例えば、内部のハードディスク、又はリムーバブル・ディスク);光磁気ディスク;及び光ディスク(CD、DVD、HD−DVD及びBlu−ray)。プロセッサ及びメモリは、特殊目的の論理回路によって補足したり及び/又は該回路中に組み込むことができる。
【0119】
ユーザーとの相互作用を提供するために、上述した技術を、ユーザーに情報を表示するための表示装置(例としては、CRT(cathode ray tube)、プラズマ、又はLCD(液晶ディスプレイモニター))や、キーボード及びポインティング・デバイス(例えば、マウス、トラックボール、タッチパッド、モーション・センサー)(これらによって、ユーサーはコンピュータに入力を行うことができる(例えば、ユーザー・インターフェース要素と相互作用する))と通信するコンピュータ上で実行することができる。同様にユーザとの相互作用を提供する目的で他の種類のデバイスを使用することができる;例えば、ユーザーに提供するフィードバックとしては、任意の形態の感覚的フィードバック(例えば、視覚的フィードバック、聴覚的フィードバック、及び触覚的フィードバック)の形態であってもよい。そして、ユーザーからの入力については、音響、スピーチ、及び/又は触覚的な入力を含む任意の形態で受け取ることができる。
【0120】
上述した技術は、バック・エンド・コンポーネントを含む分散コンピューティング・システムにおいて実行することができる。バック・エンド・コンポーネントとしては、例えば、データ・サーバー、ミドルウェア・コンポーネント、及び/又はアプリケーション・サーバー等であってもよい。上述した技術は、フロント・エンド・コンポーネントを含む分散コンピューティング・システムにおいて実行することができる。フロント・エンド・コンポーネントとしては、例えば、GUI、ユーザーが例示的な実装形態と相互作用することができるウェブ・ブラウザ、及び/又は伝送デバイス用の他のGUIを有するクライアント・コンピュータであってもよい。上述した技術は、前述のバック・エンド、ミドルウェア、又はフロント・エンド・コンポーネントの任意の組合せを含む分散コンピューティング・システムにおいて実行することができる。
【0121】
コンピューティング・システムのコンポーネントは、伝送媒体(110)によって相互接続することができ、該媒体はデジタル又はアナログデータ通信に関する任意の形態又は媒体を含むことができる(例えば、通信ネットワーク)。伝送媒体(110)は、任意の設計において、1以上のパケット・ベースのネットワーク及び/又は1以上の回路・ベースのネットワークを含むことができる。パケット・ベースのネットワークとしては、以下のものを含むことができる:例えば、インターネット、キャリア・インターネット・プロトコル(IP)ネットワーク(例えば、ローカル・エリア・ネットワーク(LAN)、ワイド・エリア・ネットワーク(WAN)、キャンパス・エリア・ネットワーク(CAN)、メトロポリタン・エリア・ネットワーク(MAN),ホーム・エリア・ネットワーク(HAN))、プライベートIPネットワーク、IP構内交換機(IP private branch exchange (IPBX))、ワイヤレス・ネットワーク(例えば、ラジオ・アクセス・ネットワーク(RAN)、Bluetooth(登録商標)、Wi−Fi(登録商標)、WiMax(登録商標)、GPRS(general packet radio service)、HiperLAN)及び/又は他のパケット・ベースのネットワーク。回路ベースのネットワークとしては、例えば以下のものを含むことができる:公衆電話交換回線網(PSTN)、レガシーPBX、ワイヤレス・ネットワーク(例えば、RAN、CDMA(符号分割多重接続)ネットワーク、TDMA(時分割多重接続)ネットワーク、GSM(登録商標)ネットワーク)、及び/又は他の回路ベース・ネットワーク。
【0122】
伝送媒体(110)を介した情報伝達は、1以上の通信プロトコルに基づくことができる。通信プロトコルとしては、例えば以下のものを含めることができる:Ethernet(登録商標)プロトコル、インターネット・プロトコル(IP)、ボイップ(Voice over IP (VoIP))、ピア・ツー・ピア・プロトコル(P2P)、ハイパーテキスト・ドランスファー・プロトコル (HTTP)、セッション確立プロトコル(SIP)、H.323、メディア・ゲートウェイ・コントロール・プロトコル(MGCP)、シグナリング・システム#7(SS7)、GSM(登録商標)プロトコル、プッシュ・ツー・トーク(PTT)プロトコル、プッシュ・ツー・トーク・オーバー・セルラー(POC)プロトコル、及び/又は他の通信プロトコル。
【0123】
コンピューティング・システムの装置としては、例えば以下のものを含めることができる:コンピュータ、ブラウザ・デバイスを備えるコンピュータ、電話、IP電話、モバイル装置(例えば、携帯電話、PDA、ラップトップ・コンピュータ、電子メール装置)、及び/又は他の通信装置。ブラウザ・デバイスとしては、例えば、WWWブラウザ(例えば、マイクロソフト(登録商標)社が提供しているMicrosoft Internet Explorer(登録商標)、Mozilla社から入手できる Mozilla(登録商標) Firefox)を備えるコンピュータが含まれる。モバイル・コンピューティング・デバイスとしては、例えば、Blackberry(登録商標)を含むことができる。IP電話としては、シスコシステムから入手できるCisco(登録商標)Unified IP Phone 7985Gや、Cisco Unified Wireless Phone 7920が含まれる。
【0124】
本発明の思想及び本質的な特性から乖離することなく他の特的の形態で本発明を実施できることを当業者は理解するであろう。従って、本明細書で記述した本発明に関して、上記実施形態は限定的にではなく全て例示的な観点で考慮すべきものである。よって、本発明の範囲は、上述した内容によってではなく、添付した特許請求の範囲によって表される。そして、前記特許請求の範囲の意味及び均等物の範囲内に入る全ての変更は、本発明の範囲に入ることを意図する。

【特許請求の範囲】
【請求項1】
クライアント・コントロールを介したサーバー過負荷制限を目的とするコンピュータ化した方法であって、以下のステップを含む方法:
サービスに関する複数リクエストの第一セットを第一期間中第一伝送速度でサーバーに伝送するステップ;
第一期間中第一伝送制限速度以下になるよう前記第一伝送速度を制限するステップ;
サービスに関する前記複数リクエストの第一セットのうち少なくとも2以上のリクエストが過負荷基準を満たしているかどうかに基づいて過負荷値を決定するステップ;
前記過負荷値をコンピュータ・メモリ・モジュールに保存するステップ;
前記過負荷値及び前記第一伝送制限速度に基づいて第二伝送制限速度を決定するステップ;
サービスに関する複数リクエストの第二セットを前記第一期間後の第二期間中に第二伝送速度で前記サーバーに伝送するステップ;及び、
前記第二期間中の第二伝送速度を前記第二伝送制限速度以下になるよう制限するステップ。
【請求項2】
請求項1に記載の方法であって、前記過負荷値が目標過負荷値を下回るか上回るかを決定するステップを更に含む方法。
【請求項3】
請求項2に記載の方法であって、前記過負荷値が前記目標過負荷値を超える場合に、前記第二伝送制限速度を決定するステップが、前記過負荷値と前記目標過負荷値との差分に比例する量だけ前記第一伝送制限速度を低下させるステップを含む該方法。
【請求項4】
請求項2に記載の方法であって、前記過負荷値が前記目標過負荷値を超える場合に、前記第二伝送制限速度を決定するステップが、前記過負荷値に比例する量だけ前記第一伝送制限速度を低下させるステップを含む該方法。
【請求項5】
請求項4に記載の方法であって、前記過負荷値が前記過負荷基準を満たすリクエスト速度を表す該方法。
【請求項6】
請求項2に記載の方法であって、前記過負荷値が前記目標過負荷値未満の場合に、前記第二伝送制限速度を決定するステップが前記第一伝送制限速度を速度ステップだけ上昇させるステップを含む該方法。
【請求項7】
請求項6に記載の方法であって、前記速度ステップが固定されている該方法。
【請求項8】
請求項6に記載の方法であって、前記速度ステップが前記第一伝送制限速度に基づく該方法。
【請求項9】
請求項8に記載の方法であって、前記速度ステップの範囲が最大速度ステップ及び最小速度ステップで決定される該方法。
【請求項10】
請求項1に記載の方法であって、第一層エンティティが前記過負荷値を決定し、第二層エンティティが前記第一伝送速度を制限し、前記第一層エンティティは前記第二層エンティティとは異なる該方法。
【請求項11】
請求項10に記載の方法であって、前記第一層エンティティがトランスポート層エンティティを含み、前記第二層エンティティがアプリケーション層エンティティを含む該方法。
【請求項12】
請求項1に記載の方法であって、前記過負荷基準が明示的な過負荷基準である該方法。
【請求項13】
請求項12に記載の方法であって、前記明示的な過負荷基準が単一のリクエストのみに適用される該方法。
【請求項14】
請求項12に記載の方法であって、前記明示的な過負荷基準が非スロットリング型クライアント・レスポンスを特定する該方法。
【請求項15】
請求項12に記載の方法であって、前記第一セットからのリクエストであって且つサービスを要求する第一リクエストに関する第一拒否メッセージを前記サーバーから受け取った場合、前記第一リクエストが前記明示的な過負荷基準を満たす該方法。
【請求項16】
請求項1に記載の方法であって、前記過負荷基準が暗黙的な過負荷基準である該方法。
【請求項17】
請求項16に記載の方法であって、前記第一セットからのリクエストであって且つサービスを要求する第一リクエストが伝送されてからの経過時間が遅延閾値を超える場合に、前記第一リクエストが前記暗黙的な過負荷基準を満たす該方法。
【請求項18】
請求項16に記載の方法であって、ある時間間隔でサービスを要求する未応答のリクエストの割合が割合閾値以上になった場合に、前記暗黙的な過負荷基準を満たす該方法。
【請求項19】
請求項16に記載の方法であって、前記暗黙的な過負荷基準がピア・コンジェスションとは無関係の前記サーバーからの1以上の応答メッセージに基づく該方法。
【請求項20】
請求項19に記載の方法であって、前記1以上の応答の割合が割合閾値以上になった場合に、前記暗黙的な過負荷基準を満たす該方法。
【請求項21】
請求項19に記載の方法であって、前記暗黙的な過負荷基準が、割合閾値以上である前記1以上の応答割合の変化に基づく該方法。
【請求項22】
請求項17に記載の方法であって、前記遅延閾値が静的である該方法。
【請求項23】
請求項17に記載の方法であって、前記遅延閾値が、前記サーバーに伝送されサービスを要求する1以上の以前のリクエストに対する平均応答時間に基づく該方法。
【請求項24】
請求項17に記載の方法であって、前記遅延閾値が、前記サーバーに伝送されサービスを要求する1以上の以前のリクエストに対する百分率の応答時間に基づく該方法。
【請求項25】
請求項15又は16に記載の方法であって、前記第一セットからのリクエストであって且つサービスを要求する前記第一リクエストに対する第一応答を受け取る前に、前記第一セットからのリクエストであって且つサービスを要求する第二リクエストに対する第二応答を受け取るか否かに基づいて、第一リクエストが前記過負荷基準を満たす該方法(ここで、前記第二リクエストは、前記第一リクエストの後に前記サーバーへ伝送される)。
【請求項26】
請求項1に記載の方法であって、前記過負荷値を決定するステップが、前記過負荷基準を満たす前記第一セットからのリクエスト数を平均化するステップ及び/又はフィルタリングするステップを含む該方法。
【請求項27】
請求項26に記載の方法であって、前記過負荷値を決定するステップが、更に、前記第一期間の前の1以上の期間に関連する1以上の以前の過負荷値に基づく該方法。
【請求項28】
請求項1に記載の方法であって、前記第一期間が前記第二期間とブラインド間隔期間だけ離れている該方法。
【請求項29】
請求項28に記載の方法であって、前記ブラインド間隔が固定時間間隔であるか、及び/又は前記サーバーに伝送されサービスを要求する1以上の以前のリクエストに対する平均応答時間に基づく該方法。
【請求項30】
請求項1に記載の方法であって、前記複数リクエストの第一セットを伝送するステップが、前記1以上のリクエストの伝送について、リクエストの種類に基づいて優先順位を付けるステップを含む該方法。
【請求項31】
請求項30に記載の方法であって、前記1以上のリクエストのリクエスト種類が、高優先度、通常、又はこれらの任意の組合せを含む該方法。
【請求項32】
請求項1に記載の方法であって、前記複数リクエストの第一セット及び第二セットが同一の分類である該方法。
【請求項33】
請求項1に記載の方法であって、前記複数リクエストの第一セットが第一分類及び第二分類のリクエストを少なくとも含み、前記複数リクエストの第二セットが前記第一分類のリクエストのみからなる該方法。
【請求項34】
クライアント・コントロールを介したサーバー過負荷制限を目的とするシステムであって、以下を備えるシステム:
サービスを要求する複数リクエストの第一セットを保存するように設計されたバッファ;
前記バッファと接続される伝送機であって、サービスを要求する前記1以上のリクエストを伝送制限速度以下となる伝送速度で第一期間中サーバーに伝送するように設計される伝送機;及び
以下の手段を備えるコントローラ:
サービスに関する前記複数リクエストの第一セットのうち少なくとも2以上のリクエストが過負荷基準を満たしているかどうかに基づいて過負荷値を決定するためのコンピューティング手段;
前記過負荷値及び前記伝送制限速度に基づいて、伝送制限速度を調整するためのコンピューティング手段。
【請求項35】
コンピュータ・プログラム製品であって、機械読取可能ストレージデバイスで実際に実行され、前記コンピュータ・プログラム製品が、データ処理装置に以下の動作を行わせるために実行可能な指示を含む該プログラム製品:
サービスに関する複数リクエストの第一セットを第一期間中第一伝送速度でサーバーに伝送すること;
前記第一伝送速度を前記第一期間中第一伝送制限速度以下に制限すること;
サービスを要求する前記複数リクエストの第一セットのうち少なくとも2以上のリクエストが過負荷基準を満たしているかどうかに基づいて過負荷値を決定すること;
コンピュータ・メモリ・モジュールに前記過負荷値を保存すること;
前記過負荷値及び前記第一伝送制限速度に基づいて第二伝送制限速度を決定すること;
サービスを要求する複数リクエストの第二セットを前記第一期間後である第二期間中に第二伝送速度で前記サーバーに伝送すること;及び
前記第二期間中前記第二伝送制限速度以下になるように前記第二伝送速度を制限すること。
【請求項36】
ネットワーク中のサーバー過負荷を制限するためのコンピュータ化された方法であって、以下のステップを含む方法:
ネットワークのサーバー・ノードが下流サーバーからのフィードバック・メッセージを受け取るステップ(ここで前記フィードバック・メッセージは通信プロトコルの統計情報を含む);
コンピュータ・メモリ・モジュールに保存されたカウンター配列からの1以上のカウンターのうちどのカウンターが前記下流サーバーと関連しているかを、前記フィードバック・メッセージ中に含まれる情報に基づき1以上のハッシュ関数を用いて前記サーバー・ノードが決定するステップ(ここで、前記1以上のカウンターは、前記統計情報を含み且つ前記下流サーバーから受け取ったフィードバック・メッセージ数に対応する数を保存する);
前記統計情報を含む前記フィードバック・メッセージに応答して、前記サーバー・ノードが前記1以上のカウンターを増加させるステップ;
前記1以上のカウンター内に保存された数の値を前記1以上のハッシュ関数を用いて前記サーバー・ノードが決定するステップ;及び
前記値が所定の基準を満たすかどうかに基づいて、前記下流サーバーに関する前記ネットワーク内の過負荷エピソードを前記値が表すことを、前記サーバー・ノードが決定するステップ。
【請求項37】
請求項36に記載の方法であって、前記所定の基準が閾値であり、且つ前記決定するステップが、前記値が前記閾値を超えている事を決定するステップを含む該方法。
【請求項38】
請求項37に記載の方法であって、前記閾値をヒステレシスを用いて計算する該方法。
【請求項39】
請求項36に記載の方法であって、前記過負荷エピソードの誘発を担う1以上のソースを特定するステップを更に含む該方法(ここで各ソ−スは、前記統計情報を含むフィードバック・メッセージを前記下流サーバーに伝送させる前記下流サーバーへの伝送を初期化する)。
【請求項40】
請求項36に記載の方法であって、前記値に基づくコントロール動作を行うための1以上のコントロール・パラメータを決定するステップを更に含む該方法(ここで前記コントロール動作は、前記下流サーバーに対する前記過負荷エピソードの誘発を担う1以上のソースからのデータに関する伝送速度を減少させる)。
【請求項41】
請求項40に記載の方法であって、更に以下のステップを含む該方法:
前記過負荷エピソードの誘発を担うソースと前記下流サーバーとの間のサーバー・ノードへ、前記1以上のコントロール・パラメータを伝送するステップ;及び
前記ソースから前記下流サーバーへ伝送されるデータに関する伝送速度を減少させることにより、前記ソースから前記下流サーバーへの伝送データに関する前記サーバー・ノードでの前記コントロール動作を行うステップ(ここで、前記速度減少は前記1以上のコントロール・パラメータに基づいて行われる)。
【請求項42】
請求項40に記載の方法であって、前記伝送速度が、前記過負荷エピソードの誘発を担う1以上のソースから前記下流サーバーへのコール・アテンプト速度である該方法。
【請求項43】
請求項40に記載の方法であって、前記1以上のコントロール・パラメータを決定するステップが以下のステップを含む該方法:
前記コントロール動作をどこで行うべきかを特定する動作位置を決定するステップ;
前記動作位置で前記コントロール動作を適用する対象となる1以上のソースを定義する動作フィルターを決定するステップ;及び、
前記コントロール動作に関する動作レベルを決定するステップ。
【請求項44】
請求項43に記載の方法であって、前記動作レベルを決定するステップが以下のステップを含む該方法:
前記値が所定の閾値を超えるかどうかを決定するステップ;及び
前記値が前記所定の閾値を超える場合、前記動作レベルについて、減少因子を用いて以前の動作レベルから減少させることを決定するステップ;又は、
前記値が前記所定の閾値未満の場合、前記動作レベルについて、増加ステップを用いて以前の前記動作レベルから増加させることを決定するステップ。
【請求項45】
請求項44に記載の方法であって、前記閾値をヒステレシスを用いて計算する該方法。
【請求項46】
請求項44に記載の方法であって、決定するステップが以下のステップを含む該方法:
前記値が所定の目標値と等しいかどうかを決定するステップ;並びに、
もし前記値が前記所定の目標値と等しい場合には、前記動作レベルを変更しないステップ;又は、
もし前記値が前記所定の目標値と等しくない場合には、前記値と前記所定の目標値との差異及び以前の動作レベルに基づいて前記動作レベルを決定するステップ。
【請求項47】
請求項44に記載の方法であって、前記1以上のコントロール・パラメータを前記動作位置に配信するステップを更に含む該方法。
【請求項48】
請求項36に記載の方法であって、更に以下のステップを含む該方法:
第二フィードバック・メッセージを第二下流サーバーから受け取るステップ(ここで前記 第二フィードバック・メッセージは前記統計情報を含む);
前記第二フィードバック・メッセージ中に含まれる情報に基づき1以上のハッシュ関数を用いて、カウンター配列からの1以上のカンウターのうちのどれが前記第二下流サーバーと関連しているかを決定するステップ;及び、
前記統計情報を含む前記第二フィードバック・メッセージに応答して前記1以上のカウンターを増加させるステップ。
【請求項49】
請求項36に記載の方法であって、更に以下のステップを含む該方法:
複数のカウンター配列を保存するステップ(ここで前記複数のカウンター配列それぞれは、異なるサーバー・ノードに保存されている);及び
複数のサーバー・ノードに跨る前記複数のカウンター配列に関連する各下流サーバーから受け取ったフィードバック・メッセージの数を計算するために前記複数のカウンター配列を集計するステップ。
【請求項50】
請求項36に記載の方法であって、前記通信プロトコルがセッション確立プロトコル (Session Initiation Protocol、SIP)であり;及び
前記統計情報がセッション拒否、前記下流サーバーからの過負荷フィードバック又はその両方である該方法。
【請求項51】
請求項36に記載の方法であって、前記通信プロトコルがセッション確立プロトコル、ハイパーテキスト・ドランスファー・プロトコル(HTTP)、ストリーム制御転送プロトコル(SCTP)、又はTCPプロトコル(transmission control protocol)である該方法。
【請求項52】
請求項36に記載の方法であって、前記1以上のハッシュ関数及び前記カウンター配列がカウンティング・ブルーム・フィルターに関連する該方法。
【請求項53】
請求項52に記載の方法であって、1以上のカウンターのうちどれが前記下流サーバーに関連するかについて決定することが、キーに関連するハッシュ関数を用いて前記1以上のカウンターを決定することを含み、前記キーは前記下流サーバーに関する識別子である該方法。
【請求項54】
請求項36に記載の方法であって、前記増加させるステップが以下のステップを含む該方法:
前記1以上のカウンターを1ずつ増加させるステップ;又は、
前記1以上のカウンターを1を超える数で増加させるステップ(ここで、前記1を超える数は以下に基づいて決定される:前記統計情報;一定期間、前記下流サーバーから受け取る統計情報;複数の一定期間、前記下流サーバーから受け取る統計情報;ソースから前記下流サーバーへ行われる伝送の種類;又はこれらの任意の組合せ)。
【請求項55】
請求項36に記載の方法であって、ブルーム・フィルターに基づくマルチ・レベルな閾値を動作位置に配信するステップを更に含む該方法
(ここで前記ブルーム・フィルターに基づくマルチ・レベルな閾値は、以下を保存する:
複数の閾値(ここで前記複数の各閾値は、前記通信プロトコルに関するコール・リクエストと関連する複数のクラスからの1つのクラスに対応する);及び、
1以上のハッシュ関数を用いた前記複数の各クラスに関する、前記下流サーバーに対するコール・リクエストのカウント)。
【請求項56】
請求項55に記載の方法であって、以下のステップを含む該方法:
ソースから前記下流サーバーへのコール・リクエスト・メッセージを受け取るステップ(前記コール・リクエスト・メッセージは、前記複数のクラスのうち1つのクラスを含む);
前記ブルーム・フィルターに基づくマルチ・レベルな閾値を用いて、以下を決定するステップ:
(1)前記コール・リクエスト・メッセージ中の前記クラスに関する閾値;及び、
(2)前記1以上のハッシュ関数を用いて、ブルーム・フィルターに基づく前記コール・リクエスト・メッセージ中の前記クラスに関する、前記下流サーバーへのコール・リクエストのカウント;並びに、
もし、前記コール・リクエストのカウントが前記閾値を超える場合、前記コール・リクエスト・メッセージを拒否するステップ;又は
もし、前記コール・リクエストのカウントが前記閾値未満の場合、前記コール・リクエスト・メッセージを受け入れるステップ。
【請求項57】
請求項36に記載の方法であって、前記統計情報が:ソースから前記下流サーバーへの失敗した接続リクエスト;前記下流サーバーからの過負荷通知;又はこれら両方である該方法。
【請求項58】
ネットワーク中のサーバー過負荷を制限するためのシステムであって、以下を備える該システム:
カウンター配列を保存するように設計されるコンピュータ・メモリ・モジュール;及び
前記コンピュータ・メモリ・モジュールと通信し、以下の手段を備えるコントローラ:
下流サーバーからフィードバック・メッセージを受け取るためのコンピューティング手段(ここで前記フィードバック・メッセージは通信プロトコルの統計情報を含む);
前記カウンター配列からの1以上のカウンターのうちのどれが前記下流サーバーに関連するかについて、1以上のハッシュ関数を用い、前記フィードバック・メッセージ中に含まれる情報に基づいて決定するためのコンピューティング手段(ここで前記1以上のカウンターは、前記下流サーバーから受け取り、且つ前記統計情報を含むフィードバック・メッセージの数に対応する数を保存する);
前記統計情報を含む前記フィードバック・メッセージに応答して前記1以上のカウンターを増加させるためのコンピューティング手段;
前記1以上のカウンターに保存される数の値を前記1以上のハッシュ関数を用いて決定するためのコンピューティング手段;及び、
前記値が所定の基準を満たすかどうかに基づいて、前記下流サーバーが関連する前記ネットワーク中の過負荷エピソードを前記値が表すことを決定するためのコンピューティング手段。
【請求項59】
コンピュータ・プログラム製品であって、機械読取可能ストレージデバイスで実際に実行され、前記コンピュータ・プログラム製品が、データ処理装置に以下の動作を行わせるために実行可能な指示を含む該プログラム製品:
下流サーバーからのフィードバック・メッセージを受け取ること(ここで前記フィードバック・メッセージは通信プロトコルの統計情報を含む);
コンピュータ・メモリ・モジュールに保存されたカウンター配列からの1以上のカウンターのうちのどれが前記下流サーバーと関連するかを、前記フィードバック・メッセージ中に含まれる情報に基づき、1以上のハッシュ関数を用いて決定すること(ここで前記1以上のカウンターは、前記下流サーバーから受け取とり、且つ前記統計情報を含むフィードバック・メッセージの数に対応する数を保存する);
前記統計情報を含む前記フィードバック・メッセージに応答して前記1以上のカウンターを増加させること;
前記1以上のカウンターに保存される数の値を前記1以上のハッシュ関数を用いて決定すること;及び、
前記値が所定の基準を満たすかどうかに基づいて、前記下流サーバーが関連する前記ネットワーク中の過負荷エピソードを前記値が表すことを決定すること。

【図1】
image rotate

【図2】
image rotate

【図3】
image rotate

【図4】
image rotate

【図5】
image rotate

【図6】
image rotate

【図7】
image rotate

【図8】
image rotate

【図9】
image rotate

【図10】
image rotate

【図11】
image rotate

【図12A】
image rotate

【図12B】
image rotate

【図12C】
image rotate

【図13】
image rotate

【図14A】
image rotate

【図14B】
image rotate

【図15】
image rotate


【公表番号】特表2012−525780(P2012−525780A)
【公表日】平成24年10月22日(2012.10.22)
【国際特許分類】
【出願番号】特願2012−508589(P2012−508589)
【出願日】平成22年4月27日(2010.4.27)
【国際出願番号】PCT/US2010/032563
【国際公開番号】WO2010/129275
【国際公開日】平成22年11月11日(2010.11.11)
【出願人】(505285755)ソーナス ネットワークス, インコーポレイテッド (10)
【住所又は居所原語表記】4 Technology Park Drive,Westford,MA 01886 U.S.A.
【Fターム(参考)】