(57)【要約】【課題】負荷分散や輻輳制御などの適切な対策を早期に行うことができるノード管理装置を提供する。【解決手段】ノード管理装置１１は、互いに連携して要求を処理する複数のノード１５1〜１５nについて、各ノードが要求を処理した際の処理負荷と要求のノード間の遷移を分析する分析部１２と、処理負荷および遷移の分析結果に基づいて、所望の要求数に対する各ノードの処理負荷を予測する予測部１３と、を有する。【選択図】図１
2019067087.tif 000002
【特許請求の範囲】
【請求項１】
互いに連携して要求を処理する複数のノードについて、各ノードが前記要求を処理した際の処理負荷と前記要求のノード間の遷移を分析する分析部と、
前記処理負荷および遷移の分析結果に基づいて、所望の要求数に対する各ノードの処理負荷を予測する予測部と、を有する、ノード管理装置。
【請求項２】
前記分析部は、ノードが前記要求を処理した際の処理負荷と、該ノードにて処理された要求の遷移先を示す遷移先ノード情報とを集計し、該集計結果に基づいて、前記処理負荷および遷移先の傾向を分析する、請求項１に記載のノード管理装置。
【請求項３】
前記分析部は、ノード間の前記要求の単位処理負荷毎の遷移確率を算出し、
前記予測部は、前記要求の遷移確率に基づいて、各ノードの処理負荷を予測する、請求項１または２に記載のノード管理装置。
【請求項４】
前記分析部は、前記複数のノードについて、各ノード間を遷移した要求数を単位処理負荷毎にカウントし、該カウント値に基づいて遷移確率行列を算出し、
前記予測部は、前記遷移確率行列に基づいて、各ノードの処理負荷を予測する、請求項３に記載のノード管理装置。
【請求項５】
ノード毎に、前記予測部で予測した処理負荷の予測値と許容値とを比較し、予測値が許容値を超えている場合に、所定のメッセージを出力する対策部を、さらに有する、請求項１乃至４のいずれか一項に記載のノード管理装置。
【請求項６】
前記対策部は、前記予測値が前記許容値を超えたノードの処理負荷を低減するための対策を示すメッセージを出力する、請求項５に記載のノード管理装置。
【請求項７】
互いに連携して要求を処理する複数のノードについて、各ノードが前記要求を処理した際の処理負荷と前記要求のノード間の遷移を分析し、
前記処理負荷および遷移の分析結果に基づいて、所望の要求数に対する各ノードの処理負荷を予測することを含む、ノード管理方法。
【請求項８】
互いに連携して要求を処理する複数のノードについて、各ノードが前記要求を処理した際の処理負荷と前記要求のノード間の遷移を分析する処理と、
前記処理負荷および遷移の分析結果に基づいて、所望の要求数に対する各ノードの処理負荷を予測する処理と、をコンピュータに実行させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、互いに連携して要求を処理する複数のノードを管理する、ノード管理装置、ノード管理方法及びプログラムに関する。
【背景技術】
【０００２】
互いに連携して要求を処理する複数のノードからなるシステムの一例として、分散処理システムが知られている。この分散処理システムでは、各ノードの負荷の偏りを防ぎ、全体的な処理の効率性を保つため、負荷分散が行われる。負荷分散には、静的負荷分散と動的負荷分散がある。前者は、事前に定めた割り振りで処理をノードに割り当てる方法である。また、後者は、ノードの負荷を監視して、負荷の軽いノードに処理を割り当てる方法である。一般に、動的負荷分散の方が、静的負荷分散よりも実状に応じた負荷分散が期待される。
【０００３】
分散処理システムの一例として、特許文献１に、生産ラインの全行程を管理する生産管理システムが記載されている。この生産管理システムでは、所要に対し、在庫又は仕掛完成予定を製品在庫から順次、源流工程に向けて工程毎に引当て、各工程の在庫又は引当分、余剰分、不足分を確定する。不足分について仕込換算を行って、要仕込分の要仕込日及び要仕込数を求める。そして、引当分と要仕込分とを源流工程から下流工程に向けて負荷山積し、各工程の仕込予定日と完成予定日を求める。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特開平１１−４８１０２号公報
【発明の概要】
【発明が解決しようとする課題】
【０００５】
上述した分散処理システムでは、予め定めた割り振りで処理をノードに割り当てるが、実際に要求を処理した場合の各ノードの処理負荷を予測することはできない。このため、ノードに対する対処が間に合わず、過負荷を生じる場合がある。また、必要以上に負荷を軽減してしまう場合もある。
特許文献１に記載の生産管理システムにおいても、処理負荷の予測はできないため、上記の分散処理システムと同様の問題を生じる。
【０００６】
本発明の目的は、上記問題を解決することができる、ノード管理装置、ノード管理方法及びプログラムを提供することである。
【課題を解決するための手段】
【０００７】
上記目的を達成するため、本発明の第１のノード管理装置は、互いに連携して要求を処理する複数のノードについて、各ノードが前記要求を処理した際の処理負荷と前記要求のノード間の遷移を分析する分析部と、前記処理負荷および遷移の分析結果に基づいて、所望の要求数に対する各ノードの処理負荷を予測する予測部と、を有する。
【０００８】
本発明の第１のノード管理方法は、互いに連携して要求を処理する複数のノードについて、各ノードが前記要求を処理した際の処理負荷と前記要求のノード間の遷移を分析し、
前記処理負荷および遷移の分析結果に基づいて、所望の要求数に対する各ノードの処理負荷を予測することを含む。
【０００９】
本発明の第１のプログラムは、互いに連携して要求を処理する複数のノードについて、各ノードが前記要求を処理した際の処理負荷と前記要求のノード間の遷移を分析する処理と、前記処理負荷および遷移の分析結果に基づいて、所望の要求数に対する各ノードの処理負荷を予測する処理と、をコンピュータに実行させる。
【発明の効果】
【００１０】
過負荷や低負荷のノードを推定し、負荷分散や輻輳制御などの適切な対策を早期に行うことができる。
【図面の簡単な説明】
【００１１】
【図１】本発明の第１の実施形態によるノード管理装置の構成を示すブロック図である。
【図２】本発明の第２の実施形態によるノード管理装置の構成を示すブロック図である。
【図３】図２に示すノード管理装置にて行われるノード管理処理の一手順を示すフローチャートである。
【図４】処理負荷と遷移先ノード情報の集計結果の一例を説明するための図である。
【図５】各ノード間を遷移した要求数のカウント値の一例を説明するための図である。
【図６】要求がノード間を遷移する遷移確率の算出処理の一例を説明するための図である。
【図７】遷移確率行列を用いた予測の一例を説明するための図である。
【図８】遷移確率調整用テーブルの一例を説明するための図である。
【発明を実施するための形態】
【００１２】
次に、本発明の実施形態について図面を参照して説明する。
（第１の実施形態）
図１は、本発明の第１の実施形態によるノード管理装置の構成を示すブロック図である。なお、図１において、一方向性の矢印は、ある信号（データ又は情報）の流れの方向を端的に示したもので、双方向性を排除するものではない。
図１を参照すると、ノード管理装置１１は、分析部１２及び予測部１３を有する。分析部１２は、互いに連携して要求を処理する複数のノード１５1〜１５nについて、各ノードが要求を処理した際の処理負荷と要求のノード間の遷移を分析する。予測部１３は、分析部１２からの処理負荷及び遷移の分析結果に基づいて、所望の要求数ｗに対する各ノードの処理負荷を予測する。
【００１３】
上述したノード管理装置１１によれば、所望の要求数ｗに対する各ノードの処理負荷を定量的に予測することができるので、過負荷のノードや低負荷のノードを推定し、負荷分散や輻輳制御などの適切な対策を早期に行うことができる。
【００１４】
なお、ノード管理装置１１において、分析部１２及び予測部１３のそれぞれの機能を有する１つの制御部が設けられても良い。また、その制御部は、ＣＰＵ（Central Processing Unit）等を具備したコンピュータで実現されても良い。この場合、コンピュータがプログラムを実行することで、分析部１２及び予測部１３のそれぞれの機能を実現しても良い。
【００１５】
プログラムは、分析部１２及び予測部１３のそれぞれの機能に対応する処理をコンピュータが実行するためのものであっても良い。例えば、プログラムは、互いに連携して要求を処理する複数のノード１５1〜１５nについて、ノードが要求を処理した際の処理負荷と、要求のノード間の遷移とを分析する処理と、処理負荷及び遷移の分析結果に基づいて、所望の要求数に対する各ノードの処理負荷を予測する処理とを、コンピュータが実行するためのものであっても良い。プログラムは、コンピュータ使用可能媒体またはコンピュータ可読媒体で提供されてもよく、また、インターネット等のネットワークを介して提供されてもよい。
【００１６】
コンピュータ使用可能媒体またはコンピュータ可読媒体は、磁気、光、電子、電磁気、赤外線などを用いて情報の記録または読み取りが可能な媒体を含む。そのような媒体として、例えば、半導体メモリ、半導体または固体の記憶装置、磁気テープ、取外し可能なコンピュータディスケット、ランダムアクセスメモリ（ＲＡＭ）、読出し専用メモリ（ＲＯＭ）、磁気ディスク、光ディスク、光磁気ディスクなどがある。
【００１７】
また、ノード管理装置１１において、分析部１２は、ノード１５1〜１５nについて、ノードが要求を処理した際の処理負荷と、該ノードにて処理された要求の遷移先を示す遷移先ノード情報とを集計し、その集計結果に基づいて、処理負荷および遷移先の傾向を分析しても良い。
さらに、分析部１２が、ノード間の前記要求の遷移確率を算出し、予測部１３が、要求の遷移確率に基づいて、各ノードの処理負荷を予測しても良い。
さらに、分析部１２が、ノード１５1〜１５nについて、各ノード間を遷移した要求数を単位処理負荷毎にカウントし、該カウント値に基づいて遷移確率行列を算出し、予測部１３が、遷移確率行列に基づいて、各ノードの処理負荷を予測しても良い。
【００１８】
また、ノード管理装置１１において、ノード毎に、予測部１３で予測した処理負荷の予測値と許容値とを比較し、予測値が許容値を超えている場合に、所定のメッセージを出力する対策部を、さらに有しても良い。所定のメッセージは、例えば警告を示すメッセージであっても良い。
さらに、対策部が、予測値が許容値を超えたノードの処理負荷を低減するための対策メッセージを出力しても良い。この場合、対策は、処理負荷の改善、許容値の緩和、要求数の緩和および遷移確率の低減のいずれか一つ、または、２つ以上の組み合わせであっても良い。
【００１９】
（第２の実施形態）
図２は、本発明の第２の実施形態によるノード管理装置の構成を示すブロック図である。なお、図２において、一方向性の矢印は、ある信号（データ又は情報）の流れの方向を端的に示したもので、双方向性を排除するものではない。
図２を参照すると、ノード管理装置２１は、分散処理システム１０の処理負荷の予測及び監視を行う装置であって、遷移検出部２２、遷移集計分析部２３、処理負荷予測部２４、要求数取得部２５、対策算出部２６及び許容負荷取得部２７を有する。遷移集計分析部２３、または、遷移検出部２２と遷移集計分析部２３とからなる部分を、分析部と呼ぶことができる。処理負荷予測部２４及び要求数取得部２５を、予測部と呼ぶことができる。対策算出部２６及び許容負荷取得部２７を、対策部と呼ぶことができる。
【００２０】
分散処理システム１０は、互いに連携して要求（要求数＝ｗ）を処理する複数のノード１〜５を有する。ここでは、ノード１〜５のそれぞれに対して、特定の処理が割り当てられている。要求は、一連の処理から成り、処理に応じたノードで処理される。要求は、あるノードでの処理が終わると、次に行う処理が確定し、対応する次のノードに遷移する。要求は、処理と遷移を繰り返して、有限時間内に全ての処理が完了する。要求を処理する際のノードの処理負荷は、計測または推定できるものとする。
【００２１】
遷移検出部２２は、要求のノード間における遷移を検出する。遷移検出結果は、遷移検出部２２から遷移集計分析部２３に供給される。
遷移集計分析部２３は、ノード１〜５について、ノードが要求を処理した際の処理負荷と、該ノードにて処理された要求の遷移先を示す遷移先ノード情報とを集計する。例えば、遷移集計分析部２３は、処理負荷の単位量ごとに離散的に、各要求がどのノードで処理されていたかを示す情報を集計しても良い。遷移集計分析部２３は、処理負荷と遷移先ノード情報の集計結果に基づいて、処理負荷および遷移先の傾向を分析する。遷移集計分析部２３は、分析結果を処理負荷予測部２４に供給する。
【００２２】
なお、遷移検出部２２は、各ノードに対して、それぞれの処理負荷と遷移先ノード情報を問合せても良い。あるいは、各ノードが自発的に、自ノードの処理負荷と遷移先ノード情報とを遷移検出部２２に報告しても良い。あるいは、遷移検出部２２が、各ノードの通信を監視して、要求の処理開始のタイミングや、要求の受け渡しを検出することで、処理負荷及び遷移先ノード情報の集計を行っても良い。
【００２３】
要求数取得部２５は、ノード１〜５で処理させる要求数を取得する。例えば、要求数取得部２５は、各ノードに想定される要求数の入力を受け付けても良い。要求数取得部２５は、取得した要求数を処理負荷予測部２４に供給する。
処理負荷予測部２４は、遷移集計分析部２３からの分析結果に基づいて、所望の要求数に対する各ノードの処理負荷を予測する。所望の要求数は、要求数取得部２５から供給される。処理負荷予測部２４は、各ノードの処理負荷の予測値を対策算出部２６に供給する。
【００２４】
許容負荷取得部２７は、ノード１〜５の処理負荷の許容値を取得する。例えば、許容負荷取得部２７は、処理負荷の許容値の入力を受け付けても良い。許容負荷取得部２７は、取得した許容値を対策算出部２６に供給する。
対策算出部２６は、ノード毎に、処理負荷の予測値と許容値とを比較する。予測値が許容値を超えた場合、対策算出部２６は、警告メッセージを出力するとともに、ノードに対する対策を算出し、その対策を示すメッセージを出力する。対策算出部２６は、通知部と呼ぶことができる。
【００２５】
次に、本実施形態のノード管理装置２１の動作について具体的に説明する。
図３は、ノード管理装置２１にて行われるノード管理処理の一手順を示すフローチャートである。
【００２６】
まず、遷移検出部２２が要求のノード間の遷移を検出する。そして、遷移集計分析部２３が、各ノードの処理負荷と遷移先ノード情報を集計する（ステップＳ１０）。
次に、遷移集計分析部２３が、ステップＳ１０で得られた集計結果に基づいて、各ノードの処理負荷及び遷移先の傾向を分析する（ステップＳ１１）。次に、処理負荷予測部２４が、ステップＳ１１で得られた処理負荷及び遷移先の傾向分析結果に基づいて、要求数取得部２５が取得した要求数に対する各ノードの処理負荷を予測する（ステップＳ１２）。
【００２７】
次に、対策算出部２６が、各ノードについて、ステップＳ１２で得られた処理負荷の予測値が、許容負荷取得部２７が取得した許容値より大きいか否かを判定する（ステップＳ１３）。予測値が許容値より大きい場合に、対策算出部２６が、警告メッセージを出力するとともに、ノードに対する対策を算出し、その対策を示すメッセージを出力する。
【００２８】
以下に、処理負荷と遷移先ノード情報の集計処理（ステップＳ１０）、処理負荷及び遷移先の傾向分析処理（ステップＳ１１）、処理負荷の予測処理（ステップＳ１２）及び警告／対策算出処理（ステップＳ１４）を詳細に説明する。
以下では、ノードの処理負荷の尺度として、処理時間を用いる。すなわち、ノード間を遷移する要求を分析する際に、単位処理負荷として単位処理時間を用いる。これとは異なるケースとして、処理負荷を例えば通信量で評価する場合は、単位処理負荷として単位通信量を用いれば良い。
【００２９】
処理負荷と遷移先ノード情報の集計処理（ステップＳ１０）
図４に、処理負荷と遷移先ノード情報の集計結果の一例を示す。図４において、「ａ」、「ｂ」、「ｃ」はそれぞれ要求を示す。図４の集計結果は、要求ａ〜ｃが、ノード１〜５のいずれで処理されていたかを示す情報を処理順に単位処理時間毎に集計したものである。この例では、処理負荷を処理時間で評価するものとして、遷移集計分析部２３は、要求の遷移についての情報を各ノードにおける単位処理時間毎に集計する。
【００３０】
ノード１は、累計処理時間(以下、時刻)０から要求ａを処理し、時刻３で要求ｂを処理し、時刻４及び５で要求ｃを処理する。ノード２は、時刻１で要求ａを処理し、時刻６で要求ｃを処理する。ノード３は、時刻２で要求ａを処理し、時刻４で要求ｂを処理し、時刻７及び９で要求ｃを処理する。ノード４は、時刻３で要求ａを処理し、時刻８及び１０で要求ｃを処理する。ノード５は、時刻４で要求ａを処理し、時刻５で要求ｂを処理し、時刻１１で要求ｃを処理する。
【００３１】
時刻がtからt+1になった時、あるノードから別のノードに移った要求は、あるノードでの処理がその単位処理時間内で終わり、次のノードへ遷移したことを示す。例えば、時刻０でノード１が要求ａを処理し、時刻１でノード２が要求ａを処理している。この場合、要求ａは、単位処理時間を跨いでノードを移った要求である。
また、時刻がtからt+1になっても、あるノードに留まった要求は、あるノードでの処理が単位処理時間内に終わらず、ノードを遷移しなかったことを示す。例えば、ノード１は、時刻４及び５で要求ｃを処理している。この場合、要求ｃは、単位処理時間を跨いで同じノードに留まった要求である。
【００３２】
上記の処理負荷と遷移先ノード情報の集計処理（ステップＳ１０）は、以下で説明する処理負荷と遷移先の傾向を分析する処理（ステップＳ１１）までにすれば良い。つまり、単位処理時間毎に定期的に行なっても良く、遷移の度に逐次的に行なっても良く、あるいは、ステップ１１の直前に一括して行なっても良い。
【００３３】
処理負荷及び遷移先の傾向分析処理（ステップＳ１１）
遷移集計分析部２３は、分析結果として遷移確率行列を算出する。すなわち、遷移集計分析部２３は、あるノードで要求が単位処理負荷の処理を受けた後、次のノードへ遷移する遷移確率行列を算出する。
例えば、遷移集計分析部２３は、各ノード間を遷移した要求数を、単位処理負荷ごとにカウントし、該カウント値に基づいて遷移確率行列を算出する。以下の例で、この遷移確率行列の算出処理を具体的に説明する。
以下の例では、前述の例で示した、処理負荷(処理時間)と遷移先ノード情報の集計結果を用いる。したがって、処理負荷を処理時間で評価するものとする。
【００３４】
［要求がノードｉからノードｊへ遷移した回数の算出］
図５に、各ノード間を遷移した要求数のカウント値の一例を示す。単位処理時間毎に要求がノードｉからノードｊへ遷移した回数を累積する遷移カウンタＣｉｊを用いて、図４に示した集計結果に基づく要求数をカウントした結果が示されている。ここで、ｉ及びｊは、分散処理システム１０を構成するノードの数の範囲内で与えられる。
【００３５】
図５において、遷移カウンタＣiiは、要求がノードiからノードiに遷移した回数、すなわち、要求がノードiに留まった回数をカウントする。図４の集計結果では、要求ｃが累計処理時間(以下、時刻)４及び５でノード１に留まっているため、時刻４で、遷移カウンタＣ１１のカウント値が「１」になる。これ以降、時刻１１まで、遷移カウンタＣ１１はカウント値「１」を維持する。
【００３６】
遷移カウンタＣijは、要求がノードiからノードjに遷移した回数をカウントする。図４の集計結果では、時刻０から１にかけて、要求ａがノード１からノード２に遷移しているため、時刻０での遷移カウンタＣ12のカウント値を「１」としている。これ以降、時刻４まで、遷移カウンタＣ12はカウント値「１」を維持する。また、時刻５から６にかけて、要求ｃがノード１からノード２に遷移しているため、時刻５での遷移カウンタＣ12のカウント値を「２」にする。これ以降、時刻１１まで、遷移カウンタＣ12はカウント値「２」を維持する。
【００３７】
図５のその他の遷移カウンタＣ１３〜Ｃ１５、Ｃ２１〜Ｃ２５、Ｃ３１〜Ｃ３５、Ｃ４１〜Ｃ４５、Ｃ５１〜Ｃ５５も、遷移カウンタＣ１１又は遷移カウンタＣ１２と同様の原理で、図４の集計結果に基づいて要求のノード間の遷移をカウントする。
【００３８】
［要求がノードｉからノードｊへ遷移する遷移確率の算出］
図６に、要求がノード間を遷移する遷移確率の算出処理の一例を示す。この例では、図５に示したカウント結果に基づいて、要求がノードｉからノードｊへ遷移する遷移確率Ｐｉｊを算出した結果が示されている。
【００３９】
要求が遷移元ノードから遷移先ノードへ遷移する遷移確率Pijは、遷移元ノードiから遷移先ノードjへ遷移した要求数を、その遷移元ノードiから遷移した全要求数で割った値（確率値）として求められる。
図６において、Ｐ１１は、要求がノード１からノード１へ遷移する確率、すなわち、要求がノード１に留まる確率を示す。遷移確率Ｐ１１は、ノード１に留まった要求数を、ノード１からから遷移した全要求数で割った値で与えられる。すなわち、遷移確率Ｐ１１は、遷移カウンタＣ１１のカウント結果「１」を遷移カウンタＣ１１〜Ｃ１５のカウント結果の合計値「４」（＝Ｃ１１＋Ｃ１２＋Ｃ１３＋Ｃ１４＋Ｃ１５＝１＋２＋１＋０＋０）で割った値（＝１／４）である。
【００４０】
Ｐ１２は、要求がノード１からノード２へ遷移する確率を示す。遷移確率Ｐ１２は、ノード１からノード２へ遷移した要求数を、ノード１からから遷移した全要求数で割った値で与えられる。すなわち、遷移確率Ｐ１２は、遷移カウンタＣ１２のカウント結果「２」を遷移カウンタＣ１１〜Ｃ１５のカウント結果の合計値（＝Ｃ１１＋Ｃ１２＋Ｃ１３＋Ｃ１４＋Ｃ１５＝１＋２＋１＋０＋０）で割った値（＝１／２）である。
図６のその他の遷移確率Ｐ１３〜Ｐ１５、Ｐ２１〜Ｐ２５、Ｐ３１〜Ｐ３５、Ｐ４１〜Ｐ４５、Ｐ５１〜Ｐ５５についても、遷移確率Ｐ１１又は遷移確率Ｐ１２と同様の原理で、図５のカウント結果に基づいて算出される。
【００４１】
［遷移確率行列］
上述の遷移確率Ｐ１１〜Ｐ１５、Ｐ２１〜Ｐ２５、Ｐ３１〜Ｐ３５、Ｐ４１〜Ｐ４５、Ｐ５１〜Ｐ５５に基づき、以下の遷移確率行列
【数１】
2019067087.tif 000003
を得る。
【００４２】
【数２】
2019067087.tif 000004
この遷移確率行列
【数３】
2019067087.tif 000005
では、遷移元ノードが同じ遷移確率どうしを同じ列に配置し、遷移先ノードが同じ遷移確率どうしを同じ行に配置している。
【００４３】
処理負荷の予測処理（ステップＳ１２）
処理負荷予測部２４は、遷移集計分析部２３が算出した遷移確率行列
【数４】
2019067087.tif 000006
を用いて、所望の要求数に対する各ノードの処理負荷を予測する。例えば、処理負荷予測部２４は、ノードの処理負荷、すなわち各ノードに遷移する要求の総数を、遷移確率行列
【数５】
2019067087.tif 000007
を用いて期待値として予測する。以下の例では、前述の例で求めた遷移確率行列を用いて、この予測を行なう処理を具体的に説明する。
【００４４】
図７に、遷移確率行列
【数６】
2019067087.tif 000008
を用いた予測の一例を示す。この例では、ノード１〜５にそれぞれ、
【数７】
2019067087.tif 000009
個の要求が投入されると要求数取得部25によって想定されたとする。各ノードが、それぞれの要求を単位処理負荷（前述の例と同様に、以下、単位処理時間）分だけ処理すると、要求の一部は他のノードに遷移する。ノードiからノードjへ遷移する要求の数は、遷移確率Ｐｉｊを用いると、期待値（Ｐｉｊ×ｗｉ）と予測される。よって、最初の単位処理時間後（１回目）に、各ノードに遷移した要求数は、遷移確率行列
【数８】
2019067087.tif 000010
と各ノードに投入された要求数
【数９】
2019067087.tif 000011
の行列積
【数１０】
2019067087.tif 000012
となると期待される。
行列積
【数１１】
2019067087.tif 000013
の値は、以下の式で算出される。
【００４５】
【数１２】
2019067087.tif 000014
【００４６】
同様に、次の単位処理時間後（２回目）に、各ノードに遷移した要求数は、行列積
【数１３】
2019067087.tif 000015
となると期待される。また、３回目，．．．，１３回目についても、それぞれ行列積
【数１４】
2019067087.tif 000016
となると期待される。このような処理を繰り返す結果、各ノードの要求の延べ数、すなわち、各ノードの処理負荷は、
【数１５】
2019067087.tif 000017
となると期待される。
【００４７】
［処理時間の予測（解１）］
処理時間の累計値Ｔは、要求数（要求の処理に要する単位処理時間）の総和を
【数１６】
2019067087.tif 000018
とすると、
【数１７】
2019067087.tif 000019
で与えられる。図７の例において、ノード１〜５それぞれの処理時間の累計値
【数１８】
2019067087.tif 000020
は、
【数１９】
2019067087.tif 000021
で求めることができる。この結果、ノード１の処理時間の累計値Ｔは１．３、ノード２の処理時間の累計値Ｔは０．７、ノード３の処理時間の累計値Ｔは１．３、ノード４、５の処理時間の累計値Ｔはそれぞれ１．０である。(下式では、小数点2桁以下を四捨五入)
【数２０】
2019067087.tif 000022
【００４８】
［処理時間の予測（解２）］
また、要求は有限時間内に全ての処理が完了する、という前提条件があることから、
【数２１】
2019067087.tif 000023
となる。このため、各ノードの処理負荷は、
【数２２】
2019067087.tif 000024
で求めることができる。ここで、
【数２３】
2019067087.tif 000025
は単位行列を示す。
【００４９】
具体的に説明すると、
【数２４】
2019067087.tif 000026
である。両辺に
【数２５】
2019067087.tif 000027
をかけると、
【数２６】
2019067087.tif 000028
となる。式１の
【数２７】
2019067087.tif 000029
から式２の
【数２８】
2019067087.tif 000030
を引くと、
【数２９】
2019067087.tif 000031
となる。ゆえに、
【数３０】
2019067087.tif 000032
を得る。
【００５０】
図７の例では、
【数３１】
2019067087.tif 000033
の値は以下のように求められる。
【００５１】
【数３２】
2019067087.tif 000034
よって、
【００５２】
【数３３】
2019067087.tif 000035
を得る。これは、上記の解１の結果と同じである。
【００５３】
警告／対策算出処理（ステップＳ１４）
ここでは、処理時間の許容値をＴlimit＝１．０と仮定する。上述したように、処理時間
【数３４】
2019067087.tif 000036
と予測され、ノード１、3の処理時間が許容値を越えている。つまり、これは、ノード１、3に遷移してくる要求が過多であることを示す。
【００５４】
対策算出部２６は、処理時間の予測値と許容値とを比較する。ノード１とノード３の処理時間の予測値はともに「１．３」であり、許容値の「１．０」よりも大きい。この場合、対策算出部２６は、対策算出部２６は、警告メッセージ（例えば、「予測される処理時間が、許容される処理時間を超過しています」といったメッセージ）を出力するとともに、以下のような対策案を提示することができる。
【００５５】
［処理負荷の改善］
対策算出部２６は、予測値が許容値を超えたノード１とノード３について、「１．０に高速化するか、並列化でますか？」といった処理負荷の改善を促すメッセージを出力する。
【００５６】
［許容値の緩和］
対策算出部２６は、「Ｔlimitを１．０から１．３に緩和できますか？」といった許容値の緩和を促すメッセージを出力する。
【００５７】
［要求の緩和］
対策算出部２６は、「
【数３５】
2019067087.tif 000037
の要求量を緩和できますか？」
といった要求の緩和を促すメッセージを出力する。
【００５８】
［遷移確率の調整］
図８に、遷移確率調整用テーブルを示す。遷移確率調整用テーブルの列方向に遷移先ノードが示され、行方向に遷移元モードが示されている。テーブル中、太字で示したノード及び数値は、処理時間が超過しているノードへ要求を遷移させている遷移元のノードとその遷移確率を示す。
対策算出部２６は、図８に示した遷移確率調整用テーブルを出力するとともに、処理時間が超過しているノードへ要求を遷移させている遷移元のノードについて、遷移確率を下げることを促すメッセージを出力する。例えば、対策算出部２６は、ノード３に遷移する確率、すなわち、「Ｐ１３＝１/４」と「Ｐ２３＝１/１」と「Ｐ４３＝１/３」の遷移確率を下げることを促すメッセージを出力する。
【００５９】
以上説明した本実施形態のノード管理装置２１によれば、要求を有限時間内に処理する任意の分散処理システムについて、実際の処理結果に基づいて、任意の要求数に対する各ノードの処理負荷を定量的に予測できる。この予測では、過負荷のノードやその負荷だけでなく、過負荷の要因や低負荷のノードを推定できるため、負荷分散や輻輳制御などの対策をより早く、より詳細に立てることができる。
【００６０】
ノード管理装置２１において、遷移検出部２２、遷移集計分析部２３、処理負荷予測部２４、要求数取得部２５、対策算出部２６及び許容負荷取得部２７のそれぞれの機能を有する１つの制御部が設けられても良い。また、その制御部は、ＣＰＵ等を具備したコンピュータで実現されても良い。この場合、コンピュータがプログラムを実行することで、遷移検出部２２、遷移集計分析部２３、処理負荷予測部２４、要求数取得部２５、対策算出部２６及び許容負荷取得部２７のそれぞれの機能を実現しても良い。
【００６１】
プログラムは、遷移検出部２２、遷移集計分析部２３、処理負荷予測部２４、要求数取得部２５、対策算出部２６及び許容負荷取得部２７のそれぞれの機能に対応する処理をコンピュータが実行するためのものであって良い。プログラムは、上述したコンピュータ使用可能媒体またはコンピュータ可読媒体で提供されてもよく、また、インターネット等のネットワークを介して提供されてもよい。
【００６２】
また、ノード管理装置２１において、以下のような変形を適用することができる。
遷移検出部２２は、ノードが要求を処理した際に発生した処理負荷と、要求の遷移先ノードの情報を集計する。ここで、各ノードが、処理負荷と遷移先ノードの情報を自発的に報告しても良いが、遷移検出部２２が、処理状態や遷移結果をノードに問い合わせても良い。また、遷移検出部２２が、ノードの通信を監視して、要求の処理開始のタイミングや、要求の受け渡しを検出しても良い。
【００６３】
また、ノード内に要求が処理されるまでの待ち行列がある場合は、ノード自身、処理の開始・終了タイミングなどから処理負荷を求めても良い。一方、ノード内に待ち行列が無い場合、すなわち、ノード内では各要求が一定負荷の処理を受けるような場合には、遷移時刻などを知り得た、ノード以外の第３者が処理負荷を類推しても良い。
例えば、分散処理システムが生産ラインシステムである場合、各ノードに待ち行列がある場合がある。この場合、ノード(検査工程）で要求（仕掛品）を処理（検査）した際の負荷（検査を開始・終了した時刻）と、遷移先ノード（検査の結果、判定された次の工程）を、ノード自身が求めても良い。遷移集計分析部２３は、ノードからの報告に基づいて情報を集計する。
【００６４】
また、ノードは、移動体通信の基地局であっても良い。この場合、遷移集計分析部２３は、ノードが送信するハンドオーバーの制御情報の通信を監視し、要求（ユーザ）がノード（基地局）間を遷移（ハンドオーバー）した時刻と遷移先のノード（ターゲットの基地局）を検出しても良い。また、各ユーザは一定の処理負荷をノードに与えると仮定して、遷移集計分析部２３は、遷移（ハンドオーバー）した時刻から処理負荷を推定しても良い。
処理負荷と遷移先ノードの情報の集計の網羅性は、全ての遷移に関するものでも良く、あるいは、無作為に抽出されたサンプルでも良い。ここで、サンプルは、無作為に抽出された要求の全ての遷移、または、無作為に抽出された要求の無作為に抽出された遷移であっても良い。
【００６５】
処理負荷予測部２４は、予測の前提となる要求数として、分散処理システム１０に入力される実際の要求数を用いても良い。ここで、要求数は、過去の要求数だけでなく、現在入力されている要求数でも良い。後者の場合でも、実際の処理をする直前に処理負荷を予測できる。あるいは、処理負荷予測部２４は、何らかのシミュレーションに基づいて、将来発生する要求数を予測しても良い。または、実際の要求数と部分的なシミュレーションの要求数を加算したものを、分散処理システム１０に入力される要求数としても良い。
【００６６】
処理負荷の許容値は、例えば、ユーザインターフェースから対話的に入力されても良い(例えば、要求数wが、単発的に発生する場合)。あるいは、上記の予測の前提とした要求数の発生頻度を、処理負荷の許容値としても良い（例えば、要求数
【数３６】
2019067087.tif 000038
が、連続的に発生する場合、その発生周期を処理時間の許容値とする）。
処理負荷が許容値を超えた場合の通知先は、例えば、分散処理システムの管理者または状態監視装置、ノードの負荷分散の担当者または負荷分散装置、要求の受付システム、または輻輳制御装置である。ここで、負荷分散装置は、処理負荷の予測値が許容値を超えていないノードの処理能力の一部を、処理負荷が許容値を超えているノードの処理に割り当てても良い。
【００６７】
予測値が許容値を超えているノードと処理負荷を通報する際に、処理負荷予測部２４は、処理負荷の予測値が許容値以下のノードとその処理負荷についても併せて通知しても良い。この通知により、分散処理（例えば、予測値が許容値未満のノードから、予測値が許容値以上のノードに処理のリソースを配置換えする処理）、あるいは、輻輳制御（例えば、負荷の高いノードではなく負荷の低いノードに、要求の一部を遷移させる処理）ができる。
【００６８】
以上説明した各実施形態のノード管理装置は、本発明の一例であり、その構成や動作については、発明の趣旨を逸脱しない範囲で、当業者が理解し得る変更を適用することができる。
【産業上の利用可能性】
【００６９】
本発明は、互いに連携して要求を処理する複数のノードからなるシステムに適用することができる。例えば、本発明は、分散処理システムの負荷分散、移動体通信のトラフィック制御・輻輳制御、生産ラインの生産管理や進捗管理に適用することができる。
【符号の説明】
【００７０】
１１  ノード管理装置
１２  分析部
１３  予測部
１５1〜１５n  ノード
【図１】
2019067087.tif 000039
【図２】
2019067087.tif 000040
【図３】
2019067087.tif 000041
【図４】
2019067087.tif 000042
【図５】
2019067087.tif 000043
【図６】
2019067087.tif 000044
【図７】
2019067087.tif 000045
【図８】
2019067087.tif 000046