(57)【要約】本発明は、データの格納装置と当該データの送受信を行う処理装置間の通信負荷低減を可能とする。  通信装置は、データ装置または処理装置の識別子及び通信コストの組を格納するノード情報格納手段と、転送経路の通信コストである総コストを包含するメッセージを受信して、総コストが負となる転送経路の閉路を検出して出力、または、出ノード情報に登録されているデータ装置または処理装置に、受信した総コストから当該装置対応の通信コストを減じた新たな総コストを包含するメッセージを送信し、かつ、出ノード情報に登録されている処理装置に、受信した総コストに当該処理装置対応の通信コストを加えた新たな総コストを包含するメッセージを送信する探索処理手段を備える。
2012161289.tif 000002
【特許請求の範囲】
【請求項１】
自装置が与えられた処理を実行する処理装置である場合は、前記処理のデータに関連付けられたデータ装置の識別子及び当該データに対する通信コストの組を、自装置がデータ装置である場合は、関連付けられたデータを入出力する処理装置の識別子と当該処理装置と当該データ間の通信コストの組を含む出ノード情報を格納するノード情報格納手段と、
自装置または他装置を発信元とし、転送経路の通信コストである総コストを包含するメッセージを受信して、総コストが負となる転送経路の閉路を検出して出力、または、前記出ノード情報に登録されているデータ装置に、受信した総コストから当該データ装置対応の通信コストを減じた新たな総コスト、受信した転送経路に自装置を加えた新たな転送経路を包含するメッセージを送信し、かつ、前記出ノード情報に登録されている処理装置に、受信した総コストに当該処理装置対応の通信コストを加えた新たな総コスト、新たな転送経路を包含するメッセージを送信する探索処理手段を備え、
ノード情報格納手段と探索処理手段を備える他装置と通信路で接続された通信装置。
【請求項２】
自装置が新たな処理を行い得る残存処理能力を有する処理装置である場合、前記出ノード情報は、処理が与えられている処理装置の識別子とゼロの通信コストを包含する、請求項１の通信装置。
【請求項３】
自装置が与えられている処理を実行する処理装置である場合、前記出ノード情報はデータ装置対応に自装置と当該データ装置間の通信データ量を変更上限として包含し、メッセージは転送経路および転送経路上の変更上限の最小値Ｍ２を包含し、
前記探索処理手段は、メッセージをデータ装置に転送する際、受信したメッセージのＭ２と当該データ装置に対する変更上限の最小値を新たなＭ２とし、
受信したメッセージの転送経路から閉路を検出した際、
ａ）自装置が前記発信元でなければ、メッセージを前記発信元に送信し、
ｂ）自装置が前記発信元であれば、他装置からメッセージを受信して、各メッセージの閉路について、当該閉路に含まれる各処理装置から、当該処理装置の残存処理能力Ｐ及び与えられている処理の単位データ量当たりの消費処理能力Ｌ２、当該閉路において当該処理装置の１つ手前の処理装置の与えられている処理の単位データ量当たりの消費処理能力Ｌ１を取得して、各処理装置対応の処理追加可能量Ｐ／（Ｌ１−Ｌ２）を算出してその最小値Ｍ１を取得し、Ｍ１と当該メッセージのＭ２の小さい方を変更流量としたときの（総コストｘ変更流量）を求め、
当該値が最大の閉路を選択し、選択した閉路および変更流量を出力する、請求項１または２の通信装置。
【請求項４】
前記ノード情報格納手段は、自装置の識別子を出ノード情報に包含する他装置の識別子を含む入ノード情報を格納し、メッセージは、転送経路の長さである探索長を包含し、
前記探索処理手段は、
受信したメッセージの探索長に１加算された探索長を包含するメッセージを前記出ノード情報に登録されている前記データ装置、若しくは、前記処理装置に送信し、
１からノード数Ｎ迄の各値ｋについて、前記入りノード情報に登録されている各他装置から探索長がｋであるメッセージを受信して、探索長ｋの総コストの最小値ｄｋおよび最小値ｄｋを含むメッセージを自装置に送信した他装置の識別子である経路ノードｋを取得し、
１からＮ−１までの各探索長ｋについて、平均コスト＝（ｄＮ−ｄｋ）／（Ｎ−ｋ）を算出し、その最大値Ｍと、１からノード数Ｎ迄の各値ｋについての経路ノードｋを含む探索結果を作成し、かつ、
ａ）自装置が前記発信元でなければ、前記探索結果を前記発信元に送信し、
ｂ）自装置が前記発信元であれば、全ての他装置から探索結果を受信して、全探索結果のうちで、最小の最大値Ｍを含む探索結果が包含する経路ノードＮを始点として、ｋ＝ノード数Ｎから順次ｋを減じながら、経路ノードｋをたぐって前記閉路を検出する、
Ｎ−１個の他装置と接続された請求項１または２の通信装置。
【請求項５】
１からＮ迄の各探索長ｋおよび前記入りノード情報に登録されている他装置（入りノード）対応に、前記探索処理手段が、当該探索長のメッセージを当該入りノードから受信したか否かを示す入ノード状態を格納する経路格納手段を備え、
前記探索処理手段は、探索長がｋのメッセージを受信したとき、前記経路格納手段から、当該探索長ｋのメッセージを受信していない入りノード（ｋ未確定ノード）を検索して、なければ、メッセージを前記データ装置、若しくは、前記処理装置に送信し、
あれば、ｋ未確定ノードに探索長ｋを包含する取得要求を送信し、
探索長がｋの取得要求を受信したとき、前記経路格納手段から当該探索長ｋ−１のメッセージを受信していない入りノード（ｋ−１未確定ノード）を検索して、
ａ）存在すれば、ｋ−１未確定ノードに探索長ｋ−１を包含する取得要求を送信し、
ｂ）存在せず、ｂ１）探索長がｋの取得要求をデータ装置から受信すれば、探索長ｋ−１の総コストの最小値ｄｋ−１から当該データ装置の通信コストを減算した値を総コストとしｋを探索長として包含するメッセージを当該データ装置に送信し、ｂ２）探索長がｋの取得要求を処理装置から受信すれば、最小値ｄｋ−１に当該処理装置の通信コストを加算した値を総コストとしｋを探索長として包含するメッセージを当該処理装置に送信する、請求項４の通信装置。
【請求項６】
自装置が与えられている処理を実行する処理装置である場合、前記出ノード情報はデータ装置対応に自装置と当該データ装置間の通信データ量を変更上限として包含し、
自装置が前記発信元であれば、前記探索処理手段は、検出された前記閉路における経路ノードｋから経路ノードｋ−１への変更上限、経路ノードｋが処理装置である場合は自装置の残存処理能力及び与えられている処理の単位データ量当たりの消費処理能力を受信して、
当該閉路に含まれる各処理装置について、当該処理装置の残存処理能力Ｐ及び与えられている処理の単位データ量当たりの消費処理能力Ｌ２、当該閉路において当該処理装置の１つ手前の処理装置の与えられている処理の単位データ量当たりの消費処理能力Ｌ１から、各処理装置対応の処理追加可能量Ｐ／（Ｌ１−Ｌ２）を算出してその最小値Ｍ１を取得し、
Ｍ１と変更上限の最小値Ｍ２の小さい方を変更流量として、当該閉路および変更流量を出力する、請求項４または５の通信装置。
【請求項７】
前記閉路に含まれるデータ装置に関連付けられたデータの変更流量分のデータの通信先を、前記閉路の転送経路順に於ける当該データ装置の前の処理装置から後の処理装置に変更させる処理移動手段、を備える請求項３または請求項６の通信装置。
【請求項８】
データ装置は複数のデータと関連付けられており、
処理装置の出ノード情報は、当該データ装置対応の通信コストとして、当該複数のデータへのおのおのの通信コストを、通信量に応じて重み付け加算した値を包含する、請求項１乃至７のいずれかの通信装置。
【請求項９】
データ装置はｍ個（ｍは複数）のデータと関連付けられており、
処理装置の出ノード情報は、当該データ装置対応の通信コストとして、当該ｍ個のデータへのおのおのの通信コストの小さい方からｎ個（ｎはｍ以下の数）を、選択して加算した値を包含する、請求項１乃至８のいずれかの通信装置。
【請求項１０】
処理装置の通信開始を契機に、前記探索処理手段は、出ノード情報に他装置の識別子と通信コストの組を格納し、
他装置から、転送経路の長さである探索長を包含するメッセージを受信して、受信したメッセージの探索長に１加算された探索長を包含するメッセージを前記出ノード情報に登録されている前記データ装置、若しくは、前記処理装置に送信し、
１からノード数Ｎ迄の各値ｋについて、他装置から探索長がｋであるメッセージを受信して、探索長ｋの総コストの最小値ｄｋおよび最小値ｄｋを含むメッセージを自装置に送信した他装置の識別子である経路ノードｋを取得し、
１からＮ−１までの各探索長ｋについて、平均コスト＝（ｄＮ−ｄｋ）／（Ｎ−ｋ）を算出し、当該平均コストの最大値が負であれば、経路ノードＮを始点として、ｋ＝ノード数Ｎから順次ｋを減じながら、経路ノードｋをたぐって前記閉路を検出する、
Ｎ−１個の他装置と接続された請求項１または２の通信装置。
【請求項１１】
自装置に対応するワーカ装置が与えられた処理を実行する処理装置である場合は、前記処理のデータに関連付けられたデータ装置の識別子及び当該データに対する通信コストの組を、自装置に対応するワーカ装置がデータ装置である場合は、関連付けられたデータを入出力する処理装置の識別子と当該処理装置と当該データ間の通信コストの組を含む出ノード情報をノード情報格納手段に格納し、
自装置または他装置を発信元とし、転送経路の通信コストである総コストを包含するメッセージを受信して、総コストが負となる転送経路の閉路を検出して出力、または、前記出ノード情報に登録されているデータ装置に対応する他の通信装置に、受信した総コストから当該データ装置対応の通信コストを減じた新たな総コスト、受信した転送経路に自装置に対応するワーカ装置を加えた新たな転送経路を包含するメッセージを送信し、かつ、前記出ノード情報に登録されている処理装置に対応する他の通信装置に、受信した総コストに当該処理装置対応の通信コストを加えた新たな総コスト、新たな転送経路を包含するメッセージを送信する探索処理手段を備える通信装置を、複数台通信路で接続した通信システム。
【請求項１２】
自装置が与えられた処理を実行する処理装置である場合は、前記処理のデータに関連付けられたデータ装置の識別子及び当該データに対する通信コストの組を、自装置がデータ装置である場合は、関連付けられたデータを入出力する処理装置の識別子と当該処理装置と当該データ間の通信コストの組を含む出ノード情報をノード情報格納手段に格納する格納処理と、
自装置または他装置を発信元とし、転送経路の通信コストである総コストを包含するメッセージを受信して、総コストが負となる転送経路の閉路を検出して出力、または、前記出ノード情報に登録されているデータ装置に、受信した総コストから当該データ装置対応の通信コストを減じた新たな総コスト、受信した転送経路に自装置を加えた新たな転送経路を包含するメッセージを送信し、かつ、前記出ノード情報に登録されている処理装置に、受信した総コストに当該処理装置対応の通信コストを加えた新たな総コスト、新たな転送経路を包含するメッセージを送信する探索処理を、
ノード情報格納処理と探索処理を実行する他装置と通信路で接続されたコンピュータに実行させるプログラム。
【請求項１３】
自装置が新たな処理を行い得る残存処理能力を有する処理装置である場合、前記出ノード情報は、処理が与えられている処理装置の識別子とゼロの通信コストを包含する、請求項１２のプログラム。
【請求項１４】
自装置が与えられている処理を実行する処理装置である場合、前記出ノード情報はデータ装置対応に自装置と当該データ装置間の通信データ量を変更上限として包含し、メッセージは転送経路および転送経路上の変更上限の最小値Ｍ２を包含し、
前記探索処理手段は、メッセージをデータ装置に転送する際、受信したメッセージのＭ２と当該データ装置に対する変更上限の最小値を新たなＭ２とし、
受信したメッセージの転送経路から閉路を検出した際、
ａ）自装置が前記発信元でなければ、メッセージを前記発信元に送信し、
ｂ）自装置が前記発信元であれば、他装置からメッセージを受信して、各メッセージの閉路について、当該閉路に含まれる各処理装置から、当該処理装置の残存処理能力Ｐ及び与えられている処理の単位データ量当たりの消費処理能力Ｌ２、当該閉路において当該処理装置の１つ手前の処理装置の与えられている処理の単位データ量当たりの消費処理能力Ｌ１を取得して、各処理装置対応の処理追加可能量Ｐ／（Ｌ１−Ｌ２）を算出してその最小値Ｍ１を取得し、Ｍ１と当該メッセージのＭ２の小さい方を変更流量としたときの（総コストｘ変更流量）を求め、
当該値が最大の閉路を選択し、選択した閉路および変更流量を出力する前記探索処理を前記コンピュータに実行させる、請求項１２または１３のプログラム。
【請求項１５】
自装置の識別子を出ノード情報に包含する他装置の識別子を含む入ノード情報を前記ノード情報格納手段に格納する前記ノード情報格納処理と、
メッセージに、転送経路の長さである探索長を包含させ、
受信したメッセージの探索長に１加算された探索長を包含するメッセージを前記出ノード情報に登録されている前記データ装置、若しくは、前記処理装置に送信し、
１からノード数Ｎ迄の各値ｋについて、前記入りノード情報に登録されている各他装置から探索長がｋであるメッセージを受信して、探索長ｋの総コストの最小値ｄｋおよび最小値ｄｋを含むメッセージを自装置に送信した他装置の識別子である経路ノードｋを取得し、
１からＮ−１までの各探索長ｋについて、平均コスト＝（ｄＮ−ｄｋ）／（Ｎ−ｋ）を算出し、その最大値Ｍと、１からノード数Ｎ迄の各値ｋについての経路ノードｋを含む探索結果を作成し、かつ、
ａ）自装置が前記発信元でなければ、前記探索結果を前記発信元に送信し、
ｂ）自装置が前記発信元であれば、全ての他装置から探索結果を受信して、全探索結果のうちで、最小の最大値Ｍを含む探索結果が包含する経路ノードＮを始点として、ｋ＝ノード数Ｎから順次ｋを減じながら、経路ノードｋをたぐって前記閉路を検出する前記探索処理を、Ｎ−１個の他装置と接続された前記コンピュータに実行させる請求項１２または１３のプログラム。
【請求項１６】
１からＮ迄の各探索長ｋおよび前記入りノード情報に登録されている他装置（入りノード）対応に、前記探索処理手段が、当該探索長のメッセージを当該入りノードから受信したか否かを示す入ノード状態を格納する経路格納手段を備えた前記コンピュータに、
探索長がｋのメッセージを受信したとき、前記経路格納手段から、当該探索長ｋのメッセージを受信していない入りノード（ｋ未確定ノード）を検索して、なければ、メッセージを前記データ装置、若しくは、前記処理装置に送信し、
あれば、ｋ未確定ノードに探索長ｋを包含する取得要求を送信し、
探索長がｋの取得要求を受信したとき、前記経路格納手段から当該探索長ｋ−１のメッセージを受信していない入りノード（ｋ−１未確定ノード）を検索して、
ａ）存在すれば、ｋ−１未確定ノードに探索長ｋ−１を包含する取得要求を送信し、
ｂ）存在せず、ｂ１）探索長がｋの取得要求をデータ装置から受信すれば、探索長ｋ−１の総コストの最小値ｄｋ−１から当該データ装置の通信コストを減算した値を総コストとしｋを探索長として包含するメッセージを当該データ装置に送信し、ｂ２）探索長がｋの取得要求を処理装置から受信すれば、最小値ｄｋ−１に当該処理装置の通信コストを加算した値を総コストとしｋを探索長として包含するメッセージを当該処理装置に送信する、前記探索処理を前記コンピュータに実行させる請求項１５のプログラム。
【請求項１７】
自装置が与えられている処理を実行する処理装置である場合、前記出ノード情報はデータ装置対応に自装置と当該データ装置間の通信データ量を変更上限として包含し、
自装置が前記発信元であれば、検出された前記閉路における経路ノードｋから経路ノードｋ−１への変更上限、経路ノードｋが処理装置である場合は自装置の残存処理能力及び与えられている処理の単位データ量当たりの消費処理能力を受信して、
当該閉路に含まれる各処理装置について、当該処理装置の残存処理能力Ｐ及び与えられている処理の単位データ量当たりの消費処理能力Ｌ２、当該閉路において当該処理装置の１つ手前の処理装置の与えられている処理の単位データ量当たりの消費処理能力Ｌ１から、各処理装置対応の処理追加可能量Ｐ／（Ｌ１−Ｌ２）を算出してその最小値Ｍ１を取得し、
Ｍ１と変更上限の最小値Ｍ２の小さい方を変更流量として、当該閉路および変更流量を出力する前記探索処理を前記コンピュータに実行させる、請求項１５または１６のプログラム。
【請求項１８】
前記閉路に含まれるデータ装置に関連付けられたデータの変更流量分のデータの通信先を、前記閉路の転送経路順に於ける当該データ装置の前の処理装置から後の処理装置に変更させる処理移動処理を前記コンピュータに実行させる、請求項１４または請求項１７のプログラム。
【請求項１９】
データ装置は複数のデータと関連付けられており、
処理装置の出ノード情報は、当該データ装置対応の通信コストとして、当該複数のデータへのおのおのの通信コストを、通信量に応じて重み付け加算した値を包含する、請求項１２乃至１８のいずれかのプログラム。
【請求項２０】
データ装置はｍ個（ｍは複数）のデータと関連付けられており、
処理装置の出ノード情報は、当該データ装置対応の通信コストとして、当該ｍ個のデータへのおのおのの通信コストの小さい方からｎ個（ｎはｍ以下の数）を、選択して加算した値を包含する、請求項１２乃至１９のいずれかのプログラム。
【請求項２１】
処理装置の通信開始を契機に、出ノード情報に他装置の識別子と通信コストの組を格納し、
他装置から、転送経路の長さである探索長を包含するメッセージを受信して、受信したメッセージの探索長に１加算された探索長を包含するメッセージを前記出ノード情報に登録されている前記データ装置、若しくは、前記処理装置に送信し、
１からノード数Ｎ迄の各値ｋについて、他装置から探索長がｋであるメッセージを受信して、探索長ｋの総コストの最小値ｄｋおよび最小値ｄｋを含むメッセージを自装置に送信した他装置の識別子である経路ノードｋを取得し、
１からＮ−１までの各探索長ｋについて、平均コスト＝（ｄＮ−ｄｋ）／（Ｎ−ｋ）を算出し、当該平均コストの最大値が負であれば、経路ノードＮを始点として、ｋ＝ノード数Ｎから順次ｋを減じながら、経路ノードｋをたぐって前記閉路を検出する前記探索処理を、
Ｎ−１個の他装置と接続された前記コンピュータに実行させる請求項１２または１３のプログラム。
【請求項２２】
自装置が与えられた処理を実行する処理装置である場合は、前記処理のデータに関連付けられたデータ装置の識別子及び当該データに対する通信コストの組を、自装置がデータ装置である場合は、関連付けられたデータを入出力する処理装置の識別子と当該処理装置と当該データ間の通信コストの組を含む出ノード情報をノード情報格納手段に格納し、
自装置または他装置を発信元とし、転送経路の通信コストである総コストを包含するメッセージを受信して、総コストが負となる転送経路の閉路を検出して出力、または、前記出ノード情報に登録されているデータ装置に、受信した総コストから当該データ装置対応の通信コストを減じた新たな総コスト、受信した転送経路に自装置を加えた新たな転送経路を包含するメッセージを送信し、かつ、前記出ノード情報に登録されている処理装置に、受信した総コストに当該処理装置対応の通信コストを加えた新たな総コスト、新たな転送経路を包含するメッセージを送信する、
ノード情報格納処理と探索処理を実行する他装置と通信路で接続された通信装置における通信方法。
【請求項２３】
自装置が新たな処理を行い得る残存処理能力を有する処理装置である場合、前記出ノード情報は、処理が与えられている処理装置の識別子とゼロの通信コストを包含する、請求項２２の通信方法。
【請求項２４】
自装置が与えられている処理を実行する処理装置である場合、前記出ノード情報はデータ装置対応に自装置と当該データ装置間の通信データ量を変更上限として包含し、メッセージは転送経路および転送経路上の変更上限の最小値Ｍ２を包含し、
前記探索処理手段は、メッセージをデータ装置に転送する際、受信したメッセージのＭ２と当該データ装置に対する変更上限の最小値を新たなＭ２とし、
受信したメッセージの転送経路から閉路を検出した際、
ａ）自装置が前記発信元でなければ、メッセージを前記発信元に送信し、
ｂ）自装置が前記発信元であれば、他装置からメッセージを受信して、各メッセージの閉路について、当該閉路に含まれる各処理装置から、当該処理装置の残存処理能力Ｐ及び与えられている処理の単位データ量当たりの消費処理能力Ｌ２、当該閉路において当該処理装置の１つ手前の処理装置の与えられている処理の単位データ量当たりの消費処理能力Ｌ１を取得して、各処理装置対応の処理追加可能量Ｐ／（Ｌ１−Ｌ２）を算出してその最小値Ｍ１を取得し、Ｍ１と当該メッセージのＭ２の小さい方を変更流量としたときの（総コストｘ変更流量）を求め、
当該値が最大の閉路を選択し、選択した閉路および変更流量を出力する、請求項２２または請求項２３の通信方法。
【請求項２５】
自装置の識別子を出ノード情報に包含する他装置の識別子を含む入ノード情報を前記ノード情報格納手段に格納し、
メッセージに、転送経路の長さである探索長を包含させ、
受信したメッセージの探索長に１加算された探索長を包含するメッセージを前記出ノード情報に登録されている前記データ装置、若しくは、前記処理装置に送信し、
１からノード数Ｎ迄の各値ｋについて、前記入りノード情報に登録されている各他装置から探索長がｋであるメッセージを受信して、探索長ｋの総コストの最小値ｄｋおよび最小値ｄｋを含むメッセージを自装置に送信した他装置の識別子である経路ノードｋを取得し、
１からＮ−１までの各探索長ｋについて、平均コスト＝（ｄＮ−ｄｋ）／（Ｎ−ｋ）を算出し、その最大値Ｍと、１からノード数Ｎ迄の各値ｋについての経路ノードｋを含む探索結果を作成し、かつ、
ａ）自装置が前記発信元でなければ、前記探索結果を前記発信元に送信し、
ｂ）自装置が前記発信元であれば、全ての他装置から探索結果を受信して、全探索結果のうちで、最小の最大値Ｍを含む探索結果が包含する経路ノードＮを始点として、ｋ＝ノード数Ｎから順次ｋを減じながら、経路ノードｋをたぐって前記閉路を検出する、Ｎ−１個の他装置と接続された前記通信装置に於ける請求項２２または２３の方法。
【請求項２６】
１からＮ迄の各探索長ｋおよび前記入りノード情報に登録されている他装置（入りノード）対応に、前記探索処理手段が、当該探索長のメッセージを当該入りノードから受信したか否かを示す入ノード状態を格納する経路格納手段を備えた前記コンピュータに、
探索長がｋのメッセージを受信したとき、前記経路格納手段から、当該探索長ｋのメッセージを受信していない入りノード（ｋ未確定ノード）を検索して、なければ、メッセージを前記データ装置、若しくは、前記処理装置に送信し、
あれば、ｋ未確定ノードに探索長ｋを包含する取得要求を送信し、
探索長がｋの取得要求を受信したとき、前記経路格納手段から当該探索長ｋ−１のメッセージを受信していない入りノード（ｋ−１未確定ノード）を検索して、
ａ）存在すれば、ｋ−１未確定ノードに探索長ｋ−１を包含する取得要求を送信し、
ｂ）存在せず、ｂ１）探索長がｋの取得要求をデータ装置から受信すれば、探索長ｋ−１の総コストの最小値ｄｋ−１から当該データ装置の通信コストを減算した値を総コストとしｋを探索長として包含するメッセージを当該データ装置に送信し、ｂ２）探索長がｋの取得要求を処理装置から受信すれば、最小値ｄｋ−１に当該処理装置の通信コストを加算した値を総コストとしｋを探索長として包含するメッセージを当該処理装置に送信する、請求項２５の通信方法。
【請求項２７】
自装置が与えられている処理を実行する処理装置である場合、前記出ノード情報はデータ装置対応に自装置と当該データ装置間の通信データ量を変更上限として包含し、
自装置が前記発信元であれば、検出された前記閉路における経路ノードｋから経路ノードｋ−１への変更上限、経路ノードｋが処理装置である場合は自装置の残存処理能力及び与えられている処理の単位データ量当たりの消費処理能力を受信して、
当該閉路に含まれる各処理装置について、当該処理装置の残存処理能力Ｐ及び与えられている処理の単位データ量当たりの消費処理能力Ｌ２、当該閉路において当該処理装置の１つ手前の処理装置の与えられている処理の単位データ量当たりの消費処理能力Ｌ１から、各処理装置対応の処理追加可能量Ｐ／（Ｌ１−Ｌ２）を算出してその最小値Ｍ１を取得し、
Ｍ１と変更上限の最小値Ｍ２の小さい方を変更流量として、当該閉路および変更流量を出力する、請求項２５または請求項２６の通信方法。
【請求項２８】
前記閉路に含まれるデータ装置に関連付けられたデータの変更流量分のデータの通信先を、前記閉路の転送経路順に於ける当該データ装置の前の処理装置から後の処理装置に変更させる、請求項２４または請求項２７の通信方法。
【請求項２９】
データ装置は複数のデータと関連付けられており、
処理装置の出ノード情報は、当該データ装置対応の通信コストとして、当該複数のデータへのおのおのの通信コストを、通信量に応じて重み付け加算した値を包含する、請求項２２乃至請求項２８のいずれかの通信方法。
【請求項３０】
データ装置はｍ個（ｍは複数）のデータと関連付けられており、
処理装置の出ノード情報は、当該データ装置対応の通信コストとして、当該ｍ個のデータへのおのおのの通信コストの小さい方からｎ個（ｎはｍ以下の数）を、選択して加算した値を包含する、請求項２２乃至請求項２９のいずれかの通信方法。
【請求項３１】
処理装置の通信開始を契機に、出ノード情報に他装置の識別子と通信コストの組を格納し、
他装置から、転送経路の長さである探索長を包含するメッセージを受信して、受信したメッセージの探索長に１加算された探索長を包含するメッセージを前記出ノード情報に登録されている前記データ装置、若しくは、前記処理装置に送信し、
１からノード数Ｎ迄の各値ｋについて、他装置から探索長がｋであるメッセージを受信して、探索長ｋの総コストの最小値ｄｋおよび最小値ｄｋを含むメッセージを自装置に送信した他装置の識別子である経路ノードｋを取得し、
１からＮ−１までの各探索長ｋについて、平均コスト＝（ｄＮ−ｄｋ）／（Ｎ−ｋ）を算出し、当該平均コストの最大値が負であれば、経路ノードＮを始点として、ｋ＝ノード数Ｎから順次ｋを減じながら、経路ノードｋをたぐって前記閉路を検出する、
Ｎ−１個の他装置と接続された前記通信装置に於ける請求項２２または請求項２３の通信方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、通信制御装置、通信制御システム、通信制御方法、および、プログラムに関する。特に、本発明は、装置間の通信負荷低減を可能とする通信制御装置、通信制御方法、および、プログラムに関する。
【背景技術】
【０００２】
通信負荷の低減機構を有するバッチ処理型分散システムの一例が、特許文献１に記載されている。このバッチ処理型分散システムは、処理対象データを格納するデータ格納装置と、データ格納装置からデータを取得して処理するデータ処理装置（ワーカ装置）と、ワーカ装置からの要求に応じてどのデータをそのワーカ装置が処理するかを決定するマスタ装置と、を包含する。このシステムにおいて、マスタ装置は、処理割り当て要求を行ったワーカ装置に、当該ワーカ装置の最も近くに配置されているデータ格納装置のデータの処理をするように決定する。これにより、マスタ装置は、ワーカ装置とデータ格納装置間の通信負荷を低く抑えようとする。
ネットワーク負荷の増大を防止し輻輳の発生を抑えることが出来る分散データ処理システムが、特許文献２に記載されている。この分散データ処理システムは、データ処理装置（ワーカ装置）とデータを格納するサーバとの通信遅延を用いて、クライアントからの要求に含まれる各処理をどのワーカ装置に実行させるのかを決定する。この分散データ処理システムは、例えば、ワーカ装置とサーバの座標から通信遅延を求め、その通信遅延とデータ量からワーカ装置での処理実行時におけるネットワーク負荷を求め、ネットワーク負荷の少ないワーカ装置に処理を実行させる。
他の通信処理装置による処理を代替して行うことができ、データの送受信による通信負荷を低減させることが出来る通信装置が、特許文献３に記載されている。処理実行ノードを動的に変更する分散処理システムが、特許文献４に記載されている。順序づけた一連のジョブの各々に、それぞれ計算機を割り当て実行させるジョブシステムが、特許文献５に開示されている。分散した計算機システム間で、サイトの負荷状況を考慮した、ジョブの実行の交換を可能とする計算機ネットワークシステムが、特許文献６に記載されている。
通信負荷の低減機構を有するストリーム処理型分散システムの一例が、非特許文献１に記載されている。このストリーム処理型分散システムは、バネの緩和モデルに基づき、各ノードが自律分散的にデータストリームの処理を移動させる。本システムは、この処理の移動により、移動前よりも通信負荷の低い分散ストリーム処理を実現する。
【先行技術文献】
【特許文献】
【０００３】
【特許文献１】Ｄｅａｎ  Ｊｅｆｆｒｅｙ，Ｇｈｅｍａｗａｔ  Ｓａｎｊａｙ  Ｓｙｓｔｅｍ  ａｎｄ  ｍｅｔｈｏｄ  ｆｏｒ  ｅｆｆｉｃｉｅｎｔ  ｌａｒｇｅ−ｓｃａｌｅ  ｄａｔａ  ｐｒｏｃｅｓｓｉｎｇ  ＵＳ７，６５０，３３１
【特許文献２】特開２０１０−９７４８９号公報
【特許文献３】特開２００９−２９８２３５号公報
【特許文献４】特開２００６−２６１９４９号公報
【特許文献５】特開２０００−１２１５０２号公報
【特許文献６】特開平３−８５６６３号公報
【非特許文献】
【０００４】
【非特許文献１】Ｐｅｔｅｒ  Ｐｉｅｔｚｕｃｈ，Ｊｏｎａｔｈａｎ  Ｌｅｄｌｉｅ，Ｊｅｆｆｒｅｙ  Ｓｈｎｅｉｄｍａｎ，Ｍｅｍａ  Ｒｏｕｓｓｏｐｏｕｌｏｓ，Ｍａｔｔ  Ｗｅｌｓｈ，ａｎｄ  Ｍａｒｇｏ  Ｓｅｌｔｚｅｒ  Ｎｅｔｗｏｒｋ−Ａｗａｒｅ  Ｏｐｅｒａｔｏｒ  Ｐｌａｃｅｍｅｎｔ  ｆｏｒ  Ｓｔｒｅａｍ−Ｐｒｏｃｅｓｓｉｎｇ  Ｓｙｓｔｅｍｓ  Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  ｔｈｅ  ２２ｎｄ  Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｃｏｎｆｅｒｅｎｃｅ  ｏｎ  Ｄａｔａ  Ｅｎｇｉｎｅｅｒｉｎｇ（ＩＣＤＥ’０６），Ａｔｌａｎｔａ，ＧＡ，Ａｐｒｉｌ  ２００６．
【発明の概要】
【発明が解決しようとする課題】
【０００５】
特許文献１のマスタ装置は、ワーカ装置毎に、当該ワーカ装置に閉じた部分最適を行う決定をする。この決定は、分散システム全体にとって、必ずしも最適な処理割当とならない場合がある。すなわち、この方法で決定される割り当てよりも、データが通信網を通る量が少ないような割り当てが可能である場合がある。さらに、マスタ装置という特定のコンピュータに情報収集、決定処理が集中して、大規模システムに於いてボトルネックが発生したり、このコンピュータの障害発生時にシステム全体に及ぼす影響が大きかったりという問題がある。
特許文献２の分散データ処理システムは、ワーカ装置単位の部分最適を行うものであり、複数のワーカ装置に跨る最適化は行わない。非特許文献１のストリーム処理型分散システムは、ストリーム単位の部分最適を行うものであり、複数のストリームに跨る最適化は行わない。
特許文献３乃至６の技術は、いずれも、データの格納装置と当該データの送受信を行う処理装置間の通信負荷を低減させるものではない。
本発明は、上記課題を解決するための技術を提供することを目的とする。
【課題を解決するための手段】
【０００６】
本発明の一実施形態の通信装置は、自装置が与えられた処理を実行する処理装置である場合は、前記処理のデータに関連付けられたデータ装置の識別子及び当該データに対する通信コストの組を、自装置がデータ装置である場合は、関連付けられたデータを入出力する処理装置の識別子と当該処理装置と当該データ間の通信コストの組を含む出ノード情報を格納するノード情報格納手段と、
自装置または他装置を発信元とし、転送経路の通信コストである総コストを包含するメッセージを受信して、総コストが負となる転送経路の閉路を検出して出力、または、前記出ノード情報に登録されているデータ装置に、受信した総コストから当該データ装置対応の通信コストを減じた新たな総コスト、受信した転送経路に自装置を加えた新たな転送経路を包含するメッセージを送信し、かつ、前記出ノード情報に登録されている処理装置に、受信した総コストに当該処理装置対応の通信コストを加えた新たな総コスト、新たな転送経路を包含するメッセージを送信する探索処理手段を備え、
ノード情報格納手段と探索処理手段を備える他装置と通信路で接続される。
本発明の一実施形態のプログラムは、自装置が与えられた処理を実行する処理装置である場合は、前記処理のデータに関連付けられたデータ装置の識別子及び当該データに対する通信コストの組を、自装置がデータ装置である場合は、関連付けられたデータを入出力する処理装置の識別子と当該処理装置と当該データ間の通信コストの組を含む出ノード情報をノード情報格納手段に格納する格納処理と、
自装置または他装置を発信元とし、転送経路の通信コストである総コストを包含するメッセージを受信して、総コストが負となる転送経路の閉路を検出して出力、または、前記出ノード情報に登録されているデータ装置に、受信した総コストから当該データ装置対応の通信コストを減じた新たな総コスト、受信した転送経路に自装置を加えた新たな転送経路を包含するメッセージを送信し、かつ、前記出ノード情報に登録されている処理装置に、受信した総コストに当該処理装置対応の通信コストを加えた新たな総コスト、新たな転送経路を包含するメッセージを送信する探索処理を、
ノード情報格納処理と探索処理を実行する他装置と通信路で接続されたコンピュータに実行させる。
本発明の一実施形態の通信方法は、自装置が与えられた処理を実行する処理装置である場合は、前記処理のデータに関連付けられたデータ装置の識別子及び当該データに対する通信コストの組を、自装置がデータ装置である場合は、関連付けられたデータを入出力する処理装置の識別子と当該処理装置と当該データ間の通信コストの組を含む出ノード情報をノード情報格納手段に格納し、
自装置または他装置を発信元とし、転送経路の通信コストである総コストを包含するメッセージを受信して、総コストが負となる転送経路の閉路を検出して出力、または、前記出ノード情報に登録されているデータ装置に、受信した総コストから当該データ装置対応の通信コストを減じた新たな総コスト、受信した転送経路に自装置を加えた新たな転送経路を包含するメッセージを送信し、かつ、前記出ノード情報に登録されている処理装置に、受信した総コストに当該処理装置対応の通信コストを加えた新たな総コスト、新たな転送経路を包含するメッセージを送信する、
ノード情報格納処理と探索処理を実行する他装置と通信路で接続された通信装置における方法である。
【発明の効果】
【０００７】
本発明は、複数のコンピュータがデータを通信しながら進めるデータ処理を、複数実行している分散処理システムにおいて、当該複数のデータ処理全体としての通信負荷を低減することを可能とする。
また、本発明は、負荷低減実行のさい、特定のコンピュータや装置が処理の迅速性や信頼性の点でボトルネックとなることを回避しやすくする。
【図面の簡単な説明】
【０００８】
【図１】通信制御システム９０の第１の構成例を示す図である。
【図２】通信制御システム９０の第２の構成例を示す図である。
【図３】通信制御システム９０で実行される通信変更、処理の配置変更の第１の例を示す図である。
【図４】通信制御システム９０で実行される通信変更、処理の配置変更の第２の例を示す図である。
【図５】負閉路探索部１１の構成を示す図である。
【図６】負閉路探索部１１内の通信コスト算出部１１２とノード情報生成部１１３の構成を示す図である。
【図７】探索処理部１１０の構成を示す図である。
【図８Ａ】ノード情報生成部１１３におけるノード作成部１１３２の動作フローチャート（１）である。
【図８Ｂ】ノード情報生成部１１３におけるノード作成部１１３２の動作フローチャート（２）である。
【図８Ｃ】ノード情報生成部１１３におけるノード作成部１１３２の動作フローチャート（３）である。
【図９】起動部１１０１の動作フローチャートである。
【図１０】受信部１１０２の動作フローチャートである。
【図１１Ａ】転送部１１０３の動作フローチャート（１）である。
【図１１Ｂ】転送部１１０３の動作フローチャート（２）である。
【図１２】負閉路検出部１１０４の動作フローチャートである。
【図１３】受信部１１０２等で交換されるメッセージの内容を示す図である。
【図１４】第２の実施形態の負閉路探索部１１の構成を示す図である。
【図１５】起動部１１０１の動作フローチャートである。
【図１６Ａ】転送部１１０３の動作フローチャート（１）である。
【図１６Ｂ】転送部１１０３の動作フローチャート（２）である。
【図１６Ｃ】転送部１１０３の動作フローチャート（３）である。
【図１７】負閉路検出部１１０４の動作フローチャートである。
【図１８】交換されるメッセージの内容を示す。
【図１９】ノード情報格納部１１１のデータ構成を示す図である。
【図２０】経路格納部１１０６に格納される経路情報を示す図である。
【図２１】表示実行部１８が出力する表示画面２００の一例を示す図である。
【図２２】第３の実施形態の負閉路探索部１１の構成を示す図である。
【図２３Ａ】更新部１１１３がデータノードに処理開始を反映する処理のフローチャート（１）である。
【図２３Ｂ】更新部１１１３がデータノードに処理開始を反映する処理のフローチャート（２）である。
【図２４Ａ】更新部１１１３がデータノードに処理終了を反映する処理のフローチャート（１）である。
【図２４Ｂ】更新部１１１３がデータノードに処理終了を反映する処理のフローチャート（２）である。
【図２４Ｃ】更新部１１１３がデータノードに処理終了を反映する処理のフローチャート（３）である。
【図２５Ａ】更新部１１１３が処理ノードに処理開始を反映する処理のフローチャート（１）である。
【図２５Ｂ】更新部１１１３が処理ノードに処理開始を反映する処理のフローチャート（２）である。
【図２５Ｃ】更新部１１１３が処理ノードに処理開始を反映する処理のフローチャート（３）である。
【図２６】更新部１１１３が処理ノードに処理終了を反映する処理のフローチャートである。
【図２７】更新部１１１３のリンク登録処理のフローチャートである。
【図２８Ａ】更新部１１１３のリンク削除通知処理のフローチャート（１）である。
【図２８Ｂ】更新部１１１３のリンク削除通知処理のフローチャート（２）である。
【図２９】平均コストの算出処理のフローチャートである。
【図３０】付帯制約があるときの総コスト算出処理のフローチャートである。
【図３１】ノード数Ｎの通知対応動作のフローチャートである。
【図３２】ユーザから実行指示される処理の例を示す図である。
【図３３】第１の実施の形態における動作例の説明図（１）である。
【図３４】第１の実施の形態における動作例の説明図（２）である。
【図３５】第１の実施の形態における動作例の説明図（３）である。
【図３６】第１の実施の形態における動作例のメッセージフローの説明図である。
【図３７】第１の実施の形態における動作例の探索結果１４の例を示す図である。
【図３８】第１の実施の形態における動作例の説明図（４）である。
【図３９】第１の実施の形態における動作例の説明図（５）である。
【図４０】第１の実施の形態における動作例の説明図（６）である。
【図４１】第１の実施の形態における動作例の説明図（７）である。
【図４２】第１の実施の形態における動作例の説明図（８）である。
【図４３】第１の実施の形態における動作例の説明図（９）である。
【図４４Ａ】第２の実施の形態における動作例のメッセージフローの説明図（１）である。
【図４４Ｂ】第２の実施の形態における動作例のメッセージフローの説明図（２）である。
【図４４Ｃ】第２の実施の形態における動作例のメッセージフローの説明図（３）である。
【図４４Ｄ】第２の実施の形態における動作例のメッセージフローの説明図（４）である。
【図４４Ｅ】第２の実施の形態における動作例のメッセージフローの説明図（５）である。
【図４５】第２の実施の形態における動作例の経路情報の説明図（１）である。
【図４６】第２の実施の形態における動作例の経路情報の説明図（２）である。
【図４７】第２の実施の形態における動作例の経路情報の説明図（３）である。
【図４８】第２の実施の形態における動作例の説明図（１）である。
【図４９】第２の実施の形態における動作例の説明図（２）である。
【図５０】第２の実施の形態における動作例の説明図（３）である。
【図５１】第２の実施の形態における動作例の説明図（４）である。
【図５２】第２の実施の形態における動作例の説明図（５）である。
【図５３】第３の実施の形態における動作例の説明図（１）である。
【図５４】第３の実施の形態における動作例の説明図（２）である。
【図５５】第３の実施の形態における動作例の説明図（３）である。
【図５６】第３の実施の形態における動作例の説明図（４）である。
【図５７】第３の実施の形態における動作例の説明図（５）である。
【図５８】第４の実施の形態における動作例の説明図（１）である。
【図５９】第４の実施の形態における動作例の説明図（２）である。
【図６０】第５の実施形態にかかる通信装置８の構成を示す図である。
【発明を実施するための形態】
【０００９】
＜第１の実施の形態＞
図１は、本実施の形態にかかる通信制御システム９０の第１の構成例を示す。通信制御システム９０は、通信網１０に接続された複数のコンピュータ等である処理サーバ装置１を包含する。なお、個々の装置を区別する場合、各装置は、１ａ、１ｂ、１ｃ、等の符合で参照される。装置内の構成要素についても同様である。
処理サーバ装置１の各々は、データ格納部１４と、データ処理部１３と、通信先格納部１２と、負閉路探索部１１とを包含する。データ格納部１４は、プログラム等によるデータ処理の入力となるデータを格納している、または、データ処理から出力されたデータを格納する。
データ処理部１３は、指定されたデータを処理する論理装置であり、例えば、指定されたプログラムを実行するプロセッサである。データ処理部１３は、指定されたデータ格納部１４に格納されているデータを取得して処理し、指定されたデータ格納部１４にデータを出力する。
データ処理部１３が取得または出力するデータが格納されるデータ格納部１４は、同じ処理サーバ装置１のものであっても、異なる処理サーバ装置１のものであっても良い。例えば、データ処理部１３ａは、データ格納部１４ｂに格納されているデータを取得して処理し、出力データをデータ格納部１４ｃに格納しても良い。本実施形態の通信制御システム９０は、データ処理部１３とデータ格納部１４との間で、通信網１０に発生する通信負荷を低減させる。
通信先格納部１２は、処理の入出力データを通信する相手となる処理サーバ装置１の識別子を格納する。
負閉路探索部１１は、他の処理サーバ装置１の負閉路探索部１１とメッセージ交換を行って、処理サーバ装置１間（厳密には、データ処理部１３とデータ格納部１４との間）の通信負荷を低減させる、データを格納する処理サーバ装置１とデータを処理する処理サーバ装置１の組み合わせを検出する。
この構成例において、負閉路探索部１１は、同じ処理サーバ装置１に含まれるデータ処理部１３、データ格納部１４に関する処理を行う。
なお、データ処理部１３は、データ格納部１４からデータの入力、または、データ格納部１４へのデータの出力の一方だけを行っても良い。また、処理サーバ装置１は、データ処理部１３、データ格納部１４のうち、何れか一方だけを備えていても良い。即ち、処理サーバ装置１は、データ処理に特化した処理サーバ、データ格納に特化したデータサーバあるいは、ファイルサーバであっても良い。
図２は、本実施の形態にかかる通信制御システム９０の第２の構成例を示す。この通信制御システム９０は、データ格納先管理装置４と、通信網１０に接続されたコンピュータ等であるワーカ装置２とマスタ装置３とを包含する。各マスタ装置３は、１以上、通常は複数台のワーカ装置２と対応付けされている。マスタ装置３および、当該マスタ装置３とワーカ装置２は、例えば、システム定義情報で対応付けがなされていれば良く、ネットワーク・トポロジや通信コスト等の観点で、近くに配置されている必要はない。
ワーカ装置２は、上述したデータ処理部１３およびデータ格納部１４を包含し、あるワーカ装置２のデータ処理部１３と同一又は他のワーカ装置２のデータ格納部１４との間でデータの送受信を行う。ワーカ装置２は、データ処理部１３とデータ格納部１４のいずれか一方だけを備えていても良く、データの処理に特化した処理サーバ、データの格納に特化したデータサーバ、ファイルサーバ、ストレージ装置であっても良い。
この通信制御システム９０は、データ処理部１３とデータ格納部１４との間（換言すれば、ワーカ装置２間）で、通信網１０に発生する通信負荷を低減させる。
マスタ装置３は、負閉路探索部１１と通信先格納部１２を包含する。
通信先格納部１２は、同部を包含するマスタ装置３に対応するワーカ装置２ごとに、当該ワーカ装置２がデータを取得または出力すべきワーカ装置２の識別子を格納する。
なお、処理サーバ装置１、ワーカ装置２、および、マスタ装置３の、負閉路探索部１１、通信先格納部１２、データ処理部１３およびデータ格納部１４は、論理回路、記憶装置等のハードウェアから構成される。各部の一部又は全ては、各装置のプロセッサで実行されるソフトウェアにより実現されても良い。
負閉路探索部１１は、他のマスタ装置３の負閉路探索部１１とメッセージ交換を行って、ワーカ装置２間（厳密には、データ処理部１３とデータ格納部１４との間）の通信負荷を低減させる、データを格納するワーカ装置２とデータを処理するワーカ装置２の組み合わせを検出する。
この構成例において、負閉路探索部１１は、当該負閉路探索部１１を包含するマスタ装置３に対応付けられている１または複数のワーカ装置２に含まれるデータ処理部１３、データ格納部１４に関する処理を行う。
データ格納先管理装置４は、負閉路探索部１１と、データの識別子や属性に対して当該データを格納するワーカ装置２の識別子を記憶したデータ格納先格納部１８を包含する。データ格納先管理装置４は、通信制御システム９０において、データの識別子や属性から、そのデータの格納先であるワーカ装置２を特定する。データ格納先管理装置４は、単一のコンピュータ等の装置であっても、複数の装置からなるシステム等であっても良い。
図５は、負閉路探索部１１の構成を示す。負閉路探索部１１は、ノード情報格納部１１１と、通信コスト算出部１１２と、ノード情報生成部１１３と、探索処理部１１０とを含む。
負閉路探索部１１は、通信制御システム９０を、処理サーバ装置１またはワーカ装置２をノードとする通信ネットワークとしてモデル化し、関連情報を生成等する。負閉路探索部１１は、処理サーバ装置１またはワーカ装置２がデータ処理部１３を備えて処理サーバ等として機能するときはそれらを処理ノードとしてモデル化し、データ格納部１４を備えてファイルサーバ等として機能するときはそれらをデータノードとしてモデル化する。
なお、負閉路探索部１１は、データ処理部１３およびデータ格納部１４を備えて、処理サーバ等およびデータサーバ等として機能する処理サーバ装置１またはワーカ装置２は、データノードと処理ノードの２つのノードとしてモデル化する。したがって、負閉路探索部１１は、一台の処理サーバ装置１またはワーカ装置２を、１つのノードとして扱うこともあるし、２つのノードとして扱うこともある。
以降の説明に於いて、メッセージ交換はノード間で行われる。一台の処理サーバ装置１またはワーカ装置２が複数のノードをモデル化している場合、当該ノード間のメッセージ交換は、例えば、一台の処理サーバ装置１またはワーカ装置２内で擬似的に実行される。
なお、負閉路探索部１１等の動作の説明に於いて、『当該ノード』という言葉は、図１に示す通信制御システム９０に於いて、その負閉路探索部１１等を含む処理サーバ装置１がモデル化されたノードを指す。図２に示す通信制御システム９０に於いては、『当該ノード』という言葉は、その負閉路探索部１１等を含むマスタ装置３に対応する、何れかのワーカ装置２がモデル化されたノードを示す。
また、以下の説明に於いて、『そのノード』という言葉は、複数のノードのおのおのを処理対象として繰り返し実行される処理が、ｎ番目（ｎは、１乃至繰り返しの最大数の何れかの数）に実行されたときに処理対象とするノードを示す。
ノード情報格納部１１１は、ノード間の通信コストや、メッセージ交換を行うノードの情報を格納する。
通信コスト算出部１１２は任意の２つのノード間の通信コストを算出する。なお、一台の処理サーバ装置１またはワーカ装置２が２つのノードとしてモデル化されている場合、通信コスト算出部１１２は、両ノード間の通信コストをゼロとして出力しても良い。
ノード情報生成部１１３は、メッセージ交換を行うノードの情報を生成する。探索処理部１１０は、ノード情報格納部１１１に格納された情報を参照して、他のノードとメッセージ交換を行う。
なお、図５は、処理サーバ装置１における構成を示すが、マスタ装置３の負閉路探索部１１の構成も同様である。処理サーバ装置１またはマスタ装置３は、後述するプログラム格納部１５、実行状態格納部１６、処理移動部１７または表示実行部１８を備えていても良い。
図６は、負閉路探索部１１内の通信コスト算出部１１２とノード情報生成部１１３の構成を示す。
ノード情報生成部１１３は、通信先取得部１１３１と、ノード作成部１１３２と、ノード情報交換部１１３３とを包含する。通信先取得部１１３１は、当該ノードとの間でデータ通信を実行または予定している他のノードの識別子を、その通信容量（ｂｐｓ）あるいは総データ量（Ｂｙｔｅｓ）などの通信利用状況に関する情報とともに取得する。
ノード作成部１１３２は、当該ノードと関連する他ノードの情報を、通信先取得部１１３１や、後述のノード情報共有格納部１１３４や、他ノードのノード情報格納部１１１から取得し、ノード情報格納部１１１に格納する。ノード作成部１１３２は、さらに、ノード間の通信コストを通信コスト算出部１１２１から取得し、ノード情報格納部１１１に格納する。
なお、通信制御システム９０は、複数の異なるノード間出ノード情報を共有する為のノード情報共有格納部１１３４を備えていても良い。ノード情報共有格納部１１３４は、ノード情報生成部１１３等からアクセス可能である。
通信コスト算出部１１２は、図６を参照すると、対象ノード情報格納部１１２２と、通信コスト算出部１１２１とを包含する。対象ノード情報格納部１１２２は、負閉路探索部１１が通信負荷低減の対象とする他ノードに関する情報を格納する。通信コスト算出部１１２１は、当該ノードと他のノードとの通信コストを算出する。
ノード間の通信コストは、通信制御システム９０の管理者等がそのノード間の通信を避けたい度合いを示す値である。通信コストは、一般的には、通信容量の小ささ、伝送遅延の大きさ、通信品質の悪さ、通信料金の高さ等であるが、これに限定されない。算出手法も、特に限定されない。
一つの手法は、通信網１０におけるノードとスイッチとの接続情報を用いる。通信コスト算出部１１２１は、通信網構成格納部１１２３と構成コスト格納部１１２４を参照して、通信コストを算出する。ここで、通信網構成格納部１１２３はノードとスイッチの接続情報を格納し、構成コスト格納部１１２４は同一スイッチに接続したノード同士であればコストが２である、などの接続関係に応じた静的なコストを格納する。
一方、通信コスト算出部１１２１は、動的に変化する通信負荷に対応するため、実行されている通信の利用帯域や、バッファ長などから通信コストを算出する方式を用いても良い。この場合、通信コスト算出部１１２１は、例えば、通信網１０におけるノード間の接続情報と、接続に関与するスイッチに関しての通信負荷情報を格納している通信装置負荷格納部１１２５を参照する。
通信コスト算出部１１２１は、ノード間の接続情報を用いない方法である非特許文献１に記載のノード座標を用いる方法に従って通信コストを算出しても良い。この方法は、任意の２ノード間の通信遅延がユークリッド距離で推定できるように、各ノードを通信網１０の仮想的なユークリッド空間で表現する。同部は、ノード座標を格納したノード座標格納部１１２６を参照しても良い。
図７は、探索処理部１１０の構成を示す。探索処理部１１０は、複数の処理サーバ装置１やマスタ装置３に跨って散在するノード情報格納部１１１に格納されたノード間のグラフにおいて、エッジに付された通信コストの総和が負であるような閉路を探索する。探索処理部１１０は、複数の処理サーバ装置１やマスタ装置３間でメッセージ交換して負閉路を探索する。
探索処理部１１０は、図７を参照すると、起動部１１０１と、受信部１１０２と、転送部１１０３と、経過格納部１１０５と、負閉路検出部１１０４を包含する。
起動部１１０１は、当該ノードの局所的な通信負荷が、予め与えられた一定の閾値を越えたか否かなどの判定を行う。転送部１１０３は、ノード間で交換されるメッセージに負荷されたコストを更新し、どの他ノードに転送するかの判断を行う。経過格納部１１０５は、他ノードから受信した探索経過を格納する。
受信部１１０２は、他のノードから探索情報を受け付け、その種別に応じて、転送部１１０３や負閉路検出部１１０４に出力する。
負閉路検出部１１０４は、その探索経過を集計して、処理サーバ装置１やワーカ装置２の通信利用状況と利用可能状況をモデル化したノード間のグラフにおいて、そのコストの総和が負である閉路を検出し、その総コスト、可能な通信変更量などを算出して、処理移動部１７や表示実行部１８等に出力する。
ここで、処理移動部１７や表示実行部１８は、例えば、処理サーバ装置１やマスタ装置３が、負閉路探索部１１外に備えている（図５参照）。
処理移動部１７は、負閉路検出部１１０４が出力する閉路（ノードの識別子のシーケンス等）情報に基づいて、処理の開始や移動を行う処理サーバ装置１やワーカ装置２を特定し、データ処理の開始や変更等を処理サーバ装置１やワーカ装置２に指示する。さらに、処理移動部１７は、新たな処理を開始する処理サーバ装置１やワーカ装置２に、処理プログラムを送信して、インストール、ダイナミックローディング、デプロイを指示しても良い。
プログラムの送信は、データ処理部１３がデータを処理する為に実行するプログラムが、全ての処理サーバ装置１やワーカ装置２に予め配備されたプログラムではなく、ユーザにより与えられたプログラムであるような場合に必要となる。プログラム格納部１５は、受信したプログラムの一時保存をしても良い。
処理サーバ装置１やワーカ装置２に対するデータ処理の開始、変更指示やプログラム配備は、通信制御システム９０のオペレータ等が各処理サーバ装置１やワーカ装置２に対して実施しても良い。この場合、表示実行部１８等は、負閉路検出部１１０４の出力した閉路情報を外部に表示する。
実行状態格納部１６は、データ処理部１３が状態を持って処理実行されている際に必要となる。処理を他のデータ処理装置１またはワーカ装置２に移動させる際に、データ処理部１３または処理移動部１７が、状態の一時格納先として用いる。なお、図２の通信制御システム９０に於いては、プログラム格納部１５や実行状態格納部１６は、マスタ装置３またはワーカ装置２の何れが備えていても良い。
図２１は、表示実行部１８が出力する表示画面２００の一例を示す。この例に於いて、表示実行部１８は、負閉路検出部１１０４の出力情報に基づいて、通信コストが低減する処理の配置計画をシステム管理者等に表示する。
この表示画面２００は、例えば、変更計画一覧２０１と、詳細表示画面２０２と、可視化画面を包含する。変更計画一覧２０１は検出された処理の配置変更計画を一覧表示する。詳細表示画面２０２は、特定の計画に関して、その変更計画の対象となる処理名およびデータ名、通信量とともに、移動元のサーバ、ならびに移動先のサーバを表示する。可視化画面は、特定の計画に関する、その変更を実行する前後のシステム構成ならびに通信量を表示する。
システム管理者等は、提示された変更計画を妥当と判断した際に、その変更承認指示を処理サーバ装置１等に入力する。表示実行部１８は、その指示を受け付け、変更実施指示を処理移動部１７に与える。
また、表示画面２００は、負閉路検出部１１０４が検出した負閉路の表示（例えば、図３８）を包含しても良い。この場合、システム管理者等は、表示画面２００を見て、各処理サーバ装置１、マスタ装置３、または、ワーカ装置２に、データ処理の開始、プログラムのインストール等の指示コマンドを入力する。
図３および図４は、本発明にかかる通信制御システム９０で実行される通信変更、処理の配置変更の例を示す。この変更は、通信制御システム９０に於ける、処理サーバ装置１またはワーカ装置２間の通信コストを低減させる。図３はサーバ処理装置１によるストリーム処理、図４はワーカ装置２によるバッチ処理についての図である。
ストリーム処理は、プログラム動作しているコンピュータ等に、単位時間当たりにある量のデータが投入され、常時実行される処理である。バッチ処理は、特定のデータ量を持つデータがコンピュータ等に割り当てられ、その量の処理が実行されると終了する処理である。
また、図３は、処理サーバ装置１の間の詳細な接続関係が明らかでない状況を示す。ただし、この通信制御システム９０には、図３の矢印の長さが示す通信遅延が発生する。
図３の通信制御システム９０は、第１の処理と第２の処理を実行している。第１の処理に於いては、データストリーム１４０ａが処理サーバ装置１ｈで発生し、移動可能な処理１３０ａがこれを処理し、その結果を、処理１３０ｃが実行されている処理サーバ装置１ｄに渡す。処理１３０ｃは、他の処理サーバ装置１では実行不可能である。
第２の処理は、データストリーム１４０ｂが処理サーバ装置１ｉで発生し、移動可能な処理１３０ｂがこれを処理し、その結果を、処理サーバ装置１ｅのデータ格納部１４ｅに格納する。
図３において、データ処理１３０ｂが処理サーバ装置１ｆに存在し、データ処理１３０ａが処理サーバ装置１ｇに存在する利用状態は、非効率な通信状態である。この後、通信制御システム９０は処理の配置変更を実行し、データ処理１３０ｂを処理サーバ装置１ｇで実行し、データ処理１３０ａを処理サーバ装置１ｆで実行するように変更する。このため、通信制御システム９０は、通信を効率的に利用できる。
図４の通信制御システム９０は、最初に第１の処理のみを実行している。第１の処理は、ワーカ装置２ｂに格納されたデータ１４０ａに対して処理１３０ａを実行する。この処理１３０ａは、ワーカ装置２ｂに最も近いワーカ装置２ｂにて実行されている。
次にｔ１の時点で、通信制御システム９０は第２の処理を開始する。第２の処理はワーカ装置２ｂに格納された別のデータ１４０ｂに対して、処理１３０ｂを実行する。この処理１３０ｂは、例えば、別のワーカ装置２ｅにて実行される。
第１の処理が終了した後、ｔ２時点で、ワーカ装置２ｆに格納されたデータ１４０ｃを処理１３０ｃが処理する第３の処理が開始される。処理１３０ｃは、例えば、第１の処理が利用していたワーカ装置２ｆに割り当てられる。このとき通信制御システム９０は、上段のスイッチを経由する通信を２つ実行し、非効率な通信状況となる。
この後ｔ３時点で、通信制御システム９０は処理の配置変更を実行し、処理１３０ｂをワーカ装置２ｂにて実行する。この結果、処理１３０ｂは、同一ワーカ装置２ｂ上のデータを処理する状態となる。また、通信制御システム９０は、処理１３０ｃをワーカ装置２ｅで実行して、同一スイッチに接続しているワーカ装置２ｆ上のデータ１４０ｃを処理するように変更する。
次に、図８Ａ乃至図１２のフローチャートおよび図１３及び図１９のテーブルを参照して、本実施の形態の通信制御システム９０の動作を説明する。本実施の形態では、探索処理部１１０が、フラッディングにより、総コストが負である閉路を探索する。
本実施形態に於いて、フローチャートで示される手順を実行するのは、図１の構成では処理サーバ装置１ａ〜１ｃ等、図２の構成ではマスタ装置３ａ〜３ｂ等である。また、ここで述べる手順にて処理される対象ノードは、図１の構成では処理サーバ装置１であり、図２の構成ではマスタ装置３が管理するワーカ装置２ａ〜２ｄ等である。
さらに、各処理サーバ装置１とワーカ装置２は、データ処理部１３ａ〜１３ｃ等をモデル化した処理ノード１ａＰ〜１ｃＰ等、ならびに、データ格納部１４ａ〜１４ｃ等をモデル化したデータノード１ａＤ〜１ｃＤ等として別々に処理対象となる。
図８Ａ乃至図８Ｃは、ノード情報生成部１１３におけるノード作成部１１３２の動作フローチャートである。ノード作成部１１３２は、ノード間の有向リンクを生成する。具体的に、ノード作成部１１３２は、あるノードのノード情報格納部１１１に出ノードリスト６１を作成し、リンク先のノードのノード情報格納部１１１に入ノードリスト６２を作成する。
ノード情報格納部１１１はノードごとに存在する。従って、処理サーバ装置１またはワーカ装置２が、処理ノードとしてもデータノードとしても機能する場合、処理サーバ装置１またはマスタ装置３は、処理ノード用およびデータノード用の２つのノード情報格納部１１１を備える。経過格納部１１０５および経路格納部１１０６も同様である。
図１９は、ノード情報格納部１１１のデータ構成を示す。ノード情報格納部１１１は、出ノードリスト６１、入ノードリスト６２、処理ノード候補リスト６３及びノード数６４を包含する。
出ノードリスト６１は、当該ノードを起点とするリンク（出線）の終点ノード（出ノード）情報のリストである。出ノードリスト６１は、出ノード対応に、ノードの識別子、そのノードまでの通信コスト、通信変更上限の３つのデータを包含する。
入ノードリスト６２は、当該ノードを終点とするリンク（入線）の起点ノード（入ノード）情報の集合である。入ノードリスト６２は、入ノード対応に、ノードの識別子を包含する。
処理ノード候補リスト６３は、出ノードリスト６１、入ノードリスト６２に入れる処理ノード候補の識別子リストである。処理ノード候補リスト６３は、通信制御システム９０に包含される通信可能な全ての処理ノードのリストであっても良い。ノード数６４は、通信制御システム９０に属するノード数の総数として見なす値を包含する。
処理ノード候補リスト６３とノード数６４は、予め与えられていても良い。あるいは、ノード作成部１１３２等が、ノード情報共有格納部１１３４の情報、他ノードのノード情報格納部１１１の情報、あるいは探索処理部１１０が他ノードとのメッセージ交換で取得した情報から生成しても良い。この場合、ノード作成部１１３２等は、例えば、取得された全ノードの識別子数をノード数６４とし、取得された全ノードのうち、処理ノードであるものを処理ノード候補リスト６３に登録する。
図８Ａ及び図８Ｂは、処理ノードを対象に、当該ノードと他の処理ノードやデータノードとのリンクを生成する手順を示す。図８Ｃは、データノードを対象に、当該ノードと処理ノードとのリンクを生成する手順を示す。図８Ａ乃至図８Ｃに示すノード作成部１１３２の手順は一例であり、一方の手順の中で、他方の手順を実行しても良い。
図８Ａ乃至図８Ｃに示す手順は、処理ノードからデータノードへのリンクを作成する手順と、処理ノードから処理ノードへのリンクを作成する手順を包含する。
なお、ノード作成部１１３２等は、図８Ａならびに図８Ｃに示す手順実行前に、当該ノード対応のノード情報格納部１１１を適切に初期化する。
図８Ａの手順において、ノード作成部１１３２等は、先ず出ノードリスト６２をクリアする（Ｓ８１）。
ノード作成部１１３２は、処理ノードからデータノードへのリンクを作成する手順（Ｓ８２）において、以下を実行する。まず、ノード作成部１１３２は、当該処理ノードが他ノードからデータを取得している状況・取得計画を通信先格納部１２から取得する。次にノード作成部１１３２は、その各々のノードについて、ノード識別子と、通信コスト算出部１１２から得たそのノードとの通信コストの負値を、ノード情報格納部１１１の出ノードリスト６２に格納する。さらに、ノード作成部１１３２は、現在利用中・計画の処理量を通信変更上限として格納する。
ここで、通信コストの負値は、通信コストと絶対値が同じで、正負を逆転した値である。ノード作成部１１３２が出ノードリスト６２に通信コストの負値を格納する理由は、転送部１１０３等で行う閉路の総コスト計算を加算処理に統一するためである。ノード作成部１１３２は通信コストそのものを出ノードリスト６１に格納し、転送部１１０３等で、加算すべき場合と減算すべき場合を切り分けて、閉路の総コストを計算しても良い。
ノード作成部１１３２は、さらに、そのノードに対して、当該ノードの識別子をそのノードノード情報格納部１１１の入ノードリスト６２に格納するように通知する。但し、図２に示す通信制御システム９０の場合は、各ノードに通知するのではなく、各ノードに関連付けられたマスタ装置３に通知する（以降、この注釈は省略する）。
ここで、現在利用中とは、ストリーム処理等に於いて、この処理ノードが別のデータノードからデータをある帯域（Ｍｂｐｓ）で読んでいる、あるいは別のデータノードに書いていることを意味する。また、計画とは、バッチ処理等に於いて、この後に、この処理ノードが別のデータノードからあるデータ量（ＧＢｙｔｅ）読む計画である、あるいは別のデータノードにあるデータ量書く計画である、ことを意味する。
次に、当該ノードが移動可能な処理を実行していた場合（Ｓ８３でＹ）、ノード作成部１１３２は、処理ノードから処理ノードへのリンクを生成する（Ｓ８４）。
ここで、ノード作成部１１３２は、ノード情報格納部１１１の処理ノード候補リスト６３に登録されている処理ノードのうち、残存処理可能量がゼロではないノードを選択し、その処理ノードの識別子を当該ノードの入ノードリスト６２に格納する。ノード作成部１１３２は、そのノードに対して当該ノードの識別子、ゼロの通信コスト、無限大の通信変更上限をそのノードの出ノードリスト６１に格納するよう通知する。ここで、無限大とは、通信制御システム９０の通信変更上限（通信量）として可能な値より大きな値、例えば、ノードが取りうる整数値の最大値である。他の変数についても同様である。
また、ノード作成部１１３２は、処理ノードを、処理ノード候補リスト６３からではなく、ノード情報共有格納部１１３４等から取得しても良い。
なお、ここでこのような条件で処理ノードから他の処理ノードへのリンクを設ける効果を述べる。このようなリンクがない状況で、探索処理部１１０が、あるデータノードから処理ノードを経て、別のデータノードへ至る経路を含んだ閉路を検出し、その経路に沿って通信の変更を実行しても、この経路上の処理ノード自体が送受信する通信量は変わらない。そのため、処理移動部１７等が、初期状態から通信コストを減らすような変更を複数加えても、その初期状態に依存した値にまでしか通信コストの最小化しかできない。
そこで、本実施の形態の通信制御システム９０は、処理ノード間でリンクを持ち、データノードから処理ノードを経由し、また別の処理ノードを経由して、別のデータノードに至る経路を含む負閉路を検出する。このような負閉路を検出することで、通信制御システム９０は、前者のデータノードと前者の処理ノード間の通信を増加させ、後者の処理ノードとデータノード間の通信を減少させ、初期状態に依存せずに通信コストを低減する。
このような目的で処理ノード間のリンクを張るため、ノード作成部１１３２は、まだ何らかの処理を実行できる処理ノード（残存処理可能量が非ゼロ）から、何らかの処理を実行している処理ノードへのリンクのみを生成する。
なお、ここで上記要件を満たす任意の処理ノードの対について、リンクを生成するのではなく、ノード生成部１１３２は、仮想的なノードを設け、残存処理可能量が非ゼロの処理ノードから、この仮想的なノードへのリンクをもち、この仮想的なノードから、何らかの処理を実行している処理ノードへのリンクを持つようにしても良い。
また、ノード作成部１１３２は、本処理の終了前に、前回実行時以降の通信状態等の変更を反映させて、入ノードリスト６２等からノードを削除する（Ｓ８５、Ｓ８６）。
ノード作成部１１３２は、図８Ｃの手続きを、例えば、図８Ａ及び図８Ｂの処理に続いて実行する。
ノード情報格納部１１１の入ノードリスト６２に処理ノードが存在する場合（Ｓ８７でＹ）、ノード作成部１１３２は、入ノードリスト６２内の処理ノードから、その処理ノードが当該データノードのデータを処理する単位処理量を取得し、その最小値を最小単位処理量とする（Ｓ８８）。
さらに、ノード作成部１１３２は、処理ノード候補リスト６３内の処理ノードについて、以下の処理を行う。まず、その処理ノードの残存処理可能量がゼロでないか（Ｓ８９でＮ）、あるいはゼロであって、その処理ノードで実行中の処理のうちで最大の単位処理量が最小単位処理量より小さくない場合（Ｓ８ＡでＮ）、ノード生成部１１３２は、当該ノードとそのノードとの間の通信コストを通信コスト算出部１１２から取得する（Ｓ８Ｂ）。ノード生成部１１３２は、そのノードの識別子、通信コスト、無限大の通信変更上限を、当該ノードのノード情報格納部１１１の出ノードリスト６１に格納し、そのノードの入ノードリスト６２に当該ノードの識別子を登録するよう通知する（Ｓ８Ｃ）。
なお、ノード生成部１１３２は、ここで登録する通信変更上限を、このデータノードと処理ノードの間の通信路の最小帯域としても良い。ストリーム処理における場合、このようにすることで、通信制御システム９０は、通信路の帯域より大きな通信を行う計画を回避することができる。
本手順にて、このような単位処理量に応じたリンク生成を行う理由を述べる。残存処理能力が非ゼロの場合、このデータノードのデータをその処理ノードが処理するように追加する変更計画は妥当である。また、残存処理能力がゼロであっても、その処理ノードが現在処理中の通信量あたりの負荷よりも、新たに追加候補となるデータノードからのデータ処理の負荷が小さければ、その追加計画は妥当である。従って、ノード作成部１１３２は、このような場合に変更計画が生成され得るようにリンクを生成する。
図９は、起動部１１０１の動作フローチャートである。起動部１１０１は、サービス終了等の終了設定がされていない限り動作し続ける（Ｓ９１でＮ）。起動部１１０１は、当該ノードに関する局所的な通信負荷を監視し、その局所負荷が閾値を越えると（Ｓ９２でＹ）、起点ノードを当該ノード、探索長を１として、探索要求４０を生成する（Ｓ９３）。
起動部１１０１は、このノードのノード情報格納部１１１の出ノードリスト６１に格納されている複数のノードのそれぞれに探索要求４０を送信する。このとき、起動部１１０１は、探索要求４０の総コストとしてそのノードへの通信コストを、通信変更上限としてそのノードへの通信変更上限を設定し、ノードリストにそのノードの識別子を追加する（Ｓ９４）。その後、起動部１１０１は、負閉路検出部１１０４から通知される、探索の終了を待ち合わせる（Ｓ９５）。
図１０は、受信部１１０２の動作フローチャートである。受信部１１０２は、サービス終了等の終了設定がされていない限り動作し続ける（Ｓ１０１でＮ）。受信部１１０２は、受信した探索情報の種別を判定し（Ｓ１０３）、探索結果４１であれば、負閉路検出部１１０４に、探索結果４１に基づく処理移動を依頼する（Ｓ１０４）。また、探索要求４０であれば、受信部１１０２は、転送部１１０３に、受信した探索要求４０を更新し、他ノードに転送することを依頼する（Ｓ１０５）。
図１３は、受信部１１０２等で交換されるメッセージの内容を示す。探索要求４０は、起点ノード、ノードリスト、探索長、総コスト、通信変更上限を包含する。探索結果４１は、ノードリスト、総コスト、通信変更上限を包含する。
起点ノードは、探索要求４０を生成して発信したノードの識別子である。ノードリストは、探索要求４０が転送された経路（探索経路）上のノードの識別子のリストである。ノードリストは、各ノードの残存処理可能量、単位処理量も包含する。探索長は、探索経路の長さである。総コストは、探索経路上に存在するノード間の通信コストの総和である。通信変更上限は、探索経路上に存在するノードに対応する通信変更上限の最小値である。
図１１Ａ及び図１１Ｂは、転送部１１０３の動作フローチャートである。転送部１１０３は、探索要求４０内のノードリストに、当該ノードが存在するか否かを確認する。存在する場合（Ｓ１１１でＹ）、転送部１１０３は探索要求４０内の総コストが負であるか否かを判定し、負である場合（Ｓ１１７でＹ）、探索要求４０の起動ノードに対して、探索結果４１を通知する（Ｓ１１８）。負でない場合（Ｓ１１７でＮ）、転送部１１０３は、動作を終了する。
探索要求４０のノードリストに当該ノードが存在しない場合（Ｓ１１１でＮ）、転送部１１０３は、探索要求４０内の探索長が予め与えられた最大長より大きいか否かを判定し、大きい場合（Ｓ１１２でＹ）、終了する。
探索要求４０内の総コストが予め与えられた終了閾値以上である場合も（Ｓ１１３でＹ）、転送部１１０３は終了する。これらの条件により、転送部１１０３は、通信網１０内の探索要求４０の転送を制限する。
この条件を満たさない場合（Ｓ１１３でＮ）、転送部１１０３は、ノード情報格納部１１１の出ノードリスト６２の各ノードについて、以下の処理を行う。
転送部１１０３は、受信した探索要求４０の総コストに、そのノードへの通信コストを加算し、探索長を１加算し、ノードリストに当該ノードの識別子を追加する。当該ノードが処理ノードの場合、転送部１１０３は、ノードリストに当該ノードの残存処理可能量と単位処理量を追加する。また、そのノードの通信変更上限が、探索要求４０内の通信変更上限より小さければ、探索供給４０の通信変更上限を、そのノードの通信変更上限で更新する（Ｓ１１４）。
その後、そのノードが探索要求４０内の起動ノードであり（Ｓ１１５でＹ）、かつ、探索要求４０の総コストが負であれば（Ｓ１１９でＹ）、転送部１１０３は、探索結果４１を起動ノードに通知する（Ｓ１１Ａ）。そのノードが起動ノードでない場合（Ｓ１１５でＮ）、転送部１１０３は、探索要求４０を、そのノードに送信し（Ｓ１１６）、動作を終了する。
図１２は、負閉路検出部１１０４の動作フローチャートである。負閉路検出部１１０４は、受信した探索結果４１を経過格納部１１０５に格納し（Ｓ１１０５）、それが予め定められた一定量以上となると（Ｓ１２２でＹ）、経過格納部１１０５に格納された探索結果４１のそれぞれについて、変更流量と総コストの積を求める（Ｓ１２３〜Ｓ１２４）。
負閉路検出部１１０４は、先ず、探索結果４１に含まれる処理ノードごとの処理追加可能量を算出する（Ｓ１２３）。
具体的に、先ず、負閉路検出部１１０４は、探索結果４１のノードリストから、当該処理ノードの残存処理可能量（Ｐ）、当該処理ノードの単位処理量の最小値（Ｌ２）、閉路の経路に於いて、当該処理ノードの一つ前のデータノードの単位処理量（Ｌ１）を取得する。１）その処理ノードの前後のノードがデータノードである場合、即ち、その処理ノードが処理中のデータ量を減らし、新たなデータの処理を追加する場合であって、Ｌ１＜＝Ｌ２であれば、負閉路検出部１１０４は、その処理ノードの処理追加可能量を無限大とする。この場合、その処理ノードの処理負担は軽くなるので、変更量は制限されない。２）その処理ノードの前後のノードがデータノードである場合であって、Ｌ１＞Ｌ２であれば、負閉路検出部１１０４は、その処理ノードの処理追加可能量をＰ／（Ｌ１−Ｌ２）とする。この場合、変更量を大きくすると、単位変更量当たり（Ｌ１−Ｌ２）だけ処理量の負担が増えるため、変更量は、残存処理可能量で制約される。３）前のノードがデータノードで、後ろのノードが処理ノードの場合、即ち、処理中のデータ量は減らず、新たなデータの処理を追加する場合は、負閉路検出部１１０４は、その処理ノードの処理追加可能量をＰ／Ｌ１とする。４）前のノードが処理ノードの場合、即ち、新たなデータの処理を追加しない場合は、負閉路検出部１１０４は、その処理ノードの処理追加可能量を無限大とする。
変更流量は、算出された処理追加可能量の最小値と通信変更上限の小さい方の値である。処理ノードごとの処理追加可能量の算出（Ｓ１２３）後、負閉路検出部１１０４は、この変更流量と総コストの積を求める（Ｓ１２４）。
最後に、負閉路検出部１１０４は、変更流量と総コストの積が最大である探索結果４１のノードリスト及び変更流量を処理移動部１７に出力し、処理の移動と処理プログラムの配備を処理移動部１７に要求する（Ｓ１２５）。
処理移動部１７は、入力したノードリストが示す閉路に含まれるデータノードの変更流量分のデータの通信先を、転送経路順に於けるそのデータノードの前の処理ノードから後の処理ノードに変更させる。このため、処理移動部１７は、変更対象となるデータノードや処理ノードに変更要求の通知等を行い、かつ、新たな処理を行う処理ノードに対して、プログラムの送信等を行う。
なお、負閉路検出部１１０４は、変更流量と総コストの積が最大である探索結果４１のノードリスト及び変更流量を表示実行部１８に出力し、望ましい配備変更としてオペレータ等に向けて表示させても良い。
本実施の形態の通信制御システム９０は、複数のノード（処理サーバ装置１またはワーカ装置２）がデータを通信しながら進めるデータ処理を、複数実行している通信制御システム９０において、当該複数のデータ処理全体としての通信負荷を低減することを可能とする。
その理由は、探索処理部１１０等が、総コストが負となるノードの通信パスの閉路を検出して、その負閉路（ノードの識別子の経路順のシーケンス）を出力するからである。当該負閉路は、データ通信を実行している複数組のデータノードと処理ノードを含み得る。処理移動部１７或いは通信制御システム９０のオペレータ等は、当該出力に基づいて、複数の通信に渡る通信コストの総和を低減するような処理配置変更が可能である。特に、本実施の形態の通信制御システム９０は、第１の処理を実行している処理ノードから、当該第１の処理を他のノードに移動させて、新たに第２の処理を実行させるような柔軟な処理の配置変更も可能である。
さらに、この変更計画は、処理すべきデータをすべて処理する、または、処理サーバ装置１の処理能力以上のデータ処理を割り当てない等の動作制約を満たす。従って、この処理配置の変更は、外部から実行指示を受けた処理自体に影響を与えない。
また、本実施の形態の通信制御システム９０は、負荷低減実行のさい、特定のコンピュータや装置が負閉路検出処理等の迅速性や信頼性の点でボトルネックとなることを回避しやすくする。
その理由は、通信制御システム９０は、特定のコンピュータ等にシステム全般の通信の利用情報を集めるのではなく、異なるノードに分散して格納されている、通信の利用状態を参照し、探索要求４０等のメッセージを交換しながら、上述の負閉路を検出するからである。
＜第２の実施の形態＞
本実施の形態にかかる通信制御システム９０は、動的計画法に基づいて負閉路を検出する。通信コストが最も小さい負閉路を特定する最適化アルゴリズムは、ノード数に対してＮＰ困難である。一方、平均コストが最小の負閉路を特定するアルゴリズムは、多項式時間で終了することが、Ｋａｒｐの定理として知られている。Ｋａｒｐの定理は、以下の式の原理に基づく。
Ｍ  ＝  ｍｉｎ  ｍａｘ（ｄＮ（ｖ）−ｄｋ（ｖ））／（Ｎ−ｋ）．．．（１）
ｖ∈Ｖ  ｋ＝１〜Ｎ−１
ここで、Ｍは最小平均コスト、Ｎはノード数、Ｖはノード集合、ｄｋ（ｖ）は或るノードからノードｖにｋホップで辿りつく経路（Ｗａｌｋ）のコスト中で最小のコスト、ｄＮ（ｖ）は或るノードからノードｖにＮホップで辿りつく経路のコスト中で最小のコストである。
なお、最適解は、最小平均コストの負閉路の除去を、多項式回数実行することで得られる。
本実施の形態の通信制御システム９０は、分散したデータ格納部１４やデータ処理部１３間の通信を低減するための最適化処理を、特定の処理サーバ装置１やマスタ装置３に集中せずに分散的に実行する。即ち、単一のコンピュータ等が、上記定理に基づいて最適化処理を逐次的に実行するのではなく、非同期に動作する複数の処理サーバ装置１やマスタ装置３の間で、通信メッセージを交換しながら分散して実行する。
図１４は、第２の実施形態の負閉路探索部１１の構成を示す。本実施の形態の探索処理部１１０は、起動部１１０１と、受信部１１０２と、格納する経路格納部１１０６と、転送部１１０３と、経過格納部１１０５と、負閉路検出部１１０４とを含む。
起動部１１０１は、第１の実施形態と類似な処理を行う。受信部１１０２は、他の処理サーバ装置１やマスタ装置３から負閉路探索のためのメッセージを受信する。経路格納部１１０６は、探索の起点となるノードからの、メッセージ転送経路に沿ったコストの総和である総コストを、起点からのホップ数（探索長）ごとに格納する。
転送部１１０３は、他のノードの総コストと、当該ノードとそのノード間の通信コストをもとに別のノードの総コストを更新するためのメッセージ交換を行う。経過格納部１１０５は、並行かつ分散的に実行される複数の探索の結果を集計するために、その経過情報を一時格納する。負閉路検出部１１０４は、格納された複数の経過情報から、変更を加えると負荷低減に効果的な経路を決定する。
図１８は、本実施の形態で交換されるメッセージの内容を示す。探索要求４０には、通知、要求、応答の３種類が存在する。探索要求４０（通知）は、起点ノード、ノード数、探索長、総コスト、経路ノードを包含する。探索要求４０（要求）は、起点ノード、ノード数、探索長を包含する。探索要求４０（応答）は、探索長、総コストを包含する。
ここで、経路ノードは、探索要求４０が当該ノードに至る直前のノードに関する情報であり、ノードの識別子、種別（データノード／処理ノードの区別）、通信変更上限、単位処理負荷、残存処理可能量を包含する。
探索結果４１は、探索長、平均コストの最大値、経路ノードリストを包含する。経路ノードリストは、探索長ごとの経路ノードのリストである。
図２０は、経路格納部１１０６に格納される経路情報を示す。経路格納部１１０６は、１からノード数Ｎまでの探索長ごとに、経路情報を格納する。各経路情報は、総コストｄｋ、確定状態、経路ノード、入ノード状態、出ノード状態を包含する。
ここで、確定状態は、当該探索長の総コストが確定したか未確定であるかを示す。確定状態の初期値は、未確定を示す。入ノード状態は、当該ノードの各入ノードの状態を、出ノード状態は、当該ノードの各出ノードの状態を示す。状態は、ノード間リンクを辿ったか（済）、まだ辿っていないか（未：初期値）、辿っている途中か（要求中）を表す。
なお、ノード数Ｎは、各ノードに予め設定されている、または、各ノードに共有されている記憶装置等に予め設定されている。ノード数Ｎは、交換されるメッセージに格納されていても良い。
図１５は、本実施の形態における起動部１１０１の動作フローチャートである。第１の実施形態における起動部１１０１の動作フローチャート（図９）との差異は、以下の通りである。
起動部１１０１が、生成する探索要求４０は、探索要求４０（通知）である（Ｓ１５３）。起動部１１０１は、出ノードリスト６１に格納される複数のノードのそれぞれに探索要求４０（通知）を送信する際に、探索要求４０の総コストにそのノードへの通信コストを、経路ノードに当該ノードの情報を設定する（Ｓ１５４）。当該ノードの情報は、ノードの識別子、種別、送信先の出ノードに対する通信変更上限、単位処理負荷、残存処理可能量である。
図１６Ａ乃至図１６Ｃは、転送部１１０３の動作フローチャートである。
受信した探索要求４０の種類が要求である場合（Ｓ１６１でＹ）、転送部１１０３は、経路格納部１１０６を参照して、探索要求４０の探索長ｋから１を引いた探索長ｋ−１における総コストが確定しているかを判定する。
確定している場合（Ｓ１６ＢでＹ）、転送部１１０３は、探索長ｋ−１の総コストに、要求ノードに対する通信コストを加算した値を探索長ｋの総コストとして、当該ノードの情報を経路ノードとして、探索長ｋの探索要求４０（応答）を作成して、これを要求ノードに返信する。さらに、転送部１１０３は、経路格納部１１０６の探索長ｋに対応する要求元ノードの出ノード状態を済とする（Ｓ１６Ｃ）。
ここで、経路ノードに設定する当該ノードの情報は、当該ノードの識別子、当該ノードの種別、当該ノードと送信先ノード間の通信変更上限、当該ノードの単位処理負荷、当該ノードの残存処理可能量である。
確定していない場合（Ｓ１６ＢでＮ）、転送部１１０３は、探索長ｋに対する、要求ノードの出ノード状態を要求中とし（Ｓ１６Ｄ）、探索長ｋ−１の入ノード状態が済でない各ノードに、探索長ｋ−１の探索要求４０（要求）を送信し、その入ノード状態を要求中とする（Ｓ１６Ｅ）。
一方、探索要求４０の種類が、通知あるいは応答である場合（Ｓ１６１でＮ）、転送部１１０３は、受信した探索要求４０の探索長ｋの総コストが確定しているか、経路格納部１１０６の確定状態で判断する。
確定していれば（Ｓ１６２でＹ）、転送部１１０３は動作を終了する。確定していなければ（Ｓ１６２でＮ）、転送部１１０３は、当該探索要求４０内の総コストと、経路格納部１１０６に格納された探索長ｋの総コストとを比較する（Ｓ１６３、Ｓ１６４）。探索要求４０内の値の方が小さい場合（Ｓ１６４でＹ）、転送部１１０３は、探索要求４０に格納されている総コスト、経路ノードを、探索長ｋ対応の値として経路格納部１１０６に格納する（Ｓ１６５）。
その後、転送部１１０３は、当該探索要求４０を送信したノードの探索長ｋの入ノード状態を済とする（Ｓ１６６）。この結果、探索長ｋに関する入ノード状態が済みでない入ノードが残っており、かつ、探索要求４０の種類が通知であれば（Ｓ１６７でＮ、Ｓ１６ＡでＹ）、探索長ｋの入ノード状態が済でない各ノードに、探索長ｋの探索要求４０（要求）を送信し、その入ノード状態を要求中とする（Ｓ１６Ｅ）。
探索長ｋに関する入ノード状態が全ての入ノードについて済である場合（Ｓ１６７でＹ）、転送部１１０３は探索長ｋの確定状態を確定に変更し（Ｓ１６８）、探索長ｋ＋１の各出ノード状態が要求中となっている出ノードに対して、探索要求４０（応答）を送信し、出ノード状態を済に変更する。このとき、転送部１１０３は、探索長ｋの総コストにそのノードへの通信コストを加算した値を探索長ｋ＋１の総コストとし、当該ノードの情報を経路ノードとして、探索要求４０（応答）を作成する（Ｓ１６９）。
次に、この更新された探索長ｋがノード数Ｎと一致していない場合（図１６Ｂ、Ｓ１６ＪでＮ）、探索長ｋ＋１の各出ノード状態が未となっている出ノードに対して、探索要求４０（通知）を送信し、出ノード状態を済に変更する。このとき、転送部１１０３は、探索長ｋの総コストにそのノードへの通信コストを加算した値を探索長ｋ＋１の総コストとし、当該ノードの情報を経路ノードとして、探索要求４０（通知）を作成する（Ｓ１６Ｋ）。
次に、探索長が１からノード数Ｎまでで全て確定しているかを判別し、確定していない場合（Ｓ１６ＬでＮ）、転送部１１０３は動作を終了する。確定している場合（Ｓ１６ＬでＹ）、転送部１１０３は、探索長ｉが１からＮ−１までの経路について、探索長がｉの総コストをｄｉ、探索長がノード数Ｎの総コストをｄＮとして、式２を用いて平均コストを算出する（Ｓ１６Ｍ）。
（ｄＮ−ｄｉ）／（Ｎ−ｉ）．．．．（２）
転送部１１０３は、探索長ｉが１からＮ−１までの算出された平均コストのうちの最大値Ｍ、各探索長の経路ノードのリストを探索結果４１として起動ノードに送信して（Ｓ１６Ｎ）、動作を終了する。
図１７は、負閉路検出部１１０４の動作フローチャートである。探索要求４０を発信したノードに対応する負閉路検出部１１０４が、本フローチャートに示す動作を実行する。
負閉路検出部１１０４は、各ノードから受信した探索結果４１を、経過格納部１１０５に格納し（Ｓ１７１）、経過格納部１１０５に全ノードの結果が格納されたかを確認する（Ｓ１７２）。
全ての結果が格納されていない場合（Ｓ１７２でＮ）、負閉路検出部１１０４は動作を終了する。格納された場合（Ｓ１７２でＹ）、負閉路検出部１１０４は、探索結果４１の平均コストのうちで、最小の平均コストを持つ探索結果４１を取り出す（Ｓ１７３）。
最小の平均コストが負である場合（Ｓ１７４でＹ）、負閉路検出部１１０４は、取り出された探索結果４１から、探索長がノード数Ｎである経路ノードを得て、その識別子のノードを、最初のポインタノードとする（Ｓ１７５）。
次に、負閉路検出部１１０４は、探索長をノード数Ｎとして設定し、ノードリストを空に初期化し、通信変更上限を無限大とする（Ｓ１７６）。
続いて負閉路検出部１１０４は、同じポインタノードがノードリストに存在するまで、以下の処理を続ける。負閉路検出部１１０４は、ポインタノードをノードリストの末尾に追加し、それとともに探索長を１減少させる（Ｓ１７７）。経過格納部１１０５から、ポインタノードから通知された探索結果４１を取りだし、その時の探索長の値に対応する経路ノードを新たなポインタノードとし、通信変更上限を最小値に更新する（Ｓ１７８）。
その後、負閉路検出部１１０４は、ノードリスト内の各ノードの単位処理量と残存処理可能量から、閉路の処理追加可能量を算出する（Ｓ１７９）。算出方法は、実施の形態１と同じである。最後に、負閉路検出部１１０４は、処理移動部１７等を介して、ノードリストに於ける各ノードに対して処理の移動を実行する（Ｓ１７Ａ）。移動の方法は、実施の形態１と同じである。また、負閉路検出部１１０４は、表示実行部１８を介して移動計画を表示だけしても良い。
本形態の通信制御システム９０のメッセージ量と処理量は、ノード数の増加に対して増加率が小さい。従って、大規模な通信制御システム９０でも、通信量を削減するような通信利用状態の変更計画を効率よく決定することができる。
その理由は、分散した処理ノード装置１やマスタ装置３がノード間の閉路を探索する際に、探索処理部１１０が、異なる経路についても、起点ノードからの探索長が同一の経路の中で一つの経路だけ保存しながら探索を行うからである。本形態の通信制御システム９０は、第１の実施の形態のようにノード間で存在しうる経路数分の探索を行わない。
＜第３の実施形態＞
図２２は、第３の実施形態の負閉路探索部１１の構成を示す。本実施の形態の負閉路探索部１１は、起動部１１０１の代わりに、経路格納部１１０６の状態を更新する更新部１１１３を備える。外部からデータ送受信の開始や終了等の指示を受け付ける更新受付部１１４が、指示に応じて更新部１１１３を呼び出す。
さらに、本実施の形態の負閉路探索部１１はノード情報生成部１１３を備えず、更新部１１１３がノード情報格納部１１１に出ノードリスト６１等を作成する。経過格納部１１０５や経路格納部１１０６に格納される情報は、第２の実施形態と同じである。
また、本実施の形態の説明は、複数ノードに複製されているデータについても言及する。複数ノードに複製されているデータは、他の実施形態に於いても、存在して良い。
図２３Ａ乃至図２８Ｂは、更新部１１１３の動作フローチャートである。更新部１１１３は、更新受付部１１４からの指示内容に応じて、異なる動作をする。図２３Ａ乃至図２６は、主にリンク状態の更新を担う動作のフローチャートである。
図２３Ａ及び図２３Ｂは、データノードに関して、データ送受信と処理の開始に伴う変更を反映する動作のフローチャートである。図２４Ａ乃至図２４Ｃは、データノードに関して、データ送受信と処理の終了に伴う変更を反映する動作のフローチャートである。図２５Ａ乃至図２５Ｃは、処理ノードに関してデータ送受信や処理の開始に伴う変更を反映する動作のフローチャートである。図２６は、処理ノードに関して、データ送受信や処理の終了に伴う変更を反映する動作のフローチャートである。
図２７乃至図２９は、上述のフローチャートから参照される手順のフローチャートである。図２７は、更新部１１１３のリンク登録動作のフローチャートである。図２８Ａ及び図２８Ｂは、更新部１１１３のリンク削除通知動作のフローチャートである。図２９は、負閉路検出部１１０４の平均コスト算出動作のフローチャートである。
図２３Ａ及び図２３Ｂのデータノードに処理開始を反映する手順に於いて、更新部１１１３は、送受信データの複製を有するデータノードについて、Ｓ２３２乃至Ｓ２３５の処理を実行する。
まず、更新部１１１３は、当該ノードの出ノードリスト６１に、送受信データの複製を有するデータノードを、通信コストを０、通信変更上限を無限大として追加し、そのデータノードの入ノードリスト６１に当該データノードを追加する（Ｓ２３２）。
更新部１１１３は、さらに、そのデータノードに関して、データ送受信と処理の開始に伴う変更を反映させる（Ｓ２３２）。例えば、そのデータノード（複製データのデータノード）について図２３Ａ及び図２３Ｂに示される手順を実行することを、そのデータノードである処理サーバ装置１またはそのデータノードであるワーカ装置２に対応するマスタ装置３に依頼する。依頼を受けた装置は、当該データノードでの送受信ではないので（Ｓ２３１でＮ）、本ステップが繰り返し実行されることはない。
その後、更新部１１１３は、そのノードにリンク登録通知を行う（Ｓ２３４、Ｓ２３５）。更新部１１１３は、総コストが無限大（初期値）でない全ての探索長ｋの総コストに、そのノードへの通信コストを加算し、得られた総コストと探索長ｋ＋１の対の集合に関し、リンク登録通知を行う。
当該データノードのデータを対象とする実行中の処理（当該データノードのデータの複製となっている、他ノードのデータを対象とする処理も含む）の単位処理量の中で最小の単位処理量よりも、開始したデータ処理の単位処理量の方が小さい場合（Ｓ２３６でＹ）、更新部１１１３は、この単位処理量を最小単位処理量とする（Ｓ２３７）。
次に、更新部１１１３は、処理ノード候補リスト６３内の処理ノードについて、Ｓ２３８乃至Ｓ２３Ｄの処理を行う。
その処理ノードの残存処理可能量がゼロでない場合（Ｓ２３８でＮ）、あるいは、ゼロであっても、その処理ノードで実行中の処理のうち最大の単位処理量が、最小単位処理量以上である場合（Ｓ２３９でＮ）、更新部１１１３は、当該ノードとそのノード間の通信コストを通信コスト算出部１１２から得る（Ｓ２３Ａ）。
その後、更新部１１１３は、その処理ノードの識別子、その通信コスト、無限大の通信変更上限を、当該ノードの出ノードリスト６１に格納し、そのノードの入ノードリスト６２に当該ノードを格納する（Ｓ２３Ｂ）。ここで、『そのノードの入ノードリスト６２に当該ノードを格納する』とは、当該ノードの識別子をそのノードである処理サーバ装置１等に送信し、受信した装置が、受信した識別子を入ノードリスト６１に格納することを意味する。以降、類似表現についても同様である。
そして、更新部１１１３は、このノードに対してリンク登録通知を行う（Ｓ２３Ｃ、Ｓ２３Ｄ）。例えば、更新部１１１３は、総コストが無限大（初期値）でない全ての探索長ｋの総コストに、そのノードへの通信コストを加算し、得られた総コストと探索長ｋ＋１の対の集合に関し、リンク登録通知を行う。
なお、ここでの通信変更上限は、上述のように無限大とせず、このノード間の通信の利用可能帯域であっても良い。この場合、更新部１１１３は、このノード間の物理リンク帯域（ｂｐｓ）を通信コスト算出部１１２等から取得する。通信コスト算出部１１２は、この利用可能帯域を、例えば、接続されている通信網構成格納部１１２３等から取得する。このようにすることで、通信制御システム９０は、通信路の帯域より大きな通信を行う計画を回避することができる。
図２４Ａ乃至図２４Ｃのデータノードに処理終了を反映する手順に於いて、更新部１１１３は、送受信データの複製を有するデータノードについて、Ｓ２４２乃至Ｓ２４４の処理を実行する。
まず、更新部１１１３は、そのデータノードの入ノードリスト６２から当該ノードを削除し、当該ノードの出ノードリスト６１から、その送受信データの複製を有するデータノードを削除する（Ｓ２４２）。
そして、更新部１１１３は、そのノードに関して、データ送受信と処理の終了に伴う変更を反映する（Ｓ２４３）。例えば、そのデータノードについて図２４Ａ乃至図２４Ｃに示される手順を実行することを、そのデータノードである処理サーバ装置１またはそのデータノードであるワーカ装置２に対応するマスタ装置３に依頼する。依頼を受けた装置は、当該データノードでの送受信ではないので（Ｓ２４１でＮ）、本ステップが繰り返し実行されることはない。
その後、更新部１１１３は、そのノードにリンク削除通知を行う（Ｓ２４４）。
終了した当該データ処理以外に、当該データノードからの通信がない場合（Ｓ２４５でＮ）、更新部１１１３は、当該ノードの出ノードリスト６１内に登録されている処理ノードの入ノードリスト６２から当該ノードを削除し、当該データノードの出ノードリスト６１からその処理ノードを削除し、リンク削除通知を行う（Ｓ２４Ｆ、Ｓ２４Ｇ）。
当該データ処理以外に、当該データノードからの通信があり（Ｓ２４５でＹ）、当該データ処理が、当該データノードのデータを対象とする実行中の処理の単位処理量の中で最小ではある場合は（Ｓ２４６でＹ）、更新部１１１３は新たな処理ノードを決定する。
具体的には、更新部１１１３は、当該データノードのデータを対象とする実行中の処理の中で最小の単位処理量を最小単位処理量とし（Ｓ２４７）、処理ノード候補リスト６３内の処理ノードについてについて、Ｓ２４８乃至Ｓ２４Ｄの処理を行う。
残存処理可能量がゼロではない（Ｓ２４８でＮ）、あるいはゼロであるが、その処理ノードで実行中の処理のうち最大の単位処理量が最小単位処理量より小さくない場合に（Ｓ２４９でＮ）、更新部１１１３は、当該ノードとそのノードとの通信コストを得る（Ｓ２４Ａ）。さらに、更新部１１１３は、この通信コスト、その処理ノードの識別子、無限大の通信変更上限を、当該ノードの出ノードリスト６１に格納し、そのノードの入ノードリスト６１に当該ノードの識別子を追加し（Ｓ２４Ｂ）、リンク登録通知を行う（Ｓ２４Ｃ、Ｓ２４Ｄ）。このとき、更新部１１１３は、総コストが無限大（初期値）でない全ての探索長ｋの総コストに、そのノードへの通信コストを加算し、得られた総コストと探索長ｋ＋１の対の集合に関し、リンク登録通知を行う。
図２５Ａ等の処理ノードに処理開始を反映する手順において、更新部１１１３は、当該処理ノードと通信先のデータノードとの通信コストを算出し（Ｓ２５１）、そのノードの識別子、算出された通信コストの負値、ノード間の通信量おのおのを、当該処理ノードの出ノードリスト６１の識別子、通信コスト、通信変更上限として格納する（Ｓ２５２）。さらに、更新部１１１３は、通信先のノードの入ノードリスト６２に当該ノードを登録する（２５３）。
次に、更新部１１１３は、当該ノードが既にデータ送受信と処理を実行中であるか否かを判定する（Ｓ２５４）。これは、探索の起点を論理的な処理ノードとした時、探索長１の総コストが０であるか否かの判定となる。
実行中でない、即ち、総コストが０でない場合（Ｓ２５４でＮ）、更新部１１１３は、処理ノード候補リスト６３から、残存処理可能量が０ではない複数の処理ノードを取得する（Ｓ２５５）。更新部１１１３は、処理ノードをノード情報共有格納部１１３４等から取得しても良い。更新部１１１３は、当該ノードの入ノードリスト６２に、それらの処理ノードを登録し（Ｓ２５６）、それらの処理ノードの出ノードリスト６１に、当該ノードを、通信コストをゼロ、通信変更上限を無限大にして登録する（Ｓ２５７）。この登録は、当該ノードの識別子、通信コスト、通信変更上限を、処理ノードである処理サーバ装置１等に送信することで行われる。
続いて、更新部１１１３は、当該ノードの残存処理能力が０か否かを判定する。ゼロの場合（Ｓ２５８でＹ）、更新部１１１３は、出ノードリスト６２内の処理ノードのおのおのについて、その処理ノードの入ノードリスト６２から当該ノードを削除し、また当該ノードの出ノードリスト６１からその処理ノードを削除し、その処理ノードにリンク削除通知を行う（Ｓ２５Ｃ乃至Ｓ２５Ｅ）。
この後、或いは、当該ノードの残存処理能力が０で無い場合（Ｓ２５８でＮ）、更新部１１１３は、経路格納部１１０６の探索長１の総コストを０とし（Ｓ２５９）、出ノードリスト６１内の各ノードにリンク登録通知を行う（Ｓ２５Ａ、Ｓ２５Ｂ）。即ち、更新部１１１３は、当該ノードとそのノードとの通信コストを取得し（Ｓ２５Ａ）、総コストが無限大（初期値）でない全ての探索長ｋの総コストに、取得された通信コストを加算し、得られた総コストと探索長ｋ＋１の対の集合に関し、リンク登録通知を行う。
図２６の処理ノードに処理終了を反映する手順において、更新部１１１３は当該処理ノードの出ノードリスト６１から、通信先のデータノードを削除し、通信先のデータノードの入ノードリスト６２から当該処理ノードを削除し、当該処理ノードが、まだ他のデータノードとデータの送受信と処理を実行しているかを判定する（Ｓ２６１乃至Ｓ２６３）。
実行していない場合（Ｓ２６３でＮ）、更新部１１１３は、当該ノードの入ノードリスト６２内のノードのおのおのに対して、それらの処理ノードの出ノードリスト６１から、当該ノードを削除し、当該ノードの入ノードリスト６２からそれらの処理ノードを削除し、そのノードにリンク削除通知を行う（Ｓ２６４乃至Ｓ２６６）。続いて、更新部１１１３は、探索長１の総コストを無限大とする（Ｓ２６７）。当該ノードは、何の処理も実行していない状態となるためである。
最後に更新部１１１３は、処理ノード候補リスト６３から得られる処理ノードについて、その処理ノードの入ノードリスト６２に当該ノードを登録し、当該ノードの出ノードリスト６１にその処理ノードを登録し、そのノードにリンク登録通知を行う（Ｓ２６８乃至Ｓ２６Ｃ）。
図２７のリンク登録手順において、更新部１１１３は、リンク登録通知を行ったノード識別子と、探索長ｋとそれに対応する総コストの対を複数受け付け、通知された探索長ｋのそれぞれに対して、経路格納部１１０６からその探索長ｋの総コストを取得する（Ｓ２７１）。更新部１１１３は、この取得した値と通知された値とを比較し、通知された値が格納されていた値よりも小さい場合には（Ｓ２７２でＹ）、その探索長ｋにおける総コストを通知された値で更新し、さらに、探索長ｋの経路ノードの識別子を、この通知を行ったノード識別子で更新する（Ｓ２７３）。
総コストが更新された探索長が存在する場合（Ｓ２７４でＹ）、更新部１１１３は、出ノードリスト６１内のノードについて、更新された探索長ｋの総コストそれぞれに対して、当該ノードとそのノードへの通信コストを加算し、得られた値を探索長ｋ＋１の総コストとして格納して、そのノードにリンク登録通知を行う（Ｓ２７５乃至Ｓ２７７）。最後に、更新部１１１３は、平均コストの算出を行う（Ｓ２７８）。
図２８Ａ及び図２８Ｂのリンク削除通知手順において、更新部１１１３は、この通知を行ったノード識別子を受け付け、経路格納部のノード識別子が通知されたノード識別子と同一であるような探索長ｋについて、Ｓ２８１乃至Ｓ２８８の処理を行う。
先ず、更新部１１１３は、探索長ｋの総コストを過去値として保持しつつ、総コストの値には無限大の値を格納する（Ｓ２８１、Ｓ２８２）。次に、更新部１１１３は、入ノードリスト６２内の各ノードについて、そのノードに探索長ｋ−１における総コストを要求し、得られた値と探索長ｋの総コストと比較し、得られた値が小さい場合には、これを探索長ｋにおける総コストに登録し、そのノード識別子をその入ノードリスト６２内のノードとする（Ｓ２８３乃至Ｓ２８６）。
全ての入ノードリスト６２内のノードの処理を終えると、更新部１１１３は、探索長ｋの総コストを保持した過去値と比較する。更新されている場合（Ｓ２８７でＹ）、更新部１１１３は、更新リストに探索長ｋを追加する（Ｓ２８８）。
全ての探索長ｋについて処理を終えると、更新部１１１３は、出ノードリスト６１内のノードについて、更新リスト内の各々の探索長ｋの総コストに、そのノードとの通信コストを加算して、探索長ｋ＋１とその総コストの集合とし、そのノードへリンク登録通知を行う（Ｓ２８９、Ｓ２８Ａ）。最後に、更新部１１１３は、平均コストの算出を行う（Ｓ２８Ｂ）。
図２９の平均コストの算出手順に於いて、負閉路検出部１１０４は、探索長１からノード数Ｎ−１までの探索長ｋに関して、式２（ｄＮ−ｄｋ）／Ｎ−ｋの値を算出し（Ｓ２９１）、算出された中で最大の値を平均コストとする（Ｓ２９２）。この値が負の場合（Ｓ２９３でＹ）、経路ノードを辿って閉路を取得する（Ｓ２９４）。例えば、負閉路検出部１１０４は、探索長ｋをノード数Ｎから順次１ずつ減らしながら、探索長ｋの経路ノードにアクセスして探索長ｋ−１の経路ノードを取得し、経路ノードの閉路（経路ノードとして同一ノードの２度出現または当該ノードの出現）を検出する。探索長が１迄減らされても、閉路が検出されない場合もある。閉路が存在する場合（Ｓ２９５でＹ）は、負閉路検出部１１０４は、処理移動部１７等を介して、閉路に於ける各ノードに対して処理の移動を実行する（Ｓ２９６）。移動の方法は、実施の形態１と同じである。また、負閉路検出部１１０４は、表示実行部１８を介して移動計画を表示だけしても良い。
平均コストが負でない（Ｓ２９３でＮ）、または閉路が検出できない場合（Ｓ２９５でＮ）、負閉路検出部１１０４は動作を終了する。
ここで、図５６の（Ｂ）が示すように、あるデータ処理の入力あるいは出力するデータが複数の箇所に存在する時には、負閉路検出部１１０４は、上述の各処理で制約関係にあるデータの格納先となる処理サーバ装置１をリストにして管理する。その際、負閉路検出部１１０４は、処理される単位データ量当たりの各々の箇所のデータ量の比を管理する。
ある負閉路が検知され、その負閉路に属するノードが、その制約関係にある処理ノードリストを有している場合、負閉路検出部１１０４は、そのノードに関する通信の追加・削除を行うときには、そのリスト内の他のノードに対しても追加・削除を行う必要がある。従って、負閉路検出部１１０４は、これについて、図３０の手順により、その総コストを算出する。
負閉路検出部１１０４は、この総コストの算出において、処理ノード間の通信コストに加えて、データ量の比も反映させる（Ｓ３０２、Ｓ３０３）。このようにして算出された総コストと、負閉路の総コストを加えた結果が負である場合に、負閉路検出部１１０４は、この通信変更計画を生成する（図２９のＳ２９６）。
本実施の形態の通信制御システム９０は、第２の実施形態よりも少ないメッセージ量と処理量で、処理データの通信負荷を低減させることが可能である。その理由は、更新部１１１３が、処理データの通信とその処理の開始終了を契機に、その開始終了に起因する変分だけを経路格納部１１０６に反映させるからである。即ち、本実施の形態の探索処理部１１０は、第２の実施形態のように、起動されるたびに、経路を新たに生成し直すものではない。
＜実施形態３の変形＞
通信制御システム９０は、処理ノードとデータノード間の通信の開始終了契機ではなく、或るノードがノード数Ｎの変化を検知した場合に、経路格納部１１０６の経路を更新しても良い。例えば、ノード数Ｎの変化を検知したノードの更新部１１１３が、他の全ノードにノード数Ｎを通知し、各ノードの更新部１１１３がこれを契機に経路を更新しても良い。
図３１は、ノード数Ｎの通知対応動作のフローチャートである。通知された値Ｎがノード数６４に格納されている値Ｎ’よりも大きい場合（Ｓ３１１でＹ）、更新部１１１３は、出ノードリスト６１内のノードのおのおのに、探索長Ｎ’からＮ迄について、リンク登録通知を行う（Ｓ３１３）。
この為、更新部１１１３は、ノード数Ｎ’からＮまでの各探索長ｋについて、探索長ｋにおける総コストの値に、そのノードへの通信コストを加算して、探索長ｋ＋１の総コストを算出する（Ｓ３１２）。
通知された値Ｎが格納されている値Ｎ’よりも大きくない場合（Ｓ３１１でＮ）、更新部１１１３は、探索長Ｎ’からＮ迄の経路情報を削除する（Ｓ３１５）。
最後に、更新部１１１３は、ノード数６４の値を通知された値で更新する（Ｓ３１４）。
＜第４の実施の形態＞
本発明の第４の実施の形態では、論理的なデータをデータノードとしてモデル化する。即ち、本実施形態の通信制御システム９０は、複数のデータ格納部１４に格納されているデータを、論理的に一つのデータノードとして扱う。この為、本実施形態の通信制御システム９０は、一台のマスタ装置３の負閉路探索部１１が、複数のワーカ装置２を代表してメッセージ交換を行う図２に示した形態の方が実現しやすい。以下の説明は、この形態を前提とする。
また以下の説明は、複製データ、即ち、同一のデータが複数のワーカ装置２に冗長的に配置されているデータに言及する。さらに、また以下の説明は、Ｅｒａｓｕｒｅ符号化され、複数のワーカ装置２に配置されているデータについても言及する。このように符号化されたデータは、単一のワーカ装置２に格納されたデータからは復元できないが、配置数ｍ以下のある一定数ｎ以上のワーカ装置２に格納されたデータから復元できる。
このような複製データ、および、符号化されたデータは、他の実施の形態に於いても、存在していて良い。
第１乃至第３の実施形態に於ける通信コスト算出部１１２は、ノードとしてのワーカ装置２の間の通信コストを算出していたが、本実施の形態の通信コスト算出部１１２は、それに加え、或るワーカ装置２と論理的なデータ間の通信コストを算出する。このワーカ装置２（例えば、ワーカ装置２ａ）と論理的なデータ間の通信コストは、ワーカ装置２ａと論理的なデータを格納する複数のワーカ装置２（例えば、ワーカ装置２ｂとワーカ装置２ｄ）との間の通信コストを用いて計算される。
本実施の形態のノード情報生成部１１３や更新部１１１３等は、符号化されたデータが配置されているｍ台のワーカ装置２をまとめて１つのデータノードとして扱えばよい。
以下の説明に於いて、通信コストｃｉｊは、ワーカ装置２ｊから、データｉへの通信コストを意味する。
複製されているデータｉがワーカ装置２の集合Ｒｉに格納されている場合は、本実施の形態の通信コスト算出部１１２は、通信コストｃｉｊを、データｉを格納したワーカ装置２の集合Ｒｉに含まれるワーカ装置２ｋとワーカ装置２ｊとの通信コストｃｋｊの中で、最も小さい値とする。この場合、ｃｉｊは以下の式で表現できる。
ｃｉｊ  ＝  ｍｉｎ    ｃｋｊ        ．．．．（３）
ｋ∈Ｒｉ
なお、データｉが単一のワーカ装置２ｋに格納されている場合、通信コスト算出部１１２は、通信コストｃｉｊ＝ｃｋｊとして算出する。
データｉがＥｒａｓｕｒｅ符号化されて格納されている場合、通信コスト算出部１１２は、ワーカ装置２の集合Ｅｉ（ｊ）に含まれるワーカ装置２ｋとワーカ装置２ｊとの通信コストｃｋｊの総和を算出して、通信コストｃｉｊとする。ここで、集合Ｅｉ（ｊ）は、データｉの断片を格納したワーカ装置２の集合Ｅｉに含まれるワーカ装置２ｋとワーカ装置２ｊとの通信コストｃｋｊの中で、通信コストの小さい順に、復号に必要な一定数ｎまでを集めたワーカ装置２の集合を意味する。この場合、ｃｉｊは以下の式で表現できる。
ｃｉｊ  ＝      Σ        ｃｋｊ      ．．．．．（４）
ｋ∈Ｅｉ（ｊ）
なお、符号化された断片がさらに複製配置されている等の場合、通信コスト算出部１１２は、式（３）や式（４）の右辺のｃｋｊを、さらに式（３）や式（４）の左辺として再帰的に用いた計算を行う。
次に、処理ノード、即ち、処理ノードとしてのワーカ装置２が、分散した複数のデータの組を処理する場合の通信コストの算出について述べる。
このようにデータの組を扱う処理は、例えば、１種類のデータを入力して１種類のデータを出力する処理や、２種類のデータを入力する処理である。このような処理は、例えば、ワーカ装置２ａで実行される処理プログラムが、ワーカ装置２ｂに格納された“／ｆｏｏ／ｉｎ．ｔｘｔ”というファイルの各行を処理し、その結果として得られるデータ要素をワーカ装置２ｃの“／ｆｏｏ／ｏｕｔ．ｔｘｔ”というファイルに格納するような処理である。
この場合、データｉは、単一のデータ集合の部分集合ではなく、あるデータ集合族｛Ｄｍ｝（ｍ＝１，２，．．．Ｍ）に含まれる各集合の被覆となる部分集合の組（ｄ１，ｄ２，．．．ｄＭ）（ただし、ｄ１⊂Ｄ１，ｄ２⊂Ｄ２，．．．ｄｍ⊂ＤＭ）を元とするような集合である。上記例においては、例えば、“／ｆｏｏ／ｉｎ．ｔｘｔ”がｄ１、“／ｆｏｏ／ｏｕｔ．ｔｘｔ”がｄ２である。
各部分集合ｄｍ（ｍ＝１，．．．Ｍ）は、それぞれ単一のワーカ装置２に格納される場合や、複数のワーカ装置２に複製や符号化されて配置される場合がある。この部分集合ｄｍのデータとワーカ装置２ｊとの通信コストをｃｍｊとしたとき、通信コスト算出部１１２は、データ２ｉとワーカ装置２ｊの通信コストｃｉｊを、以下の式（５）に基づいて算出する。
ｃｉｊ＝      Σ      （δｍ×ｃｍｊ）      ．．．．．（５）
ｍ＝１，２，．Ｍ
ここでδｍは、各部分集合ｄｍのデータ量を、全ての部分集合についての和（ｍ＝１，２，．．．Ｍ）で除した値であり、
Σ      （δｍ）＝１である。
ｍ＝１，２，．Ｍ
次に、データｉが、分散した複数のデータの直積を取り、その直積集合の要素ごとに処理する場合の通信コスト算出について述べる。
この場合、データｉは、あるデータ集合族｛Ｄｍ｝（ｍ＝１，２，．．．Ｍ）に含まれる各集合Ｄｍの被覆となる部分集合の直積ΠＤｍの元（ｄｍ１，ｄｍ２，．．．ｄｍｍ，．．．ｄｍＭ）（ただし、ｄｍ１⊂Ｄ１（ｍ１＝１，２，．．．Ｍ１），ｄｍ２⊂Ｄ２（ｍ１＝１，２，．．．Ｍ２），，ｄｍｍ⊂Ｄｍ，ｄｍ⊂ＤＭ）である。
例えば、ワーカ装置２で実行される処理は、データ集合Ｄ１に含まれる部分集合ｄ１１とｄ１２と、Ｄ２に含まれる部分集合ｄ２１とｄ２２を入力されると、（ｄ１１，ｄ２１）、（ｄ１２，ｄ２１）（ｄ１１，ｄ２２）、（ｄ１２，ｄ２２）を処理する。この場合も通信コスト算出部１１２は、通信コストｃｉｊを式（５）に基づいて算出する。
本実施の形態の通信制御システム９０は、データが複数のワーカ装置２等の間で複製される場合でも、通信負荷の低減を図ることが可能となる。また、通信制御システム９０は、ワーカ装置２等に格納されたデータと、別のワーカ装置２等に格納されたデータとの組み合わせを対象とする処理についても、通信負荷の低減を図ることが可能となる。
その理由は、負閉路探索部１１が、論理的なデータをデータノードとして扱うからである。
＜第５の実施の形態＞
図６０は、本実施形態の通信装置８の構成を示す。本実施形態の通信装置８は、図１の処理サーバ装置１または図２のマスタ装置３に対応する。本実施形態の通信装置８は、他の通信装置８と通信路で接続される。通信装置８は、ノード情報格納部１１１と探索処理部１１０を備える。
ノード情報格納部１１１は、自装置が与えられた処理を実行する処理装置である場合は、処理のデータに関連付けられたデータ装置の識別子及び当該データに対する通信コストの組を格納する。ノード情報格納部１１１は、自装置がデータ装置である場合は、関連付けられたデータを入出力する処理装置の識別子と当該処理装置と当該データ間の通信コストの組を含む出ノード情報６１を格納する。
探索処理部１１０は、自装置または他装置を発信元とし、転送経路の通信コストである総コストを包含するメッセージを受信して、総コストが負となる転送経路の閉路を検出して出力する。
または、探索処理部１１０は、出ノード情報６１に登録されているデータ装置に、受信した総コストから当該データ装置対応の通信コストを減じた新たな総コスト、受信した転送経路に自装置を加えた新たな転送経路を包含するメッセージを送信、かつ、出ノード情報６１に登録されている処理装置に、受信した総コストに当該処理装置対応の通信コストを加えた新たな総コスト、新たな転送経路を包含するメッセージを送信する。
なお、通信装置８は、下記のように構成されても良い。
ノード情報格納部１１１は、自装置に対応するワーカ装置２が与えられた処理を実行する処理装置である場合は、処理のデータに関連付けられたデータ装置の識別子及び当該データに対する通信コストの組を格納する。ノード情報格納部１１１は、自装置に対応するワーカ装置２がデータ装置である場合は、関連付けられたデータを入出力する処理装置の識別子と当該処理装置と当該データ間の通信コストの組を含む出ノード情報６１を格納する。
探索処理部１１０は、自装置または他装置を発信元とし、転送経路の通信コストである総コストを包含するメッセージを受信して、総コストが負となる転送経路の閉路を検出して出力する。
または、探索処理部１１０は、出ノード情報６１に登録されているデータ装置に対応する他装置に、受信した総コストから当該データ装置対応の通信コストを減じた新たな総コスト、受信した転送経路に自装置に対応するワーカ装置２を加えた新たな転送経路を包含するメッセージを送信、かつ、出ノード情報６１に登録されている処理装置に対応する他装置に、受信した総コストに当該処理装置対応の通信コストを加えた新たな総コスト、新たな転送経路を包含するメッセージを送信する。
本実施の形態の通信制御システム９０は、複数のノード（処理サーバ装置１またはワーカ装置２）がデータを通信しながら進めるデータ処理を、複数実行している通信制御システム９０において、当該複数のデータ処理全体としての通信負荷を低減することを可能とする。
その理由は、探索処理部１１０等が、総コストが負となるノードの通信パスの閉路を検出して、その負閉路（ノードの識別子の経路順のシーケンス）を出力するからである。
＜＜具体的な動作の例＞＞
次に、具体的な例を用いて本発明の通信制御システム９０の動作を説明する。
＜第１の実施の形態における動作例＞
図３２は、ユーザから実行指示される処理の例を示す。第１の処理は、定常的にデータが発生するストリーム１４０ａをプログラム１３０ａが処理するものである。プログラム１３０ａは、ユーザが利用するアプリケーションプログラムである。ストリーム１４０ａは、およそ５０Ｍｂｐｓのデータを発生しており、プログラム１３０ａがストリーム１４０ａの単位データ量あたりに必要とする計算能力は、０．０５ＧＨｚ／Ｍｂｐｓである。
この例に於いて、計算能力は、ＣＰＵのクロック数に比例するとしている。計算能力は、プロセッサのコア数や、計測・ベンチマーク等によって算出された処理能力値で表現しても良い。
第２の処理は、２０Ｍｂｐｓのデータストリームを、０．１ＧＨｚ／Ｍｂｐｓの処理能力が必要な処理プログラム１３０ｂで処理するものである。第３の処理は、３０Ｍｂｐｓのデータストリームを、０．１ＧＨｚ／Ｍｂｐｓの処理能力が必要な処理プログラム１３０ｃで処理するものである。
図３３の（Ａ）は、本例の通信制御システム９０の構成を示す。通信制御システム９０は、９台の処理サーバ装置１から構成され、３台ずつスイッチに接続され、さらにその３台のスイッチが上位スイッチに接続されている。また、処理サーバ装置１ａ乃至１ｆは、３ＧＨｚの計算能力を有し、処理サーバ装置１ｇ乃至１ｉは２．５ＧＨｚの計算能力を有している。
なお、本説明は、図１の形態を前提としている。図２の形態の通信制御システム９０においては、処理サーバ装置１はワーカ装置２に置換される。マスタ装置３は、本図に於いては図示されていない。
このシステムに於いて、ストリーム１４０ａは処理サーバ装置１ｂに、ストリーム１４０ｂは処理サーバ装置１ｄに、ストリーム１４０ｃは処理サーバ装置１ｇに格納されている。処理プログラム１３０ａは処理サーバ装置１ｈに、１３０ｂは処理サーバ装置１ｂに、１３０ｃは処理サーバ装置１ｅに、それぞれ配置されて実行されている。このデータや処理は、その前に実行された処理、空き処理サーバ装置１の状態等に応じて配置されている。
このデータと処理の配置に対して、探索処理部１１０のノード作成部１１３２は、図３３の（Ｂ）に記載のグラフを、複数の処理サーバ装置１のノード情報格納部１１１に格納する。図３３の（Ｂ）のノード１ｂＤは、処理サーバ装置１ｂに格納されたデータを表し、ノード１ｂＰは、処理サーバ装置１ｂで実行中の処理を表す。
各ノード間の辺（エッジ）には通信コストが付されている。ノード１ｂＤからノード１ｂＰへの辺には、コスト０が付されているが、これは同一装置内の通信であるので、通信コストがゼロであることを表している。
ノード１ｂＤからノード１ｂＰへの辺の情報は、ノード１ｂＤに関するノード情報格納部１１１の出ノードリスト６１と、ノード１ｂＰに関するノード情報格納部１１１の入ノードリスト６２に格納されている。ノード１ｂＰからノード１ｄＤへは、通信コスト−５で辺が作られ、さらに通信変更上限として２０が括弧内の数字で与えられている。負値の通信コスト−５は、２つの処理サーバ装置１間で発生する伝送遅延等の通信コストの絶対値が５であり、さらに、ノード１ｄＤと対応する処理サーバ装置１ｄからノード１ｂに対してデータが送信されていることを示す。
また、利用されている通信量が２０であるために、通信変更上限が２０と設定されている。図中、括弧のない辺は、通信変更上限が無限大であることを意味する。また、処理ノードには、閉じ括弧で残存処理可能量が付されている。
ノード１ｊは論理的なノードであり、対応する処理サーバ装置１は存在しない。ノード１ｂＰ、１ｆＰ等処理を表すノードからノード１ｊへの辺は、その処理サーバ装置１に残存処理可能量、すなわち他のデータ処理をしうる能力がある場合に生成され、そのコストは０と設定される。ノード１ｊから処理を表すノードへの辺は、何らかの処理が実行中である場合に生成され、そのコストも０に設定される。
図３４は、論理的な頂点１ｊを介してリンクが張られるノード間を接続するように表現したグラフを示す。本図においては、全ての処理能力が余っているノードから、全ての何らかの処理を行っているノードに対して辺がコスト０で設定されている。これらの辺は、各々のノード情報格納部１１１に格納されている。
なお、図８Ａは、論理的なノード１ｊを含まない場合のノード情報生成手順を示す。ノード１ｊを含める場合、ノード作成部１１３２は、入力パラメータ指定等に基づいて、このノードに対応する処理ノード装置１を一意に決定する。そして、ノード作成部１１３２は、処理ノードに残存処理可能量がある場合に、処理ノードからそのノード１ｊにコスト０でリンクを持ち、処理ノードが何らかの処理が実行中である場合に、そのノード１ｊからコスト０で処理ノードへリンクを設定する。
図３５は、図３４の有向グラフを、リンク元のノードを上部、リンク先のノードを下部に表した図である。各ノードのノード作成部１１３２は、各辺の情報をリンク元のノードのノード情報格納部１１１内の出ノードリスト６１、リンク先のノードの入ノードリスト６２に格納する。
転送部１１０３と負閉路検出部１１０４等は、このような情報を格納するノード情報格納部１１１を参照して、以下のように動作する。
例えば、ノード１ｂＰが、局所的な通信負荷がある閾値を越えたことを検出した場合、そのノードは、出ノードリスト６１に格納されたノード１ｄＤ、１ｅＰ、１ｈＰに対して、それぞれ総コストを−５、０、０としてメッセージ（探索要求４０）を送信する。探索長は１である。
受信したノード１ｄＤは、メッセージ内の総コストに出ノードリスト６１内の各ノードへの通信コストを加算し、探索長に１追加し、出ノードリスト６１内の各ノードに対してメッセージを転送する。
図３６は、メッセージが各ノードを順次転送されていく経過を示す。ここで、転送閾値が−３と設定されていると、各ノードは、総コストが−３以下の場合のみメッセージを転送する。この転送閾値により、通信制御システム９０は、メッセージ量の削減を行うことができる。
各ノードは、このメッセージ転送の際に、ノードリストにノード識別子を追記していくため、メッセージがノード１ｂＰ、１ｈＰ、１ｂＤ、１ｂＰと転送されると、ノード１ｂＰは、ノードリストからノードの閉路を検知することができる。ノード１ｂＰは、検知した閉路、その総コスト等の情報から探索結果４１を作成し、メッセージ内に記憶された起動ノードに送信する。起動ノードであるノード１ｂＰは、受信した探索結果４１を蓄積する。
図３７は、起動ノードであるノード１ｂＰに集められた探索結果４１を示す。探索結果４１の通信変更上限ａは、閉路をなす経路に付されたの通信変更上限の最小値である。また、探索結果４１の処理追加可能量ｂは、その閉路内の処理ノードの処理追加可能量中の最小値である。
起動ノードであるノード１ｂＰは、これらの探索結果４１から、通信変更上限ａと処理追加可能量ｂとの小さい方の値Ｍｉｎ（ａ，ｂ）と総コストと積が、最大のもの（図３７の上から４行目）を選択する。なお、積が同値である探索結果４１が複数存在するときは、何れを選択しても良い。
ノード１ｂＰは、選択した探索結果４１から、負閉路としてノード１ｂＰ、１ｄＤ、１ｆＰ、１ｈＰ、１ｂＤ、１ｂＰからなる閉路を得る。図３８は、起動ノードであるノード１ｂＰが得た負閉路を示す。
図３９の（Ａ）は、この閉路に基づく通信量の変更、処理の移動を実行して得られる、データと処理の配置を示す。即ち、データノード１ｄＤ（処理サーバ装置１ｄ）は、データ量のうち２０Ｍｂｐｓ分の送信先を、処理ノード１ｂＰ（処理サーバ装置１ｂ）から処理ノード１ｈＰ（処理サーバ装置１ｈ）に切り替える。また、データノード１ｂＤは、データ量のうち２０Ｍｂｐｓ分の送信先を、処理ノード１ｈＰから処理ノード１ｂＰに切り替える。
これらの変更は、いずれも通信負荷が低減するような変更である。処理すべきデータは、全て、変更後も処理される。さらに、新たに利用される処理サーバ装置１は、その処理能力を越えることが無いように、新たなデータ処理が割り当てられる。なお、通信の変更にともなって、処理プログラムが移動されている。処理プログラム１３０ｂが、処理サーバ装置１ｂから削除され、処理サーバ装置１ｆに配備されている。処理プログラム１３０ａが、処理サーバ装置１ｂにも配備される。
処理の配置変更が実行されると、その変更は、通信先格納部１２に反映される。図３９の（Ｂ）は、これを参照して生成され、ノード情報格納部１１１に格納されるグラフを示す。これに対して、再度、負閉路の探索処理が行われると、図４０が示す負閉路が検出される。
図４１の（Ａ）は、この２番目の閉路に基づく通信量の変更、処理の移動を実行して得られる、データと処理の配置を示す。通信負荷はさらに低減する。
図４１の（Ｂ）は、これを参照して生成され、ノード情報格納部１１１に格納されるグラフを示す。これに対して、さらにもう一度、負閉路の探索処理が行われると、図４２が示す負閉路が検出される。
図４３は、この３番目の閉路に基づく通信量の変更、処理の移動を実行して得られる、データと処理の配置を示す。通信負荷はさらに低減する。
なお、負閉路検出部１１０４は、図３８、図４０、図４２の負閉路を検出するたびに通信量の変更、処理の移動を行わず、ノード情報格納部１１１だけを更新し、負閉路が検出されなくなってから、一括で変更計画を実行して、通信の変更・処理の移動をしても良い。この場合、通信制御システム９０の処理配置は、図３３の（Ａ）の状態から図４３の状態に一度に変更される。また、負閉路検出部１１０４は、表示実行部１８に図２０が示すように変更計画を表示し、ユーザからの指示に応じて処理の配置を変更しても良い。さらに、負閉路検出部１１０４は、表示実行部１８に図４８が示すような負閉路を表示し、ユーザからの指示に応じて処理の配置を変更しても良い。
＜第２の実施の形態における動作例＞
本説明も、上述と同様に、図３２が示す処理が図３３の（Ａ）の通信制御システム９０で実行されており、図３４のグラフが、各処理サーバ装置１等のノード情報格納部１１１に分散されて格納されていることを前提とする。
本実施の形態では、最小平均コストの探索により負閉路の検出を行う転送部１１０３が、他の処理サーバ装置１またはマスタ装置３とメッセージ交換を行い、探索の進展に伴い、経路格納部１１０６に格納された総コストの情報を更新する。
図４４Ａ乃至図４４Ｅは、経路格納部１１０６に格納された総コストの情報の変化を示す。本図に於いて、ｄｎ（ｎは０以上の整数）はメッセージの探索長を示す。ｐｕｓｈは探索要求４０（通知）、ｐｕｌｌは探索要求４０（要求）、ｐｕｌｌ  ｒｅｔｕｒｎは探索要求４０（応答）の通信を示す。また、各探索長の総コストにおいて、−は、初期値を表す値、ｉｎｆ．は無限大を表す値である。
図４５は、最終的に起動ノードの経過格納部１１０５に格納される総コストを示す。本図に於いて、ｄｎ（ｎは０以上の整数）は探索長を示す。
図４６は、最終的に起動ノードの経過格納部１１０５に格納される経路ノードのノード識別子を示す。図４７は、最終的に起動ノードの経過格納部１１０５に格納される経路ノードの通信変更上限を示す。両図に於いて、ｖｎ（ｎは０以上の整数）は探索長を示す。
なお、図示されてはいないが、経路ノードのノード種別、単位処理負荷と残存処理可能量も、起動ノードの経過格納部１１０５に同様に格納される。
以降、探索の順をおって、メッセージ交換、状態変更の例を具体的に説明する。
ノード１ｂＰは、自ノードを起動ノードとし、探索長０におけるノードからの総コストを０とする。同ノードは、出ノードリスト６１に格納されたノード１ｄＤ、１ｅＰ、１ｈＰに対して、探索長０における総コスト０と各々へのコストの和をとって、探索長１における総コスト−５、０、０を通知する。
これを受信したノード１ｄＤは、入ノードリスト６２におけるノード１ｂＰからメッセージを受け取ったので、ノード１ｂＰの入ノード状態を済とする。同ノードは、他に入ノードリスト６２にノードはないので、探索長１における総コストをこの受け取った値−５で確定させる。
同ノードは、経路ノードにこの確定された総コストに関与したノード１ｂＰの識別子を記憶し、通信変更上限としてこのメッセージに付された値２０を記憶する。値が確定したので、同ノードは、出ノードリスト６２における各ノードに、この探索長１における総コスト−５に各ノードへのコストを足し、ノード１ｂＰに対して、探索長２で総コスト０、ノード１ｅＰに対して−３、ノード１ｆＰに対して−３と通知する。
このうちノード１ｅＰは、受け取ったメッセージの総コスト−３を、その探索長における総コストの値として記憶し、入ノードリスト６２のノード１ｄＤの入ノード状態を済とする。しかし、他のノードからの入ノード状態は未であるため、ノード１ｅＰに於いて、総コストの値は確定していない。従って、同ノードは、他の入ノードリスト６２のノードに対して、探索要求４０（要求）を発行する。すなわち、ノード１ｅＰは、ノード１ｂＤ、１ｂＰ、１ｆＰに対して、探索長２における総コストの探索要求４０（要求）を出す。
これを受信した各ノードは、受信した「探索長−１」にあたる探索長１における総コストが確定しているかを確認する。ノード１ｂＤにおいては、当該探索長に関する要求を初めて受信したため、経路格納部１１０６の総コストは初期化された状態のままである。起動ノードが、同ノードの入ノードリスト６２に存在しないことから、同ノードは探索長１の総コストをＩｎｆ．に設定する。同ノードは、このＩｎｆ．の値と、ノード１ｂＤからノード１ｅＰへの通信コストの和をとり、総コストをＩｎｆ．として探索長２の探索要求４０（応答）をノード１ｅＰに返信する。
ノード１ｅＰは、全ての入ノードリスト６２のノードから、探索要求４０（応答）を受信し、全ての入ノード状態を済とし、通知又は応答された総コストの最小値−３で、探索長２の総コストを確定する。
値が確定するとノード１ｅＰは、出ノードリスト６１に存在するノード１ｇＤに探索長３における総コスト−８を通知する。
これを受信したノード１ｇＤは、入ノードリスト６２の入ノード状態が全て済となるため、ノード１ｂＰとノード１ｆＰに探索長４における総コスト−３を通知する。
このうち、ノード１ｆＰでは探索長４の値が確定しない。従って、同ノードは、入ノード状態が未であるノード１ｂＤと１ｄＤに探索要求４０（要求）を送信する。ノード１ｂＤと１ｄＤも、探索長３における値が確定していないため、探索長３における総コストを、探索長３の入ノード状態が未であるノードに要求する。
このようにして、通信制御システム９０の各処理サーバ装置１またはマスタ装置３の転送部１１０３は、各ノードの各探索長の総コストを確定させ、最終的に、図４５の各列が示す総コスト、図４６の各列が示す経路ノードの識別子、図４７の各列が示す経路ノードの通信変更上限、図示されない経路ノードの単位処理量、残存処理可能量を得る。
各ノードの転送部１１０３が平均コストの最大値Ｍを算出すると、図４５の最下行が示す値となる。各ノードは、この値Ｍと、図４６の経路ノードの識別子、図４５の通信変更上限、図示されない単位処理負荷および残存処理可能量を含む探索結果４１を起動ノードであるノード１ｂＰに送信する。
ノード１ｂＰの負閉路検出部１１０４は、この平均コストの中で最小の値を選択する。ここで、負閉路検出部１１０４は、平均コストの最大値Ｍが−１．７であるノード１ｄＤまたは１ｈＰが送信した総コスト情報を取得する。負閉路検出部１１０４は、何れを取得しても良い。
負閉路検出部１１０４は、例えば、ノード１ｄＤから受信した経路ノード情報から、ノード数７に相当する探索長の経路ノードとして１ｂＰを取得し、これをノードリストに追加する。
同部は、次に、そのノード１ｂＰから受信した経路ノード情報から、探索長６の経路ノードとして１ｂＤを取得し、これがノードリストに存在するかを確認し、存在しないので、これをノードリストに追加する。同部は、さらに、そのノード１ｂＤから受信した経路ノード情報から、探索長５の経路ノードとして１ｈＰを取得してノードリストに追加する。続いて同部は、ノード１ｈＰから得た経路ノード情報から、ノード１ｂＰを取得する。ノード１ｂＰは、既にノードリストに存在するため、この処理を終了し、閉路｛１ｂＰ，１ｂＤ，１ｈＰ，１ｂＰ｝を得る。図４８は、ここで得られた閉路を示す。
次に、負閉路検出部１１０４は、この図４８の閉路に沿って除去できるフロー量の最大値（変更流量）を得る。
まず、負閉路検出部１１０４は、経過格納部１１０５に格納されている通信変更上限（図４７）を参照して、探索長６における１ｂＰの値Ｉｎｆ．、探索長５における５０、探索長４にＩｎｆ．の中で最小の値である５０を得る。
次に、負閉路検出部１１０４は、図４８の閉路の処理追加可能量を算出する。負閉路検出部１１０４は、閉路内のデータ種別のノード（データノード）から処理種別のノード（処理ノード）への通信追加変更として、ノード１ｂＤからノード１ｂＰへの通信量追加を行い、ノード１ｂＰからは通信量の削減を行わない。ノード１ｂＰの残存処理量は１である。ノード１ｂＤにおけるストリーム１４０ａを処理するプログラム１３０ａの単位処理負荷は０．０５である。負閉路検出部１１０４は、１／０．０５を計算して、ノード１ｂＰでの処理追加可能量を２０と算出する。この閉路においては、これが最小の処理追加可能量である。
負閉路検出部１１０４は、通信変更上限の最小値５０と、処理追加可能量の最小値２０を比較して小さい値２０を変更流量取得する。負閉路検出部１１０４は、処理移動部１７等を介して、これに相当する通信量を削減するように、この閉路内の通信を変更する。
負閉路検出部１１０４は、ノード１ｂＰに、ノード１ｂＤのストリーム１４０ａを処理するプログラム１３０ａを配備し、２０Ｍｂｐｓ分のストリームを実行するように割り当てる。さらに、負閉路検出部１１０４は、ノード１ｂＤからノード１ｈＰのプログラム１３０ａへの通信を２０Ｍｂｐｓ減らし、その処理負荷を減らす。
図４９（Ａ）は、図４８の閉路に基づく通信量の変更、処理の移動を実行して得られる、データと処理の配置を示す。図４９（Ｂ）は、これを参照して生成され、ノード情報格納部１１１に格納されるグラフおよび、これに対して、もう一度、負閉路の探索処理が行われた場合に検出される負閉路を示す。
この負閉路に対し、負閉路検出部１１０４は、通信変更上限の最小値として２０を得る。
また、負閉路検出部１１０４は、この閉路に対する処理可能追加量の最小値を以下のようにして求める。まず、ノード１ｂＰについて、除去する単位処理負荷０．１の方が、追加する単位処理負荷０．０５より大きいので、負閉路検出部１１０４は、ノード１ｂＰの処理可能追加量を無限大とする。次に、ノード１ｅＰについて、除去する単位処理負荷と追加する単位処理負荷が同一なので、負閉路検出部１１０４は、ノード１ｅＰの処理可能追加量を無限大とする。ノード１ｈＰについては、除去する単位処理負荷が０．０５、追加する単位処理負荷が０．１、残存処理可能量が１であるので、負閉路検出部１１０４は、１／（０．１−０．０５）の計算により、ノード１ｈＰの処理追加可能量を２０とする。これにより、負閉路検出部１１０４は、最小の処理可能追加量を２０とする。
最小の通信変更上限値２０と最小の処理可能追加量２０は同一なので、負閉路検出部１１０４は、変更流量を２０とし、図４９（Ｂ）の閉路に適応する。
すなわち、負閉路検出部１１０４は、ノード１ｂＤ上のデータ１４０ａをノード１ｂＰ上で処理する量を２０増やし、ノード１ｂＰがノード１ｄＤから受信して処理していたストリーム１４０ｂの処理を止めて、このストリームはノード１ｅＰにて処理するような変更を計画する。さらに、負閉路検出部１１０４は、ノード１ｅＰにて処理していたノード１ｇＤ上のストリームのうち２０Ｍｂｐｓの処理を止め、その２０Ｍｂｐｓ分のストリームは、ノード１ｈＰにて処理するような変更を計画する。また、負閉路検出部１１０４は、ノード１ｈにて処理していたノード１ｂからのストリームは２０Ｍｂｐｓ分減少させるように計画する。
図５０（Ａ）は、図４９（Ｂ）の閉路に基づく通信量の変更、処理の移動を実行して得られる、データと処理の配置を示す。図５０（Ｂ）は、これを参照して生成され、ノード情報格納部１１１に格納されるグラフおよび、これに対して、さらにもう一度、負閉路の探索処理が行われた場合に検出される負閉路を示す。
図５１（Ａ）は、図５０（Ｂ）の閉路に基づいて、通信量１０Ｍｂｐｓ分の変更、処理の移動を実行して得られる、データと処理の配置を示す。図５１（Ｂ）は、これを参照して生成され、ノード情報格納部１１１に格納されるグラフおよび、これに対して、さらにもう一度、負閉路の探索処理が行われた場合に検出される負閉路を示す。
図５２は、図５１（Ｂ）の閉路に基づいて、通信量５Ｍｂｐｓ分の変更、処理の移動を実行して得られる、データと処理の配置を示す。負閉路検出部１１０４は、この構成からは負閉路を得ることが出来ない。
なお、負閉路検出部１１０４は、図４８、図４９の（Ｂ）、図５０の（Ｂ）、図５１の（Ｂ）の負閉路を検出するたびに通信量の変更、処理の移動を行わず、ノード情報格納部１１１だけを更新し、負閉路が検出されなくなってから、一括で変更計画を実行しても良い。この場合、通信制御システム９０の処理配置は、図３３の（Ａ）の状態から図５２の状態に一度に変更される。また、負閉路検出部１１０４は、図２０に示されるように、表示実行部１８に変更計画を表示し、ユーザからの指示に応じて処理の配置を変更しても良い。
＜第３の実施の形態における動作例＞
図５３の（Ｆ）は、ユーザから実行指示される第１の処理の例を示す。第１の処理は、定常的にデータが発生するストリーム１４０ａをプログラム１３０ａが処理するものである。プログラム１３０ａは、ユーザが利用するアプリケーションプログラムである。ストリーム１４０ａは、およそ３０Ｍｂｐｓのデータを発生させており、プログラム１３０ａがストリーム１４０ａの単位データ量あたりに必要とする計算能力は、０．１ＧＨｚ／Ｍｂｐｓである。
図５３の（Ａ）は、本動作例の通信制御システム９０の構成を示す。通信制御システム９０は、６台の処理サーバ装置１から構成され、３台ずつが２台のスイッチに接続され、さらにその２台のスイッチが上位スイッチに接続されている。
第１の処理のデータ１４０ａは処理サーバ装置１ｃと１ｅに格納されており、これを処理するプログラム１３０ａが処理サーバ装置１ｆで実行される。
図５３の（Ｂ）は、第１の処理の実行前の、処理サーバ装置１ｂと１ｆに格納された経路情報を示す。何の処理も実行していないため、探索長１における総コストはＩｎｆ．である。
この状態で、第１の処理の実行が開始され、更新受付部１１４を介してこれが通知されると、ノード１ｆＰの更新部１１１３は、図２５の手順を実行する。更新部１１１３は、処理ノード１ｆｐとデータノード１ｅＤとの通信コスト２を得て、この負値−２と、利用通信量３０を、処理ノード１ｆｐの出ノードリスト６１に登録し、データノード１ｅＤの入ノードリスト６２に処理ノード１ｆｐを登録する。
この時処理ノード１ｆｐの探索長１の総コストはＩｎｆ．であり、ゼロではない。従って、更新部１１１３は、ノード情報共有格納部１１３４等から取得される処理ノード候補リスト６３の中の残存処理可能量がゼロでない処理ノードを取得する。この結果、更新部１１１３は、処理ノード１ｂＰを得る。この処理ノード１ｆｐの残存処理可能量はゼロであるが、出ノードリスト６１には処理ノードは存在しない。
続いて、更新部１１１３は、この処理ノード１ｆｐの探索長１の総コストを０とし、出ノードリスト６１内のノードであるノード１ｅＤに対して、探索長２の総コスト−２でリンク登録通知をする。ノード１ｅＤは、この値を探索長２の総コストとするとともに、経路ノードのノード識別子にノード１ｆＰの識別子を登録する（図５３の（Ｃ））。
処理サーバ装置１ｆからの通知等により、処理サーバ装置１ｅにおいて、ノード１ｅＤに関してデータ送受信と処理の開始を伴う手順（図２３）が実行される。複製先の通信の開始ではなく、このノード１ｅＤ自体を対象とした処理の開始であるため、更新部１１１３は、処理対象データの複製を格納しているノード１ｃＤを取得する。
更新部１１１３は、データサーバ１ｅＤの出ノードリスト６１に、ノード１ｃＤを通信コストゼロ、無限大の通信変更上限で追加し、データサーバ１ｃＤの入ノードリスト６２に、ノード１ｅＤを追加する。
続いて、更新部１１１３は、その複製データを格納しているノード１ｃＤに関して、データ送受信と処理の開始を伴う手順（図２３）実行を指示し、ノード１ｃＤに対してリンク登録通知を行う。ノード１ｃＤの更新部１１１３は、探索長３の総コストを−２に更新する。
続いて、更新部１１１３は、データノード１ｅＤのデータを処理している処理の単位処理量０．１ＧＨｚ／Ｍｂｐｓを最小単位処理量とする。処理ノード候補リスト６３内のノード１ｂＰの残存処理可能量がゼロではないため、更新部１１１３は、ノード１ｅＤとノード１ｂＰ間の通信コスト５を、ノード１ｅＤの出ノードリスト６１に処理ノード１ｂＰの識別子と共に追加し、処理ノード１ｂＰの入ノードリスト６２に、ノード１ｅＤの識別子を追加する。
ノード１ｅＤの更新部１１１３は、ノード１ｂＰに対してリンク登録通知を行う。ノード１ｂＰは、探索長３における総コストを３にする。ノード１ｂＰにおけるリンク登録通知によって経路情報が更新されたため、ノード１ｆｐ、ノード１ｅＤへは順次、この更新の影響が伝搬する（図５３の（Ｄ））。
上述のデータノード１ｃＤに関するデータ送受信と処理の開始反映指示を受けて、処理サーバ装置１ｃ等の更新部１１１３は、処理サーバ装置１ｂＰと１ｆＰに対して、それぞれ通信コスト２と５でリンクをはる。
図５３の（Ｅ）は、その結果として得られる、ノード情報格納部１１１、経路格納部１１０６等の情報を示す。表中の矢印の起点は、経路ノードを示している。また、表の最下行は、それぞれのノードの平均コストの最大値Ｍを示している。
この状態では平均コストが負の閉路は存在しないので、通信変更計画は生成されない。なお、ここで、ノード数Ｎの増加を検知したノードは、他ノードに通知し、それに応じて経路情報が更新される。
図５４の（Ａ）は、図５３の（Ｅ）が示す状態にある通信制御システム９０が第２の処理を始めた場合の状態を示す。
図５４の（Ｆ）は、第２の処理の例を示す。第２の処理は、定常的にデータが発生するストリーム１４０ｂをプログラム１３０ｂが処理するものである。プログラム１３０ｂは、ユーザが利用するアプリケーションプログラムである。ストリーム１４０ｂは、およそ３０Ｍｂｐｓのデータを発生しており、プログラム１３０ａがストリーム１４０ｂの単位データ量あたりに必要とする計算能力は、０．１ＧＨｚ／Ｍｂｐｓである。
第２の処理のデータ１４０ｂは処理サーバ装置１ａと１ｆに格納されており、これを処理するプログラム１３０ｂが処理サーバ装置１ｂで実行される。
第２の処理が処理サーバ装置１ｂで開始されて、これが更新受付部１１４を介して通知されると、処理ノード１ｂＰの更新部１１１３は、データノード１ａＤに対して、通信コスト−２でリンクを張り、ノード１ａＤについての経路格納部１１０６の経路情報を更新する（図５４の（Ｂ））。
ノード１ａＤの更新部１１１３は、通信・処理が開始されたデータの複製を有する他のデータノード１ｆＤに対して通信コスト０で、また、ノード１ｆＰに通信コスト５でリンクを張り、それぞれの経路情報も更新する（図５４の（Ｃ））。
同様に、ノード１ｆＤの更新部１１１３は、ノード１ｆＰに対して通信コスト０、ノード１ｂＰに対して通信コスト５でリンクを張り、経路情報を更新する（図５４の（Ｄ））。
ノード１ｆＰの更新部１１１３は、平均コストの最大値Ｍの算出結果（図５４の（Ｄ）の表の最下行）として、負の値（−１／３）を検出する。
さらに、経路ノードを辿ることで（１ｆＰ，１ｆＤ，１ａＤ，１ｂｐ，１ｃＤ，１ｃＤ，１ｅＤ，１ｆＰ）の閉路（図５５の（Ａ））が得られ、これに基づく変更計画が実行されると、通信制御システム９０は、通信コストの低い処理の割り当て（図５５の（Ｂ））を実現することができる。
次に、処理フロー制約がある場合の動作を、図５７の（Ａ）が示す処理を例に説明する。ここでは、２つのデータが処理サーバ装置１ｂと処理サーバ装置１ｄに格納され、それぞれが処理サーバ装置１ｃ、処理サーバ装置１ｅで処理される。各々の処理の出力が処理サーバ装置１ｆと処理サーバ装置１ａに格納される。
図５７の（Ｂ）は、このとき出ノードリスト６１、入ノードリスト６２に格納されるリンクを示す。図５７の（Ｃ）は経路格納部１１０６に格納される経路情報を示し、図５７の（Ｄ）は、検出される負閉路（１ｅＰ，１ａＤ，１ｃｐ，１ｆＤ，１ｅＰ）を示す。この負閉路の平均通信コストの最大値Ｍは−１．５であり、総通信コストは−６である。
この負閉路に基づく通信の変更計画は、ノード１ｅＰについては、ノード１ａＤとの通信削除と１ｆＤとの通信追加、ノード１ｃＰについては、ノード１ａＤとの通信追加とノード１ｆＤとの通信削除を含む。ここで、処理フロー制約として（１ａＤ，１ｄＤ），（１ｆＤ，１ｂＤ）が存在することから、負閉路検出部１１０４は、変更計画の決定に際し、ノード１ｅＰについてはノード１ｄＤとの通信削除、ノード１ｂＤとの通信追加、ノード１ｃＰについては、ノード１ｄＤとの通信追加、ノード１ｂＤとの通信削除の通信コストも評価する。この変更は、図５７の（Ｅ）の閉路に対応する。
図５７の（Ｅ）の各リンクの通信コストは、−２÷（３／１）、５÷（３／１）、５÷（３／１）、−２÷（３／１）であり、この閉路の総通信コスト２となる。
検出された負閉路（図５７の（Ｄ））の総コストは−６、制約から計算される閉路（図５７の（Ｅ））の総コストは２であり、合計で負となる。この為、負閉路検出部１１０４は、図５７（Ｄ）と図５７（Ｅ）に基づく両変更計画を処理移動部１７に反映させる。
図５７の（Ｆ）は、移動後の処理配置を示す。
図５６は、データが逐次処理される場合で処理ノードを逐次割り当てる場合（Ａ）と、関連する処理の処理ノードを一括で割り当てる場合（Ｂ）を示している。逐次割り当てる場合（Ａ）、探索処理部１１０は、前段の処理の出力を後段の処理の入力データとしてモデル化し、第３の実施の形態までの手法を逐次用いて割り当てを決定する。
一括で割り当てる場合、探索処理部１１０は、ある処理サーバ装置１上での処理を、前段の入力データを格納した処理サーバ装置１に近いように割り当てるだけではない。探索処理部１１０は、後段の出力データを格納する処理サーバ装置１への近さも考慮して、即ち、前述したように処理フロー誓約を反映して、処理を割り当てる処理サーバ装置１を決定する。
＜第４の実施の形態における動作例＞
図５８は、本説明で用いる１入力１出力の処理を実行する通信制御システム９０の例を示す。
入力データ集合を構成する１ＧＢと２ＧＢのデータファイル（図５８の（Ａ）のｄとｂ）が、おのおの処理サーバ装置１ｄと処理サーバ装置１ｂとに格納されている（図５８の（Ｂ））。
処理サーバ装置１ｄ上のデータ（ｄ）は、処理サーバ装置１ｅで処理され、その処理結果（３ＧＢ）は、処理サーバ装置１ａに格納される。処理サーバ装置１ｂ上のデータ（２ＧＢ）は、処理サーバ装置１ｂで処理され、その処理結果（６ＧＢ）の半分（３ＧＢ）は処理サーバ装置１ａに、他の半分（３ＧＢ）は処理サーバ装置１ｆに格納される。即ち、出力データ集合を構成する６ＧＢと３ＧＢのデータファイルが、処理サーバ装置１ａと処理サーバ装置１ｆとに格納される。なお、各入力データに対応する出力データの格納先は、例えば、データの識別子や、そのハッシュ値によって一意に決まる。
この例に於いて、入力データの処理サーバ装置１と出力データの処理サーバ装置１との対は、（処理サーバ装置１ｄ，処理サーバ装置１ａ）、（処理サーバ装置１ｂ，処理サーバ装置１ａ）、（処理サーバ装置１ｂ，処理サーバ装置１ｆ）が存在する。それぞれの対は、１ＧＢの入力データ量と３ＧＢの出力データ量を有している。
本実施の形態の通信制御システム９０は、これらの対をデータノードとして管理する。そして、（処理サーバ装置１ｄ，処理サーバ装置１ａ）の対（図中データノード１５０ｄａと表記）と処理サーバ装置１ｂ（処理ノード１ｂＰ）との間の通信コストは、入出力のデータ量の比を反映させ１×５＋３×２＝１１となる。また、（処理サーバ装置１ｄ，処理サーバ装置１ａ）の対（データノード１５０ｄａ）と処理サーバ装置１ｅ（処理ノード１ｅＰ）との間の通信コストは、１×２＋３×５＝１７となる。
このような管理方式に従って、処理サーバ装置１ｅ、１ｂともに、処理サーバ装置１ａ、１ｂ、１ｄ、１ｆが、処理ノード１ｂＰ、１ｅＰ、データノード１５０ｄａ、１５０ｂａ、１５０ｂｆ対応に、それぞれの入ノードリスト６２と出ノードリスト６１を作成する。ここで、データノード１５０ｄａ、１５０ｂａ、１５０ｂｆは、おのおの（処理サーバ装置１ｄ，処理サーバ装置１ａ）、（処理サーバ装置１ｂ，処理サーバ装置１ａ）（処理サーバ装置１ｂ，処理サーバ装置１ｆ）の対に対応する。
図５８の（Ｃ）はこの結果生成されるリンクを、（Ｄ）は作成される経路情報を、（Ｅ）は検出される負閉路を示す。図５８の（Ｆ）は、この負閉路を基に変更を行った後の処理の配置を示す。
図５９は、本説明で用いる２入力の処理を実行する通信制御システム９０の例を示す。この通信制御システム９０は、図５９の（Ａ）が示すように、２つのデータ集合の直積を取った集合を処理する。
一方のデータ集合（図５９の（Ａ）のａとｆ）は、処理サーバ装置１ａと処理サーバ装置１ｆに格納され、もう一方のデータ集合（ｂとｃ）が処理サーバ装置１ｂと処理サーバ装置１ｄに格納される。各データ集合の部分集合ａ乃至ｂは、２ＧＢずつである。
２つのデータ集合を格納する処理サーバ装置１の組み合わせである、（処理サーバ装置１ａ，処理サーバ装置１ｂ）、（処理サーバ装置１ａ，処理サーバ装置１ｃ）、（処理サーバ装置１ｆ，処理サーバ装置１ｂ）、（処理サーバ装置１ｆ，処理サーバ装置１ｃ）の４つの対に対応するデータノード１６０１１、１６０１２、１０６２１、１６０２２が、データ格納先管理４にて管理される。
図５９（Ｂ）が示すように、（ａ，ｂ）のデータが、処理サーバ装置１ｄで実行されている。処理サーバ装置１ｄと処理サーバ装置１ａとの間の通信コストは５、処理サーバ装置１ｄと処理サーバ装置１ｂとの間の通信コストは５である。さらに、２つのデータ集合のデータ量は同一である。従って、処理サーバ装置１ｄの通信コスト算出部１１２は、処理ノード１ｄＰとデータノード１０６１１との間の通信コストを５＋５＝１０と算出する。データ送受信と処理を実行する処理サーバ装置１ｂ、１ｅ、１ｆは、それぞれ処理しているデータに応じた通信コストを同様に算出する。
図５９の（Ｃ）はこの結果生成されるリンクを、（Ｄ）は作成される経路情報を、（Ｅ）は検出される負閉路を示す。図５９の（Ｆ）は、この負閉路を基に変更を行った後の処理の配置を示す。
以上、実施形態を参照して本願発明を説明した。しかし、本願発明は、上記の実施形態に限定されるものではない。本願発明の構成や詳細には、本願発明のスコープ内で当業者が理解しうる様々な変更をすることができる。
この出願は、２０１１年５月２３日に出願された日本出願特願２０１１−１１４６４４を基礎とする優先権を主張し、その開示の全てをここに取り込む。
【符号の説明】
【００１０】
１  処理サーバ装置
１０  通信網
１１  負閉路探索部
１１０  探索処理部
１１０１  起動部
１１０２  受信部
１１０３  転送部
１１０４  負閉路検出部
１１０５  経過格納部
１１０６  経路格納部
１１１３  更新部
１１１  ノード情報格納部
１１２  通信コスト算出部
１１２１  通信コスト算出部
１１２２  対象ノード情報格納部
１１２３  通信網構成格納部
１１２４  構成コスト格納部
１１２５  通信装置負荷格納部
１１２６  ノード座標格納部
１１３  ノード情報生成部
１１３１  通信先取得部
１１３２  ノード作成部
１１３３  ノード情報交換部
１１３４  ノード情報共有格納部
１１４  更新受付部
１２  通信先格納部
１３  データ処理部
１４  データ格納部
１５  プログラム格納部
１６  実行状態格納部
１７  処理移動部
１８  表示実行部
１８  データ格納先格納部
２  ワーカ装置
３  マスタ装置
４  データ格納先管理装置
８  通信装置
９０  通信制御システム
【図１】
2012161289.tif 000003
【図２】
2012161289.tif 000004
【図３】
2012161289.tif 000005
【図４】
2012161289.tif 000006
【図５】
2012161289.tif 000007
【図６】
2012161289.tif 000008
【図７】
2012161289.tif 000009
【図８Ａ】
2012161289.tif 000010
【図８Ｂ】
2012161289.tif 000011
【図８Ｃ】
2012161289.tif 000012
【図９】
2012161289.tif 000013
【図１０】
2012161289.tif 000014
【図１１Ａ】
2012161289.tif 000015
【図１１Ｂ】
2012161289.tif 000016
【図１２】
2012161289.tif 000017
【図１３】
2012161289.tif 000018
【図１４】
2012161289.tif 000019
【図１５】
2012161289.tif 000020
【図１６Ａ】
2012161289.tif 000021
【図１６Ｂ】
2012161289.tif 000022
【図１６Ｃ】
2012161289.tif 000023
【図１７】
2012161289.tif 000024
【図１８】
2012161289.tif 000025
【図１９】
2012161289.tif 000026
【図２０】
2012161289.tif 000027
【図２１】
2012161289.tif 000028
【図２２】
2012161289.tif 000029
【図２３Ａ】
2012161289.tif 000030
【図２３Ｂ】
2012161289.tif 000031
【図２４Ａ】
2012161289.tif 000032
【図２４Ｂ】
2012161289.tif 000033
【図２４Ｃ】
2012161289.tif 000034
【図２５Ａ】
2012161289.tif 000035
【図２５Ｂ】
2012161289.tif 000036
【図２５Ｃ】
2012161289.tif 000037
【図２６】
2012161289.tif 000038
【図２７】
2012161289.tif 000039
【図２８Ａ】
2012161289.tif 000040
【図２８Ｂ】
2012161289.tif 000041
【図２９】
2012161289.tif 000042
【図３０】
2012161289.tif 000043
【図３１】
2012161289.tif 000044
【図３２】
2012161289.tif 000045
【図３３】
2012161289.tif 000046
【図３４】
2012161289.tif 000047
【図３５】
2012161289.tif 000048
【図３６】
2012161289.tif 000049
【図３７】
2012161289.tif 000050
【図３８】
2012161289.tif 000051
【図３９】
2012161289.tif 000052
【図４０】
2012161289.tif 000053
【図４１】
2012161289.tif 000054
【図４２】
2012161289.tif 000055
【図４３】
2012161289.tif 000056
【図４４Ａ】
2012161289.tif 000057
【図４４Ｂ】
2012161289.tif 000058
【図４４Ｃ】
2012161289.tif 000059
【図４４Ｄ】
2012161289.tif 000060
【図４４Ｅ】
2012161289.tif 000061
【図４５】
2012161289.tif 000062
【図４６】
2012161289.tif 000063
【図４７】
2012161289.tif 000064
【図４８】
2012161289.tif 000065
【図４９】
2012161289.tif 000066
【図５０】
2012161289.tif 000067
【図５１】
2012161289.tif 000068
【図５２】
2012161289.tif 000069
【図５３】
2012161289.tif 000070
【図５４】
2012161289.tif 000071
【図５５】
2012161289.tif 000072
【図５６】
2012161289.tif 000073
【図５７】
2012161289.tif 000074
【図５８】
2012161289.tif 000075
【図５９】
2012161289.tif 000076
【図６０】
2012161289.tif 000077
【国際調査報告】
2012161289.tif 000078
2012161289.tif 000079
2012161289.tif 000080