(57)【特許請求の範囲】
【請求項１】
転送装置の接続関係を示すトポロジ情報を用いて、データをキャッシュする転送装置と、当該データを要求する拠点に在る転送装置にデータを配信する際に当該データを中継する転送装置を示す経路との組合せを、当該データに対するアクセス回数が多いほど、当該データをキャッシュする転送装置の数が多く、かつ、当該データを転送する経路が短くなるように抽出する抽出部と、
前記抽出部が抽出する組合せごとに、当該組合せに含まれる各転送装置がデータをキャッシュする際に消費する電力量と、該組合せに含まれる経路上の転送装置が前記データを配信する際に消費する電力量との和を算出する算出部と、
前記抽出部が抽出する組合せのうち、前記算出部が算出した電力量の和が最小となる組合せを選択する選択部と、
前記選択部が選択する組合せを示す情報を出力する出力部と
を有することを特徴とする配置サーバ。
【請求項２】
前記抽出部は、各転送装置の接続関係から、データをキャッシュする転送装置をルートとし、当該ルートから各転送装置までの段数が最短となる配信木を識別し、当該識別した配信木において各転送装置を接続する枝を前記経路とすることを特徴とする請求項１に記載の配置サーバ。
【請求項３】
前記抽出部は、前記データをキャッシュしない転送装置が、前記データをキャッシュする転送装置を始点とする経路のいずれかに含まれるように、前記データをキャッシュする転送装置と、前記経路との組合せを抽出することを特徴とする請求項１または２に記載の配置サーバ。
【請求項４】
前記抽出部は、前記データをキャッシュする転送装置から前記データをキャッシュしない転送装置までの経路が単一の経路となるように、前記データをキャッシュする転送装置と、前記経路との組合せを抽出することを特徴とする請求項３に記載の配置サーバ。
【請求項５】
前記抽出部は、前記転送装置が転送するデータと、各データに対するアクセス要求の回数とを対応付けたデータ情報を用いて、アクセス要求の回数が多いデータから順に、当該データをキャッシュする転送装置と、当該データを保有するオリジンサーバと同一の拠点にあるオリジンサーバを持ち、かつ、当該データよりもアクセス要求の回数が多いデータについて前記選択部が選択した組合せの経路を含む経路との組合せを抽出することを特徴とする請求項１−４のいずれか１つに記載の配置サーバ。
【請求項６】
前記出力部は、各転送装置がデータをキャッシュ可能なＣＣＮ上でデータをキャッシュする転送装置を前記選択部が選択した組合せに基づいて特定し、各転送装置がキャッシュするデータを示すキャッシュリストを各転送装置に配布することを特徴とする請求項１−５のいずれか１つに記載の配置サーバ。
【請求項７】
データのキャッシュ機能とデータの配信機能とを有する複数の転送装置と、
各転送装置がキャッシュするデータと当該データを配信する経路とを指定する配置サーバとを有する情報処理システムにおいて、
前記配置サーバは、
前記転送装置の接続関係を示すトポロジ情報を用いて、データをキャッシュする転送装置と、当該データを要求するクライアントがいる拠点の転送装置にデータを配信する際に当該データを中継する転送装置を示す経路との組合せを、当該データに対するアクセス回数が多いほど、当該データをキャッシュする転送装置の数が多く、かつ、当該データを転送する経路が短くなるように抽出する抽出部と、
前記抽出部が抽出する組合せごとに、当該組合せに含まれる各転送装置がデータをキャッシュする際に消費する電力量と、該組合せに含まれる経路上の転送装置が前記データを配信する際に消費する電力量との和を算出する算出部と、
前記抽出部が抽出する組合せのうち、前記算出部が算出した電力量の和が最小となる組合せを選択する選択部と、
前記選択部が選択する組合せに基づいて、各転送装置がキャッシュするデータを指定する配置情報を生成し、生成した配置情報を各転送装置に対して配信する配信部と
を有し、
前記転送装置は、前記配信部が配信した前記配置情報に基づいて、データのキャッシュを行うことを特徴とする情報処理システム。
【請求項８】
複数の転送装置に対して、各転送装置がキャッシュするデータと、当該データを配信する経路とを指定する配置サーバが、
前記転送装置の接続関係を示すトポロジ情報を用いて、データをキャッシュする転送装置と、当該データを要求するクライアントがいる拠点の転送装置にデータを配信する際に当該データを中継する転送装置を示す経路との組合せを、当該データに対するアクセス回数が多いほど、当該データをキャッシュする転送装置の数が多く、かつ、当該データを転送する経路が短くなるように抽出し、
前記抽出した組合せごとに、当該組合せに含まれる各転送装置がデータをキャッシュする際に消費する電力量と、該組合せに含まれる経路上の転送装置が前記データを配信する際に消費する電力量との和を算出し、
前記抽出した組合せのうち、前記算出された電力量の和が最小となる組合せを選択し、
前記選択した組合せに基づいて、各転送装置がキャッシュするデータを指定する配置情報を生成し、生成した配置情報を各転送装置に対して配信する
処理を実行することを特徴とするキャッシュ配置方法。
【請求項９】
転送装置の接続関係を示すトポロジ情報を用いて、データをキャッシュする転送装置と、当該データを要求するクライアントがいる拠点の転送装置にデータを配信する際に当該データを中継する転送装置を示す経路との組合せを、当該データに対するアクセス回数が多いほど、当該データをキャッシュする転送装置の数が多く、かつ、当該データを転送する経路が短くなるように抽出し、
前記抽出した組合せごとに、当該組合せに含まれる各転送装置がデータをキャッシュする際に消費する電力量と、該組合せに含まれる経路上の転送装置が前記データを配信する際に消費する電力量との和を算出し、
前記抽出した組合せのうち、前記算出された電力量の和が最小となる組合せを選択し、
前記選択した組合せに基づいて、各転送装置がキャッシュするデータを指定する配置情報を生成し、生成した配置情報を各転送装置に対して配信する
処理をコンピュータに実行させることを特徴とするキャッシュ配置プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、配置サーバ、情報処理システム、キャッシュ配置方法、キャッシュ配置プログラムに関する。
【背景技術】
【０００２】
従来、ネットワークにおけるトラフィック量を削減し、ネットワーク機器が消費する電力を削減する技術が知られている。このような技術の一例として、コア網やメトロ網において、コンテンツの複製を複数のサーバに配置し、ユーザと地理的に近いサーバからコンテンツの配信を行うＣＤＮ（Ｃｏｎｔｅｎｔ  Ｄｅｌｉｖｅｒｙ  Ｎｅｔｗｏｒｋ）の技術が知られている。このようなＣＤＮの技術が適用されたネットワークでは、コンテンツの配信をネットワークエッジで処理するので、ネットワークに流入するトラフィック量を削減し、ネットワーク機器が消費する電力を削減する。
【０００３】
また、ネットワーク上のルータにキャッシュ機能を付与することで、コンテンツのキャッシュ配置の制約を緩和するＣＣＮ（Ｃｏｎｔｅｎｔ  Ｃｅｎｔｒｉｃ  Ｎｅｔｗｏｒｋｉｎｇ）の技術が知られている。このようなＣＣＮの技術が適用されたネットワークでは、メトロ網やコア網のルータにコンテンツの複製をキャッシュさせ、ルータがキャッシュしたコンテンツを配信することで、ネットワークに流入するトラフィック量を削減し、ネットワーク機器が消費する電力や機器配備コストを削減する。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特開２０１０−１９９７３６号公報
【発明の概要】
【発明が解決しようとする課題】
【０００５】
しかしながら上述したコンテンツの複製をサーバやルータにキャッシュさせる技術では、ネットワークのトラフィック量だけを考慮したキャッシュ配置を行うので、ネットワークで消費される電力や機器配備に伴うコストを適切に削減できないという問題がある。
【０００６】
すなわち、サーバやルータは、コンテンツの複製をキャッシュすると、コンテンツの配信を行わずともメモリ利用に伴う電力消費が発生し、あるいは、メモリ配備に伴うコストが発生する。このため、ネットワークは、コンテンツの複製を多くのサーバやルータにキャッシュさせた場合は、コンテンツの複製をキャッシュするための電力量や機器コストを増大させてしまい、消費する電力や機器コストを適切に削減できない。
【０００７】
本願に開示の技術は、上述した問題に鑑みてなされたものであり、ネットワークにおける消費電力を削減する。なお本願の技術は、消費電力量だけでなく、機器配備コストを削減する仕組みとして解釈することもできるため、後述の電力は機器コストと置き換えてもよい。
【課題を解決するための手段】
【０００８】
１つの側面では、各転送装置がキャッシュするデータを指定する配置サーバである。このような配置サーバは、転送装置の接続関係を示すトポロジ情報を用いて、データをキャッシュする転送装置と、当該データを要求する拠点に在る転送装置にデータを配信する際に当該データを中継する転送装置を示す経路との組合せを、当該データに対するアクセス回数が多いほど、当該データをキャッシュする転送装置の数が多く、かつ、当該データを転送する経路が短くなるように抽出する。また、配置サーバは、抽出した組合せごとに、当該組合せに含まれる各転送装置がデータをキャッシュする際に消費する電力量と、該組合せに含まれる経路上の転送装置がデータを配信する際に消費する電力量との和を算出する。そして、配置サーバは、抽出した組合せのうち、算出した電力量の和が最小となる組合せを選択する。その後、配置サーバは、選択した組合せを示す情報を出力する。
【発明の効果】
【０００９】
１つの側面では、ネットワークにおける消費電力を削減する。
【図面の簡単な説明】
【００１０】
【図１】図１は、実施例１に係る情報処理システムを説明するための図である。
【図２】図２は、トポロジ情報が示すネットワークを説明するための図である。
【図３】図３は、トポロジ情報の一例を説明するための図である。
【図４】図４は、ルータの機能を説明するための図である。
【図５】図５は、実施例１に係るキャッシュ配置サーバの機能構成を説明するための図である。
【図６】図６は、配信木の一例を説明するための図である。
【図７】図７は、変数ｓが示す経路の候補を説明するための図である。
【図８】図８は、経路の候補を示す情報の一例を説明するための図である。
【図９】図９は、リクエストリストの一例を説明するための図である。
【図１０】図１０は、トータルリクエストリストの一例を説明するための図である。
【図１１】図１１は、配信経路に係る制約条件の一例を説明するための第１の図である。
【図１２】図１２は、配信経路に係る制約条件の一例を説明するための第２の図である。
【図１３】図１３は、ルータの電力効率を説明するための図である。
【図１４Ａ】図１４Ａは、キャッシュ階層制約を説明するための第１の図である。
【図１４Ｂ】図１４Ｂは、キャッシュ階層制約を説明するための第２の図である。
【図１５】図１５は、シミュレーションの対象となるネットワークの一例を説明するための図である。
【図１６】図１６は、各ルータに接続されたオリジンサーバが記憶するコンテンツを説明するための図である。
【図１７】図１７は、リクエストの分布の一例を説明するための図である。
【図１８】図１８は、キャッシュ配置サーバが配布するキャッシュリストの一例を説明するための図である。
【図１９】図１９は、コンテンツＡのキャッシュ位置の一例を説明するための図である。
【図２０】図２０は、コンテンツＢのキャッシュ位置の一例を説明するための図である。
【図２１】図２１は、コンテンツＣのキャッシュ位置の一例を説明するための図である。
【図２２】図２２は、バックボーンネットワーク全体が消費する電力を説明するための図である。
【図２３】図２３は、各ルータがキャッシュするデータ量を説明するための図である。
【図２４】図２４は、キャッシュ配置サーバがトポロジ情報を用いて実行する処理の流れを説明するためのフローチャートである。
【図２５】図２５は、キャッシュ配置サーバがコンテンツのキャッシュ位置を選択する処理の流れを説明するためのフローチャートである。
【図２６】図２６は、キャッシュ配置プログラムを実行するコンピュータの一例を説明するための図である。
【発明を実施するための形態】
【００１１】
以下に添付図面を参照して本願に係る配置サーバ、情報処理システム、キャッシュ配置方法、キャッシュ配置プログラムについて説明する。
【実施例１】
【００１２】
以下の実施例１では、図１を用いて、情報処理システム１の一例について説明する。図１は、実施例１に係る情報処理システムを説明するための図である。図１に示す例では、情報処理システム１は、ＣＰ（Content  Provider）２、キャッシュ配置サーバ１０、バックボーンネットワーク３０を有する。
【００１３】
ＣＰ２は、ネットワークサービス事業者が管理するバックボーンネットワーク３０を介して、利用者にコンテンツを提供する。また、ネットワークサービス事業者が管理するキャッシュ配置サーバ１０は、バックボーンネットワーク３０の各ルータ３１〜４４に接続されるサーバであり、ＣＰ２から登録されるコンテンツを記憶するサーバであるオリジンサーバの情報を管理する。また、キャッシュ配置サーバ１０は、バックボーンネットワーク３０の各ルータ３１〜４４の接続関係を示すトポロジ情報を記憶する。
【００１４】
ここで、図２および図３を用いて、キャッシュ配置サーバ１０において管理されるトポロジ情報について説明する。図２は、トポロジ情報が示すネットワークを説明するための図である。また、図３は、トポロジ情報の一例を説明するための図である。例えば、キャッシュ配置サーバ１０は、図２に示す４台のルータ＃０〜ルータ＃３の接続関係を示すトポロジ情報を記憶する。すなわち、キャッシュ配置サーバ１０は、ルータ＃０とルータ＃１、ルータ＃０とルータ＃２、ルータ＃１とルータ＃３が接続されている旨を示すトポロジ情報を記憶する。
【００１５】
具体的には、図３に示すように、キャッシュ配置サーバ１０は、行列形式のトポロジ情報を記憶する。すなわち、キャッシュ配置サーバ１０は、トポロジ情報の各行と各列とにルータ＃０〜ルータ＃３を対応付ける。そして、キャッシュ配置サーバ１０は、各要素について、行に対応付けられたルータと列に対応付けられたルータとが接続されている場合には、接続を示す情報として「１」を格納する。例えば、図３に示す例では、トポロジ情報は、ルータ＃０にルータ＃１とルータ＃２とが接続され、ルータ＃１にルータ＃３が接続されている旨を示す。
【００１６】
図１に戻って、バックボーンネットワーク３０は、ネットワークの拠点となる複数のルータ３１〜４４を有する。各ルータ３１〜４４は、バックボーンネットワーク３０におけるコンテンツ配信の拠点である。また、各ルータ３１〜４４は、それぞれコンテンツのデータをキャッシュする機能と、利用者（クライアント）からの要求に基づいて、コンテンツを配信する機能を有する。
【００１７】
次に、図４を用いて、実施例１に係るルータ３１〜４４が有する機能について説明する。図４は、ルータの機能を説明するための図である。なお、図４に示す例では、アクセス対象となるコンテンツを、オリジンサーバ４５だけが保持している場合を示す。また、図４に示す例では、アクセス元となるクライアント５０が、ネットワーク４６を介してルータ３５と接続されており、オリジンサーバ４５が記憶するコンテンツに対して、クライアント５０がアクセス要求を発行するものとする。
【００１８】
例えば、ルータ３５は、クライアント５０からネットワーク４６を介してオリジンサーバ４５が保持するコンテンツの配信要求を受信した場合、ルータ３６にコンテンツの配信要求を送信する。同様に、ルータ３６では、ルータ３５から受信した配信要求をルータ３３に転送する。
【００１９】
そして、ルータ３３は、ルータ３５から配信要求を受信した場合、自装置の拠点にあるオリジンサーバ４５へ配信要求を送信する。その結果、オリジンサーバ４５より配信されたコンテンツのデータを、ルータ３６に転送する。さらに、ルータ３６は、ルータ３３から受信したコンテンツのデータをルータ３５へ送信する。その後、ルータ３５は、クライアントに対して、ルータ３６から受信したコンテンツを送信する。
【００２０】
ここで、ルータ３３、ルータ３５、ルータ３６がコンテンツをキャッシュする機能を有するコンテンツルータである場合には、ルータ３３、ルータ３５、ルータ３６は、以下の処理を実行する。すなわち、ルータ３３、ルータ３５、ルータ３６は、送信したコンテンツの複製をキャッシュする。そして、ルータ３３、ルータ３５、ルータ３６は、同様の配信要求を受信した場合には、配信要求の転送を行わず、自身がキャッシュしたコンテンツを配信要求元に送信する。
【００２１】
さらに、ルータ３３、ルータ３５、ルータ３６において、配信要求の対象となるコンテンツをキャッシュした場合には、バックボーンネットワーク３０に流入するトラフィック量が減少するものの、キャッシュされるデータ量が増大する。この結果、ルータ３３、ルータ３５、ルータ３６は、コンテンツのデータを転送する際に消費する電力を削減するものの、コンテンツのデータをキャッシュするために要する電力を増加させてしまう。
【００２２】
そこで、ルータ３３、ルータ３５、ルータ３６は、クライアントからのアクセス回数に応じて、クライアントに近いルータ、または、コンテンツを記憶するサーバに近いルータがキャッシュする。つまり、クライアント５０からのアクセス回数が多いコンテンツについては、クライアント５０から近いルータ３５がキャッシュし、クライアント５０からのアクセス回数が少ないコンテンツについては、クライアント５０から遠いルータ３３がキャッシュする。
【００２３】
例えば、各ルータ３３〜３５は、キャッシュ配置サーバ１０からの要求に応じて、各コンテンツに対するアクセス回数を示すリクエストリストを生成し、生成したリクエストリストをキャッシュ配置サーバ１０に送信する。そして、各ルータ３３〜３５は、キャッシュ配置サーバ１０が配布するキャッシュリストに従って、コンテンツデータのキャッシュを行う。
【００２４】
次に、キャッシュ配置サーバ１０が実行する処理について説明する。キャッシュ配置サーバ１０は、管理対象とするネットワークトポロジ情報を保持する。また、キャッシュ配置サーバ１０は、各ルータ３１〜４４から、リクエストリストを取得する。そして、キャッシュ配置サーバ１０は、トポロジ情報を用いて、コンテンツをキャッシュ可能なルータを抽出する。また、キャッシュ配置サーバ１０は、トポロジ情報を用いて、コンテンツをキャッシュしたルータから、該当コンテンツを要求するクライアントがいる拠点のルータまでの、コンテンツ配信経路を抽出する。
【００２５】
なお、キャッシュ配置サーバ１０は、コンテンツを配信する経路を抽出する場合には、以下の制約を満たす経路を抽出する。すなわち、キャッシュ配置サーバ１０は、コンテンツを保有するオリジンサーバが在る拠点のルータを始点とする各拠点までの配信経路を抽出する。また、キャッシュ配置サーバ１０は、各始点ルータから全拠点のルータへ配信される経路を抽出する。さらに、キャッシュ配置サーバ１０は、コンテンツをキャッシュするルータが一意に定まるように、経路を抽出する。また、キャッシュ配置サーバ１０は、あるコンテンツを配信する経路上には、同一のコンテンツがキャッシュされないように経路を抽出する。
【００２６】
また、キャッシュ配置サーバ１０は、取得したリクエストリストを用いて、キャッシュ対象となるコンテンツを、アクセス回数順に識別する。そして、キャッシュ配置サーバ１０は、アクセス回数が多い順に、コンテンツをキャッシュするルータと、コンテンツを配信する経路との組合せを、あらかじめ抽出したルータおよび経路から選択する。
【００２７】
詳細には、キャッシュ配置サーバ１０は、コンテンツを保有するオリジンサーバが在る拠点のルータを選択し、選択したルータをルートとする経路を選択する。また、キャッシュ配置サーバ１０は、あるコンテンツについて経路を選択する場合は、同一のオリジンサーバが記憶するコンテンツであって、アクセス回数が多いコンテンツについて選択した経路を含む経路を選択する。すなわち、キャッシュ配置サーバ１０は、アクセス回数が多いほど、コンテンツをキャッシュするルータの数が多く、かつ、コンテンツを配信する経路が短くなるように、経路を選択する。
【００２８】
そして、キャッシュ配置サーバ１０は、選択した全ての組合せについて、コンテンツをキャッシュする際に消費する電力量と、選択した経路を介してコンテンツを配信する際に消費する電力量との和を算出する。その後、キャッシュ配置サーバ１０は、算出した電力の和が最も少ない組合せを選択し、選択した組合せを示すキャッシュリストを生成する。その後、キャッシュ配置サーバ１０は、生成したキャッシュリストを、バックボーンネットワーク３０の各ルータ３１〜４４に対して配信する。
【００２９】
次に、図５を用いて、キャッシュ配置サーバ１０の機能構成について説明する。図５は、実施例１に係るキャッシュ配置サーバの機能構成を説明するための図である。図５に示す例では、キャッシュ配置サーバ１０は、トポロジ情報管理部１１、キャッシュ配置箇所抽出部１２、配信経路パターン抽出部１３、リクエストリスト取得部１４、配置候補抽出部１５、消費電力予測部１６、最小電力判別部１７、キャッシュリスト生成部１８、配信部１９を有する。
【００３０】
トポロジ情報管理部１１は、ネットワーク４６のトポロジ情報を管理する。そして、トポロジ情報部１１は、管理するトポロジ情報をキャッシュ配置箇所抽出部１２、および、配信経路パターン抽出部１３に送信する。なお、トポロジ情報管理部１１は、あらかじめネットワーク４６のトポロジ情報を保持していてもよく、また、外部からトポロジ情報を取得することとしてもよい。
【００３１】
キャッシュ配置箇所抽出部１２は、トポロジ情報管理部１１が保持するトポロジ情報を用いて、コンテンツをキャッシュ可能なルータの候補を選択する。そして、キャッシュ配置箇所抽出部１２は、選択したルータの候補を配置候補抽出部１５に通知する。
【００３２】
配信経路パターン抽出部１３は、トポロジ情報を受信すると、トポロジ情報が示す各ルータ３１〜４４の接続関係を識別する。また、配信経路パターン抽出部１３は、識別した接続関係に基づいて、各ルータ３１〜４４をルートとし、各ルータ３１〜４４の接続関係を木構造で表す配信木のうち、各拠点間の転送路が最短となる配信木を導出する。そして、配信経路パターン抽出部１３は、最短配信木上で、各ルータ３１〜４４を接続する経路の候補を抽出する。すなわち、配信経路パターン抽出部１３は、各ルータ３１〜４４がコンテンツをキャッシュした際に、他の全てのルータに対してコンテンツを配信するための全ての経路パターンを抽出する。
【００３３】
以下、図を用いて、配信経路パターン抽出部１３が経路の候補を抽出する処理の一例について説明する。なお、以下の説明では、配信経路パターン抽出部１３が図３に示すトポロジ情報を取得した際に実行する処理について説明する。例えば、配信経路パターン抽出部１３は、図３に例示するトポロジ情報を取得した場合には、ルータ＃０をルートとし、ルータ＃１〜＃３を枝に含む最短の配信木を識別する。
【００３４】
ここで、図６は、配信木の一例を説明するための図である。図６に示すように、配信経路パターン抽出部１３は、ルータ＃０をルート（元）とし、他のルータ＃１〜＃３を枝に含む最短の配信木を識別する。すなわち、配信経路パターン抽出部１３は、ルータ＃０にオリジナルのコンテンツを記憶するサーバが接続されている場合に、ルータ＃０から他のルータ＃１〜＃３にコンテンツを配信する経路を枝とする配信木を識別する。そして、配信経路パターン抽出部１３は、識別した配信木の各枝を経路の候補とし、各経路の候補を示す変数ｓを生成する。
【００３５】
ここで、図７を用いて、変数ｓについて説明する。図７は、変数ｓが示す経路の候補を説明するための図である。例えば、図７に示すように、オリジンサーバ４５と接続されたルータをｔとし、クライアント５０と接続されたルータをｊとする。そして、オリジンサーバ４５が記憶するコンテンツを配信する経路の候補に、ルータｉからルータｊへの経路が含まれるものとする。このような場合には、配信経路パターン抽出部１３は、拠点ｔに在るオリジンサーバ４５が記憶するコンテンツデータを配信する経路のうち、ルータｉからルータｊへの経路を示す変数としてｓｔ（ｉ，ｊ）を生成する。そして、配信経路パターン抽出部１３は、生成した変数ｓｔ（ｉ，ｊ）を経路の候補として配置候補抽出部１５に通知する。
【００３６】
図８は、経路の候補を示す情報の一例を説明するための図である。図８に示すように、配信経路パターン抽出部１３は、ルータ＃０をルートとした場合には、図８に示す８通りの経路の候補を抽出し、抽出した経路の候補を配置候補抽出部１５に通知する。詳細には、配信経路パターン抽出部１３は、ルータ＃０を示すｓ０（０，０）、ルータ＃１を示すｓ０（１，１）、ルータ＃２を示すｓ０（２，２）、およびルータ＃３を示すｓ０（３，３）を配置候補抽出部１５に通知する。
【００３７】
また、配信経路パターン抽出部１３は、ルータ＃０からルータ＃１への経路の候補を示すｓ０（０，１）、ルータ＃０からルータ＃２への経路の候補を示すｓ０（０，２）を配置候補抽出部１５に通知する。また、配信経路パターン抽出部１３は、ルータ＃１からルータ＃３への経路の候補を示すｓ０（１，３）、ルータ＃０からルータ＃３への経路の候補を示すｓ０（０，３）を配置候補抽出部１５に通知する。
【００３８】
また、配信経路パターン抽出部１３は、他のルータ＃１〜＃３をルートとした場合についても、上述した経路の候補を抽出し、抽出した経路の候補を配置候補抽出部１５に通知する。
【００３９】
図５に戻って、リクエストリスト取得部１４は、ネットワーク４６を介して、バックボーンネットワーク３０の各ルータ３１〜４４に、リクエストリストの送信を要求する。そして、リクエストリスト取得部１４は、各ルータ３１〜４４からリクエストリストを取得した場合には、取得したリクエストリストを用いて、コンテンツごとのアクセス回数を算出し、算出したコンテンツごとのアクセス回数を配置候補抽出部１５に通知する。
【００４０】
ここで、図９は、リクエストリストの一例を説明するための図である。図９に示すように、リクエストリスト取得部１４は、各ルータ３１〜４４から各コンテンツとヒットカウントとを対応付けたリクエストリストを取得する。ここで、ヒットカウントとは、対応付けられたコンテンツに対するアクセス要求を、該当コンテンツをキャッシュ保持する各ルータが何回受信したかを示す情報である。
【００４１】
なお、図９に示す例では、ルータ３１とルータ４４から取得するリクエストリストの一例を示し、他のルータ３２〜４３から取得するリクエストリストの例については、記載を省略した。また、図９に示す例では、コンテンツ「Ａ」、「Ｂ」、「Ｚ」のヒットカウントの一例について記載し、他のコンテンツのヒットカウントについては、記載を省略した。
【００４２】
図９に示す例では、リクエストリスト取得部１４は、ルータ３１から、コンテンツ「Ａ」のヒットカウントが「１０００」回であり、コンテンツ「Ｂ」のヒットカウントが「５００」回である旨を示すリクエストリストを受信する。また、リクエストリスト取得部１４は、コンテンツ「Ｚ」のヒットカウントが「１５０」回である旨を示すリクエストリストを受信する。
【００４３】
また、図９に示す例では、リクエストリスト取得部１４は、ルータ４４から、コンテンツ「Ａ」のヒットカウントが「６００」回であり、コンテンツ「Ｂ」のヒットカウントが「２００」回である旨を示すリクエストリストを受信する。また、リクエストリスト取得部１４は、コンテンツ「Ｚ」のヒットカウントが「４００」回である旨を示すリクエストリストを受信する。
【００４４】
リクエストリスト取得部１４は、図９に例示したリクエストリストを受信した場合は、各ルータ３１〜４４から受信したリクエストリストにおいて、各コンテンツと対応付けられたヒットカウントの和を算出する。そして、リクエストリスト取得部１４は、各コンテンツと、算出したヒットカウントの和とを対応付けたトータルリクエストリストを生成する。
【００４５】
図１０は、トータルリクエストリストの一例を説明するための図である。例えば、リクエストリスト取得部１４は、コンテンツ「Ａ」のヒットカウントの和が「２００００」であると算出し、コンテンツ「Ｂ」のヒットカウントの和が「５００００」であると算出する。また、例えば、リクエストリスト取得部１４は、コンテンツ「Ｚ」のヒットカウントの和が「１０００００」であると算出する。そして、リクエストリスト取得部１４は、図１０に示すトータルリクエストリストを生成し、生成したトータルリクエストリストを配置候補抽出部１５に送信する。
【００４６】
図５に戻って、配置候補抽出部１５は、キャッシュ配置箇所抽出部１２から、コンテンツをキャッシュ可能なルータの通知を取得する。また、配置候補抽出部１５は、配信経路パターン抽出部１３から、各ルータから他のルータへコンテンツを配信する経路の候補の通知を取得する。また、配置候補抽出部１５は、リクエストリスト取得部１４から、トータルリクエストリストを取得する。
【００４７】
そして、配置候補抽出部１５は、トータルリクエストリストの各ヒットカウントを識別に、ヒットカウントが多いコンテンツから順に、以下の処理を実行する。まず、配置候補抽出部１５は、キャッシュ配置箇所抽出部１２から通知された各ルータをルートとした経路の候補を、配信経路パターン抽出部１３から通知された経路の候補から抽出する。この際、配置候補抽出部１５は、経路の候補として、以下の制約を全て満たす経路の候補を全て抽出する。
【００４８】
すなわち、配置候補抽出部１５は、コンテンツが全てのルータ３１〜４４に対して配信可能であり、各経路の始点がコンテンツをキャッシュするルータである経路の候補を抽出する。また、配置候補抽出部１５は、経路の候補を抽出するコンテンツと同一のオリジンサーバに記憶されたコンテンツのうち、ヒットカウントがより多いコンテンツについて、既に選択した経路の候補を必ず含む経路の候補を抽出する。また、配置候補抽出部１５は、各コンテンツを配信する経路上には、同一のコンテンツがキャッシュされないように経路の候補を抽出する。
【００４９】
ここで、配置候補抽出部１５が抽出する経路の候補が満たす制約について説明する。まず、配置候補抽出部１５は、コンテンツが全てのルータ３１〜４４に対して配信可能である経路の候補を抽出する。この制約は、バックボーンネットワーク３０の各ルータ３１〜４４に接続する全てのクライアントに対して、コンテンツを配信可能とすることを保証するための制約である。なお、配置候補抽出部１５は、この制約を満たすため、以下の式（１）を満たす経路の候補を抽出する。
【００５０】
【数１】
0005880139.tif 000002
【００５１】
また、配置候補抽出部１５は、配信経路の始点がコンテンツをキャッシュするルータである経路を選択する。これは、各経路に含まれるルータに対して、コンテンツが配信可能であることを保証するための制約である。なお、配置候補抽出部１５は、この制約を満たすため、以下の式（２）を満たす経路の候補を抽出する。なお、式（２）中のｕｉとは、ルータｉにコンテンツがキャッシュされているか否かを示す変数であり、コンテンツがキャッシュされている場合には「１」、コンテンツがキャッシュされていない場合には「０」となる。
【００５２】
【数２】
0005880139.tif 000003
【００５３】
また、配置候補抽出部１５は、経路の候補を抽出するコンテンツについて、同一のオリジンサーバに記憶されたコンテンツであり、かつ、よりアクセス回数が多いコンテンツについて既に選択された経路を必ず含む経路の候補を抽出する。以下、図１１を用いてこの制約について説明する。
【００５４】
図１１は、配信経路に係る制約条件の一例を説明するための第１の図である。例えば、配置候補抽出部１５は、アクセス回数が「ｎ」のコンテンツについて経路を抽出する場合には、同一のオリジンサーバｔを持つコンテンツであって、アクセス回数が「ｎ」よりも多いコンテンツについて採用された経路として、ｒｔ（ｉ，ｊ）＝｛ｈ、ｊ｝を取得する。このような場合には、配置候補抽出部１５は、ｒｔ（ｉ，ｊ）＝｛ｈ、ｊ｝を含む経路ｓｔ（ｉ，ｊ）＝｛ｉ，ｈ，ｊ｝を経路の候補として抽出する。
【００５５】
このような制約は、ＣＣＮ（Ｃｏｎｔｅｎｔ-Ｃｅｎｔｒｉｃ  Ｎｅｔｗｏｒｋｉｎｇ）の技術が各ルータ３１〜４４に適用されている場合に満たすべき制約である。すなわち、各ルータ３１〜４４は、ＣＣＮの技術が適用されている場合には、クライアントからのアクセス要求は、要求が転送される経路上のルータでコンテンツがキャッシュされていない限り、オリジンサーバが在る拠点のルータまで順に転送し、アクセス要求を転送した順にコンテンツを返信する。このため、オリジンサーバが在る拠点のルータからクライアントがいる拠点のルータまでの経路には、コンテンツをキャッシュするルータが含まれることとなる。また、同一のオリジンサーバが記憶するコンテンツであって、よりアクセス回数の高いコンテンツが、経路上に必ず存在することとなる。
【００５６】
このような制約を満たすため、配置候補抽出部１５は、同一のオリジンサーバが記憶するコンテンツであって、アクセス回数が「ｎ」よりも低いコンテンツについて、ルータｈからルータｊへの経路ｒｔ（ｉ，ｊ）を含む経路ｓｔ（ｉ，ｊ）＝｛ｉ，ｈ，ｊ｝を経路の候補として抽出する。詳細には、配置候補抽出部１５は、以下の式（３）を満たす経路の候補を抽出する。なお、式（３）中のｒｔ（ｈ，ｊ）−ｈは、経路ｒｔ（ｈ，ｊ）の順序列から始点となるルータｈを除いた経路順序対を示す。
【００５７】
【数３】
0005880139.tif 000004
【００５８】
なお、配置候補抽出部１５は、経路の候補を抽出するコンテンツについて、同一のオリジンサーバを持つコンテンツで、かつ、よりアクセス回数が多いコンテンツについて既に選択された経路を任意の方法で識別することができる。例えば、後述するように、最小電力判別部１７は、コンテンツをキャッシュするルータと、コンテンツを配信する経路の候補との組合せのうち、最も消費電力が少ない組合せを選択する。そこで、配置候補抽出部１５は、最小電力判別部１７が選択した組合せを取得する。そして、配置候補抽出部１５は、取得した組合せに含まれる経路の候補を用いて、同一のオリジンサーバに記憶されたコンテンツであり、かつ、よりアクセス回数が多いコンテンツについて既に選択された経路を識別することとしてもよい。
【００５９】
また、配置候補抽出部１５は、あるコンテンツを配信する経路上には、同一のコンテンツがキャッシュされないように経路の候補を抽出する。この制約は、コンテンツの無駄なキャッシュを行わないようにするための規約である。詳細には、配置候補抽出部１５は、以下の式（４）を満たす経路の候補を抽出する。
【００６０】
【数４】
0005880139.tif 000005
【００６１】
ここで、図１２は、配信経路に係る制約条件の一例を説明するための第２の図である。例えば、図１２に示すように、あるコンテンツについての経路ｓｔ（ｉ，ｊ）＝｛ｉ，ｈ，ｊ｝上におけるルータｈおよびルータｕについては、同一のコンテンツがキャッシュされないため、ｕｈ＝０、ｕｊ＝０となる。
【００６２】
このように、配置候補抽出部１５は、上述した式（１）〜式（４）を全て満たす経路の候補を全て抽出する。そして、配置候補抽出部１５は、コンテンツをキャッシュするルータと、抽出した各経路の候補との組合せを生成し、生成した全ての組合せと、配信対象となるコンテンツとを消費電力予測部１６に通知する。
【００６３】
つまり、配置候補抽出部１５は、あるコンテンツをキャッシュするルータに対して、全ての制約を満たす複数通りの経路の候補を抽出する。そして、配置候補抽出部１５は、コンテンツをキャッシュするルータと、抽出した複数の経路の候補について、全ての組合せを生成し、生成した各組合せを消費電力予測部１６に通知する。
【００６４】
図５に戻って、消費電力予測部１６は、配置候補抽出部１５からコンテンツをキャッシュするルータと、コンテンツを配信する経路の候補との組合せと、配信対象となるコンテンツの通知とを受信する。そして、消費電力予測部１６は、取得した各組合せについて、コンテンツをキャッシュする際にルータが消費する電力量と、経路の候補を介してコンテンツを配信する際にルータが消費する電力量との和を算出する。そして、消費電力予測部１６は、各組合せと、各組合せについて算出した電力の和とを配信対象となるコンテンツとともに最小電力判別部１７に通知する。
【００６５】
以下、消費電力予測部１６が消費する電力の和を算出する処理について具体的に説明する。まず、消費電力予測部１６は、以下の式（５）を用いて、コンテンツをキャッシュする際にルータが消費する電力量と、経路の候補を介してコンテンツを配信する際にルータが消費する電力量との和を算出する。ここで、式（５）中のＣａｋ、ｉとは、ルータｉにキャッシュを配置した際にルータｉが消費する電力量を示す。また、式（５）中のＴｒｋ，（ｉ，ｊ）とは、経路ｓｔ（ｉ，ｊ）を介してコンテンツが配信された場合に消費される電力量を示す。また、消費電力予測部１６は、組合せに含まれる経路ｓｔ（ｉ，ｊ）を「１」とし、組合せに含まれない経路ｓｔ（ｉ，ｊ）を「０」として式（５）を計算する。
【００６６】
【数５】
0005880139.tif 000006
【００６７】
ここで、消費電力予測部１６は、以下の式（６）を用いて、Ｃａｋ、ｉを算出する。なお、式（６）中のＰｃａとは、ルータｉが有するメモリの電力効率（[Ｗ／ｂｙｔｅｓ]）であり、Ｄｋとは、配信対象となるコンテンツのデータ量（［ｂｙｔｅｓ］）である。
【００６８】
【数６】
0005880139.tif 000007
【００６９】
また、消費電力予測部１６は、以下の式（７）を用いて、Ｔｒｋ，（ｉ，ｊ）を算出する。なお、式（７）中のＢｋとは、ルータｉからルータｊまでの経路におけるコンテンツの転送レート（［ｂｐｓ］）である。また、式（７）中のＲｋ，ｊとは、配信対象となるコンテンツに対し、ルータｊから送信されたリクエストの回数である。また、式（７）中のＰｒとは、ルータの電力効率（［Ｗ／ｂｐｓ］）である。また、式（７）中のＰｗｄｍとは、ＷＤＭ(Wavelength  Division  Multiplexing)装置の電力効率（［Ｗ／ｂｐｓ］）である。また、Ｈ（ｓｔ（ｉ，ｊ））とは、経路ｓｔ（ｉ，ｊ）におけるホップ数である。
【００７０】
【数７】
0005880139.tif 000008
【００７１】
ここで、図１３を用いて、ルータが消費する電力について説明する。図１３は、ルータの電力効率を説明するための図である。なお、図１３に示す例では、ルータ３１、ルータ３２、ルータ３８の接続について示した。図１３に示すように、バックボーンネットワーク３０においては、ルータ３１、ルータ３２、ルータ３８間の通信を高速に行うため、光波長多重通信を行うための装置であるＷＤＮ装置３１ａ、ＷＤＮ装置３２ａ、ＷＤＮ装置３８ａが接続される。そして、ＷＤＮ装置３１ａ、ＷＤＮ装置３２ａ、ＷＤＮ装置３８ａが光波長多重通信を行う事で、コンテンツの配信を高速に行うこととなる。
【００７２】
このため、消費電力予測部１６は、バックボーンネットワーク３０においてコンテンツを転送する際に消費される電力量を算出するためには、各ルータ３１〜４４が消費する電力Ｐｒだけではなく、ＷＤＭ装置が消費する電力Ｐｗｄｍを考慮する。具体的には、式（７）を用いて、コンテンツを転送する際に消費する電力Ｔｒｋ，（ｉ，ｊ）を算出する。その後、消費電力予測部１６は、消費電力予測部１６から通知された組合せと、式（５）を用いて算出した電力量とを最小電力判別部１７に通知する。
【００７３】
図５に戻って、最小電力判別部１７は、消費電力予測部１６から、コンテンツをキャッシュするルータとコンテンツを配布する経路の候補との組合せ、算出された電力量、配信対象となるコンテンツの通知を受信する。このような場合には、最小電力判別部１７は、配布対象となるコンテンツごとに、受信した電力量が最も少ない組合せを選択する。そして、最小電力判別部１７は、選択した組合せと、配信対象となるコンテンツとをキャッシュリスト生成部１８に通知する。
【００７４】
キャッシュリスト生成部１８は、最小電力判別部１７から、コンテンツをキャッシュするルータとコンテンツを配信する経路の候補との組合せ、および、配信対象となるコンテンツの通知を受信する。このような場合には、キャッシュリスト生成部１８は、配信対象となるコンテンツごとに、配信対象となるコンテンツをキャッシュするルータを示すキャッシュリストを生成する。
【００７５】
そして、キャッシュリスト生成部１８は、配信対象となる全てのコンテンツについて、配信対象となるコンテンツをキャッシュするルータを示すキャッシュリストを生成した場合には、生成したキャッシュリストを配信部１９に送信する。
【００７６】
配信部１９は、キャッシュリスト生成部１８が生成したキャッシュリストを受信する。そして、配信部１９は、受信したキャッシュリストを、ネットワーク４６を介して、バックボーンネットワーク３０の各ルータ３１〜４４に配信する。
【００７７】
例えば、トポロジ情報管理部１１、キャッシュ配置箇所抽出部１２、配信経路パターン抽出部１３、リクエストリスト取得部１４、配置候補抽出部１５、消費電力予測部１６、最小電力判別部１７、キャッシュリスト生成部１８、配信部１９は、電子回路である。ここで、電子回路の例として、ＡＳＩＣ（Application  Specific  Integrated  Circuit）やＦＰＧＡ（Field  Programmable  Gate  Array）などの集積回路、またはＣＰＵ（Central  Processing  Unit）やＭＰＵ（Micro  Processing  Unit）などを適用する。
【００７８】
このように、キャッシュ配置サーバ１０は、バックボーンネットワーク３０の各ルータ３１〜４４の接続関係を示すトポロジ情報を管理する。また、キャッシュ配置サーバ１０は、トポロジ情報を用いて、コンテンツのデータをキャッシュする１つ又は複数のルータと、コンテンツを配信する際に利用する経路の候補との組合せを抽出する。
【００７９】
そして、キャッシュ配置サーバ１０は、抽出した各組合せについて、コンテンツをキャッシュする際に消費する電力量と、経路の候補を介してコンテンツを配信する際に消費する電力量との和を算出する。その後、キャッシュ配置サーバ１０は、算出した電力量の和が最も少ない組合せを選択し、選択した組合せを示すキャッシュリストを出力する。すなわち、キャッシュ配置サーバ１０は、式（１）〜式（７）を用いて、消費電力が最小となるキャッシュの配置位置と配信経路とを数理計画問題に帰着して解く。
【００８０】
このため、キャッシュ配置サーバ１０は、バックボーンネットワーク３０が消費する電力を削減することができる。すなわち、従来のネットワークにおいては、ルータがコンテンツを転送する際に消費する電力量のみに基づいて、コンテンツをキャッシュするルータを決定する。このため、従来のネットワークにおいては、キャッシュするコンテンツの量を多くした際に、コンテンツをキャッシュする際に消費する電力が増大する結果、消費電力を削減することができなかった。
【００８１】
一方、キャッシュ配置サーバ１０は、トポロジ情報を用いて、コンテンツをキャッシュするルータと、コンテンツを配信する経路の候補との組合せを抽出する。そして、キャッシュ配置サーバ１０は、抽出した組合せのうち、コンテンツをキャッシュする際に消費する電力量と、コンテンツを配信する際に消費する電力量との和が最も少ない組合せを選択し、各ルータ３１〜４４に通知する。このため、キャッシュ配置サーバ１０は、バックボーンネットワーク３０の消費電力を削減することができる。
【００８２】
また、キャッシュ配置サーバ１０は、経路の候補を抽出するコンテンツについて、同一のオリジンサーバに記憶されたコンテンツであり、かつ、よりアクセス回数が多いコンテンツについて既に選択された経路の候補を必ず含む経路を候補として抽出する。すなわち、キャッシュ配置サーバ１０は、同一のオリジンサーバで保有されるコンテンツを配信する経路が、同一の最短配信木と重なるように、各コンテンツを配信する経路の候補を抽出する。このため、キャッシュ配置サーバ１０は、各ルータ３１〜４４がコンテンツを配信する経路にキャッシュ階層制約が存在する場合にも、制約に沿った経路の候補を抽出するので、適切に消費電力を削減することができる。
【００８３】
すなわち、各ルータ３１〜４４は、ＣＣＮの技術が適用されている場合は、コンテンツ要求を各ルータ３１〜４４が順次転送し、コンテンツがキャッシュヒットすると、コンテンツ要求を転送した経路を逆に辿ってコンテンツを配信する。このような場合には、各ルータ３１〜４４には、あるコンテンツの配信経路上には、同一のオリジンサーバに記憶されたコンテンツであって、アクセス回数がより多いコンテンツが必ず存在するという制約が発生する。
【００８４】
例えば、図１４Ａは、キャッシュ階層制約を説明するための第１の図である。図１４Ａに示す例では、ルータ＃０〜＃８が接続されたトポロジ上で、ＣＣＮによるキャッシュ配信を行う。ここで、ルータ＃０、ルータ＃４、ルータ＃８に接続されたオリジンサーバから、各ルータ＃０〜＃８に接続されたクライアントにコンテンツを配信する際は、図１４Ｂ中（Ａ）、（Ｂ）、（Ｃ）に示す経路を介してコンテンツを配信する。
【００８５】
図１４Ｂは、キャッシュ階層制約を説明するための第２の図である。例えば、各ルータ＃０〜＃８は、ルータ＃０に接続したオリジンサーバから各クライアントに対してコンテンツを配信する場合には、図１４Ｂ中（Ａ）に示す経路を介して、コンテンツを配信する。ここで、全てのルータ＃０〜＃８が全てのコンテンツをキャッシュした場合には、トラフィック量は削減されるものの、コンテンツをキャッシュするための消費電力が増大する。
【００８６】
そこで、各ルータ＃０〜＃８は、アクセス回数が多いコンテンツについては、転送経路上においてより利用者に近いルータがキャッシュし、アクセス回数が少ないコンテンツについては、転送経路上において、オリジンサーバに近いルータがキャッシュする。図１４Ｂ中（Ａ）に示す例では、ルータ＃０に接続されたオリジンサーバが保有するコンテンツのうち、アクセス回数が多いコンテンツについては、ルータ＃０〜＃８がキャッシュする。また、アクセス回数が少ないコンテンツについては、ルータ＃０のみ、もしくは、ルータ＃０、ルータ＃３、ルータ＃４がキャッシュする。
【００８７】
すなわち、同一のオリジンサーバが記憶するコンテンツは、同一配信木に含まれる経路を介して配信される。そして、同一のオリジンサーバが記憶するコンテンツのうち、アクセス回数が多いコンテンツはより利用者に近いルータがキャッシュを行う。このため、キャッシュ配置サーバ１０は、あるコンテンツについて、経路の候補を抽出する際は、同一のオリジンサーバが記憶するコンテンツのうち、よりアクセス回数が多いコンテンツの経路を必ず含む経路の候補を抽出する。
【００８８】
また、図１４Ｂ中（Ｂ）に示すようにルータ＃４に接続されたオリジンサーバが保有するコンテンツをクライアントに配信する場合には、各ルータ＃０〜＃８は、ルータ＃０に接続されたオリジンサーバが保有するコンテンツとは異なる経路を介して配信する。また、図１４中（Ｃ）に示すように、ルータ＃８に接続されたオリジンサーバが保有するコンテンツをクライアントに配信する場合には、各ルータ＃０〜＃８は、ルータ＃０、ルータ＃４に接続されたオリジンサーバが記憶するコンテンツとは異なる経路を介して配信する。
【００８９】
そこで、キャッシュ配置サーバ１０は、各ルータごとに、各ルータ３１〜４４をルートとした最短配信木を識別し、識別した配信木の枝から、キャッシュ階層構造の制約等を満たす枝を経路の候補として抽出する。このため、キャッシュ配置サーバ１０は、各ルータ３１〜４４にＣＣＮの技術が適用されている場合にも、制約を考慮したキャッシュ配置を行う事ができる。
【００９０】
次に、図を用いて、キャッシュ配置サーバ１０によるキャッシュ配置のシミュレーション結果について説明する。まず、図１５を用いて、シミュレーションの対象となるネットワークのトポロジについて説明する。図１５は、シミュレーションの対象となるネットワークの一例を説明するための図である。図１５に示す例では、ルータ＃０〜ルータ＃８を格子状に接続したネットワークをシミュレーションの対象とする。
【００９１】
次に、図１６を用いて、各ルータに接続されたオリジンサーバが記憶するコンテンツについて説明する。図１６は、各ルータに接続されたオリジンサーバが記憶するコンテンツを説明するための図である。図１６に示すように、以下のシミュレーションでは、１０００個のコンテンツに対し，ルータ＃０〜ルータ＃８に接続されるオリジンサーバをランダムに決定している。
【００９２】
また、以下のシミュレーションでは、各コンテンツのサイズを１４Ｍバイトとし、各コンテンツの平均スループットを１０Ｍｂｐｓとした。また、各ルータ＃０〜＃８が有するＤＲＡＭ（Dynamic  Random  Access  Memory）は、３．１２５×１０−１０［Ｗ／ｂｉｔ］の電力効率を有するものとする。また、各ルータ＃０〜＃８は、１．３×１０−８［Ｗ／ｂｐｓ］の電力効率を有するものとする。また、各ルータ＃０〜＃８と接続されたＷＤＭ装置は、１．６７×１０−９［Ｗ／ｂｐｓ］の電力効率を有するものとする。
【００９３】
また、図１７は、リクエストの分布の一例を説明するための図である。図１７に示すように、以下のシミュレーションでは、Ｚｉｐｆ分布に従って、コンテンツＩＤが大きくなるごとに、リクエスト回数が減少するものとしてシミュレーションを実行する。
【００９４】
このような場合には、キャッシュ配置サーバ１０は、図１８に示すキャッシュリストを生成する。図１８は、キャッシュ配置サーバが配布するキャッシュリストの一例を説明するための図である。なお、図１８には、同一拠点＃０にあるオリジンサーバを持つコンテンツ「Ａ」、コンテンツ「Ｂ」、コンテンツ「Ｃ」についてのキャッシュ可能場所を示すキャッシュリストを示した。なお、アクセス回数は、コンテンツ「Ａ」、コンテンツ「Ｂ」、コンテンツ「Ｃ」の順に減少するものとする。
【００９５】
図１８に示す例では、キャッシュ配置サーバ１０は、コンテンツ「Ａ」について、ルータＩＤが「０」、「１」、「２」、「３」、「４」、「５」、「６」、「７」、「８」のルータがキャッシュ可能場所である旨を示すキャッシュリストを生成する。すなわち、キャッシュ配置サーバ１０は、アクセス回数が他のコンテンツよりも多いコンテンツ「Ａ」について、全てのルータ＃０〜＃８がキャッシュを行ってよい旨を示すキャッシュリストを生成する。
【００９６】
また、キャッシュ配置サーバ１０は、コンテンツ「Ｂ」について、ルータＩＤが「０」
、「１」、「５」、「６」のルータがキャッシュ可能である旨を示すキャッシュリストを生成する。すなわち、キャッシュ配置サーバ１０は、アクセス回数が中程度のコンテンツ「Ｂ」について、ルータ＃０、ルータ＃１、ルータ＃５、ルータ＃６がキャッシュを行ってよい旨を示すキャッシュリストを生成する。
【００９７】
また、キャッシュ配置サーバ１０は、コンテンツ「Ｃ」について、ルータＩＤが「０」
のルータのみがキャッシュ可能である旨を示すキャッシュリストを生成する。すなわち、キャッシュ配置サーバ１０は、アクセス回数が他のコンテンツよりも低いコンテンツ「Ｃ」について、ルータ＃０がキャッシュを行ってよい旨を示すキャッシュリストを生成する。
【００９８】
次に、図１９〜２１を用いて、図１８に示すキャッシュリストを取得した各ルータ＃０〜＃８が、コンテンツの配信を行う経路について説明する。図１９は、コンテンツＡのキャッシュ位置の一例を説明するための図である。また、図２０は、コンテンツＢのキャッシュ位置の一例を説明するための図である。また、図２１は、コンテンツＣのキャッシュ位置の一例を説明するための図である。
【００９９】
図１９に示す例では、各ルータ＃０〜＃８は、それぞれコンテンツＡをキャッシュする。このため、各ルータ＃０〜＃８は、クライアントからコンテンツＡに対するアクセス要求を受信した場合には、アクセス要求を他のルータに転送することなく、自拠点にあるルータがキャッシュするコンテンツＡのデータをクライアントに返信する。
【０１００】
また、図２０に示す例では、ルータ＃０、ルータ＃１、ルータ＃６、ルータ＃５がコンテンツＢをキャッシュする。そして、ルータ＃０、ルータ＃１、ルータ＃６、ルータ＃５では、クライアントからコンテンツＢに対するアクセス要求を受信した場合には、アクセス要求を他のルータに転送することなく、自拠点にあるルータがキャッシュするコンテンツＡのデータをクライアントに返信する。一方、ルータ＃３は、コンテンツＢに対するアクセス要求を受信した場合には、ルータ＃０にアクセス要求を転送し、その後、ルータ＃０から送信されるコンテンツＢのデータをクライアントに転送する。
【０１０１】
また、ルータ＃２およびルータ＃４は、コンテンツＢに対するアクセス要求を受信した場合には、ルータ＃１にアクセス要求を転送し、その後、ルータ＃１から送信されるコンテンツＢのデータをクライアントに転送する。また、ルータ＃７は、コンテンツＢに対するアクセス要求を受信した場合には、ルータ＃６にアクセス要求を転送し、その後、ルータ＃６から送信されるコンテンツＢのデータをクライアントに転送する。また、ルータ＃８は、コンテンツＢに対するアクセス要求を受信した場合には、ルータ＃５にアクセス要求を転送し、その後、ルータ＃５から送信されるコンテンツＢのデータをクライアントに転送する。
【０１０２】
また、図２１に示す例では、ルータ＃０がコンテンツＣをキャッシュする。このため、他のルータ＃１〜＃８は、図２１に示す経路を介して、ルータ３０からコンテンツＣを取得し、クライアントに転送する。具体的には、ルータ＃１、＃２、＃４、＃５、＃８は、ルータ＃０、ルータ＃１、ルータ＃２を経由する経路、または、ルータ＃０、ルータ＃１、ルータ＃４、ルータ＃５、ルータ＃８を経由する経路を介してコンテンツＣを取得する。また、ルータ＃３、＃６、＃７は、ルータ＃０、ルータ＃３、ルータ＃６、ルータ＃７を経由する経路を介して、コンテンツＣを取得する。
【０１０３】
次に、図２２を用いて、バックボーンネットワーク３０の消費電力について説明する。図２２は、バックボーンネットワーク全体が消費する電力を説明するための図である。なお、図２２に示す例では、横軸に配布対象となるコンテンツの数、縦軸にバックボーンネットワーク３０の消費電力（Ｗ）をとり、コンテンツの数ごとにバックボーンネットワーク３０の消費電力をプロットした。
【０１０４】
また、図２２に示す例では、コンテンツを１つのルータのみがキャッシュした際にバックボーンネットワーク３０が消費する電力を１点破線でプロットした。また、図２２に示す例では、コンテンツを全てのルータがキャッシュした際にバックボーンネットワーク３０が消費する電力を破線でプロットした。また、図２２に示す例では、キャッシュ配置サーバ１０が配信するキャッシュリストに従ってコンテンツをキャッシュした際にバックボーンネットワーク３０が消費する電力を実線でプロットした。
【０１０５】
図２２に示すように、キャッシュ配置サーバ１０が配信するキャッシュリストに従ってコンテンツをキャッシュした場合には、他の２方式と比較して、バックボーンネットワーク３０が消費する電力を低く抑えることができる。
【０１０６】
また、図２３は、各ルータがキャッシュするデータ量を説明するための図である。なお、図２３に示す例では、横軸にルータ＃０〜＃８、縦軸に各ルータ＃０〜＃８がキャッシュするコンテンツのデータ量（ギガバイト）をとり、各ルータ＃０〜＃８がキャッシュするデータ量をプロットした。
【０１０７】
また、図２３に示す例では、コンテンツを１つのルータのみがキャッシュした際に各ルータ＃０〜＃８がキャッシュするデータ量を１点破線でプロットした。また、図２３に示す例では、コンテンツを全てのルータがキャッシュした際に各ルータ＃０〜＃８がキャッシュするデータ量を破線でプロットした。また、図２３に示す例では、キャッシュ配置サーバ１０が配信するキャッシュリストに従ってコンテンツをキャッシュした際に各ルータ＃０〜＃８がキャッシュするデータ量を実線でプロットした。
【０１０８】
図２３に示すように、キャッシュ配置サーバ１０が配信するキャッシュリストに従ってコンテンツをキャッシュした場合には、各ルータ＃０〜＃８は、１つのルータがコンテンツのキャッシュを行うよりも若干キャッシュするデータ量が増加する。しかし、各ルータ＃０〜＃８は、全てのルータ＃０〜＃８が全てのコンテンツのデータをキャッシュするよりも、少ない量のデータをキャッシュすることとなる。この結果、キャッシュ配置サーバ１０は、各ルータ＃０〜＃８が消費する電力を適切に削減することができる。
【０１０９】
次に、図を用いて、キャッシュ配置サーバ１０が実行する処理の流れについて説明する。まず、図２４を用いて、キャッシュ配置サーバ１０がトポロジ情報を用いて、コンテンツをキャッシュするルータと、経路の候補を抽出する処理の流れについて説明する。図２４は、キャッシュ配置サーバがトポロジ情報を用いて実行する処理の流れを説明するためのフローチャートである。
【０１１０】
まず、キャッシュ配置サーバ１０で、管理対象とするバックボーンネットワーク３０のトポロジ情報を取得する（ステップＳ１０１）。次に、キャッシュ配置サーバ１０は、トポロジ情報を用いて、コンテンツをキャッシュ可能な全てのルータを抽出する（ステップＳ１０２）。そして、キャッシュ配置サーバ１０は、抽出した各ルータをルートとする最短配信木を識別する（ステップＳ１０３）。その後、キャッシュ配置サーバ１０は、最短配信木の各枝に含まれる経路を抽出し（ステップＳ１０４）、処理を終了する。
【０１１１】
次に、図２５を用いて、キャッシュ配置サーバ１０がコンテンツのキャッシュ位置を選択するし処理の流れを説明する。図２５は、キャッシ配置サーバがコンテンツのキャッシュ位置を選択する処理の流れを説明するためのフローチャートである。
【０１１２】
まず、キャッシュ配置サーバ１０は、バックボーンネットワーク３０の各ルータ３１〜４４から、リクエストリストを取得する（ステップＳ２０１）。次に、キャッシュ配置サーバ１０は、リクエストリストを用いて、コンテンツを人気度の高い順、つまり、アクセス回数の多い順にソートする（ステップＳ２０２）。次に、キャッシュ配置サーバ１０は、ソートしたコンテンツから人気度が最も高いコンテンツを対象コンテンツとして１つ選択する（ステップＳ２０３）。
【０１１３】
そして、キャッシュ配置サーバ１０は、対象コンテンツに対するキャッシュ配置位置を抽出する（ステップＳ２０４）。すなわち、キャッシュ配置サーバ１０は、対象コンテンツを記憶するオリジンサーバが在る拠点のルータをキャッシュ配置位置として抽出する。次に、キャッシュ配置サーバ１０は、ステップＳ２０４で抽出したルータをルートとする最短配信木から抽出した経路候補のうち、所定の制約を満たす経路を配信経路の候補として抽出する（ステップＳ２０５）。
【０１１４】
次に、キャッシュ配置サーバ１０は、キャッシュ配置位置と経路の候補との組合せを生成する（ステップＳ２０６）。そして、キャッシュ配置サーバ１０は、各組み合わせについて、コンテンツをキャッシュする際の消費電力と、経路の候補を介してコンテンツを配信する際の消費電力との和が最も少ない組合せを選択する（ステップＳ２０７）。
【０１１５】
つぎに、キャッシュ配置サーバ１０は、全てのコンテンツについてキャッシュ配置位置と経路の候補との組合せを選択したか否かを判別し（ステップＳ２０８）、選択していないと判別した場合には（ステップＳ２０８否定）、ステップＳ２０３の処理を実行する。つまり、キャッシュ配置サーバ１０は、キャッシュ配置位置と経路の候補との組合せを選択していないコンテンツのうち、最も人気度が高いコンテンツを選択する。一方、キャッシュ配置サーバ１０は、全てのコンテンツについてキャッシュ配置位置と経路の候補との組合せを選択した場合には（ステップＳ２０８肯定）、キャッシュリストの配信を行い（ステップＳ２０９）、処理を終了する。
【０１１６】
［実施例１の効果］
上述したように、キャッシュ配置サーバ１０は、バックボーンネットワーク３０のルータ３１〜４４の接続関係を示すトポロジ情報を管理する。また、キャッシュ配置サーバ１０は、トポロジ情報を用いて、コンテンツをキャッシュするルータを選択するとともに、選択したルータからコンテンツをキャッシュしないルータにコンテンツを配信する際に利用する全ての経路の候補との組合せを抽出する。
【０１１７】
そして、キャッシュ配置サーバ１０は、各組合せについて、コンテンツをキャッシュする際に消費する電力量と、経路の候補を介してコンテンツを配信する際に経路に含まれるルータが消費する電力量との和を算出する。その後、キャッシュ配置サーバ１０は、電力量の和が最小となる組合せを選択し、選択した組合せを示すキャッシュリストを各ルータ３１〜４４に配信する。このため、キャッシュ配置サーバ１０は、バックボーンネットワーク３０の消費電力を削減することができる。また、キャッシュ配置サーバ１０は、機器配置コストを削減することができる。
【０１１８】
また、キャッシュ配置サーバ１０は、コンテンツをキャッシュするルータをルートとして他ルータまでの最短配信木を識別し、識別した最短配信木における枝を経路の候補とする。このため、キャッシュ配置サーバ１０は、コンテンツを配信する最短経路を抽出することができるので、バックボーンネットワーク３０がコンテンツを配信する際に消費する電力や機器配置コストを削減することができる。
【０１１９】
また、キャッシュ配置サーバ１０は、コンテンツをキャッシュしないルータがコンテンツをキャッシュするルータを始点とする経路のいずれかに含まれるように、コンテンツをキャッシュするルータと経路の候補との組合せを抽出する。このため、キャッシュ配置サーバ１０は、各ルータ３１〜４４に接続する全てのクライアントに対して、任意のコンテンツを配信させることができる。
【０１２０】
また、キャッシュ配置サーバ１０は、コンテンツをキャッシュするルータから各クライアントがいる拠点のルータまでの経路が単一の経路となるように、経路の候補を抽出する。このため、キャッシュ配置サーバ１０は、コンテンツを配信する経路が重複させないようにすることができる。
【０１２１】
また、キャッシュ配置サーバ１０は、コンテンツに対するアクセス回数が多い順に、コンテンツのキャッシュを配置するルータと、コンテンツを配信する経路の候補とを抽出する。ここで、キャッシュ配置サーバ１０は、同一のオリジンサーバに記憶されたコンテンツであって、経路の候補を抽出するコンテンツよりもアクセス回数が多いコンテンツについて選択した経路を含む経路を抽出する。このため、キャッシュ配置サーバ１０は、ルータ３１〜４４がＣＣＮの技術を用いてコンテンツの配信を行う場合にも、ＣＣＮのキャッシュ階層制約を満たしたキャッシュの配置を行う事ができる。
【０１２２】
また、キャッシュ配置サーバ１０は、ＣＣＮ上で各ルータ３１〜４４がキャッシュするデータを指定するキャッシュリストを生成し、生成したキャッシュリストを各ルータ３１〜４４に配信する。このため、キャッシュ配置サーバ１０は、バックボーンネットワーク３０が有する各ルータ３１〜４４の設定を自動で行うことができる。
【実施例２】
【０１２３】
これまで本発明の実施例について説明したが実施例は、上述した実施例以外にも様々な異なる形態にて実施されてよいものである。そこで、以下では実施例２として本発明に含まれる他の実施例を説明する。
【０１２４】
（１）バックボーンネットワークについて
上述したバックボーンネットワーク３０は、特定のトポロジで接続されたルータ３１〜４４を有していた。しかし、実施例はこれに限定されるものではない。すなわち、キャッシュ配置サーバ１０は、任意のトポロジで接続されたルータの消費電力を削減することができる。また、バックボーンネットワーク３０は、コア網やメトロ網だけではなく、任意の様態を有することができる。
【０１２５】
また、各ルータ３１〜４４は、ＣＣＮ以外の技術が適用されていても良い。すなわち、キャッシュ配置サーバ１０は、ＣＣＮのキャッシュ階層制約以外にも、各ルータ３１〜４４に適用される任意のプロトコルによる制約を考慮した経路を抽出することができる。
【０１２６】
（２）数式について
キャッシュ配置サーバ１０は、上述した式（１）〜（７）を用いて、消費電力量が最小となるキャッシュ位置と配信経路とを選択した。しかし実施例はこれに限定されるものではない。すなわち、キャッシュ配置サーバ１０は、ルータ３１〜４４がコンテンツをキャッシュする際に消費する電力、および、各ルータ３１〜４４がコンテンツを配信する際に消費する電力を算出することができれば、任意の数式を採用することができる。また、各ルータ３１〜４４について上述した既約以外の既約を適用する場合には、適用する既約に応じた数式を採用すればよい。
【０１２７】
（３）キャッシュリストについて
上述したキャッシュ配置サーバ１０は、キャッシュリストを各ルータ３１〜４４に送信し、各ルータ３１〜４４がキャッシュリストに応じて、コンテンツのデータをキャッシュした。しかし、実施例はこれに限定されるものではない。例えば、キャッシュ配置サーバ１０は、新たに設計するバックボーンネットワークのトポロジ情報に応じて、適切なキャッシュ位置を設計することとしてもよい。
【０１２８】
また、キャッシュ配置サーバ１０は、キャッシュリストに経路を示す情報を付加して配信し、各ルータ３１〜４４は、キャッシュリストに含まれる経路を示す情報を用いてコンテンツの配信を行うこととしてもよい。また、キャッシュ配置サーバ１０は、定期的に各ルータ３１〜４４からリクエストリストを取得し、定期的に最適なキャッシュ位置とコンテンツの配信経路とを抽出することとしてもよい。
【０１２９】
（４）プログラム
ところで、実施例１に係るキャッシュ配置サーバ１０は、ハードウェアを利用して各種の処理を実現する場合を説明した。しかし、実施例はこれに限定されるものではなく、あらかじめ用意されたプログラムをコンピュータで実行することによって実現するようにしてもよい。そこで、以下では、図２６を用いて、実施例１に示したキャッシュ配置サーバ１０と同様の機能を有するプログラムを実行するコンピュータの一例を説明する。図２６は、キャッシュ配置プログラムを実行するコンピュータの一例を説明するための図である。
【０１３０】
図２６に例示されたコンピュータ１００は、ＲＯＭ（Read  Only  Memory）１１０、ＨＤＤ（Hard  Disk  Drive）１２０、ＲＡＭ（Random  Access  Memory）１３０、ＣＰＵ（Central  Processing  Unit）１４０がバス１６０で接続される。また、コンピュータ１００は、他のコンピュータと通信を行うためのＩ／Ｏ（Input  Output）１５０がバス１６０で接続される。
【０１３１】
ＲＡＭ１３０には、キャッシュ配置プログラム１３１が記憶されており、ＣＰＵ１４０が読み出して実行することによって、図２６に示す例では、キャッシュ配置プロセス１４１として機能するようになる。なお、キャッシュ配置プロセス１４１は、図５に示すキャッシュ配置サーバ１０と同様の機能を発揮する。
【０１３２】
なお、本実施例で説明したキャッシュ配置プログラムは、あらかじめ用意されたプログラムをパーソナルコンピュータやワークステーションなどのコンピュータで実行することによって実現することができる。このプログラムは、インターネットなどのネットワークを介して配布することができる。また、このプログラムは、ハードディスク、フレキシブルディスク（ＦＤ）、ＣＤ−ＲＯＭ（Compact  Disc  Read  Only  Memory）、ＭＯ（Magneto  Optical  Disc）、ＤＶＤ（Digital  Versatile  Disc）などのコンピュータで読取可能な記録媒体に記録される。また、このプログラムは、コンピュータによって記録媒体から読み出されることによって実行することもできる。
【符号の説明】
【０１３３】
１  情報処理システム
２  ＣＰ
１０  キャッシュ配置サーバ
１１  トポロジ情報管理部
１２  キャッシュ配置箇所抽出部
１３  配信経路パターン抽出部
１４  リクエストリスト取得部
１５  配置候補抽出部
１６  消費電力予測部
１７  最小電力判別部
１８  キャッシュリスト生成部
１９  配信部
３０  バックボーンネットワーク
３１〜４４  ルータ
４５  オリジンサーバ
４６  ネットワーク
５０  クライアント
【図１】
0005880139.tif 000009
【図２】
0005880139.tif 000010
【図３】
0005880139.tif 000011
【図４】
0005880139.tif 000012
【図５】
0005880139.tif 000013
【図６】
0005880139.tif 000014
【図７】
0005880139.tif 000015
【図８】
0005880139.tif 000016
【図９】
0005880139.tif 000017
【図１０】
0005880139.tif 000018
【図１１】
0005880139.tif 000019
【図１２】
0005880139.tif 000020
【図１３】
0005880139.tif 000021
【図１４Ａ】
0005880139.tif 000022
【図１４Ｂ】
0005880139.tif 000023
【図１５】
0005880139.tif 000024
【図１６】
0005880139.tif 000025
【図１７】
0005880139.tif 000026
【図１８】
0005880139.tif 000027
【図１９】
0005880139.tif 000028
【図２０】
0005880139.tif 000029
【図２１】
0005880139.tif 000030
【図２２】
0005880139.tif 000031
【図２３】
0005880139.tif 000032
【図２４】
0005880139.tif 000033
【図２５】
0005880139.tif 000034
【図２６】
0005880139.tif 000035