(57)【要約】　　　（修正有）【課題】データを総合して処理する必要がある場合に、複数のノードで処理を行うときでも、ネットワークの状況によるサービス品質の低下を押さえる。【解決手段】エンドユーザの収容が可能であり、サーバ機能があり、エンドユーザ端末３０からのアクセスのルーチング機能があり、また他のノード２０との通信機能がある装置と、各ノード２０間を収容するネットワークと、各ノード間の通信コストを観測、もしくは推定する装置（コスト計算装置４０）と、サーバ機能が実際に稼働するノード２０を決定し、それに合わせて、各ユーザがそのノード２０からサービスを受ける際のアクセスのルーティング表を決定する装置（最適ノード決定装置５０）と、最適ノード決定装置５０の計算結果を元にサーバ機能が稼働するノード２０を切り替え、それに合わせて各ノード２０のルーティング表を更新する装置（更新装置６０）とを有す。【選択図】　　　　図１
2004080208.tif 000002
【特許請求の範囲】
【請求項１】
エンドユーザ端末へのサービス機能が稼働する最適なノードを選択し、該ノードとエンドユーザ端末との通信をルーティングするサーバ機能稼働ノード決定システムであって、
エンドユーザ端末を収容し、かつサーバ機能を備え、該エンドユーザ端末からのアクセスのルーティング機能を備え、他のノードとの通信機能を備えた複数のノードと、
該複数のノード間を収容するネットワークと、
各ノード間の通信コストを観測もしくは推定するコスト計算装置と、
サーバ機能が実際に稼働するノードを決定し、それに合わせて各エンドユーザ端末が該ノードからサービスを受ける際のアクセスのルーティング表を決定する最適ノード決定装置と、
該最適ノード決定装置の計算結果を元に、サーバ機能が稼働するノードを切り替え、それに合わせて各ノードのルーティング表を更新する更新装置とを有することを特徴とするサーバ機能稼働ノード決定システム。
【請求項２】
請求項１記載のサーバ機能稼働ノード決定システムにおいて、
前記ノードは、単一の装置である必要はなく、ルータ、ユーザマシン、各種サーバマシンなどが接続されたクラスタなどを含み、かつ該ノード間の通信は双方向とも同じ経路を用いることを特徴とするサーバ機能稼働ノード決定システム。
【請求項３】
請求項１記載のサーバ機能稼働ノード決定システムにおいて、
前記コスト計算装置は、周期的または最適ノード決定装置からの依頼があった場合に、各ノード間の通信コストを観測もしくは推定して、その結果を最適ノード決定装置に通知することを特徴とするサーバ機能稼働ノード決定システム。
【請求項４】
請求項１記載のサーバ機能稼働ノード決定システムにおいて、
前記最適ノード決定装置は、コスト計算装置からの通知結果を元にサーバ機能を稼働させるノードを決定し、新たなルーティング表を作成し、周期的またはノードの状況に変化が生じた場合に上記動作を行うことを特徴とするサーバ機能稼働ノード決定システム。
【請求項５】
請求項１記載のサーバ機能稼働ノード決定システムにおいて、
前記更新装置は、最適ノード決定装置の決定結果を受けて、新しく選択されたノードへサーバ機能起動命令を発行し、それまでサーバ機能が稼働していたノードへサーバ機能停止命令を発行し、同時に新しいルーティング表を各ノードへ送信することを特徴とするサーバ機能稼働ノード決定システム。
【請求項６】
エンドユーザ端末へのサービス機能が稼働する最適なノードを選択し、該ノードとエンドユーザ端末との通信をルーティングするサーバ機能稼働ノード決定方法であって、
ノードに対応して頂点を設定し、各ノード間の通信経路が他のノードを経由していなければ、該ノードに対応する頂点間を辺で結び、各辺にそれに対応する通信経路の通信コストの値を割り振ることで、ルーティングを考えるためのグラフを構成し、該グラフの頂点の集合をＶで表し、辺の集合をＥで表し、ｅ∈Ｅに対してｌ（ｅ）でｅの長さを表したときのグラフをＧ＝（Ｖ，Ｅ，ｌ）と置く第１のステップと、
Ｖの中でサービスを受けているユーザ端末を収容している参加ノードに対応するものの集合をＪとし、Ｊの元を全て含むＧの部分木で、含まれている辺の長さの総和がなるべく小さいものを求める第２のステップと、
上記第２のステップで求めた部分木Ｔに含まれる頂点の集合ＶＴ上の関数ＦをＦ（ｖ）＝ｍａｘｕ∈ＶＴｄ（ｕ，ｖ）と定義し（ｄ（ｕ，ｖ）はＴ内でｕ，ｖを結ぶ道に含まれる辺の長さの総和）、Ｆの最小値を与える頂点ｘ＊を求める第３のステップと、
ｘ＊に対応するノードを最適ノードとして出力する第４のステップと、
各ｖ∈Ｊからｘ＊へのＴ内での道をｖとｘ＊に対応するノードが通信する際の最適通信経路とし、該２つのノードが通信する際には、該経路を用いるようにしたルーティング表を出力する第５のステップと
を有することを特徴とするサーバ機能稼働ノード決定方法。
【請求項７】
請求項６記載のサーバ機能稼働ノード決定方法において、
前記第１、第２のステップおよび第４、第５のステップを有するが、第３のステップのみは、該第２のステップで求めた部分木Ｔに含まれる頂点の集合ＶＴ上の関数Ｆを、Ｆ（ｖ）＝Σｕ∈ＶＴ（ｄ（ｕ，ｖ）−ａ（ｖ））２と定義し（ｄ（ｕ，ｖ）はＴ内でｕ，ｖを結ぶ道に含まれる辺の長さの総和、ａ（ｖ）はｄ（ｕ，ｖ）のｕ∈ＶＴについての平均）、Ｆの最小値を与える頂点ｘ＊を求めるステップであることを特徴とするサーバ機能稼働ノード決定方法。
【請求項８】
エンドユーザ端末へのサービス機能が稼働する最適なノードの計算アルゴリズムを実装したサーバ機能稼働ノード決定プログラムであって、
最適ノード決定装置に、
ノードに対応して頂点を設定し、各ノード間の通信経路が他のノードを経由していなければ、該ノードに対応する頂点間を辺で結び、各辺にそれに対応する通信経路の通信コストの値を割り振ることで、ルーティングを考えるためのグラフを構成し、該グラフの頂点の集合をＶで表し、辺の集合をＥで表し、ｅ∈Ｅに対してｌ（ｅ）でｅの長さを表したときのグラフをＧ＝（Ｖ，Ｅ，ｌ）と置く第１の手順と、
Ｖの中でサービスを受けているユーザ端末を収容している参加ノードに対応するものの集合をＪとし、Ｊの元を全て含むＧの部分木で、含まれている辺の長さの総和がなるべく小さいものを求める第２の手順と、
上記第２の手順で求めた部分木Ｔに含まれる頂点の集合ＶＴ上の関数ＦをＦ（ｖ）＝ｍａｘｕ∈ＶＴｄ（ｕ，ｖ）と定義し（ｄ（ｕ，ｖ）はＴ内でｕ，ｖを結ぶ道に含まれる辺の長さの総和）、Ｆの最小値を与える頂点ｘ＊を求める第３の手順と、
ｘ＊に対応するノードを最適ノードとして出力する第４の手順と、
各ｖ∈Ｊからｘ＊へのＴ内での道をｖとｘ＊に対応するノードが通信する際の最適通信経路とし、該２つのノードが通信する際には、該経路を用いるようにしたルーティング表を出力する第５の手順とを実行させるためのプログラム。
【請求項９】
請求項８記載のプログラムにおいて、
最適ノード計算装置に、
前記第１、第２の手順および第４、第５の手順を実行させるが、第３の手順のみは、該第２の手順で求めた部分木Ｔに含まれる頂点の集合ＶＴ上の関数Ｆを、Ｆ（ｖ）＝Σｕ∈ＶＴ（ｄ（ｕ，ｖ）−ａ（ｖ））２と定義し（ｄ（ｕ，ｖ）はＴ内でｕ，ｖを結ぶ道に含まれる辺の長さの総和、ａ（ｖ）はｄ（ｕ，ｖ）のｕ∈ＶＴについての平均）、Ｆの最小値を与える頂点ｘ＊を求める手順を実行させることを特徴としたサーバ機能稼働ノード決定プログラム。
【請求項１０】
請求項８または９記載のサーバ機能稼働ノード決定プログラムを記録した記録媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、サーバ機能が稼働するノードをネットワークの状況に応じて変更することにより、サービス品質を向上させるサーバ機能稼働ノード決定方法およびシステム、ならびにそのプログラムに関する。
【０００２】
【従来の技術】
サーバには、インターネットでの接続を行うための基盤となる機能を提供するサーバと、アプリケーションサービスを提供するサーバとに分けられる。前者には、ＤＮＳ（Ｄｏｍａｉｎ　Ｎａｍｅ　Ｓｙｓｔｅｍ）サーバ、ＤＨＣＰ（（Ｄｙｎａｍｉｃ　Ｈｏｓｔ　Ｃｏｎｔｉｇｕｒａｔｉｏｎ　Ｐｒｏｔｏｃｏｌ）サーバ、アクセスサーバなどがあり、後者には、ＷＷＷ（Ｗｏｒｌｄ　Ｗｉｄｅ　Ｗｅｂ）サーバ、メールサーバ、ニュースサーバなどがある。
【０００３】
これらのサーバにおいて、サーバ機能が静的な情報の配信などの場合には、同じ機能が稼働するノードを複数用意しておき、エンドユーザからのアクセスをネットワークの状況に応じて、これらのノードの間で分散することで、サービスの品質を高める技術が存在している。
【０００４】
【発明が解決しようとする課題】
サーバ機能が各エンドユーザから送信されたデータを総合して処理して、送信するデータを動的に生成する必要がある場合は、複数のノードで処理を行うと、ノード間でそれぞれが収容するエンドユーザからのデータを送信する必要が生じるので、処理が複雑となる。さらに、データの同期性も問題となる。
【０００５】
上記問題を解決するためには、サーバ機能を単一のノードで稼働させておくことが望ましい。
しかしながら、サーバ機能を持つノードを固定しておくと、ネットワークの状況によっては、サービス品質が低下するという問題がある。
【０００６】
本発明の目的は、単一のノードで処理を行う方式を採用しつつ、処理を行うノードを適宜変更することで、これら従来の問題を解決し、データを総合して処理する必要がある場合に、ネットワークの状況によるサービス品質の低下を抑えることが可能なサーバ機能稼働ノード決定方法およびシステム、ならびにそのプログラムを提供することにある。
【０００７】
【課題を解決するための手段】
上記目的を達成するため、本発明のサーバ機能稼働ノード決定システムは、エンドユーザの収容が可能であり、サーバ機能があり、エンドユーザからのアクセスのルーチング機能があり、また他のノードとの通信機能（通信を行う際の経路の測定機能も含む）がある装置と、各ノード間を収容するネットワークと、各ノード間の通信コストを観測、もしくは推定する装置（コスト計算装置）と、サーバ機能が実際に稼働するノードを決定し、それに合わせて、各ユーザがそのノードからサービスを受ける際のアクセスのルーティング表を決定する装置（最適ノード決定装置）と、最適ノード決定装置の計算結果を元にサーバ機能が稼働するノードを切り替え、それに合わせて各ノードのルーティング表を更新する装置（更新装置）とを有し、このシステムにおいて、エンドユーザへのサービス機能が稼働する最適なノードを選択し、そのノードとエンドユーザの通信をルーティングする。
【０００８】
本発明の最適ノードの決定方法は、ルーティングを考えるグラフを構成するために、ノードに対応して頂点を設定し、各ノード間の通信経路が他のノードを経由していなければ、それらのノードに対応する頂点間を辺で結ぶ。各辺に、それに対応する通信経路の通信コストの値を割り振る。（以後、辺に割り振られている値を長さと呼ぶ）このようにして作成したグラフをＧ＝（Ｖ，Ｅ，ｌ）と置く。ここで、ＶはグラフＧの頂点の集合を表し、Ｅは辺の集合を表し、ｅ∈Ｅに対してｌ（ｅ）でｅの長さを表す（ステップ１）。
Ｖの中で参加ノードに対応するものの集合をＪとする。Ｊの元を全て含むＧの部分木で、含まれている辺の長さの総和がなるべく小さいものを求める（ステップ２）。
ステップ２で求めた部分木Ｔに含まれる頂点の集合ＶＴ上の関数ＦをＦ（ｖ）＝ｍａｘｕ∈ＶＴｄ（ｕ，ｖ）と定義する。ここで、ｄ（ｕ，ｖ）はＴ内でｕ，ｖを結ぶ道に含まれる辺の長さの総和である。Ｆの最小値を与える頂点ｘ＊を求める（ステップ３）。
ｘ＊に対するノードを最適ノードとして出力する（ステップ４）。
各ｖ∈Ｊからｘ＊へのＴ内での道をｖとｘ＊に対応するノードが通信する際の最適通信経路とする。この２つのノードが通信する際には、この経路を用いるようにしたルーティング表を出力する（ステップ５）。
【０００９】
【発明の実施の形態】
以下、本発明の動作原理および実施例を、図面により詳細に説明する。
（動作原理）
本発明のサーバ機能稼働ノード決定システムは、以下のシステムを考える。このシステムにおいて、エンドユーザへのサービス機能（サーバ機能）が稼働する最適なノードを選択し、そのノードとエンドユーザとの通信をルーティングする。
【００１０】
本発明のシステムの構成要素は、以下の通りである。
（イ）次の機能を行う能力がある装置（ノード）
エンドユーザを収容する、
サーバ機能を有する、
エンドユーザからのアクセスのルーティング機能を有する、
他のノードとの通信機能（通信を行う際の経路の測定機能も含む）、
【００１１】
（ロ）各ノード間を収容するネットワーク、
（ハ）各ノード間の通信コストを観測もしくは推定する装置（コスト計算装置）、
（ニ）サーバ機能が実際に稼働するノードを決定し、それに合わせて、各ユーザがそのノードからサービスを受ける際のアクセスのルーティング表を決定する装置（最適ノード決定装置）、
（ホ）最適ノード決定装置の計算結果を元にサーバ機能が稼働するノードを切り替え、それに合わせて各ノードのルーティング表を更新する装置（更新装置）、
【００１２】
本発明のシステム構成要素の詳細は、以下の通りである。
（ａ）ノードは単一の装置である必要はなく、ルータ、ユーザマシン、各種サーバマシン等が接続されたクラスタ等でもよい。収容しているエンドユーザの中に、実際にサービスを受けているユーザが存在しているノードを参加ノード、サービスを受けているユーザを収容していないノードを不参加ノードと呼ぶ。また、ノード間の通信は双方向とも同じ経路を用いるものとする。
【００１３】
（ｂ）コスト計算装置は、周期的または最適ノード決定装置からの依頼があった場合に、各ノード間の通信コストを観測、もしくは推定して、その結果を最適ノード決定装置へ通知する。最適ノード決定装置はその結果を元にサーバ機能を稼働させるノードを決定し、新たなルーティング表を作成する。最適ノード決定装置は、周期的、またはノード状況に変化（ある参加ノードが不参加ノードに変わった場合、または、ある不参加ノードが参加ノードへ変わった場合）にこの動作を行う。
【００１４】
（ｃ）更新装置は、その結果を受けて、必要ならば新しく選択されたノードへサーバ機能起動命令を出し、いままでサーバ機能が稼働していたノードへサーバ機能停止命令を出す。同時に新しいルーティング表を各ノードへ送信する。
（ｄ）以後、各ノードは、新ルーティング表を用いてルーティングを行う。
【００１５】
本発明のサーバ機能稼働ノード決定方法は、以下のように行う。
（ステップ１）
ルーティングを考えるグラフを次のように構成する。すなわち、ノードに対応して頂点を設定し、各ノード間の通信経路が他のノードを経由していなければ、それらのノードに対応する頂点哀を辺で結ぶ。各辺に、それに対応する通信経路の通信コストの値を割り振る。以下、辺に割り振られている値を長さと呼ぶ。
このようにして作成したグラフをＧ＝（Ｖ，Ｅ，ｌ）と置く。ここで、ＶはグラフＧの頂点の集合を表し、Ｅは辺の集合を表し、ｅ∈Ｅに対してｌ（ｅ）でｅの長さを表す。
【００１６】
（ステップ２）
Ｖの中で参加ノードに対応するものの集合をＪとする。Ｊの元を全て含むＧの部分木で、含まれている辺の長さの総和がなるべく小さいものを求める。
（ステップ３）
ステップ２で求めた部分木Ｔに含まれる頂点の集合ＶＴ上の関数ＦをＦ（ｖ）＝ｍａｘｕ∈ＶＴｄ（ｕ，ｖ）と定義する。ここで、ｄ（ｕ，ｖ）はＴ内でｕ，ｖを結ぶ道に含まれる辺の長さの総和である。Ｆの最小値を与える頂点ｘ＊を求める。
【００１７】
（ステップ４）
ｘ＊に対するノードを最適ノードとして出力する。
（ステップ５）
各ｖ∈Ｊからｘ＊へのＴ内での道をｖとｘ＊に対応するノードが通信する際の最適通信経路とする。この２つのノードが通信する際には、この経路を用いるようにしたルーティング表を出力する。
【００１８】
本発明の他のサーバ機能稼働ノード決定方法は、前記（ステップ１〜２）および（ステップ４，５）は同じ動作であるが、上記（ステップ３）のみが異なり、以下のように動作する。
（ステップ３）
ステップ２で求めた部分木Ｔに含まれる頂点の集合ＶＴ上の関数Ｆを、Ｆ（ｖ）＝Σｕ∈ＶＴ（ｄ（ｕ，ｖ）−ａ（ｖ））２と定義する。ここで、ｄ（ｕ，ｖ）はＴ内でｕ，ｖを結ぶ道に含まれる辺の長さの総和で、ａ（ｖ）はｄ（ｕ，ｖ）のｕ∈ＶＴについての平均である。Ｆの最小値を与える頂点ｘ＊を求める。
【００１９】
（実施例）
以下に、本発明の実施例を図に従って説明する。
図１は、本発明の一実施例を示すサーバ機能稼働ノード決定システムの模式図である。
図１において、ノード（請求項１）に対応するのは各エッジノード２０である。エッジノード２０は、インターネット内に配置され、ルータ１０やスイッチ等で接続されている。エンドユーザ端末３０とサーバ機能が稼働しているエッジノード２０との間の通信は、そのエンドユーザ端末３０を収容するエッジノード２０を介して行われる。エンドユーザ端末３０とエッジノード２０は、直接接続されずにインターネット網を介して通信してもよい。図１では、それぞれのエンドユーザ端末３０がいずれかのエッジノード２０に収容されていることを示すために、各エッジノード２０とそれが収容しているエンドユーザ端末３０を線で結んで表記している。４０はコスト計算機、５０は最適ノード決定装置、６０は更新装置である。これらは、システム内に設けられる。
【００２０】
エッジノード２０間での通信のルーティングは、アプリケーション層で行う。
この例では、ノードｎｉ，ｎｊ間の通信コストとして、ノードｎｉ，ｎｊ間で通信が行われる際にパケットが通過する経路のホップ数を採用する。さらに、各エッジノードは他のエッジノードと通信する際に、パケットが通過する経路を調べる手段を持ち、コスト計算装置４０が各エッジノードに分散して配置されているものと考える。
【００２１】
各エッジノード２０は、予め定めた周期毎にお互いの通信経路を調べ、その結果を最適ノード決定装置５０へ通知する。さらに、あるエッジノード２０の状態が変化した場合、そのエッジノード２０はその旨を最適ノード決定装置５０へ送信する。それにより、最適ノード決定装置５０は各ノードへ通信経路調査命令を出し、その結果を受信する。いずれの場合でも、最適ノード決定装置５０は、ノード間の通信経路とそれぞれの経路の通信コスト（ホップ数）をもとに、サーバ機能稼働ノード決定方法（請求項１）で述べた手順通りにサーバ機能が稼働するノードおよび各ノードがそのノードとパケットをやりとりする際のルーティング表を決定し、各ノードへ通知する。
【００２２】
図２は、サーバ機能稼働ノード決定方法の動作手順を示すフローチャートである。
先ず、時刻がルーティング表更新時刻（予め、一定時刻ごとに設定）になったことを検出すると（ステップ１０１）、各ノードは互いに通信経路を調査し、その結果を最適ノード決定装置へ送信する（ステップ１０２）。最適ノード決定装置は、サーバ機能が稼働するノードおよびそのノードと他のノードが通信する際の経路を決定し（ステップ１０３）、サーバ機能が稼働する新ノードへ稼働命令を送信し、今までサーバ機能が稼働していたノードへ停止命令を送信し、新ノードへのルーティング表を各ノードへ送信する（ステップ１０４）。
【００２３】
一方、新たにエンドユーザ端末がサービスに参加すると（ステップ１０５）、新たに参加した端末を収容するノードは不参加ノードか否かを判別し（ステップ１０６）、不参加ノードでなければ、新しく参加したノードは、そのままサービスを受ける（ステップ１０７）。また、不参加ノードであれば、収容ノードは自分の状態を参加状態へ変更し、そのことを最適ノード決定装置へ連絡する（ステップ１０８）。最適ノード決定装置は、各ノードへ通信経路調査指令を出す（ステップ１０９）。そして、ステップ１０２に進む。
【００２４】
図３は、本発明のルーティング表決定アルゴリズムの流れを示すフローチャートである。
なお、ステップ２のアルゴリズムＡの詳細は図４で後述し、ステップ３のアルゴリズムＢの詳細は図５で後述する。
（ステップ１）
グラフを以下の通り構成する。
１）各ノードに対応して頂点を設定し、ノードｕ，ｖ間の通信経路が他のノードを経由していなければ、ｕ，ｖに対応する頂点を辺で結ぶ。
辺の長さ＝対応する通信経路の通信コストの値とする。
このようにして構成したグラフをＧ＝（Ｖ，Ｅ，ｌ）と置く。（なお、Ｖ，Ｅはそれぞれ頂点、辺の集合を表し、辺ｅに対してｌ（ｅ）でｅの長さを表す）（２０１）。
【００２５】
（ステップ２）
Ｊ＝対応するノードが参加ノードである頂点の集合と置く。アルゴリズムＡを用いて、Ｊの元を全て含むＧの部分木Ｔを求める（２０２）。
（ステップ３）
ＴにアルゴリズムＢを適用し、出力として頂点ｘ＊を得る（２０３）。
（ステップ４）
ｘ＊に対応するノードを最適ノードとして出力する（２０４）。
【００２６】
（ステップ５）
ｖ∈Ｊについて、ｘ＊との間のＴにおける道に対応する通信経路を、この２点に対応するノードが通信する際の最適通信経路とする。この経路を用いて通信するように設定された、各ノードのルーティング表を出力する（２０５）。
【００２７】
図４は、図３におけるステップ２で用いるアルゴリズムＡのフローチャートである。
（ステップ１）
グラフＧ、頂点集合Ｊより完全グラフＧ１＝（Ｖ１，Ｅ１，ｌ１）を構成する。ここで、Ｖ１＝Ｊで、Ｅ１は頂点間の辺を表す。ｌ１はＥ１上の関数で、ｅ＝（ｕ，ｖ）∈Ｅ１に対して、ｌ１（ｅ）＝‘Ｇにおいてｕ，ｖを結ぶ最短経路の長さ（経路に含まれる辺の長さの総和）’と定義する（３０１）。
【００２８】
（ステップ２）
Ｇ１で最小被覆木を求める。これをＴ１と置く（３０２）。
（ステップ３）Ｔ１の各辺を対応するＧでの最短経路に置き換えてＧの部分グラフを構成する。この部分グラフをＧＳと置く（３０３）。
（ステップ４）
ＧＳの最小被覆木を求める。その最小被覆木をＴＳと置く（３０４）。
（ステップ５）
ＴＳの葉でＪに含まれないものがあったならば削除していく。全ての葉がＪになったならば、それをＴとして出力する（３０５）。
【００２９】
図５は、図３のステップ３で用いるアルゴリズムＢのフローチャートである。（ステップ１）
木Ｔをコピーして木Ｔ’を作る（４０１）。
（ステップ２）
木Ｔ’が一つの辺ｅ＝（ｕｒ，ｖｓ）であったならば（４０２）、二点ｕｒ，ｖｓのうち、Ｆの値が大きくない方をｘ＊として出力として終了する（４０４，４１３）。
【００３０】
（ステップ３）
木Ｔ’の重心ｖｃを次の手順で求める。ここで、ｎ（ｖ）は各頂点ｖに割り当てられている変数を表し、ｎは木Ｔ’の頂点の数を表す（４０３）。
（ステップ３．１）
木Ｔ’をコピーして木Ｐを作る。木Ｐの任意の頂点ｖについて、
ｎ（ｖ）←ｎ−１とする（４０３）。
【００３１】
（ステップ３．２）
木〜Ｔ’がただ一つの頂点ｖ０からなっていたならば（４０５）、ｖ０を重心ｖｃとして出力して終了する（４０６）。
（ステップ３．３）
木Ｐの葉ｖについて、次の処理を行う：ｎ（ｖ）≦［ｎ／２］ならば（４０７）、ｖを重心ｖｃとして出力して終了する（４０８）。
そうでなければ、ｖに木Ｐにおいて隣接する頂点ｕに対して、ｎ（ｕ）←ｎ（ｕ）−（ｎ−ｎ（ｖ））とし、ｖと辺（ｕ，ｖ）を木Ｐから取り除いて、ステップ３．２（４０５）に戻る（４０９）。
【００３２】
（ステップ４）
ｗをｄ（ｗ，ｖｃ）＝ｍａｘｕ∈ＶＴ｛ｄ（ｕ，ｖｃ）｝を満たす頂点とする。Ｔ−ｖの連結成分の中でｖ’を含むものをＴ”’とする。Ｔ”’とｖｃとＴ内で、この二つを結ぶ辺からなるＴの部分木をＴ”と置く（４１０）。
（ステップ５）
【数１】
2004080208.tif 000003
を満たす頂点ｗ∈ＶＴがあったならば（４１１）、ＶＣをｘ＊として出力して終了する（４１２，４１３）。
（ステップ６）
Ｔ’←Ｔ’∩Ｔ”としてステップ２（４０２）に戻る（４１４）。
【００３３】
図４、図５のアルゴリズムが目的を達成することは、数学的に証明された既知の事実である。
これにより、アルゴリズムＡ，Ｂの動作を具体的なグラフを例にとって説明する。
図６は、サーバ機能稼働ノード決定方法を説明するためのネットワークの図である。
各エッジノードが互いの通信経路を調べた結果を最適ノード決定装置へ通知し、最適ノード決定装置がサーバ機能稼働ノード決定方法（請求項１）のステップ１を実行した結果、図６に示したグラフＧ＝（Ｖ，Ｅ，ｌ）が得られたとする。
ここで、グラフの頂点の名前には対応するエッジノードの名前を付け、各辺の脇にその辺の長さを記した。ｎ２，ｎ４，ｎ６，ｎ８が参加ノードであり、その他のノードｎ１，ｎ３，ｎ５，ｎ７は不参加ノードである。辺に記載された１，３，５，７等は辺の長さを表わしている。
【００３４】
図７および図８は、Ｇ＝（Ｔ，Ｅ，ｌ）に対してアルゴリズムＡを適用した場合の動作説明図である。
図７は、アルゴリズムＡのステップ１の説明図であって、左上では、ノードｎ２から他の頂点であるノードｎ４，ｎ６，ｎ８への最短距離、すなわち経路に含まれる辺の長さの総和を求めると、太線の経路の長さの和は、それぞれ３，３，２である。左下では、ノードｎ４から他の頂点への最短路を求めると、それぞれ３，６，３である。また、右上では、ノードｎ６から他の頂点への最短路を求めると、それぞれ３，６，４である。これらの３通りを矢印のように集約すると、右下のようになる。
【００３５】
図８は、アルゴリズムＡのステップ２〜５の説明図であって、ステップ２では、Ｇ１で最小被覆木を求めて、これをＴ１と置くと、太線の部分が最小被覆木Ｔ１である。次に、ステップ３では、Ｔ１の各辺を対応するＧでの最短経路に置き換えてＧの部分グラフを構成する。この部分グラフをＧＳと置く。
次に、ステップ４では、ＧＳの最小被覆木を求めて、それをＴＳと置く。
次に、ステップ５では、ＴＳの葉でＪに含まれないものがあれば削除するが、全ての葉がＪであるので、Ｔ＝ＴＳとしてＴを出力する。
【００３６】
図９および図１０は、アルゴリズムＡの出力である木ＴをアルゴリズムＢで処理した場合の動作説明図である。
図９は、アルゴリズムＢのステップ１、ステップ２およびステップ３の説明図であって、ステップ１では、木Ｔをコピーして木Ｔ’を作り、ステップ２の１度目は木Ｔ’が一つの辺になっていないため、何もせず素通りして次に進む。ステップ３．１の１度目では、木Ｔ’をコピーして木Ｐを作り、木Ｐの任意の頂点ｖについて、ｎ（ｖ）←ｎ−１とする。すなわち、ｎは木Ｔ’の頂点の数８であるが、これをアルゴリズムに入力して得られたＴおよびそのコピーであるＴ’では、頂点の数は６個になっているので、６−１＝５となる。
【００３７】
ステップ３．２では、Ｐが一の頂点ｖ０であればｖ０をｖＣとして出力して終了するのであるが、ここではＰは一つの頂点ではないため、素通りして次に進む。ステップ３．３では、葉（端にある頂点）ｖとしてｎ４を選んでいる。ｎ（ｎ４）＝５，ｎ＝６であるので、ｎ（ｎ４）＞「ｎ」となる。そこで、ｖに隣接する頂点ｕを選んでｎ（ｎ）←ｎ（ｎ）−（ｎ−ｎ（ｖ））とした後にｖと（ｕ，ｖ）を取り除くことになる。ここでは、ｕ＝ｎ１であるため、ｎ（ｎ１）にｎ（ｎ１）−（ｎ−ｎ（ｎ４））＝５−（６−５）＝４を代入して、ｎ４と（ｎ１，ｎ４）を取り除く。
【００３８】
このようにして、ステップ３．２の２度目も素通り、ステップ３．３の２度目では、ｎ１とｎ３を取り除き、ｎ３の頂点数を５から３とする。ステップ３．３の３度目には、ｎ２とｎ６を取り除き、ｎ２の頂点数を５から４にする。４度目には、ｎ２とｎ３を取り除き、ｎ３の頂点数を３から１にする。このようにして、ステップ３．３の５度目には、ｎ３とｎ８が残るので、ｎ３をｖＣとして出力する。
【００３９】
図１０のステップ４の１度目においては、ｖＣ＝ｎ３からの道の長さが最も長いものはｎ６であるため、ｗ＝ｎ６とする。次に、ＴからｖＣ＝ｎ３を取り除いたものを考える。頂点を取り除いて、何も記載がないときには、そこに直接つながっている辺も除くので、Ｔはばらばらになるが、その中でｗ＝ｎ６を含むものは、頂点ｎ２，ｎ６およびそれ等をつなぐ辺（ｎ２，ｎ６）である。そこで、これらの頂点および辺をまとめてＴ”’と置く。Ｔ”’には辺だけでなく、その両端の頂点も含まれることに注意を要する。
【００４０】
ステップ６の１度目では、Ｔ’←Ｔ’∩Ｔ”から、ｎ２とｎ３およびｎ２とｎ６の頂点と辺がＴ’として次に進む。ステップ３．１の２度目は、木Ｔ’をコピーして木Ｐを作成する。頂点ｖについては、ｎ２，ｎ３，ｎ６の頂点数はいずれも２である。ステップ３．３の１度目では、葉ｖとしてｎ３を選んでいるので、隣接する頂点ｕを選んで、ｎ３とｎ２とその間の辺を取り除くことになる。ｎ２の頂数は２から１になる。ステップ３．３の２度目には、ｎ２をｖＣとして出力する。
【００４１】
ステップ４の２度目には、Ｔ−ｖの連結部分の中でｗを含むものをＴ”’とし（ｎ６＝ｗ）、二つを結ぶ辺からなるＴの部分木をＴ”と置くことで、ｎ２とｎ６が残る。ステップ５の２度目は素通りで、ステップ６の２度目では、Ｔ’←Ｔ’∩Ｔ”としてｎ２，ｎ６が残る。ステップ２の３度目に、木’が一つの辺ｅ＝（ｕｒ，ｖｓ）であれば、Ｆの値が大きくない方、つまりｎ２をｘ＊として出力する。
【００４２】
図１１は、サーバ機能を稼働させるノードが決定された後の全体図である。
図６のグラフで表された状態に対しては、サーバ機能はノードｎ２で稼働させて、参加状態にある各ノードがノードｎ２と通信する際には、図１１のグラフで太線で表示した辺に対応する経路で行うという計算結果が出力される。
最適サーバ決定装置は、ノードｎ２へサーバ機能稼働命令を出し、図１１に対応したルーティング表を各ノードへ送信し、これまでサーバ機能が稼働していたノードには、サーバ機能の停止命令を出す。
【００４３】
本発明の図２〜図５に示すフローをプログラムに変換し、これをＣＤ−ＲＯＭなどの記録媒体に格納しておくことで、最適ノード決定装置、コスト計算装置、更新装置のいずれかに、これらの記録媒体を装着し、プログラムをインストールして装置にこれを実行させれば、本発明が容易に実現されることになる。
【００４４】
【発明の効果】
以上説明したように、本発明によれば、データを総合して処理する必要がある場合に、複数のノードで処理を行うときでも、ネットワークの状況によるサービス品質の低下を押さえることが可能となる。
【図面の簡単な説明】
【図１】本発明の一実施例を示すサーバ機能稼働ノード決定システムの構成の模式図である。
【図２】図１におけるシステムの動作の流れを示すフローチャートである。
【図３】本発明の一実施例を示すルーティング表決定アルゴリズムの動作フローチャートである。
【図４】図３におけるステップ２のアルゴリズムＡの詳細動作のフローチャートである。
【図５】図３におけるステップ３のアルゴリズムＢの詳細動作のフローチャートである。
【図６】本発明により得られたグラフの構成図である。
【図７】図６のグラフに対してアルゴリズムＡを適用した場合の図（その１）である。
【図８】図６のグラフに対してアルゴリズムＡを適用した場合の図（その２）である。
【図９】図６のグラフに対してアルゴリズムＢで処理した場合の図（その１）である。
【図１０】図６のグラフに対してアルゴリズムＢで処理した場合の図（その２）である。
【図１１】図６のグラフで表された状態に対して計算結果の図である。
【符号の説明】
１０…ルータ、２０…エッジノード、３０…エンドユーザ端末、
４０…コスト計算装置、５０…最適ノード決定装置、６０…更新装置、
ｎ１〜ｎ８…参加および不参加ノード。
【図１】
2004080208.tif 000004
【図２】
2004080208.tif 000005
【図３】
2004080208.tif 000006
【図４】
2004080208.tif 000007
【図５】
2004080208.tif 000008
【図６】
2004080208.tif 000009
【図７】
2004080208.tif 000010
【図８】
2004080208.tif 000011
【図９】
2004080208.tif 000012
【図１０】
2004080208.tif 000013
【図１１】
2004080208.tif 000014