(57)【要約】      （修正有）【課題】アクセスＩＳＰがトランジットＩＳＰに送出するＰ２Ｐトラフィック量を削減する目的でキャッシュを用いる場合、トランジットＩＳＰとの接点にキャッシュを配置する。【解決手段】トランジットＩＳＰが自身のＮＷ内を流れるＰ２Ｐトラヒック量の削減を目的に、当該ＮＷ上にキャッシュを配置する場合において、キャッシュ最適設計処理部１０２において、各リンクにおけるＰ２Ｐトラヒック量の平均を全リンクに対して足し合わせた総量を最小化するよう、ＮＷに設置する各キャッシュの容量を、与えられたＮＷトポロジと需要量を用いて算出することにより、キャッシュの容量も含めたキャッシュ配置個所の最適設計を行うことができ、効果的なＰ２Ｐトラヒックの削減が可能となる。【選択図】図２
2010199842.tif 000002
【特許請求の範囲】
【請求項１】
プログラムされたコンピュータ処理によって、各々接続された複数のネットワークのそれぞれに設置するキャッシュの最適容量を算出するキャッシュ設計システムであって、
プログラムされたコンピュータの処理実行手段として、
入力装置を介して入力されたネットワークトポロジ情報と需要量を記憶装置に格納する入力処理手段と、
上記記憶装置からネットワークトポロジ情報と需要量を読み出し、該ネットワークトポロジ情報と需要量を用いて、当該ネットワークの各リンクにおけるトラヒック量の平均の合計が最小化するよう、当該ネットワークに設置する各キャッシュの容量を算出するキャッシュ最適設計手段と、
該キャッシュ最適設計手段が算出した、当該ネットワークに設置する各キャッシュの容量を出力する出力処理手段と
を有することを特徴とするキャッシュ設計システム。
【請求項２】
請求項１に記載のキャッシュ設計システムであって、
上記ネットワークトポロジ情報として、他のネットワークとの接続リンクをキャッシュの配置個所とした情報を含み、
上記キャッシュ最適設計手段は、
上記他のネットワークとの接続リンクに設置するキャッシュの容量に対して、
上記ネットワークの各リンクにおけるトラヒック量の平均の合計を最小化する算出を行うことを特徴とするキャッシュ設計システム。
【請求項３】
請求項１もしくは請求項２のいずれかに記載のキャッシュ設計システムであって、
上記入力処理手段は、上記入力装置を介して入力された上記キャッシュ容量の合計値を記憶装置に格納し、
上記キャッシュ最適設計手段は、
上記記憶装置からネットワークトポロジ情報と需要量およびキャッシュ容量の合計値を読み出し、該ネットワークトポロジ情報と需要量およびキャッシュ容量の合計値を用いて、上記各キャッシュの容量の算出を行う
ことを特徴とするキャッシュ設計システム。
【請求項４】
プログラムされたコンピュータ処理によって、トランジットＩＳＰのネットワーク（トランジットＮＷ）に設置する、Ｐ２Ｐコンテンツを配信するキャッシュの最適容量を算出するキャッシュ設計システムであって、
プログラムされたコンピュータの処理実行手段として、
入力装置を介して入力されたネットワークトポロジ情報とＰ２Ｐ配信要求量を記憶装置に格納する入力処理手段と、
上記記憶装置からネットワークトポロジ情報とＰ２Ｐ配信要求量を読み出し、該ネットワークトポロジ情報とＰ２Ｐ配信要求量を用いて、当該トランジットＮＷの各リンクにおけるトラヒック量の平均の合計が最小化するよう、当該トランジットＮＷに設置する各キャッシュの容量を算出するキャッシュ最適設計手段と、
該キャッシュ最適設計手段が算出した、当該トランジットＮＷに設置する各キャッシュの容量を出力する出力処理手段とを有することを特徴とするキャッシュ設計システム。
【請求項５】
請求項４に記載のキャッシュ設計システムであって、
上記入力処理手段は、上記入力装置を介して入力された上記キャッシュ容量の合計値を記憶装置に格納し、かつ、上記ネットワークトポロジ情報として、上記トランジットＮＷにおける下位ＮＷとの接続リンクのみをキャッシュの設置個所とした情報を含み、
上記キャッシュ最適設計手段は、
上記下位ＮＷとの接続リンクに設置する各キャッシュの容量を、
上記キャッシュ容量の合計値と上記下位ＮＷとの接続リンクのみをキャッシュの設置個所とする情報を制約条件として用い、最適性の原理を利用した動的計画法を用いた多項式時間での厳密最適解として算出する
ことを特徴とするキャッシュ設計システム。
【請求項６】
請求項４もしくは請求項５のいずれかに記載のキャッシュ設計システムであって、
上記入力手段は、上記入力装置を介して入力されたキャッシュ容量の下限制約値と上限制約値を記憶装置に格納し、
上記キャッシュ最適設計手段は、
上記記憶装置からネットワークトポロジ情報とＰ２Ｐ配信要求量およびキャッシュ容量の下限制約値と上限制約値を読み出し、該ネットワークトポロジ情報とＰ２Ｐ配信要求量およびキャッシュ容量の下限制約値と上限制約値を用いて、該キャッシュ容量の下限制約値と上限制約値の範囲内で上記各キャッシュの容量を算出する
ことを特徴とするキャッシュ設計システム。
【請求項７】
請求項４に記載のキャッシュ設計システムであって、
上記入力処理手段は、上記入力装置を介して入力された上記キャッシュ容量の合計値と、上記トランジットＮＷに設置するキャッシュ容量の下限制約値と上限制約値を記憶装置に格納し、かつ、上記ネットワークトポロジ情報として、上記トランジットＮＷにおける下位ＮＷとの接続リンクのみをキャッシュの設置個所とした情報を含み、
上記キャッシュ最適設計手段は、
上記キャッシュ容量の合計値と上記トランジットＮＷに設置するキャッシュ容量の下限制約値と上限制約値および上記下位ＮＷとの接続リンクのみをキャッシュの設置個所とする情報を制約条件として用いて、下記の手順で、
上記下位ＮＷとの接続リンクに設置する各キャッシュの容量を算出する
ことを特徴とするキャッシュ設計システム。
手順
（１）ノードｉに設置されるキャッシュの容量Ｃｉを、予め定められたコンテンツサイズの平均値Ｂと任意の整数ｋｉを用いてＣｉ＝ｋｉＢに置き換え、
（２）コンテンツｍのアクセス頻度ｑｍとサイズｂｍとの積であるｙｍ（＝ｑｍ×ｂｍ）の値がｋ番目に大きいコンテンツの人気順位を表すｑｓ（ｋ）と、予め定められるノードｉの人口比ｒｉおよびノードｊとノードｋ間のホップ長ｈｊｋを用いた下記の数１の式で平均経由ホップ長の削減量Ｄｉ（ｋｉ）を表し、
【数１】
2010199842.tif 000007
（３）上記上限制約値であるＣｍａｘを、Ｍ個のコンテンツのサイズの総量ＭＢとトランジットＮＷ全体で用意するキャッシュの総容量Ｃを用いて、Ｃｍａｘ＝ｍｉｎ｛ＭＢ，Ｃ｝とし、該Ｃｍａｘと、上記下限制約値であるＣｍｉｎに相当する上記任意の整数ｋｉの限界値を各々ｋｍａｘ（＝ｉｎｆ（Ｃｍａｘ／Ｂ）），ｋｍｉｎ（＝ｓｕｐ（Ｃｍｉｎ／Ｂ））とし、
かつ、上記トランジットＮＷ全体で用意するキャッシュの総容量Ｃに相当する上記整数ｋの値をＫ（＝ｉｎｆ（Ｃ／Ｂ））として、
下記の数２の式に示す再帰方程式を形成し、
【数２】
2010199842.tif 000008
（４）上記数２の再帰方程式を、ｉ＝１から順にｉ＝Ｎまで、全ての可能なａｉの値に対して各々解き、最終的にφＮ（Ｋ）を与える整数ｋ１，ｋ２，…，ｋＮを、各ノードに設置すべき最適なキャッシュ容量として求める。
【請求項８】
プログラムされたコンピュータ処理によって、ネットワークにおけるキャッシュの配置箇所を選択するシステムのキャッシュ設計方法であって、
プログラムされたコンピュータの処理手順として、
請求項１から請求項７のいずれかに記載のキャッシュ設計システムにおける各手段が実行する処理手順を含むことを特徴とするキャッシュ設計方法。
【請求項９】
コンピュータを、請求項１から請求項７のいずれかに記載のキャッシュ設計システムにおける各手段として機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ネットワークにおけるキャッシュ（コンピュータ）の配置技術に係り、特に、インターネットを流れるＰ２Ｐトラヒック量を効率的に削減するのに好適なキャッシュ配置技術に関するものである。
【背景技術】
【０００２】
インターネットにおいては、近年、ＢｉｔＴｏｒｒｅｎｔ（登録商標）やｅＤｏｎｋｅｙ（登録商標）等のＰ２Ｐ型ファイル共有サービスの普及が目覚ましい。Ｐ２Ｐ型ファイル共有サービスでは、データをダウンロードしたユーザ端末が他のユーザに対してデータをアップロードし配信に協力する。そのため人気の高いコンテンツやファイルほどサーバ機能を果たす端末数が増加することになり、スケーラビリティに優れた配信システムである。
【０００３】
もともとは違法コンテンツをダウンロードする技術としてＰ２Ｐ配信サービスの利用者が急増したが、著作権保有者らからの相次ぐ訴訟により多くの違法コンテンツの転送サービスが中止に追い込まれた。しかし、Ｐ２Ｐ配信システムを技術的に見た場合、高いスケーラビリティを有する優れた配信技術であることから、近年、フリーソフトの配信や著作権をＰ２Ｐ配信事業者が管理する合法的な配信システムとして注目されている。
【０００４】
このため、Ｐ２Ｐトラヒックは、インターネットにおける交流トラヒック量の大部分を占めており、今後、Ｐ２Ｐ型配信システムを用いた動画ストリーミング配信などの所要伝送帯域の大きなサービスの普及が予想され、さらに、Ｐ２Ｐトラヒックが急増していくことが想定される。
【０００５】
ＩＳＰ（Ｉｎｔｅｒｎｅｔ  Ｓｅｒｖｉｃｅ  Ｐｒｏｖｉｄｅｒ）は、トラヒック量の増加に対して通信品質を維持するために、大量の設備を増設する必要があるが、ユーザを直接収容する多くの「アクセスＩＳＰ」は、ユーザに対して転送データ量とは無関係に定額の料金を徴収しているため、Ｐ２Ｐトラヒック量が増加しても収益の増加に結びつかず、設備増設のための費用を賄うことができない。
【０００６】
そのため、一部のアクセスＩＳＰには、Ｐ２Ｐトラヒックを規制する動きも見られるが、ユーザにとっての不満が大きく、他のＩＳＰに乗り換える等の結果を招き、ＩＳＰにとって望ましい解決法とはいえない。
【０００７】
また、バックボーンＮＷを運用し、アクセスＩＳＰ間のトラヒックの中継サービスを行う「トランジットＩＳＰ」は、接続するアクセスＩＳＰに対して転送スループットの９５％値といった従量型の課金を適用することが多く、Ｐ２Ｐトラヒック量の増加に伴う設備増設コストを、ある程度、賄うことが原理的には可能である。
【０００８】
しかし、多くのＰ２Ｐサービスでは、配信元となるピア（コンピュータ）がランダムに選択されるため、ホップ距離の長い遠方に存在するピアから配信がなされる可能性もあり、ＮＷ内を無駄にトラヒックが流れる問題が指摘されている。
【０００９】
バックボーンＮＷには大量のトラヒックが交流するため、限られたＮＷ資源を効率的に運用することは、トランジットＩＳＰにとって重要な問題である。
【００１０】
一般に、データ配信においては、できるだけ配信先のユーザ端末が収容されているノードにホップ距離が近いノードから要求データを配信することで、消費されるＮＷ資源を抑えることができ、効率的なＮＷ資源の運用が可能となる。
【００１１】
Ｐ２Ｐ配信システムにおいては、このように、配信のローカリティを高めるための多くの提案がなされているが、（ｉ）ピアの選択法を工夫してローカリティの高い配信元ピアを選択するアプローチと、（ｉｉ）キャッシュを利用するアプローチの二つに分類することができる。
【００１２】
（ｉ）のアプローチは、ピアをランダムに選択する代わりに、近隣に存在するピアを選択する技術であるが、Ｐ２Ｐ配信システムでは、各ピアやＰ２Ｐ事業者が設置するスーパピアが自律的に配信元ピアを選択するため、利用者やＰ２Ｐ事業者の協力が必要となる。
【００１３】
また、ＮＷトポロジや経路情報といったＮＷ情報を有するＩＳＰが、これらの情報を他者に公開することは難しく、利用者やＰ２Ｐ事業者は計測等によって取得した限定的な情報に基づき、近隣に存在すると思われるピアを推測で選択せざるをえず、ローカリティ向上の精度に限界がある。
【００１４】
一方、（ｉｉ）のアプローチは、ＩＳＰが、ＮＷ上にキャッシュを配置し、配信先ピアとホップ距離が近いキャッシュから配信を行うことで配信フローのローカリティを向上させるアプローチであり、この（ｉｉ）のアプローチは、アクセスＩＳＰにとっては、トランジットＩＳＰに流出するトラヒック量を抑えてトランジットＩＳＰへの支払い費用を削減する技術として、またトランジットＩＳＰにとっては、ＮＷ内を流れる交流フローの平均ホップ長を抑えてＮＷ資源の利用効率を向上させる技術として有効であり、様々な検討がなされており、商用ベースのキャッシュ機器も多数開発されている。
【００１５】
このように、キャッシュは、Ｗｅｂトラヒック配信において、レスポンス時間を改善する技術として広く利用されており、Ｐ２Ｐトラヒック量を削減する技術としても有効である。
【００１６】
Ｐ２Ｐトラヒックをキャッシュする製品や研究は、（１）ルータの特定のポートを流れるトラヒックを計測して、Ｐ２Ｐフローを識別するもの、（２）キャッシュをＰ２Ｐサービスのスーパピアとして稼働させるもの、の二つのアプローチに分類できる。
【００１７】
（１）のアプローチでは、ルータの特定のポートに入出力されるパケット流をミラーリング等により計測してＰ２Ｐフローを識別する。Ｐ２Ｐフローの識別技術としては、ポート番号に基づくもの、パケットのペイロードを調査するもの、フローの挙動によるもの、等が存在するが、ペイロードの調査に基づくものが一般的である。
【００１８】
Ｐ２Ｐの配信要求を識別した際、計測点に設置されたキャッシュが、要求されたコンテンツ（もしくはコンテンツの一部）を保有している場合には、自キャッシュから配信する。また、キャッシュが保有していないコンテンツを運ぶＰ２Ｐフローが検出された場合には、配信中のコンテンツをキャッシュする。
【００１９】
そのため、キャッシュ可能なコンテンツは、キャッシュを配信フローが経由するものに限定され、受動的にキャッシュが更新される。ＣａｃｈｅＬｏｇｉｃ（登録商標）社のＣａｃｈｅｐｌｉａｎｃｅ（登録商標）等、多くのキャッシュ製品が本アプローチを用いている。
【００２０】
ところで、Ｇｎｕｔｅｌｌａ（登録商標）等、階層型のＰ２Ｐサービスにおいては、ピアの一部がスーパピアとして機能し、配下のピアに対してピア選択機能を提供する。そこで、上述の（２）のアプローチでは、これら階層型Ｐ２Ｐサービスを対象に、キャッシュをスーパピアとして稼働させ、配下のピアに対してキャッシュからコンテンツを配信する。
【００２１】
この技術では、ピアとして稼働するため、他のスーパピアやピアに対してコンテンツを能動的にダウンロードし、キャッシュすることが可能である。Ｏｖｅｒｓｉ（登録商標）社のＯｖｅｒＣａｃｈｅ（登録商標）が本アプローチを用いたキャッシュ製品である。
【００２２】
現状では、上述の（１）の「Ｐ２Ｐフローを識別するアプローチ」を用いたキャッシュ製品が多く、一般的であることから、以後、Ｐ２Ｐフローを識別するアプローチを対象としての説明を行う。
【００２３】
キャッシュに新たにコンテンツをキャッシュする際、記憶領域が不足する場合には、キャッシュ内の一部のコンテンツを削除して空き領域を確保する必要がある。
【００２４】
この際に、削除するコンテンツをどのように選択するかが問題となる。同様の問題は、コンピュータのメモリやＷｅｂコンテンツをキャッシュする場合にも生じ、この問題に対する従来技術として、要求頻度が最小のものを削除するＬＦＵ（Ｌｅａｓｔ  Ｆｒｅｑｕｅｎｔｌｙ  Ｕｓｅｄ）や、最後に要求のあった時刻が最も古いものを削除するＬＲＵ（Ｌｅａｓｔ  Ｒｅｃｅｎｔｌｙ  Ｕｓｅｄ）が広く用いられている。
【００２５】
ところが、Ｐ２Ｐサービスで交換されるコンテンツは、音楽や動画等、サイズの大きく異なるもので構成されている。そのため、コンテンツのサイズも考慮してキャッシュを更新することが有効であり、過去の総転送バイト量が最小のコンテンツを優先的に削除するＬＳＢ（Ｌｅａｓｔ  Ｓｅｎｔ  Ｂｙｔｅ）が、最大のバイトヒット率を達成できる。
【００２６】
尚、バイトヒット率とは、総転送データ量（ｂｙｔｅ）に対する、実際にキャッシュから配信された総転送データ量（ｂｙｔｅ）の比率であり、コンテンツサイズのレンジ幅が大きいＰ２Ｐトラヒックをキャッシュする場合のキャッシュの性能を図る尺度として、ヒット率の代わりに用いられる指標である。
【００２７】
以上に説明した技術については、非特許文献１に記載されている。
【先行技術文献】
【非特許文献】
【００２８】
【非特許文献１】Ｍ．Ｈｅｆｅｅｄａ  ａｎｄ  Ｏ．Ｓａｌｅｈ，“Ｔｒａｆｆｉｃ  Ｍｏｄｅｌｉｎｇ  ａｎｄ  Ｐｒｏｐｏｒｔｉｏｎａｌ  Ｐａｒｔｉａｌ  Ｃａｃｈｉｎｇ  ｆｏｒ  Ｐｅｅｒ・ｔｏ・Ｐｅｅｒ  Ｓｙｓｔｅｍｓ，”  ＩＥＥＥ／ＡＣＭ  Ｔｒａｎｓａｃｔｉｏｎｓ  ｏｎ  Ｎｅｔｗｏｒｋｉｎｇ，  Ｖｏｌ．１６，  Ｎｏ．６，  ｐｐ．１４４７−１４６０，  ２００７．
【発明の概要】
【発明が解決しようとする課題】
【００２９】
アクセスＩＳＰがトランジットＩＳＰに送出するＰ２Ｐトラヒック量を削減する目的でキャッシュを用いる場合、トランジットＩＳＰとの接続点にキャッシュを配置すれば十分な効果を得ることができる。
【００３０】
一方、主としてトランジットＩＳＰが交流Ｐ２Ｐトラヒック量を削減する目的でキャッシュを用いる場合には、Ｐ２Ｐトラヒック量の削減効果は、キャッシュを配置する場所に大きく依存するため、キャッシュ配置位置と、各々の設置位置における「キャッシュ容量」を慎重に設計する必要がある。
【００３１】
図１は、トランジットＩＳＰにおけるキャッシュの配置位置の具体例を示す説明図である。図１においては、トランジットＩＳＰのＮＷ（Ｔｒａｎｓｉｔ  ＩＳＰ）１０に、アクセスＩＳＰのＮＷ（Ａｃｃｅｓｓ  ＩＳＰ−ｘ，ｙ）１１，１２が、ゲートウェイ・ルータ（ＧＷ  ｒｏｕｔｅｒ）１１ａ，１２ａを介して接続されている。
【００３２】
トランジットＩＳＰのＮＷ１０には、コアルータ１０ａ〜１０ｅが設けられ、アクセスＩＳＰのＮＷ１１，１２のそれぞれには、ピア１１ｂ〜１１ｄ，１２ｂ〜１２ｄが接続されている。
【００３３】
図１に示すように、トランジットＩＳＰのＮＷ１０においてキャッシュを配置する場所としては、コアルータ１０ａ〜１０ｅ間を結ぶリンク１０ｆ，１０ｇ（Ｃａｃｈｅ  ｌｏｃａｔｉｏｎ−Ａ）と、下位のアクセスＩＳＰのＮＷ１１，１２との接続リンク１０ｈ，１０ｉ（Ｃａｃｈｅ  ｌｏｃａｔｉｏｎ−Ｂ）とが考えられる。
【００３４】
キャッシュが配信元として機能できるのは、キャッシュを経由するフローに限定されるため、リンク１０ｆ，１０ｇ（Ｃａｃｈｅ  ｌｏｃａｔｉｏｎ−Ａ）にキャッシュを配置した場合には、該当リンク１０ｆ，１０ｇを経由する配信フローの配信先ピアに対して、一方、接続リンク１０ｈ，１０ｉ（Ｃａｃｈｅ  ｌｏｃａｔｉｏｎ−Ｂ）にキャッシュを配置した場合には、接続する下位のＮＷ１２に収容されたピア１２ｂ〜１２ｄに対して、各々、キャッシュからの配信が可能である。
【００３５】
以下、トランジットＩＳＰが、自ＮＷ１０内のＰ２Ｐトラヒック量を削減することを目的に、Ｃａｃｈｅ  ｌｏｃａｔｉｏｎ−Ｂ（下位ＮＷ１２との接続点１０ｈ）にキャッシュを設置する場合を対象として説明する。
【００３６】
ＮＷにおけるノード数をＮとすると、Ｎ個のキャッシュ設置可能な場所が存在する。一般に、ノード間の転送コスト、ＮＷトポロジ、各ノードで発生するデマンド量、設置ノード数Ｋ（配置数）が与えられたときに、総転送コストを最小化する配置数Ｋのファシリティ配置位置を選択する問題は、ＵＫＭ（Ｕｎｃａｐａｃｉａｔｅｄ  Ｋ−Ｍｅｄｉａｎ）として知られている。
【００３７】
さらに、配置数Ｋが与えられず、設置数も含めて配置位置を最適化する問題はＵＦＬ（Ｕｎｃａｐａｃｉａｔｅｄ  Ｆａｃｉｌｉｔｙ  Ｌｏｃａｔｉｏｎ）として知られており、共にＮＰ困難であるため、様々な近似解法が検討されている。
【００３８】
しかし、これらの設計法では、各設置位置に同一のファシリティ（設備・装置）を配置することが想定されているが、キャッシュの装置としての性能はキャッシュ容量に大きく依存するため、Ｐ２Ｐトラヒック削減を目的としてキャッシュを配置する場合には、各々の拠点に設置するキャッシュの容量も含めて最適設計を図ることが重要である。
【００３９】
また、Ｐ２Ｐトラヒック削減を目的にキャッシュをＮＷ上に最適配置する技術として、リンク利用率から定まる効用関数と各キャッシュ設置に要するコストに対して、総コストが許容上限内に収まる範囲で効用の総和を最大化するキャッシュ配置技術が提案されているが、この技術においても、やはり、キャッシュ容量については考慮されておらず、キャッシュヒット率を固定値として与えている。
【００４０】
解決しようとする問題点は、上述のように、従来の技術では、キャッシュの各配置拠点の特定に、キャッシュ容量を考慮していない点である。
【００４１】
本発明の目的は、これら従来技術の課題を解決し、キャッシュの容量も含めたキャッシュ配置個所の最適設計を行うことにより、効果的なＰ２Ｐトラヒックの削減を可能とすることである。
【課題を解決するための手段】
【００４２】
上記目的を達成するため、本発明では、例えば、トランジットＩＳＰが自身のＮＷ内を流れるＰ２Ｐトラヒック量の削減を目的に、当該ＮＷ上にキャッシュを配置する場合において、各リンクにおけるＰ２Ｐトラヒック量の平均の、全リンクにおける総量が、最小化するよう、各キャッシュの配置箇所と各キャッシュの容量を、与えられたＮＷトポロジと需要量を用いて算出する。
【発明の効果】
【００４３】
本発明によれば、各キャッシュの配置拠点を特定する際に、各キャッシュの容量を考慮し、キャッシュの容量も含めたキャッシュ配置個所の最適設計を行うことができ、効果的なＰ２Ｐトラヒックの削減が可能となる。
【図面の簡単な説明】
【００４４】
【図１】本発明を適用するネットワークの構成例を示すブロック図である。
【図２】本発明に係るキャッシュ設計システムの構成例を示すブロック図である。
【図３】本発明の評価に用いたネットワークの基本特性例を示す説明図である。
【図４】本発明の評価に用いたネットワークの特性例を示す説明図である。
【図５】本発明の評価に用いたネットワークにおけるキャッシュの設置状況例を示す説明図である。
【図６】本発明に係るキャッシュ設計システムによるキャッシュの削減効果例を示す説明図である。
【図７】本発明に係るキャッシュ設計方法の処理手順例を示すフローチャートである。
【発明を実施するための形態】
【００４５】
以下、図を用いて本発明を実施するための形態例を説明する。図２は、本発明に係るキャッシュ設計システムの構成例を示すブロック図であって、本例のキャッシュ設計システムは、ＣＰＵ（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）や主メモリ等を具備したコンピュータ構成からなり、プログラムされたコンピュータ処理によって、ネットワークにおけるキャッシュの配置箇所を選択するものであって、プログラムされたコンピュータの処理を実行する機能として、入力処理部１００とキャッシュ最適設計処理部１０２および出力処理部（図中「キャッシュ最適設計結果出力処理部」と記載）１０３を具備している。
【００４６】
入力処理部１００は、図示していないキーボードやマウス等の入力装置を用いた操作者の入力操作により、例えば、外部記憶媒体、あるいは、ネットワークを介したオンラインで入力される、ネットワークトポロジ情報と需要量を記憶装置１０１に格納する。
【００４７】
キャッシュ最適設計処理部１０２は、記憶装置１０１からネットワークトポロジ情報と需要量を読み出し、読み出したネットワークトポロジ情報と需要量を用いて、当該ネットワークの各リンクにおけるトラヒック量の平均の合計が最小化するよう、当該ネットワークに設置する各キャッシュの容量を算出する。
【００４８】
出力処理部１０３は、キャッシュ最適設計処理部１０２が算出した、当該ネットワークに設置する各キャッシュの容量を、ＣＲＴ（Ｃａｔｈｏｄｅ  Ｌａｙ  Ｔｕｂｅ）やＬＣＤ（Ｌｉｑｕｉｄ  Ｃｒｙｓｔａｌ  Ｄｉｓｐｌａｙ）等の表示装置に表示する、もしくは、プリンタで印字する、あるいは、記憶媒体に記録する、オンライン上の他のコンピュータ装置等に送信する等の出力処理を行う。
【００４９】
以下、このような構成からなるキャッシュ設計システムによる、図１に示したネットワークにおけるＰ２Ｐトラヒック削減のためのキャッシュ最適設計処理について、詳細を説明する。
【００５０】
本例では、図１におけるトランジットＩＳＰが、自ネットワーク（ＮＷ）１０内を流れるＰ２Ｐトラヒック量を削減することを目的に、下位のネットワーク（ＮＷ）１１，１２との接続リンク１０ｈ，１０ｉにキャッシュを設置する場合を想定し、キャッシュ容量も含めてキャッシュ配置位置を最適設計する。
【００５１】
まず、キャッシュ設計システムによるＰ２Ｐトラヒック削減のためのキャッシュ最適設計処理を行う際に用いる「需要量」情報に関する『前提条件』について説明する。
【００５２】
『前提条件』
キャッシュを更新する際には、過去の転送総データ量が最小のコンテンツを優先的に削除することが望ましい。
【００５３】
そこで、未キャッシュのコンテンツをキャッシュする際には、各キャッシュにおいて、各コンテンツｍに対して、下位のＮＷに収容されたピアからの配信要求数をカウントしておき、単位時間あたりの配信要求数（最初の要求発生時刻と現在時刻の差で要求数を除した値）とコンテンツサイズとの積の値ｘｍが最小のコンテンツから順に、新たに収容するコンテンツの収容スペースが確保されるまで削除するものとする。
【００５４】
ｑｍとｂｍ（ｂｙｔｅ）を各々、コンテンツｍの相対的なアクセス頻度とサイズとし、ｙｍ＝ｑｍ・ｂｍと定義すると、平均的には、ｙｍの大きなコンテンツほど高い確率でキャッシュに存在すると言える。
【００５５】
そこで、Ｐ２ＰサービスによってＭ個のコンテンツが提供されているとき、ｙｍの値が大きな順に識別番号ｍを付与する（ｙ１＞＝ｙ２＞＝…＞＝ｂＭ）。
【００５６】
本例では、簡単のためコンテンツの人気順位、ならびに要求頻度分布は固定とする。また、Ｍ個のコンテンツの平均サイズをＢ（ｂｙｔｅ）とする。
【００５７】
各都市におけるＰ２Ｐユーザの人口に対する比率は一定で地域的な偏りがなく、さらに、ノードｉに接続された下位のＮＷが収容するユーザ数は、それら下位のＮＷがカバーするエリアの人口ｐｉに比例すると考えることができるため、ノードｉに接続された下位のＮＷに収容されたユーザから発生する配信要求数のＮＷ全体の配信要求数に対する比率は、ノードｉの収容人口比率ｒｉ（ｒｉ＝ｐｉ／Σｋ＝１Ｎｐｋ）に一致すると仮定できる。
【００５８】
また、コンテンツに対する嗜好にも地域的な偏りがなく、各配信要求は、独立に同一の確率分布に従い、ダウンロードするコンテンツを選択すると仮定する。
【００５９】
Ｗｅｂコンテンツのアクセス頻度分布は、Ｚｉｐｆ分布に従うが、Ｐ２Ｐサービスではコンテンツが更新される機会が少なく、一旦、ダウンロードしたコンテンツを、同一のピアが再度ダウンロードすることが少ない。
【００６０】
そのため、Ｐ２Ｐコンテンツのアクセス頻度分布は、高人気のコンテンツの要求頻度がＺｉｐｆ分布と比較して低減した、Ｍａｎｄｅｌｂｒｏｔ−Ｚｉｐｆ分布に従うことが知られている。
【００６１】
すなわち、コンテンツを人気の高い順に並べたときの人気順位がｋ番目のコンテンツに対するアクセス頻度ｑｋは、ｑｋ＝ｃ／（ｋ+ｑ）αで与えられる。尚、ｃは正規化定数で、「ｃ＝１／Σｉ＝１Ｍｑｉ」であり、αはアクセス頻度の低減度合を決めるパラメタ、ｑは高人気コンテンツのアクセス頻度のＺｉｐｆ分布と比較した低下度合いを決めるパラメタである。
【００６２】
各配信要求に対して、配信元ピアが要求されたコンテンツを保有するピアの中からランダムに一つ選択すると仮定する。
【００６３】
配信元となるノードは人口比ｒｉに比例する確率で選択されることになる。
【００６４】
配信フローは、リンク重みを１としたＯＳＰＦ（Ｏｐｅｎ  Ｓｈｏｒｔｅｓｔ  Ｐａｔｈ  Ｆｉｒｓｔ）により経路が設定され（最短ホップの経路が用いられる）、任意のノードｉとノードｊ間の配信経路上のホップ長（最短ホップ長）をｈｉｊとする（ただしｈｉｉ＝０と定義）。
【００６５】
以上の『前提条件』のもとでの『動的計画法（コンピュータ科学の分野において、ある最適化問題を複数の部分問題に分割して解く際に、そこまでに求められている以上の最適解が求められないような部分問題を切り捨てながら解いていく技術）を用いたキャッシュ最適設計法』について説明する。
【００６６】
『動的計画法を用いたキャッシュ最適設計法』
本例では、キャッシュを用いてＰ２Ｐトラヒック量を削減するための具体的な目標として、与えられたＮＷトポロジとＰ２Ｐ配信要求量（「需要量」）に対して、ＮＷを構成する各リンクを流れるＰ２Ｐトラヒック量を全てのリンクに対して足し合わせたものを最小化することを考える。
【００６７】
このことは、転送バイトあたりの配信フローの平均ホップ長ｈを最小化することと等価である。ただし、コンテンツｍの配信フローの平均ホップ長を「ｈｍ」とすると、当該平均ホップ長ｈｍは次の数１の式で与えられる。
【００６８】
【数１】
2010199842.tif 000003
【００６９】
各キャッシュの容量を大きくするほど、バイトヒット率が向上し、さらに、多数のキャッシュをＮＷ上に設置するほど、ＮＷ全体での「転送バイトあたりの配信フローの平均ホップ長ｈ」が低減することが予想されるが、キャッシュ設置に要するコストが増大する。
【００７０】
そこで、本例では、ＮＷ全体で用意するキャッシュの総容量をＣ（ｂｙｔｅ）として制約条件を与え、この制約条件のもとで、キャッシュ配置ノードと各キャッシュの容量を最適設計することを考える。
【００７１】
すなわち、ノードｉに設置するキャッシュの容量をＣｉとすると（キャッシュを設置しない場合Ｃｉ＝０となる）、「Σｉ＝１ＮＣｉ＝Ｃ」が制約条件となる。
【００７２】
図１におけるトランジットＩＳＰが、ＮＷ１０において、下位のＮＷ１１，１２との接続点（接続リンク１０ｈ，１０ｉ；Ｃａｃｈｅ  ｌｏｃａｔｉｏｎ−Ｂ）にキャッシュを設置する場合、各々のキャッシュを経由するフローは、キャッシュが設置された下位のＮＷに収容されているピアを配信先か配信元とするフローに限定される。
【００７３】
ただし、下位のＮＷ１１，１２に収容されたピア１１ｂ〜１１ｄ，１２ｂ〜１２ｄが配信元であるフローに対しては、そのキャッシュを用いても、トランジットＩＳＰのＮＷ１０上の経由ホップ長は変化しないため、下位のＮＷ１１，１２に収容されたピア１１ｂ〜１１ｄ，１２ｂ〜１２ｄが配信先であるフローに対してのみキャッシュから配信する効果がある。
【００７４】
例えば、図１において、下位のＮＷ１１におけるピアＳｘ１１ｃから下位のＮＷ１２におけるピアＲｙ１２ｂに対してのＰ２Ｐフローと、下位のＮＷ１２におけるピアＳｙ１２ｃから下位のＮＷ１１におけるピアＲｘ１１ｂに対するＰ２Ｐフローが存在するとき、これらは共にコアルータ１０ｅの下位のＮＷ１２との接続リンク１０ｈ（Ｃａｃｈｅ  ｌｏｃａｔｉｏｎ−Ｂ）に設置されたキャッシュを経由しての、計測対象となるが、下位のＮＷ１１におけるピアＳｘから下位のＮＷ１２におけるピアＲｙに対するＰ２Ｐフローのみが、接続リンク１０ｈに設置されたキャッシュからの配信対象となり得る。
【００７５】
そのため、あるノードにキャッシュを設置しても、その効果はキャッシュを設置したノードに収容されたピアに限定され、他のノードに収容されたピアには全く影響を与えない。
【００７６】
一般的に、あるノードにキャッシュを設置することによる効果がＮＷ全体に及ぶ場合、設置する各キャッシュの容量を一定とした場合にも、解くべき問題はＵＫＭやＵＦＬとなりＮＰ困難な問題となる。
【００７７】
そのため、各配置キャッシュの容量を合わせて最適設計する場合、問題はさらに複雑となり、多項式時間で解ける厳密解法は存在しない。
【００７８】
しかし、下位のＮＷ１１，１２との接続点（接続リンク１０ｈ，１０ｉ）にのみキャッシュを設置する場合には、上述したように、各ノードにキャッシュを設置することによる効果がＮＷ全体に波及せず、そのノードに限定されるため、最適性の原理を利用して動的計画法を用いて多項式時間で厳密最適解を得ることが可能である。
【００７９】
以下、このように、下位のＮＷ１１，１２との接続点（接続リンク１０ｈ，１０ｉ）にのみキャッシュを設置することに限定することにより、各配置キャッシュの容量を合わせて最適設計する際に、最適性の原理を利用して動的計画法を用いて、多項式時間で厳密最適解を得る手続きを説明する。
【００８０】
一般に、Ｎ個の変数ｘ１，ｘ２，…，ｘＮを、制約条件「Σｎ＝１Ｎｘｎ＝ａ，ｘｎ≧０」のもとで、目的関数ｆ（ｘ１，…，ｘＮ）を最適化する最適化問題において、ｆ（ｘ１，…，ｘＮ）が、「ｆ（ｘ１，…，ｘＮ）＝ｆ１（ｘ１）+ｆ２（ｘ２）+  …  +ｆＮＮ（ｘＮ）」の形であるとき、最適性の原理に従い、下記の数２の式で示す形式の再帰方程式に変換し、動的計画法によって解くことが可能となる。
【００８１】
【数２】
2010199842.tif 000004
【００８２】
本例で検討するキャッシュ最適配置問題は、各ノードのキャッシュの効果が他のノードのキャッシュの有無や容量に影響されず、そのキャッシュの容量のみで決まることから、動的計画法が適用可能な形式の目的関数を構築することが可能である。
【００８３】
各コンテンツのサイズｂｍは一定ではないが、キャッシュを設計する際には全てのコンテンツのサイズを平均値Ｂの固定値で考え、キャッシュ容量ＣｉをＢの整数倍で設計する。
【００８４】
ＬＳＢ（Ｌｅａｓｔ  Ｓｅｎｔ  Ｂｙｔｅ）を用いてキャッシュを更新する結果、アクセス頻度とコンテンツサイズの積ｘｍが大きなコンテンツがキャッシュに存在する可能性が高い。
【００８５】
そのため、平均的には、コンテンツｍの相対的なアクセス頻度ｑｍとサイズｂｍの積であるｙｍ（＝ｑｍｂｍ）の値が大きな、上位Ｃｉ個のコンテンツが、ノードｉに設置されたキャッシュに存在する可能性が高いといえる。
【００８６】
そこで、任意の整数ｋｉを用いてＣｉ＝ｋｉＢ（ｂｙｔｅ）で設計したとき、本キャッシュの設置で得られるバイトあたりの相対的な平均経由ホップ長の削減量をＤｉ（ｋｉ）とすると、次の数３の式で算出できる。
【００８７】
【数３】
2010199842.tif 000005
【００８８】
尚、上記数３の式において、ｑｓ（ｋ）は、ｙｍの値がｋ番目に大きいコンテンツの人気順位であり、また、Ｒｋは、本例で新しく定義する「辺境度（Ｒｅｍｏｔｅ  ｆａｃｔｏｒ）」と呼ぶ尺度であり、ノードｋが他のノードから離れている程度を表し、人口比ｒｊと、ノードｊとノードｋ間の平均ホップ長ｈｊｋを用いて、「Ｒｋ≡Σｊ＝１Ｎｒｊ・ｈｊｋ」と定義する。
【００８９】
各配信要求に対して配信元となるピアをランダムに選択した場合、配信元ピアがノードｉに属する確率は、ノードｉの人口比ｒｉに比例するため、辺境度Ｒｉは、キャッシュを用いないでノードｉに属するピアに対してＰ２Ｐ配信を行った場合の平均的な経由ホップ数に相当する。
【００９０】
平均経由ホップ長の削減量Ｄｉ（ｋｉ）の総和をＤ（ｋ）と定義すると（Ｄ（ｋ）≡Σｉ＝１ＮＤｉ・ｋｉ））、本例のシステムでの処理対象であるキャッシュ最適設計問題は、この総和Ｄ（ｋ）を最大化する問題となりので、動的計画法で解くことが可能である。
【００９１】
尚、設置するキャッシュの容量があまりに小さい場合には、キャッシュの効果が期待できない反面、設置や運営に伴うコストが発生するため、設置キャッシュ容量Ｃｉに許容下限値Ｃｍｉｎ（ｂｙｔｅ）を設定する。
【００９２】
また、Ｍ個のコンテンツのサイズの総量ＭＢを超えてキャッシュ容量を設計しても、キャッシュの効果は一定であるため、設置キャッシュ容量Ｃｉの許容上限値としてＣｍａｘ＝ｍｉｎ｛ＭＢ，Ｃ}（ｂｙｔｅ）を設定する。
【００９３】
また、設置キャッシュ容量Ｃｉの許容下限値Ｃｋｍｉｎと許容上限値Ｃｍａｘに相当する整数ｋｉの限界値を、各々、下限値ｋｍｉｎと上限値ｋｍａｘとする（ｋｍｉｎ＝ｓｕｐ（Ｃｍｉｎ／Ｂ），ｋｍａｘ＝ｉｎｆ（Ｃｍａｘ／Ｂ））。尚、「ｓｕｐ（Ｃｍｉｎ／Ｂ）」は、（Ｃｍｉｎ／Ｂ）の上限を、「ｉｎｆ（Ｃｍａｘ／Ｂ）」は（Ｃｍａｘ／Ｂ）の下限を表す。
【００９４】
また、ＮＷ全体で用意するキャッシュの総容量Ｃに相当する、整数ｋの値をＫとする（Ｋ＝ｉｎｆ（Ｃ／Ｂ））。
【００９５】
このとき、動的計画法を用いた最適キャッシュ設計法は、以下の数４に示す再帰方程式で記述できる。
【００９６】
【数４】
2010199842.tif 000006
【００９７】
この数４の再帰方程式を、ｉ＝１から順にｉ＝Ｎまで、全ての可能なａｉの値に対して各々解き、最終的にφＮ（Ｋ）を与える整数ｋ１，ｋ２，…，ｋＮが、各ノードに設置すべき最適なキャッシュ容量として得られる。
【００９８】
「Ｓ」をキャッシュ容量の取り得る最大パタン数とすると、「Ｓ＝ｍａｘ｛ｍｉｎ｛Ｎｋｍａｘ，Ｋ｝，ｋｍａｘ｝であり、最適設計に要する計算時間はＯ（ＮＳ２）となり、多項式時間で厳密最適解を得ることが可能である。
【００９９】
次に、図３，図４を用いて、本例のキャッシュ設計システムの『性能評価』について説明する。
【０１００】
『性能評価』
まず、『性能評価に用いたＮＷ』について説明する。
【０１０１】
評価には、ＣＡＩＤＡ（Ｃｏｏｐｅｒａｔｉｖｅ  Ａｓｓｏｃｉａｔｉｏｎ  ｆｏｒ  Ｉｎｔｅｒｎｅｔ  Ｄａｔａ  Ａｎａｌｙｓｉｓ：ＤＮＳ、ルーティング、パフォーマンスなど、インターネットに関する多様なモニタリングや分析の活動を、他の組織や個人との協力で実施しているプロジェクト）のＷｅｂページで公開されている商用ＩＳＰバックボーンＮＷの中で、ノード数Ｎが１０以上の３１個のＮＷトポロジを用いる。
【０１０２】
図３に、これら３１個のＮＷのノード数Ｎ、リンク数Ｌ、平均ノード次数、最大ノード次数、および、重み付け平均ノード間距離ＷＡＨ（Ｗｅｉｇｈｔｅｄ  Ａｖｅｒａｇｅ  Ｈｏｐ  Ｄｉｓｔａｎｃｅ）をまとめた状態を示す。
【０１０３】
キャッシュを用いない場合、ノードｉを発ノード、ノードｊを着ノードとするＰ２Ｐトラヒック交流量のＮＷ全体の交流Ｐ２Ｐトラヒック量に対する比率ｒｉｊは、発着ノードの人口の積に比例し、「ｒｉｊ＝ｐｉｐｊ／Σｍ＝１ＮΣｎ＝１Ｎｐｍｐｎ」となる。
【０１０４】
重み付け平均ノード間距離ＷＡＨは、比率ｒｉｊで重み付けた配信フローの平均ホップ長であり、「Σｉ＝１ＮΣｊ＝１Ｎｒｉｊｈｉｊ」で定義する。
【０１０５】
また、図４（ａ）においては、３１個の各々のＮＷについて、最大次数比率（最大ノード次数をノード数Ｎで除した値）を平均ノード次数に対してプロットした状態を示している。
【０１０６】
本図４（ａ）に基づき、便宜上、これら３１個のＮＷを、以下の「Ｈ＆Ｓ」と「Ｌａｄｄｅｒ」の二つの種別に分類する。  
【０１０７】
「Ｈ＆Ｓ」：ハブ＆スポーク型と呼ばれるＮＷ種別であり、高次数のハブノードが存在し、最大ノード次数が大きい。ハブノードを経由して多数のノードに到達できるため、平均ホップ長が短い傾向がある。ここでは、最大次数比率が０．４以上か、もしくは平均次数が３以上のＮＷと定義する。図４（ａ）においては１８個のＮＷが該当する。
【０１０８】
「Ｌａｄｄｅｒ」：高次数ノードが存在せず、ループを組み合わせたトポロジ構造となる。リンク総延長を抑えられる反面、遠方のノードに到達するためには、多数のノードを経由する必要があり、平均ホップ長が長い傾向がある。ここでは、最大次数比率が０．４未満かつ平均次数が３未満のＮＷと定義する。図４（ａ）においては１３個のＮＷが該当する。
【０１０９】
図３においては、各々のＮＷに対して該当するＮＷ種別もあわせて表記している。
【０１１０】
また、図４（ｂ）において、３１個の各々のＮＷに対して算出された、平均辺境度（Σｉ＝１ＮＲｉ／Ｎ）を、重み付け平均ノード間距離ＷＡＨに対してプロットしている。重み付け平均ノード間距離ＷＡＨと平均辺境度には正の強い相関性があること、および、Ｌａｄｄｅｒ型ＮＷは、Ｈ＆Ｓ型ＮＷと比較してこれら値が大きい傾向があることが確認できる。
【０１１１】
次に、『評価条件』について説明する。
【０１１２】
各ノードにおいてｒｉの比率でＰ２Ｐ配信要求をポアソン過程で発生させ、ＮＷ全体での要求発生レートΛを、Λ＝１／秒に設定した。コンテンツ数をＭ＝１０００に設定し、コンテンツの選択確率ｑ（ｍ）を決める、Ｍａｎｄｅｌｂｒｏｔ−Ｚｉｐｆ分布のパラメタα（アクセス頻度の低減度合を決めるパラメタ）と、パラメタｑ（高人気コンテンツのアクセス頻度のＺｉｐｆ分布と比較した低下度合いを決めるパラメタ）を、Ｇｎｕｔｅｌｌａの８カ月間に渡るアクセスログ解析から得られた値であるα＝０．７５、ｑ＝３に設定した。
【０１１３】
発着ノード間に最短ホップとなる経路が複数存在する場合には、それらの中から一つを配信要求ごとにランダムに選択した。
【０１１４】
各キャッシュ設置ノードにおいて、上述の『前提条件』において述べた方法で、コンテンツごとに、各コンテンツｍの単位時間あたりの配信要求数とコンテンツサイズとの積の値ｘｍを算出してキャッシュを更新するが、初めて配信要求のあったコンテンツに対しては、この値ｘｍが無限大になるため、二回以上配信要求のあったコンテンツのみをキャッシュ対象とした。
【０１１５】
ＢｉｔＴｏｒｒｅｎｔ（登録商標）の実測によって得られたコンテンツのサイズ分布は、おおよそ１０Ｍｂｙｔｅのものが８％、１００Ｍｂｙｔｅのものが２８％、３００Ｍｂｙｔｅのものが４０％、７００Ｍｂｙｔｅのものが１１％、そして１．４Ｇｂｙｔｅのものが１３％であったことから、この分布に一致するようランダムに各コンテンツのサイズｂｍを設定した。平均コンテンツサイズＢは４００Ｍｂｙｔｅ、キャッシュ容量の上限は４００Ｇｂｙｔｅとなる。また、キャッシュ容量の下限を１０Ｇｂｙｔｅに設定した。
【０１１６】
以上の条件での『キャッシュ配置結果』を以下に説明する。
【０１１７】
図５に、全キャッシュ容量Ｃを０．３Ｔｂｙｔｅ、１Ｔｂｙｔｅ、３Ｔｂｙｔｅとした場合の各々について、３１個の各々のＮＷにおける設置キャッシュ数と全ノード数Ｎの散布図（図５（ａ）、図５（ｃ）、図５（ｅ））と、各キャッシュ設置ノードの設計容量と人口比の散布図（図５（ｂ）、図５（ｄ）、図５（ｆ））を各々示す。
【０１１８】
図５（ａ），（ｂ）に示すように、総キャッシュ容量が小さい場合（０．３Ｔｂｙｔｅ）、人口比が大きくキャッシュ設置が効果的なノードに、集中的にキャッシュが配置される。全ノード数Ｎが増加しても人口比の大きなノード数はあまり増加しないため、設置キャッシュ数は、ノード数Ｎとはほとんど無関係となっている。また、図５（ｅ），（ｆ）に示すように、全キャッシュ容量Ｃの増加に伴い、より人口比の小さいノードにもキャッシュが配置されることが確認できる。
【０１１９】
次に、図６を用いて、本例のシステムによる『Ｐ２Ｐトラヒック削減効果』を説明する。
【０１２０】
キャッシュを用いない場合のコンテンツｍの配信フローの平均ホップ長をｈｏ（ｍ）、キャッシュを最適設計した場合のコンテンツｍの配信フローの平均ホップ長をｈｃ（ｍ）とするとき、転送バイトあたりの経由ホップ長の平均削減量ｘｉを、「ξ＝Σｍ＝１Ｍｑｍｂｍ（ｈｃ（ｍ）−ｈｏ（ｍ））」で定義する。
【０１２１】
図６（ａ）においては、平均削減量ｘｉを、各ノードの人口比ｒｉと辺境度Ｒｉの相関係数に対してプロットしている。各キャッシュの効果は、配置したノードの人口比ｒｉと辺境度Ｒｉの積と正の相関があるため、これら尺度間の相関性が大きいＮＷほど、キャッシュの効果が高い。
【０１２２】
また、図６（ｂ）においては、各ＮＷに対して、平均削減量ｘｉを平均辺境度に対してプロットしている。Ｌａｄｄｅｒ型ＮＷは、平均辺境度が、Ｈ＆Ｓ型ＮＷと比較して大きく、平均辺境度がキャッシュの効果に与える影響が強い。そのため、Ｌａｄｄｅｒ型ＮＷにおいては、辺境度とキャッシュの効果に正の相関性が見られる。
【０１２３】
このように、本例では、トランジットＩＳＰが自身のＮＷ１０内を流れるＰ２Ｐトラヒック量の削減を目的に、当該ＮＷ上にキャッシュを配置する場合において、各リンクにおけるＰ２Ｐトラヒック量の平均を全リンクに対して足し合わせた総量を最小化するよう、ＮＷ１０に設置する各キャッシュの容量を、与えられたＮＷトポロジと需要量を用いて算出する。
【０１２４】
より具体的には、図７に示すように、入力処理部１００により、入力装置を介して入力されたネットワークトポロジ情報と需要量を記憶装置１０１に格納し（ステップＳ７０１）、キャッシュ最適設計処理部１０２において、記憶装置１０１からネットワークトポロジ情報と需要量を読み出し、このネットワークトポロジ情報と需要量を用いて、当該トランジットＮＷ１０の各リンクにおけるトラヒック量の平均の合計が最小化するよう、当該トランジットＮＷ１０に設置する各キャッシュの容量を算出し（ステップＳ７０２）、そして、出力処理部１０３により、キャッシュ最適設計処理部１０２が算出した、当該トランジットＮＷに設置する各キャッシュの容量を出力する（ステップＳ７０３）。
【０１２５】
尚、ネットワークトポロジ情報として、トランジットＮＷ１０における下位ＮＷ１１，１２との接続リンク１０ｈ，１０ｉのみをキャッシュの設置個所とした情報を含み、キャッシュ最適設計処理部１０２は、下位ＮＷ１１，１２との接続リンク１０ｈ，１０ｉに設置する各キャッシュの容量を、動的計画法を用いた多項式時間での厳密最適解として算出する。
【０１２６】
また、入力処理部１００は、入力装置を介して入力されたキャッシュ容量の下限制約値と上限制約値を記憶装置１０１に格納し、キャッシュ最適設計処理部１０２は、記憶装置１０１からネットワークトポロジ情報と需要量およびキャッシュ容量の下限制約値と上限制約値を読み出し、読み出したネットワークトポロジ情報と需要量およびキャッシュ容量の下限制約値と上限制約値を用いて、キャッシュ容量の下限制約値と上限制約値の範囲内で各キャッシュの容量を算出する。
【０１２７】
以上、図１〜図７を用いて説明したように、本例では、トランジットＩＳＰが自身のＮＷ１０内を流れるＰ２Ｐトラヒック量の削減を目的に、当該ＮＷ上にキャッシュを配置する場合において、各リンクにおけるＰ２Ｐトラヒック量の平均を全リンクに対して足し合わせた総量を最小化するよう、ＮＷ１０に設置する各キャッシュの容量を、与えられたＮＷトポロジとＰ２Ｐ配信要求量（需要量）を用いて算出する。
【０１２８】
このように、本例では、各キャッシュの配置拠点を特定する際に、各キャッシュの容量を考慮し、キャッシュの容量も含めたキャッシュ配置個所の最適設計を行うことにより、効果的なＰ２Ｐトラヒックの削減が可能である。
【０１２９】
尚、本発明は、図１〜図７を用いて説明した例に限定されるものではなく、その要旨を逸脱しない範囲において種々変更可能である。例えば、本例では、下位ＮＷ１１，１２と接続されたトランジットＮＷ１０におけるキャッシュを例に説明しているが、このようなトランジットＮＷ１０におけるキャッシュを対象とするものに限定されない。
【０１３０】
例えば、各々接続された複数のネットワークのそれぞれに設置するキャッシュの最適容量を算出するキャッシュ設計システムとして、入力装置を介して入力されたネットワークトポロジ情報と需要量を記憶装置に格納する入力処理部と、記憶装置からネットワークトポロジ情報と需要量を読み出し、読み出したネットワークトポロジ情報と需要量を用いて、当該ネットワークの各リンクにおけるトラヒック量の平均の合計が最小化するよう、当該ネットワークに設置する各キャッシュの容量を算出するキャッシュ最適設計処理部と、このキャッシュ最適設計処理部が算出した、当該ネットワークに設置する各キャッシュの容量を出力する出力処理部とを設けた構成とすることでも良い。
【０１３１】
そして、このようなキャッシュ設計システムにおいて、ネットワークトポロジ情報として、他のネットワークとの接続リンクをキャッシュの配置個所とした情報を含み、キャッシュ最適設計処理部が、他のネットワークとの接続リンクに設置するキャッシュの容量に対して、ネットワークの各リンクにおけるトラヒック量の平均の合計を最小化する算出を行うことでも良い。
【０１３２】
さらに、入力処理部が、入力装置を介して入力されたキャッシュ容量の合計値を記憶装置に格納し、キャッシュ最適設計処理部が、記憶装置からネットワークトポロジ情報と需要量およびキャッシュ容量の合計値を読み出し、これらのネットワークトポロジ情報と需要量およびキャッシュ容量の合計値を用いて、各キャッシュの容量の算出を行うことでも良い。
【符号の説明】
【０１３３】
１００：入力処理部、１０１：記憶装置、１０２：キャッシュ最適設計処理部、１０３：出力処理部（「キャッシュ最適設計結果出力処理部」）。
【図１】
2010199842.tif 000009
【図２】
2010199842.tif 000010
【図３】
2010199842.tif 000011
【図４】
2010199842.tif 000012
【図５】
2010199842.tif 000013
【図６】
2010199842.tif 000014
【図７】
2010199842.tif 000015