(57)【要約】リアルタイム取引処理システムは、リーキーバケット及びフロー制御手段を含んでいる。前記フロー制御手段は、各リアルタイム取引の応答時間をモニタリングし、前記応答時間を所定の応答時間と比較し、前記応答時間が前記所定の応答時間を超える時に前記リーキーバケットのコンテンツを増加させる。前記リアルタイム取引処理システムは、前記リーキーバケットの前記コンテンツに比例して取引を拒否する。さらに、各リアルタイム取引の応答時間をモニタリングすることによって前記リアルタイム取引処理システムを動作させる方法は、前記応答時間を前記所定の応答時間と比較し、前記応答時間が前記所定の応答時間を超える時に前記リーキーバケットのコンテンツを増加させる。
2005501316.tif 000002
【特許請求の範囲】
【請求項１】
リーキーバケット及びフロー制御手段を含むリアルタイム取引処理システムであって、
前記フロー制御手段が、各リアルタイム取引の応答時間をモニターし、前記応答時間を所定の応答時間と比較し、前記応答時間が前記所定の応答時間を超える時、前記リーキーバケットのコンテンツを増加させるように配置されているリアルタイム取引処理システム。
【請求項２】
前記所定応答時間が、前記各々の取引の関数である請求項1に記載のリアルタイム取引処理システム。
【請求項３】
前記増加が、前記各々の取引の関数である請求項1又は2に記載のリアルタイム取引処理システム。
【請求項４】
前記リアルタイム取引システムが、リーキーバケット及びフロー制御手段を含むリアルタイム取引処理システムを動作させる方法であって、
（ａ）各リアルタイム取引の前記応答時間をモニターすること、
（ｂ）所定の応答時間を有する前記応答時間を含んでいること、及び、
（ｃ）前記応答時間が前記所定の応答時間を超える時、前記リーキーバケットの前記コンテンツを増加させること、の段階を含む前記方法。
【請求項５】
前記所定の応答時間が、前記各々の取引の関数である請求項4の方法。
【請求項６】
前記増加が、前記各々の取引の関数である請求項4又は5に記載の方法。
【請求項７】
リーキーバケット及びフロー制御手段を含むリアルタイム取引処理システムであって、
前記フロー制御手段が、各リアルタイム取引の前記応答時間をモニターし、前記応答時間を所定の応答時間と比較し、前記リーキーバケットの前記コンテンツに比例して取引を拒否するように配置されているリアルタイム取引処理システム。
【請求項８】
前記リアルタイム取引システムが、リーキーバケット及びフロー制御手段を含むリアルタイム取引処理システムを動作させる方法であって、
（ａ）各リアルタイム取引の前記応答時間をモニターすること、
（ｂ）前記応答時間を所定の応答時間と比較すること、
（ｃ）前記応答時間が所定の応答時間を超える時、前記利キーバケットの前記コンテンツを増加させること、
（ｄ）前記リー記バケットの前記コンテンツをモニターすること、及び、
（ｅ）前記リーキーバケットのモニターされたコンテンツに比例して取引を拒否すること、の段階を含む前記方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、リーキーバケットを含むリアルタイム処理システムに関する。
【発明の開示】
【課題を解決するための手段】
【０００２】
本発明に従い、リーキーバケット及びフロー制御手段を含むリアルタイム取引処理システムは提供され、前記フロー制御手段は、各リアルタイム取引の応答時間を監視し、前記応答時間を所定の応答時間と比較し、前記リアルタイムが前記所定応答時間を超える時に前記リーキーバケットの内容を増大させる調整がなされる。さらに、提供されるリーキーバケット及びフロー制御手段を含むリアルタイム取引処理システムにおいて、前記フロー制御手段は、各リアルタイム取引の応答時間を監視し、前記応答時間を所定の応答時間と比較し、前記リーキーバケットのコンテンツに比例して拒否するために配置されている。
【０００３】
ここで、本発明の例は、添付図を参照し、例を介して描写する。
【０００４】
第1に、本発明の実際の例を描写する。
【０００５】
問題は、銀行の副頭取に関係する。前記銀行は、全国をカバーするサンダーランドに顧客コールセンターを経営している。副頭取は、前記コールセンターがどの程度忙しいのか、また、どのような種類のサービスを多くの顧客が利用しているかについて知識を得たいが、彼は、前記コールセンターのマネージャーが正確な情報を伝えているかを信頼していない。ロンドン営業所を離れることなく前記情報を得る良い方法が存在する。彼は、1日に何回か前記コールセンターに電話し、応答するまでにどのくらい長い時間を待たなければならないかについてメモを取る。すなわち、彼は、コールと腹立たしい‘お待ちください’という音楽の全ての秒数を書き留めて、（差し引き残高をチェックする）取引の長さを加える。
【０００６】
彼が、長時間待たなければならないならば、前記コールセンターは非常に忙しいことを意味している。彼が、通常、2コールでコールの応答を得て、その取引が迅速であれば、彼は、おそらくスタッフの数を減らすことができる。
【０００７】
彼は、前記コールセンターは忙しいが、忙し過ぎることはないことを意味する時間を混合しそうである。
【０００８】
すなわち、しきりにサンプルした場合であれば、遅延時間は、直接的にそれを照会することなく、遠隔サーバの占有率についての知識を得ることになる。
【０００９】
顧客が、その日の一定時間、長い待ち時間について不平を言い始めていることが判明する。
【００１０】
前記副頭取は、前記コールセンターに来る仕事量を制御したい。1つの問題は、1時間毎のコーヒーブレイクによる停止時間である。彼は、ロンドン営業所から交換機を制御できるシステムを導入する。彼は、このシステムを採用することに決め、コールが入る度に、バケットにビーンを置く。顧客が電話を切る度に、彼は、ビーンを取り出す。バケットが一杯になれば、電話を変えて、‘後ほど電話する’アナウンスが、顧客にされる。全てのコールセンターの従業員が、同時にコーヒーブレイクするならば、あまり多くない顧客に対しても不便であることが確実である。一定量をバケットに加えることによって、コールが入る度に、前記バケットは、遠隔サーバが故障する時に、結局は一杯になり、拒否され得る。
【００１１】
しかしながら、このシステムは、全体の故障の場合に働くのみである。前記副頭取は、前記コールセンターの占有率が高すぎるならば、（‘後ほど電話をする’アナウンスを流す）トラフィックを拒否したい。
【００１２】
ほぼ100％それらを実行すれば、彼は、従業員に過度の圧力を加えることが懸念され、結果として1つの問題又は訴訟までも起こり得る。コールと音楽の待ち時間が長すぎる時、彼は、早期の実験から占有率が高いということを認識している。彼は、最大法定占有率（70％）で（余分なサービス時間を待っている）全時間を記録することを決定する。彼は、30秒から5分までの時間の範囲であることを見付けるが、コールの95％は、2分よりも短い。そのため、彼は、次のことをすることに決定する。2分よりも長いコールの全てに対して、バケットの中にビーンを置くことである。その方法は、コールが長すぎるならば、バケットは、一杯になり、トラフィックを拒否することについてルールを呼び出す。
【００１３】
しかし、このシナリオには問題がある。前記コールセンターが法定占有率以下である時にも5％の長いコールはどうか？前記コールセンターが70％の占有率で動作しているならば、その時、コールの5％（2分よりも長いコール）は、結果としてバケットに入ることになる（そのまま残る）。
【００１４】
結局、前記銀行の頭取は、バケットが一杯になり、ルールに従って、コールを拒否することを余儀なくされた。彼は、前記システムを多少変更することを決定した。‘漏れ（リーク）’を設けた。そして、時々、1つ残らずバケットからビーンを取り出す。最大受ける顧客コール率を、ビーンがバケットに入る平均割合であることにして単純に漏れ率を計算した。最大受ける率を釣り合い点とするならば、バケットに入っているビーンの割合が、出て行くビーンの割合に等しく、その時、前記顧客コール率が最大を超える時はいつでも、ビーンは漏れ出すよりも多く入っていくことが確実となり、バケットは一杯になる。
【００１５】
より特定するために、前記コールセンターに100名の低賃金労働者を備える。任意の時に占有されるように、最大で70名欲しい。平均コールに1分遅れること、70％の占有率で2分より少ないことが95％であることに気付く。コールの割合が1分に70回である時、70％の占有率が生じる。そのコールの割合で、2分よりも長い毎分3.5回のコールがある（3.5は70の5％）。そのルールは、2分より遅れる全てのコールは、バケットにビーンを置くことによってペナルティーを支払わなければならないことである。そのため、そのルールに従って、前記コール率が70コール/分である時、それは、1分に3.5個のビーンをバケットに置くことを意味する。1分に3.5個のビーンをバケットから取ることにより、平均で、バケットは、同じレベルに留まり、一杯の10分の3ぐらいである。
【００１６】
ここで、コール率が80コール/分に増加する。従業員は、よりストレスを抱え、効果的でなく、空き回線を待っているより多くの顧客いるため、平均コール時間は、1.1分にまで上がり、コールの20％よりも多くが、2分よりも長い。占有率は、80％に達する。しかし、ここで、バケットの調整システムが実施される。まだ、2分のペナルティールールを適用している時、20％*80コール/分=16ビーン/分をバケットに置いている。3.5ビーン/分のみが、漏れ出す時、バケットは、数分後一杯になり（正確には、時間はバケットのサイズ次第である）、その時、コールは拒否され始める。一度、コールが拒否されると、（許諾される）コール率が下がり、占有率及びコール時間は減り、70％の占有率の状態に再度安定する。コール率が50コール/分の時はどうなるか？その率では、平均時間は、まだ、おおよそ1分であるが、2分より長いのはコールの1％だけである。そのため、0.5（50のうちの1％）ビーン/分のみが、バケットに入る。しかしながら、まだ3.5ビーン/分の漏れ出しがある。そのため、バケットはほとんどの時間で空である。
【００１７】
このアルゴリズムは、トラフィックを制御するのにサービスと待ちの時間を利用する。遅延時間は、ペナルティーがバケットに追加されることを意味する。バケットが一杯になる時、新しいトラフィックは拒否される。漏れがあることにより、トラフィックが軽い時、バケットは、時折の長い時間によって一杯にならないようにする。単純な1つの大きな改良がある。前記銀行の副頭取は、あまりに厳しい‘すべてを掛けた’拒否アルゴリズムを見付け出す。そして、バケットの中の拒否ゾーンを設ける。拒否されるトラフィックの割合は、バケットのビーンレベルより下である拒否ゾーンの割合によって与えられる。例えば、拒否ゾーンは、バケットの上半分であることを想定する。バケットが満杯に対して半分より少ない時、トラフィックは拒否されない。バケットが、満杯の3/4である時、トラフィックの50％は拒否される。バケットが90％満たされている時、トラフィックの80％は、拒否される。バケットが100％の満杯である時、トラフィックの100％が拒否される。
【００１８】
前記トラフィックは、前記バケットレベルによって包括される前記バケット拒否ゾーンの割合に従って拒否される。
【００１９】
ここで、幾つかの複雑な状況を紹介する。平均保留時間が1分の電話サービスは、単純な説明照会サービスがあった。新しいサービスを導入した銀行により、呼ぶ側は新しい説明を利用し、電話で外国通貨などを購入できた。トラフィックを拒否するシステムは、コールがカテゴリーへの分類が実現されるまで細分化する。
【００２０】
コールのタイプ    平均時間*：    コールの95％が*より短い：
説明照会            1分            2分
融資状態照会        2分            4.5分
新しい説明の適用    30分            35分
*  これらの時間は、70％占有率で測定される。
【００２１】
コールが、前記タイプのコールに対して、その‘95％の時間’より長いならば、1つのペナルティーのビーンがバケットに置かれることが、各カテゴリーに対して決定される。
【００２２】
ここで、困難が生じる。放棄申し出のために、電話による新しい説明の適用に氾濫が起こる。平均時間が30分である時、3.3コール/分のコール率は、前記コールセンターの全時間で100名の労働者を占有するのに十分である。前記コールセンターは、完全に、全ての時間を占有される。しかしながら、バケットが一杯にならないことがわかる。
【００２３】
調査研究は、全てのシングルコールは遅れること、そして3.3ビーン/秒がバケットに入ることを示す。しかしながら、バケットは、3.5ビーン/分の割合でまだ漏れ出している。バケットは、ほとんど空のままであって、コールは決して拒否されない。これは、保護メカニズムの故障を示しており、変更されなければならない。
【００２４】
ペナルティーに‘重さ’の要素を与えることが決定され、より多くの時間を消費しているコールは、比較的軽いコールよりも大きなペナルティーを与える。前記重さの要素が選択されると、各個別のタイプのコールに対し、最大コール率（すなわち、前記センターが70％占有される時のコール率）においてバケットに流れるビーンの割合は、正確には、漏れの割合によってバランスがとられる。例えば、コールの100％が新しい説明の適用であると想定する。その時、前記コールセンターは、2.33コール/分のコール率で70％占有される。コールの5％が遅れるならば、その時は、次のことを意味する：
【００２５】
0.05*2.33*ペナルティー=3.5  すなわち、ペナルティー=30
【００２６】
このタイプの全遅延コールに対して、30ビーンは、バケットに置かれなければならない。このタイプのコールが、単純な1分のコールを30回要する時、これは意味をなす。
【００２７】
予想される遅延時間及びペナルティーの両方は、コールのタイプ次第である。前記ペナルティーは、コールのコストに比例している。
【００２８】
SCP/SDPアーキテクチャの数値シミュレーションは、スイッチ制御リーキーバケットロード制御アルゴリズムを調査研究するのに用いられている。このアルゴリズムは、応答時間を予測する1つのサービス内で個々のリードライトの数を考慮している。要求が、その時から遅れてスイッチ制御に戻るならば、その後、ペナルティートークンは、カウンタ（前記バケット）に加えられる。バケットのレベルが固定値より高いならば、新しいトラフィックの部分は拒否される。バケットが完全に一杯になり、全トラフィックが拒否される時、この部分は、バケットレベルと共に上がる。前記バケットは、以下の2つの理由で周期的にトークンを漏らす。
１）軽いトラフィックの期間内に蓄積されるスプリアスのトークンは、漏れ出されなければならない。
２）前記バケットは、トラフィックバーストによって生じる過負荷からそれ自体を漏らすことができなければならない。
【００２９】
このアルゴリズムは、図2及び3に示すアーキテクチャを検査する。図2において、前記SCP及びSDPは、シングルユニックスボックス（Unix box）に属している。図3において、幾つかのデュアルCPUのSCP（C）ボックスは、通信リンクを介して要求を2つのマルチCPUのSDPボックス（マスター及びスレーブ）に送信する。
【００３０】
シングルボックスSCPシミュレーションモデルは、様々なタイプのトラフィックに対するトラフィックレートの関数として応答時間及びプロセッサ占有率を測定するのに用いられる。これらの測定が、前記リーキーバケットアルゴリズムに対する入力データを確立するのにどのように用いられるかを示す。
【００３１】
表1及び2で与えられるソフトウェア処理の予備測定を用いて、単純なシミュレーションモデルが、図3のアーキテクチャに書かれている。前記モデルは、異なるトラフィックタイプに対するトラフィックレートの関数として応答時間及びプロセッサ占有率を測定するためにスイッチを切られた過負荷を用いて実行した。
【００３２】
それは、他の問題を調査するためにも用いた。SDPクライアントソフトウェア処理の数の選択には特定の利益がある。この数は設定可能であって、小さすぎるならば、性能に強く影響し得る。
【００３３】
モデル実行からのデータは、リーキーバケットモデルに対する入力パラメータ、すなわち、異なるサービスのターゲット応答時間及びペナルティーに対する式の係数を順番に計算するのに用いた。この設定データを前記モデルにフィードバックし、その後、‘実際的な’トラフィック混合、SCPの異なる数、及びSDPのCPUの異なる数を含む様々なタイプのトラフィックに使用可能な過負荷を使って前記モデルを実行した。
【００３４】
ターゲット応答時間及びペナルティーは、単純な一次方程式を用いて算出した。これらの方程式に対する係数を見付け出すのに用いた処理について、必須となる測定及び最適な方程式を得るためのテクニックの両方を詳細に述べる。大部分は、この処理について自動化できる。
【００３５】
ペナルティーに対する一次方程式は、全ての状況下で当てはまることが期待される。ターゲット応答時間に対する一次方程式は、後述する一定の場合には細分化する。
【００３６】
プロセッサ占有率が所望の最大値である時、閾値応答時間Ttargetは、応答時間の分布が95％の部分に対応するように選ばれる。‘プロセッサ占有率’という用語が用いられる時、1つのボックスアーキテクチャにおける全占有率、及びマルチボックスアーキテクチャにおけるSDPのCPU占有率を意味する。例えば、所望の最大占有率が66％であることを想定している。前記CPUが66％占有される時、応答時間の95％は、Ttargetよりも少ない。例えば、図4は、前記SCPシミュレーションモデルにおける220コール/秒で実行される1回の読み出しサービスに対する応答時間のヒストグラムを示しており、95％の時間は、およそ120msである。これは、Ttargetに近い。グラフは、実施には、70％のCPU占有率に対応するトラフィックレートの応答時間ヒストグラムを示す。試行錯誤して、正確に66％の占有率を与える前記トラフィックレートを見付けることは困難である。ここで、応答時間Tresponseは、以下の式による占有率の関数として算出される。
【００３７】
Tresponse=T0(nr, nw)+Tr(nr, nw)x占有率/(1-占有率)
【００３８】
ここで、T0(nr, nw)及びTr(nr, nw)は、リードライトの数次第であり、測定されなければならない。動作について第3のカテゴリーが存在し、それは失敗したリード又はライトである。これは、前記アルゴリズムに含まれるが、nrの依存は、以下の議論では無視する。Ttaargetを得るために、所望のCPU占有率に対する占有率は、上式からここでは66％としている。この式を数学的に正当化するよりもむしろ、有効な結果を利用できるデータに対して与えるということが単純に注目される（図5を参照）。詳細は後述する。
【００３９】
バケットに追加されるペナルティートークンの数が、サービスと無関係であるならば、過負荷方式を矛盾無く維持することに明らかな問題が存在する。以下の例を考慮すべきである。1回リードサービスは、応答時間が142msより大きいならば、100のペナルティートークンとする。コール率が66％のCPU占有率に対応する時、応答時間の5％はこれよりも大きい。このトラフィックレートは、1秒に202コールである。202コール/秒で、トークンがバケットに入っていく割合は、0.5x202x100=1000トークン/秒である。その時、バケットは、1000トークン/秒の漏れ率を有することを想定すると、バケットレベルは、毎秒前記トラフィックレートでおおよそ一定であり、漏れ出す時に、同じ数のトークンがバケットに入っていく。前記トラフィックレートが上がるならば、その時、バケットは一杯になり、前記過負荷拒否アルゴリズムは、切り替えられて、トラフィックは、拒否され始める。
【００４０】
ここで、3回リードサービスから成るトラフィックを想像してみる。66％のCPU占有率に対応する前記トラフィックレベルは、おおよそ91コール/秒である。この割合で、同じ‘遅延応答につき100トークン’のルールが適用されたならば、バケットに入っていくトークンの割合は、おおよそ毎秒500である。しかしながら、バケットは、毎秒1000漏れるように設定されている。この場合、バケットが、満たされる限り2倍漏れており、前記トラフィックレベルが最大である時でさえ、前記システムは、過負荷に押し込まれる機会をほとんど有していない。
【００４１】
それゆえ、バケットに追加されるペナルティートークンの数は、サービスのCPUコストに比例せざるをえず、3回リードサービスは、1回リードサービスよりも遅延応答毎に多くのトークンを付け加えなければならない。トークンのサイズに対する式は以下である。
【００４２】
(漏れ率)/[(最大占有率のコール率)x0.05]=トークンサイズ
【００４３】
以下では、1000トークン/秒の漏れ率を想定する。
【００４４】
表1は、SCPシミュレーションモデルにけるnrコール実行（nr=1,...,5）の解析を示す。
【００４５】
表１
2005501316.tif 000003
【００４６】
ここで、RT66は、66％占有率のトラフィックレートであって、コストは以下の式によって与えられる。
【００４７】
コスト=CPUの数 x 1000ms/sec x 占有率/(コール/秒のコール率)
【００４８】
前記コストは、ミリ秒単位で測定される。
【００４９】
この表は、予想されるように、45msの平均（5番のリード値を無視して）でT0がおおよそ一定であり、Tqがリード数の線形関数であること示す。（遅延の解釈として最小自乗法によって算出された）データに対する最適合度は、Tq=27.5n-3.8を与える。しかしながら、図6及び表1を見ると、5番のリードポイントはわずかに離れているように見え、Tqは高すぎるように見え、T0は低すぎるように見えることが分かる。5番のリードポイントを含めないならば、残りの4ポイントは、Tq=22.7n+5.8の式でほとんど完全に適合する。
【００５０】
1つの目的は、式によるターゲット応答時間Ttargetの算出手段を見付けることである。任意数のリード及びCPU占有率に対する95％応答時間の式は、以下の通りである。
【００５１】
Tresponse(n, 占有率)=45+(22.7n+5.8)x(占有率/(1-占有率))
【００５２】
66％の占有率を想定すると、結果は表2になる。この表において、nr=1,2,3,4,5に対する前記表からTtargetを用いた式で算出されたTtarget(n)=45+2(22.7n+5.8)が比較される。[占有率=66%である時、(1-占有率)/占有率=2であることに注目する]。
【００５３】
表２
2005501316.tif 000004
【００５４】
この式の予測出力は悪くないが、式は、nr=5に対して細分化しそうである。単純な一次式は、一般には有効であるのに対して、全てのサービスに対して閾値応答時間を正確に計算するには十分に有効ではなく、ターゲット応答時間は、個別に測定されなければならないと考えられる。次節で、マルチボックスに類似する結論を示す。
【００５５】
nrリードサービスの代わりにnwライトサービスが試験されれば、上記解析全ては、等しく妥当である。すなわち、ライトがリードよりも時間消費が大きいが、占有率及び95％応答時間がコール率の間で同様の関数関係を保つ。
【００５６】
ここで、SCPシミュレーションから‘ロングリード’サービスに対する幾つかのデータが与えられ、それはこれらの目的に対してライトと呼ばれる。
【００５７】
前記モデルは、1回、2回、及び3回ライトに対して幾つかの異なるトラフィックレートで実行した。その時、このデータをリーキーバケットアルゴリズムに対する係数を抽出するために解析した。その際に、高い占有率でのデータポイントは、合理的な適合を得るために除いた（図7）。
【００５８】
事前解析は、全体的に占有率と応答時間の前記コール率の間に存在する一定の関係次第である。SCPシミュレーションデータは、これらの関係に実際に適当に適合することが分かる。前記SCPに収集された実際のデータが同種の関係をモデルとして与えるかどうかを見ることは興味深い。ここで、シングルボックスSCPモデルに収集された幾つかの測定結果により、異なる3つのサービスに対するグラフを示す（図9）。前記データは、1回リード（ベンチマーク5）に対するものであり、1回リード及び1回ライトサービスである（ベンチマークC）。前記第3のサービスは、12回リード及び1回ライトから成る長く高価なサービスであった。前記データは以下に与えられる。グラフは、実際、前記占有率と前記コール率の間に線形関係があり、変数x=占有率/(100-占有率)と前記95％応答時間の間に線形関係があることを示す。
【００５９】
表３
2005501316.tif 000005
【００６０】
図3に示される構成を考慮すると、コールは、前記SCP(C)に到達して、slpに進行する。前記コールが2つのデータベースに1回リード及び1回ライトのアクセスを必要とすると想定する。前記slpは、リード要求を次のsdpクライアント処理に割り当て、kにラベル付けされて、前記要求は待ち行列kに加わる。前記sdpクライアント処理は、前記要求をマスターとスレーブの間を交替している前記SDPの1つに送信する。前記要求は、ソフトウェア処理rcv、sdb-servk、slp-dbak、及びインフォーミックス（Informix）データベースアクセス処理oninitkを通過する。シミュレーションの目的で、各ソフトウェア処理は、データベースアクセスに対するものを除いて固定量のCPU時間がかかると仮定し、この場合、ポアソン分布時間を仮定する。もちろん、前記処理がCPU時間に対して待ち行列に入らなければならない時、前記要求は待ち行列に入る遅延を受ける。様々なソフトウェア処理のタイミングは、SCP/SDPモデルにおいて行い、以下の表4-6に示す。1回リード及び1回リード/1回ライトサービスに対して実行したものである。1回ライトサービスに対するタイミングは、違いを取得することによって推論した。
【００６１】
表４
2005501316.tif 000006
【００６２】
表５
2005501316.tif 000007
【００６３】
表６
2005501316.tif 000008
【００６４】
バケット入力パラメータを算出するために、1、3、5、及び8のリードから成るサービスに対して前記モデルを異なるトラフィックレートで実行した。x=占有率/(1-占有率)の関数として95％応答時間のプロットを図10に示す。
【００６５】
前記1回リード線形適合が非常に有効であることに注目すべきである。その理由は、プロットにおいて、占有率が前記SDPのCPU占有率であるということである。すなわち、前記遅延は、前記SDPのCPU時間に対して待ち行列に入ることから生じると仮定される。しかしながら、1回リードサービスのために、コールのCPUコストが、SCP(C)で4.618ms、SDPで3.19msであって、2CPUパーボックス（cpu-per-box）SCP(C)であるツーボックス（a two-box）における占有率が、2CPUパーボックス（cpu-per-box）SDPであるツーボックス（a two-box）よりも大きいことを意味する。そのため、高いトラフィックに対して、ほとんどの重大である遅延は、前記SCP(C)のCPU時間に対して待ち行列に入ることから生じており、前記SDPの待ち行列に入ることからは生じていない。この効果は、応答時間に対する最適合の式を見付けるプログラムの予測を歪める。データを用いてMathematicaで発生させた表の式及び予測は、（ライト実行からのデータを排除している）図9に示される。（Mathematicaは、Wolfram Reserch Inc所有のソフトウェアプログラムの登録商標である。）：
【００６６】
2005501316.tif 000009
【００６７】
T_95(Ttarget)の予測は、あまり有効ではない。リードされる前記データセットが、入力から排除されているならば、表は以下のようになる。
【００６８】
2005501316.tif 000010
【００６９】
（前記ライトデータは第2のプリントアウトに含まれている。）1回リードの測定がプログラムによって用いられないならば、予測は、他のサービスよりもかなり有用であることが明らかである。問題に対する解決方法は、測定から得られたターゲット応答時間を‘バンド（band）によって’充填し、Mathematica最小自乗適合プログラムを利用して、nrリードターゲット応答時間（nr>1）に対する式を与えて、1回リードサービスを特定の場合として処理することである。この時に、ターゲット値が用いられる。
【００７０】
他方では、前記SCPが前記SDPよりも多く占有されるようにできてはならないということが示されており、トラフィックの実質的割合が、（幾つかのインストール（installations）の場合のように）1回リードサービスによって与えられたならば、より多くのSCPボックスが追加される。これは、同等のコール率における各SCP(C)のCPUのロードを軽くするという固有の効果を有している。テストデータは、4つのSCP(C)ボックスで再実行される。この実行に対して、1回のサービスを有する特別な問題は無い。図11は、有用な線形適合を示し、前記Mathematicaは以下の結果を与える。
【００７１】
2005501316.tif 000011
【００７２】
以下の結論が得られる。サービスのコストが、前記SDPに関するよりも前記SCPに関する方が大きいならば、その時、前記線形最小自乗適合は妥当ではなく、特別な保護がなされなければならない。
【００７３】
サンプルのバケットの実行は、マルチボックスアーキテクチャが存在する場合に2のSCP(C)及びマスター-スレーブSDPを用いてなされる。各ボックスは、2つのCPUを有する。最後のセクションから、バケットのパラメータが以下のように確立された。
【００７４】
Ttarget=11.15xnr+53.60xnw+(11.10xnr+16.21xnw)/(nr+nw)
及び
ペナルティー=0.16+2.4xnr+9.06xnw
【００７５】
前記トラフィックは、以下のコールミックス（callmix）である。
【００７６】
表７
2005501316.tif 000012
【００７７】
表８
2005501316.tif 000013
【００７８】
結果は、図12及び図13に示す。キャリー/オファー(carried/offered)曲線は、ITUによって詳述されるようなパターンに従う。前記応答時間は、トラフィックが拒否され始めるまでトラフィックが上昇すると共に鋭く昇り、約400コール/秒で最大に達し、減衰し始める。前記SLP占有率は、最大に昇り、その後、おおよそ一定を維持する。
【００７９】
前記（シングルボックス）SCPモデルにおけるシミュレーション及び実行の両方は、以下の式が妥当であることを示す（式の故障nrの番号は、前記SCPに符号化される時に、前記アルゴリズムに適合させるためにここに含まれるということに注目すべきである）。
【００８０】
Ttarget(nr, nw, nr)=Tr(nr)+ Tw(nw)+ Tr(nr)+C(nr, nw, nr)
【００８１】
ここで、プロセッサが特定される最大占有率である時、Ttargetは、95％応答時間であって、nrはサービスにおけるリード数、nwはライト数、nfは失敗したリード又はライトの数である。多くの場合、Tr、Tw、及びTfは、それぞれnr、nw、及びnfの線形関数に従う。
【００８２】
すなわち、
2005501316.tif 000014
【００８３】
ここで、Tr、Tw、及びTfは、定数であって、後述の代替式を用いて算出され得る。C(nr,nw,nf)は、（一定又はほとんど一定である）‘平均遮蔽（インターセプト）’である。
【００８４】
C(nr,nw,nf)=(nrcr+nwcw+nfcf)/(nr+nw+nf)
【００８５】
ここで、cr,cw,及びcfは、後述の最小自乗プログラムによっても与えられる。ターゲット応答時間とリードライトの数の間の前記線形関係は、以下の2つの状況において細分化するように思える。
【００８６】
１）トラフィックが、シングルボックスアーキテクチャにおけるリードライトの大きな平均数を有するコールから成る時
２）トラフィックが、マルチボックスアーキテクチャにおけるリードの小さな平均数（1に近い）を有するコールから成る時
【００８７】
これらの2つの場合において、応答時間は、式によって予測されるよりも大きいように思われるため、多少の‘手動による調整’が必要となる。
【００８８】
上述のように、遅延応答後のバケットに残されるペナルティートークンの大きさは、サービス次第でなければならない。ペナルティーに対する式は、
【００８９】
ペナルティー=nrkr+nwkw+nfkf+k0
【００９０】
ここで、kr、kw、kf及びk0は、以下のプログラムにおける代替式を用いて前記SCPモデルの測定から見付けられなければならない。
【００９１】
前記Mathematicaプログラムは、Cで書かれているのに等しく、入力データファイルが読み取られるように、read2,...,write1,write2,...は、様々なサービスに対するコール率、占有率、及び95％応答時間を含んでいる。例えば、前記ファイルread3は以下の形態を有する。
【００９２】
2005501316.tif 000015
【００９３】
これは、2回リードサービスの幾つかの異なる実行に対する前記コール率、CPU占有率、及び95％応答時間である。前記プログラムは、その時、Ttargetに対する式に従って所望の最大占有率（maxocc）での前記サービスのために、前記ペナルティー及び95％の応答時間の各サービスに対する算出を行う。その時、Ttarget及びペナルティーに対する最適な一次式を見付けるためにこれらの値を用いる。詳細には、それは、kr、kw、kf及びその（一次近似）Ttargetの式を与える。多くの状況では、この方法によって与えられる前記パラメータは、直接的に前記SCPに対する構成データに入力され得る。
【００９４】
前記SCP数値モデルからのデータは、最適な曲線を見付け出すために最小自乗法を用いて解析した。
【００９５】
nデータポイントを考慮すると、(x1,y1), (x2,y2),..., (xi,yi),..., (xn,yn)となる。
【００９６】
変数x及びyは、線形関係y=a+bxであると仮定し、ここで、a及びbは定数である。個々のデータポイントは、誤りに対する測定の対象であって、必ずしも直線に沿って傾斜する必要はないが、ランダム分散の量は少ない（図14参照）。
【００９７】
前記最適曲線は、そのポイントから曲線までの距離の2乗の和を最小にするものであって、y=a+bxによって与えられ、ここで、a及びbは以下によって与えられる。
【００９８】
2005501316.tif 000016
【００９９】
ここで、バーを付された数は、x及びyの値の通常の平均値である。
【０１００】
前記応答時間TRは、発行されるデータベース要求と受信される応答メッセージの間の時間であって、3つの部分に細分化され得る。第1の部分は、要求/応答の往復移動時間のための固定時間である。第2の時間は、データベースによってかかる（変化する）時間である。アクセス時間が、固定される平均でポアソン分布に従うことを仮定することができる。第3に、待ち行列の遅延がある。前記データベースが、1回で2以上のコールを扱うならば、待ち行列においてそれよりも前に処理される間、要求は待たなければならない。これら3つの遅延は、T1、T2、T3であるならば、その時、
（平均応答時間）=T{MR}=T1+T2+T3
【０１０１】
T1及びT2は、定数であって、測定され得る。重要なのはT3を見積もることにあり、それは待ち行列の長さ次第である。
【０１０２】
一般的な待ち行列のシステムを考える。顧客が到達し、待ち行列で待ち、そして供給される。割合λのポアソン到着及び割合μのポアソン分布のサービス時間が存在すると仮定するらならば、その時、前記待ち行列の時間は、以下によって与えられる。
【０１０３】
Tqueueing={1/μ}{λ/μ/(1-λ/μ)}
【０１０４】
しかしながら、ポアソン分布のトラフィックに対して、前記割合λ及びμは、内部到達時間及びサービス時間についてそれぞれ相互に等しい。そのため、式は以下のようになる。
Tqueueing=Ts{Ts/Tia/(1-Ts/Tia)}
【０１０５】
このシステムに対して、Tsは1つのデータベースアクセスの平均時間であり、Tiaは要求の内部到達時間である。プロセッサがデータベースアクセスのみを行っており、事実上他は何もしていないと仮定すると、Ts/Tiaは、プロセッサが動作している単純な時間の割合であり、すなわち占有率である。そのため、前記待ち行列の時間は、以下のようになる。
【０１０６】
T3=Tqueueing=Tsx占有率/(1-占有率)
T1+T2=T0かつTsをTqによって置換するならば、その時、式は以下のようになる。
TR=T0(m,n)+ Tq(m,n)x占有率/(1-占有率)
【０１０７】
導出は平均遅延にあてはまるが、少なくとも概算で95％遅延に対しても妥当であるように思われる。
【０１０８】
ここで、前記ペナルティートークンのサイズがサービスに対してどのように算出されるかに関してより十分に説明をする。CPUの所望の最大占有率を（66％に上記の例で設定された）maxoccにする。個々のサービスに対しては、maxoccのCPU占有率に対応するコール率は、データの最小自乗解析から推定される。（占有率が、コールが無くても前記CPUを占有する背景タスクが存在する時、前記コール率に単純に比例していないことに注目すべきである。）最初の式から、前記ペナルティートークンは、前記コール率に反比例する。それゆえ、以下のようになる。
【０１０９】
(n回リードに対するペナルティー)/(1回リードに対するペナルティー)=(1回リードに対する最大コール率)/(n回リードに対する最大コール率)
【０１１０】
前記ペナルティーは、サービスの‘コスト’によって同等に表され、それは、サービスがミリ秒単位でのCPUにかかる時間である。明確には、前記コール率、コスト、及び占有率は、以下の関係を有する。
【０１１１】
コール率x(コスト/1000)=(占有率/100)
ここで、占有率は、（0.0から100.0の間の）パーセントである。上式により、
ペナルティー=漏れ率x(最大占有率/100)x(1回リードのコスト/1000)
【０１１２】
ここで、コストは、ミリ秒の単位であって、最大占有率は、0.0から100.0の間である。コストが、以下に与えられるサービスnrのリード数の一次関数であることは、直感的に明らかであると思われる。
ペナルティー=k0+krnr
ここでk0及びkrは、測定される定数である。上式から、krは以下のようになる。
kr=漏れ率x(最大占有率/100)x(1回リードのコスト/1000)
k0は、データベースアクセスなくサービスのコストを用いて（概算で）算出されるペナルティーである。ksを直接的に測定することが必ずしも必要であるとは限らないが、異なるサービスに対する測定又は占有率対コール率からそれらを算出することを必要とする。
【０１１３】
上記は、nrリードを用いたサービスに関して集中してきたが、その議論は、リード、ライト、及び失敗を有するより一般的なサービスに延長され得るものである。最終的な式は、以下のようになる。
ペナルティー= nrkr+nwkw+nfkf+k0
【図面の簡単な説明】
【０１１４】
【図１】本発明のファンクションを例証する“リーキーバケット”のグラフ表示を示す。
【図２】シミュレーション用に想定したシングルボックスSCPアーキテクチャを例証する。
【図３】シミュレーション用に想定したマルチボックスSCP(C)/SDPアーキテクチャを例証する。
【図４】応答時間分布のヒストグラム例を示す。シングルボックスSCPシミュレーションで7約70％のプロセッサ占有率で実行される1回リードサービスの応答時間msを表している。
【図５】x=1が50％占有率に対応する変数x=占有率/（1-占有率）とy=95%応答時間msの間の線形関係を例証する。
【図６】リードnr=1,2,3,4,5の数と95％‘待ち行列’時間Tqの間の線形関係を例証する。
【図７Ａ】シングルボックスSCPシミュレーションにおける1回ライトサービスを例証する。前記SCPシミュレーションで測定されるデータに対して、変数x=占有率/（100-占有率）と95％応答時間ms（y軸）の間の関係は、近似の線形関係である。
【図７Ｂ】シングルボックスSCPシミュレーションにおける1回ライトサービスを例証する。前記SCPシミュレーションで測定されるデータに対して、変数x=占有率/（100-占有率）と95％応答時間ms（y軸）の間の関係は、近似の線形関係である。
【図８Ａ】2回ライトサービス（８Ａ）及び3回ライトサービス（８Ｂ）を用いて図７Ａ及び図７Ｂにおけるような線形適合を例証する。
【図８Ｂ】2回ライトサービス（８Ａ）及び3回ライトサービス（８Ｂ）を用いて図７Ａ及び図７Ｂにおけるような線形適合を例証する。
【図９Ａ】1回リードサービスにおけるリアルシングルボックスSCPで測定されるデータに対して、変数x=占有率/（100-占有率）と95％応答時間ms（y軸）の間の近似の線形関係を例証する。
【図９Ｂ】1回ライト、1回ライトサービスにおけるリアルシングルボックスSCPで測定されるデータに対して、変数x=占有率/（100-占有率）と95％応答時間ms（y軸）の間の近似の線形関係を例証する。
【図９Ｃ】12回リード、1回ライトサービスにおけるリアルシングルボックスSCPで測定されるデータに対して、変数x=占有率/（100-占有率）と95％応答時間ms（y軸）の間の近似の線形関係を例証する。
【図１０Ａ】1、3、5、及び8回リードそれぞれに対する95％時間遅延（y軸）対占有率/（1-占有率）（x軸）を例証する。占有率は、（マスター）SDPのCPU占有率であって、その構成は、2SCP(C)（各2プロセッサ）及び2SDP（マスター/スレーブ）（各2プロセッサ）である。
【図１０Ｂ】1、3、5、及び8回リードそれぞれに対する95％時間遅延（y軸）対占有率/（1-占有率）（x軸）を例証する。占有率は、（マスター）SDPのCPU占有率であって、その構成は、2SCP(C)（各2プロセッサ）及び2SDP（マスター/スレーブ）（各2プロセッサ）である。
【図１０Ｃ】1、3、5、及び8回リードそれぞれに対する95％時間遅延（y軸）対占有率/（1-占有率）（x軸）を例証する。占有率は、（マスター）SDPのCPU占有率であって、その構成は、2SCP(C)（各2プロセッサ）及び2SDP（マスター/スレーブ）（各2プロセッサ）である。
【図１０Ｄ】1、3、5、及び8回リードそれぞれに対する95％時間遅延（y軸）対占有率/（1-占有率）（x軸）を例証する。占有率は、（マスター）SDPのCPU占有率であって、その構成は、2SCP(C)（各2プロセッサ）及び2SDP（マスター/スレーブ）（各2プロセッサ）である。
【図１１】1回リードに対する95%時間遅延（y軸）対占有率/（1-占有率）（x軸）を例証する。その構成は、4SCP(C)（各2プロセッサ）及び2SDP(C)（マスター/スレーブ）（各2プロセッサ）である。
【図１２Ａ】リーキーバケット及びトラフィックミックスAの性能を例証する。キャリートラフィック（y軸）対オファーと他フィック（x軸）（コール/秒）を示す。
【図１２Ｂ】リーキーバケット及びトラフィックミックスAの性能を例証する。手段応答時間（ms）対オファートラフィックレート（コール/秒）を示す。
【図１２Ｃ】リーキーバケット及びトラフィックミックスAの性能を例証する。オファートラフィックレート（コール/秒）の関数としてSCP（マスター）CPU占有率（％）を示す。
【図１３Ａ】リーキーバケット及びトラフィックミックスBの性能を例証する。キャリートラフィック（y軸）対オファートラフィック（x軸）（コール/秒）を示す。
【図１３Ｂ】リーキーバケット及びトラフィックミックスBの性能を例証する。手段応答時間（ms）対オファートラフィックレート（コール/秒）を示す。
【図１３Ｃ】リーキーバケット及びトラフィックミックスBの性能を例証する。オファートラフィックレート（コール/秒）の関数としてSCP（マスター）CPU占有率（％）を示す。
【図１４Ａ】生データのプロットが、x及びyの間の線形関係を示すことを例証する。
【図１４Ｂ】図１４Ａのポイントを介して、最適合グラフy=a+bxをプロットするために用いられている最小自乗の式を例証する。
【図１】
2005501316.tif 000017
【図２】
2005501316.tif 000018
【図３】
2005501316.tif 000019
【国際公開パンフレット】
2005501316.tif 000020
2005501316.tif 000021
2005501316.tif 000022
2005501316.tif 000023
2005501316.tif 000024
2005501316.tif 000025
2005501316.tif 000026
2005501316.tif 000027
2005501316.tif 000028
2005501316.tif 000029
2005501316.tif 000030
2005501316.tif 000031
2005501316.tif 000032
2005501316.tif 000033
2005501316.tif 000034
2005501316.tif 000035
2005501316.tif 000036
2005501316.tif 000037
2005501316.tif 000038
2005501316.tif 000039
2005501316.tif 000040
2005501316.tif 000041
2005501316.tif 000042
2005501316.tif 000043
2005501316.tif 000044
2005501316.tif 000045
2005501316.tif 000046
2005501316.tif 000047
2005501316.tif 000048
2005501316.tif 000049
2005501316.tif 000050
2005501316.tif 000051
2005501316.tif 000052
2005501316.tif 000053
2005501316.tif 000054
2005501316.tif 000055
【国際公開パンフレット（コレクトバージョン）】
2005501316.tif 000056
2005501316.tif 000057
【国際調査報告】
2005501316.tif 000058
2005501316.tif 000059