サーバ群配置設計システムと方法およびプログラム
【課題】リンク故障時においてもサーバへのアクセスを確保した上で、さらにサーバ集合までの距離を抑えるようなサーバ配置を決定する。
【解決手段】トポロジ情報・設計パラメタ入力部１０１は、ネットワークのトポロジとサーバ数の上限Ｓと整数ｋ，Ｂ，ｒを入力して記憶装置に格納し、サーバ配置箇所選択部１０２は、全てのノードに対して、辺独立な経路でｋ個以上のサーバに到達でき、かつ各ノードからｒ個の最近接サーバまでのホップ距離の総和がＢ以下となるように、Ｓ個以下のサーバを、各ノードからｒ個の最近接サーバまでのホップ距離の総和が最小となるよう、ネットワーク上のノード配置を特定し、サーバ配置箇所出力部１０３は、サーバ配置箇所選択部１０２が特定したノード配置情報を出力する。
【解決手段】トポロジ情報・設計パラメタ入力部１０１は、ネットワークのトポロジとサーバ数の上限Ｓと整数ｋ，Ｂ，ｒを入力して記憶装置に格納し、サーバ配置箇所選択部１０２は、全てのノードに対して、辺独立な経路でｋ個以上のサーバに到達でき、かつ各ノードからｒ個の最近接サーバまでのホップ距離の総和がＢ以下となるように、Ｓ個以下のサーバを、各ノードからｒ個の最近接サーバまでのホップ距離の総和が最小となるよう、ネットワーク上のノード配置を特定し、サーバ配置箇所出力部１０３は、サーバ配置箇所選択部１０２が特定したノード配置情報を出力する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ネットワーク上でコンテンツ配信サービスをするサーバ（コンピュータ）の配置技術に係り、特に、同一コンテンツを保持する複数のサーバを、各サーバの負荷を考慮して効率良く配置するのに好適な技術に関するものである。
【背景技術】
【０００２】
ＷＷＷ（Ｗｏｒｌｄ Ｗｉｄｅ Ｗｅｂ）によるコンテンツ提供において、ユーザによるサーバへのアクセスの快適性の確保は重要である。そのための一つの技術として、同一コンテンツを保持する複数のミラーサーバをネットワーク上に配置し、ユーザからのアクセスを適切なサーバにルーティングすることにより、遅延時間の削減とサーバの負荷分散およびネットワークとサーバの故障への耐性の向上を図るものがある。
【０００３】
この技術を採る場合、ネットワーク上でのサーバの配置場所が性能を左右するため、サーバ配置設計が重要となる。
【０００４】
このようなサーバ配置に関して、これまで様々な観点から研究が行われている。それらは主にサーバまでの距離やサーバ負荷分散を考慮したモデル化が中心である。
【０００５】
例えば、「ｐセンター問題」に基づく技術は、ｐ個のサーバ（センター・コンピュータ）をネットワーク上に配置する際、各点（例えばクライアント・コンピュータ）から最も近いサーバまでの距離の最大値を最小にするというものである。これは、いずれのノード（クライアント・コンピュータ）からも、最も近いサーバまでの距離が短くなるように配置していることを意味する。
【０００６】
類似の技術として、「ｐメディアン問題」や、「施設配置問題」に基づくものがある。これらはいずれも、サーバ集合までの距離を考慮したものであり、サーバアクセスの遅延の削減やネットワーク負荷軽減を目的としたものである。
【０００７】
一方、サーバ群へのアクセスの「信頼性」を考慮したモデル化技術もある。このような信頼性の観点から、リンク故障などの異常時においても、いずれかのサーバまでの経路が確保され、全てのユーザがサービスを継続して受けられることが重要である。
【０００８】
このような信頼性を評価する尺度として、ユーザ（クライアント・コンピュータ）とサーバ群との間の連結性を測るＮＡ（Ｎｏｄｅ−ｔｏ−Ａｒｅａ）連結度というものがある。高い信頼性を実現するためには、要求されるＮＡ連結度を満たすようにサーバ配置を決定することになる。
【０００９】
以上の技術については、非特許文献１に記載されている。
【先行技術文献】
【非特許文献】
【００１０】
【非特許文献１】滝根，伊藤，西尾，“ネットワーク設計理論”，岩波書店，Ｊｕｎ．，２００１．
【発明の概要】
【発明が解決しようとする課題】
【００１１】
このように、クライアントからサーバまでの距離や信頼性それぞれについて要求を満足するサーバ配置を決定する技術は、これまでも広く研究されてきている。しかし、クライアントからサーバまでの距離と信頼性の両者を考慮したものはない。
【００１２】
このような、連結度を保証して信頼性を向上させることと経路長（＝サーバまでの距離）を抑えることの、両方の制約条件を満たすような解を出力するアルゴリズムは、単に、これらアルゴリズムを組み合わせるだけでは対処できず、本質的に新たなアルゴリズムを設計する必要がある。
【００１３】
解決しようとする問題点は、従来の技術では、連結度を保証して信頼性を向上させることと経路長を抑えることの、両方の制約条件を満たすような解を、効率的に求めることができない点である。
【００１４】
本発明の目的は、これら従来技術の課題を解決し、リンク故障時においてもサーバへのアクセスを確保した上で、さらにサーバ集合までの距離を抑えるようなサーバ配置を決定することを可能とすることである。
【課題を解決するための手段】
【００１５】
上記目的を達成するため、本発明では、ヒューリスティックアルゴリズム（近似アルゴリズム）を設計し、信頼性の評価尺度としてＮＡ辺連結度を用い、サーバ集合との間の距離として各点からサーバまでの距離の和を用いることにより、ネットワークのトポロジが与えられたときに、サーバへの接続性を確保しつつホップ距離が最小となるよう、サーバを最適配置する。例えば、（１）ネットワークのトポロジとサーバ数の上限Ｓと整数ｋ，Ｂ，ｒが与えられたときに、全てのノードに対して、辺独立な経路でｋ個以上のサーバに到達でき、かつ各ノードからｒ個の最近接サーバまでのホップ距離の総和がＢ以下となるように、Ｓ個以下のサーバを、各ノードからｒ個の最近接サーバまでのホップ距離の総和が最小となるよう、ネットワーク上のノードに配置する。尚、（２）領域までの距離の和が大きくならないように、各不足成分から点を選んでいく。また、（３）このように各不足成分から点を選ぶ際、他の全ての点までの距離の和が大きくならないよう点を選択する。
【発明の効果】
【００１６】
本発明によれば、ネットワークのトポロジを基に、サーバへの接続性を確保しつつホップ距離が最小となるよう、サーバを最適配置することができ，例えば、ＷＷＷによるコンテンツ提供における、ユーザによるサーバへのアクセスの快適性を確保することが可能となる。
【図面の簡単な説明】
【００１７】
【図１】本発明に係るサーバ群配置設計処理システムの構成例を示すブロック図である。
【図２】図１におけるサーバ群配置設計処理システムの第１の処理動作例を示すフローチャートである。
【図３】図１におけるサーバ群配置設計処理システムの第２の処理動作例を示すフローチャートである。
【図４】図１におけるサーバ群配置設計処理システムの評価例を示す説明図である。
【発明を実施するための形態】
【００１８】
以下、図を用いて本発明を実施するための最良の形態例を説明する。図１では、本発明に係るサーバ群配置設計処理システムの構成例を示しており、本例のサーバ群配置設計処理システムは、ＣＰＵ（Ｃｅｎｔｒａｌ Ｐｒｏｃｅｓｓｉｎｇ Ｕｎｉｔ）や主メモリを具備したコンピュータ構成からなり、プログラムされたコンピュータ処理を実行する機能として、トポロジ情報・設計パラメタ入力部１０１とサーバ配置箇所選択部１０２およびサーバ配置箇所出力部１０３を具備し、これら各部のプログラムされたコンピュータ処理によって、コンテンツ配信サービスをするサーバのネットワーク上での配置を行うと共に、このようなサーバ配置を行う際、サーバへの複数の接続経路を確保すると共に、サーバへの距離が最小となるように、サーバ配置位置の決定を行う。
【００１９】
トポロジ情報・設計パラメタ入力部１０１は、ネットワークのノード・リンクの構成と設計パラメータを入力するものであり、図示していないキーボードやマウス等の入力装置を用いた操作者の入力操作により、例えば、外部記憶媒体、あるいは、オンラインから入力されるトポロジ情報と設計パラメタを入力し、図示していない記憶装置に記憶する。
【００２０】
本例では、トポロジ情報・設計パラメタ入力部１０１は、ネットワークのトポロジとサーバ数の上限Ｓと整数ｋ，Ｂ，ｒを入力して記憶装置に格納する。
【００２１】
サーバ配置箇所選択部１０２は、トポロジ情報・設計パラメタ入力部１０１が入力したデータを用いて最適なサーバ配置個所を算出するものであり、トポロジ情報・設計パラメタ入力部１０１が入力し記憶装置に記憶したトポロジ情報と設計パラメタを読み出して、本発明に係る処理（信頼性と効率性を考慮したサーバ群配置処理）を実行する。
【００２２】
本例では、サーバ配置箇所選択部１０２は、ネットワークのトポロジとサーバ数の上限Ｓと整数ｋ，Ｂ，ｒが与えられたときに、全てのノードに対して辺独立な経路でｋ個以上のサーバに到達でき、かつ各ノードからｒ個の近接サーバまでのホップ距離の総和がＢ以下となるように、Ｓ個以下のサーバを、ネットワーク上のノードに配置する処理を実行する。
【００２３】
サーバ配置個所出力部１０３は、サーバ配置箇所選択部１０２が算出した、サーバを配置するノード群を出力するものであり、サーバ配置箇所選択部１０２の決定結果を、ＣＲＴ（Ｃａｔｈｏｄｅ Ｌａｙ Ｔｕｂｅ）やＬＣＤ（Ｌｉｑｕｉｄ Ｃｒｙｓｔａｌ Ｄｉｓｐｌａｙ）等の表示装置に表示したり、プリンタで印字したり、記憶媒体に記録したり、オンライン上の他のコンピュータ装置等に送信したりする。
【００２４】
以下、このような構成からなるサーバ群配置設計処理システムによる、本発明に係る、サーバ群配置設計処理動作について説明する。
【００２５】
トポロジ情報・設計パラメタ入力部１０１により、処理対象のネットワークのトポロジと設計パラメタを入力する。トポロジデータの例としては、ノードｉとノードｊ間にリンクが存在する場合には「１」を、しない場合には「０」をとる２値変数を要素に持つ行列が考えられる。
【００２６】
また、設計パラメタは、サーバの連結度を表すパラメタｋ（例：ｋ＝３）と、平均ホップ長を考慮する範囲を決めるパラメタｐ（例：ｐ＝２）の二つがある。
【００２７】
サーバ配置箇所選択部１０２は、トポロジ情報・設計パラメタ入力部１０１が入力したトポロジ情報と設計パラメタを用いて効果的なサーバ配置箇所を算出し、サーバ配置箇所出力部１０３は、サーバ配置箇所選択部１０２の算出結果（サーバ配置個所）を出力する。
【００２８】
サーバ配置箇所選択部１０２が算出してサーバ配置箇所出力部１０３が出力するデータは、サーバを設置するノードの集合であり、データフォーマットとしては、例えばノードｎにサーバを配置する場合に「１」を、しない場合に「０」をとる２値変数を要素にもつノード数の次元のベクトルが考えられる（例：（０，０，１，１，０，１，１，０））。
【００２９】
本例のサーバ配置箇所選択部１０２では、以下に詳細を示すようにして、サーバの連結度を表すパラメタｋに対して、極小ｋ辺不足成分Ｓ１，Ｓ２，…，Ｓｐを求め、ｉ＝１，２，…，ｐの各ノードｉに対して、ｍｉｎｖ∈Ｓｉｍａｘｗ∈Ｖ｛ｃ（ｗ）＋ｄ（ｖ，ｗ）｝となる点ｖをｖ＊とし、そのような点ｖ＊が複数ある場合、ｍａｘｗ∈Ｖ｛ｃ（ｗ）＋ｄ（ｖ，ｗ）｝の値をとるｗの個数が最小となる点ｖ＊を選び、全てのｗ∈Ｖに対して、「ｃ（ｗ）←ｃ（ｗ）＋ｄ（ｖ＊，ｗ）」とし、「Ａ←｛ｖ＊｝」とすることで、信頼性と効率性を考慮したサーバ群配置箇所を選択する。
【００３０】
以下、上述のサーバ配置箇所選択部１０２による、本発明に係る信頼性と効率性を考慮したサーバ群配置設計法について、詳細を説明する。
【００３１】
まず、本発明に係る信頼性と効率性を考慮したサーバ群配置設計を行う際に用いる「問題」の「定式化」について説明する。
【００３２】
同一コンテンツを提供するサーバ群へのアクセスの信頼性として、一定の個数のリンク故障時においても、少なくともいずれか一つのサーバへの可到達性を保証できることと考える。従って、信頼性の尺度として、「ＮＡ（Ｎｏｄｅ−ｔｏ−Ａｒｅａ）辺連結度」を用いる。ここでは、説明の簡単のためリンク故障のみを扱うことにする。
【００３３】
まず、ＮＡ辺連結度の定義を述べる。点Ｖと辺Ｅからなる無向グラフＧ＝（Ｖ，Ｅ）において、点部分集合Ｗ（Ｗ⊂Ｖ，Ｗ≠φ）…（φ：空集合）に対して、辺の部分集合｛（ｖ，ｗ）∈Ｅ｜ｖ∈Ｗ，ｗ∈Ｖ−Ｗ｝を「Ｅ（Ｗ）」と表し、カットという。
【００３４】
「Ａ⊆Ｗ，Ｂ⊆Ｖ−Ｗ」であるとき、カットＥ（Ｗ）は集合Ａと集合Ｂを分離するといい、カットＥ（Ｗ）に含まれる辺の本数をカットサイズという。集合Ａと集合Ｂを分離する任意のカットのサイズがｋ以上であるとき、集合Ａと集合Ｂはｋ辺連結と言う。
【００３５】
ｋ辺連結であるような最大のカットサイズｋを、集合Ａと集合Ｂの間の局所辺連結度と言い、λ（Ａ，Ｂ）と表す。これは、どのような（λ（Ａ，Ｂ）−１）本以下の同時リンク故障によっても、集合Ａと集合Ｂ間での通信が継続できることを意味する。
【００３６】
グラフＧ＝（Ｖ，Ｅ）と、その点部分集合族Ｘ＝｛Ｖ１，Ｖ２，…，Ｖｐ｝の組（Ｇ，Ｘ）を「領域グラフ」と言う。各「Ｖｉ∈Ｘ」を領域と言う。このような領域グラフを用いることによって、複数種類のサービスの信頼性を同時に扱うことができるようになる。
【００３７】
すなわち、領域グラフ（Ｇ，Ｘ）において、各点と領域間の局所辺連結度の最小値を、領域グラフのＮＡ辺連結度と言い、λ（Ｇ，Ｘ）と表す。このＮＡ辺連結度がｋである領域グラフをｋＮＡ辺連結領域グラフという。
【００３８】
以降は、説明を簡単にするために、領域グラフの領域は一つ「Ａ」だけとするが、複数の領域の場合も同様にできる。
【００３９】
「信頼性を確保する」ことに目的を限定したサーバ配置は、サーバ数がＳ、要求ＮＡ辺連結度がｋの時、ｋＮＡ辺連結になるように領域を決定する問題、すなわち、以下の「ＮＡ辺連結度保証領域決定問題」として定式化できる。
【００４０】
「ＮＡ辺連結度保証領域決定問題」
ＩＮＳＴＡＮＣＥ：Ｇ＝（Ｖ，Ｅ）、自然数ｋ，Ｓ．
ＱＵＥＳＴＩＯＮ：領域グラフ（Ｇ，Ａ）（ただし｜Ａ｜≦Ｓ）におけるＮＡ辺連結度がｋであるようなＡ⊆Ｖは存在するか？
【００４１】
この問題は、Ｏ（１）で解けることが分かっている。
【００４２】
しかし、サーバ配置設計では、このような「信頼性」に加えて「遅延時間の低減」が必要となる。
【００４３】
「遅延時間の低減」を考慮した場合、ｐセンター問題のように、最も近いサーバまでの距離が短くなるようにするという評価基準もありうるが、本例では、以下のように、より現実的な設定を考慮する。
【００４４】
同一コンテンツをサービスするサーバが複数ある場合、ユーザにアクセスさせるサーバは、サーバ間負荷分散アルゴリズムに依存する。アクセスするサーバが決定すると、ＯＳＰＦなどルーティングプロトコルによって最短経路を用いてアクセスする。
【００４５】
従って、本例では、近いものからｒ個のサーバまでの距離（最短経路長）の和が小さいこと（ある自然数Ｂ以下）が望ましいと考える。
【００４６】
尚、近いものからｒ個のサーバまでの距離の最悪値が小さいという評価尺度も考えられる。上述の本例の評価尺度では、その最悪値が高々「Ｂ−ｒ＋１」まで大きくなりうるという意味で、本例の評価尺度の方が緩い。
【００４７】
しかし、最悪値を厳しく抑えることで実行不可能となり、結果的にｒ個のサーバまでの距離をいずれも大きくせざるを得なくなるよりも、むしろサーバまでの距離にばらつきがあっても小さいものが含まれ、また利用されるネットワークリソースの総和が少ない方が望ましい。この観点から、距離の和を抑制する、上述の本例の評価尺度を用いることにする。
【００４８】
そこで、本例では、サーバ配置問題を次のように定式化する。
【００４９】
「ＮＡ辺連結度と距離を保証するサーバ配置問題」
ＩＮＳＴＡＮＣＥ：Ｇ＝（Ｖ，Ｅ）， 自然数ｋ，Ｂ， サーバ数Ｓ．
ＱＵＥＳＴＩＯＮ：領域グラフ（Ｇ，Ａ）（ただし｜Ａ｜≦Ｓ）におけるＮＡ辺連結度がｋ，近いものからｒ個のサーバまでの距離の和がＢ以下（ｍａｘｖ∈ＶΣｉｄ（ｖ，ｓｉ）≦Ｂ）であるようなＡ⊆Ｖは存在するか？
【００５０】
以下、このような問題を解決するために本例で用いる「サーバ配置アルゴリズム」について説明する。
【００５１】
ｋ−ＮＡ辺連結を満たすサーバ配置であれば、多項式時間で解ける。このサーバ配置問題に対するアルゴリズムを以下に述べる。
【００５２】
まず、辺不足集合を定義する。グラフＧにおけるｈ（＜ｋ）辺連結成分Ｃ⊂Ｖであって、Ｃのカットサイズがｋ未満であるものを、ｋ辺不足成分という。ｋ辺不足成分Ｃのうち、Ｃに含まれる任意の真部分集合（集合Ａの要素がすべて集合Ｂの要素になっていて、ＢにはＡの要素以外の要素があるとき、ＡはＢの真部分集合という。）がｋ辺不足成分ではないようなものを、極小ｋ辺不足成分という。
【００５３】
このような定義を用いた下記のアルゴリズム（「Ａｌgｏｒｉｔｈｍ ｋ−ＮＡＬＯＣ」）に対応する処理を実行することで、ｋ−ＮＡ辺連結を満たすサーバ配置問題を解くことができる。
【００５４】
「Ａｌgｏｒｉｔｈｍ ｋ−ＮＡＬＯＣ」
１：ｆｏｒ ｈ＝１，２，…，ｋ ｄｏ
２： ｈ辺連結成分Ｃ（ｈ）＝｛Ｃ（ｈ）１}，Ｃ（ｈ）２，…，Ｃ（ｈ）ｐ（ｈ）｝を求める
３：ｅｎｄ ｆｏｒ
４：極小ｋ辺不足成分の集合｛Ｃ１，Ｃ２，…，Ｃｐ｝を求める
５：｛Ｃ１，Ｃ２，…，Ｃｐ｝の各集合から、任意の点ｖｉ∈Ｃｉを一つずつ選び、
Ｓ＝｛ｖ１，ｖ２，…，ｖｐ｝とする
【００５５】
つまり、極小ｋ辺不足成分から１点ずつ選んで得られた点集合を領域とすることによって、ｋＮＡ辺連結にすることができる。
【００５６】
本例では、「ＮＡ辺連結度」を保証すると共に、「距離」も保証するサーバ配置問題に対して、次の「Ａｌgｏｒｉｔｈｍ ＭＩＮ_ＭＡＸ_Ｄｉｓｔａｎｃｅ」と「Ａｌgｏｒｉｔｈｍ Ａｖｅｒａgｅ_Ｄｉｓｔａｎｃｅ」の２つのヒューリスティックアルゴリズム（近似アルゴリズム）を用いる。
【００５７】
「Ａｌgｏｒｉｔｈｍ ＭＩＮ_ＭＡＸ_Ｄｉｓｔａｎｃｅ」
１：Ａ←φ…（φ：空集合），全てのｗ∈ｖに対してｃ（ｗ）←０
２：極小ｋ辺不足成分Ｓ１，Ｓ２，…，Ｓｐを求める。
３： ｆｏｒ ｉ＝１，２，…，ｐ ｄｏ
４： ｍｉｎｖ∈Ｓｉｍａｘｗ∈Ｖ｛ｃ（ｗ）＋ｄ（ｖ，ｗ）｝となるｖをｖ＊とする
そのような点が複数ある場合、ｍａｘｗ∈Ｖ｛ｃ（ｗ）＋ｄ（ｖ，ｗ）｝の値をとる
ｗの個数が最小となる点を選ぶ．
５： 全てのｗ∈Ｖに対してｃ（ｗ）←ｃ（ｗ）＋ｄ（ｖ＊，ｗ）
６： Ａ←｛ｖ＊｝
７： ｅｎｄ ｆｏｒ
８： Ｉｆ ｓｕｍ＿｛ｉ＝１｝^｛ｒ｝ｍｉｎ＿｛ｐ｝ｄ（ｐ，ｘ）＜＝Ｂ ｆｏｒ ａｎｙ ｘ ｔｈｅｎ Ｏｕｔｐｕｔ Ａ
【００５８】
これは、領域までの距離の和が大きくならないように、各不足成分から点を選んでいっていることになる。尚、８行目の記載は、「Ｉｆ Σｒｉ＝１ｍｉｎｐｄ（ｖ，ｗ）≦Ｂ ｆｏｒ ａｎｙ ｘ ｔｈｅｎ Ｏｕｔｐｕｔ Ａ」と同じ意味である。
【００５９】
「Ａｌgｏｒｉｔｈｍ Ａｖｅｒａgｅ_Ｄｉｓｔａｎｃｅ」
１：Ａ←φ，全てのｗ∈ｖに対してｃ（ｗ）←０
２：極小ｋ辺不足成分Ｓ１，Ｓ２，…，Ｓｐを求める。
３：ｆｏｒ ｉ＝１，２，…，ｐ ｄｏ
４： ｍｉｎｖ∈ＳｉΣｗ∈Ｖ｛ｃ（ｗ）＋ｄ（ｖ，ｗ）｝となるｖをｖ＊とする
そのような点が複数ある場合は、点番号の小さいものを選ぶ．
５： 全てのｗ∈ｖに対してｃ（ｗ）←ｃ（ｗ）＋ｄ（ｖ＊，ｗ）
６： Ａ←｛ｖ＊｝
７：ｅｎｄ ｆｏｒ
８： Ｉｆ ｓｕｍ＿｛ｉ＝１｝^｛ｒ｝ｍｉｎ＿｛ｐ｝ｄ（ｐ，ｘ）＜＝Ｂ ｆｏｒ ａｎｙ ｘ ｔｈｅｎ Ｏｕｔｐｕｔ Ａ
【００６０】
これは、各不足成分から点を選ぶ際、他の全ての点までの距離の和が大きくならないようにしていることになる。尚、８行目の記載は、「Ｉｆ Σｒｉ＝１ｍｉｎｐｄ（ｖ，ｗ）≦Ｂ ｆｏｒ ａｎｙ ｘ ｔｈｅｎ Ｏｕｔｐｕｔ Ａ」と同じ意味である。
【００６１】
以下、図２と図３を用いて、上記２つのアルゴリズム（「Ａｌgｏｒｉｔｈｍ ＭＩＮ_ＭＡＸ_Ｄｉｓｔａｎｃｅ」、「Ａｌgｏｒｉｔｈｍ Ａｖｅｒａgｅ_Ｄｉｓｔａｎｃｅ」）に従ってのサーバ配置個所選択部１０２の処理動作例を説明する。
【００６２】
図２の「Ａｌｇｏｒｉｔｈｍ ＭＩＮ_ＭＡＸ_Ｄｉｓｔａｎｃｅ」では、まず、ステップＳ２０１において、集合Ａを空集合に、コストの総和ｃ（ｗ）を全て０に初期化する。尚、ｃ（ｗ）における「ｗ」は、ある１つのノードを意味し、ｄ（ｖ，ｗ）がノードｖとノードｗとの間の配信に要するコストであり、ｃ（ｗ）は、複数のサーバからノードｗへの配信に要するコストの総和である。
【００６３】
次に、ステップＳ２０２において、要求されるＮＡ辺連結度ｋに対して極小ｋ辺不足成分Ｓ１，Ｓ２，…，Ｓｐを生成する。
【００６４】
ステップＳ２０３においては、全ての極小ｋ辺不足成分に対して、ステップＳ２０４，Ｓ２０５の処理を反復して行う。すなわち、ステップＳ２０４においては、各極小ｋ辺不足成分Ｓｉ（ｉ＝１，２，…，ｐ）に含まれるノードの中から、他の全てのノードに至るコストの最大値が最小となるノードｖ＊を１つ選択し、ステップＳ２０５においては、ステップＳ２０３での処理で選択したノードｖ＊を集合Ａに追加すると共に、ｃ（ｗ）をアップデートする（ｃ（ｗ）←ｃ（ｗ）＋ｄ（ｖ＊，ｗ））。
【００６５】
そして、ステップＳ２０６において、任意のノードｘに対して、距離ｄ（ｐ，ｘ）の短いものからｒ個のサーバまでの距離の総和がＢ以下である場合に、得られた集合Ａを解として出力する。
【００６６】
図３の「Ａｌgｏｒｉｔｈｍ Ａｖｅｒａgｅ_Ｄｉｓｔａｎｃｅ」での処理は、図２にの「Ａｌgｏｒｉｔｈｍ ＭＩＮ_ＭＡＸ_Ｄｉｓｔａｎｃｅ」における処理のステップＳ２０４での処理を、「各極小ｋ辺不足成分Ｓｉ（ｉ＝１，２，…，ｐ）に含まれるノードの中から、他の全てのノードに至るコストの平均値が最小となるノードｖ＊を１つ選択する（ステップＳ２０４’）」処理に代えたものであり、その他の処理は同じである。
【００６７】
次に、図４を用いて、本例のシステムの性能評価結果を説明する。ここでは、ＣＡＩＤＡ （Ｃｏｏｐｅｒａｔｉｖｅ Ａｓｓｏｃｉａｔｉｏｎ ｆｏｒ Ｉｎｔｅｒｎｅｔ Ｄａｔａ Ａｎａｌｙｓｉｓ）において公開されている実際のＩＳＰバックボーンＮＷのグラフ構造を利用して、サーバ配置を決定する。
【００６８】
図４の表４０１の「配置サーバ数」においては、各ＮＷで必要なサーバ数を挙げている。このサーバ数は辺連結度を「２」にするために最低限必要なサーバ数である。表４０１で示す内容から、比較的少数のサーバ設置で要件が満たされることが確認できる。
【００６９】
以上、図１〜図４を用いて説明したように、本例では、ヒューリスティックアルゴリズム（近似アルゴリズム）を設計し、信頼性の評価尺度としてＮＡ辺連結度を用い、サーバ集合との間の距離として各点からサーバまでの距離の和を用いることにより、ネットワークのトポロジが与えられたときに、サーバへの接続性を確保しつつホップ距離が最小となるよう、サーバを最適配置する。
【００７０】
例えば、ネットワークのトポロジとサーバ数の上限Ｓと整数ｋ，Ｂ，ｒが与えられたときに、全てのノードに対して、辺独立な経路でｋ個以上のサーバに到達でき、かつ各ノードからｒ個の最近接サーバまでのホップ距離の総和がＢ以下となるように、Ｓ個以下のサーバを、各ノードからｒ個の最近接サーバまでのホップ距離の総和が最小となるよう、ネットワーク上のノードに配置する。
【００７１】
具体的には、図１に示す構成においｔ、ネットワークにおけるサーバ群の配置個所の選択を、プログラムされたコンピュータのグラフ理論を用いた処理によって行うものであり、トポロジ情報・設計パラメタ入力部１０１により、入力装置を介して入力されるネットワークのトポロジ情報（グラフＧ（Ｖ，Ｅ））とサーバ数の上限値Ｓ、および、ＮＡ辺連結度ｋと、アクセス元のノードに近接するサーバの個数ｒと、ｒ個のサーバまでの距離の和の上限Ｂとを、記憶装置に格納し、サーバ配置箇所選択部１０２により、トポロジ情報・設計パラメタ入力部１０１が記憶装置に格納したデータ（Ｓ，ｋ，Ｂ）を用いた下記のサーバ配置問題の解を求める処理を実行することによって、辺独立な経路でｋ個以上のサーバに到達でき、かつ、ｒ個の近接サーバまでのホップ距離の総和がＢ以下となるノード集合Ａを、Ｓ個以下のサーバを配置するノードとして選択し、サーバ配置箇所出力部１０３により、サーバ配置個所選択部１０２が選択したノード集合Ａをサーバ配置箇所として出力装置に出力する。
【００７２】
「ＮＡ辺連結度と距離を保証するサーバ配置問題」
ＩＮＳＴＡＮＣＥ：Ｇ＝（Ｖ，Ｅ）， 自然数ｋ，Ｂ， サーバ数Ｓ．
ＱＵＥＳＴＩＯＮ：領域グラフ（Ｇ，Ａ）（ただし｜Ａ｜≦Ｓ）におけるＮＡ辺連結度がｋ，近いものからｒ個のサーバまでの距離の和がＢ以下であるようなＡ⊆Ｖは存在するか？
【００７３】
また、サーバ配置個所選択部１０２は、下記のアルゴリズムに従った処理を実行することによって、領域までの距離の和が大きくならないように、各不足成分から点を選んでいく。
【００７４】
「Ａｌgｏｒｉｔｈｍ ＭＩＮ_ＭＡＸ_Ｄｉｓｔａｎｃｅ」
１：Ａ←φ…（φ：空集合），全てのｗ∈ｖに対してｃ（ｗ）←０
２：極小ｋ辺不足成分Ｓ１，Ｓ２，…，Ｓｐを求める。
３： ｆｏｒ ｉ＝１，２，…，ｐ ｄｏ
４： ｍｉｎｖ∈Ｓｉｍａｘｗ∈Ｖ｛ｃ（ｗ）＋ｄ（ｖ，ｗ）｝となるｖをｖ＊とする
そのような点が複数ある場合、ｍａｘｗ∈Ｖ｛ｃ（ｗ）＋ｄ（ｖ，ｗ）｝の値をとる
ｗの個数が最小となる点を選ぶ．
５： 全てのｗ∈Ｖに対してｃ（ｗ）←ｃ（ｗ）＋ｄ（ｖ＊，ｗ）
６： Ａ←｛ｖ＊｝
７： ｅｎｄ ｆｏｒ
８：Ｉｆ Σｒｉ＝１ｍｉｎｐｄ（ｖ，ｗ）≦Ｂ ｆｏｒ ａｎｙ ｘ ｔｈｅｎ Ｏｕｔｐｕｔ Ａ
【００７５】
あるいは、サーバ配置個所選択部１０２は、下記のアルゴリズムに従った処理を実行することによって、各不足成分から点を選ぶ際、他の全ての点までの距離の和が大きくならないよう点を選択する。
【００７６】
「Ａｌgｏｒｉｔｈｍ Ａｖｅｒａgｅ_Ｄｉｓｔａｎｃｅ」
１：Ａ←φ，全てのｗ∈ｖに対してｃ（ｗ）←０
２：極小ｋ辺不足成分Ｓ１，Ｓ２，…，Ｓｐを求める。
３：ｆｏｒ ｉ＝１，２，…，ｐ ｄｏ
４： ｍｉｎｖ∈ＳｉΣｗ∈Ｖ｛ｃ（ｗ）＋ｄ（ｖ，ｗ）｝となるｖをｖ＊とする
そのような点が複数ある場合は、点番号の小さいものを選ぶ．
５： 全てのｗ∈ｖに対してｃ（ｗ）←ｃ（ｗ）＋ｄ（ｖ＊，ｗ）
６： Ａ←｛ｖ＊｝
７：ｅｎｄ ｆｏｒ
８：Ｉｆ Σｒｉ＝１ｍｉｎｐｄ（ｖ，ｗ）≦Ｂ ｆｏｒ ａｎｙ ｘ ｔｈｅｎ Ｏｕｔｐｕｔ Ａ
【００７７】
このことにより、本例によれば、リンク故障時においてもサーバへのアクセスを確保した上で、さらにサーバ集合までの距離を抑えるようなサーバ配置を決定することが可能となり、従来技術の問題点（連結度を保証して信頼性を向上させることと経路長を抑えることの、両方の制約条件を満たすような解を、効率的に求めることができなかった）を解決できる。
【００７８】
尚、本発明は、図１〜図４を用いて説明した例に限定されるものではなく、その要旨を逸脱しない範囲において種々変更可能である。
【符号の説明】
【００７９】
１０１：トポロジ情報・設計パラメタ入力部、１０２：サーバ配置箇所選択部、１０３：サーバ配置箇所出力部、４０１：表。
【技術分野】
【０００１】
本発明は、ネットワーク上でコンテンツ配信サービスをするサーバ（コンピュータ）の配置技術に係り、特に、同一コンテンツを保持する複数のサーバを、各サーバの負荷を考慮して効率良く配置するのに好適な技術に関するものである。
【背景技術】
【０００２】
ＷＷＷ（Ｗｏｒｌｄ Ｗｉｄｅ Ｗｅｂ）によるコンテンツ提供において、ユーザによるサーバへのアクセスの快適性の確保は重要である。そのための一つの技術として、同一コンテンツを保持する複数のミラーサーバをネットワーク上に配置し、ユーザからのアクセスを適切なサーバにルーティングすることにより、遅延時間の削減とサーバの負荷分散およびネットワークとサーバの故障への耐性の向上を図るものがある。
【０００３】
この技術を採る場合、ネットワーク上でのサーバの配置場所が性能を左右するため、サーバ配置設計が重要となる。
【０００４】
このようなサーバ配置に関して、これまで様々な観点から研究が行われている。それらは主にサーバまでの距離やサーバ負荷分散を考慮したモデル化が中心である。
【０００５】
例えば、「ｐセンター問題」に基づく技術は、ｐ個のサーバ（センター・コンピュータ）をネットワーク上に配置する際、各点（例えばクライアント・コンピュータ）から最も近いサーバまでの距離の最大値を最小にするというものである。これは、いずれのノード（クライアント・コンピュータ）からも、最も近いサーバまでの距離が短くなるように配置していることを意味する。
【０００６】
類似の技術として、「ｐメディアン問題」や、「施設配置問題」に基づくものがある。これらはいずれも、サーバ集合までの距離を考慮したものであり、サーバアクセスの遅延の削減やネットワーク負荷軽減を目的としたものである。
【０００７】
一方、サーバ群へのアクセスの「信頼性」を考慮したモデル化技術もある。このような信頼性の観点から、リンク故障などの異常時においても、いずれかのサーバまでの経路が確保され、全てのユーザがサービスを継続して受けられることが重要である。
【０００８】
このような信頼性を評価する尺度として、ユーザ（クライアント・コンピュータ）とサーバ群との間の連結性を測るＮＡ（Ｎｏｄｅ−ｔｏ−Ａｒｅａ）連結度というものがある。高い信頼性を実現するためには、要求されるＮＡ連結度を満たすようにサーバ配置を決定することになる。
【０００９】
以上の技術については、非特許文献１に記載されている。
【先行技術文献】
【非特許文献】
【００１０】
【非特許文献１】滝根，伊藤，西尾，“ネットワーク設計理論”，岩波書店，Ｊｕｎ．，２００１．
【発明の概要】
【発明が解決しようとする課題】
【００１１】
このように、クライアントからサーバまでの距離や信頼性それぞれについて要求を満足するサーバ配置を決定する技術は、これまでも広く研究されてきている。しかし、クライアントからサーバまでの距離と信頼性の両者を考慮したものはない。
【００１２】
このような、連結度を保証して信頼性を向上させることと経路長（＝サーバまでの距離）を抑えることの、両方の制約条件を満たすような解を出力するアルゴリズムは、単に、これらアルゴリズムを組み合わせるだけでは対処できず、本質的に新たなアルゴリズムを設計する必要がある。
【００１３】
解決しようとする問題点は、従来の技術では、連結度を保証して信頼性を向上させることと経路長を抑えることの、両方の制約条件を満たすような解を、効率的に求めることができない点である。
【００１４】
本発明の目的は、これら従来技術の課題を解決し、リンク故障時においてもサーバへのアクセスを確保した上で、さらにサーバ集合までの距離を抑えるようなサーバ配置を決定することを可能とすることである。
【課題を解決するための手段】
【００１５】
上記目的を達成するため、本発明では、ヒューリスティックアルゴリズム（近似アルゴリズム）を設計し、信頼性の評価尺度としてＮＡ辺連結度を用い、サーバ集合との間の距離として各点からサーバまでの距離の和を用いることにより、ネットワークのトポロジが与えられたときに、サーバへの接続性を確保しつつホップ距離が最小となるよう、サーバを最適配置する。例えば、（１）ネットワークのトポロジとサーバ数の上限Ｓと整数ｋ，Ｂ，ｒが与えられたときに、全てのノードに対して、辺独立な経路でｋ個以上のサーバに到達でき、かつ各ノードからｒ個の最近接サーバまでのホップ距離の総和がＢ以下となるように、Ｓ個以下のサーバを、各ノードからｒ個の最近接サーバまでのホップ距離の総和が最小となるよう、ネットワーク上のノードに配置する。尚、（２）領域までの距離の和が大きくならないように、各不足成分から点を選んでいく。また、（３）このように各不足成分から点を選ぶ際、他の全ての点までの距離の和が大きくならないよう点を選択する。
【発明の効果】
【００１６】
本発明によれば、ネットワークのトポロジを基に、サーバへの接続性を確保しつつホップ距離が最小となるよう、サーバを最適配置することができ，例えば、ＷＷＷによるコンテンツ提供における、ユーザによるサーバへのアクセスの快適性を確保することが可能となる。
【図面の簡単な説明】
【００１７】
【図１】本発明に係るサーバ群配置設計処理システムの構成例を示すブロック図である。
【図２】図１におけるサーバ群配置設計処理システムの第１の処理動作例を示すフローチャートである。
【図３】図１におけるサーバ群配置設計処理システムの第２の処理動作例を示すフローチャートである。
【図４】図１におけるサーバ群配置設計処理システムの評価例を示す説明図である。
【発明を実施するための形態】
【００１８】
以下、図を用いて本発明を実施するための最良の形態例を説明する。図１では、本発明に係るサーバ群配置設計処理システムの構成例を示しており、本例のサーバ群配置設計処理システムは、ＣＰＵ（Ｃｅｎｔｒａｌ Ｐｒｏｃｅｓｓｉｎｇ Ｕｎｉｔ）や主メモリを具備したコンピュータ構成からなり、プログラムされたコンピュータ処理を実行する機能として、トポロジ情報・設計パラメタ入力部１０１とサーバ配置箇所選択部１０２およびサーバ配置箇所出力部１０３を具備し、これら各部のプログラムされたコンピュータ処理によって、コンテンツ配信サービスをするサーバのネットワーク上での配置を行うと共に、このようなサーバ配置を行う際、サーバへの複数の接続経路を確保すると共に、サーバへの距離が最小となるように、サーバ配置位置の決定を行う。
【００１９】
トポロジ情報・設計パラメタ入力部１０１は、ネットワークのノード・リンクの構成と設計パラメータを入力するものであり、図示していないキーボードやマウス等の入力装置を用いた操作者の入力操作により、例えば、外部記憶媒体、あるいは、オンラインから入力されるトポロジ情報と設計パラメタを入力し、図示していない記憶装置に記憶する。
【００２０】
本例では、トポロジ情報・設計パラメタ入力部１０１は、ネットワークのトポロジとサーバ数の上限Ｓと整数ｋ，Ｂ，ｒを入力して記憶装置に格納する。
【００２１】
サーバ配置箇所選択部１０２は、トポロジ情報・設計パラメタ入力部１０１が入力したデータを用いて最適なサーバ配置個所を算出するものであり、トポロジ情報・設計パラメタ入力部１０１が入力し記憶装置に記憶したトポロジ情報と設計パラメタを読み出して、本発明に係る処理（信頼性と効率性を考慮したサーバ群配置処理）を実行する。
【００２２】
本例では、サーバ配置箇所選択部１０２は、ネットワークのトポロジとサーバ数の上限Ｓと整数ｋ，Ｂ，ｒが与えられたときに、全てのノードに対して辺独立な経路でｋ個以上のサーバに到達でき、かつ各ノードからｒ個の近接サーバまでのホップ距離の総和がＢ以下となるように、Ｓ個以下のサーバを、ネットワーク上のノードに配置する処理を実行する。
【００２３】
サーバ配置個所出力部１０３は、サーバ配置箇所選択部１０２が算出した、サーバを配置するノード群を出力するものであり、サーバ配置箇所選択部１０２の決定結果を、ＣＲＴ（Ｃａｔｈｏｄｅ Ｌａｙ Ｔｕｂｅ）やＬＣＤ（Ｌｉｑｕｉｄ Ｃｒｙｓｔａｌ Ｄｉｓｐｌａｙ）等の表示装置に表示したり、プリンタで印字したり、記憶媒体に記録したり、オンライン上の他のコンピュータ装置等に送信したりする。
【００２４】
以下、このような構成からなるサーバ群配置設計処理システムによる、本発明に係る、サーバ群配置設計処理動作について説明する。
【００２５】
トポロジ情報・設計パラメタ入力部１０１により、処理対象のネットワークのトポロジと設計パラメタを入力する。トポロジデータの例としては、ノードｉとノードｊ間にリンクが存在する場合には「１」を、しない場合には「０」をとる２値変数を要素に持つ行列が考えられる。
【００２６】
また、設計パラメタは、サーバの連結度を表すパラメタｋ（例：ｋ＝３）と、平均ホップ長を考慮する範囲を決めるパラメタｐ（例：ｐ＝２）の二つがある。
【００２７】
サーバ配置箇所選択部１０２は、トポロジ情報・設計パラメタ入力部１０１が入力したトポロジ情報と設計パラメタを用いて効果的なサーバ配置箇所を算出し、サーバ配置箇所出力部１０３は、サーバ配置箇所選択部１０２の算出結果（サーバ配置個所）を出力する。
【００２８】
サーバ配置箇所選択部１０２が算出してサーバ配置箇所出力部１０３が出力するデータは、サーバを設置するノードの集合であり、データフォーマットとしては、例えばノードｎにサーバを配置する場合に「１」を、しない場合に「０」をとる２値変数を要素にもつノード数の次元のベクトルが考えられる（例：（０，０，１，１，０，１，１，０））。
【００２９】
本例のサーバ配置箇所選択部１０２では、以下に詳細を示すようにして、サーバの連結度を表すパラメタｋに対して、極小ｋ辺不足成分Ｓ１，Ｓ２，…，Ｓｐを求め、ｉ＝１，２，…，ｐの各ノードｉに対して、ｍｉｎｖ∈Ｓｉｍａｘｗ∈Ｖ｛ｃ（ｗ）＋ｄ（ｖ，ｗ）｝となる点ｖをｖ＊とし、そのような点ｖ＊が複数ある場合、ｍａｘｗ∈Ｖ｛ｃ（ｗ）＋ｄ（ｖ，ｗ）｝の値をとるｗの個数が最小となる点ｖ＊を選び、全てのｗ∈Ｖに対して、「ｃ（ｗ）←ｃ（ｗ）＋ｄ（ｖ＊，ｗ）」とし、「Ａ←｛ｖ＊｝」とすることで、信頼性と効率性を考慮したサーバ群配置箇所を選択する。
【００３０】
以下、上述のサーバ配置箇所選択部１０２による、本発明に係る信頼性と効率性を考慮したサーバ群配置設計法について、詳細を説明する。
【００３１】
まず、本発明に係る信頼性と効率性を考慮したサーバ群配置設計を行う際に用いる「問題」の「定式化」について説明する。
【００３２】
同一コンテンツを提供するサーバ群へのアクセスの信頼性として、一定の個数のリンク故障時においても、少なくともいずれか一つのサーバへの可到達性を保証できることと考える。従って、信頼性の尺度として、「ＮＡ（Ｎｏｄｅ−ｔｏ−Ａｒｅａ）辺連結度」を用いる。ここでは、説明の簡単のためリンク故障のみを扱うことにする。
【００３３】
まず、ＮＡ辺連結度の定義を述べる。点Ｖと辺Ｅからなる無向グラフＧ＝（Ｖ，Ｅ）において、点部分集合Ｗ（Ｗ⊂Ｖ，Ｗ≠φ）…（φ：空集合）に対して、辺の部分集合｛（ｖ，ｗ）∈Ｅ｜ｖ∈Ｗ，ｗ∈Ｖ−Ｗ｝を「Ｅ（Ｗ）」と表し、カットという。
【００３４】
「Ａ⊆Ｗ，Ｂ⊆Ｖ−Ｗ」であるとき、カットＥ（Ｗ）は集合Ａと集合Ｂを分離するといい、カットＥ（Ｗ）に含まれる辺の本数をカットサイズという。集合Ａと集合Ｂを分離する任意のカットのサイズがｋ以上であるとき、集合Ａと集合Ｂはｋ辺連結と言う。
【００３５】
ｋ辺連結であるような最大のカットサイズｋを、集合Ａと集合Ｂの間の局所辺連結度と言い、λ（Ａ，Ｂ）と表す。これは、どのような（λ（Ａ，Ｂ）−１）本以下の同時リンク故障によっても、集合Ａと集合Ｂ間での通信が継続できることを意味する。
【００３６】
グラフＧ＝（Ｖ，Ｅ）と、その点部分集合族Ｘ＝｛Ｖ１，Ｖ２，…，Ｖｐ｝の組（Ｇ，Ｘ）を「領域グラフ」と言う。各「Ｖｉ∈Ｘ」を領域と言う。このような領域グラフを用いることによって、複数種類のサービスの信頼性を同時に扱うことができるようになる。
【００３７】
すなわち、領域グラフ（Ｇ，Ｘ）において、各点と領域間の局所辺連結度の最小値を、領域グラフのＮＡ辺連結度と言い、λ（Ｇ，Ｘ）と表す。このＮＡ辺連結度がｋである領域グラフをｋＮＡ辺連結領域グラフという。
【００３８】
以降は、説明を簡単にするために、領域グラフの領域は一つ「Ａ」だけとするが、複数の領域の場合も同様にできる。
【００３９】
「信頼性を確保する」ことに目的を限定したサーバ配置は、サーバ数がＳ、要求ＮＡ辺連結度がｋの時、ｋＮＡ辺連結になるように領域を決定する問題、すなわち、以下の「ＮＡ辺連結度保証領域決定問題」として定式化できる。
【００４０】
「ＮＡ辺連結度保証領域決定問題」
ＩＮＳＴＡＮＣＥ：Ｇ＝（Ｖ，Ｅ）、自然数ｋ，Ｓ．
ＱＵＥＳＴＩＯＮ：領域グラフ（Ｇ，Ａ）（ただし｜Ａ｜≦Ｓ）におけるＮＡ辺連結度がｋであるようなＡ⊆Ｖは存在するか？
【００４１】
この問題は、Ｏ（１）で解けることが分かっている。
【００４２】
しかし、サーバ配置設計では、このような「信頼性」に加えて「遅延時間の低減」が必要となる。
【００４３】
「遅延時間の低減」を考慮した場合、ｐセンター問題のように、最も近いサーバまでの距離が短くなるようにするという評価基準もありうるが、本例では、以下のように、より現実的な設定を考慮する。
【００４４】
同一コンテンツをサービスするサーバが複数ある場合、ユーザにアクセスさせるサーバは、サーバ間負荷分散アルゴリズムに依存する。アクセスするサーバが決定すると、ＯＳＰＦなどルーティングプロトコルによって最短経路を用いてアクセスする。
【００４５】
従って、本例では、近いものからｒ個のサーバまでの距離（最短経路長）の和が小さいこと（ある自然数Ｂ以下）が望ましいと考える。
【００４６】
尚、近いものからｒ個のサーバまでの距離の最悪値が小さいという評価尺度も考えられる。上述の本例の評価尺度では、その最悪値が高々「Ｂ−ｒ＋１」まで大きくなりうるという意味で、本例の評価尺度の方が緩い。
【００４７】
しかし、最悪値を厳しく抑えることで実行不可能となり、結果的にｒ個のサーバまでの距離をいずれも大きくせざるを得なくなるよりも、むしろサーバまでの距離にばらつきがあっても小さいものが含まれ、また利用されるネットワークリソースの総和が少ない方が望ましい。この観点から、距離の和を抑制する、上述の本例の評価尺度を用いることにする。
【００４８】
そこで、本例では、サーバ配置問題を次のように定式化する。
【００４９】
「ＮＡ辺連結度と距離を保証するサーバ配置問題」
ＩＮＳＴＡＮＣＥ：Ｇ＝（Ｖ，Ｅ）， 自然数ｋ，Ｂ， サーバ数Ｓ．
ＱＵＥＳＴＩＯＮ：領域グラフ（Ｇ，Ａ）（ただし｜Ａ｜≦Ｓ）におけるＮＡ辺連結度がｋ，近いものからｒ個のサーバまでの距離の和がＢ以下（ｍａｘｖ∈ＶΣｉｄ（ｖ，ｓｉ）≦Ｂ）であるようなＡ⊆Ｖは存在するか？
【００５０】
以下、このような問題を解決するために本例で用いる「サーバ配置アルゴリズム」について説明する。
【００５１】
ｋ−ＮＡ辺連結を満たすサーバ配置であれば、多項式時間で解ける。このサーバ配置問題に対するアルゴリズムを以下に述べる。
【００５２】
まず、辺不足集合を定義する。グラフＧにおけるｈ（＜ｋ）辺連結成分Ｃ⊂Ｖであって、Ｃのカットサイズがｋ未満であるものを、ｋ辺不足成分という。ｋ辺不足成分Ｃのうち、Ｃに含まれる任意の真部分集合（集合Ａの要素がすべて集合Ｂの要素になっていて、ＢにはＡの要素以外の要素があるとき、ＡはＢの真部分集合という。）がｋ辺不足成分ではないようなものを、極小ｋ辺不足成分という。
【００５３】
このような定義を用いた下記のアルゴリズム（「Ａｌgｏｒｉｔｈｍ ｋ−ＮＡＬＯＣ」）に対応する処理を実行することで、ｋ−ＮＡ辺連結を満たすサーバ配置問題を解くことができる。
【００５４】
「Ａｌgｏｒｉｔｈｍ ｋ−ＮＡＬＯＣ」
１：ｆｏｒ ｈ＝１，２，…，ｋ ｄｏ
２： ｈ辺連結成分Ｃ（ｈ）＝｛Ｃ（ｈ）１}，Ｃ（ｈ）２，…，Ｃ（ｈ）ｐ（ｈ）｝を求める
３：ｅｎｄ ｆｏｒ
４：極小ｋ辺不足成分の集合｛Ｃ１，Ｃ２，…，Ｃｐ｝を求める
５：｛Ｃ１，Ｃ２，…，Ｃｐ｝の各集合から、任意の点ｖｉ∈Ｃｉを一つずつ選び、
Ｓ＝｛ｖ１，ｖ２，…，ｖｐ｝とする
【００５５】
つまり、極小ｋ辺不足成分から１点ずつ選んで得られた点集合を領域とすることによって、ｋＮＡ辺連結にすることができる。
【００５６】
本例では、「ＮＡ辺連結度」を保証すると共に、「距離」も保証するサーバ配置問題に対して、次の「Ａｌgｏｒｉｔｈｍ ＭＩＮ_ＭＡＸ_Ｄｉｓｔａｎｃｅ」と「Ａｌgｏｒｉｔｈｍ Ａｖｅｒａgｅ_Ｄｉｓｔａｎｃｅ」の２つのヒューリスティックアルゴリズム（近似アルゴリズム）を用いる。
【００５７】
「Ａｌgｏｒｉｔｈｍ ＭＩＮ_ＭＡＸ_Ｄｉｓｔａｎｃｅ」
１：Ａ←φ…（φ：空集合），全てのｗ∈ｖに対してｃ（ｗ）←０
２：極小ｋ辺不足成分Ｓ１，Ｓ２，…，Ｓｐを求める。
３： ｆｏｒ ｉ＝１，２，…，ｐ ｄｏ
４： ｍｉｎｖ∈Ｓｉｍａｘｗ∈Ｖ｛ｃ（ｗ）＋ｄ（ｖ，ｗ）｝となるｖをｖ＊とする
そのような点が複数ある場合、ｍａｘｗ∈Ｖ｛ｃ（ｗ）＋ｄ（ｖ，ｗ）｝の値をとる
ｗの個数が最小となる点を選ぶ．
５： 全てのｗ∈Ｖに対してｃ（ｗ）←ｃ（ｗ）＋ｄ（ｖ＊，ｗ）
６： Ａ←｛ｖ＊｝
７： ｅｎｄ ｆｏｒ
８： Ｉｆ ｓｕｍ＿｛ｉ＝１｝^｛ｒ｝ｍｉｎ＿｛ｐ｝ｄ（ｐ，ｘ）＜＝Ｂ ｆｏｒ ａｎｙ ｘ ｔｈｅｎ Ｏｕｔｐｕｔ Ａ
【００５８】
これは、領域までの距離の和が大きくならないように、各不足成分から点を選んでいっていることになる。尚、８行目の記載は、「Ｉｆ Σｒｉ＝１ｍｉｎｐｄ（ｖ，ｗ）≦Ｂ ｆｏｒ ａｎｙ ｘ ｔｈｅｎ Ｏｕｔｐｕｔ Ａ」と同じ意味である。
【００５９】
「Ａｌgｏｒｉｔｈｍ Ａｖｅｒａgｅ_Ｄｉｓｔａｎｃｅ」
１：Ａ←φ，全てのｗ∈ｖに対してｃ（ｗ）←０
２：極小ｋ辺不足成分Ｓ１，Ｓ２，…，Ｓｐを求める。
３：ｆｏｒ ｉ＝１，２，…，ｐ ｄｏ
４： ｍｉｎｖ∈ＳｉΣｗ∈Ｖ｛ｃ（ｗ）＋ｄ（ｖ，ｗ）｝となるｖをｖ＊とする
そのような点が複数ある場合は、点番号の小さいものを選ぶ．
５： 全てのｗ∈ｖに対してｃ（ｗ）←ｃ（ｗ）＋ｄ（ｖ＊，ｗ）
６： Ａ←｛ｖ＊｝
７：ｅｎｄ ｆｏｒ
８： Ｉｆ ｓｕｍ＿｛ｉ＝１｝^｛ｒ｝ｍｉｎ＿｛ｐ｝ｄ（ｐ，ｘ）＜＝Ｂ ｆｏｒ ａｎｙ ｘ ｔｈｅｎ Ｏｕｔｐｕｔ Ａ
【００６０】
これは、各不足成分から点を選ぶ際、他の全ての点までの距離の和が大きくならないようにしていることになる。尚、８行目の記載は、「Ｉｆ Σｒｉ＝１ｍｉｎｐｄ（ｖ，ｗ）≦Ｂ ｆｏｒ ａｎｙ ｘ ｔｈｅｎ Ｏｕｔｐｕｔ Ａ」と同じ意味である。
【００６１】
以下、図２と図３を用いて、上記２つのアルゴリズム（「Ａｌgｏｒｉｔｈｍ ＭＩＮ_ＭＡＸ_Ｄｉｓｔａｎｃｅ」、「Ａｌgｏｒｉｔｈｍ Ａｖｅｒａgｅ_Ｄｉｓｔａｎｃｅ」）に従ってのサーバ配置個所選択部１０２の処理動作例を説明する。
【００６２】
図２の「Ａｌｇｏｒｉｔｈｍ ＭＩＮ_ＭＡＸ_Ｄｉｓｔａｎｃｅ」では、まず、ステップＳ２０１において、集合Ａを空集合に、コストの総和ｃ（ｗ）を全て０に初期化する。尚、ｃ（ｗ）における「ｗ」は、ある１つのノードを意味し、ｄ（ｖ，ｗ）がノードｖとノードｗとの間の配信に要するコストであり、ｃ（ｗ）は、複数のサーバからノードｗへの配信に要するコストの総和である。
【００６３】
次に、ステップＳ２０２において、要求されるＮＡ辺連結度ｋに対して極小ｋ辺不足成分Ｓ１，Ｓ２，…，Ｓｐを生成する。
【００６４】
ステップＳ２０３においては、全ての極小ｋ辺不足成分に対して、ステップＳ２０４，Ｓ２０５の処理を反復して行う。すなわち、ステップＳ２０４においては、各極小ｋ辺不足成分Ｓｉ（ｉ＝１，２，…，ｐ）に含まれるノードの中から、他の全てのノードに至るコストの最大値が最小となるノードｖ＊を１つ選択し、ステップＳ２０５においては、ステップＳ２０３での処理で選択したノードｖ＊を集合Ａに追加すると共に、ｃ（ｗ）をアップデートする（ｃ（ｗ）←ｃ（ｗ）＋ｄ（ｖ＊，ｗ））。
【００６５】
そして、ステップＳ２０６において、任意のノードｘに対して、距離ｄ（ｐ，ｘ）の短いものからｒ個のサーバまでの距離の総和がＢ以下である場合に、得られた集合Ａを解として出力する。
【００６６】
図３の「Ａｌgｏｒｉｔｈｍ Ａｖｅｒａgｅ_Ｄｉｓｔａｎｃｅ」での処理は、図２にの「Ａｌgｏｒｉｔｈｍ ＭＩＮ_ＭＡＸ_Ｄｉｓｔａｎｃｅ」における処理のステップＳ２０４での処理を、「各極小ｋ辺不足成分Ｓｉ（ｉ＝１，２，…，ｐ）に含まれるノードの中から、他の全てのノードに至るコストの平均値が最小となるノードｖ＊を１つ選択する（ステップＳ２０４’）」処理に代えたものであり、その他の処理は同じである。
【００６７】
次に、図４を用いて、本例のシステムの性能評価結果を説明する。ここでは、ＣＡＩＤＡ （Ｃｏｏｐｅｒａｔｉｖｅ Ａｓｓｏｃｉａｔｉｏｎ ｆｏｒ Ｉｎｔｅｒｎｅｔ Ｄａｔａ Ａｎａｌｙｓｉｓ）において公開されている実際のＩＳＰバックボーンＮＷのグラフ構造を利用して、サーバ配置を決定する。
【００６８】
図４の表４０１の「配置サーバ数」においては、各ＮＷで必要なサーバ数を挙げている。このサーバ数は辺連結度を「２」にするために最低限必要なサーバ数である。表４０１で示す内容から、比較的少数のサーバ設置で要件が満たされることが確認できる。
【００６９】
以上、図１〜図４を用いて説明したように、本例では、ヒューリスティックアルゴリズム（近似アルゴリズム）を設計し、信頼性の評価尺度としてＮＡ辺連結度を用い、サーバ集合との間の距離として各点からサーバまでの距離の和を用いることにより、ネットワークのトポロジが与えられたときに、サーバへの接続性を確保しつつホップ距離が最小となるよう、サーバを最適配置する。
【００７０】
例えば、ネットワークのトポロジとサーバ数の上限Ｓと整数ｋ，Ｂ，ｒが与えられたときに、全てのノードに対して、辺独立な経路でｋ個以上のサーバに到達でき、かつ各ノードからｒ個の最近接サーバまでのホップ距離の総和がＢ以下となるように、Ｓ個以下のサーバを、各ノードからｒ個の最近接サーバまでのホップ距離の総和が最小となるよう、ネットワーク上のノードに配置する。
【００７１】
具体的には、図１に示す構成においｔ、ネットワークにおけるサーバ群の配置個所の選択を、プログラムされたコンピュータのグラフ理論を用いた処理によって行うものであり、トポロジ情報・設計パラメタ入力部１０１により、入力装置を介して入力されるネットワークのトポロジ情報（グラフＧ（Ｖ，Ｅ））とサーバ数の上限値Ｓ、および、ＮＡ辺連結度ｋと、アクセス元のノードに近接するサーバの個数ｒと、ｒ個のサーバまでの距離の和の上限Ｂとを、記憶装置に格納し、サーバ配置箇所選択部１０２により、トポロジ情報・設計パラメタ入力部１０１が記憶装置に格納したデータ（Ｓ，ｋ，Ｂ）を用いた下記のサーバ配置問題の解を求める処理を実行することによって、辺独立な経路でｋ個以上のサーバに到達でき、かつ、ｒ個の近接サーバまでのホップ距離の総和がＢ以下となるノード集合Ａを、Ｓ個以下のサーバを配置するノードとして選択し、サーバ配置箇所出力部１０３により、サーバ配置個所選択部１０２が選択したノード集合Ａをサーバ配置箇所として出力装置に出力する。
【００７２】
「ＮＡ辺連結度と距離を保証するサーバ配置問題」
ＩＮＳＴＡＮＣＥ：Ｇ＝（Ｖ，Ｅ）， 自然数ｋ，Ｂ， サーバ数Ｓ．
ＱＵＥＳＴＩＯＮ：領域グラフ（Ｇ，Ａ）（ただし｜Ａ｜≦Ｓ）におけるＮＡ辺連結度がｋ，近いものからｒ個のサーバまでの距離の和がＢ以下であるようなＡ⊆Ｖは存在するか？
【００７３】
また、サーバ配置個所選択部１０２は、下記のアルゴリズムに従った処理を実行することによって、領域までの距離の和が大きくならないように、各不足成分から点を選んでいく。
【００７４】
「Ａｌgｏｒｉｔｈｍ ＭＩＮ_ＭＡＸ_Ｄｉｓｔａｎｃｅ」
１：Ａ←φ…（φ：空集合），全てのｗ∈ｖに対してｃ（ｗ）←０
２：極小ｋ辺不足成分Ｓ１，Ｓ２，…，Ｓｐを求める。
３： ｆｏｒ ｉ＝１，２，…，ｐ ｄｏ
４： ｍｉｎｖ∈Ｓｉｍａｘｗ∈Ｖ｛ｃ（ｗ）＋ｄ（ｖ，ｗ）｝となるｖをｖ＊とする
そのような点が複数ある場合、ｍａｘｗ∈Ｖ｛ｃ（ｗ）＋ｄ（ｖ，ｗ）｝の値をとる
ｗの個数が最小となる点を選ぶ．
５： 全てのｗ∈Ｖに対してｃ（ｗ）←ｃ（ｗ）＋ｄ（ｖ＊，ｗ）
６： Ａ←｛ｖ＊｝
７： ｅｎｄ ｆｏｒ
８：Ｉｆ Σｒｉ＝１ｍｉｎｐｄ（ｖ，ｗ）≦Ｂ ｆｏｒ ａｎｙ ｘ ｔｈｅｎ Ｏｕｔｐｕｔ Ａ
【００７５】
あるいは、サーバ配置個所選択部１０２は、下記のアルゴリズムに従った処理を実行することによって、各不足成分から点を選ぶ際、他の全ての点までの距離の和が大きくならないよう点を選択する。
【００７６】
「Ａｌgｏｒｉｔｈｍ Ａｖｅｒａgｅ_Ｄｉｓｔａｎｃｅ」
１：Ａ←φ，全てのｗ∈ｖに対してｃ（ｗ）←０
２：極小ｋ辺不足成分Ｓ１，Ｓ２，…，Ｓｐを求める。
３：ｆｏｒ ｉ＝１，２，…，ｐ ｄｏ
４： ｍｉｎｖ∈ＳｉΣｗ∈Ｖ｛ｃ（ｗ）＋ｄ（ｖ，ｗ）｝となるｖをｖ＊とする
そのような点が複数ある場合は、点番号の小さいものを選ぶ．
５： 全てのｗ∈ｖに対してｃ（ｗ）←ｃ（ｗ）＋ｄ（ｖ＊，ｗ）
６： Ａ←｛ｖ＊｝
７：ｅｎｄ ｆｏｒ
８：Ｉｆ Σｒｉ＝１ｍｉｎｐｄ（ｖ，ｗ）≦Ｂ ｆｏｒ ａｎｙ ｘ ｔｈｅｎ Ｏｕｔｐｕｔ Ａ
【００７７】
このことにより、本例によれば、リンク故障時においてもサーバへのアクセスを確保した上で、さらにサーバ集合までの距離を抑えるようなサーバ配置を決定することが可能となり、従来技術の問題点（連結度を保証して信頼性を向上させることと経路長を抑えることの、両方の制約条件を満たすような解を、効率的に求めることができなかった）を解決できる。
【００７８】
尚、本発明は、図１〜図４を用いて説明した例に限定されるものではなく、その要旨を逸脱しない範囲において種々変更可能である。
【符号の説明】
【００７９】
１０１：トポロジ情報・設計パラメタ入力部、１０２：サーバ配置箇所選択部、１０３：サーバ配置箇所出力部、４０１：表。
【特許請求の範囲】
【請求項１】
ネットワークにおけるサーバ群の配置個所の選択を、プログラムされたコンピュータのグラフ理論を用いた処理によって行うサーバ群配置設計システムであって、
プログラムされたコンピュータ処理を実行する手段として、
入力装置を介して入力されるネットワークのトポロジ情報（グラフＧ（Ｖ，Ｅ））とサーバ数の上限値Ｓ、および、ＮＡ辺連結度ｋと、アクセス元のノードに近接するサーバの個数ｒと、ｒ個のサーバまでの距離の和の上限Ｂとを、記憶装置に格納する入力手段と、
該入力手段が記憶装置に格納したデータ（Ｓ，ｋ，Ｂ）を用いた下記のサーバ配置問題の解を求める処理を実行することによって、辺独立な経路でｋ個以上のサーバに到達でき、かつ、ｒ個の近接サーバまでのホップ距離の総和がＢ以下となるノード集合Ａを、Ｓ個以下のサーバを配置するノードとして選択するサーバ配置個所選択手段と、
該サーバ配置個所選択手段が選択したノード集合Ａをサーバ配置箇所として出力装置に出力する出力手段と
を有することを特徴とするサーバ群配置設計システム。
記
「ＮＡ辺連結度と距離を保証するサーバ配置問題」
ＩＮＳＴＡＮＣＥ：Ｇ＝（Ｖ，Ｅ）， 自然数ｋ，Ｂ， サーバ数Ｓ．
ＱＵＥＳＴＩＯＮ：領域グラフ（Ｇ，Ａ）（ただし｜Ａ｜≦Ｓ）におけるＮＡ辺連結度がｋ，近いものからｒ個のサーバまでの距離の和がＢ以下であるようなＡ⊆Ｖは存在するか？
【請求項２】
請求項１に記載のサーバ群配置設計システムであって、
上記サーバ配置個所選択手段は、
下記のアルゴリズムに従った処理を実行することによって、
領域までの距離の和が大きくならないように、各不足成分から点を選んでいくことを特徴とするサーバ群配置設計システム。
記
「Ａｌgｏｒｉｔｈｍ ＭＩＮ_ＭＡＸ_Ｄｉｓｔａｎｃｅ」
１：Ａ←φ…（φ：空集合），全てのｗ∈ｖに対してｃ（ｗ）←０
２：極小ｋ辺不足成分Ｓ１，Ｓ２，…，Ｓｐを求める。
３： ｆｏｒ ｉ＝１，２，…，ｐ ｄｏ
４： ｍｉｎｖ∈Ｓｉｍａｘｗ∈Ｖ｛ｃ（ｗ）＋ｄ（ｖ，ｗ）｝となるｖをｖ＊とする
そのような点が複数ある場合、ｍａｘｗ∈Ｖ｛ｃ（ｗ）＋ｄ（ｖ，ｗ）｝の値をとる
ｗの個数が最小となる点を選ぶ．
５： 全てのｗ∈Ｖに対してｃ（ｗ）←ｃ（ｗ）＋ｄ（ｖ＊，ｗ）
６： Ａ←｛ｖ＊｝
７： ｅｎｄ ｆｏｒ
８：Ｉｆ Σｒｉ＝１ｍｉｎｐｄ（ｖ，ｗ）≦Ｂ ｆｏｒ ａｎｙ ｘ ｔｈｅｎ Ｏｕｔｐｕｔ Ａ
【請求項３】
請求項１に記載のサーバ群配置設計システムであって、
上記サーバ配置個所選択手段は、
下記のアルゴリズムに従った処理を実行することによって、
各不足成分から点を選ぶ際、他の全ての点までの距離の和が大きくならないよう点を選択することを特徴とするサーバ群配置設計システム。
記
「Ａｌgｏｒｉｔｈｍ Ａｖｅｒａgｅ_Ｄｉｓｔａｎｃｅ」
１：Ａ←φ，全てのｗ∈ｖに対してｃ（ｗ）←０
２：極小ｋ辺不足成分Ｓ１，Ｓ２，…，Ｓｐを求める。
３：ｆｏｒ ｉ＝１，２，…，ｐ ｄｏ
４： ｍｉｎｖ∈ＳｉΣｗ∈Ｖ｛ｃ（ｗ）＋ｄ（ｖ，ｗ）｝となるｖをｖ＊とする
そのような点が複数ある場合は、点番号の小さいものを選ぶ．
５： 全てのｗ∈ｖに対してｃ（ｗ）←ｃ（ｗ）＋ｄ（ｖ＊，ｗ）
６： Ａ←｛ｖ＊｝
７：ｅｎｄ ｆｏｒ
８：Ｉｆ Σｒｉ＝１ｍｉｎｐｄ（ｖ，ｗ）≦Ｂ ｆｏｒ ａｎｙ ｘ ｔｈｅｎ Ｏｕｔｐｕｔ Ａ
【請求項４】
ネットワークにおけるサーバ群の配置個所の選択を、プログラムされたコンピュータのグラフ理論を用いた処理によって行うシステムのサーバ群配置設計方法であって、
プログラムされたコンピュータの処理実行手順として、
請求項１から請求項３のいずれかに記載のサーバ群配置設計システムにおける各手段が実行する処理手順を含むことを特徴とするサーバ群配置設計方法。
【請求項５】
コンピュータを、請求項１から請求項３のいずれかに記載のサーバ群配置設計システムにおける各手段として機能させるためのプログラム。
【請求項１】
ネットワークにおけるサーバ群の配置個所の選択を、プログラムされたコンピュータのグラフ理論を用いた処理によって行うサーバ群配置設計システムであって、
プログラムされたコンピュータ処理を実行する手段として、
入力装置を介して入力されるネットワークのトポロジ情報（グラフＧ（Ｖ，Ｅ））とサーバ数の上限値Ｓ、および、ＮＡ辺連結度ｋと、アクセス元のノードに近接するサーバの個数ｒと、ｒ個のサーバまでの距離の和の上限Ｂとを、記憶装置に格納する入力手段と、
該入力手段が記憶装置に格納したデータ（Ｓ，ｋ，Ｂ）を用いた下記のサーバ配置問題の解を求める処理を実行することによって、辺独立な経路でｋ個以上のサーバに到達でき、かつ、ｒ個の近接サーバまでのホップ距離の総和がＢ以下となるノード集合Ａを、Ｓ個以下のサーバを配置するノードとして選択するサーバ配置個所選択手段と、
該サーバ配置個所選択手段が選択したノード集合Ａをサーバ配置箇所として出力装置に出力する出力手段と
を有することを特徴とするサーバ群配置設計システム。
記
「ＮＡ辺連結度と距離を保証するサーバ配置問題」
ＩＮＳＴＡＮＣＥ：Ｇ＝（Ｖ，Ｅ）， 自然数ｋ，Ｂ， サーバ数Ｓ．
ＱＵＥＳＴＩＯＮ：領域グラフ（Ｇ，Ａ）（ただし｜Ａ｜≦Ｓ）におけるＮＡ辺連結度がｋ，近いものからｒ個のサーバまでの距離の和がＢ以下であるようなＡ⊆Ｖは存在するか？
【請求項２】
請求項１に記載のサーバ群配置設計システムであって、
上記サーバ配置個所選択手段は、
下記のアルゴリズムに従った処理を実行することによって、
領域までの距離の和が大きくならないように、各不足成分から点を選んでいくことを特徴とするサーバ群配置設計システム。
記
「Ａｌgｏｒｉｔｈｍ ＭＩＮ_ＭＡＸ_Ｄｉｓｔａｎｃｅ」
１：Ａ←φ…（φ：空集合），全てのｗ∈ｖに対してｃ（ｗ）←０
２：極小ｋ辺不足成分Ｓ１，Ｓ２，…，Ｓｐを求める。
３： ｆｏｒ ｉ＝１，２，…，ｐ ｄｏ
４： ｍｉｎｖ∈Ｓｉｍａｘｗ∈Ｖ｛ｃ（ｗ）＋ｄ（ｖ，ｗ）｝となるｖをｖ＊とする
そのような点が複数ある場合、ｍａｘｗ∈Ｖ｛ｃ（ｗ）＋ｄ（ｖ，ｗ）｝の値をとる
ｗの個数が最小となる点を選ぶ．
５： 全てのｗ∈Ｖに対してｃ（ｗ）←ｃ（ｗ）＋ｄ（ｖ＊，ｗ）
６： Ａ←｛ｖ＊｝
７： ｅｎｄ ｆｏｒ
８：Ｉｆ Σｒｉ＝１ｍｉｎｐｄ（ｖ，ｗ）≦Ｂ ｆｏｒ ａｎｙ ｘ ｔｈｅｎ Ｏｕｔｐｕｔ Ａ
【請求項３】
請求項１に記載のサーバ群配置設計システムであって、
上記サーバ配置個所選択手段は、
下記のアルゴリズムに従った処理を実行することによって、
各不足成分から点を選ぶ際、他の全ての点までの距離の和が大きくならないよう点を選択することを特徴とするサーバ群配置設計システム。
記
「Ａｌgｏｒｉｔｈｍ Ａｖｅｒａgｅ_Ｄｉｓｔａｎｃｅ」
１：Ａ←φ，全てのｗ∈ｖに対してｃ（ｗ）←０
２：極小ｋ辺不足成分Ｓ１，Ｓ２，…，Ｓｐを求める。
３：ｆｏｒ ｉ＝１，２，…，ｐ ｄｏ
４： ｍｉｎｖ∈ＳｉΣｗ∈Ｖ｛ｃ（ｗ）＋ｄ（ｖ，ｗ）｝となるｖをｖ＊とする
そのような点が複数ある場合は、点番号の小さいものを選ぶ．
５： 全てのｗ∈ｖに対してｃ（ｗ）←ｃ（ｗ）＋ｄ（ｖ＊，ｗ）
６： Ａ←｛ｖ＊｝
７：ｅｎｄ ｆｏｒ
８：Ｉｆ Σｒｉ＝１ｍｉｎｐｄ（ｖ，ｗ）≦Ｂ ｆｏｒ ａｎｙ ｘ ｔｈｅｎ Ｏｕｔｐｕｔ Ａ
【請求項４】
ネットワークにおけるサーバ群の配置個所の選択を、プログラムされたコンピュータのグラフ理論を用いた処理によって行うシステムのサーバ群配置設計方法であって、
プログラムされたコンピュータの処理実行手順として、
請求項１から請求項３のいずれかに記載のサーバ群配置設計システムにおける各手段が実行する処理手順を含むことを特徴とするサーバ群配置設計方法。
【請求項５】
コンピュータを、請求項１から請求項３のいずれかに記載のサーバ群配置設計システムにおける各手段として機能させるためのプログラム。
【図１】
【図２】
【図３】
【図４】
【図２】
【図３】
【図４】
【公開番号】特開２０１０−１９９７３６（Ｐ２０１０−１９９７３６Ａ）
【公開日】平成２２年９月９日（２０１０．９．９）
【国際特許分類】
【出願番号】特願２００９−３９７１６（Ｐ２００９−３９７１６）
【出願日】平成２１年２月２３日（２００９．２．２３）
【出願人】（０００００４２２６）日本電信電話株式会社 (13,992)
【出願人】（５０３０９２１８０）学校法人関西学院 (71)
【Ｆターム（参考）】
【公開日】平成２２年９月９日（２０１０．９．９）
【国際特許分類】
【出願日】平成２１年２月２３日（２００９．２．２３）
【出願人】（０００００４２２６）日本電信電話株式会社 (13,992)
【出願人】（５０３０９２１８０）学校法人関西学院 (71)
【Ｆターム（参考）】
[ Back to top ]