(57)【特許請求の範囲】
【請求項１】
配信サーバと該配信サーバからのデータを受信する複数のサーバと、前記サーバを利用する複数のクライアントとを含むネットワーク構成におけるデータ配信システムにおいて、
前記配信サーバに、予め定められた前記サーバと前記クライアントとの間の評価式に基づき評価値を算出し、該評価値の値によりデータを送信する前記サーバの順序を決定する手段を備え、
前記順序決定手段に、
ｎ個の前記サーバ群の中からｘ個（ｘは１からｎの整数）のサーバの組み合わせ（ｎＣｘ）を選択し、選択した前記組み合わせを構成する各々の組に対して、前記組に属する前記サーバと該サーバに接続される前記クライアントとの間の評価値を前記評価式に基づいて算出し、算出した各々の組の前記評価値を予め定められた評価法に基づき評価して最も評価の高い評価値を選び、選ばれた前記評価値をｘ個のサーバに対する理想解として求め、前記理想解をｘ＝１〜ｎについて順次求めてｎ個の前記理想解の集合を前記ネットワーク全体の評価値として算出、記憶する理想解算出手段と、
前記ｎ個のサーバ群の順列集合（ｎＰｎ）を作成する順列集合作成手段と、
前記順列集合作成手段で作成された各々の順列について、順次１からｎまで増加するｙ個のサーバを選択し、前記ｙ個のサーバと該サーバに接続されるクライアントとの間の評価値を前記評価式に基づいて算出し、該評価値から前記理想解算出手段で求めたｙ個のサーバに対する前記理想解を減じて差分を演算し、該差分をｙ＝１〜ｎについて加算して一の順列に対する差分合計を算出し、該差分合計を全ての順列に対して求め、前記差分合計の最も小さい順列を選択する選択順序決定手段と、を少なくとも有することを特徴とするデータ配信システム。
【請求項２】
配信サーバと該配信サーバからのデータを受信する複数のサーバと、前記サーバを利用する複数のクライアントとを含むネットワーク構成におけるデータ配信システムにおいて、
前記配信サーバに、予め定められた前記サーバと前記クライアントとの間の評価式に基づき評価値を算出し、該評価値の値によりデータを送信する前記サーバの順序を決定する手段を備え、
前記順序決定手段に、
ｎ個の前記サーバ群の各々について、前記サーバと該サーバに接続されるクライアントとの間の評価値、並びに該サーバが配置される以前に、既にサーバとして配置されているサーバ群とそれらサーバ群に接続されるクライアントとの間の評価値を合算した評価式に基づいて算出する個別評価値算出手段と、
ｎ個のサーバ群の全てについて評価値を求め、前記評価値の集合を算出する全評価値算出手段と、
前記全評価値算出手段で作成された前記評価値の集合を予め定められた評価法に基づき評価して最も評価の高い評価値に対応するサーバを選択し、前記選択されたサーバを前記サーバ群の中から除外する選択順序決定手段と、
全てのサーバの選択順序が確定したか否かを判断する判断手段と、を少なくとも有することを特徴とするデータ配信システム。
【請求項３】
前記順序決定手段に、請求項１記載の手段及び請求項２記載の手段の双方を備えたことを特徴とするデータ配信システム。
【請求項４】
ｎ個の前記サーバ群のうち、ｚ個（ｚは２からｎ−２の間の整数）のサーバに対して請求項１記載の手段により前記サーバの選択順序を決定し、
残りのサーバに対しては請求項２記載の手段により前記サーバの選択順序を決定することを特徴とする請求項３記載のデータ配信システム。
【請求項５】
前記サーバの座標を（Ｓｘ、Ｓｙ）とし、前記クライアントの座標を（Ｃｘ、Ｃｙ）とした場合に、前記評価式が、｜Ｓｘ−Ｃｘ｜＋｜Ｓｙ−Ｃｙ｜で表されることを特徴とする請求項１乃至４のいずれか一に記載のデータ配信システム。
【請求項６】
配信サーバと該配信サーバからのデータを受信する複数のサーバと、前記サーバを利用する複数のクライアントとを含むネットワーク構成におけるデータ配信方法において、
前記配信サーバにおいて、予め定められた前記サーバと前記クライアントとの間の評価式に基づき評価値を算出し、該評価値の値によりデータを送信する前記サーバの順序を決定する方法として、
ｎ個の前記サーバ群の中からｘ個（ｘは１からｎの整数）のサーバの組み合わせ（ｎＣｘ）を選択し、選択した前記組み合わせを構成する各々の組に対して、前記組に属する前記サーバと該サーバに接続される前記クライアントとの間の評価値を前記評価式に基づいて算出し、算出した各々の組の前記評価値を予め定められた評価法に基づき評価して最も評価の高い評価値を選び、選ばれた前記評価値をｘ個のサーバに対する理想解として求め、前記理想解をｘ＝１〜ｎについて順次求めてｎ個の前記理想解の集合を前記ネットワーク全体の評価値として算出、記憶する理想解算出ステップと、
前記ｎ個のサーバ群の順列集合（ｎＰｎ）を作成する順列集合作成ステップと、
前記順列集合作成ステップにより作成した各々の順列について、順次１からｎまで増加するｙ個のサーバを選択し、前記ｙ個のサーバと該サーバに接続されるクライアントとの間の評価値を前記評価式に基づいて算出し、該評価値から前記理想解算出手段で求めたｙ個のサーバに対する前記理想解を減じて差分を演算し、該差分をｙ＝１〜ｎについて加算して一の順列に対する差分合計を算出し、該差分合計を全ての順列に対して求め、前記差分合計の最も小さい順列を選択する選択順序決定ステップと、を少なくとも有することを特徴とするデータ配信方法。
【請求項７】
配信サーバと該配信サーバからのデータを受信する複数のサーバと、前記サーバを利用する複数のクライアントとを含むネットワーク構成におけるデータ配信方法において、
前記配信サーバにおいて、予め定められた前記サーバと前記クライアントとの間の評価式に基づき評価値を算出し、該評価値の値によりデータを送信する前記サーバの順序を決定する方法として、
ｎ個の前記サーバ群の各々について、前記サーバと該サーバに接続されるクライアントとの間の評価値、並びに該サーバが配置される以前に、既にサーバとして配置されているサーバ群とそれらサーバ群に接続されるクライアントとの間の評価値を合算した評価式に基づいて算出する個別評価値算出ステップと、
ｎ個のサーバ群の全てについて評価値を求め、前記評価値の集合を算出する全評価値算出ステップと、
前記全評価値算出ステップで作成された前記評価値の集合を予め定められた評価法に基づき評価して最も評価の高い評価値に対応するサーバを選択し、前記選択されたサーバを前記サーバの中から除外する選択順序決定ステップと、
全てのサーバの選択順序が確定したか否かを判断するステップと、を少なくとも有することを特徴とするデータ配信方法。
【請求項８】
前記サーバの選択順序を決定する方法として、請求項６記載のステップ及び請求項７記載のステップの双方を備えたことを特徴とするデータ配信方法。
【請求項９】
ｎ個の前記サーバ群のうち、ｚ個（ｚは２からｎ−２の間の整数）のサーバに対して請求項６記載のステップにより前記サーバの選択順序を決定し、
残りのサーバに対しては請求項７記載のステップにより前記サーバの選択順序を決定することを特徴とする請求項８記載のデータ配信方法。
【請求項１０】
前記サーバの座標を（Ｓｘ、Ｓｙ）とし、前記クライアントの座標を（Ｃｘ、Ｃｙ）とした場合に、前記評価式が、｜Ｓｘ−Ｃｘ｜＋｜Ｓｙ−Ｃｙ｜で表されることを特徴とする請求項６乃至９のいずれか一に記載のデータ配信方法。
【請求項１１】
請求項６乃至１０のいずれか一に記載の方法をコンピュータで実行するためのプログラムを記録した記録媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、ネットワーク上に設置された複数のサーバに対してデータを配信するデータ配信システム及びデータ配信方法に関する。
【０００２】
【従来の技術】
ネットワーク上に設置された複数のサーバに対して、様々な種類のデータを配信する従来のデータ配信システム及びデータ配信方法について、図９及び図１０を用いて説明する。図９は、従来のデータ配信システムの構成を示す図であり、図１０は、データの配信方法を示すフローチャート図である。図９に示すように、従来のデータ配信システム１１は、配信サーバ１２と、配信サーバ１２のデータの配信方法を制御する配信制御手段１３と、配信サーバ１２からのデータを受信する複数のサーバ１４（図では１４ａ、１４ｂ、１４ｃ、１４ｄ、１４ｅの５つのサーバ）と、サーバに接続される複数のクライアント１５（図では１５ａ、１５ｂ、１５ｃの３つのクライアント）とから構成されている。
【０００３】
このような構成の従来のデータ配信システム１１におけるデータ配信方法について図１０を参照して説明すると、まず、Ｓ６０１において、配信サーバ１２は通信網内に存在するサーバ１４のリストを配信制御手段１３から獲得する。次に、Ｓ６０２において、配信サーバ１２はＳ６０１で獲得したリストに掲載されているサーバ１４全体に対してデータを配信する。なお、図９のサーバ１４（１４ａ〜１４ｅ）がデータをキャッシュしておくサーバであるが、これらのサーバ１４はＷＷＷ(World Wide Web)のコンテンツデータやライブ放送などのストリーミングメディアデータを格納することが可能である。
【０００４】
【発明が解決しようとする課題】
しかしながら、このようなデータ配信システム１１において、従来は人手でサーバ１４の配置を決定することが多く、一度サーバ１４が設置されるとその位置を変更することは少なく、また、ユーザの需要に関係なく、数多くのサーバ１４を設置するために配信先が多くなりすぎてしまい、ネットワークのトラヒックを増大させたり、サーバ１４にデータをキャッシュしておくためのコストが余分にかかってしまうという問題がある。
【０００５】
本発明は、上記問題点に鑑みてなされたものであって、その主たる目的は、データ配信の初期段階ではサーバ数が少なく、状況に応じてデータが配信されるサーバ数が増加するようなネットワーク構成において、常にクライアントからのアクセスが公平となるように、データの配信を制御することができるデータ配信システム及びデータ配信方法を提供することにある。
【０００６】
【問題を解決するための手段】
上記目的を達成するため、本発明は、配信サーバと該配信サーバからのデータを受信する複数のサーバと、前記サーバを利用する複数のクライアントとを含むネットワーク構成におけるデータ配信システムにおいて、前記配信サーバに、予め定められた前記サーバと前記クライアントとの間の評価式に基づき評価値を算出し、該評価値の値によりデータを送信する前記サーバの順序を決定する手段を備え、前記順序決定手段に、ｎ個の前記サーバ群の中からｘ個（ｘは１からｎの整数）のサーバの組み合わせ（ｎＣｘ）を選択し、選択した前記組み合わせを構成する各々の組に対して、前記組に属する前記サーバと該サーバに接続される前記クライアントとの間の評価値を前記評価式に基づいて算出し、算出した各々の組の前記評価値を予め定められた評価法に基づき評価して最も評価の高い評価値を選び、選ばれた前記評価値をｘ個のサーバに対する理想解として求め、前記理想解をｘ＝１〜ｎについて順次求めてｎ個の前記理想解の集合を前記ネットワーク全体の評価値として算出、記憶する理想解算出手段と、前記ｎ個のサーバ群の順列集合（ｎＰｎ）を作成する順列集合作成手段と、前記順列集合作成手段で作成された各々の順列について、順次１からｎまで増加するｙ個のサーバを選択し、前記ｙ個のサーバと該サーバに接続されるクライアントとの間の評価値を前記評価式に基づいて算出し、該評価値から前記理想解算出手段で求めたｙ個のサーバに対する前記理想解を減じて差分を演算し、該差分をｙ＝１〜ｎについて加算して一の順列に対する差分合計を算出し、該差分合計を全ての順列に対して求め、前記差分合計の最も小さい順列を選択する選択順序決定手段と、を少なくとも有するものである。
【０００８】
また、本発明は、配信サーバと該配信サーバからのデータを受信する複数のサーバと、前記サーバを利用する複数のクライアントとを含むネットワーク構成におけるデータ配信システムにおいて、前記配信サーバに、予め定められた前記サーバと前記クライアントとの間の評価式に基づき評価値を算出し、該評価値の値によりデータを送信する前記サーバの順序を決定する手段を備え、前記順序決定手段に、ｎ個の前記サーバ群の各々について、前記サーバと該サーバに接続されるクライアントとの間の評価値、並びに該サーバが配置される以前に、既にサーバとして配置されているサーバ群とそれらサーバ群に接続されるクライアントとの間の評価値を合算した評価式に基づいて算出する個別評価値算出手段と、ｎ個のサーバ群の全てについて評価値を求め、前記評価値の集合を算出する全評価値算出手段と、前記全評価値算出手段で作成された前記評価値の集合を予め定められた評価法に基づき評価して最も評価の高い評価値に対応するサーバを選択し、前記選択されたサーバを前記サーバ群の中から除外する選択順序決定手段と、全てのサーバの選択順序が確定したか否かを判断する判断手段と、を少なくとも有するものである。
【０００９】
また、本発明のデータ配信方法は、配信サーバと該配信サーバからのデータを受信する複数のサーバと、前記サーバを利用する複数のクライアントとを含むネットワーク構成におけるデータ配信方法において、前記配信サーバにおいて、予め定められた前記サーバと前記クライアントとの間の評価式に基づき評価値を算出し、該評価値の値によりデータを送信する前記サーバの順序を決定する方法として、ｎ個の前記サーバ群の中からｘ個（ｘは１からｎの整数）のサーバの組み合わせ（ｎＣｘ）を選択し、選択した前記組み合わせを構成する各々の組に対して、前記組に属する前記サーバと該サーバに接続される前記クライアントとの間の評価値を前記評価式に基づいて算出し、算出した各々の組の前記評価値を予め定められた評価法に基づき評価して最も評価の高い評価値を選び、選ばれた前記評価値をｘ個のサーバに対する理想解として求め、前記理想解をｘ＝１〜ｎについて順次求めてｎ個の前記理想解の集合を前記ネットワーク全体の評価値として算出、記憶する理想解算出ステップと、前記ｎ個のサーバ群の順列集合（ｎＰｎ）を作成する順列集合作成ステップと、前記順列集合作成ステップにより作成した各々の順列について、順次１からｎまで増加するｙ個のサーバを選択し、前記ｙ個のサーバと該サーバに接続されるクライアントとの間の評価値を前記評価式に基づいて算出し、該評価値から前記理想解算出手段で求めたｙ個のサーバに対する前記理想解を減じて差分を演算し、該差分をｙ＝１〜ｎについて加算して一の順列に対する差分合計を算出し、該差分合計を全ての順列に対して求め、前記差分合計の最も小さい順列を選択する選択順序決定ステップと、を少なくとも有する構成とするものである。
【００１１】
また、本発明のデータ配信方法は、配信サーバと該配信サーバからのデータを受信する複数のサーバと、前記サーバを利用する複数のクライアントとを含むネットワーク構成におけるデータ配信方法において、前記配信サーバにおいて、予め定められた前記サーバと前記クライアントとの間の評価式に基づき評価値を算出し、該評価値の値によりデータを送信する前記サーバの順序を決定する方法として、ｎ個の前記サーバ群の各々について、前記サーバと該サーバに接続されるクライアントとの間の評価値、並びに該サーバが配置される以前に、既にサーバとして配置されているサーバ群とそれらサーバ群に接続されるクライアントとの間の評価値を合算した評価式に基づいて算出する個別評価値算出ステップと、ｎ個のサーバ群の全てについて評価値を求め、前記評価値の集合を算出する全評価値算出ステップと、前記全評価値算出ステップで作成された前記評価値の集合を予め定められた評価法に基づき評価して最も評価の高い評価値に対応するサーバを選択し、前記選択されたサーバを前記サーバ群の中から除外する選択順序決定ステップと、全てのサーバの選択順序が確定したか否かを判断するステップと、を少なくとも有するものである。
【００１２】
更に、本発明においては、前記サーバの座標を（Ｓｘ、Ｓｙ）とし、前記クライアントの座標を（Ｃｘ、Ｃｙ）とした場合に、前記評価式が、｜Ｓｘ−Ｃｘ｜＋｜Ｓｙ−Ｃｙ｜で表されることが好ましい。
【００１３】
【発明の実施の形態】
本発明の一実施の形態に係るデータ配信システム及びデータ配信方法について、図１乃至図３を参照して説明する。図１は、本実施の形態に係るデータ配信システムの構成を示す図である。また、図２及び図３は、データ配信システムの動作を示すフローチャート図であり、図２は初期状態におけるデータ配信方法を、図３はサーバを増設した場合のデータ配信方法を示している。
【００１４】
図１に示すように、本実施の形態のデータ配信システム１は、配信サーバ２と、後述する実施例で詳細に示す所定のサーバ選択順序決定手段を備えた配信制御手段３と、配信サーバ２からのデータを受信する複数のサーバ４（図では４ａ、４ｂ、４ｃ、４ｄ、４ｅの５つのサーバ）と、サーバに接続される複数のクライアント５（図では５ａ、５ｂ、５ｃの３つのクライアント）とから構成されている。
【００１５】
なお、コンテンツとして様々な種類のデータを配信するデータ配信サービスにおいては、実行環境などにより、従来のサーバ（図９のサーバ１４ａ〜１４ｅ）のようにすべてのデータを受け入れられない場合があり、図１のサーバ４ｄはデータの受け入れができないサーバであり、サーバ４ａ、４ｂ、４ｃ、４ｅがデータ受信可能なサーバである。
【００１６】
この様な構成のデータ配信システム１の動作について説明する。図２に示すように、Ｓ１０１において、配信サーバ２は、所定の選択順序決定手段を備えた配信制御手段３からデータの受信が可能なサーバ４の順序付きリストを獲得する。そしてＳ１０２において、獲得したリストにある初期サーバ配置個数であるＮ個のサーバ４に対してデータを配信する。なお、図１では、Ｎ＝２の場合を例示しており、サーバ４ａとサーバ４ｅに対してデータの配信を行っている。
【００１７】
次に、現在のサーバ配信個数では負荷が大きく、新たにサーバ４を１個追加したい場合の動作について説明する。この場合、図３のフローチャート図で示される処理を行う。すなわち、Ｓ２０１において、図２のＳ１０１で獲得したリスト上で、既に獲得したサーバ４ａ、４ｅの次に位置づけされたサーバを獲得する。そして、Ｓ２０２において、Ｓ２０１で獲得したサーバに対してデータを配信する。
【００１８】
このように、全てのサーバに対して無条件にデータを配信するのではなく、配信制御手段３に設けたサーバ選択順序決定手段により、常にクライアント５からのアクセスが公平となるように、データの受信が可能なサーバ群からサーバ４を選択、配置することにより、ネットワークの負荷を分散させることができ、トラヒックの増大を防ぎ、サーバ４がデータをキャッシュする負担を軽減することができる。
【００１９】
なお、ユーザの需要が不明な状況で多数のサーバ４にデータを配置するのは、ネットワークのトラヒックを増大させるなどの点でコストがかかるため、初期のデータ配信段階では、データが置かれるサーバ４の数は少ないものとなる可能性が高い。そのため、サーバ数の少ない初期段階でのサーバ配置は、需要が不明なユーザを対象とするとすることができるように、可能な限り公平なアクセスを実現する必要がある。
【００２０】
また、ユーザの需要の増加などに対応し、未配送のサーバに対して新たにデータを配送することにより、負荷分散することが可能となるが、その際、既にあるサーバ４との配置などを考慮し、クライアント５にとって有利な配置となるように配信するサーバ４を選択することが望ましい。
【００２１】
【実施例】
上記した本発明の一実施の形態に係るデータ配信システムにおけるサーバ選択順序決定手段についてさらに詳細に説明すべく、本発明の実施例について図面を参照して具体的に説明する。
【００２２】
［実施例１］
まず、本発明の第１の実施例に係るデータ配信システム及びデータ配信方法について、図４を参照して説明する。図４は、第１の実施例に係るデータ配信システムにおけるサーバ選択順序決定方法について説明するためのフローチャート図である。本実施例のデータ配信システムは、配信制御手段３に設けるサーバ選択順序決定手段として、理想解を算出する手段（Ｓ３０１）と、サーバ群から順列集合を作成する手段（Ｓ３０２）と、Ｓ３０１及びＳ３０２とで求められた結果を比較し、サーバの選択順序を決定する手段（Ｓ３０３）とを含み構成されている。
【００２３】
このような構成のデータ配信システムの動作について説明する。第１の実施例のデータ配信方法は、クライアント５とサーバ４との関係が平均的に公平となるようにすることを目的とし、選択順序全体を考慮して、その順序を決定するものである。
【００２４】
まず、入力情報がＳ３０１の理想解算出手段へと渡される。この入力情報とは、コンテンツ受信可能なサーバ群に関する情報、クライアント５に関する情報、およびサーバ４とクライアント５に関する評価式等が含まれる。この評価式には、様々な式を採用することが可能であり、簡単な２乗距離などを採用することも可能であり、ネットワークの負荷を考慮した評価式を採用することも可能である。
【００２５】
なお、以下の説明に際して、入力情報であるサーバ群をＳ、個々のサーバをＳ(i):(i=,…,n)、クライアントの集合をＣ、個々のクライアントをＣ(j)：(j=1,…,m)とする。また、サーバの位置に関してはメッシュで与えられるものとし、評価式は次式で表されるものとする。
【００２６】
0003885865.tif 000002
【００２７】
まず、Ｓ３０１の理想解算出手段を用いて、ネットワークシステム上に展開されているサーバのすべてに対しての理想解を求める。ここでの理想解とは、サーバを１個選択した場合、２個選択した場合、…、ｎ個選択した場合、と選択個数を増加させた場合のそれぞれの理想解を指し、それぞれの理想解は、クライアントとサーバとの間の評価式Ｆ(Ｓ(i),Ｃ(j))を利用することで求められる。
【００２８】
この評価式を用いて一つのサーバを評価する場合について説明すると、この一つのサーバに接続される全クライアントに対して、上記評価式を用いてサーバとのスコアをそれぞれ求め、それらのスコアを合計したものが、そのサーバに対する評価値となり、次式で与えられる。
【００２９】
0003885865.tif 000003
【００３０】
また、サーバが複数ある場合は、クライアントは最も近傍にあるサーバへアクセスするものとして、そのサーバに対しての評価をスコアとして付けることとし、そのスコアを合計したものが複数のサーバが展開している場合におけるノード配置の評価値Ｅとなる。その評価値Ｅは、次式によって与えられる。
【００３１】
0003885865.tif 000004
【００３２】
したがって、理想解はサーバが１個、２個…の場合のそれぞれについて上記の評価方法により、評価値が最も評価されるサーバ配置の組み合わせとなる。このＳ３０１によって作成されたサーバ個数ごとの評価値を理想解Ideal(i):(i=1,…,n)とする。この理想解を用いて、実際のサーバ配置を求める。
【００３３】
次に、Ｓ３０２の順列集合作成手段において、サーバ群Ｓからの順列集合を作成する。データ受信可能なサーバ群Ｓがあり、このサーバ群からサーバを選択、配置する場合、サーバ群Ｓからサーバを取り出す順序はサーバ群Ｓの順列の数（ｎＰｎ）だけ存在するため、それらの順列集合を作成する。作成された順列集合のある一つの集合をＰ(i)（ｉは順列における先頭からの順番を示す）とする。
【００３４】
そして、Ｓ３０３の選択順序決定手段において、Ｓ３０１、Ｓ３０２で求めた理想解、順列集合を利用して、サーバの選択順序を決定する。具体的には、ある順列集合Ｐ(i)に対し、先頭のサーバを取り出した場合、ネットワークシステムに存在するサーバは一つであるため、まずＰ(1)のサーバ配置に対する評価値Ｅ(1)を求め、次に、サーバが１個の場合の理想解Ideal(1)の評価値との差分diff(1)を求める。
【００３５】
次に、Ｐ(1)、Ｐ(2)の２つのサーバが選択されたとして、その２つに対する評価値Ｅ(2)を求め、Ideal(2)との差分diff(2)を求める。そして、この処理をサーバ群の個数であるｎ回だけ繰り返し、diff(i):(i=1,…,n)を求める。この差分の和をＤとするとＤは次式で表される。
【００３６】
0003885865.tif 000005
【００３７】
この処理をＳ３０２で生成した順列集合すべてに対して求め、それぞれの順列集合に対して理想解との差分の和Ｄを求める。そして、それぞれ求められたＤの中で、値が最小のＤを求める。最小の値を与えるＤの順列に従ったサーバの選択順序が、理想解の評価値に平均的に近い組み合わせと考えることができる。このように、本実施例のデータ配信システム及びデータ配信方法によれば、サーバが増加した場合であっても、クライアントからのアクセスの公平性を維持することが可能となる。
【００３８】
［実施例２］
次に、本発明の第２の実施例に係るデータ配信システム及びデータ配信方法について、図５を参照して説明する。図５は、第２の実施例に係るデータ配信システムにおけるサーバ選択順序決定方法について説明するフローチャート図である。本実施例のデータ配信システムは、配信制御手段３に設けるサーバ選択順序決定手段として、サーバ４とクライアント５との間の評価値を算出する手段（Ｓ４０１）と、サーバ群に含まれる全サーバに対して同様の処理を行う手段（Ｓ４０２）と、Ｓ４０２で求められる評価値を比較し、サーバの選択順序を決定する手段（Ｓ４０３）と、全サーバに対して順序が決定されたかを判断する手段（Ｓ４０４）とを含み構成されている。
【００３９】
本実施例の方法は、前記した第１の実施例の方法とは異なり、順序全体を考慮してその順序を決定することはなく、その時点での最良の配置を行うことを目的として、逐次的にその順序を決定することを特徴としている。
【００４０】
ここで、前記した第１の実施例と同等に、入力情報としては、サーバ群の集合に関する情報、クライアントに関する情報、サーバとクライアント間の評価を示す評価関数などが既に与えられているとする。入力情報であるサーバ群をＳ、個々のサーバをＳ(i):(i=1,…,n)とし、クライアントの集合をＣ、その集合に含まれる個々のクライアントをＣ(j):(j=1,…m)とする。また評価式は、Ｓ(i)とＣ(j)とに関する関数Ｆ(Ｓ(i),Ｃ(j))によって与えられるものとする。
【００４１】
まず、Ｓ４０１の個別評価値算出手段を用いて、ある一つのサーバＳ(i)に対する全クライアントからの評価式を求める。その評価値Ｅ(i)は、次式で与えられる。
【００４２】
0003885865.tif 000006
【００４３】
次に、Ｓ４０２の全評価値算出手段を用いて、サーバ群Ｓに存在するすべてのサーバに対して同様の処理を行い、それぞれの評価値を求める。この際、既に複数のサーバが配置されている場合の評価値Ｅは、次式によって与えられる。
【００４４】
0003885865.tif 000007
【００４５】
これにより評価値Ｅ(i):(i=1,…,n)がそれぞれ求められる。そして、Ｓ４０３の選択順序決定手段により、予め定められた評価手法に基づき、Ｅ(i):(i=1,…,n)中で最も評価の高いものを特定する。この最も評価の高いＥ(i)がその時点での最適な選択ということになり、そのサーバを次に選択すべきサーバとして特定し、サーバ群Ｓの中からこの特定されたサーバを除外する。
【００４６】
そして、Ｓ４０４の判断手段により、サーバ群Ｓに含まれる全サーバの選択順序が決まったかどうかを判断し、決定していない場合は、Ｓ４０１からＳ４０３までの処理を繰り返し行う。全選択順序が決定すればその結果を出力することとなる。これをサーバ群Ｓに含まれる全サーバの選択順序が決定するまで行うことにより、サーバの増加が行われても、クライアントからのアクセスの公平性を維持するサーバ配置を実現することが可能となる。
【００４７】
［実施例３］
次に、本発明の第３の実施例に係るデータ配信システム及びデータ配信方法について、図６を参照して説明する。図６は、第３の実施例に係るデータ配信方法におけるサーバ選択順序決定方法について説明するフローチャート図である。本実施例の方法は、前記した第１及び第２の実施例におけるサーバ選択順序決定方法を組み合わせ、よりクライアントの公平性を向上させたものである。
【００４８】
図６に示すように、本実施例のデータ配信システムは、配信制御手段３に設けるサーバ選択順序決定手段として、指定された個数までの理想解を求める手段（Ｓ５０１）と、サーバ群から指定された個数の順列集合を作成する手段（Ｓ５０２）と、Ｓ５０１とＳ５０２とで求められた結果を比較し、指定された個数だけのサーバ選択順序を決定する手段（Ｓ５０３）と、指定個数以降のサーバ、クライアント間の評価値を求める手段（Ｓ５０４）と、サーバ群Ｓに対して評価値を求める手段（Ｓ５０５）と、Ｓ５０５の結果を比較し、サーバ選択順序を決定する手段（Ｓ５０６）と、全サーバの順序が決定したか否かを判断する手段（Ｓ５０７）とを含み構成されている。
【００４９】
このような構成のデータ配信システムのサーバ選択順序決定方法について説明する。本実施例のサーバ順序決定方法では、第１の実施例に記載したサーバ選択順序決定手段（Ｓ３０１〜Ｓ３０３）を図６のＳ５０１、Ｓ５０２、Ｓ５０３で実現し、また、第２の実施例に記載したサーバ選択順序決定手段（Ｓ４０１〜Ｓ４０４）を図６のＳ５０４、Ｓ５０５、Ｓ５０６、Ｓ５０７で実現している。
【００５０】
なお、本実施例においても、入力情報はすでに与えられているものとする。入力情報としては、サーバ群の集合に関する情報、クライアントに関する情報、サーバとクライアント間の評価を示す評価関数、第１の順序決定手段で決定するサーバ順序の個数Ｎなどが与えられる。入力情報であるサーバ群をＳとし、個々のサーバをＳ(i)：(i=1,…,n)、クライアントの集合をＣ、その集合に含まれる個々のクライアントをＣ(j)：(j=1,…m)とする。また評価式は、Ｓ(i)とＣ(j)とに関する関数Ｆ(Ｓ(i),Ｃ(j))によって与えられるものとする。
【００５１】
まず、複数のサーバがある配置にあるときの評価値Ｅは、次式によって与えられる。なお、サーバの位置に関してはメッシュで与えられるものとする。
【００５２】
0003885865.tif 000008
【００５３】
次に、Ｓ５０１の理想解算出手段により、１個からＮ個までのサーバ配置の理想解をそれぞれ求める。その方法は、複数のサーバが展開している場合におけるノード配置の評価値Ｅを利用し、サーバが１個、…Ｎ個の場合のそれぞれについて上記の評価方法により、評価値が最も評価されるサーバ配置の組み合わせを求めることにより行う。それらの理想解をIdeal(i):(i=1,…,N)とする。
【００５４】
次に、Ｓ５０２の順列集合作成手段により、サーバ群ＳからＮ個を選択する順列集合を作成する。本実施例ではｎＰＮ個の順列集合が作成される。
【００５５】
次に、Ｓ５０３の選択順序決定手段により、Ｓ５０１で求めた理想解とＳ５０２で求めた順列集合との比較を行う。Ｓ５０２で求めた順列集合のある組み合わせをＰ(i)（ｉは順列における先頭からの順番を示すi=1,…,N）とする。まず、Ｐ(1)のサーバ配置に対する評価値Ｅ(1)を求め、次に、サーバが１個の場合の理想解Ideal(1)の評価値との差分diff(1)を求める。
【００５６】
次に、Ｐ(1)、Ｐ(2)の２つのサーバが選択されたとして、その２つに対する評価値Ｅ(2)を求め、Ideal(2)との差分diff(2)を求める。この処理をサーバ群の個数であるＮ回だけ繰り返し、diff(i):(i=1,…,N)を求める。この差分の和をＤとすると、Ｄは次式で表される。
【００５７】
0003885865.tif 000009
【００５８】
この処理をＳ５０２で生成した順列集合のすべてに対して求め、それぞれの順列集合に対して理想解との差分の和Ｄを求める。そして、すべての順列集合に対して求められた理想解との差分の和が最も小さい値を取る集合が、Ｎ個までのサーバに関して最適な順序となる。
【００５９】
次に、Ｎ個以降のサーバ順序を決定するために、Ｓ５０１、Ｓ５０２、Ｓ５０３で求めた結果がＳ５０４へと渡される。Ｓ５０４の個別評価値算出手段、Ｓ５０５の全評価値算出手段では、サーバ群Ｓにおいて未選択のサーバに対してそれぞれの評価値を求める。評価値の求め方は、前記した第２の実施例の選択順序決定手段と同様である。そして、Ｓ５０６の選択順序決定手段により、Ｓ５０４、Ｓ５０５において求めた評価値の中から最も評価の高いものを選択し、次に選択すべきサーバとして特定する。Ｓ５０７において、全サーバについて選択順序が決定したかを判断し、決定していなければＳ５０４、Ｓ５０５、Ｓ５０６の処理を繰り返し、サーバ群Ｓに含まれる全サーバに関して、選択順序を決定する。
【００６０】
このような、評価方法の異なる第１及び第２の実施例に記載した選択順序決定手段を組み合わせることにより、より柔軟な選択順序決定システムを構成することが可能となる。
【００６１】
［実施例４］
次に、本発明の第４の実施例に係るデータ配信方法及びデータ配信の例について、図７及び図８を参照して説明する。図７及び図８は、前記した第１乃至第３の実施例に記載したデータ配信方法を用いて処理した結果を示す図であり、図７は、各々の実施例と理想解との関係を示す図であり、図８は、その具体的な結果を示す図である。
【００６２】
本実施例では、５ｘ５のマップのそれぞれのセルに１つのサーバが存在し、クライアントも一様に存在する場合について記載する。また、この際の評価式は、サーバの座標を（Ｓx，Ｓy）、クライアントの座標を（Ｃx，Ｃy）とした場合に次の式で与えられるとする。
【００６３】
0003885865.tif 000010
【００６４】
このような状況において、理想解、第１の実施例の順序決定手段による解、第２の実施例の順序決定手段による解、それらを組み合わせた場合の融合解を、それぞれサーバを６個獲得する時点まで求める。その結果として、理想解、第１の実施例の手段による解、第２の実施例の手段による解、それらを組み合わせた融合解のそれぞれを比較したものが図７であり、実際にどのような配置になるかを示したものが図８である。なお、融合解に関しては、６個のサーバを選択する中で、３個のサーバまでを第１の実施例の順序決定手段で、それ以降の選択を第２の実施例の順序決定手段にて求めている。
【００６５】
図７に示すように、前記した第１乃至第３の実施例に記載したどの方法であっても、理想解に近い解を導出することができ、クライアントからの公平なアクセスを維持するという目的を達成することができる。
【００６６】
【発明の効果】
以上説明したように、本発明のデータ配信システム及びデータ配信方法によれば、あるサーバ群において利用されるサーバ数が動的に変化する場合であっても、常にクライアントからのアクセスが公平となるサーバの配置を実現するサーバの選択順序を決定することができるという効果を奏する。
【００６７】
その理由は、配信サーバの配信制御手段にサーバ選択順序決定手段を設け、この選択順序決定手段において、予め定めた評価式に基づき算出した評価値を用いてサーバの選択順序を決定しているからである。
【図面の簡単な説明】
【図１】本発明の一実施の形態に係るデータ配信システム構成を示す図である。
【図２】本発明の一実施の形態に係るデータ配信システムの動作を示すフローチャート図である。
【図３】本発明の一実施の形態に係るデータ配信システムの動作を示すフローチャート図である。
【図４】本発明の第１の実施例に係るデータ配信システムのサーバ選択順序決定方法を説明するフローチャート図である。
【図５】本発明の第２の実施例に係るデータ配信システムのサーバ選択順序決定方法を説明するフローチャート図である。
【図６】本発明の第３の実施例に係るデータ配信システムのサーバ選択順序決定方法を説明するフローチャート図である。
【図７】理想解、第１の実施例の順序決定手段、第２の実施例の順序決定手段、第１の実施例の決定手段と第２の実施例の決定手段を組み合わせた手段の比較を示す図である。
【図８】理想解、第１の実施例の順序決定手段、第２の実施例の順序決定手段、第１の実施例の決定手段と第２の実施例の決定手段を組み合わせた手段によるそれぞれの具体例を示す図である。
【図９】従来のデータ配信システムの構成を示す図である。
【図１０】従来のデータ配信システムの動作を示すフローチャート図である。
【符号の説明】
１  データ配信システム
２  配信サーバ
３  選択順序決定手段を備えた配信制御手段
４、４ａ〜４ｅ  サーバ
５、５ａ〜５ｃ  クライアント
１１  データ配信システム
１２  配信サーバ
１３  配信制御手段
１４、１４ａ〜１４ｅ  サーバ
１５、１５ａ〜１５ｃ  クライアント
【図１】
0003885865.tif 000011
【図２】
0003885865.tif 000012
【図３】
0003885865.tif 000013
【図４】
0003885865.tif 000014
【図５】
0003885865.tif 000015
【図６】
0003885865.tif 000016
【図７】
0003885865.tif 000017
【図８】
0003885865.tif 000018
【図９】
0003885865.tif 000019
【図１０】
0003885865.tif 000020