(57)【要約】【課題】キャリア型ＣＤＮのネットワーク内に流れるトラヒック総量の最小化を図る。【解決手段】サーバ拠点配置装置１０１は、ネットワーク上の各ノードから１つを選択して、全てのコンテンツを記憶するオリジナルサーバシステムを配置すると共に（Ｓ９０１）、各ノードから複数を選択して、オリジナルサーバシステムが記憶するコンテンツをキャッシュして配信するコンテンツサーバ１０３（キャッシュサーバシステム）として配置する（Ｓ９０２）。この際、ＮＷトポロジと各クライアントコンピュータから各コンテンツに対する配信要求の発生頻度を入力情報として入力し、配信フローの平均ホップ長が最小化するよう、オリジナルサーバシステムとキャッシュサーバシステムを選択する。【選択図】図２
2010057107.tif 000002
【特許請求の範囲】
【請求項１】
プログラムされたコンピュータ処理によって、ネットワークを介してクライアントコンピュータにコンテンツを配信する複数のサーバコンピュータシステムの配置を行うサーバ配置方法であって、
プログラムされたコンピュータの処理実行手順として、
上記ネットワーク上の各ノードから１つのノードを選択し、選択したノードに全てのコンテンツを記憶するオリジナルサーバシステムを配置する第１の手順と、
上記ネットワーク上の各ノードから複数のノードを選択し、選択した各ノードに上記オリジナルサーバシステムが記憶するコンテンツをキャッシュして配信するキャッシュサーバシステムを配置する第２の手順と
を含むことを特徴とするサーバ配置方法。
【請求項２】
請求項１に記載のサーバ配置方法であって、
上記第１，第２の手順では、
ネットワークトポロジ情報と、上記全ノードからの各コンテンツに対する配信要求の発生頻度とを入力して、
配信フローの平均ホップ長が最小化するよう、上記オリジナルサーバシステムと上記キャッシュサーバシステムを配置するノードの選択を行うことを特徴とするサーバ配置方法。
【請求項３】
請求項２に記載のサーバ配置方法であって、
上記第１の手順では、
上記ネットワーク上の各ノードｎに対して、当該ノードｎから他の各ノードに至る最短経路上のホップ数を上記配信要求の発生頻度数比で重み付けした総和の逆数で、当該ノードｎの中心度Ｈｏ（ｎ）を定義し、
該中心度Ｈｏ（ｎ）が最大のノードを選択して上記オリジナルサーバを配置することを特徴とするサーバ配置方法。
【請求項４】
請求項２もしくは請求項３のいずれかに記載のサーバ配置方法であって、
上記第２の手順では、
各キャッシュサーバシステムの容量Ｂを一定値とし、かつ、ネットワーク全体のキャッシュサーバシステムの容量Ｋと各キャッシュサーバシステム数Ｃを用いた床関数式「Ｂ＝ｆｌｏｏｒ（Ｋ／Ｃ）」により、各キャッシュサーバシステム数Ｃも含めて、各キャッシュサーバシステムを配置するノードを選択することを特徴とするサーバ配置方法。
【請求項５】
請求項２から請求項４のいずれかに記載のサーバ配置方法であって、
上記第１，第２の手順では、
上記オリジナルサーバシステムと上記キャッシュサーバシステムを配置するＳ個のノードの中でノードｎからのホップ距離が最短のノードまでのホップ距離ｈｎ，ｍｉｎと、上記オリジナルサーバシステムを配置したノードから上記ノードｎまでのホップ距離ｈｎ,ｏ、および、上記ノードｎからの配信要求がコンテンツｍに対するものである確率ｑｎ（ｍ）の累積分布関数Ｑｎ（ｍ）と、上記ノードｎからの配信要求発生比率ｒｎとを用いて、下記の数１の式から、上記配信フローの平均ホップ長の推定値（ｈ＾）を算出することを特徴とするサーバ配置方法。
【数１】
2010057107.tif 000011
【請求項６】
請求項２から請求項４のいずれかに記載のサーバ配置方法であって、
上記第２の手順は、
ノードｉから、ｊ個の各キャッシュサーバシステムが配置された各ノードの集合Ｎｊ（ｊ＝０ではオリジナルサーバシステムが配置されたノードを除いた集合Ｎ０）における最近接のノードまでのホップ長ｈｉ，ｍｉｎ，Ｎｊと、
上記ノードｉから集合Ｎｊ外のノードｎ（ｎ∈Ｎ＼Ｎｊ）までのホップ長ｈｎ，ｉとを用いて、下記の数２の式から、
既にｊ個のキャッシュサーバシステムが集合Ｎｊに含まれる各ノードに設置された状態で、上記ノードｎに新たにキャッシュサーバシステムを配置することで得られる上記配信フローの平均ホップ長の推定値「ｈ＾」の削減効果Ｅｎ、Ｎｊを算出し、
算出した削減効果Ｅｎ、Ｎｊが最大のノードから順にキャッシュサーバシステムを配置するノードとして選択していくことを特徴とするサーバ配置方法。
【数２】
2010057107.tif 000012
【請求項７】
キャリアが運用するネットワーク（キャリア型ネットワーク）においてＣＤＮによりサーバコンピュータにキャッシュされたコンテンツを要求元のクライアントコンピュータに配信するキャリア型ＣＤＮシステムにおけるサーバコンピュータの配置方法であって、
請求項１から請求項６のいずれかに記載のサーバ配置方法における各手順により、上記オリジナルサーバシステムと上記キャッシュサーバシステムのそれぞれを配置するノードの選択を行い、選択したノードに上記オリジナルサーバシステムと上記キャッシュサーバシステムのそれぞれを配置すると共に、
上記オリジナルサーバシステムおよび上記キャッシュサーバシステムを、複数のサーバコンピュータをクラスタリングして構成することを特徴とするキャリア型ＣＤＮにおけるサーバ配置方法。
【請求項８】
プログラムされたコンピュータ処理によって、ネットワークを介してクライアントコンピュータにコンテンツを配信する複数のサーバコンピュータシステムの配置を行うサーバ配置システムであって、
プログラムされたコンピュータ処理を実行する手段として、
請求項１から請求項７のいずれかに記載のサーバ配置方法における各手順を実行する手段を具備し、
該手段により、上記オリジナルサーバシステムと上記キャッシュサーバシステムのそれぞれを配置するノードの選択と、選択したノードへの上記オリジナルサーバシステムと上記キャッシュサーバシステムのそれぞれの配置を行うことを特徴とするサーバ配置システム。
【請求項９】
キャリアが運用するネットワーク（キャリア型ネットワーク）においてサーバコンピュータにキャッシュされたコンテンツを要求元のクライアントコンピュータに配信するキャリア型ＣＤＮシステムであって、
プログラムされたコンピュータ処理を実行する装置として、
請求項１から請求項７のいずれかに記載のサーバ配置方法における各手順を実行する手段を具備し、該手段により、上記オリジナルサーバシステムと上記キャッシュサーバシステムのそれぞれを配置するノードの選択と、選択したノードへの上記オリジナルサーバシステムと上記キャッシュサーバシステムのそれぞれの配置を行うサーバ拠点配置装置と、
全てのクライアントコンピュータからのコンテンツの配信要求を受信して、当該クライアントコンピュータへのコンテンツの配信に適したキャッシュサーバシステムの選択指示を送出する集中制御装置と、
該集中制御装置から送出された選択指示を受信して、クライアントコンピュータへのコンテンツの配信に適したキャッシュサーバシステムを選択し、選択したキャッシュサーバシステムに対して、当該コンテンツの当該クライアントコンピュータへの配信を指示するサーバ選択装置と
を設けたことを特徴とするキャリア型ＣＤＮシステム。
【請求項１０】
コンピュータに、請求項１から請求項７のいずれかに記載のサーバ配置方法における各手順を実行させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、インターネットにおけるコンテンツ配信サーバの配置技術に係り、特に、キャリア型ＣＤＮ（Ｃｏｎｔｅｎｔｓ  Ｄｅｌｉｖｅｒｙ  Ｎｅｔｗｏｒｋ）における大容量のリッチコンテンツの配信を効率的に行うのに好適なサーバの配置技術に関するものである。
【背景技術】
【０００２】
従来、インターネットにおいては、Ｗｅｂ等のテキストや静止画像といった容量の小さい小サイズのコンテンツのダウンロードが主要な利用形態であった。しかし、近年、各種コンテンツプロバイダによって提供される映画やライブ放送等の、数１００Ｍから数Ｇバイト以上の非常にサイズの大きな動画象コンテンツのストリーミング配信が急速に広まりつつある。
【０００３】
そのため、これら大容量のリッチコンテンツをユーザにストレスなく、また、ネットワーク（ＮＷ）に負担をかけることなく経済的かつ快適に配信することがインターネットに求められている。
【０００４】
従来、小サイズのコンテンツをユーザに配信するための技術としてＣＤＮが広く普及している。このＣＤＮサービスをコンテンツプロバイダに対して提供するＣＤＮ事業者として、Ａｋａｍａｉ  Ｔｅｃｈｎｏｌｏｇｉｅｓ社（商標）やＬｉｍｅｌｉｇｈｔ  Ｎｅｔｗｏｒｋｓ社（商標）を含め、多数存在する。
【０００５】
ＣＤＮは、ＮＷインフラの伝送容量が限られていた時代に設計された技術であり、ユーザのレスポンス時間の改善を目的とし、可能な限り多数のサーバを様々なＮＷ上に配置し、ユーザに近いサーバを配信に用いる。
【０００６】
例えば、Ａｋａｍａｉ  Ｔｅｃｈｎｏｌｏｇｉｅｓ社（商標）の場合、全世界７０カ国の約１,０００のＮＷ上に、２万台以上のサーバを配置している。
【０００７】
このように、サーバの数が膨大であることから、各サーバの容量は限られたものになる。従来のインターネットにおいて配信されるコンテンツは、テキストや静止画像等の小サイズのものが中心であり、このような配信形態でも有効であった。
【０００８】
尚、以上の従来技術については、非特許文献１等に記載されている。
【０００９】
近年、動画コンテンツのストリーミング配信サービスの利用が急増している。例えば、ＹｏｕＴｕｂｅ（商標）といったユーザ自身が作成した動画コンテンツ（ＵＧＣ：  Ｕｓｅｒ−Ｇｅｎｅｒａｔｅｄ  Ｃｏｎｔｅｎｔ）を配信するシステムの場合、各コンテンツの容量（サイズ）が小さいため従来のＣＤＮでも十分に対応可能である。
【００１０】
しかし、今後、テレビ放送局や映画製作会社といった有力なコンテンツプロバイダが保有する魅力的なコンテンツの配信がインターネットにおいても普及していくことが予想される。これらのコンテンツは容量が大きく、このようなサイズの大きいコンテンツ（リッチコンテンツ）を従来のＣＤＮで提供することは、各サーバに蓄積可能なコンテンツ数に大きな制約があり困難である。
【００１１】
このようなリッチコンテンツを効率的に配信するために、Ｌｉｍｅｌｉｇｈｔ  Ｎｅｔｗｏｒｋｓ社（商標）は、限定された箇所に大規模なデータセンタ（コンピュータシステム）を設け、それらを独自の大容量ＮＷインフラで接続した新しい形態のＣＤＮ事業を展開し始めている。
【００１２】
この新しい形態のＣＤＮは「第二世代ＣＤＮ」と呼ばれ、各データセンタにおいては、大量のサーバをクラスタリング技術によって統合し、大容量のリッチコンテンツを多数、全てのデータセンタに用意することを目指している。
【００１３】
また近年、目的コンテンツを保有する他のユーザから配信を受けるＢｉｔＴｏｒｒｅｎｔ（登録商標）等のＰ２Ｐ（Ｐｅｅｒ  ｔｏ  Ｐｅｅｒ）型のコンテンツ配信が広く普及している。
【００１４】
例えば、ＢｉｔＴｏｒｒｅｎｔ（登録商標）では、コンテンツのデータを複数のブロックに分割し、コンテンツを取得したいユーザはブロックのダウンロードを行うと同時に、他の同一コンテンツの配信を希望するユーザ（ピア）に対してアップロードを並列して行う。
【００１５】
この技術では、コンテンツを取得したいユーザの数が増加するほど該当コンテンツを保有するピア数が増加するため、人気の極めて高いコンテンツを多数のユーザに配布する際に非常に効果的な配信形態となる。
【００１６】
通常、同一のコンテンツを有するサーバが多数存在する場合、経由ホップ数の少ない位置に存在するサーバから配信を受けることが、ＮＷの消費資源量やユーザのレスポンス時間の観点から望ましい。
【００１７】
そのため、多くのＣＤＮでは、ユーザの配信要求に対しホップ距離の近いサーバから配信を行う。
【００１８】
しかし、ＢｉｔＴｏｒｒｅｎｔ（登録商標）等、多くのＰ２Ｐ型配信システムにおいては、配信元となるピアはランダムに選択されるため、近くにピアが存在する場合にも、遠くに存在するピアが選択され配信を受ける場合もあり、ＮＷ内を無駄にトラヒックが流れる。
【００１９】
近年、Ｐ２Ｐ型配信を用いたＵＧＣの配信の増加が顕著であり、ＮＷ内の資源浪費が問題になっている。そこでＩＳＰ（Ｉｎｔｅｒｎｅｔ  Ｓｅｒｖｉｃｅｓ  Ｐｒｏｖｉｄｅｒ）とＰ２Ｐ配信事業者が連携して互いの情報を交換することで、ＮＷ内を流れるトラヒック量を抑えたピア選択を行うＰ４Ｐ（Ｐａｙ  ｆｏｒ  Ｐｅｒｆｏｒｍａｎｃｅ）が検討されている。
【００２０】
このＰ４Ｐによって、ＮＷに与える影響を抑えたＰ２Ｐ型配信サービスが可能となるが、配信サーバの役目を担うピアがユーザである点には変わりなく、その行動は利己的であるため、ユーザにコンテンツのアップロードを行うための動機づけを与える必要がある。
【００２１】
また、一元的に全サーバの位置を設計し管理することができないため、ＮＷ全体で見たときに最適な位置にサーバを配置することができず、従来のＰ２Ｐと比較すればＮＷに与える影響が緩和されるものの、最適な配信形態が実現されるとはいえない。
【００２２】
また、配信中のサーバが離脱する可能性があるため、継続的で安定した配信が望まれる動画コンテンツのストリーミング配信には適さない。
【００２３】
Ｐ４Ｐの他に、Ｐ２ＰとＣＤＮと組み合わせてＰ２Ｐを補完的に利用することで、ＣＤＮのサーバに加わる負荷を抑えるアプローチも検討されているが、ＣＤＮのサーバコスト削減が主な目的であり、ＮＷに与える影響を最小化する配信システムの実現を目的にしていない。
【００２４】
一般に、個々のユーザの配信要求によって生成されるコンテンツ配信フローの受信側であるユーザの位置を変えることはできないが、送信側であるサーバの位置は自由に設計・制御できる柔軟性があり、ＮＷ内に流れるトラヒックの交流を決める大きな要因となる。
【００２５】
そのため、容量が大きく配信フローのＮＷに与える影響が大きいリッチコンテンツを配信する際には、サーバとコンテンツの位置を集中的に管理し、各配信要求に対して最適なサーバから配信を行うことが重要である。
【００２６】
そのための一つの方法として、キャリア（電気通信事業者）やＩＳＰが、自ＮＷ内の複数の箇所に大容量のサーバ拠点（データセンタ）を設け、自らリッチコンテンツの配信を行うＣＤＮを構築する形態が有望である。
【００２７】
以降、このような形態を「キャリア型ＣＤＮ」と呼ぶ。このキャリア型ＣＤＮでは、キャリアやＩＳＰは自ＮＷのトポロジ、リンク容量といったＮＷインフラに関する情報に加え、全てのサーバ拠点を一元的に管理することが可能である。
【００２８】
さらに、このキャリア型ＣＤＮでは、従来の小容量の無数のサーバを配置するＣＤＮ事業者とは異なり、限定された少数の場所に大容量のサーバ群を収容したデータセンタを構築することで、コンテンツのコピーの存在位置の一元管理を容易にし、さらに、多数のリッチコンテンツを多数のサーバ拠点に用意することができ、リッチコンテンツの最適な位置からの配信機会を向上させることが可能となる。
【００２９】
実際、ＡＴ＆Ｔ（商標）は、近年、自身がＣＤＮ事業を展開することを表明している。また、Ｌｉｍｅｌｉｇｈｔ  Ｎｅｔｗｏｒｋｓ（商標）は自身でＮＷインフラを構築しており、第二世代ＣＤＮ事業者はキャリアと見なすこともでき、キャリア型ＣＤＮに近い形態であると考えることができる。
【００３０】
このように、キャリア型ＣＤＮは、リッチコンテンツの配信をＮＷに与える影響を抑えた最適な配信設計のもとで行う配信システムとして有望である。
【００３１】
しかし、このようなキャリア型ＣＤＮによる配信システムにおいて、データセンタの最適な配置を行うための技術は提案されていない。
【００３２】
【非特許文献１】Ｍ.  Ｋａｒｌｓｓｏｎ  ａｎｄ  Ｍ.  Ｍａｈａｌｉｎｇａｍ，“Ｄｏ  Ｗｅ  Ｎｅｅｄ  Ｒｅｐｌｉｃａ  Ｐｌａｃｅｍｅｎｔ  Ａｌｇｏｒｉｔｈｍｓ  ｉｎ  Ｃｏｎｔｅｎｔ  Ｄｅｌｉｖｅｒｙ  Ｎｅｔｗｏｒｋｓ？”  ＷＣＷ  ０２.
【発明の開示】
【発明が解決しようとする課題】
【００３３】
解決しようとする問題点は、従来の技術では、キャリア型ＣＤＮによる配信システムにおけるデータセンタを最適に配置することができない点である。
【００３４】
本発明の目的は、これら従来技術の課題を解決し、キャリア型ＣＤＮにおいて、配信フローの平均ホップ長を最小化し、各リンクの平均負荷を最小化するよう、オリジナルサーバ拠点とキャッシュサーバ拠点を最適配置することを可能とすることである。
【課題を解決するための手段】
【００３５】
上記目的を達成するため、本発明では、例えばキャリア型ＣＤＮにおいて、配信フローの平均ホップ長を最小化し、各リンクの平均負荷を最小化するよう、オリジナルサーバ拠点とキャッシュサーバ拠点を最適配置することを特徴とする。すなわち、キャリアが自身のネットワーク（ＮＷ）の限定された拠点に、大容量のデータセンタを構築し、ＣＤＮを運用するキャリア型ＣＤＮにおいて、全てのコンテンツを常に収容するオリジナルサーバ拠点を１つ配置し、さらに、保有するコンテンツをユーザからの配信要求に基づいて、例えばＬＦＵ（Ｌｅａｓｔ  Ｆｒｅｑｕｅｎｃｔｌｙ  ｕｓｅｄ）により更新するキャッシュサーバ拠点を複数のデータセンタに配置する。例えば、ＮＷトポロジと、各ノードから各コンテンツに対する配信要求発生頻度とが与えられたときに、配信フローの平均ホップ長が最小化するよう、一つのオリジナルサーバ拠点と、任意個数のキャッシュサーバ拠点を最適配置する。特に、各ノードｎに対して、ノードｎから各ノードに至る最短経路上のホップ数を要求発生数比で重み付けした総和の逆数でノードｎの中心度Ｈｏ（ｎ）を定義し、中心度が最大のノードにオリジナルサーバを配置する。また、ＮＷ全体のキャッシュサーバ容量Ｋを与え、各キャッシュサーバの容量Ｂを配置キャッシュサーバ拠点数Ｃに対して一定値（Ｂ＝ｆｌｏｏｒ（Ｋ／Ｃ））で与え、配置キャッシュサーバ拠点数Ｃも含めてキャッシュサーバ拠点を最適配置する。より詳細には、ｈｎ，ｍｉｎとｈｎ,ｏを各々、オリジナルサーバ拠点も含めたＳ個の全サーバ拠点の中でノードｎからホップ距離が最短のものまでのホップ距離と、オリジナルサーバからノードｎまでのホップ距離とし、さらに、Ｑｎ（ｍ）をノードｎからの配信要求がコンテンツｍに対するものである確率ｑｎ（ｍ）の累積分布関数とし、そして、ｒｎをノードｎからの要求発生比率とするとき、下記の数１の式で配信フローの平均ホップ長を推定する。
【００３６】
【数１】
2010057107.tif 000003
また、ｈｉ，ｍｉｎ，Ｎｊを、Ｎｊにキャッシュサーバ拠点が設置された状態における、ノードｉから最近接サーバ拠点までのホップ長とするとき、既にｊ個のキャッシュサーバ拠点がノード集合Ｎｊに設置された状態で（Ｎ０は全ノード集合Ｎからオリジナルサーバ拠点Ｏを除いたＮ＼Ｏ；「＼」は集合の引算）、さらに、全ノード集合Ｎから集合Ｎｊを除いた集合におけるノードｎ（ｎ∈Ｎ＼Ｎｊ）にキャッシュサーバ拠点を設置することで得られる配信フローの平均ホップ長の推定値ｈ＾の削減効果Ｅｎ、Ｎｊを、下記の数２により算出し、Ｅｎ、Ｎｊが最大のノードから順にキャッシュサーバ拠点を配置していく。
【００３７】
【数２】
2010057107.tif 000004
【発明の効果】
【００３８】
本発明によれば、キャリア型ＣＤＮにおいて、配信フローの平均ホップ長を最小化し、各リンクの平均負荷を最小化するよう、オリジナルサーバ拠点とキャッシュサーバ拠点を最適配置することができ、キャリア型ＣＤＮのネットワーク内に流れるトラヒック総量の最小化を図ることが可能である。
【発明を実施するための最良の形態】
【００３９】
以下、図を用いて本発明を実施するための最良の形態例を説明する。図１は、本発明に係るサーバ配置システムを設けたキャリア型ＣＤＮのネットワーク構成例を示すブロック図であり、図２は、３６個のネットワークの平均ノード次数と最大ノード次数の散布状況例を示す説明図、図３は、Ｃａｂｏｅ＆Ｗｉｒｅｌｅｓｓのトポロジ例とノード人口状況例を示す説明図、図４は、Ｃａｂｏｅ＆Ｗｉｒｅｌｅｓｓに対する本発明のシミュレーション結果例を示す説明図、図５は、Ｃａｂｏｅ＆Ｗｉｒｅｌｅｓｓに対する本発明による設計結果例を示す説明図、図６は、１８個のネットワークにおける性能比較例を示す説明図、図７は、３６個のネットワークにおける性能比較例を示す説明図、図８は、３６個のネットワークにおける正規化キャッシュサーバ数を示す説明図、図９は、図１におけるサーバ拠点配置装置による本発明に係るサーバ配置手順例を示すフローチャートである。
【００４０】
図１において、１０１はサーバ拠点配置装置、１０２は集中制御局、１０３はコンテンツサーバ、１０４はサーバ選択装置、１０５はユーザ端末であり、それぞれは、ＣＰＵ（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）や主メモリ、表示装置、入力装置、外部記憶装置等を具備したコンピュータ構成からなり、光ディスク駆動装置等を介してＣＤ−ＲＯＭ等の記憶媒体に記録されたプログラムやデータを外部記憶装置内にインストールした後、この外部記憶装置から主メモリに読み込みＣＰＵで処理することにより、プログラムされたコンピュータ処理を実行する。
【００４１】
プログラムされたコンピュータ処理として、サーバ拠点配置装置１０１は、サーバ拠点（コンテンツを配信するサーバコンピュータを設置するノード）を最適配置し、集中制御局１０２は、ユーザ端末１０５より生じた配信要求が伝えられると、サーバ選択装置１０４に対してサーバ選択を依頼し、依頼を受けたサーバ選択装置１０４は、ユーザ端末１０５から通信距離が最も近いサーバを一つ選択し、選択したコンテンツサーバ１０３に配信を要求し、配信要求を受けたコンテンツサーバ１０３は、ユーザ端末１０５に該当コンテンツを配信する。
【００４２】
その際、配信経路上に存在する他のコンテンツサーバは、当該コンテンツを、ＬＦＵ（Ｌｅａｓｔ  Ｆｒｅｑｕｅｎｔｌｙ  Ｕｓｅｄ）に基づきキャッシュして保有し、保有したコンテンツの情報を集中制御局１０２およびサーバ選択装置１０４に通知する。
【００４３】
図１に示すキャリア型ＣＤＮのネットワークには、当該ネットワークを介してユーザ端末１０５（クライアントコンピュータ）にコンテンツを配信する複数のコンテンツサーバ（サーバコンピュータシステム）が設けてあり、サーバ拠点配置装置１０１は、図９に示す処理手順により、複数のサーバコンピュータシステムの配置を行う。
【００４４】
すなわち、サーバ拠点配置装置１０１は、プログラムされたコンピュータの処理として、ネットワーク上の各ノード（具体的には、ルータ機能を具備した装置が設置されたネットワークの交換ポイントとなる）から１つのノードを選択し、選択したノードに、全てのコンテンツを記憶するオリジナルサーバシステムを配置する第１の手順（ステップＳ９０１）と、ネットワーク上の各ノードから複数のノードを選択し、選択した各ノードにオリジナルサーバシステムが記憶するコンテンツをキャッシュして配信するキャッシュサーバシステム（コンテンツサーバ１０３）を配置する第２の手順（ステップＳ９０２）とを実行する。
【００４５】
この際、サーバ拠点配置装置１０１は、第１，第２の手順において、ネットワークトポロジ情報と、全ノードからの各コンテンツに対する配信要求の発生頻度とを入力して、配信フローの平均ホップ長が最小化するよう、オリジナルサーバシステムおよびキャッシュサーバシステムを配置するノードの選択を行う。
【００４６】
特に、サーバ拠点配置装置１０１は、第１の手順において、ネットワーク上の各ノードｎに対して、当該ノードｎから他の各ノードに至る最短経路上のホップ数を配信要求の発生頻度数比で重み付けした総和の逆数で、当該ノードｎの中心度Ｈｏ（ｎ）を定義し、この中心度Ｈｏ（ｎ）が最大のノードを選択してオリジナルサーバを配置する。
【００４７】
また、サーバ拠点配置装置１０１は、第２の手順において、各キャッシュサーバシステムの容量Ｂを一定値とし、かつ、ネットワーク全体のキャッシュサーバシステムの容量Ｋと各キャッシュサーバシステム数Ｃを用いた床関数式「Ｂ＝ｆｌｏｏｒ（Ｋ／Ｃ）」により、各キャッシュサーバシステム数Ｃも含めて、各キャッシュサーバシステムを配置するノードを選択する。
【００４８】
また、サーバ拠点配置装置１０１は、第１，第２の手順において、オリジナルサーバシステムとキャッシュサーバシステムを配置するＳ個のノードの中でノードｎからのホップ距離が最短のノードまでのホップ距離ｈｎ，ｍｉｎと、オリジナルサーバシステムを配置したノードからノードｎまでのホップ距離ｈｎ,ｏ、および、ノードｎからの配信要求がコンテンツｍに対するものである確率ｑｎ（ｍ）の累積分布関数Ｑｎ（ｍ）と、ノードｎからの配信要求発生比率ｒｎとを用いて、下記の数３の式から、配信フローの平均ホップ長の推定値（ｈ＾）を算出する。
【００４９】
【数３】
2010057107.tif 000005
【００５０】
また、サーバ拠点配置装置１０１は、第２の手順において、ノードｉから、ｊ個の各キャッシュサーバシステムが配置された各ノードの集合Ｎｊ（ｊ＝０ではオリジナルサーバシステムが配置されたノードを除いた集合Ｎ０）における最近接のノードまでのホップ長ｈｉ，ｍｉｎ，Ｎｊと、ノードｉから集合Ｎｊ外のノードｎ（ｎ∈Ｎ＼Ｎｊ）までのホップ長ｈｎ，ｉとを用いて、下記の数４の式から、既にｊ個のキャッシュサーバシステムが集合Ｎｊに含まれる各ノードに設置された状態で、ノードｎに新たにキャッシュサーバシステムを配置することで得られる配信フローの平均ホップ長（推知値）「ｈ＾」の削減効果Ｅｎ、Ｎｊを算出し、算出した削減効果Ｅｎ、Ｎｊが最大のノードから順にキャッシュサーバシステムを配置するノードとして選択していく。
【００５１】
【数４】
2010057107.tif 000006
【００５２】
次に、このような本発明に係るキャリア型ＣＤＮおよびキャリア型ＣＤＮにおけるサーバ配置技術について、詳細を説明する。
【００５３】
まず、『３．５  キャリア型ＣＤＮ』について説明する。
【００５４】
キャリア型ＣＤＮにおいては、Ｔｉｅｒ１といった大規模なバックボーンＮＷを有する単一のキャリアやＩＳＰが、運営するＮＷ上の数ヵ所〜１０数ヵ所程度の限定された拠点（ノード）に、大規模なデータセンタを構築する。ＮＷ全体のノード数をＮ、大規模なデータセンタを設けたノード（サーバ拠点）数をＳ、リッチコンテンツ数をＭとする。
【００５５】
また、集中制御局が存在し、各サーバ拠点に存在するコンテンツを管理し、各配信要求に対して配信に用いるサーバを選択する。
【００５６】
尚、本例では、単一のキャリアやＩＳＰに閉じたＣＤＮサービスを想定し、そのＮＷ内を流れるトラヒック総量の最小化を目的とするが、複数のキャリアやＩＳＰが連携してキャリア型ＣＤＮサービスを展開する形態も考えることができる。
【００５７】
各データセンタは、クラスタリング技術を用いて多数のサーバ装置を収容し、非常に大きなストレージ容量と、大量の配信要求に対する同時処理能力を有する。
【００５８】
次に、『３．５．１  コンテンツ展開法』について説明する。
【００５９】
各リッチコンテンツの複製をＳ個のサーバ拠点にどのように配布するかが問題になるが、従来のＣＤＮにおいては、Ｒｅｐｌｉｃａｔｉｏｎ法とＣａｃｈｉｎｇ法が検討されてきた。
【００６０】
Ｒｅｐｌｉｃａｔｉｏｎ法では、各コンテンツを配布するサーバ集合を、配信フローの平均ホップ数の最小化といった最適化問題（ＲＰＡ：Ｒｅｐｌｉｃａ  Ｐｌａｃｅｍｅｎｔ  Ａｌｇｏｒｉｔｈｍ）として導出し、事前に各コンテンツの複製を該当サーバに展開する。
【００６１】
コンテンツの展開法としては様々なものが検討されている。また、ＲＰＡ問題に対しても多数の方法が検討されているが、事前に各ノードにおいて各コンテンツに対して発生する配信要求の頻度を推定する必要がある。
【００６２】
ＲＰＡ問題はＮＰ困難であるため近似解法を用いる必要があり、様々な方式が検討されているが、単に目的関数の改善度合いが最良のノードにコンテンツを配置していくＧｒｅｅｄｙ法が最良である。
【００６３】
一方、Ｃａｃｈｉｎｇ法では、事前にコンテンツをサーバに配布することはせず、各サーバをキャッシュサーバとして機能させる。すなわち、各配信要求に対して最も近い位置に存在するサーバがプロキシサーバとして動作し、そこに該当コンテンツが存在しない場合には、オリジナルサーバからダウンロードし、ユーザに配信すると同時に該当コンテンツをキャッシュする。
【００６４】
サーバ容量を超過する場合には、ＬＦＵ（Ｌｅａｓｔ  Ｆｒｅｑｕｅｎｔｌｙ  Ｕｓｅｄ）やＬＲＦ（Ｌｅａｓｔ  Ｒｅｃｅｎｔｌｙ  Ｕｓｅｄ）といったキャッシュ置き換えアルゴリズムにより、アクセス頻度が最少のコンテンツや最後に要求されてからの経過時間が最長のコンテンツと置換する。
【００６５】
各キャッシュサーバで保有しているコンテンツの情報をサーバ間で交換し共有すれば、キャッシュミス時に、オリジナルサーバではなく、該当コンテンツを保有する近隣のサーバから配信を行うことが可能である。そのため、レスポンス時間の向上と消費網資源の低減を目的とし、キャッシュ間で協調を図る方式も検討されている。
【００６６】
このＣａｃｈｉｎｇ法では、要求頻度が高いコンテンツが各サーバにキャッシュされやすい。そのため、動的にアクセス頻度が変化する現実的な環境において、サーバ間で情報を共有する理想的なＣａｃｈｉｎｇ法は、最適なＲｅｐｌｉｃａｔｉｏｎ法と比較して良好な特性を示す。
【００６７】
しかし、サーバ情報を共有しない場合、サーバの容量が小さくキャッシュミス率が高い環境では、配信コストが高いオリジナルサーバからの配信頻度が高く、Ｒｅｐｌｉｃａｔｉｏｎ法と比較して性能は劣化する。
【００６８】
現実のＣＤＮの多くは、オペレーションが容易であることから、性能は劣化するものの、サーバ情報を共有しないＣａｃｈｉｎｇ法を用いている。
【００６９】
コンテンツのサーバへの展開法としては、サーバ間で情報を共有する理想的なＣａｃｈｉｎｇ法を用いることが、ＮＷ内のトラヒック量とレスポンス時間を抑える意味で望ましい。
【００７０】
ところでキャリア型ＣＤＮでは、サーバ拠点を少数の箇所に限定すると共に、全体を管理する集中制御局の存在を想定しているため、各サーバ拠点が保有するコンテンツの情報を一元的に管理可能である。
【００７１】
そこで、本例では、キャリア型ＣＤＮにおけるコンテンツの展開法として、理想的なＣａｃｈｉｎｇ法を用いることを想定する。
【００７２】
ただし、コンテンツの配信を保証するためには、Ｓ個のサーバ拠点の中で最低でも一つ以上に各コンテンツのコピーが存在する必要がある。そのため、本例では、Ｓ個のサーバ拠点の中で一つをオリジナルサーバ拠点とし、オリジナルサーバには常にＭ個の全コンテンツが保持されることを想定する。そして、他のＣ（＝Ｓ−１）個のサーバ拠点はキャッシュサーバとして機能する。
【００７３】
この場合、初期状態では、オリジナルサーバのみにコンテンツが存在するが、ユーザの配信要求に伴い、キャッシュサーバにコンテンツがキャッシュされるため、全てのサーバ拠点にコンテンツが拡散していくことになる。
【００７４】
サービス運用開始後にも、適時、コンテンツプロバイダが新しいリッチコンテンツを提供することが予想されるが、この場合にも、オリジナルサーバにのみコンテンツをアップロードすることで、後はユーザの配信要求に応じて、自動的にＮＷの他のサーバ拠点にコンテンツが拡散していく。
【００７５】
次に、『３．５．２  配信処理シーケンス』について説明する。
【００７６】
任意のノードｎに収容されているユーザ端末（１０５）から生じたリッチコンテンツｍの配信要求は、集中制御局（１０２）に通知される。集中制御局（１０２）は、コンテンツｍを保持している全てのサーバ拠点を把握しており、オリジナルサーバも含め、これらサーバ拠点の中でノードｎにホップ距離が最短のものを一つ配信元として選択する。
【００７７】
最短距離のものが複数存在する場合には、それらの中からランダムに一つを選択する。もし、どのサーバ拠点もコンテンツｍをキャッシュしていない場合は、オリジナルサーバから配信を行うことになる。
【００７８】
そして、選択した配信サーバ（コンテンツサーバ１０３）に対して、集中制御局（１０２）は、ノードｎにコンテンツｍを配信するよう指示する。尚、コンテンツの配信経路はダイクストラの最短ホップ経路を想定する。もし、最短ホップ経路が複数存在する場合には、その中からランダムに一つを選択する。
【００７９】
各サーバ拠点において、過去Ｗの時間内に配信を行った回数Ｘｊを、各コンテンツｊ（の識別情報）に対応付けて記憶装置に保持し、ＬＦＵによりキャッシュサーバを更新する。
【００８０】
選択されたサーバ拠点からノードｎに至る経路上に存在する各サーバ拠点において、コンテンツｍを保持しておらず、かつ、サーバの空き容量が不足する場合には、コンテンツｍに対する配信回数Ｘｍと、保有するリッチコンテンツ中の配信回数Ｘｊの最小値（Ｘｍｉｎ）を比較し、Ｘｍ＞Ｘｍｉｎの場合には、Ｘｊが最小のコンテンツを消去してコンテンツｍを代わりに蓄積する。
【００８１】
本例では、説明の簡単のため、Ｍ個の全コンテンツのサイズを同一とするが、サイズがコンテンツごとに異なる場合にも容易に拡張が可能である。ただし、ユーザに配信中のコンテンツは消去対象から除く。また、サーバに空き容量が存在する場合には、単にコンテンツｍをキャッシュする。
【００８２】
このようにして、保有するコンテンツに変更が生じた際には、サーバ拠点は、集中制御局（１０２）に対して保有コンテンツの更新情報を通知する。
【００８３】
このように、ＬＦＵにより、キャッシュするコンテンツを更新することで、各キャッシュサーバ拠点において自律的に保有コンテンツの更新を行いつつ、常に人気の高いコンテンツをキャッシュすることが可能となる。
【００８４】
また、コンテンツの人気順位があまり変動しない場合には、過去時間Ｗを大きく設定し、保守的に各コンテンツの人気度を見積もることが望ましく、逆に、人気順位が頻繁に変化する場合には、過去時間Ｗを小さく設定し、より短期の人気傾向を反映させることが望ましいと考えられる。
【００８５】
次に、『３．６  サーバ拠点配置設計法』について説明する。
【００８６】
従来のＣＤＮでは、無数のサーバをＮＷ上に配置するため、サーバの最適配置位置に関する検討はほとんどされておらず、例えば、Ｒｅｐｌｉｃａｔｉｏｎ法においては、全ノードにサーバが存在することを想定し、各コンテンツの配置位置の最適設計を図っている。また、Ｃａｃｈｉｎｇ法においてもサーバの最適配置法に関する検討は少ない。
【００８７】
このため、ＬＦＵ等のキャッシュ置き換えアルゴリズムを想定し、一部のコンテンツのみがキャッシュ可能である場合の、任意トポロジを対象としたサーバ最適配置問題を扱った研究は見られない。
【００８８】
これに対して、本例のキャリア型ＣＤＮでは、限られた拠点に大容量のサーバ群を設置するため、サーバ拠点の配置が性能に大きな影響を与える。そこで、キャリア型ＣＤＮの性能評価に入る前に、サーバ拠点の最適配置法について検討する。
【００８９】
まず、『３．６．１  Ｇｒｅｅｄｙ法による設計アルゴリズム』について説明する。
【００９０】
一般に、サーバ配置問題は、整数計画問題であるため、任意トポロジを対象とした場合、ＮＰ困難な問題となり、非常に小規模なＮＷを除き、近似解法を用いる必要がある。多くの最適配置問題でＧｒｅｅｄｙ法が最良であることから、本例でもＧｒｅｅｄｙ法に基づく設計アルゴリズムを検討する。
【００９１】
キャリアやＩＳＰの立場で最適設計を行う場合、設計目標として、（ｉ）ＮＷ内を流れる総トラヒック量（各リンクを流れるトラヒック量の総和）を最小化する、（ｉｉ）利用率の最も高いリンクの利用率を最小化する、などが考えられる。
【００９２】
本例では、上述の（ｉ）を設計目標の対象として、最適設計を考える。（ｉ）は配信フローの平均ホップ長を最小化することと等価であり、消費ＮＷ資源量を最小化すると同時にユーザのレスポンス時間の改善も期待される。
【００９３】
ある十分に長い時間Ｔ内にノードｎから発生する配信要求数ＲｎのＮＷ全体で発生する配信要求数Ｒに対する比率をｒｎ（ｒｎ＝Ｒｎ／Ｒ）とする。また、ノードｎに収容されているユーザ端末からの配信要求がコンテンツｍに対するものである確率をｑｎ（ｍ）とする。そして、比率ｒｎと確率ｑｎ（ｍ）が、全てのｎ（ノード）とｍ（コンテンツ）に対して既知であるとする。
【００９４】
Ｓ個のサーバ拠点のうち、一つをオリジナルサーバ拠点、他のＣ（Ｃ＝Ｓ−１）個をキャッシュサーバ拠点とし、オリジナルサーバ拠点とキャッシュサーバ拠点の配置問題を分けて考える。
【００９５】
まず、『オリジナルサーバ拠点の配置法』について説明する。
【００９６】
配信フローの平均ホップ長を最小化するためには、他のノードへの最短ホップ経路上のホップ長が短いＮＷの中心に位置するノードにサーバ拠点を配置することが望ましい。
【００９７】
そこで、オリジナルサーバ拠点にはＭ個の全コンテンツが保持されることを考慮し、オリジナルサーバ拠点の配置に対するノードｎの中心度Ｈｏ（ｎ）を次の数５の式で定義する。
【００９８】
【数５】
2010057107.tif 000007
【００９９】
ただし、数５の式において、「ｈｎ,ｉ」は、ノードｎからノードｉに至る最短ホップ経路上のホップ数であり、ｈｎ,ｎ＝０である。そして、中心度Ｈｏ（ｎ）が最大のノードにオリジナルサーバ拠点を設置する。
【０１００】
次に、『キャッシュサーバ拠点の配置法』について説明する。
【０１０１】
オリジナルサーバ拠点を定めた後で、Ｃ個のキャッシュサーバ拠点をＮ−１個の候補中に配置する問題は組合せ最適化問題であり、厳密な最適解を得るためにはＯ（２Ｎ）の次元の計算量が必要になる。そのため、計算時間はＮの増加に伴い指数関数的に増加し、大規模なＮＷに対して厳密解を得ることは困難である。そこでＧｒｅｅｄｙ法による近似最適設計法を検討する。
【０１０２】
各コンテンツのサイズがＬ（ｂｙｔｅｓ）、配信フローの平均ホップ長がｈのとき、期間Ｔ内に各リンクを流れるトラヒック量を全リンクに対して足し合わせた総トラヒック量Ｖ（ｂｙｔｅｓ）は、次の数６の式となる。
【０１０３】
【数６】
2010057107.tif 000008
【０１０４】
ただし、数６の式において、ｈｎはノードｎに対する配信フローの平均ホップ長である。サーバ拠点の位置を変えてもＲ（ＮＷ全体で発生する配信要求数）とＬ（各コンテンツのサイズ）は不変であることから、ＶをＲとＬで除した配信フローの平均ホップ長ｈの最小化を設計目標とする。
【０１０５】
コンテンツのサーバ拠点への展開法としてＣａｃｈｉｎｇ法を想定しているため、各コンテンツｍを保持するサーバ拠点の集合は確率的に変動する。そのため、Ｃ個のキャッシュサーバ拠点配置を定めたときの平均ホップ長ｈを厳密に算出することはできない。
【０１０６】
ただし、ＬＦＵを用いて各キャッシュサーバ拠点で自律的にキャッシュコンテンツを更新する場合、平均的には人気の高いコンテンツがキャッシュされるため、配信フローの平均ホップ長ｈの推定値「ｈ＾」を次の数７の式で定義する。
【０１０７】
【数７】
2010057107.tif 000009
【０１０８】
ただし、上述の数７の式において、「Ｂ」は、キャッシュサーバ拠点のサーバ容量であり、最大でＢ個のコンテンツを保有することが可能である。また、「ｈｎ，ｍｉｎ」と「ｈｎ,ｏ」は、各々、オリジナルサーバ拠点も含めたＳ個の全サーバ拠点の中で、ノードｎからホップ距離が最短のものまでのホップ距離と、オリジナルサーバからノードｎまでのホップ距離である。
【０１０９】
さらに、上述の数７の式において、「Ｑｎ（ｍ）」は「ｑｎ（ｍ）」の累積分布関数であり、「Ｑｎ（ｍ）＝Σｉ＝１ｍｑｎ（ｉ）」である。すなわち、Ｃ個のキャッシュサーバ拠点は、人気の高い上位Ｂ個のコンテンツを保有していると考え、これら上位Ｂ個のコンテンツについては最近接サーバ拠点から、残る「Ｍ−Ｂ」個のコンテンツについてはオリジナルサーバから各ユーザに配信されると考える。
【０１１０】
ところで、キャッシュサーバ拠点数Ｃをどのように設計するかが問題となるが、サーバ容量Ｂが一定であれば、サーバ拠点数Ｃの増加に伴い、平均ホップ長ｈの推定値「ｈ＾」は低減し、ＮＷ内のトラヒック量は削減する。しかし一方でサーバ拠点の構築に要する費用が増加する。
【０１１１】
そこで、キャッシュサーバ拠点全体のサーバ容量を一定値Ｋ（単位はコンテンツ数）で与え、本制約の下で平均ホップ長ｈの推定値「ｈ＾」が最小化するよう、拠点数Ｃも含めて最適設計する。
【０１１２】
このとき、サーバ容量Ｂは「Ｋ÷Ｃ」（サーバ容量の一定値÷サーバ拠点数）を超えない最大の整数値となる。サーバ容量Ｂは「Ｂ≧１」を満たす必要があるため、サーバ拠点数Ｃの許容上限値Ｃｍａｘは、「Ｃｍａｘ＝ｍａｘ（Ｎ−１,Ｋ）」となる。
【０１１３】
また、全コンテンツ数Ｍを超えてサーバ容量Ｂを増加させても平均ホップ長ｈの推定値「ｈ＾」の改善に貢献しないため、サーバ拠点数Ｃの下限値Ｃｍｉｎを「Ｋ÷Ｍ」を下回らない最小の整数値に設定する。
【０１１４】
Ｇｒｅｅｄｙ法を用いたサーバ設置法は、目的関数を最も改善する場所に順次サーバを設置し、一旦、設置したサーバは除去しない方法である。
【０１１５】
既にｊ個のキャッシュサーバ拠点がノード集合Ｎｊに設置された状態で（Ｎ０は全ノード集合Ｎからオリジナルサーバ拠点Ｏを除いたＮ＼Ｏ）、さらにノードｎ（ｎ∈Ｎ＼Ｎｊ）にキャッシュサーバ拠点を設置することで得られる平均ホップ長の推定値「ｈ＾」の削減効果を「Ｅｎ，Ｎｊ」とすると、次の数８の式となる。
【０１１６】
【数８】
2010057107.tif 000010
【０１１７】
尚、数８の式において、「ｈｉ，ｍｉｎ，Ｎｊ」は、ノード集合Ｎｊにキャッシュサーバ拠点が設置された状態における、ノードｉから最近接サーバ拠点までのホップ長である。
【０１１８】
ただし、数８の式において正確には「Ｑｉ（Ｂ）」を乗じる必要があるが、ノードｎの選択場所にかかわらず同じ値を乗じることになるため除いて考える。
【０１１９】
以下の（Ｉ）〜（ＩＶ）に、配信フローの平均ホップ長の推定値「ｈ＾」を最小化する、Ｇｒｅｅｄｙ法によるキャッシュサーバ拠点最適配置アルゴリズムをまとめる。
【０１２０】
（Ｉ）ｋ＝Ｃｍｉｎ、Ｎ０＝Ｎ＼Ｏ、ｊ＝０に初期設定。
（ＩＩ）ｎ∈Ｎ＼Ｎｊの全てのノードｎに対して、数８の式により、削減効果Ｅｎ，Ｎｊを算出。
（ＩＩＩ）削減効果Ｅｎ，Ｎｊが最大のノードｎ＊にキャッシュサーバ拠点を設置し、「ｊ＝ｊ＋１」、「Ｎｊ＝Ｎｊ＋ｎ＊」に更新。
（ＩＶ）ｊ＜ｋの場合には（ＩＩ）に進み、ｊ＝ｋの場合には、Ｃ＝ｋの最適キャッシュサーバ拠点配置における推定平均ホップ長「ｈｋ＾」を、数７の式により算出して、ｋ＝ｋ＋１とし、ｋ＜Ｃｍａｘの場合には（Ｉ）に進み、ｋ＝Ｃｍａｘの場合は「ｈｋ＾」が最小のｋをＣとして選択し、その際のキャッシュサーバ拠点配置を解として出力して終了。
【０１２１】
次に、図２〜図８を用いて、本発明に係る『３．７  性能評価』について説明する。
【０１２２】
まず、『３．７．１  評価条件』について説明する。
【０１２３】
『ＮＷトポロジ』
本例では、評価にはＣＡＩＤＡのＷｅｂページで公開されている３６の商用ＩＳＰのバックボーンＮＷのトポロジを用いる。図２に、これら３６のＮＷの平均ノード次数「Ｅ（ｄ）」と最大ノード次数「Ｍａｘ（ｄ）」の散布状態を示す。本図２より、３６のＮＷを以下の「Ｆｕｌｌ  ｍｅｓｈ」、「Ｈ＆Ｓ」、「Ｌａｄｄｅｒ」の３つのグループに分類する。
【０１２４】
「Ｆｕｌｌ  ｍｅｓｈ」：各ノードが全てのノードと接続するトポロジで、ここでは「Ｅ（ｄ）≧Ｍａｘ（ｄ）−１」と「Ｅ（ｄ）≧３」を満たすＮＷと定義する。図２では２つのＮＷが該当する。
【０１２５】
「Ｈ＆Ｓ」：次数の高いノード（ハブノード）が存在し、最大ノード次数Ｍａｘ（ｄ）が大きい。ハブ＆スポーク型と呼ばれ、航空路線のトポロジが本形態となることが知られている。ハブノードを経由して多数のノードに到達することができるため、フローのホップ長が短い反面、負荷がハブノードに集中しやすい。ここでは「Ｆｕｌｌ  ｍｅｓｈ」以外のＮＷで、「Ｍａｘ（ｄ）≧１０」を満たすＮＷと定義する。図２においては１２のＮＷが該当する。
【０１２６】
「Ｌａｄｄｅｒ」：高次数ノードが存在せず、ループを組み合わせたトポロジ構造となる。平均ノード次数Ｅ（ｄ）と最大ノード次数Ｍａｘ（ｄ）が共に小さい。リンク総延長を抑えることができる反面、遠方のノードに到達するためには多数のノードを経由する必要があり、フローのホップ長が長い。高速道路網が本形態となることが知られている。ここでは「Ｆｕｌｌ  ｍｅｓｈ」以外のＮＷで、「Ｍａｘ（ｄ）＜１０」を満たすＮＷと定義する。図２においては２２のＮＷが該当する。
【０１２７】
『コンテンツ』
本例では、各ノードにおいて、コンテンツの配信要求をポアソン過程で発生させ、発生レートの比率ｒｎを各ノードが存在する都市の人口に比例させる。すなわち、ＮＷ全体での要求発生レートを「Λ」とすると、ノードｎにおける発生レートはｒｎΛとなる。コンテンツ数Ｍは「Ｍ＝１０００」とする。
【０１２８】
ノードｎで生じた各配信要求は、独立に、確率「ｑｎ（ｍ）」でコンテンツｍを選択するが、この確率ｑｎ（ｍ）は全ノードで同一とし、パラメタ「０.２７１」のＺｉｐ分布で与える。また、コンテンツの人気順位は固定とし、各コンテンツの配信に要する時間（転送時間）ＴＬは一定とする。
【０１２９】
シミュレーションでは、Λ＝１／秒、ＴＬ＝１２００秒に設定した。ただし、本発明により求めるサーバ拠点の設計や評価指標である配信フローの平均ホップ長ｈは、「要求発生レートΛ」と「転送時間ＴＬ」の影響を受けない。
【０１３０】
次に、『３．７．２  コンテンツの拡散特性』について説明する。
【０１３１】
全てのコンテンツは、初期状態ではオリジナルサーバ拠点のみに存在するが、ユーザへのコンテンツ配信に伴い、ＮＷ上のＣ個のキャッシュサーバ拠点に拡散していく。
【０１３２】
ここではシミュレーションを用いて、コンテンツの拡散度合いに関して評価する。ただし、「Ｃａｂｌｅ＆Ｗｉｒｅｌｅｓｓ」のトポロジに対して、設置キャッシュサーバ拠点数を「Ｃ＝５」と設定し、推定平均ホップ長「ｈ＾」を最小化する最適キャッシュサーバ拠点配置を総あたり探索した場合（以後、Ｏｐｔｉｍｕｍ法と表記）のサーバ拠点配置を対象とする。
【０１３３】
図３においては、本ＮＷのトポロジと各ノードの人口を示しており、この図３では人口の大きい上位３つのノードを星印で示している。
【０１３４】
人口の大きなノード（ＩＤ：１６，４，１７）への平均的な距離が近く、次数の高いノード（ＩＤ：１０）にオリジナルサーバ拠点が配置されている（図３では二重丸で囲んで示している）。
【０１３５】
また、図３において丸印で囲んで示した５つのノード（ＩＤ：３，４，１２，１６，１７）にキャッシュサーバ拠点が配置されている。
【０１３６】
このように、キャッシュサーバ拠点は、人口の大きなノード（ＩＤ：３，４，１６，１７）や、ノードがまわりに密集しており配信フローのホップ長低減効果の高いノード（ＩＤ：１２）に、配置されることが確認できる。
【０１３７】
図４（ａ）においては、全キャッシュサーバ容量（ＮＷ全体のキャッシュサーバ容量）Ｋを「Ｋ＝１０００」としたときの、５つのキャッシュサーバ拠点（図３におけるＩＤ：３，４，１２，１６，１７）の各々でキャッシュされたコンテンツ数の時系列を示している。
【０１３８】
人口の大きなノードに設置されたキャッシュサーバ拠点ほど配信要求を多く受けるため、コンテンツのキャッシュ数の増加が早い。また、各キャッシュサーバ拠点の容量Ｂは「Ｂ＝２００」であるため、キャッシュ数が「２００」に達した後は一定となる。
【０１３９】
図４（ｂ）においては、人気順位が１番目、１０番目、１００番目、２００番目、１０００番目の各コンテンツの、オリジナルサーバも含めたＮＷ上に存在する全コピー数の時系列を示している。
【０１４０】
この図４（ｂ）に示される内容から、人気の高いコンテンツは、ほぼ全時間にわたり全キャッシュサーバに存在すること、低人気のコンテンツは、全時間にわたりオリジナルサーバにのみ存在すること、また、人気順位がキャッシュサーバ容量Ｂ付近（Ｂ＝２００）のコンテンツのコピー数は変動することが確認できる。
【０１４１】
さらに、図４（ｃ）においては、シミュレーション開始後１０６秒が経過した時点における各コンテンツのコピー数を人気の降順にプロットしている。この図４（ｃ）に示される内容から、人気の高いコンテンツは多数のキャッシュサーバに存在すること、また、人気順位が容量Ｂ（＝２００）近辺のコンテンツのコピー数のばらつきが大きいことが確認できる。
【０１４２】
このように、ＬＦＵを用いて、フローが経由する全キャッシュサーバ拠点のキャッシュを更新する結果、人気順位が容量Ｂ付近のコンテンツのコピー数は、確率的な変動が大きいものの、キャッシュサーバに上位Ｂ個のコンテンツの存在を仮定した上述の数７の式による平均ホップ長の推定は、十分に精度が高いことが予想される。
【０１４３】
図４（ｄ）においては、正規化平均ホップ長（ＮＡＨ：  Ｎｏｒｍａｌｉｚｅｄ  Ａｖｅｒａｇｅ  Ｈｏｐ  ｃｏｕｎｔ）を、全キャッシュサーバ容量Ｋの４つの場合（Ｋ＝１０，１００，１０００，１００００）に対して、キャッシュサーバ拠点数Ｃを変化させてプロットした結果を示している。
【０１４４】
ただし、図４（ｄ）において、ＮＡＨは、配信フローの平均ホップ長を、キャッシュサーバを全く用いないで全てのコンテンツをオリジナルサーバから配信した場合の平均ホップ長で除した値である。また、シミュレーションで得られた実測値を点でプロットし、上述の数７の式で得られる推定値から算出した値を実線で示している。
【０１４５】
いずれの場合も、Ｃ（キャッシュサーバ拠点数）を与えてＯｐｔｉｍｕｍ法によりキャッシュサーバ拠点を配置した。Ｃが大きな場合、人気順位が容量Ｂ近辺のコンテンツのコピー数のばらつきが大きくなることから、推定精度が若干悪化する。
【０１４６】
しかし、ＮＷ全体のキャッシュサーバ容量Ｋとキャッシュサーバ拠点数Ｃの広い領域で、上述の数７の式により得られる平均ホップ長の推定値は十分に精度が高いことが確認できる。
【０１４７】
そこで、以後はシミュレーションを用いず、推定値を用いて各種設計、ＮＡＨの評価を行う。
【０１４８】
以下、『３．７．３  Ｃａｂｌｅ＆Ｗｉｒｅｌｅｓｓにおけるサーバ拠点配置法の比較』について説明する。
【０１４９】
ここでは、「Ｃａｂｌｅ＆Ｗｉｒｅｌｅｓｓ」のトポロジを対象に、本発明の中心度に基づくキャッシュサーバ拠点配置法（以後、Ｃｅｎｔｒａｌｉｔｙ法と表記）を適用したときの効果を評価する。
【０１５０】
比較のため、単にノード次数の高いノードから順に配置する場合（以後、Ｄｅｇｒｅｅ法と表記）と、人口の大きなノードから順に配置する場合（以後、Ｐｏｐｕｌａｔｉｏｎ法と表記）の結果も合わせて示す。
【０１５１】
多くのフローは高次数ノードを経由すること、また、人口の大きなノードから多数の配信要求が生じることから、いずれの比較方式も平均ホップ長の低減効果が期待される。
【０１５２】
図５（ａ）においては、ＮＷ全体のキャッシュサーバ容量Ｋを変化させたときの正規化平均ホップ長ＮＡＨを示している。Ｋ（全キャッシュサーバ容量）の増加に伴いＮＡＨは低減し、各リンクを流れるトラヒック量が削減されるが、Ｋの増加に伴うＮＡＨの削減効果はＫの小さい領域で顕著である。
【０１５３】
次数に基づきキャッシュサーバ拠点を配置した場合、他の設計法と比較して性能が大きく劣化するが、Ｃｅｎｔｒａｌｉｔｙ法とＰｏｐｕｌａｔｉｏｎ法は、ほぼ厳密最適解（Ｏｐｔｉｍｕｍ法）と同等の性能を達成する。
【０１５４】
また、ＮＷ全体のキャッシュサーバ容量Ｋを１０から１０,０００の範囲で変化させて各配置法におけるキャッシュサーバ拠点位置を確認したところ、Ｐｏｐｕｌａｔｉｏｎ法は若干Ｏｐｔｉｍｕｍ法と配置位置が異なるが、Ｃｅｎｔｒａｌｉｔｙ法は完全にＯｐｔｉｍｕｍ法と一致することが確認された。
【０１５５】
また、図５（ｂ）においては、最適設置キャッシュサーバ拠点数Ｃを同様にプロットした様子を示している。この図５（ｂ）に示すように、Ｄｅｇｒｅｅ法のみ突出して最適設置キャッシュサーバ拠点数Ｃが大きいが、他の三つの設計法ではほぼ同数のＣが最適となっている。Ｋ（全キャッシュサーバ容量）の増加に伴い最適なＣは増加するが、Ｋの小さな領域ではＤｅｇｒｅｅ法を除きＣの最適値は小さい。
【０１５６】
この理由を調べるため、図５（ｃ）において、最適設置キャッシュサーバ拠点数Ｃを固定させ、各キャッシュサーバの容量Ｂを変化させたときのＮＡＨ（正規化平均ホップ長）を示す。Ｂの増加に伴うＮＡＨの低減効果はＢの小さい領域で顕著であることが確認できる。
【０１５７】
このため、Ｋ（全キャッシュサーバ容量）が小さい場合、キャッシュサーバ拠点数Ｃを増やすよりも、Ｃを抑えて代わりに各拠点の容量Ｂを大きくすることが、ＮＡＨを低減させる上で効果的でありＣの最適値は小さくなる。
【０１５８】
次に、『３．８  様々なＮＷにおける配置法の比較』について説明する。
【０１５９】
ここまでは、「Ｃａｂｌｅ＆Ｗｉｒｅｌｅｓｓ  ｎｅｔｗｏｒｋ」を対象に評価を行ったが、以下、様々なＮＷを対象にキャッシュサーバ拠点配置法の効果を比較する。
【０１６０】
まず、三つの近似最適設計法をＯｐｔｉｍｕｍ法と比較するが、ノード数Ｎの大きなＮＷを対象に厳密最適解を得ることは困難であるため、Ｎが２２以下の１８のＮＷを対象に正規化平均ホップ長ＮＡＨを比較する。
【０１６１】
図６（ａ）〜（ｃ）においては、ＮＷ全体のキャッシュサーバ容量Ｋを「Ｋ＝１００」とした場合の三つの近似最適設計法の各々におけるＮＡＨ（正規化平均ホップ長）をＯｐｔｉｍｕｍ法におけるＮＡＨに対してプロットした結果を示し、図６（ｄ）〜（ｆ）においては、Ｋ＝１０００とした場合の結果を同様に示す。
【０１６２】
図６（ａ）〜（ｆ）のそれぞれにおいて、直線ｙ＝ｘ上にプロットされている場合に、近似最適設計法が厳密最適解と同じ性能を達成することを意味するが、図６（ａ），（ｃ），（ｄ），（ｆ）に示すように、Ｃｅｎｔｒａｌｉｔｙ法もしくはＰｏｐｕｌａｔｉｏｎ法を用いることで、１８のＮＷの全てにおいて厳密最適解が得られることが確認できるが、図６（ｂ），（ｄ）に示すように、Ｄｅｇｒｅｅ法を用いた場合には、性能が大きく劣化する。
【０１６３】
図７（ａ）〜（ｃ）においては、３６の全てのＮＷを対象に、Ｃｅｎｔｒａｌｉｔｙ法とＰｏｐｕｌａｔｉｏｎ法の性能を比較した結果を示している。また、本図７（ａ）〜（ｃ）においては、Ｃｅｎｔｒａｌｉｔｙ法とＰｏｐｕｌａｔｉｏｎ法におけるＮＡＨ（正規化平均ホップ長）の散布図を３６のＮＷを対象にＫ（ＮＷ全体のキャッシュサーバ容量）の三つの場合（Ｋ＝１００，１０００，１００００）について各々示している。
【０１６４】
本図７（ａ）〜（ｃ）の内容から、全ノード集合Ｎが２２を超える大規模ＮＷの多くで、Ｐｏｐｕｌａｔｉｏｎ法の性能がＣｅｎｔｒａｌｉｔｙ法と比較して劣化することが確認できる。また、劣化度合いは、全キャッシュサーバ容量Ｋが大きく、キャッシュサーバ拠点数Ｃが増加するほど大きいことが確認できる。
【０１６５】
例えば図７（ｂ）に示すように、Ｋ＝１０００のとき、Ｐｏｐｕｌａｔｉｏｎ法はＣｅｎｔｒａｌｉｔｙ法と比較してＮＡＨが１０％〜２０％程度劣化する。全ノード集合Ｎとキャッシュサーバ拠点数Ｃが共に小さい場合、単に人口の大きなノードから順にキャッシュサーバ拠点を配置しても十分な性能が得られるが、Ｎ（全ノード集合）やＣ（キャッシュサーバ拠点数）が大きく配信フローの設置パタンが複雑化する場合、本例で示したＣｅｎｔｒａｌｉｔｙ法を用いることが有効である。
【０１６６】
三つの近似最適配置法（Ｐｏｐｕｌａｔｉｏｎ法、Ｄｅｇｒｅｅ法、Ｃｅｎｔｒａｌｉｔｙ法）の計算量はどれもＯ（Ｎ３）（Ｎ：全ノード集合）であり、Ｐｏｐｕｌａｔｉｏｎ法やＤｅｇｒｅｅ法を用いる積極的な理由はなく、どのような場合にもＣｅｎｔｒａｌｉｔｙ法を用いることが望ましい。
【０１６７】
また、図７（ｂ）より、キャリア型ＣＤＮにおいてオリジナルサーバの容量と同量程度（Ｋ（全キャッシュサーバ容量）＝Ｍ（全コンテンツ数）＝１０００）のキャッシュサーバ容量をＮＷ上の限られた拠点に適切に配置することで、配信フローの平均ホップ長を３０％〜７０％程度、低減できることが確認できる。
【０１６８】
このことは、ＮＷ中を流れる総トラヒック量や各リンクの平均トラヒック量も、同様に３０％〜７０％程度、削減されることを意味する。
【０１６９】
また、ノード間のホップ長が長い傾向のあるＬａｄｄｅｒ型のＮＷが、Ｈ＆Ｓ型のＮＷと比較してキャリア型ＣＤＮの効果が高い。
【０１７０】
図８（ａ）〜（ｃ）においては、Ｃｅｎｔｒａｌｉｔｙ法を用いてキャッシュサーバ拠点を最適配置した場合の、正規化キャッシュサーバ拠点数（Ｃ／（Ｎ−１））をＫ（全キャッシュサーバ容量）に対してプロットした結果を、ＮＷ種別（Ｆｕｌｌ  ｍｅｓｈ  ｎｅｔｗｏｒｋｓ，Ｈ＆Ｓ  ｎｅｔｗｏｒｋｓ，Ｌａｄｄｅｒ  ｎｅｅｏｒｋｓ）ごとに分けて示している。
【０１７１】
図８（ｃ）に示すＬａｄｄｅｒ型ＮＷは、キャッシュサーバ拠点を設置することによるフローの平均ホップ長の低減効果が高く、容量Ｂを減らしても多数の拠点に設置することが有効な傾向が見られる。
【０１７２】
例えば、全キャッシュサーバ容量Ｋ＝Ｍ（全コンテンツ数）程度である場合、多くのＮＷではキャッシュサーバ拠点の最適配置数が「Ｎ（全ノード集合）−１」の１０％〜４０％程度であり、限られた箇所に限定して大容量のキャッシュサーバ拠点を設置することが望ましい。
【０１７３】
以上、図１〜図９を用いて説明したように、本例では、キャリア型ＣＤＮにおいて、配信フローの平均ホップ長を最小化し、各リンクの平均負荷を最小化するよう、オリジナルサーバ拠点とキャッシュサーバ拠点を最適配置する。
【０１７４】
すなわち、キャリアが自身のネットワーク（ＮＷ）の限定された拠点に、大容量のデータセンタを構築し、ＣＤＮを運用するキャリア型ＣＤＮにおいて、全てのコンテンツを常に収容するオリジナルサーバ拠点を１つ配置し、さらに、保有するコンテンツをユーザからの配信要求に基づいて、例えばＬＦＵにより更新するキャッシュサーバ拠点を複数のデータセンタに配置する。
【０１７５】
例えば、ＮＷトポロジと、各ノードから各コンテンツに対する配信要求発生頻度とが与えられたときに、配信フローの平均ホップ長が最小化するよう、一つのオリジナルサーバ拠点と、任意個数のキャッシュサーバ拠点を最適配置する。
【０１７６】
特に、各ノードｎに対して、ノードｎから各ノードに至る最短経路上のホップ数を要求発生数比で重み付けした総和の逆数でノードｎの中心度Ｈｏ（ｎ）を定義し、この中心度が最大のノードにオリジナルサーバを配置する。
【０１７７】
また、ＮＷ全体のキャッシュサーバ容量Ｋを与え、各キャッシュサーバの容量Ｂを配置キャッシュサーバ拠点数Ｃに対して一定値（Ｂ＝ｆｌｏｏｒ（Ｋ／Ｃ））で与え、配置キャッシュサーバ拠点数Ｃも含めてキャッシュサーバ拠点を最適配置する。
【０１７８】
また、ｈｎ，ｍｉｎとｈｎ,ｏを各々、オリジナルサーバ拠点も含めたＳ個の全サーバ拠点の中でノードｎからホップ距離が最短のものまでのホップ距離と、オリジナルサーバからノードｎまでのホップ距離とし、さらに、Ｑｎ（ｍ）をノードｎからの配信要求がコンテンツｍに対するものである確率ｑｎ（ｍ）の累積分布関数とし、そして、ｒｎをノードｎからの要求発生比率とするとき、上述の数７の式で配信フローの平均ホップ長を推定する。
【０１７９】
また、ｈｉ，ｍｉｎ，Ｎｊを、Ｎｊにキャッシュサーバ拠点が設置された状態における、ノードｉから最近接サーバ拠点までのホップ長とするとき、既にｊ個のキャッシュサーバ拠点がノード集合Ｎｊに設置された状態で（Ｎ０は全ノード集合Ｎからオリジナルサーバ拠点Ｏを除いたＮ＼Ｏ）、さらにノードｎ（ｎ∈Ｎ＼Ｎｊ）にキャッシュサーバ拠点を設置することで得られる推定平均ホップ長ｈ＾の削減効果Ｅｎ、Ｎｊを、上述の数８により算出し、Ｅｎ、Ｎｊが最大のノードから順にキャッシュサーバ拠点を配置していく。
【０１８０】
本例によれば、キャリア型ＣＤＮにおいて、配信フローの平均ホップ長を最小化し、各リンクの平均負荷を最小化するよう、オリジナルサーバ拠点とキャッシュサーバ拠点を最適配置することができ、キャリア型ＣＤＮのネットワーク内に流れるトラヒック総量の最小化を図ることが可能となる。
【０１８１】
尚、本発明は、図１〜図９を用いて説明した例に限定されるものではなく、その要旨を逸脱しない範囲において種々変更可能である。例えば、本例では、キャリア型ＣＤＮにおけるサーバ配置に関して説明しているが、他の、一元管理されたネットワークにおけるサーバ配置にも適用可能である。
【０１８２】
すなわち、ネットワークを介してサーバコンピュータからコンテンツを、当該コンテンツの要求元のクライアントコンピュータに配信するネットワークにおいて、サーバコンピュータとして、全てのコンテンツを記憶する１つのオリジナルサーバシステムと、このオリジナルサーバシステムが記憶するコンテンツの幾つかを記憶してクライアントコンピュータからの配信要求に応じて当該コンテンツを配信すると共に配信したコンテンツに対するＬＦＵによるキャッシュ制御を行う複数のキャッシュサーバシステムとを設け、オリジナルサーバシステムとキャッシュサーバシステムのそれぞれを本発明により選択したノードに配置する構成としても良い。
【０１８３】
また、本例のコンピュータ構成例に関しても、キーボードや光ディスクの駆動装置の無いコンピュータ構成としても良い。また、本例では、光ディスクを記録媒体として用いているが、ＦＤ（Ｆｌｅｘｉｂｌｅ  Ｄｉｓｋ）等を記録媒体として用いることでも良い。また、プログラムのインストールに関しても、通信装置を介してネットワーク経由でプログラムをダウンロードしてインストールすることでも良い。
【図面の簡単な説明】
【０１８４】
【図１】本発明に係るサーバ配置システムを設けたキャリア型ＣＤＮのネットワーク構成例を示すブロック図である。
【図２】３６個のネットワークの平均ノード次数と最大ノード次数の散布状況例を示す説明図である。
【図３】Ｃａｂｏｅ＆Ｗｉｒｅｌｅｓｓのトポロジ例とノード人口状況例を示す説明図である。
【図４】Ｃａｂｏｅ＆Ｗｉｒｅｌｅｓｓに対する本発明のシミュレーション結果例を示す説明図である。
【図５】Ｃａｂｏｅ＆Ｗｉｒｅｌｅｓｓに対する本発明による設計結果例を示す説明図である。
【図６】１８個のネットワークにおける性能比較例を示す説明図である。
【図７】３６個のネットワークにおける性能比較例を示す説明図である。
【図８】３６個のネットワークにおける正規化キャッシュサーバ数を示す説明図である。
【図９】図１におけるサーバ拠点配置装置による本発明に係るサーバ配置手順例を示すフローチャートである。
【符号の説明】
【０１８５】
１０１：サーバ拠点配置装置、１０２：集中制御局、１０３：コンテンツサーバ、１０４：サーバ選択装置、１０５：ユーザ端末。
【図１】
2010057107.tif 000013
【図２】
2010057107.tif 000014
【図３】
2010057107.tif 000015
【図４】
2010057107.tif 000016
【図５】
2010057107.tif 000017
【図６】
2010057107.tif 000018
【図７】
2010057107.tif 000019
【図８】
2010057107.tif 000020
【図９】
2010057107.tif 000021